Integrating local and partial network view for routing on scale-free networks  

作　　者：TANG MingDong ZHANG GuoQiang SUN Yi LIU JianXun YANG Jing LIN Tao 

机构地区：[1]Key Lab of Knowledge Processing and Networked Manufacturing, Hunan University of Science and Technology [2]School of Computer Science and Technology, Nanjing Normal University [3]Institute of Computing Technology,Chinese Academy of Sciences [4]China Mobile Research Institute [5]Institute of Acoustics,Chinese Academy of Sciences

出　　处：《Science China(Information Sciences)》2013年第10期117-126,共10页中国科学（信息科学）（英文版）

基　　金：partly supported by National Basic Research Program of China(Grant No.2012CB315802);National Natural Science Foundation of China(Grant Nos.61020106002,61100178,61100054,60973129);Startup Foundation of Nanjing Normal University(Grant No.2011119XGQ0248)

摘　　要：Traditional routing schemes, such as OSPF, optimize data plane routing efficiency by maintaining full view of the network at the control plane. However, maintaining full network view and handling frequent routing information updates are costly in large-scale complex networks, which are considered to be the root causes for the routing scalability issue. Recently, it is suggested that routing on local or partial information is plausible if slight performance degradation is acceptable. This paper proposes a routing scheme, operating on an integrated network view at each node that consists of its local neighborhood and a globally unique skeleton tree. This scheme significantly reduces storage, communication and processing costs. On scale-free networks, this benefit only comes at the cost of marginal performance degradation, which implies that it is not worthwhile to do shortest path routing based on full view of the network on scMe-free networks. In contrast, the routing efficiency is severely aggravated on purely random networks, indicating the inappropriateness of this scheme and the rationality of maintaining full network view on random networks.Traditional routing schemes, such as OSPF, optimize data plane routing efficiency by maintaining full view of the network at the control plane. However, maintaining full network view and handling frequent routing information updates are costly in large-scale complex networks, which are considered to be the root causes for the routing scalability issue. Recently, it is suggested that routing on local or partial information is plausible if slight performance degradation is acceptable. This paper proposes a routing scheme, operating on an integrated network view at each node that consists of its local neighborhood and a globally unique skeleton tree. This scheme significantly reduces storage, communication and processing costs. On scale-free networks, this benefit only comes at the cost of marginal performance degradation, which implies that it is not worthwhile to do shortest path routing based on full view of the network on scMe-free networks. In contrast, the routing efficiency is severely aggravated on purely random networks, indicating the inappropriateness of this scheme and the rationality of maintaining full network view on random networks.

关 键 词：ROUTING scale-free networks complex networks POWER-LAW 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]