Compact routing is recently considered as a main alternative to overcome the fundamental scaling limitations of the Internet routing system. The basic idea of compact routing is to balance between routing table size and path length. In addition, the quality of the path is quantitatively measured by stretch.

Generally speaking, 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.

For this reason, the highest degree landmark based routing scheme (HDLBR) is proposed, 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.

In order to provide an insight into the real performance of the proposed scheme on power-law networks, simulations are performed to compare HDLBR to the Abraham scheme (the first nearly-optimal universal name-independent scheme).

Simulation results show that HDLBR produces average routing table size on each node in the order of O∼n(1/2) bits, which is smaller than the two realizations of Abraham schemes. The average stretch produced by HDLBR is well below 1.2 for the power-law networks used in the simulation, comparable to the base Abraham scheme. It is about 10% larger than the customized Abraham scheme (Fig. 1). Hence, HDLBR achieves good tradeoff between average routing table size and average stretch on power-law graphs.

Fig. 1. Comparison of average stretches of the HDLBR scheme and Abraham schemes.

 Table 1. Comparison of the average stretch and routing table size between the HDLBR scheme and the Abraham scheme on three AS-level Internet topologies.

Table 1 gives the average stretch of the HDLBR scheme and the realizations of the Abraham scheme on three AS-level Internet topologies. It is observed that the HDLBR scheme has comparable or smaller average stretches than the base Abraham scheme, but is slightly outperformed by the customized Abraham scheme.

It is also noticed that recent proposals for Internet routing architecture strongly recommend Locator/ID separation (LIS) to support the scalability, mobility and security requirements of future Internet. Essentially, name-independent routing schemes implement the idea of LIS. However, despite its natural support of the LIS idea, all the performance evaluation of HDLBR is undertaken in static network environment. Understanding how it behaves in the dynamic environment is critical for developing a practically scalable routing protocol, which could be the future research direction.

This research entitled “HDLBR: A name-independent compact routing scheme for power-law networks”  was published online: http://www.sciencedirect.com/science/article/pii/S0140366412003210# and on the currently issued journal of Computer Communications (Vol. 36, No. 3, Pages 351–359, 1 February 2013).