Internet网络拓扑建模

ＩＳＳＮ１０００－９８２５，ＣＯＤＥＮ

ＪｏｕｒｎａｌＲＵＸＵＥＷＥ ｍａｉｌ：ｊＯＳ＠ｉｓｃａｓ．ａｃ．ｃｎｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ

Ｔｅｌ腰ａｘ：＋８６．１０．６２５６２５６３ｏｆＳｏｆｔｗａｒｅ，Ｖ０１．２０，ＮｏＩ，Ｊａｎｕａｒｙ２００９，ＰＰ．１０９—１２３ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１００１．２００９．０３３９０

＠ｂｙＩｎｓｔｉｔｕｔｅＤ，Ｓｏｆｔｗａｒｅ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｉ＂Ｓｃｉｅｎｃｅｓ．Ａｌｌｒｉｇｈｔｓｒｅｓｅｒｖｅｄ．

Ｉｎｔｅｒｎｅｔ网络拓扑建模

周苗１＋，杨家海２，刘洪波２，吴建平１

１（清华大学计算机科学与技术系，北京

２（清华大学网络研究中心，北京１０００８４）１０００８４）

ＭｏｄｅｌｉｎｇｔｈｅＣｏｍｐｌｅｘＩｎｔｅｒｎｅｔＴｏｐｏｌｏｇｙ

ＺＨＯＵＭｉａ０１＋，ＹＡＮＧＪｉａ．Ｈａ［２，ＬＩＵＨｏｎｇ．Ｂ０２，ＷＵＪｉａｎ．ＰｉｎｇＩ

１（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８４，Ｃｈｉｎａ）

２（ＮｅｔｗｏｒｋＲｅｓｅａｒｃｈＣｅｎｔｅｒ，Ｔｓｉｎｇｈ岫Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８４，Ｃｈｉｎａ）

＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇａｕｔｈｏｒ：Ｅ—ｍａｉｌ：ｚｈｏｕｍ０５＠ｍａｉｌｓ．ｔｓｉｎｇｈｕａ．ｅｄｕ．ｃｎ

ＺｈｏｕＭ，ＹａｎｇＪＨ，ＬｉｕＨＢ，ＷｕＪＰ．ＭｏｄｅｌｉｎｇｔｈｅｃｏｍｐｌｅｘＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙ．Ｊｏｕｒｎａｌ０１＂Ｓｏｆｔｗａｒｅ，２００９，２０（１）：１０９－１２３．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／１０００—９８２５／３３９０．ｈｔｍ

Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓｔｈｅｂａｓｉｃｃｏｎｃｅｐｔｏｆｔｏｐｏｌｏｇｙ’Ｓｐｒｏｐｅｒｔｉｅｓａｎｄｍｏｄｅｌｉｎｇｍｅｔｒｉｃｓ；ｃａｔｅｇｏｒｉｚｅｓａｎｄａｎａｌｙｚｅｓｂｏｔｈＡＳ－ｌｅｖｅｌ

ｏｎｍｏｄｅｌｓａｎｄｒｏｕｔｅｒ－ｌｅｖｅｒｍｏｄｅｌｓ．Ｍｏｒｅｏｖｅｒ，ｔｈｉｓｐａｐｅｒｓｕｍｍａｒｉｚｅｓｃｕｒｒｅｎｔｒｅｓｅａｒｃｈａｃｈｉｅｖｅｍｅｎｔｓＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙ’Ｓｍｏｄｅｌｉｎｇ，ｅｓｐｅｃｉａｌｌｙａｔｔｈｅｒｏｕｔｅｒ－ｌｅｖｅｌ．Ｆｉｎａｌｌｙ，ｉｔｉｄｅｎｔｉｆｉｅｓｆｕｔｕｒｅｄｉｒｅｃｔｉｏｎｓ

ａｎｄｏｐｅｎｐｒｏｂｌｅｍｓｏｆｔｈｅ

Ｋｅｙｗｏｒｄｓ：Ｉｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｍｏｄｅｌｉｎｇｒｅｓｅａｒｃｈ．ｍｏｄｅｌｉｎｇ；ｒｏｕｔｅｒ －ｌｅｖｅｌｍｏｄｅｌｉｎｇ；ｔｏｐｏｌｏｇｙｐｒｏｐｅｒｔｉｅｓ；ｍｅｔｒｉｃｓｔｏｐｏｌｏｇｙ；ＡＳ －ｌｅｖｅｌ

摘要：首先概述Ｉｎｔｅｒａｃｔ网络拓扑建模的意义和分类；总结现阶段已发现的主要网络拓扑特性与度量指标；然后分析、讨论自治域级和路由器级的Ｉｎｔｅｒｎｅｔ网络拓扑建模与最新的研究成果；最后针对目前拓扑建模中存在的难点和问题给出总结，并展望未来的研究发展方向．

关键词：Ｉｎｔｅｍｅｔ网络拓扑；自治域级拓扑建模；路由器级拓扑建模；拓扑特性；度量指标

文献标识码：Ａ中图法分类号：ＴＰ３９３

近年来。大规模的复杂Ｉｎｔｅｒｎｅｔ网络拓扑分析研究引起了计算机及物理、数学等多个领域研究人员的兴趣【ｌ＿６１．然而，Ｉｎｔｅｒｎｅｔ网络自身具有复杂性和多变性，导致直接将其作为实验对象进行研究和分析变得十分困难．因此，人们希望根据真实网络数据和关键特征对Ｉｎｔｅｒｎｅｔ网络拓扑进行模型抽象，以拓扑模型代替真实Ｉｎｔｅｍｅｔ网络作为实验对象进行研究分析，达到通过拓扑建模认识Ｉｎｔｅｍｅｔ基本特性并指导实际网络建设的目的１１．ｚ卜１０Ｊ．

针对Ｉｎｔｅｒｎｅｔ网络拓扑建模的研究历程和未来发展方向，张宇【１１】、曾伟【１２Ｉ都曾对网络拓扑建模问题作过综述．但是，上述工作均只针对自治域级（ＡＳ（ａｕｔｏｎｏｍｏｕｓｓｙｓｔｅｍ）－ｌｅｖｅｌ）拓扑建模，极少涉及路由器级（ｒｏｕｔｅｒ－ｌｅｖｅｌ）的拓扑建模．可是，作为Ｉｎｔｅｒｎｅｔ网络拓扑建模的重要方面，人们已开始越来越关注路由器级的网络拓扑建模［１，３，１３１．相对自治域级网络拓扑结构，路由器级拓扑更大程度上受到网络服务提供商（ＩＳＰ）各自的技术水平和用户需求等相关因素的影响．并且，已有研究成果［２，１４１表明，路由器级别的Ｉｎｔｅｒｎｅｔ网络拓扑特性极有可能存在与自治域级

ＳｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔ

ＲｅｃｅｉｖｅｄＮｏ．６０４７３０８３（国家自然科学基金）２００８－０１ ０８；Ａｃｃｅｐｔｅｄ２００８－０５—０５

１１０ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．２０，Ｎｏ．１，Ｊａｎｕａｒｙ２００９Ｉｎｔｅｍｅｔ网络拓扑特性不一样的生成机理．另外，Ｌｉ等人【１３１也对路由器级拓扑的无标度性提出了质疑，并基于设计优化方法提出路由器级启发式优化模型（简称ＨＯＴ（ｈｅｕｒｉｓｔｉｃａｌｌｙ

设计原则的全局优化模型的转变．

本文将首先概要介绍Ｉｎｔｅｒｎｅｔ网络拓扑建模的意义和分类，总结现阶段已发现的主要网络拓扑特性与度量指标，然后分析、讨论自治域级和路由器级的Ｉｎｔｅｒｎｅｔ网络拓扑建模与最新的研究成果，最后将展望该领域未来的研究发展方向，并针对目前Ｉｎｔｅｒａｃｔ拓扑建模中存在的难点问题及全文主要内容进行总结．

１ｏｐｔｉｍａｌｔｏｐｏｌｏｇｉｅｓ）ｍｏｄｅｌ）与新的相关度量指标，这为路由器级拓扑建模指出了新的发展方ｔ２，１４１，即从基于随机原则的无标度网络模型（ＳＦｍｏｄｅｌ）至Ｕ基于Ｉｎｔｅｒｎｅｔ拓扑建模概述

一直以来，不同领域的研究者都对Ｉｎｔｅｒｎｅｔ网络拓扑建模进行了大量的研究工作．对网络理论研究者来说，其建模目的是根据所获得的真实网络拓扑数据进行网络模拟，从而分析预测新的路由协议等对不同层面Ｉｎｔｅｒｎｅｔ网络连通性的影响，以及拓扑变化对网络性能的影响，并最终改善网络技术、提高网络服务性能；对非网络理论研究者，尤其是对数理学领域的研究人员，其对Ｉｎｔｅｒｎｅｔ网络拓扑建模的研究出发点是探索普遍存在的规则原理．例如，数理学者希望发现小范围网络模型与大规模嘲络模型之间的必然联系，研究复杂网络领域的普遍规律【１＇４】．不同领域的研究方法和目的的差异造成Ｉｎｔｅｒｎｅｔ网络拓扑建模可能存在不同的模型生成算法和相关度量指标，在具体建模过程中，要根据研究需要进行选择；但是总体说来，无论何种领域的研究者，其建模研究的共同思路是一致的．

概括来说，可将网络拓扑建模研究分为以下３个方面：（１）在实验获得真实网络连接的基础上，获得实际网络的拓扑图，如Ｒｏｃｋｅｔｆｕｅｌ［１５１，Ｓｋｉｔｔｅｒｔｌ６，１７１等；（２）探索能够刻画实际网络拓扑特征的度量指标，包括简单度量，如节点平均度和平均度分布等，以及复杂度量聚类系数、似然系数、频率系数等；（３）研究基于上述度量指标的拓扑演化模型和生成算法，要求所产生的拓扑模型尽可能地接近真实网络，即具有相同拓扑特性．

随着人们对Ｉｎｔｅｍｅｔ网络拓扑建模研究的深入，现阶段已涌现出大量的Ｉｎｔｅｍｅｔ网络拓扑模型，我们将其按照两种方法来分类．

（１）静态模型和动态模型

如图Ｉｔ‘０１所示．

Ｆｉｇ．１Ｍｅｔｈｏｄｏｌｏｇｉｅｓｏｆｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｒｅｓｅａｒｃｈ

图ｌＩｎｔｅｒａｃｔ网络拓扑建模概述

这里的静态模型是指从拓扑发现得到的实际拓扑数据中生成能够反映实际网络拓扑特性静态网络拓扑图；动态模型是指根据某种或某几种拓扑特性而研究网络的构建过程，设计拓扑生成算法，得到能够刻画拓扑特

周苗等：Ｉｎｔｃｒｎｅｔ网络拓扑建模

性生成机理的拓扑产生器．

（２）自治域级拓扑模型和路由器级拓扑模型

若基于建模对象的不同，也可将Ｉｎｔｅｒｎｅｔ拓扑模型分为自治域级拓扑模型【１８＿２４’和路由器级拓扑模型１１３，２ａ１．在自治域级拓扑模型中，节点（ｎｏｄｅ）代表自治系统，边（１ｉｎｋ）代表自治系统之间的连接关系；在路由器级拓扑模型中．节点代表自治域内的路由器，边代表路由器之间的１跳连接关系．相对于自治域级拓扑的随机性，路由器级拓扑受到各ＩＳＰ自身技术水平和经济能力以及用户需求等多方面人为因素的限制，体现出一种基于设计优化的拓扑结构．

目前，对于自治域级Ｉｎｔｅｍｅｔ拓扑建模，已有大量研究成果和相关论文［７，９，１８－２４１，但仍然缺乏能够模拟大规模复杂网络范围并且反映多种实际网络拓扑特性的自治域级拓扑模型；对于路由器级Ｉｎｔｅｒｎｅｔ拓扑建模，现有路由器级拓扑发现算法都不能保证测量目标集合的完备性，造成后继建模工作的困难增大，现阶段相应分析理论还不够成熟，如今，路由器级拓扑建模已成为Ｉｎｔｅｒｎｅｔ拓扑建模的研究热点之一【１１．

２Ｉｎｔｅｒｎｅｔ拓扑特性与度量指标

Ｉｎｔｅｍｅｔ网络拓扑建模最根本的基础是相关的实际网络拓扑特性，以及刻画这些拓扑特性的度量指标．是否反映真实网络拓扑特性是评价拓扑模型的首要原则．

２．１Ｉｎｔｅｒｎｅｔ拓扑特性

我们把网络不依赖于特定节点的具体位置或特定边的具体形态就能表现出来的整体性质称为网络拓扑特性．网络拓扑特性对于网络中各种行为的扩散和发展变化有着深刻的影响．通过大量对现实Ｉｎｔｅｒｎｅｔ网络拓扑数据进行的研究工作，人们对大规模的复杂Ｉｎｔｅｒａｃｔ网络拓扑特性已有了一定了解，目前，在拓扑建模中主要考虑的拓扑特性包括幂律分布（ｐｏｗ＊ｌａｗ）特性【２们、鲁棒且脆弱性（ｒｏｂｕｓｔｙｅｔｆｒａｇｉｌｅ）ｔ２７１、聚集（ｃｌｕｓｔｅｒｉｎｇ）特性【２８】等．２．１。ｌ幂律分布特性

幂律分布特性是一种广泛存在于自然界与人类社会的性质，该特性表现为大量事件出现概率很小，而少量事件出现概率很大的分布现象．例如，人类语言中只有少数词汇的使用频率很高，而绝大多数词汇实际上很少被使用的现象．各领域学者已发现的典型幂律分布，包括地震规模大小的分布、月坑直径的分布、战争规模分布、生物物种数量的分布等等，其形式多种多样【２９】．

Ｉｎｔｅｒａｃｔ网络拓扑结构中存在的幂律分布特性【２６】是１９９９年由Ｆａｌｏｕｔｓｏｓ三兄弟发现的．在Ｉｎｔｅｒｎｅｔ网络拓扑结构中存在的幂律分布特性未被揭示之前，Ｉｎｔｅｒｎｅｔ网络一直被认为是一种随机网络（ｒａｎｄｏｍｎｅｔｗｏｒｋ），且网络节点度分布符合二项分布，即在满足Ⅳｐ（其中∥是节点个数炉是连接概率）趋于定值的情形下，近似服从泊松分布．由于泊松分布下高度数节点存在的可能性呈指数级衰减，因此，可基本忽略高度数节点，而将网络拓扑近似看作一种均匀结构，即绝大多数节点的度数都分布在节点平均度附近‘３０。３２１；而Ｉｎｔｅｒｎｅｔ网络中幂律分布特性的发现证明了Ｉｎｔｅｍｅｔ网络的节点度分布应满足幂律分布，即节点度间实际上相差悬殊，在双对数图中应表现为一条斜率为负的直线，这一线性关系是判断给定的实例中随机变量是否满足幂律分布的依据．另外，由于幂函数具有标度不变性，因此，人们现在也把节点度服从幂律分布的网络称为无标度网络（ｓｃａｌｅ．ｆｒｅｅｎｅｔｗｏｒｋ）．

Ｆａｌｏｕｔｓｏｓ兄弟发现的幂律分布特性包括３条幂律及ｌ条近似幂律【２６１，分别为：

幂律ｌ（秩指数矗）．节点出度与该节点等级的月次幂成比例．

ｄ，ｏＣ蠢．

其中，或表示节点ｖ的出度，～表示节点ｖ在网络拓扑中按度降序排列的等级．

幂律２（度指数Ｄ）．度大于ｄ的节点在网络拓扑中所占百分比与节点出度ｄ的Ｄ次幂成比例．

厶茁ｄＤ，

其中，后代表该百分比ｐ是Ｒ的倒数．幂律３（特征值力，特征值五，与其次序ｉ的献幂成比例．

１１２ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．２０，Ｎｏ．１，Ｊａｎｕａｒｙ２００９

疋芘ｉ６，

其中，兄，为网络对应连接矩阵的特征值，ｆ为将特征值按降序排列时的序列号．

另外，幂律２还指出一条近似幂律（ｈｏｐ—ｐｌｏｔ指数田：磊跳内节点对（ｐａｉｒｓ

比例．ｏｆｎｏｄｅｓ）的数量与ｈ的始次幂成

幂律分布特性对于Ｉｎｔｅｒｎｅｔ网络拓扑结构生成以及网络性能改进影响很大，例如，该特性可反映出网络拓扑结构与用户需求之间的明显联系，因此我们可以考虑能否在降低用户需求幂律指数，即分布式部署高度数节点的情况下，改善网络传输性能等等［３３，３４］．另外，Ｉｎｔｅｒｎｅｔ网络拓扑结构的幂律分布特性对网络的动力学性质等也有深刻影响．以病毒传播为例，之前基于规则网络及随机网络的研究曾认ｆｆ；ｊ［３５，３６］，病毒只有当传染强度大于某阈值时才能在Ｉｎｔｅｒｎｅｔ网络中长期存活；而基于幂律分布特性的研究则表明，Ｉｎｔｅｒｎｅｔ网络不存在类似的阈值（３７＿４０１。要想在现有Ｉｎｔｅｒｎｅｔ这样的无标度网络上彻底消灭病毒，即使是已知病毒也不太可能【６，４１１．

２．１．２鲁棒且脆弱性

鲁棒且脆弱性特性【２７】是大规模Ｉｎｔｅｒａｃｔ网络的基本特性之一，也是体现随机图网络和无标度网络之间存在显著差异的重要拓扑特性．与早期随机图网络不同，无标度网络中幂律分布特性的存在极大地提高了高度数节点存在的可能性，因此，无标度网络同时显现出针对随机故障的鲁棒性和针对蓄意攻击的脆弱性．

这种鲁棒且脆弱性对网络容错和抗攻击能力有很大影响．研究表ｆｉｒ］［４２，４３１。无标度网络具有很强的容错性，但是对基于节点度值的选择性攻击而言，其抗攻击能力相当差，高度数节点的存在极大地削弱了网络的鲁棒性，一个恶意攻击者只需选择攻击网络很少的一部分高度数节点，就能使网络迅速瘫痪．另外，已有研究‘１０】指出，Ｉｎｔｅｒｎｅｔ网络路由器级拓扑表现出与自治域级拓扑所不同的鲁棒且脆弱性。并且其生成机理不能同样用无标度模型来加以刻画．

２．１．３聚集特性

随着对网络拓扑的进一步研究，人们发现仅用节点度分布来刻画网络拓扑结构是远远不够的，满足同样幂律分布的网络完全可以呈现截然不同的拓扑结构。在幂律分布特性的基础上，人们开始研究网络拓扑中存在的聚集特性【２ｓ】．

聚集特性是主要反映网络节点关联性［６】的特性之一，并通过定义聚集系数来刻画节点邻居之间的亲疏程度．基于自治域级Ｉｎｔｅｍｅｔ网络拓扑的相关研究表吲４４，４５１，实陌－－．。。］．。。。。。。’。。…ｚ。．。的聚集系数，且低度数节点也很可能具有较高的局部聚集系数．然而，目前相当多的嘲络拓扑模型并不能刻画出这一拓扑特性．有关详细的聚集系数介绍参见第２．２节．

２．２主要度量指标

目前，在Ｉｎｔｅｒｎｅｔ网络拓扑建模中使用的主要度量指标包括节点度分布、聚集系数、介数、核数、平均路径长度等：

（１）节点度分布Ｐ（扮：节点度分布函数尹（七）定义为网络中度数为后的节点个数占总节点数的比例，也等于在随机一致原则下挑选出的节点具有度数ｋ的概率；所有节点度之和的平均值则称为网络的节点平均度（”．

规则图中：所有节点拥有相同数量的边，即节点的度分布ｐ（七）函数为定值；

随机图中：节点的度分布遵循泊松分布，大多数网络节点的度都集中于网络节点平均度门ｐ附近，远离峰值的节点数呈指数衰减，即随机图中一个节点拥有ｋ条边（七大于等于节点平均度）的概率很小：

无标度嘲络中：节点的度分布接近幂律形式分布Ｉ口（七）一ｋ－ｒ．

（２）聚集系数：聚集系数（ｃｌｕｓｔｅｒｉｎｇｃｏｅｆｆｉｃｉｅｎｔ）是从全局来刻画网络的聚集特性的度量指标，用来刻画一个节点邻居之间的亲疏程度．Ｄｏｒｏｇｏｖｔｅｓｅｖｔ删给出了３种不同的衡量聚集特性的参数。分别为：

局部聚集系数Ｃ（∞：

Ｃ（．ｉ｝）＝［，，ｌ。（七）】／（七（七一１）／２），

其中，［ｍ。（动】表示节点度为ｋ的节点的邻居之间平均存在的连接数．

平均聚集系数（ｍｅａｎｌｏｃａｌｃｌｕｓｔｅｒｉｎｇ）：’

周苗等：Ｉｎｔｅｍｅｔ网络拓扑建模１１３

一●＇

ｋｃ＝∑Ｐ（七）ｃ（七），

其中，Ｐ∞表示图中任意一个节点的度数为七的概率，即节点的度分布

全局聚集系数（ｃｌｕｓｔｅｒｉｎｇｃｏｅｆｆｉｃｉｅｎｔ）：

∑Ｐ（七）［‰（七）】

Ｃ础＝

ＩＩ∑Ｐ（ｋ）ｋ（七一１）／２＝—』—————————．—＝：——．一，【后２】一七∑Ｐ（七）七（七一１）ｃ（七）

其中，眵］表示节点度的二阶矩阵，ｋ表示网络的平均节点度数．

目前，在拓扑建模领域，通常使用平均聚集系数来衡量聚集特性，但是，这一度量指标并不总能正确地反映网络的真实情况．在某些情况下，平均聚集系数和全局聚集系数可能存在不一致性【４３１，需要更深入的研究、分析、论证．

（３）介数（ｂｅｔｗｅｅｎｎｅｓｓ）：介数【４６】也是Ｉｎｔｅｒｎｅｔ网络拓扑的一个重要度量，分为节点介数（ｎｏｄｅｂｅｔｗｅｅｒｍｅｓｓ）和边介数（ｅｄｇｅｂｅｔｗｅｅｎｎｅｓｓ）．其中，节点介数衡量了通过网络中该节点的最短路径的数目，反映了节点在网络中的枢纽性，节点介数越大，说明这个节点的枢纽性越强，删除这样的节点会造成大量节点对之间的最短路径变长：边介数定义为在网络的所有最短路径中，通过某条边的最短路径的条数，类似地，边介数也同样反映了该边在网络中的枢纽性．

若用呀表示节点ｆ和．，之间最短路径的数目，，为节点或边，啾Ｊ『）代表节点ｆ和，之间通过，的最短路径的条数，得到介数的数学表达为

马＝∑ａ，ＡＯ／％

在Ｇｏｈ等人【４７１指出网络中节点介数的分布遵循幂律分布之后，Ｍａｈａｄｅｖａｎ等人进一步在文献［４８】中对从３个渠道获得的拓扑数据进行分析，提出Ｉｎｔｅｍｅｔ网络节点介数与度数（ｄｅｇｒｅｅ）之间的关系，由图２【４８１可以看到，对于从ＢＧＰ路由表和Ｓｋｉａｅｒ这两种渠道获得的Ｉｎｔｅｒｎｅｔ网络拓扑数据，节点介数和度数之间呈现出明显的幂律关系．

介数是能够体现流量特性的性能度量指标，关系到链路带

宽以及路由器节点的利用率等，尤其是在基于最短路径生成的

网络中．

（４）核数：若一个节点存在于七．核（七．ｃｏｒｅ），而在（斛１）．核中被

移除，则称这个节点的核数（ｃｏｒｅｎｅｓｓ）为后；其中，缸核是指原始图

经过迭代消去所有节点度小于或等于七的节点后得到的子图．

一个核数为ｋ的节点可以出现在ｋ核子图中，但不会出现在（七＋１）

核的子图里，我们也把所有节点核数中的最大值称为图的核数．

节点核数（ｎｏｄｅｃｏｒｅｎｅｓｓ）在某种程度上说是比节点度数更

反映关联性的度量指标，可以表明节点在核中的深度．若一个节

点的节点度数很高而同时节点核数很小，则说明其关联并不紧

密．例如，在具有Ⅳ个节点的星形网络中，其中心节点的度数为Ⅳ＿ｌ而核数为０，此时，它与邻居节点的连通性易于破坏．

图３１９１表明了Ｉｎｔｅｍｅｔ网络节点核数和度数的关系，当节点度小于１００时，节点核数和度数呈现幂律关系；当度数大于１００时。网络节点核数基本保持不变．

（５）平均路径长度（ａｖｅｒａｇｅｐａｔｈｌｅｎｇｔｈ）：平均路径长度代表所有节点对之间的距离的均值，定义为【４９１

Ｆｉｇ．２Ｎｏｒｎｌａｌｉｚｅｄｎｏｄｅｂｅｔｗｅｅｎｎｅｓｓ曰，图２标准化介数与度数的关系

扛击弘

１１４ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．２０，Ｎｏ．１，Ｊａｎｕａｒｙ２００９其中，西表示节点ｉ到节点．，的最短路径．该度量指标用于刻画网络的连通性‘５０１

３自治域级拓扑建模

Ｉｎｔｅｍｅｔ网络拓扑建模按照层次的不同，可分为自治域级拓扑建模与路由器级拓扑建模．在自治域级拓扑模型中（如图４所示【１９１），节点代表一个自治系统（Ａｓ），边代表自治系统之间的连接关系．随着网络技术的不断发展，自治域级拓扑建模经历了从随机图拓扑模型发展到基于层次结构的拓扑模型，再到目前基于节点度的拓扑模型这３个发展阶段．由于Ｉｎｔｅｒｎｅｔ网络规模的飞速发展，截止２００７年７月，全世界的自治域总数从２０００年的８０００多个迅速增长到大约２８０００个，自治域间连接超过８２０００条，因此，进一步研究全球互联网络的自治域级拓扑建模成为人们现在的研究重点．

Ｆｉｇ．３Ａｖｅｒａｇｅｃｏｒｅｎｅｓｓｏｆｋ－ｄｅｇｒｅｅｎｏｄｅｓＦｉｇ．４ＩｎｔｅｒｎｅｔＡＳ－ｌｅｖｅｌｔｏｐｏｌｏｇｙ

图３Ｉｎｔｅｒａｃｔ网络节点核数与度数的关系图４Ｉｎｔｅｍｅｔ网络自治域级拓扑

３．１基于随机图的拓扑模型

随机图拓扑模型是Ｉｎｔｅｒｎｅｔ发展处于初级阶段时出现的网络拓扑模型，该类模型基于经典的由Ｅｒｄｏｓ和Ｒｅｎｙｉ所提出ＥＲ随机图理论１３¨，对早期的Ｉｎｔｅｒｎｅｔ，即ＡＲＰＡＮＥＴ进行了模拟再现．此类模型的节点隧机分布在一个平面上，并用概率决定任意两点间是否存在连接，不同的概率函数决定不同的拓扑模型．

Ｗａｘｍａｎ模型是随机图拓扑模型中的典型代表，该模型在１９８８年由Ｗａｘｍａｎ［５１１提出．Ｗａｘｍａｎ模型以任意两节点函数间的距离为自变量来计算两点间直接相连的概率，其概率函数为

Ｐ（∥，ｙ）＝ｔ２ｌｅ－ｄｌ（ＢＬ’．

上式中，ａ＞Ｏ，胚ｌ；ｄ为∥到１，的欧氏距离；￡为两点问的最长距离．当增加口时，所建模型将有更多的短边，更长的跳数直径，更短的长度直径；增加矽将增加模型中长边所占的比例．

Ｗａｘｍａｎ模型的平均节点度为研？ｌ口ｅ－ｄｌ（ｆｌＬ’】＝，疵日ｅ一“肛’】．对于Ｗａｘｍａｎ模型的目标边数，有一组口’肿集合可以保证达到．当模型参数强碉定时，参数工对模型的边数几乎没有影响，因为虽然Ｌ的改变会影响两节点间距离ｄ的值，但是ｄ／Ｌ的值保持不变．

由于在基于随机图的拓扑模型中，节点度数会随着节点数量的增加而增加，因此，随机图拓扑模型无法生成节点众多且节点平均度较小的网络．

３．２基于层次结构的拓扑模型

随着网络技术的进步和网络规模的迅速扩大，早期的基于随机图的拓扑模型已经无法适用，于是出现了基于层次结构的Ｉｎｔｅｒｎｅｔ拓扑模型，这类模型在２０世纪９０年代中期成为Ｉｎｔｅｍｅｔ拓扑建模的主流，可用于生成较大规模且节点平均度较小的网络．其中，较有代表性的有Ｔｉｅｒｓ模型【５２】、Ｔｒａｎｓｉｔ．Ｓｔｕｂ模型【５３１和ＧＴＩＴＭ［５４１模型等．

Ｔｉｅｒｓ模型的目的在于反映ＷＡＮ，ＭＡＮ和ＬＡｂ／这３个层次之间的自治域连接关系，在建摸过程中需要指定

周苗等：Ｉｎｔｅｍｅｔ网络拓扑建模１１５ＭＡＮ和ＬＡＮ的目标个数，并且ＬＡＮ采用星形拓扑结构．Ｔｒａｎｓｉｔ．Ｓｔｕｂ模型则利用不同大小的限制空间分别限制各层上的节点．

３．３基于节点度的拓扑模型

１９９９年至今，随着幂律分布特性的揭示，Ｉｎｔｅｒｎｅｔ网络拓扑建模进入了一个新的发展阶段，出现了更能反映较大规模Ｉｎｔｅｒｎｅｔ网络的自治域级拓扑模型，即基于节点度的自治域级拓扑模型．在目前已出现的大量自治域级拓扑模型中，比较有代表性的是静态模型Ｉｎｅｔ［５５１，动态模型ＢＡｔ５６１，ＡＢ［５６１，ＢＲＩＴＥ［５７１，ＧＬＰ［５８１，Ｄｐ［５９１，ＰＦｐ／砷１，ＴＡＮＧ［６１１，ＧＬＲＧ［６２】，ＣＭＵ［６３垮：

（１）静态模型Ｉｎｅｔ：在建模过程中采用非线性优先的连接方式，通过初始放置所有节点，并对每个节点分配连接度，从而有层次地添加边．尽管ｌｎｅｔ无法反应Ｉｎｔｅｍｅｔ的动态变化，但对于某种特定规模的Ｉｎｔｅｍｅｔ网络，能够较为真实地反应某些拓扑特性，如度分布遵循幂律分布，且最大度也接近真实网络的实际值等．Ｗｉｎｉｃｋ和Ｊａｍｉｎ在文献［５５】中提出Ｉｎｅｔ模型可模拟３０３７个节点的实际网络，即１９９７年Ｉｎｔｅｒｎｅｔ网络中的自治域数目．

（２）动态模型ＢＡ：ＢＡ模型是第一个演化网络模型，由Ｂａｒａｂａｓｉ和Ａｌｂｅｒｔ等人提出，现在拓扑建模研究中普遍将其作为无标度网络基本模型．ＢＡ模型也是第一个从动态增长观点研究复杂网络具有幂律度分布特性的模型，并论证了生成无标度网络的两条重要机理：增长（ｇｒｏｗｔｈ）和择优（ｐｒｅｆｅｒｅｎｔｉａｌａｔｔａｃｈｍｅｎｔ）．但是，ＢＡ模型对初始网络没有完全设定，只说明开始给定玎。个节点，但这胛。个节点间如何建边尚未讨论，而对于不同的初始网络，其后演化的结果网络并不相同；并且，ＢＡ模型的算法可能导致重复建边．另外，优先连接也并不适用于所有出现幂律分布的情形，即便是对于某些无标度网络，利用优先连接来解释幂律的形成机理也很不合理【６４１．

（３）ＡＢ模型：ＡＢ模型是Ａｌｂｅｒｔ和Ｂａｒａｂａｓｉ对ＢＡ模型的修正，该模型采用了线性优先的连接方式，通过概率增加点和边，并对内部边重新配置，保证了孤立节点建立新连接的可能性，逐步生成动态的ＡＳ级拓扑模型．ＡＢ模型的连接度分布呈现幂律，且幂律指数接近真实网络．但是，它在聚类系数和特征路径长度上存在着很强的负相关性，其聚类系数严重低于网络实际值；并且，在最大连接度和次最大连接度等方面也都和实际网络存在较大的偏差∽１．

（４）ＢＲＩＴＥ模型：是一种采用Ｗａｘｍａｎ概率与线性优先相结合方式的动态自治域级拓扑模型，其特点在于反映实际Ｉｎｔｅｒｎｅｔ拓扑的多面性，如层次性和连接度分布等，对于不同的参数及不同的节点分布方式，ＢＲＩＴＥ会产生不同的拓扑特性．另外，在建模过程中，它将当时已存在的Ｗａｘｍａｎ，ＡＢ，Ｉｎｅｔ都融合其中，并提供了更好的接口界面供仿真使用．

（５）ＧＬＰ模型：即广义线性优先模型，它的建模过程依靠广义线性优先的连接方式，其思想方法是假设Ｉｎｔｅｒｎｅｔ网络中的节点比ＢＡ线性优先连接更倾向于连接到高度数节点．ＧＬＰ模型中的度分布也服从幂律分布规律，在幂律指数和最大连接度上接近真实Ｉｎｔｅｒｎｅｔ网络，但其特征路径长度和聚类系数略低于实际值畔】．

（６）ＤＰ模型：亦采用线性优先的连接方式，又叫动态优先模型．其建边条件根据自治域之间的Ｃ．Ｓ关系或对等关系，其结果反映了一定规模Ｉｎｔｅｍｅｔ的小世界现象，但当聚类系数不断增大时。ＤＰ模型无法反映这种变化趋势．

（７）ＰＦＰ模型：又称为正反馈优先模型，其建模过程基于新的节点与内部边交互增长和非线性优先连接这两个机理，重点在于反映自治域层面Ｉｎｔｅｍｅｔ拓扑中存在的富人俱乐部（ｒｉｃｈ．ｃｌｕｂ）现象．

（８）ＴＡＮＧ模型：ＴＡＮＧ模型的幂律指数和叶子节点所占比例均接近实际值，并且在一定程度上反映出Ｉｎｔｅｒｎｅｔ的聚类特性，其构建思想基于增量加边和超线性优先连接．

小结上述自治域级拓扑模型可以看到：现有自治域级拓扑建模算法相对单一，大多数模型都基于优先连接这样的类似原理上，造成所建模型的不完备性．除不完备性外，在最近的自治域级网络拓扑建摸研究中，ＲｉｃａｒｄｏＯｌｉｖｅｉｒａ等人【８】针对实时自治域级拓扑建模会受到Ｉｎｔｅｒｎｅｔ路由抖动等因素影响的现象，定义了ｌｉｖｅｎｅｓｓ问题，并尝试建立能够反映实时变化的自治域级拓扑模型．他们提出，只有在解决ｌｉｖｅｎｅｓｓ问题的前提下，才能够进一步正确判断观测拓扑的变化是否反映出真实ＡＳ节点或链路的增加或删除，而不是由短暂的动态路由变化所产生的暂时拓扑改变．所谓拓扑建模的ｌｉｖｅｎｅｓｓ问题，即在实时观测拓扑变化过程中，如何区分出那些暂时的动态

１１６ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏｉ．２０，Ｎｏ．１，Ｊａｎｕａｒｙ２００９路由所引起的真实网络拓扑变化的问题．我们用Ｇ。，表示真实网络拓扑图，用Ｇ咖，表示由观测数据得到的拓扑观测图，则Ｇ。，包含于Ｇｏ咖，这两类拓扑图的不同我们称之为拓扑建模中的完整性问题．而ｌｉｖｅｎｅｓｓ问题则可以具体化为：当Ｇｏ抽中一个节点或一条边消失的时候，该节点或边是否还存活于瓯，中；当‰，中某个节点或某条边首次出现的时候，该节点或边是否曾存活于Ｇ。，中．Ｏｌｉｖｅｉｒａ等人认为，路由抖动等因素对自治域级拓扑模型的正确性影响很大，直接关系到所建模型的正确性．

４路由器级拓扑建模

在路由器级拓扑模型中，节点和边所指代的对象均与自治域级拓扑模型中不同，其节点代表各自治域内的路由器，边代表路由器之间的】跳连接关系．如图５所示．

Ｆｉｇ．５Ｉｎｔｅｒｎｅｔｒｏｕｔｅｒ－ｌｅｖｅｌｔｏｐｏｌｏｇｙ

图５Ｉｎｔｅｒｎｅｔ网络路由器级拓扑

４．１路由器级拓扑建模研究现状

由于技术水平、安全考虑等各种原因，现有的Ｉｎｔｅｍｅｔ路由器级拓扑发现方法无法保证测量目标集合的完备性，这种真实路由器级网络拓扑数据的不完整性和不完备性极大地影响了后继的拓扑建模研究工作【６５１．因此。目前对于路由器级的拓扑建模研究仍比较少．该方向的拓扑建模研究已成为Ｉｎｔｅｍｅｔ拓扑建模研究中的主要问题之一，相应的分析理论还不够成熟．

之前关于路由器级拓扑建模的研究成果大都集中在对路由器级拓扑结构是否同样存在幂律分布特性的讨论上，出现最早的是文献【２６】对Ｐａｎｓｉｏｔ．Ｇｒａｄ数据集【６６Ｉ中存在幂律分布特性的论证，相关研究包括Ｍａｇｏｎｉ等人【６７１通过３个不同规模的路由器级拓扑实例验证了幂律分布特性；Ｂｒｏｉｄｏ等人【６８】则基于Ｓｋｉｔｔｅｒ所获取的数据讨论了路由器级拓扑的度分布．

在幂律分布特性被验证以后，无标度模型曾被一度认为可同样适用子路由器级拓扑建模．文献ｆ６９】首先指出这种不考虑设计因素的生长模型不适合于描述Ｉｎｔｅｍｅｔ拓扑，应该寻找具有优化设计特点的生长模型．应该权衡资源消耗等因素；文献【２１】认为成本、性能、结构优化等因素在路由器级Ｉｍｅｍｅｔ拓扑建模过程中可能具有极为重要的影响，并指出应该以此为理论基础来解释幂律特性的生成原理。基于文献ｔ２１，６９１的启发，Ｌ｛等人【１３】提出基于网络性能优化设计的路由器级拓扑建模方法，即启发式优化拓扑模型，简称ＨＯＴ模型；文献［１３】论证说明各ＩＳＰ所部署路由器的自身性能和ＩＳＰ的经济考量是影响路由器级拓扑的最重要因素，并且验证了仅基于节点度分布的无标度模型不符合真实的路由器级拓扑结构．这种启发式优化的建模思想为路由器级拓扑建模指出了新的发展方向【２ｊ，即从随机原则到设计原则的转变．

在现有的路由器级拓扑建模中，随着ＨＯＴ模型的提出，已更多地开始考虑能够反映实际网络行为特征的度量指标，如与路由器性能相关的链路带宽、与反映网络路由器实际部署的节点间距离等等，如文献［７０】中ＣＩＳＣＯ提出的层次设计模型（ＬＤｍｏｄｅｌ）等，但目前仍不够成熟，其典型性与适用性都需要进一步研究分析．

４．２路由器级无标度模型

由于路由器级拓扑同样存在幂律分布特性［２６，６７．６８】，因此，基于节点度分布的无标度模型被一度认为可同样用于路由器级拓扑建模，并刻画出相关网络特性，如鲁棒且脆弱性等．

周苗等：Ｉｎｔｅｍｅｔ网络拓扑建模１１７在无标度模型中，Ｉｎｔｅｒｎｅｔ网络的路由器级拓扑结构与自治域级拓扑结构一样存在少数高度数节点，并且这些高度数节点直接关系到网络连通性．因此，基于无标度模型对鲁棒且脆弱性的刻画，路由器级网络应该同样体现出针对随机故障的鲁棒性以及故意攻击高度数节点下的脆弱性．

４．３路由器级ＨＯＴ模型

受文献［６９，７０】的启发，“等人【１３１提出了基于启发式优化方法的路由器级ＨＯＴ模型．不同于无标度模型，ＨＯＴ模型具有优化设计特点，在建模分析时主要基于路由器自身性能和网络功能这两方面来度量，体现了一种从随机原则到设计原则的转变．

首先是路由器的自身性能对拓扑建模的影响，如图６所示【１３１－－台Ｃｉｓｃ０１２４１６高端路由器的节点度数与带宽的关系，可以看到，只有当度数小于１５（即路由器的并发连接小于１５）时，可实现线速，且总线带宽显著增加，证明了技术约束即路由器自身性能是影响路由器级拓扑建模的重要度量指标．

Ｆｉｇ．６ＴｅｃｈｎｏｌｏｇｙｃｏｎｓｔｒａｉｎｔｆｏｒＣＩＳＣＯ１２４１６：Ｄｅｇｒｅｅｖｓ．ｂａｎｄｗｉｄｔｈ

图６针对一台思科１２４１６：网络路由器的节点度数与带宽关系

另一个影响路由器级拓扑建模的重要因素是功能需求，即ＩＳＰ各自的经济因素和用户对网络的需求．“等人论证认为，经济因素决定到网络的设计和部署，用户需求直接关系到ＩＳＰ网络拓扑结构．

因此。针对Ｉｎｔｅｒａｃｔ网络路由器级拓扑的ＨＯＴ模型有两个基本考虑前提：约束和性能．约束是指由技术和经济因素限定路由器以及路由器间的连接，即生成模型中的点和边；后者是指骨干网络的路由器之问建边是基于性能最优原则．

基于这种网络性能优化设计思想。ＨＯＴ模型在建模过程中采用了～系列全新的度量指标，其中包括：

（１）性能相关度量

ＨＯＴ模型中采用了３个性能相关度量，分别为吞吐量（ｔｈｒｏｕｇｈｐｕｔ）、路由器利用率（ｒｏｕｔｅｒｕｔｉｌｉｚａｔｉｏｎ）和用户带宽分布（ｅｎｄｕｓｅｒｂａｎｄｗｉｄｔｈｄｉｓｔｒｉｂｕｔｉｏｎ）．建模过程中将网络最大吞吐量视为评价网络性能的标准，并通过路由器总线带宽与度数的约束条件计算网络最大吞吐量，公式如下：

尸（ｇ）＝ｍａｘｐ∑凡，

∥

ｓ．ｔ．兄Ｙ！扭．

上式中，Ｒ是路由矩阵＾是路由器节点对（ｉ９３之间符合约束条件的流量，约束条件中的Ｘ则为一系列西的最大值，矢量口代表路由器总线带宽与度数的约束．

（２）ＬｉｋｅｌｉｈｏｏｄＳ

ＨＯＴ模型没有继续选用最大似然系数作为度量指标【６５１，在对具有相同节点度分布的图ｇ进行区分时，定义

了修正的似然系数，表示相邻节点的节点度乘积之和与晟大似然系数的比值：

１１８ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．２０，Ｎｏ．１，Ｊａｎｕａｒｙ２００９

Ｊ（ｇ）＝∑“，）二（们ｑ哆，

Ｓ（ｇ）＝ｊ（ｇ）／Ｊ。。．

上式中，∽代表相邻节点ｉ和，的节点度之和，鼠曲代表修正的似然系数

通过ＨＯＴ模型与基于优先连接机理的无标度模

型ＰＡ（ｐｒｅｆｅｒｅｎｔｉａｌａｔｔａｃｈｍｅｎｔ），以及基于随机原则的无

标度模型ＧＲＧ（ｇｅｎｅｒａｌ

雷盘ｅ

Ｑｒａｎｄｏｍｇｒａｐｈ）等在网络性能和相关似然系数上的对比分析（如图７所剥１３１），Ｌｉ等人指出，ＨＯＴ模型的网络性能最佳且更接近于实际Ｉｎｔｅｍｅｔ

网络性能，并同时论证了基于最大似然系数进行路由

器级拓扑建模的网络性能很差，与实际Ｉｎｔｅｍｅｔ网络有

很大出入．

另外，通过具有相同节点度分布的４种路由器级

拓扑模型与一个路由器拓扑实例模型的对比分析（如

图８所示【２１），Ｌｉ等人验证了基于设计优化原则的ＨＯＴ

模型比基于随机原则的ＧＲＧ或ＰＡ这样的无标度模型

更接近于真实网络拓扑结构，同时也证明了具有相同

ｄｅｇｒｅｅ．ｒａｎｋ幂律分布的无标度图可以有完全不同的结磊看０山矗Ｆｉｇ．７ＰｅｒｆｏｒｍａｎｃｅＶＳ．１ｉｋｅｌｉｈｏｏｄｆｏｒｅａｃｈｔｏｐｏｌｏｇｙ图７ＨＯＴ模型与其他模型的性能与相关似然

构．图８（ａ）为５种模型所采用的相同节点度分布Ｄ；图８（ｂ）为ＰＡ模型；图８（ｃ）为ＧＲＧ模型；图８（ｄ）为ＨＯＴ模型；图８（ｅ）为路由器级拓扑结构实例；图８（０是由高度数节点所构成、完全不考虑网络性能的假想模型．

Ｆｉｇ．８Ｆｉｖｅｎｅｔｗｏｒｋｓｈａｖｉｎｇｔｈｅｓａｍｅｎｏｄｅｄｅｇｒｅｅｄｉｓｔｒｉｂｕｔｉｏｎ

图８具有相同节点度分布的５种路由器级网络拓扑模型

４．４ＨＯＴ模型与无标度模型对比分析

通过ＨＯＴ模型与无标度模型在网络性能上的对比，Ｄｏｙｌｅ等人㈣进一步发现基于设计优化原则的ＨＯＴ模型网络性能明显提高（如图９所示）；同时也指出了路由器级拓扑结构所存在的鲁棒且脆弱性的生成机理与传统无标度模型所刻画的不一致，见表１。从表１可以看到，ＨＯＴ模型比无标度模型更接近于实际的路由器级网络的

拓扑结构，例如，按照传统无标度模型，则路由器级拓扑中的高度节点应为骨干网核心节点，但实际网络中的高

周苗等：Ｉｎｔｅｍｅｔ网络拓扑建模１１９度数节点却应该是骨干网边界路由器，这与ＨＯＴ模型所刻画的相符

蓁

ＲｏｕｔｅｒｎｏｄｅｄｅｇｒｅｅＮａｍｂｅｒｏｆｎＯｄｅｓａｔｔａｃｋｅｄ

（ａ）Ｃｃ）

Ｆｉｇ．９ＰｅｒｆｏｒｍａｎｃｅｏｆＨＯＴｎｅｔａｎｄＳＦｎｅｔ

图９ＨＯＴ模型与ｓＦ模型的网络性能对比

ＴａｂｌｅＩＣｏｍｐａｒｉｓｏｎｏｆＳＦｎｅｔ．ＨＯＴｎｅｔａｎｄｒｅａｌｒｏｕｔｅｒ－ｌｅｖｅｌｔｏｐｏｌｏｇｙ

表１无标度模型、ＨＯＴ模型与真实路由器级拓扑对比

ＳｔｒｕｃｔｕｒｅＳＦｎｅｔＨｏＴｎｅｔＲｅａｌＩｎｔｅｒｎｅｔ

ＨｉｇｈＤｅｇ．ＶｅｒｔｉｃｅｓＣｏｒｅＰｅｒｉｐｈｅｒｙＰｅｒｉｐｈｅｒｙ

Ｄｅｇ．Ｄｉｓｔ．Ｐｏｗｅ卜ＬａｗＰｏｗｅｒ－ＬａｗＨｉｇｈｌｙｖａｒｉａｂｌｅ

ＧｅｎｅｒａｔｅｄｂｙＲａｎｄｏｍＤｅｓｉｇｎＤｅｓｉｇｎ

ＣｏｒｅｖｅｒｔｉｃｅｓｈｉｇｈｄｅｇｒｅｅＬｏｗｄｅｇｒｅｅＬｏｗｄｅｇｒｅｅ

ＴｈｒｏｕｇｈｐｕｔＬｏｗＨｉｇｈＨｉｇｈ

ＡｔｔａｃｋｔｏｌｅｒａｎｃｅＦｒａｇｉｌｅＲｏｂｕｓｔＲｏｂｕｓｔ

！翌ｇ！！ｉ生．一一一．望ｉｇ！：旦望！！！！盥！：旦望！！丝！！堕！生旦Ｕ苎！！

这种启发式优化建模思想为路由器级拓扑建模指出了新的发展方向【ｌ’２１，即从随机原则到设计原则的转变，使路由器级拓扑模型从不考虑性能设计等因素的无标度模型过渡到基于设计原则的全局优化模型．

有待改进的是，ＨＯＴ模型本身也存在局限性，ＨＯＴ模型在建模过程中仅能针对单个ＩＳＰ管辖内的路由器级拓扑，而无法刻画更大规模的路由器级网络拓扑结构．

但是，随着ＨＯＴ模型的提出，目前的路由器级建模更加注重能够体现真实路由器级网络行为特征及细粒化的物理指标，如链路带宽、网络流量、网络时延以及实际部署结构，节点间距离等．

５展望

综上所述，我们可以发现，现阶段所有的Ｉｎｔｅｒｎｅｔ网络拓扑模型，不论自治域级或者路由器级，都存在～些不足，其中特别是路由器级的拓扑建模研究仍处于起步阶段，目前的研究成果和方法尚待丰富和发展．前面已经看到，作为复杂网络的典型代表，Ｉｎｔｅｍｅｔ网络拓扑具有许多基本参数，如节点度及其分布、聚集系数、介数和核数等，但更重要的是，新度量指标的有待发现，这些度量指标与网络性能（如同步性能、路由性能等等）之间相互影响的内在机制如何，都需要后来的研究人员进一步通过大量的数值仿真和实证来加以研究，从而对Ｉｎｔｅｍｅｔ拓扑特性和度量指标作更深入的定性和定量分析．

到目前为止，Ｉｎｔｅｒｎｅｔ网络拓扑建模已经取得了丰硕的研究成果，但是也存在许多困难和难点，该领域的未来研究一方面将继续沿着自治域级和路由器级拓扑建模的方向纵深发展；另一方面，还需继续探索新的网络拓扑特性和度量指标；研究将Ｉｎｔｅｍｅｔ拓扑建模相关理论用于下一代ＩＰｖ６互联网体系结构设计的有关问题．具体包括：

（１）拓扑数据发现

真实拓扑数据的获得是Ｉｎｔｅｍｅｔ网络拓扑建模的前提．研究如何探测获得全球规模的完备自治域级和路由器级拓扑数据仍然是研究的难点，特别是当前随着ＩＰｖ６网络研究的深入，给拓扑数据发现又带来了一些新问题，ＩＰｖ６地址结构的扩大使得原有ＩＰｖ４网络中基于穷举探测的拓扑发现方法不再适用，如何解决这些问题，都有

１２０ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．２０，Ｎｏ．１，Ｊａｎｕａｉｙ２００９待研究．

（２）自治域级拓扑建模

对于自治域级拓扑建模来说，需要探索如何构建一种基于实际拓扑结构并能真实反映实时节点与链路变化的完备性自治域级拓扑模型，进一步考虑Ｉｎｔｅｒｎｅｔ路由抖动等因素对拓扑建模的影响；探索建立全球大范围内的自治域级拓扑模型．

（３）路由器级拓扑建模

对于路由器级拓扑建模而言，基于设计原则的全局优化模型是接下来要研究的重点．ＨＯＴ模型的提出有力地证明了路由器级拓扑结构的非随机性，使路由器级拓扑建模开始由传统的无标度模型向基于设计原则的全局优化模型过渡，未来研究中如何更好地体现这种设计优化，如何更好地刻画网络性能和用户需求等建模相关度量，以及如何建立更大规模的路由器级网络拓扑模型等均是研究重点；并且，进一步在路由器级拓扑建模时体现真实路由器级网络拓扑的连通结构及细粒化物理指标，如链路带宽和网络时延甚至节点间距离，对于今后探索路由器级网络拓扑特性研究也具有重要意义；另外，建模过程要更加基于模型本身的实际应用，例如建立网络路由模型时更注重与路由相关的传输损耗和公平性等等．

（４）拓扑特性和度量指标

不论对于自治域级还是路由器级拓扑建模，实际拓扑结构中到底存在哪些未知拓扑特性仍有待探索，而对于已知特性，如幂律分布特性、鲁棒且脆弱性、聚集特性等来说，研究这些特性的生成机理以及如何刻画并利用这些特性对实际网络性能进行改善等等也都是今后的研究重点．

（５）实际应用

研究将Ｉｎｔｅｍｅｔ网络拓扑建模的相关理论进一步联系实际应用，探索拓扑特性和拓扑结构等对网络行为以及网络性能的影响，最终改善网络技术及提高网络服务性能．如针对网络数据搜索，挖掘不同粒度的骨干网络，探索全球范围Ｉｎｔｅｒｎｅｔ网络中的聚集现象并做出定量评估。这对于解决数据信息和信息源的分类、测量和控制问题，均有深远意义；又如研究病毒传播与网络拓扑结构的相互影响，进一步达到抑制网络病毒传播的目的等等．另外，特别需要探究将相关理论在下一代ＩＰｖ６互联网体系结构设计中的应用问题．

６总结

总结如前所述的自治域级拓扑模型可以看到：（１）相当多的自治域级拓扑建模工作都仅基于某一个或某几个度量指标上，如节点度分布等，从而直接带来了建模的不准确性和不完整性；（２）生成算法比较单一，很多模型都基于优先连接这样的类似原理；（３）这些自治域级网络拓扑模型均针对某一个或少数拓扑特性，缺乏完备性．而在路由器级拓扑建模中，现有的研究成果显示，基于设计优化原则的ＨＯＴ模型比基于随机原则的无标度模型更符合真实路由器级拓扑结构，在网络性能上也更接近于真实的路由器级网络拓扑；并且传统无标度模型也无法用于刻画路由器级网络拓扑特性（如鲁棒且脆弱性）生成机理的刻画．ＨＯＴ模型的提出进一步带来路由器级拓扑建模由传统基于随机原则的无标度模型向基于设计原则的全局优化模型的转变．

本文针对Ｉｎｔｅｒｎｅｔ网络拓扑建模这一研究领域，概要介绍了Ｉｎｔｅｍｅｔ网络拓扑建模的概念和意义以及研究内容和研究方法：在分析了Ｉｎｔｅｒｎｅｔ网络主要的拓扑特性和度量指标后，分别详细讨论了自治域级和路由器级的拓扑建模成果和现有拓扑模型；总结了现阶段该研究领域的相关不足以及今后的若干发展方向．

目前Ｉｎｔｅｒｎｅｔ网络拓扑建模的首要困难是缺乏完备的大规模网络真实拓扑数据，我们知道，Ｉｎｔｅｒｎｅｔ拓扑建模和分析均是以发现网络真实拓扑数据作为基础的，然而现阶段在Ｉｎｔｅｒ，ｎｅｔ拓扑研究中所能利用到的真实数据不仅稀少，并且还受到技术、地域以及社会人为因素的种种限制，这些约束条件造成发现的数据结果不完善及不准确，因此如何提高拓扑发现的效率和正确性仍是我们需要解决的首要问题，特别地，目前处于ＩＰｖ４／ＩＰｖ６过渡时期，给真实拓扑数据的获取增加了新的困难，因此，我们后继工作的一个重要部分就是以ＣＥＲＮＥＴ２骨干网为基础，多探测一些发现完整并且实时变化的拓扑真实数据，并探索现实大规模网络范围内对链路带宽和节点通信量的测量与数据更新方法．

周苗等：Ｉｎｔｅｒｎｅｔ网络拓扑建模１２ｌ致谢感谢清华大学网络协议与测试实验室与网络中心网络运行管理技术研究室各位老师和同学的关心和支持，与诸位的讨论使我们受益匪浅．

Ｒｅｆｅｒｅｎｃｅｓ：

［１１ＫｆｉｏｕｋｏｖＤ，ＣｈｕｎｇＦ，ＣｌａｆｆｙＫＣ．ＴｈｅｗｏｒｋｓｈｏｐｏｎＩｎｔｅｍｅｔｔｏｐｏｌｏｇｙ（１Ｉ）ｌ，１１）ｒｅｐｏｒｔ．ＡＣＭＳＩＧＣＯＭＭＣｏｍｐｕｔｅｒＣｏｍｍｕｎｉｃａｔｉｏｎ

Ｒｅｖｉｅｗ，２００７。３７（１）：６９－７３．

【２】ＡｌｄｅｒｓｏｎＤ，ＬｉＬ，ＷｉｌｌｉｎｇｅｒＷ．ＵｎｄｅｒｓｔａｎｄｉｎｇＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙ：Ｐｒｉｎｃｉｐｌｅｓ，ｍｏｄｅｌｓａｎｄｖａｌｉｄａｔｉｏｎ．ＡＣＭＴｒａｎｓ．ｏｎＮｅｔｗｏｒｋｉｎｇ．

２００５，１３（６）：１２０５－１２１８．

【３】ＭａｈａｄｅｖａｎＰ．ＨｕｂｂｌｅＣ，ＫｒｉｏｕｋｏｖＤ．Ｏｒｂｉｓ：Ｒｅｓｃａｌｉｎｇｄｅｇｒｅｅｃｏｒｒｅｌａｔｉｏｎｓ

ｔｈｅＡＣＭｔｏｇｅｎｅｒａｔｅａｎｎｏｔａｔｅｄＩｎｔｅｒａｃｔｔｏｐｏｌｏｇｉｅｓ．Ｉｎ：Ｐｒｏｃ．ｏｆＳｌＧＣＯＭＭ．２００７．

ｓｔｒｕｃｔｕｒｅ【４】ＮｅｗｍａｎＭ．ＴｈｅａｎｄｆｕｎｃｔｉｏｎｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓＳＩＡＭＲｅｖｉｅｗ，２００３，４５：１６７—２５６．

ａ【５】ＶｉｇｅｒＦ，ＢａｒｒａｔＡ，Ｄａｌｌ’ＡｓｉａＬ，ＺｈａｎｇＣＨ，ＫｏｌａｃｚｙｋＥＤ．Ｗｈａｔｉｓｔｈｅｒｅａｌｓｉｚｅｏｆ

ＰｈｙｓｉｃａｌＲｅｖｉｅｗｓａｍｐｌｅｎｅｔｗｏｒｋ？ＴｈｅｃａｓｅｏｆｔｈｅＩｎｔｅｒｎｅｔ．Ｅ，２００７。７５（５）：０５６１１１．

Ｃｏｍｐｌｅｘ【６】ＧｕｏＬ，ＸｕＸＭ．ＴｈｅＮｅｔｗｏｒｋ．ＳｈａｒＩｇｈａｉ：ＳｈａｎｇｈａｉＳｃｉｅｎｔｉｆｉｃａｎｄＴｅｃｈｎｏｌｏｇｉｃａｌＥｄｕｃａｔｉｏｎＰｕｂｌｉｃａｔｉｏｎ，２００６（ｉｎ

Ｃｈｉｎｅｓｅ）．

Ｄａｌｌ’ＡｓｔａＬ，ＨａｍｅｌｉｎＩＡ，ＢａｒｒａｔＡ．Ｅｘｐｌｏｒｉｎｇｎｅｔｗｏｒｋｓｗｉｔｈｔｒａｃｅｒｏｕｔｅ ｌｉｋｅ

Ｓｃｉｅｎｃｅ，２００５，３５５：６－２４．ｐｒｏｂｅｓ：Ｔｈｅｏｒｙａｎｄｓｉｍｕｌａｔｉｏｎｓ．ＴｈｅｏｒｅｔｉｃａｌＣｏｍｐｕｔｅｒ

【８】

１９］ＯｌｉｖｅｉｒａＲＺｈａｎｇＢＣ，ＺｈａｎｇＬＸ．ＯｂｓｅｒｖｉｎｇｔｈｅｅｖｏｌｕｔｉｏｎｏｆＩｎｔｅｒｎｅｔＡＳｔｏｐｏｌｏｇｙ．Ｉｎ：ｌｈ＇ｏｃ．ｏｆｔｈｅＡＣＭＳＩＧＣＯＭＭ．２００７．ＳＯＵＦＣＣＳＭａｈａｄｅｖａｎＰ，ＫｒｉｏｕｋｏｖＤ，ＦｏｍｅｎｋｏｖＭ．ＴｈｅＩｎｔｅｍｅｔＡＳ－ｌｅｖｅｌｔｏｐｏｌｏｇｙ：Ｔｈｒｅｅｄａｔａ

Ｃｏｍｍｕｎｉｃａｔｉｏｎａｎｄｏｎｅｄｅｆｉｎｉｔｉｖｅｍｅｔｒｉｃ．ＣｏｍｐｕｔｅｒＲｅｖｉｅｗ．２００６，３６（１）：１７－２６．

ＡＣＭ［１０】ＭａｈａｄｅｖａｎＰ，ＫｒｉｏｕｋｏｖＤ，ＦａｌｌＫ．Ｓｙｓｔｅｍａｔｉｃｔｏｐｏｌｏｇｙａｎａｌｙｓｉｓａｎｄｇｅｎｅｒａｔｉｏｎｕｓｉｎｇｄｅｇｒｅｅｃｏｒｒｅｌａｔｉｏｎｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅ

ＳｌＧＣＯＭＭ．２００６．

【１ｌ】ＺｈａｎｇＹ，ＺｈａｎｇＨＬ，ＦａｎｇＢＸ．Ａｓｕｒｖｅｙ

ｗｉｔｈＥｎｇｌｉｓｈｏｎＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｍｏｄｅｌｉｎｇ．ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，２００４，ｌ５（８）：１２２０—１２２６（ｉｎＣｈｉｎｅｓｅａｂｓａ＇ａｃｔ）．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ＣＷｌ０００－９８２５／１５／１２２０．ｈｔｍ

【１２】ＺｅｎｇＷ，ＸｕＭＷ，ＷｕＪＰ．Ｓｕｒｖｅｙｏｆｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｍｏｄｅｌｓ．ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ，２００５，（７）（ｉｎＣｈｉｎｅｓｅｗｉｔｈ

ａｂｓｔｒａｃｔ）．

Ｄ，ＷｉｌｌｉｎｇｅｒＷ．Ａｆ＇ｆｉｓｔ—ｐｒｉｎｃｉｐｌｅｓａｐｐｒｏａｃｈｔｏＥｎｇｌｉｓｈ【１３】ＬｉＬ，ＡｌｄｅｒｓｏｎｕｎｄｅｒｓｔａｎｄｉｎｇｔｈｅＩｎｔｅｒｎｅｔ’ｓｒｏｕｔｅｒ—ｌｅｖｅｌｔｏｐｏｌｏｇｙ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅ

ＡＣＭＳＩＧＣＯＭＭ．２００４．

［１４】ＤｏｙｌｅＪＣ，ＡｌｄｅｒｓｏｎＤ，ＬｉＬ，ＬｏｗＳ，ＲｏｕｇｈａｎＭ，ＳｈａｌｕｎｏｖＳ，ＴａｎａｋａＲＷｉｌｌｉｎｇｅｒＷ．Ｔｈｅ“ｒｏｂｕｓｔｙｅｔｆｒａｇｉｌｅ’’ｎａｔｕｒｅｏｆｔｈｅ

ＵＳＡ，２００５，１０２（４１）：１４４９７—１４５０２．Ｉｎｔｅｒｎｅｔ．Ｐｒｏｃ．ｏｆｔｈｅＮａｔｉｏｎａｌＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ

５】’ＳｐｒｉｎｇＮ，Ｍａｈａｊａｎ

ＳｋｉｔｔｅｒＡＳＲ，ＷｅｔｈｅｒａｌｌＤ．ＭｅａｓｕｒｉｎｇＩＳＰｔｏｐｏｌｏｇｉｅｓｗｉｔｈＲｏｃｋｅｔｆｕｅｌ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＡＣＭＳＩＧＣＯＭＭ．２００２．６】

７】

８】ａｄｊａｃｅｎｃｙｌｉｓｔ．ｈｔｔｐ：／／ｗｗｗ．ｃａｉｄａ．ｏｒｇ／ｔｏｏｌｓ／ｍｅａｓｕｒｅｍｅｎｔ／ｓｋｉｔｔｅｒ／ａｓａｄｊａｃｅｎｃｉｅｓ．ｘｍｌＳｋｉｔｔｅｒｄｅｓｔｉｎａｔｉｏｎＤｏｒｏｇｏｖｔｓｅｖ

２００３．ｌｉｓｔ．ｈｔｔｐ：／／ｗｗｗ．ｃａｉｄａ．ｏｒｇ／ｕｎａｌｙｓｉｓ／ｔｏｐｏｌｏｇｙ／ｍａｃｒｏｓｃｏｐｉｃ／ｌｉｓｔ．ｘｍｌｔｏＳＮ，ＭｅｎｄｅｓＪＦＦ．ＥｖｏｌｕｔｉｏｎｏｆＮｅｔｗｏｒｋｓ：ＦｒｏｍＢｉｏｌｏｇｉｃａｌＮｅｔｓｔｈｅＩｎｔｅｒｎｅｔａｎｄＷＷｗ．ＯｘｆｏｒｄＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ．

【１９】ＣａｒｍｉＳ，ＨａｖｌｉｎＳ，ＫｉｒｋｐａｔｒｉｃｋＳ．ＡｍｏｄｅｌｏｆＩｎｔｅｍｅｔｔｏｐｏｌｏｇｙｕｓｉｎｇｋ－ｓｈｅｌｌｄｅｃｏｍｐｏｓｉｔｉｏｎ．Ｐｒｏｃ．ｏｆｔｈｅＮａｔｉｏｎａｌＡｃａｄｅｍｙｏｆ

ＳｃｉｅｎｃｅｓｏｆｔｈｅＵＳＡ，２００７，１０４（２７）：１１１５０－１１１５４．

【２０】ＣｈａｎｇＨ，ＧｏｖｉｎｄａｎＲ，ＪａｍｉｎＳ．ＴｏｗａｒｄｃａｐｔｕｒｉｎｇｒｅｐｒｅｓｅｎｔａｔｉｖｅＡＳ—ｌｅｖｅｌＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｉｅｓ．ＣｏｍｐｕｔｅｒＮｅｔｗｏｒｋｓ，２００４，

４４（６）：７３７－７５５．

【２ｌ】ＣｈａｎｇＨ，ＪａｍｉｎＳ，ＷｉｌｌｉｎｇｅｒＷ．Ｉｎｔｅｍｅｔｃｏｎｎｅｃｔｉｖｉｔｙ

ｏｎａｔｔｈｅＡＳ—ｌｅｖｅｌ：Ａｎｏｐｔｉｍｉｚａｔｉｏｎ－ｄｒｉｖｅｎｍｏｄｅｌｉｎｇａｐｐｒｏａｃｈ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＡＣＭＳＩＧＣＯＭＭＷｏｒｋｓｈｏｐＭｏｄｅｌｓ，ＭｅｔｈｏｄｓａｎｄＴｏｏｌｓｆｏｒＲｅｐｒｏｄｕｃｉｂｌｅＮｅｔｗｏｒｋＲｅｓｅａｒｃｈ．２００３．

ｏｎｆ２２】ＤｉｍｉｔｒｏｐｏｕｌｏｓＸ．ＲｉｌｅｙＧ．Ｍｏｄｅｌｉｎｇａｕｔｏｎｏｍｏｕｓ ｓｙｓｔｅｍｒｅｌａｔｉｏｎｓｈｉｐｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅ２０ｔｈＷｏｒｋｓｈｏｐＰｒｉｎｃｉｐｌｅｓｏｆＡｄｖａｎｃｅｄ

ａｎｄＤｉｓｔｒｉｂｕｔｅｄＳｉｍｕｌａｔｉｏｎ，Ｖ０１．２６．２００６．１４３－１４９．

【２３】ＧｋａｎｔｓｉｄｉｓＣ，ＭｉｈａｉｌＭ，ＺｅｇｕｒａＥ．ＴｈｅＭａｒｋｏｖｃｈａｉｎｓｉｍｕｌａｔｉｏｎｍｅｔｈｏｄｆｏｒｇｅｎｅｒａｔｉｎｇｃｏｎｎｅｃｔｅｄｐｏｗｅｒｌａｗｒａｎｄｏｍｇｒａｐｈｓ．Ｉｎ：

ＷｏｒｋｓｈｏｐｏｎＰｒｏｃ．ｏｆｔｈｅ５ｔｈＡｌｇｏｒｉｔｈｍＥｎｇｉｎｅｅｒｉｎｇａｎｄＥｘｐｅｒｉｍｅｎｔｓ（ＡＬＥＮＥＸ）．２００３．

【２４】ＧａｏＬＯｎｉｎｆｅｒｒｉｎｇａｕｔｏｎｏｍｏｕｓｓｙｓｔｅｍｒｅｌａｔｉｏｎｓｈｉｐｓｉｎｔｈｅＩｎｔｅｒｎｅｔ．ＡＣＭＴｒａｎｓ．ｏｎＮｅｔｗｏｒｋｉｎｇ。２００１，９（６）：７３３—７４５．

１２２ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ软件学报Ｖ０１．２０，Ｎｏ．１，Ｊａｎｕａｒｙ２００９

【２５】ＣｈａｎｇＨ，ＪａｍｉｎＳ。ＷｉｌｌｉｎｇｅｒＷ．Ａｎｅｍｐｉｒｉｃａｌａｐｐｒｏａｃｈ

ＭｅａｓｕｒｅｍｅｎｔＣｏｎｆ．（Ｉ－ＭＣ）．２００５．ｔｏｍｏｄｅｌｉｎｇｉｎｔｅｒ－ＡＳｔｒａｆｆｉｃｍａｔｒｉｃｅｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＩｎｔｅｒｎｅｔ

【２６】ＦａｌｏｕｔｓｏｓＣ，ＦａｌｏｕｔｓｏｓＭ，ＦａｌｏｕｔｓｏｓＰ．Ｏｎｐｏｗｅｒ ｌａｗｒｅｌａｔｉｏｎｓｈｉｐｓｏｆｔｈｅＩｎｔｅｍｅｔｔｏｐｏｌｏｇｙ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＡＣＭＳＩＧＣＯＭＭ．

１９９９．

２７】

２８】ＡｌｂｅｒｔＲ，ＪｅｏｎｇＨ，Ｂａｒａｂ嬲ｉＡＬ．Ｅｒｒｏｒａｎｄａｔｔａｃｋｔｏｌｅｒａｎｃｅｉｎｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．Ｎａｔｕｒｅ，２０００，４０６：３８７＿４８２．ＮｅｗｍａｎＭ．Ｐｒｏｐｅｒｔｉｅｓｏｆｈｉｇｈｌｙｃｌｕｓｔｅｒｅｄｎｅｔｗｏｒｋｓ．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００３，６８：０２６１２１．

Ｎｅｗｍａｎ２９】

３０】Ｍ．Ｐｏｗｅｒｌａｗｓ，ＰａｒｅｔｏｄｉｓｔｒｉｂｕｔｉｏｎｓａｎｄＺｉｐｆｓｌａｗ．ＣｏｎｔｅｍｐｏｒａｒｙＰｈｙｓｉｃｓ，２００５，４６：３２３－３５１．Ｅｒｄ６ｓＰ，ＲｄｎｙｉＡ，Ｏｎｔｈｅｅｖｏｌｕｔｉｏｎｏｆｒａｎｄｏｍｇｒａｐｈｓ．ＰｕｂｌｉｃａｔｉｏｎｓｏｆｔｈｅＭａｔｈｅｍａｔｉｃａｌＩｎｓｔｉｔｕｔｅｏｆｔｈｅＨｕｎｇａｒｉａｎＡｃａｄｅｍｙｏｆ

Ｓｃｉｅｎｃｅｓ，１９６０，５：１７—６１．

ｌ】

２】Ｅｒｄ６ｓＰ，Ｒ６ｎｙｉＡ．Ｏｎｒａｎｄｏｍｇｒａｐｈｓ．ＰｕｂｌｉｃａｔｉｏｎｅｓＥｒｄ６ｓＰ，Ｒ６ｎｙｉＭａｔｈｅｍａｔｉｃａｅ，１９５９。６：２９０－２９７．Ａ．Ｏｎｔｈｅｓｔｒｅｎｇｔｈｏｆｃｏｎｎｅｃｔｅｄｎｅｓｓｏｆａｒａｎｄｏｍｇｒａｐｈ．ＡｃｔａＭａｔｈｅｍａｔｉｃａＳｃｉｅｎｔｉａＨｕｎｇａｒｙ，１９６１，１２：２６１－２６７．

Ｍ，ＲａｓｔｏｇｉＲ．ＥｆｆｉｃｉｅｎｔｌｙｍｏｎｉｔｏｒｉｎｇｂａｎｄｗｉｄｔｈａｎｄｌａｔｅｎｃｙｉｎＩＰｎｅｔｗｏｒｋｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＩＥＥＥ３】ＢｒｅｉｔｂａｒｔＹ，Ｇｅｒｏｆａｌａｋｉｓ

ＩＮＦＯＣＯＭ．２００１．

【３４】ＰａｒｋＫ，ＬｅｅＨ．Ｏｎｔｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｒｏｕｔｅ—ｂａｓｅｄｐａｃｋｅｔｆｉｌｔｅｒｉｎｇｆｏｒｄｉｓｔｒｉｂｕｔｅｄＤｏＳａｔｔａｃｋｐｒｅｖｅｎｔｉｏｎｉｎｐｏｗｅｒ ｌａｗＩｎｔｅｒａｃｔｓ．Ｉｎ：

Ｐｒｏｃ．ｏｆｔｈｅＡＣＭＳＩＧＣＯＭＭ．２００１．

ｍａｔｈｅｍａｔｉｃｓｏｆｉｎｆｅｃｔｉｏｕｓ【３５】

【３６】

【３７】ＨｃｔｈｃｏｔｅＨＷ．Ｔｈｅｄｉｓｅａｓｅｓ．ＳＩＡＭＲｅｖｉｅｗ，２０００，４２（４）：５９９—６５３．ＬｅｖｅｉｌｌｅＪ．Ｅｐｉｄｅｍｉｃｓｐｒｅａｄｉｎｇｉｎｔｅｃｈｎｏｌｏｇｉｃａｌｎｅｔｗｏｒｋｓ．ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ，ＨＰＬ－２００２—２８７，ＨＩ＇ＬａｂｏｒａｔｏｒｉｅｓＢｒｉｓｔｏｌ，２００２．Ｐａｓｔｏｒ—Ｓａｔｏｒｒａｓ心Ｖｅｓｐｉｇｎａｎｉ

６３（６）：０６６１１７．Ａ．Ｅｐｉｄｅｍｉｃｄｙｎａｍｉｃｓａｎｄｅｎｄｅｍｉｃｓｔａｔｅｓｉｎｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００１。

【３８】Ｐａｓｔｏｒ－ＳａｔｏｒｒａｓＲ，ＶｅｓｐｉｇｎａｎｉＡ．Ｅｐｉｄｅｍｉｃｓｐｒｅａｄｉｎｇｉｎｓｃａｌｅ－ｆｌｅｅ

Ｌｌｏｙｄｎｅｔｗｏｒｋｓ．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＬｅｔｔｅｒｓ，２００１，８６（１４）：３２００．ｆ３９】

【４０】

【４ｌ】

【４２】ＡＬ，ＭａｙＲＭ．Ｈｏｗｖｉｒｕｓｅｓｓｐｒｅａｄａｍｏｎｇｃｏｍｐｕｔｅｒｓａｎｄｐｅｏｐｌｅ．Ｓｃｉｅｎｃｅ，２００１，２９２：１３１６－１３１７．ＳＮ，ＭｅｎｄｅｓＪＦＦ．Ｅｖｏｌｕｔｉｏｎｏｆｎｅｔｗｏｒｋｓ．ＡｄｖａｎｃｅｓｉｎＰｈｙｓｉｃｓ，２００２，５ｌ：１０７９－１１８７．ＤｏｒｏｇｏｖｔｓｅｖＢａｒａｂｊｔｓｉＡＬ，ＢｏｎａｂｅａｕＥ．Ｓｃａｌｅ－Ｆｒｅｅｎｅｔｗｏｒｋｓ．ＳｃｉｅｎｔｉｆｉｃＡｍｅｒｉｃａｎ，２００３，２８８＂５０－５９．ＤｏｒｏｇｏｖｔｓｅｖＳＮ．Ｃｌｕｓｔｅｒｉｎｇｏｆｃｏｒｒｅｌａｔｅｄ

Ｂｏｌｌｏｂａｓｎｅｔｗｏｒｋｓ．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００４，６９（２）：０２７１０４．ｏｎ【４３】Ｂ，ＲｉｏｒｄａｎＯＭ．Ｍａｔｈｅｍａｔｉｃａｌｒｅｓｕｌｔｓｓｃａｌｅ ｆｒｅｅｒａｎｄｏｍｇｒａｐｈｓ．Ｉｎ：ＨａｎｄｂｏｏｋｏｆＧｒａｐｈｓａｎｄＮｅｔｗｏｒｋｓ．Ｂｅｒｌｉｎ：Ｗｉｌｅｙ－ＶＣＨ，２００３．

［４４１

【４５】

【４６】

【４７】

［４８】ＣａｒｌｓｏｎＪＭ，ＤｏｙｌｅＪ．Ｃｏｍｐｌｅｘｉｔｙａｎｄｒｏｂｕｓｔｎｅｓｓ．Ｐｒｏｃ．ｏｆｔｈｅＮａｔｉｏｎａｌＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓｏｆｔｈｅＵＳＡ，２００２，９９（１）：２５３９－２５４５．ａｎｄｖｕｌｎｅｒａｂｉｌｉｔｙｏｆｓｃａｌｅ—ｆｒｅｅｒａｎｄｏｍｇｒａｐｈｓ．ＩｎｔｅｒａｃｔＭａｔｈ，２００３，１：１－３５．ＢｏｌｌｏｂａｓＢ，ＲｉｏｒｄａｎＯ．ＲｏｂｕｓｔｎｅｓｓＨｏｌｍｅＰ，ＫｉｍＢＪ，ＹｏｏｎＣＮ，ＨａｒｔＳＫ．Ａｔｔａｃｋｖｕｌｎｅｒａｂｉｌｉｔｙｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＧｏｈＥ，２００２。６５（５）：０５６１０９．ＫＩ，ＫａｈａｎｇＢ，ＫｉｍＤ．Ｓｐｅｃ仃ａａｎｄｅｉｇｅｎｖｅｃｔｏｒｓｏｆｓｃａｌｅ—ｆｒｅｅｎｅｔｗｏｒｋｓ．ＰｈｙｓｉｃａｌＰ，ＫｒｉｏｕｋｏｖＤ，ＦｏｍｅｎｋｏｖＲｅｖｉｅｗＥ．２００１，“（５）：ｌ一５．Ｍａｈａｄｅｖａｎ

ＩｎｔｅｒｎｅｔＭ，ＨｕｆｆａｋｅｒＢ，ＤｉｍｉｔｒｏｐｏｕｌｏｓＸ．ＣｌａｆｆｙＫＣ。ＶａｈｄａｔＡ．Ｌｅｓｓｏｎｓｆｒｏｍｔｈｒｅｅｖｉｅｗｓｏｆｔｈｅｔｏｐｏｌｏｇｙ．ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ，ＣＡＩＤＡ，２００５．

ａ【４９】ＣｈｕｎｇＦ，ＬｕＬ．１１１ｅａｖｅｒａｇｅｄｉｓｔａｎｃｅｉｎ

ＳｏｕｌｅＡ，ＮａｃｃｉＡ，ＬｅｏｎａｒｄｉＥ．Ｈｏｗ

Ｏｆｔｈｅｔｏｒａｎｄｏｍｇｒａｐｈｗｉｔｈｇｉｖｅｎｅｘｐｅｃｔｅｄｄｅｇｒｅｅｓ．ＩｎｔｅｒｎｅｔＭａｔｈ，２００３，ｌ：９１－１１３．ｔｒａｆｆｉｃｍａｔｒｉｘｅｌｅｍｅｎｔｓｉｎａ【５０】ｉｄｅｎｔｉｆｙａｎｄｅｓｔｉｍａｔｅｔｈｅｌａｒｇｅｓｔｄｙｎａｍｉｃｅｎｖｉｒｏｎｍｅｎｔ．Ｉｎ：Ｐｒｏｃ．ＡＣＭＳＩＧＭＥＴＲＩＣＳ．２００４．

ｏｎ５１】

５２】ＷａｘｍａｎＢＭ．Ｒｏｕｔｉｎｇｏｆｍｕｌｔｉｐｏｉｎｔｃｏｎｎｅｃｔｉｏｎｓ．ＩＥＥＥＪｏｕｒｎａｌＤｏａｒＳｅｌｅｃｔｅｄＡｒｅａｓｉｎＣｏｍｍｕｎｉｃａｔｉｏｎｓ，１９８８，６（９）：１６１７－１６２２．Ｍ．Ａｂｅｔｔｅｒｍｏｄｅｌｆｏｒｇｅｎｅｒａｔｉｎｇｔｅｓｔｎｅｔｗｏｒｋｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＩＥＥＥＧＬＯＢＥＣＯＭ．１９９６．

５３】

５４】

５５１ＣａｌｖｅｒｔＫＬ．ＤｏａｒＺｅｇｕｒａＭ，ＺｅｇｕｒａＥ．ＭｏｄｅｌｉｎｇＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙ．ＩＥＥＥＣｏｍｍｕｎｉｃａｔｉｏｎｓＭａｇａｚｉｎｅ，１９９７，３５（６）：ｔ６０—１６３．ｔｏＥＷ，ＣａｌｖｅｒｔＫ，ＢｈａｔｔａｃｈａｏｅｅＳ．Ｈｏｗｍｏｄｅｌａｎｉｎｔｅｒｎｅｔｗｏｒｋ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＩＥＥＥＩＮＦＯＣＯＭ．１９９６．ＷｉｎｉｃｋＪ，ｌａｍｉｎＳ．Ｉｎｅｔ－３．０：Ｉｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｇｅｎｅｒａｔｏｒ．ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ，ＣＳＥ－ＴＲ－４５６—０２，ＤｅｐａｒｔｍｅｎｔｏｆＥＥＣＳ，Ｕｎｉｖｅｒｓｉｔｙｏｆ

Ｍｉｃｈｉｇａｎ，２００２．

【５６】ＡｌｂｅｒｔＫＢａｒａｂａｒｉＡＬ．Ｔｏｐｏｌｏｇｙｏｆｅｖｏｌｖｉｎｇｎｅｔｗｏｒｋｓ：ｌｏｃａｌｅｖｅｎｔｓａｎｄｕｎｉｖｅｒｓｉｔｙ．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＬｃｔｔ啪，２０００，

８５（２４）：５２３４－５２３７．

【５７１ＭｅｄｉｎａＡ，ＬａｋｈｉｎａＡ，ＭａｔｔａＩ，Ｂｙｅｒｓ

２００１．Ｊ．ＢＲＩＴＥ：Ａｎａｐｐｒｏａｃｈｔｏｕｎｉｖｅｒｓａｌｔｏｐｏｌｏｇｙｇｅｎｅｒａｔｉｏｎ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＩＥＥＥＭＡＳＣＯＴＳ．

［５ｓ】ＢｕＴ＇ＴｏｗｓｌｅｙＤ．ｏｎｄｉｓｔｉｎｇｕｉｓｈｉｎｇｂｅｔｗｅｅｎＩｎｔｅｒａｃｔｐｏｗｅｒ－ｌａｗｔｏｐｏｌｏｇｙｇｅｎｅｒａｔｏｒｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＩＥＥＥＩＮＦＯＣＯＭ．２００２．

周苗等：Ｉｎｔｅｒｎｅｔ网络拓扑建模１２３

【５９】ＰａｒｋＳＴ，ＰｅｎｎｏｃｋＤＭ，ＧｉｌｅｓＣＬ．ＣｏｍｐａｒｉｎｇｓｔａｔｉｃａｎｄｄｙｎａｍｉｃｍｅａｓｕｒｅｍｅｎｔｓａｎｄｍｏｄｅｌｓｏｆｔｈｅＩｎｔｅｒｎｃｔ’ＳＡＳｔｏｐｏｌｏｇｙ．Ｉｎ：Ｐｒｏｃ．

ＩＮＦＯＣＯＭ．２００４．ｏｆ血ｅＩＥＥＥ

【６０】

【６ｌ】ＺｈｏｕＳａｇｙＳ，ＭｏｎｄｒａｇｏｎＩＬｌ．ＡｃｃｕｒａｔｅｌｙｍｏｄｅｌｉｎｇｔｈｅＩｎｔｅｒａｃｔｔｏｐｏｌｏｇｙ．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＥ，２００４，７０（６）：０６６１０８．Ｂ。ＭｉｒａＧ，ＡｖｉｓｈａｉＷ．Ａｎｉｎｃｒｅｍｅｎｔａｌｓｕｐｅｒ—ｌｉｎｅａｒｐｒｅｆｅｒｅｎｔｉａｌＩｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｍｏｄｅｌ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＰａｓｓｉｖｅａｎｄＡｃｔｉｖｅ

ＭｅａｓｕｒｅｍｅｎｔＷｏｒｋｓｈｏｐ（ＰＡＭ）．２００４．

【６２】ＡｉｅｌｌｏＷ。ＣｈｕｎｇＦ，ＬｕＬ．Ａｒａｎｄｏｍｇｒａｐｈｍｏｄｅｌｆｏｒｍａｓｓｉｖｅｇｒａｐｈｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＡＣＭＳｙｒｕｐ．ＯｉｌＴｈｅｏｒｙｏｆＣｏｍｐｕｔｉｎｇ

（ＳＴＯＣ）．２０００．

【６３】ＰａｌｍｅｒＣ．ＳｔｅｆｆａｎＧ．Ｇｅｎｅｒａｔｉｎｇｎｅｔｗｏｒｋｔｏｐｏｌｏｇｉｅｓｔｈａｔｏｂｅｙｐｏｗｅｒｌａｗｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＩＥＥＥＧＬＯＢＥＣＯＭ．２０００．

【“】

【６５］ＷａｎｇＸＦ。ＬｉＸ，ＣｈｅｎＧＲ．ＣｏｍｐｌｅｘＮｅｔｗｏｒｋ：ＴｈｅｏｒｉｅｓａｎｄＡｐｐｌｉｃａｔｉｏｎｓ．Ｂｅｏｉｎｇ：ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，２００６（ｉｎＣｈｉｎｅｓｅ）．ＡｌｄｅｒｓｏｎＤ。ＤｏｙｌｅＪ，Ｇｏｖｉｎｄａｎ凡ＷｉｌｌｉｎｇｅｒＷ．Ｔｏｗａｒｄａｎｏｐｔｉｍｉｚａｔｉｏｎ—ｄｒｉｖｅｎｆｒａｍｅｗｏｒｋｆｏｒｄｅｓｉｇｎｉｎｇａｎｄｇｅｎｅｒａｔｉｎｇｒｅａｌｉｓｔｉｃ

ｉｎｔｅｒｎｅｔｔｏｐｏｌｏｇｉｅｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＡＣＭＳＩＧＣＯＭＭ．２００３．

ｔｒｅｅｓＰａｎｓｉｏｔＪ．ＧｒａｄＤ．ＯｎｒｏｕｔｅｓａｎｄｍｕｌｔｉｃａｓｔｉｎｔｈｅＩｎｔｅｒｎｅｔ．ＡＣＭＳＩＧＣＯＭＭＣｏｍｐｕｔｅｒＣｏｍｍｕｎｉｃａｔｉｏｎＲｅｖｉｅｗ，１９９８。

２８（１）：４１—５０．

【６７】ＭａｇｏｎｉＤ。ＰａｎｓｉｏｔＪＪ．Ｉｎｔｅｒｎｅｔｔｏｐｏｌｏｇｙｍｏｄｅｌｅｒｂａｓｅｄ

ＣｏｍｍｕｎｉｃａｔｉｏｎｓＣｏｎｆｏｎｍａｐｓａｍｐｌｉｎｇ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＩＥＥＥＳｙｍｐ．ｏｎＣｏｍｐｕｔｅｒｓａｎｄＯｓｃｃ）．２００２．

【６８】ＢｒｏｉｄｏＡ，ＣｌａｆｆｙＫＣ．Ｉｎｔｅｍｅｔｔｏｐｏｌｏｇｙ：ＣｏｎｎｅｃｔｉｖｉｔｙｏｆＩＰ伊ａｐｈｓ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅＩｎｔ’ｌＳｙｍｐ．ｏｎＣｏｎｖｅｒｇｅｎｃｅｏｆＩＴａｎｄ

Ｃｏｍｍｕｎｉｃａｔｉｏｎ（ＩＴＣＯＭ）．２００１．

【６９】ＦａｂｒｉｋａｎｔＡ，ＫｏｕｔｓｏｕｐｉａｓＥ。ＰａｐａｄｉｍｉｔｒｉｏｕＣＨ．Ｈｅｕｒｉｓｔｉｃａｌｌｙｏｐｔｉｍｉｚｅｄｔｒａｄｅ ｏｆｆｓ：Ａｎｅｗｐａｒａｄｉｇｍ

Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅｆｏｒｐｏｗｅｒｌａｗｓｉｎｔｈｅＩｎｔｃｒｎｃｔ．Ｉｎｔ’ｌＣｏｌｌｏｑｕｉｕｍｏｎＡｕｔｏｍａｔａ，ＬａｎｇｕａｇｅｓａｎｄＰｒｏｇｒａｍｍｉｎｇ（］ＣＡＬＰ）．２００２．

【７０】ＭｅｉＹＫ．Ｒｏｕｔｅｒ Ｌｅｖｅｌｔｏｐｏｌｏｇｙｍｏｄｅｌｉｎｇａｎｄａｓｓｅｓｓｍｅｎｔ【ＭＳ．Ｔｈｅｓｉｓ］．ＨｏｎｇＫｏｎｇ：ＣｉｔｙＵｎｉｖｅｒｓｉｔｙｏｆＨｏｎｇＫｏｎｇ，２００７．附中文参考文献：

【６】郭雷，许晓鸣．复杂网络．上海：上海科技教育出版杜，２００６

１１】张宇，张宏莉，方滨兴．Ｉｎｔｅｒｎｃｔ拓扑建模综述．软件学报，２００４，１５（８）：１２２０一】２２６．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｏｎ／１０００．９８２５／１５／１２２０．ｈｕｎ１２】曾伟，徐明伟，吴建平用络拓扑模型述评．计算机应用研究，２００５（７）．

６４】汪小帆。李翔，陈关荣．复杂网络理论及其应用．北京：清华大学出版社，２００６．

周苗（１９８３一），女，湖北武汉人，硕士生，主

要研究领域为网络协议，网络测量与管理．刘洪波（１９７８一），男，博士，助理研究员，主要研究领域为流量工程．网络测量．

杨家海（１９６６－－），男，博士，教授，ＣＣＦ高级

会员，主要研究领域为计算机网络，网络管

理与测量．吴建平（１９５３一），男，博士，教授，博士生导师，ＣＣＦ高级会员，主要研究领域为计算机

网络，网络协议与测试，网络体系结构．

本文来源：https://www.bwwdw.com/article/0e5q.html