张连明：复杂网络与可扩展路由
ＺＴＥＣＯＭＭＵＮＩＣＡＴｌＯＮＳ
复杂网络与可扩展路由
ＣＯｍｐｌｅｘＮｅｌｗＯｆｋａｎｄＳＣａＩａｂＩｅＲｏｕｌｉｎｇ
摘要：互联网规模扩大，相应路由表大小呈指数增加，形成下一代互联网可扩展路由
。瓶颈’。基于复杂网络和可扩展路由的相关理论与主要策略，文章对相关研究成果，
如小世界效应所表现出来的特性、小世界和无标度网络模型，网格、层次及隐藏度量
等３种可扩展路由网络模型，随机游走、贪婪、最大度、优先、本地介数、距离与度及相
似性与度混合等多种路由策略等进行了分析与归纳。这些研究结果和方法为因互联
网规模不断扩大所带来的路由系统可扩展性问题提供解决方案
关键诩：复杂网络；可扩展路由；局部拓扑信息
Ａｂｓｔｒａｃｔ：ＷｉｔｈｔｈｅＩｎｔｅｍｅｔ’ｓｅｘｐａｎｓｉｏｎ，ｈｓｒｏｕｔｉｎｇｔａｂＩｅｓｉ孢ｉｎｃｒｅａｓｅｓｅ×Ｄｏｎｅｎｔｉａ¨ｙ，
ｗｈｉｃｈｉｓａｂｏｔｔｌｅｎｅｃｋｏｆｒＯｕｔｉｎｇｓｃａＩａｂｉＩｎｙｉｎｔｈｅｎｅ×ｔｇｅｎｅｒａｔｉＯｎＩｎｔｅｒｎｅｔ．Ｉｎｔｈｉｓｐａｐｅｒ，
ｗｅｓｕｍｓｕｐａｎｄａｎａＩｙｚｅｓｔｈｅｉｎｌｐＯｒｔａｎｔｔｈｅＯｒｉｅｓａｎｄｓｔｒａｔｅｇｊｅｓｆＯｒｃＯｍｐＩｅ×ｎｅｔｗＯｒｋｓ
ａｎｄｓｃａＩａｂＩｅｒｏｕｔｉｎｇ．ＦｏｒｃｏｍｐＩｅｘｎｅｔｗＯｒｋｓ．ｔｈｅｃｈａｆａｃｔｅｒｉｓｔｉｃｓｏｆｓｍａ¨一ｗｏｒＩｄｅ什ｅｃｔ．
ｓｍａ¨一ｗＯ—ｄｎｅｔ、ⅣｏｒｋｍｏｄｅＩｓａｎｄｓｃａｌｅ—ｆｒｅｅｎｅｔ、Ⅳ０ｒｋｍＯｄｅＩａｒｅｄｉｓｃｕｓｓｅｄ．ＡｓｆＯｒ
ｓｃａＩａｂｌｅｒｏｕｔｉｎｇ，ｔｈｅｍｏｄｅｌｓｏｆｇｒｉｄ．ｈｉｅ伯ｒｃｈｉｃａＩａｎｄｈｉｄｄｅｎｍｅｔｒｉｃａｒｅｄｅｓｃｒ．ｂｅｄ．
ＭＯｒｅｏｖｅｒ，ｔｈｅｒｏｕｔｉｎｇＳｔ怕ｔｅｇｉｅｓｏｆ怕ｎｄＯｍｗａＩｋ，ｇｒｅｅｄｙ，ｍａ×ｉｍｕｍｄｅｇｒｅｅ，ｐ陀ｆｅｒｅｎｔｉａｌ
ｃｈｏｉｃｅ，Ｉｏｃａ｜ｂｅｔ、～ｅｅｎｎｅｓｓｃｅｎｔ阳¨ｔｙ，ｄｉｓｔａｎｃｅ—ｄｅｇｒｅｅａｎｄｈｏｍｏｐｈｉＩｙ—ｄｅｇｒｅｅａｒｅ
ａｎａＩｙｚｅｄ．Ｔｈｅｓｅｒｅｓ∞ｒｃｈｒｅｓｕ№ａｎｄｍｅｔｈｏｄｓｗｉＩＩｐｒｏｖｉｄｅａｓｏＩｕｔｉｏｎｔ０ｔｈｅｐｒｏｂＩｅｍｏｆ
ｓｃａ｜ａｂｌｅｒＯｕｔｉｎｇｂｒｏｕｇｈｔｂｙｔｈｅＩｎｔｅｒｎｅｔ’ｓｅｘｐａｎｓｉｏｎ．
Ｋｅｙｗｏｒｄｓ：ｃｏｍｐＩｅｘｎｅｔｗＯｒｋ：ｓｃａＩａｂｌｅｒｏｕｔ．ｎｇ：ＩｏｃａＩｌｎｆｏｒｍａｔｉｏｎｏｆｔｏｐＯｌｏｇｙ
为揭示复杂系统内在特征、规律和行为，常利用网络描述其结构。节点代表系统内部各个体，链接代表个体间关系。随机图论是复杂系统研究的早期基础理论。近１０年来，复杂网络作为一门新兴网络科学悄然升起，目前逐步成为复杂系统研究的重要理论和国际科学前沿研究课题之一。其主要研究内容包括…：揭示刻画复杂系统的统计性质，建立适合的复杂系统网络模型，分析预测复杂系统的行为，提出已有网络性能改进和新型网络设计的有效方法。
基金Ｔ币目：中国博士后科学基金资助项目（２００７０４２０７８２）
随着互联网规模的不断扩大，路
由表大小呈指数增长，庞大的路由表
对路由系统造成了巨大负担【２ｌ。因
此，近年来互联网络由系统规模可扩
展性问题受到普遍关注Ⅲ。尽管目前
还没有对路由系统的规模可扩展性
限制作任何形式化分析，但学术界达
成了如下共识：路由系统规模可扩展
性是下一代瓦联网多维可扩展的基
础，是加快部署具有庞大地址空间的
ＩＰｖｌ６协议的突破口。如何在海量地址
空间范围内实现高效路由，不管在理
论上还是技术上，仍然是没有解决的
难题，面对如此巨大的地址空间，理
想的路由一定是规模可扩展路由，随
着网络规模的不断扩大能够自适应
５
张连明亿ＨＡＮＧＬｉａｎｍ｜ｎｇ
ｆ湖南拜范大学物理与信毫科学学院。湖南长
沙．４１００８１ｌ
ｆＣｏ｜ｌ盼ｅ硝Ｐｈｖｓ记ｓ删｜ｎｆｏｍｌａｔ衙１Ｓｃ’悖ｎｃｅ．
Ｈｕ触ｎ№ｍ翻Ｕｎ№鸭ｌｌｙ．ｃ岫礤ｈａ。４１００８１。
ａ‘，『，垴Ｊ
的路由。
１复杂网络
１．１小世界效应
１９６７年，Ｍ岫ｍ…做了一个实验：
随机选定两个目标对象和一批志愿
者，要求这些志愿者通过其所认识的
人，用自己认为尽可能少的传递次
数，设法把一封信最终转交到一个给
定的目标对象手中，并要求每个节点
只能向其朋友转交一封信。实验结果
显示，大约３０％的信平均经过６跳成
功达到目标对象。显然，该实验的研
究对象为人表示节点、人与人之间的
朋友或邻居关系表示链接的社会网
络，其揭示了社会网络具有小世界效
应：较短的平均路径长度，短路径的
可搜索性。同时，该实验提出了两个
基本问题：社会网络为什么能实现搜
索？可搜索网络的结构是怎样的？这
项研究结果发现引发了小世界网络
直径、小世界网络模型及其中的搜索
与导航等方面的一系列研究。
１．２小世界网络模型
１９９８年，ｗａ№和Ｎ㈣等人【“１率
先对具有小世界效应的网络进行形
式化建模，提出了ｗｓ小世界网络模
型和ＮＷ小世界网络模型。ｗＳ小世界
模型的构造方法如下：刀个节点围成 万方数据