Compact Routing Scheme for Scale-Free Networks
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    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(clog2n) 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.

    Reference
    Related
    Cited by
Get Citation

唐明董,张国清,杨 景,张国强.针对无标度网络的紧凑路由方法.软件学报,2010,21(7):1732-1743

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 09,2008
  • Revised:January 15,2009
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063