Graph Embedding-Based Scalable Routing in Large Networks

It is important in large networks to use routes that are as short as possible while keeping routing tables small. Generic shortest-path routing does extremely well in optimizing routes, but each node has to maintain state for all nodes. Thus generic shortest-path routing does not scale well as routing table size grows linearly with network size. The authors study scalable routing via graph embedding, i.e. embedding networks into specific coordinate spaces such that packets can be delivered with greedy forwarding. However, generic embedding usually can not guarantee packet delivery. To obtain guaranteed delivery and high routing efficiency, the idea of embedding graph spanners is presented in this paper. Based on the fact that most real-world networks have small-world and scale-free topologies, a embedding & routing scheme is proposed, namely GEROUTE, which uses the shortest-path trees rooted at high-degree nodes as spanners, and assigns to each node a set of short labels such that the distance between any two nodes in the spanners can be inferred from their labels. Over the metric space defined by labels, each node only stores the labels of its neighbors and always picks the neighbor closest to the destination as next hop when routing packets. Analysis and simulations show that the scheme can perform particularly well on Internet-like graphs, outperforming prior related routing schemes.