Compact Routing on Random Power Law Graphs

Routing table size and route length are two key metrics for evaluating a routing scheme, and there is an obvious tradeoff between them, i.e. the space-stretch tradeoff. The generic shortest-path routing takes an extreme position by only optimizing the route length, hence the routing table size grows linearly with the network size. Compact routing refers to design of routing schemes with optimized space-stretch tradeoffs. The optimal universal compact routing scheme to date stores a O¿(n^1/2) routing table at each node with a stretch 3 for arbitrary networks. Researches on complex networks show that in most real-life networks the degree distribution exhibits a power law tail, i.e. a few nodes have a very high degree and many with low degree. The high-degree nodes play the important role of hubs in communication and networking. Aiming to achieve a better space-stretch tradeoff for routing in power law networks, we propose a high-degree landmark routing scheme. Through theoretical analysis on random power law graphs we show our scheme can almost surely provide a O¿(n^1/3) routing table at each node with a stretch 3. Simulations on random power law graphs and real Internet AS graph also show our scheme can outperform the optimal universal scheme.