HDLBR: A name-independent compact routing scheme for power-law networks

Compact routing intends to achieve a good tradeoff between routing path length and storage overhead, and is recently considered as a main alternative to overcome the fundamental scaling limitations of the Internet routing system. It is generally believed that specialized compact routing schemes for peculiar network topologies have better average performance than universal ones, and name-independent schemes are more flexible due to their natural support of the Locator/ID split principle. In this paper, we propose the highest degree landmark based routing scheme (HDLBR), which is the first specialized name-independent compact routing scheme for Internet-like power-law networks. HDLBR optimizes routing performance by selecting a few nodes with high degrees as the landmarks and making these nodes to be the entrances for mapping topologically agnostic node names to topology-aware node addresses. Simulation results show that HDLBR has very small average routing table size, in the order of O∼(n1/2) bits per node on both synthesized power-law graphs and the real AS graphs. Meanwhile, the average stretch of the HDLBR scheme is comparable with the base Abraham scheme using random coloring, and is only slightly outperformed by the customized Abraham scheme which also takes into account the degree heterogeneity of power-law networks.