复杂网络与可扩展路由

Complex Network and Scalable Routing

互联网规模扩大,相应路由表大小呈指数增加,形成下一代互联网可扩展路由"瓶颈"。基于复杂网络和可扩展路由的相关理论与主要策略,文章对相关研究成果,如小世界效应所表现出来的特性、小世界和无标度网络模型,网格、层次及隐藏度量等3种可扩展路由网络模型,随机游走、贪婪、最大度、优先、本地介数、距离与度及相似性与度混合等多种路由策略等进行了分析与归纳。

With the Internet＇ s expansion, its routing table size increases exponentially, which is a bottleneck of routing scalability in the next generation Intemet. In this paper, we sums up and analyzes the important theories and strategies for complex networks and scalable routing. For complex networks, the characteristics of small-world effect, small-world network models and scale-free network model are discussed. As for scalable routing, the models of grid, hierarchical and hidden metric are described. Moreover, the routing strategies of random walk, greedy, maximum degree, preferentia choice, local betweenness centrality, distance-degree and homophily-degree are analyzed. These research results and methods will provide a solution to the problem of scalable routing brought by the Internet＇ s expansion.