HDLBR: A name-independent compact routing scheme for power-law networks
HDLBR: A name-independent compact routing scheme for power-law networks
复制标题
DOI：
10.1016/j.comcom.2012.09.009
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
Mingdong Tang;Guoqiang Zhang;T. Lin;Jianxun Liu
中科院分区：
文献类型：
--
作者：
Mingdong Tang;Guoqiang Zhang;T. Lin;Jianxun Liu
紧凑路由旨在实现路由路径长度和存储开销之间的良好权衡，最近被认为是克服互联网路由系统基本扩展限制的主要替代方案。一般认为，针对特殊网络拓扑的专用紧凑路由方案比通用路由方案具有更好的平均性能，而与名称无关的路由方案由于自然支持Locator/ID分割原则而更加灵活。在本文中，我们提出了基于最高度地标的路由方案（HDLBR），这是第一个针对类互联网幂律网络的专用名称无关的紧凑路由方案。HDLBR通过选择一些高度的节点作为路标，并将这些节点作为入口，将拓扑无关的节点名称映射到拓扑感知的节点地址，从而优化路由性能。仿真结果表明，HDLBR具有非常小的平均路由表大小，在合成幂律图和真实AS图上每个节点的平均路由表大小为O ~ （n1/2）位。同时，HDLBR方案的平均拉伸与使用随机着色的基本Abraham方案相当，仅略优于考虑幂律网络程度异质性的自定义Abraham方案。
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.