%0 Journal Article
%T Compact Routing Scheme for Scale-Free Networks<br>针对无标度网络的紧凑路由方法
%A TANG Ming-Dong
%A ZHANG Guo-Qing
%A YANG Jing
%A ZHANG Guo-Qiang
%A <br>唐明董
%A 张国清
%A 杨 景
%A 张国强
%J 软件学报
%D 2010
%I 
%X 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.
%K compact routing
%K scale-free network
%K network topology
%K simulation
%K stretch<br>紧凑路由
%K 无标度网络
%K 网络拓扑
%K 仿真
%K 伸长系数
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=3387D44DF598374A52695D3058A6003C&yid=140ECF96957D60B2&vid=659D3B06EBF534A7&iid=DF92D298D3FF1E6E&sid=48603EE1050A0BB7&eid=4477555D45FDE796&journal_id=1000-9825&journal_name=软件学报&referenced_num=2&reference_num=24