上海交通大学硕士学位论文基于复杂网络的Internet拓扑建模研究姓名：宋莉雅申请学位级别：硕士专业：控制理论与控制工程指导教师：汪小帆20060201上海交通大学硕士学位论文基于复杂网络的 Internet 拓扑建模研究摘 要Internet 是一个典型的复杂网络。Internet 上的通讯协议优化、病毒传播及拥塞控制等均与其拓扑密切相关。因此，针对不同的预测和改善 Internet 性能的目的，研究 Internet 拓扑特性及构建合适的网络拓扑模型就显得非常必要。Internet 拓扑建模是一项复杂的工作，涉及到图论、统计物理学、网络测量、数学建模及算法设计等多个领域。如何获得 Internet的拓扑连接信息，如何对 Internet 拓扑特征及其演化机理进行恰当描述，如何构造接近于 Internet 实际情况的拓扑图是 Internet 拓扑建模研究的主要内容。本论文的主要工作包括：论文首先简单介绍了复杂网络的研究背景，并对复杂网络理论研究中有关 Internet 拓扑特性及建模的发展现状进行了阐述。论文对自治系统层面 Internet 拓扑进行了详细研究。深入分析了记录 Internet 上自治系统间连接情况的统计数据，并对不同统计数据来源所刻画的 Internet 拓扑特性进行了描述和对比。论文就 Internet 拓扑产生器的研究进行了综合阐述。目前主要是针对自治系统层面 Internet 进行拓扑建模，大致经历了随机图产生器、结构产生器和基于连接度的产生器这三个发展阶段。论文给出了这些拓扑产生器的建模机理，并对其进行了定性对比。上海交通大学硕士学位论文在研究分析 Internet 演化机理及已有拓扑建模的基础上，受局域世界模型和多局域世界模型的启发，针对自治系统层面 Internet拓扑建模，论文提出了一个新的局域世界综合演化模型。论文就局域世界综合演化模型的建模机理、生成步骤进行了详细阐述，并对局域世界模型、多局域世界模型和局域世界综合演化模型进行了简要对比。通过大量的仿真实验，论文研究分析对比了局域世界综合演化模型及 Oregon 所采集的 1998 年和 2001 年自治系统层面 Internet的拓扑特性。发现局域世界综合演化模型有效刻画了同等规模自治系统层面 Internet 的诸多拓扑特性，如无标度性、小世界特性、层次性、异配性、富人俱乐部特性等。局域世界综合演化模型是对自治系统层面 Internet 的有效建模。关键词: Internet，自治系统，拓扑建模，局域世界综合演化模型上海交通大学硕士学位论文AN INVESTIGATION ON INTERNET TOPOLOGYMODELING BASED ON COMPLEX NETWORKSABSTRACTInternet is a typical complex network. The optimization of trafficprotocol, virus spreading and congestion control are all closely related tothe Internet topology. In order to predict and improve the Internetproperties, it is quite necessary to study the Internet topology propertiesand propose suitable topology generator, which can embody thefundamental characteristics of real network.Internet topology modeling is a complicated work, which is relatedto many fields, such as graph theory, statistical physics, networkmeasuring, mathematics modeling and algorithm design. How to get theInternet topology information, how to describe the Internet topologyproperties and evolving mechanism accurately and how to build atopology graph which is similar to the real Internet are the main subjectsof Internet topology modeling research. The main works of this thesis areas follows:上海交通大学硕士学位论文The thesis introduced the background of complex network research,described the state-of-art of Internet topology modeling in the field ofcomplex network.The thesis carried on detailed research on the AS-level Internettopology. We studied and compared the topology properties of differentstatistical data sources, which kept the record of link information betweendifferent autonomous systems.The thesis expatiated upon the Internet topology generators research.The current research focused on the AS-level Internet topology modelingand had developed through three stages: random graph generator,structural generator and degree-based generator. We gave the modelingmechanisms and comparison of these topology generators.Based on the analysis of Internet evolving mechanism and existingtopology modeling results and stimulated by local-world model and multilocal-world model, we proposed a new evolving local-world integratedmodel for the AS-level Internet. The thesis gave the modeling mechanismand processes of the evolving local-world integrated model and comparedthe three models, which were all referred to the local world phenomenon.Through a number of simulation experiments, we studied andcompared the topology properties of the evolving local-world integratedmodel and the AS-level Internet in the year of 1998 and 2001, which werecollected by Oregon. We found the evolving local-world integrated model上海交通大学硕士学位论文characterized the AS-level Internet topology properties effectively, suchas scale-free, small-world, hierarchy structure, disassortative propertiesand rich-club phenomenon. The evolving local-world integrated model isa proper topology generator of the AS-level Internet.KEY WORDS: Internet, Autonomous System, Topology Modeling,Evolving Local World Integrated Model上海交通大学学位论文原创性声明上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：宋莉雅日期： 2006 年 2 月 16 日上海交通大学学位论文版权使用授权书上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密保密，在 年解密后适用本授权书。本学位论文属于不保密不保密?。（请在以上方框内打“” ）学位论文作者签名：宋莉雅 指导教师签名：汪小帆日期：2006 年 2 月 16 日 日期：2006 年 2 月 16 日上海交通大学硕士学位论文1第一章第一章 绪绪 论论1.1 复杂网络的研究背景复杂网络的研究背景复杂网络的研究涉及到系统科学、统计物理学、社会科学、生物学等多个领域。通过研究发现，现实中很多网络并不是完全随机的，也不是完全结构图，而具有无标度、小世界等统计特性，称这样的网络为复杂网络。Internet、万维网、大型电力网、交通网、科研合作网、社会关系网、生物代谢网等均可以看作是复杂网络，可以说，现实世界是一个由各种复杂网络所组成的集合体。描述众多现象时，可以将系统中的个体定义为节点，个体之间存在的关联定义为节点之间的边，这样便抽象成一个网络图。18 世纪伟大的数学家欧拉基于七桥问题的抽象和论证思想，开创了一个数学分支图论。在二十世纪里，图论已发展成一门坚实的理论。事实上，今天人们关于复杂网络的研究与欧拉当年关于七桥问题的研究在某种程度上是一脉相承的，即网络结构与网络性质密切相关。复杂网络的理论研究始于 20 世纪 60 年代 Erds 和 Rnyi 提出的 ER 随机图模型1。随机图理论在此后将近 40 年的时间里一直是研究复杂网络结构的基本理论。但绝大多数复杂网络的实际结构并不是完全随机的，例如，两个人之间是否是朋友、Internet 中两个路由器之间是否有光纤连接、WWW 上两个页面之间是否有超文本链接等都不会是完全靠抛硬币来决定的。两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志：一篇是美国康奈尔（Cornell）大学理论和应用力学系的博士生 Watts 及其导师、非线性动力学专家 Strog