Geohyperbolic Routing and Addressing Schemes

Ivan Voitalov, Rodrigo Aldecoa, Lan Wang, Dmitri Krioukov
ACM SIGCOMM Computer Communication Review
Volume 47 Issue 3, July 2017
July 31, 2017

Abstract

The key requirement  to routing in any telecommunication network, and especially in  Internet-of-Things (IoT) networks, is scalability. Routing must route packets  between any source and destination in the network without incurring  unmanageable routing overhead that grows quickly with increasing network size  and dynamics. Here we present an addressing scheme and a coupled network  topology design scheme that guarantee essentially optimal routing  scalability. The FIB sizes are as small as they can be, equal to the number  of adjacencies a node has, while the routing control overhead is minimized as  nearly zero routing control messages are exchanged even upon catastrophic  failures in the network. The key new ingredient is the addressing scheme,  which is purely local, based only on geographic coordinates of nodes and a  centrality measure, and does not require any sophisticated non-local  computations or global network topology knowledge for network embedding. The  price paid for these benefits is that network topology cannot be arbitrary  but should follow a specific design, resulting in Internet-like topologies.  The proposed schemes can be most easily deployed in overlay networks, and  also in other network deployments, where geolocation information is available,  and where network topology can grow following the design specifications.