针对无标度网络的紧凑路由方法

Compact Routing Scheme for Scale-Free Networks

衡量一种路由算法优劣的两个重要指标是路由表的大小和路径的长度,但这两个方面通常是互相矛盾的.紧凑路由(compact routing)研究旨在设计路由算法在这两个指标上获得优化的平衡(tradeoff).目前,已有许多学者针对任意拓扑的网络提出了普适(universal)的紧凑路由方法(compact routing scheme).但是,真实的网络都具有特定的拓扑,普适的紧凑路由方法并没有利用真实网络呈现的特定拓扑特征,因而在这类网络上未必能取得最优的性能.最近的研究发现,许多真实网络都具有无标度特征和强聚集特征,利用这两类拓扑特征,提出了一种针对这类网络的紧凑路由方法.该路由方法将网络看成是由一个骨干树和一些捷径组成,在任意源节点和目的节点之间路由,使用路径的长度不超过它们的最短路径长度加上一个整数b.路由表大小限制在O(clog2n)比特,其中,b和c是由网络结构决定的参数.实验结果表明,在无标度网络上,b和c可以同时取较小的值.与以往的紧凑路由方法相比,该方法在平均性能上表现更好.

Routing table size and routing path length are two critical measures for evaluating a routing algorithm, and there exists a tradeoff problem between them. Compact routing refers to the design of routing algorithms obtaining relatively optimal tradeoffs between the above two measures. So far, researchers have proposed quite a few universal compact routing schemes, which have high optimized bounds on routing table size and path length for arbitrary network topologies. However, as real-world networks usually have specific topologies, the universal schemes are possibly sub-optimal on them for not exploiting the topological properties. Recent work discovered many real-world networks had scale-free topologies. By exploiting the power-law and strong clustering features, a compact routing scheme with additive stretch for this class of networks is presented in this paper. By separating a network into a backbone tree and shortcuts, this scheme ensures between any source node and destination node in a network, the routing path length is at most an additive factor of b longer than the shortest path between them, and the local routing table at each node is upper bounded by O（clog^2n） bits, wherein b and c are parameters related to the network topology. Experimental results show that b and c have small values in scale-free networks, and the proposed scheme can achieve better average-case performance than known schemes.