复杂网络与可扩展路由

基金项目：中国博士后科学基金资助项目(20070420782)

    为揭示复杂系统内在特征、规律和行为，常利用网络描述其结构，节点代表系统内部各个体，链接代表个体间关系。随机图论是复杂系统研究的早期基础理论。近10年来，复杂网络作为一门新兴网络科学悄然升起，目前逐步成为复杂系统研究的重要理论和国际科学前沿研究课题之一。其主要研究内容包括[1]：揭示刻画复杂系统的统计性质，建立适合的复杂系统网络模型，分析预测复杂系统的行为，提出已有网络性能改进和新型网络设计的有效方法。

    随着互联网规模的不断扩大，路由表大小呈指数增长，庞大的路由表对路由系统造成了巨大负担[2]。因此，近年来互联网络由系统规模可扩展性问题受到普遍关注[3]。尽管目前还没有对路由系统的规模可扩展性限制作任何形式化分析，但学术界达成了如下共识：路由系统规模可扩展性是下一代互联网多维可扩展的基础，是加快部署具有庞大地址空间的IPv6协议的突破口。如何在海量地址空间范围内实现高效路由，不管在理论上还是技术上，仍然是没有解决的难题，面对如此巨大的地址空间，理想的路由一定是规模可扩展路由，随着网络规模的不断扩大能够自适应的路由。

1 复杂网络

1.1 小世界效应
    1967年，Milgram[4]做了一个实验：随机选定两个目标对象和一批志愿者，要求这些志愿者通过其所认识的人，用自己认为尽可能少的传递次数，设法把一封信最终转交到一个给定的目标对象手中，并要求每个节点只能向其朋友转交一封信。实验结果显示，大约30%的信平均经过6跳成功达到目标对象。显然，该实验的研究对象为人表示节点、人与人之间的朋友或邻居关系表示链接的社会网络，其揭示了社会网络具有小世界效应：较短的平均路径长度，短路径的可搜索性。同时，该实验提出了两个基本问题：社会网络为什么能实现搜索？可搜索网络的结构是怎样的？这项研究结果发现引发了小世界网络直径、小世界网络模型及其中的搜索与导航等方面的一系列研究。

1.2 小世界网络模型
    1998年，Watts和Newman等人[5-6]率先对具有小世界效应的网络进行形式化建模，提出了WS小世界网络模型和NW小世界网络模型。WS小世界模型的构造方法如下：n 个节点围成一个环，每个节点都与它左右相邻的各K /2节点相连，K 为偶数；以概率p随机地重新连接网络中的每个边。而在NW小世界模型的构造方法中则以概率p 在随机选取的一对节点之间加上一条边。显然，小世界网络是完全规则网络到完全随机网络的过渡。研究表明，小世界模型具有两个重要性质：较短的平均路径长度(约为logn)和较高的聚类系数。小世界模型和随机模型的共同特征是所有节点的度都近似相等，度分布可以近似用泊松(Poisson)分布来表示，这类网络也称为均匀网络或指数网络。

1.3 无标度网络模型
    Faloutsos等[7]以自治域为节点，以两个域边界路由器间连接边，对自治域层次上Internet拓扑进行研究，发现它的度分布为幂律分布：p(k )～k -γ，其中k为节点度，p (k )为k度节点的概率，γ为幂指数。相对于指数分布，幂率分布中低度节点数量多，而高度节点数量少，且不存在随机网络的特征标度，故被称为无标度特性。Barabasi和Albert[8]提出了一种无标度网络模型，其构造方法如下：从一个具有m0个节点的网络开始，每次引入一个新节点，并且连到m(≤m 0)个已存在的节点上；一个新节点与一个已存在的节点i 相连接的概率pi 为：  Ki /∑kj

    其中:ki为节点i 的度，kj为节点j 的度。

    无标度模型具有两个特性：增长特性和优先连接特性。研究表明，无标度网络具有较短的平均路径长度为logn，或甚至为logn /(loglogn)。

2 可扩展路由网络及模型

2.1 可扩展路由
    路由是指将信息从一个节点传递到另一个节点的过程，信息传递过程中所经历的理想路径为两节点之间的最短路径。为了找到最短路径，节点必须掌握整个网络的全局拓扑信息，路由表大小随网络规模呈指数增长，路由可扩展性能很差。反之，完全不了解拓扑信息，也不可能实现路由功能。可扩展路由是不随网络规模增大而导致其性能快速降低的路由，即节点只需掌握局部拓扑信息(如邻居节点和目标节点信息等)。最短路径是基于网络全局拓扑信息发现的，在局部拓扑信息情况下，一般只能找到比最短路径长的路径。
可扩展路由定义为基于局部拓扑信息就可以发现较短路径的路由。研究表明，并不是所有网络均能实现可扩展路由。可扩展路由网络具有节点度异质性，或小的直径和高聚集系数等特性。利用局部信息可以发现较短路径的网络称为可扩展路由网络。下面给出了几种典型的可扩展路由网络模型。

2.2 网格模型
    Kleinberg提出了一种可扩展路由网格模型[9]：网络中的n 个节点分布在一个D 维网格上，距离r 定义为两节点间的网格步数。一个节点通过短程连接或长程连接与网格中的其他节点相连，短程连接与距离不超过大于等于1的邻居节点相连，长程连接与其他非邻居节点相连，两个节点之间有长程连接的概率与r -α成正比，α≥0。网格模型是WS小世界模型的一般化形式。当固定短程链接网络距离和长程连接数目，且α=0时，网格模型就为WS小世界模型。

    基于局部拓扑信息(包括网格结构、目标节点位置和路由路径上节点位置及其长程连接)的贪婪路由策略，即节点将信息传给离目标节点最近的短程连接或长程连接邻居节点，证明了如下定理[10]：
在二维情况下(D =2)，当α=2时，存在最优可扩展路由算法，其平均传递步数为O ((logn )2)；当0≤α<2时，路由算法的平均传递步数为Ω(n(2-α)/3)；当α>2时，路由算法的平均传递步数为Ω(n(2-α)/(α-1))。

    由此可见，在WS小世界模型中(α=0)，路由算法找到的路径(Ω(n(2/3))比其最短路径长度(O(logn))要大；在Kleinberg模型中，当α=D时，可扩展路由性能表现最佳，这说明了只有具有特定拓扑特性的网络上才能实现有效的可扩展路由。

2.3 层次模型
    网格模型中的距离是基于地理位置的，Watts等人[11]提出了一种基于社会距离的层次模型，在该模型中，职业、地理位置、兴趣等特性相同或相近的个体(即节点)组成最低层群，最底层群根据它们的共同特性聚集成规模更大的上层群，直到聚集成一个最高层群，得到一个层次网络。在层次模型中，节点间的社会距离定位为yij =minxijh,h =1,2,…,H，其中xij为节点i 和节点j 最低的共同上级所在的层数为它们之间的距离，H为分层标准重数。最底层同一群中两节点间的社会距离为1。最底层同一群中的节点之间互为邻居节点。处在不同群中的两个节点i 和节点j 之间的连接概率约为，β为相似系数。

    在贪婪路由策略中，假设每一步信息终止的概率为q，消息最终到达目标节点的概率大于等于q0，则此时对应的路由算法的平均传递步数为O(lnq0/ln(1-q))。

    研究表明，当β>0和H >1时，层次网络模型可以实现可扩展路由；当H =2或3时，β可取得最大值，可扩展路由也最有效。与网格模型相比，层次模型平均传递步数与网络规模无关，并且实现可扩展路由的条件更宽松。

2.4 隐藏度量模型
    最近，Boguna等人[12-14]揭示了复杂网络隐藏度量空间的存在，提出了隐藏度量模型。该模型中，任一两节点间均存在隐藏度量距离，且满足三角不等式。如果使用一维圆周作为隐藏度量空间，节点均匀分布在圆周上。则两节点间的连接概率r 依赖于它们之间的隐藏距离d 和两节点各自的度k和k’，满足：
r (d:k,k’)=r (d /dc)=(1+d /dc)-λ
其中，λ(>1)为聚集控制参数，d’c为特征距离尺度，且dc～kk’。
基于隐藏度量模型的贪婪路由策略研究表明，无标度网络的聚集系数越大，可扩展路由性能越好；当幂指数λ<3时，无标度网络可以实现可扩展路由，当λ=2时，路由路径最短，当λ≈2.6时，路由成功率最大；路由算法的平均传递步数为O((lnlnn)/ln(γ-2))，当网络规模有限时，路由算法的平均传递步数为O(lnlnn)。

    由于大多数实际复杂网络的幂指数满足：2<γ<3，均可应用该模型实现可扩展路由。

3 可扩展路由策略
    路由传递信息所经过的路径长度除了与路由过程中利用的拓扑信息量有关之外，还与具体的可扩展路由策略有关。贪婪路由是一种典型的路由策略，其路由规则在可扩展路由网络模型中做了介绍，下面给出其他几种。

3.1 随机游走路由
    随机游走路由规则：节点传递信息给其任一邻居节点，接收到信息的邻居节点又将信息传递给它的任一邻居节点，直到找到目标节点为止。随机游走路由策略分为[15]：(1)无限制随机游走路由，不记录已访问节点信息；(2)不返回前步节点随机游走路由，同一边上不连续来回传递某信息；(3)无三边循环随机游走路由；(4)无四边循环随机游走路由；(5)不重复访问节点随机游走路由，信息已达到过的节点不允许再被传递信息。第(4)种策略包括第(3)种策略，第(5)种策略包括第(4)和第(3)种策略。

    在上述5种策略中，第5种策略的效率最高。WS小世界模型中的随机游走路由步数介于规则网络随机游走步数(n 2)与随机网络随机游走步数(1/p，p为连接概率)之间，随机网络中的随机游走路由步数最少。在无标度网络中[16]，整个网络随机游走步数为n 3(1-2/γ)。

3.2 最大度路由
    最大度路由规则：节点传递信息到它的节点度最大的邻居，依次下去，直到信息传递到目标节点。
研究表明，最大度路由策略适用于非均匀网络，而不适用于均匀网络。在无标度网络中，最大度路由策略比随机游走策略更有效，可扩展路由到整个网络的路由步数为n 2- 4 /γ。

3.3 优先选择路由
    优先选择路由规则[17]：事先约定一个邻居节点被选中的概率p，节点传递信息时按概率p 选择一个邻居节点，依次下去，直到信息传递到目标节点。

    一般情况下，概率为节点度函数，比如，概率为pi =ki /∑kj，其中pi 为选择第i 个邻居节点的概率，ki为第i个邻居节点的度，j为当前节点所有邻居节点。又比如，概率为pi ∝kθ，θ>1，此时，低度邻居更难被选中。

    研究表明，优先选择路由策略不适用于小世界网络。在无标度网络中，优先选择路由步数为n 0.34。

3.4 距离与度混合路由
    距离与度混合路由规则[18]：节点传递信息给具有f (di,ki)最小度量值的邻居，依次下去，直到信息传递到目标节点。

    通常，度量函数f (di,ki)可为：(1)di -g (ki)，di为节点i到目标节点的最短距离，ki为节点i的度，g (ki)是选取高度邻居节点的一个激励函数，可表示具有ki 度节点与该节点之间边的期望最大长度，如c 1lnki +c 2；(2)，dm 为归一化常数；(3) ； (4)；
(5)，f (ki )为ki的一个增函数，如f (ki )=lnki +1。

    在上述策略中，第一种很难实现，且效率较低，后面4种策略的效率都很高，都接近于与全局信息的路由策略。

3.5 本地介数路由
    本地介数路由规则[19]：节点传递信息给本地介数L(i )最大的邻居，依次下去，直到信息传递到目标节点。

    节点i 的本地介数L(i )定义为：

    其中，s,t 属于本地网络，σs t  是从s 到t 的所有最短路由的总数(包括权值)，σs t (i )表示通过节点i 的最短路径之和。

    节点i 的本地介数与其度、连接节点i和根节点之间边权值有关。节点度越高或边权值越低，节点本地介数越大，在网络中也越重要。

    与本地介数路由类似的还有最小边权值和最小平均边权值路由。研究表明，如果链接权值的异构性比节点度的异构性高，基于链接权值的路由策略性能更好；当链接权值的异构性较少时，链接的重要也减少，本地介数可扩展路由策略的性能更好些。

3.6 相似性与度混合路由
    相似性与度路由规则[20]：节点i传递信息给具有最优化值P(qij,ki )的邻居节点j，依次下去，直到信息传递到目标节点。

    相似性和度混合度量函数可定义为P(qij,ki )=1-(1-qij)或P (qij,ki )=1 - ，其中qij为节点i 和节点j 之间的相似性度量参数(如节点j 连接到节点i 的概率)，ki为节点i 的度。如果网络没有相似性，则选择最大度路由策略；如果所有节点的度均相等，则选择与目标节点相似的节点。但在实际网络中，这两种情况很少见。

4 结束语
    复杂网络结构决定了网络路由功能，各种路由策略的比较研究可以发现复杂网络拓扑性质。复杂网络中的可扩展路由理论与实验研究是近年来的热门话题，本文对相关研究成果进行了分析与归纳。

    (1)讨论了各种可扩展路由网络模型的构造方法和优缺点。网格模型和社会层次模型的约束条件太多，适用范围很窄，很难应用于实际复杂网络中。隐藏度量空间模型则不同，它几乎没有任何约束条件，非常适合各种复杂网络。

    (2)综述了各种基于局部信息的可扩展路由策略。贪婪路由主要用于理论研究，但在复杂网络中，它不是最优的，并可能存在节点空洞现象。最大度路由策略在P2P网络中有了较好的应用，但选择最大度邻居节点可能远离目标节点。随机游走路由策略在个人移动通信中具有广泛的应用前景。优先选择路由、本地介数路由和各种混合路由策略的关键在于选择节点度量函数的确定，一个好的度量函数可以提高路由性能，缺点是实现比较复杂。

    (3)可扩展路由是基于局部拓扑信息的，不同的路由策略所使用的局部拓扑信息有所不同，使得它们之间的性能也存在差异。相同之处在于，各种可扩展路由策略都必须找到最小路径长度和成功率之间的平衡点。在具体的路由策略中，还需要考虑节点重复访问、节点空洞等问题。

    (4)基于局部拓扑信息的思想已经在资源搜索和导航中得到了广泛应用。复杂网络中的可扩展路由研究成果和研究方法可以为目前下一代互联网络由系统的可扩展路由研究提供理论支撑和方法借鉴。

5 参考文献
[1] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京: 清华大学出版社, 2006.
[2] KRIOUKOV D, CLAFFY K, FALL K, et al. On compact routing for the Internet [J]. ACM Computer Communication Review, 2007, 37(3):42-52.
[3] MEYER D, ZHANG L, FALL K. Report from the IAB workshop on routing and addressing [R]. IRTF RFC4984. 2007.
[4] MILGRAM S. The small world problem [J]. Psychology Today, 1967, 1(1):61-67.
[5] WATTS D J, Strogatz S H. Collective dynamics of "small-world" networks [J]. Nature, 1998, 393: 440-442.
[6] NEWMAN M E J, WATTS D J. Renormalization group analysis of the small-world network model [J]. Physics Letters:A, 1999, 263:341-346.
[7] FALOUTSOS M, FALOUTSOS P, FALOUTSOS C. On power-law relationships of the Internet topology [J]. ACM Computer Communication Review, 1999, 29(4):251-262.
[8] BARABASI A L, ALBERT R. Emergence of scaling in random networks [J]. Science, 1999, 286: 509-512.
[9] KLEINBERG J. Navigation in a small world [J]. Nature, 2000, 406: 845.
[10] KLEINBERG J. Complex networks and decentralized search algorithms [C]//Proceedings of the International Congress of Mathematicians(ICM’06):Vol.3, Aug 22-30, 2006, Madrid, Spain. Finland: EMS Ph,2006:1019-1044.
[11] WATTS D J, DODDS P S, NEWMAN M E J. Identity and search in social networks [J]. Science, 2002, 296:1302-1305.
[12] SERRANO M, KRIOUKOV D, BOGUNA M. Self-similarity of complex networks and hidden metric spaces [J]. Physical Review Letters, 2008, 100:78701.
[13] BOGUNA M, KRIOUKOV D, CLAFFY K. Navigability of complex networks [J]. Nature Physics, 2009,5:74-80.
[14] BOGUNA M, KRIOUKOV D. Navigating ultrasmallworlds in ultrashort time [J]. Physical Review Letters, 2009, 102:58701.
[15] YANG S. Exploring complex networks by walking on them [J]. Physical Review: E, 2005, 71:16107.
[16] ADAMIC L, LUKOSE R, PUNIYANI A, et al. Search in power-law networks [J]. Physical Review: E, 2001, 64:46135.
[17] KIM B J, YOON C N, HAN S K, et al. Path finding strategies in scale-free networks [J]. Physical Review: E, 2002, 65:27103.
[18] THADAKAMALLA H P, ALBERT R, KUMARA S R T. Search in spatial scale-free networks [J]. New Journal of Physics, 2007, 9(6):190.
[19] THADAKAMALLA H P, ALBERT R, KUMANA S R T. Search in weighted complex networks [J]. Physical Review: E, 2005, 72:66128.
[20] IMSEK O JENSEN D. Navigating networks by using homophily and degree [J]. Proceedings of the National Academy of Sciences, 2007, 105(35):12758-12762.

收稿日期：2009-08-06

[摘要] 互联网规模扩大，相应路由表大小呈指数增加，形成下一代互联网可扩展路由“瓶颈”。基于复杂网络和可扩展路由的相关理论与主要策略，文章对相关研究成果，如小世界效应所表现出来的特性、小世界和无标度网络模型，网格、层次及隐藏度量等3种可扩展路由网络模型，随机游走、贪婪、最大度、优先、本地介数、距离与度及相似性与度混合等多种路由策略等进行了分析与归纳。这些研究结果和方法为因互联网规模不断扩大所带来的路由系统可扩展性问题提供解决方案

[关键词] 复杂网络；可扩展路由；局部拓扑信息

[Abstract] With the Internet’s expansion, its routing table size increases exponentially, which is a bottleneck of routing scalability in the next generation Internet. 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, preferential 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.

[Keywords] complex network; scalable routing; local information of topology