Internet拓扑建模与演化综述✴

关晓惠，钱亚冠，周志敏

（1.浙江水利水电专科学校计算机与信息工程系，杭州310018；2.浙江科技学院理学院，杭州310023）

Internet拓扑建模与演化综述✴

关晓惠1，钱亚冠2，周志敏1

（1.浙江水利水电专科学校计算机与信息工程系，杭州310018；2.浙江科技学院理学院，杭州310023）

认识Internet拓扑结构及其演化趋势对下一代网络技术的研究至关重要。总结了Internet拓扑研究成果，综述了Internet静态拓扑模型和动态演化模型，着重考察了拓扑在节点度和结构两方面的演化特征，据此提出了今后的研究方向，即运用统计物理的非广延Tsallis熵理论来研究拓扑特征以及用分层的方式研究Internet拓扑结构，以期取得有效的成果。

下一代网络；Internet拓扑模型；幂律；演化；节点度；Tsallis熵

1 引言

Internet是复杂网络的一个典型例子，也可以说是一个庞大的人工生态系统。Internet发展时间尽管不长，但随着用户数的不断增多，其规模变得极其庞大；政治、经济和技术的变化也影响着拓扑结构的演变。Internet发展到现在，几乎没有人能清楚地描述它的真实拓扑结构。研究Internet拓扑演化模型有着重要的意义：深入理解现存路由协议的局限性，正确评估新的协议、体系的设计，预测将来互联网的发展需求；深入理解网络技术、拓扑结构和背后的经济因素之间的相互作用关系；路由协议的模拟与仿真、网络病毒的传播等均需要网络拓扑模型；发现拓扑演变背后的动因、本质规律，对于指导和预测将来Internet上部署各种新技术、新协议和新应用将具有重要指导意义。

对Internet拓扑的研究一般遵循这样的过程：从真实的Internet环境中提取拓扑数据，通过各种数学方法分析拓扑特征，根据分析得到的拓扑特征建立相应的拓扑模型和生成算法，通过数学分析的方法或实验的方法来验证所建立模型的正确性。

对Internet的拓扑研究，前人已经做了很多工作，从最初的随机图模型到结构模型，到Faloutsos提出的节点度的分布幂律特征［1］，再到Barabasi等提出的无标度网络［2］，以及后来Zhou S等提出的rich -club现象［3］、Mahadevan等关于节点度的相关性研究［4］，这些都是基于静态模型基础的。目前，动态演化模型的研究越来越受到关注［5-7］。

由于Internet是通过BGP协议将全球AS（自治系统）互联起来的网络，其拓扑结构主要由AS之间的互连关系表现出来，因此本文也主要阐述AS级的拓扑模型，即将每个AS看作图的节点，将AS之间的连接抽象成图中节点的邻接关系。

2 拓扑建模存在的困难

2.1 拓扑数据测量的困难

不管是建立还是验证分析Internet的拓扑模型，都需要可靠和真实的数据。目前获得Internet拓扑数据的方法主要有：

（1）通过测量技术获得，常用工具是traceroute，由于Internet的拓扑时刻处于动态变化，因此测量得到的数据具有滞后性；

（2）通过路由器上的BGP表、IRR、RIR获得，由于测量节点的数量有限，探测的目的节点数量也有限；AS之间存在的路由策略，BGP路由表不一定对外宣告；拓扑结构的高度动态变化等因素；尤其是很难发现冗余链接。

出于商业竞争、网络安全等因素的考虑，对于ISP来说，网络拓扑、路由策略、对等关系、容错能力和容量规划等信息对外界都是不公开的。AS级的营运商会经常变更他们之间的连接和流量交换策略；AS内部也因为经常发生路由设备的失败、维护和升级等事件，使得路由器级的拓扑结构同样也是不稳定的。因此，获取Internet真实的拓扑数据非常困难。

正是由于无法精确了解Internet的真实拓扑结构，也就为正确建立和验证拓扑模型带来了很大的困难。CAIDA（The Cooperative Association for Internet Data Analysis）认为目前需要解决的问题有［8］：

（1）所有的测量都受到实验条件和观测条件的限制，如观测点的地理分布范围、数量，被探测节点的数量等，使得数据不可避免的带有局限性；

（2）数据的不完整导致我们将一些合成的拓扑模型当作真实的Internet拓扑，已经证明像E-R随机图这样一类特殊的图不能代表真实的Internet拓扑；

（3）应该将测量的目标放到具体的地理区域，通过比较不同的地理区域和社会经济环境下的数据去区分Internet在全局核心和局部区域的不同特征。

在CAIDA发起的WIT（the Workshop on Internet Topology）上，所有与会的网络研究组织一致认为高质量的测量数据对于拓扑建模研究非常重要。目前可供给研究者使用的拓扑数据源有RouteViews、RIPE、Skitter、DIMES、iPlane等。

2.2 生成机理与演化规律

目前，我们只是对Internet的静态拓扑统计特性有所了解，如节点度分布的幂律特征、rich-club特征等，但Internet拓扑如何演变，以及模拟演变过程，即找到合适的拓扑生成算法，使之在演变过程中始终保持这些特征是一个困难的问题。我们发现的这些统计特征只是一个静态的、表层的、描述性的（de

scriptive），要解决这个难题必须找到形成这些统计特征背后的生长机理和各种促进因素，包括技术的、经济的和社会的，必须是解析性的（explanatory）。文献［9］指出，即使两个拓扑具有相同的统计度量，它们之间也可能具有不同的拓扑结构，如二维格子和三叉树，均具有相同的节点度分布。Internet拓扑的形成没有事先设计规划，各个ISP只在自己的AS域内进行优化规划，但Internet拓扑却很好地表现出“小世界”特征，使得路由非常高效，是什么原因使得局部最优同时也能全局最优，寻找这些背后的生成机理对于下一代网络的研究具有重要意义。

2.3 模型验证的困难

由于缺乏对真实Internet拓扑的了解，以及测量方法的局限和拓扑的动态变化，使得拓扑模型的验证也存在极大的困难。文献［10］指出了目前拓扑模型验证的困难在于以下几方面。

（1）拓扑生成器旨在产生一类拓扑图，它们反映Internet某些拓扑特征。区分这些拓扑图的类型依赖于哪些拓扑特征需要表达，以及这些特征如何表达。如何确定这些分类在真实性和典型性之间的界限是目前还无法解决的问题。

（2）目前对Internet的拓扑特征还没有被充分的研究。由于路由选择的复杂性，通过traceroute工具和BGP数据进行逆向工程方式分析，得出的拓扑特征存在不合理的地方。

（3）目前已经存在很多拓扑度量，但并不是每个都与Internet的拓扑相关，选择哪些拓扑度量去验证模型是一个目前还没解决的问题。

3 拓扑演化

拓扑模型可分为静态模型和动态模型［11］。静态模型是指从可获得的实际拓扑数据中生成能够反映实际网络拓扑特性的静态网络拓扑图，可以称为是一个拓扑快照（Topology Snapshot）；动态模型是指根据某种或某几种拓扑特性而研究网络的生长／演化过程，反映拓扑特性生成机理，因此也把动态模型称为演化模型。动态演化的不仅包括节点和边在数量上的增长，也包含数量的减少和节点之间连接的改变等。

对于动态模型，我们又将它们分为基与节点度的演化和基于结构的演化两类。

3.1 基于节点度的演化模型

3.1.1 BA模型

BA模型是Barabasi和Albert于1999年提出，大型网络能自组织成无标度（Scale-free）状态，主要是因为：增长（Growth）特性，即网络的规模是不断扩大的；优先连接（preferential-attachment）特性，即新的节点加入网络，总是倾向于与较高连接度的“大”节点连接。

BA模型就是基于上述两个特征构造的具有度分布呈幂律特征的无标度网络。构造算法如下：

（1）增长：从一个具有m0个节点的网络开始，每次加入一个新的节点，并连接到m个已存在的节点上，m≤m0；

（2）优先连接：新加入的节点以概率∏（ki）=与节点i连接，ki是节点i的度。

3.1.2 AB模型

AB模型是Albert和Barabasi于2000年提出的［12］，是对BA模型的扩展。AB模型的拓扑演化来自于新节点的加入、新边的加入和边的重新连接。具体算法是从m0个孤立的节点开始，每一步执行下面3个步骤中的一个：

（1）以概率p加入m（m≤m0）条新边，这些边连接已存在的节点：随机选择一个节点作为新边的起始点，再以概率

选择另一端的节点；此过程重复m次；

（2）以概率q重连m条边：随机取节点i和它的一条边lij，删除这条边并重新以概率∏ab（kj）选择一个节点j作新的连接；此过程重复m次；

（3）以概率1-p-q增加一个新节点，以概率∏ab（kj）与网络中已存在的m个节点连接。

上述概率p、q满足0≤p＜1，0≤q＜1-p。

3.1.3 GLP模型

GLP模型［13］称广义线性优先（Generalized Linear Preference）模型，由Tian Bu和Don Towsley于2002年提出。该模型不仅体现了度分布的幂律特征，还表达了两个“小世界”模型的聚簇特性和特征路径长度。经过观察，发现Internet节点比BA模型线性优先连接更倾向于连接到连接度高的节点上，因此提出了广义线性优先的方法。另外，文献［14］的研究表明，Internet在AS级很少发生重连（rewiring）操作。GLP模型去除了AB模型的重连操作，算法与AB模型相似，是从一个有m0个节点、m0-1条边连接的网络开始，首先以概率p增加m≤m0条新边，新边两端的每个节点以概率

在网络中已存在的节点中选择。β∈（-∞，1）是一个可调节参数，β值越小，表明对高连接度节点的偏好性越小。其次，以概率1-p增加一个新节点，新节点以概率∏（di）连接m个节点。Tian Bu从数学上证明了广义线性优先模型具有幂律特征的度分布。

3.1.4 GNG模型

GNG（Generalized Network Growth）模型［15］与GLP模型相似，由Caldarelli于2003年提出。基本思路是除了允许同时以概率p加入节点和以概率（1-p）加入连接，还采用了一种新的偏好方案：即要么加入一个新节点，以概率

与节点i连接；要么以概率

在节点i、j之间加入一条新边。GNG模型生成的网络具有无标度特征，在节点度的分布、介数的分布和聚簇系数等方面与Internet拓扑测量吻合，但动态增长特征与测量结果不符合。

3.1.5 IG模型

IG（Interactive Growth）模型［16］由S.Zhou于2003年提出。IG模型仍然采用BA模型的两个基本操作：新节点和新边的加入，连接概率也采用BA模型的线性偏好连接∏（ki），但BA、AB、GLP模型的新节点和新边的加入是相互独立的，IG模型提出新节点和新边联合增长模式。联合增长模型基于如下发现：新加入的节点连接到它的宿主节点（host），会给宿主节点增加流量，同时也带来宿主节点周围节点的流量模式变化，从而需要增加从宿主节点到它对等方（peer）的新连接，以便均衡流量和优化网络性能。实验表明，与AB、GLP模型相比，IG模型在节点度的分布和rich-club特性上更接近于真实的Internet拓扑。

具体算法是从一个小的随机网络开始，反复执行如下操作：

（1）以概率p∈（0，1），加入一个新节点，并以概率∏（ki）与网络中已有节点（称宿主节点）连接，如图1中新节点A-接入节点连接，再在宿主节点与其它网内节点之间添加两条内部连接，如图中的伙伴节点-接入节点-伴节点连接；

（2）以概率1-p，加入一个新节点，并以概率∏（ki）与网络中已有的两个宿主节点连接，再在其中一个宿主节点和网内其它节点之间添加一条内部连接。

3.1.6 PFP模型

PFP模型［17］是由S.Zhou于2008年在IG模型的基础上提出，称为正向反馈优先模型。Internet在AS级拓扑中的节点最大度kmax约等于节点总数的1／4，而IG和BA模型在节点最大度这个指标上远远超过了这个值。根据Internet历史数据，Pastor-

Satorras［18］和V′azquez［19］发现新节点与低连接度节点的连接倾向遵循线性优先概率∏（i）=ki／∑jkj，

而Chen［20］发现高连接度节点的“吸引力”远高于低连接度节点。PFP模型在偏好连接概率上进行了改进：由原来的线性优先改为非线性优先，

∏（i）=k1+δlgki／∑jk1+δlgkj，δ∈0，[] 1以提高连接度高的节点的“吸引力”。

算法与IG模型相似，是从一个小的随机网络开始，反复执行如下操作：

（1）以概率p∈（0，1），加入一个新节点，并以概率∏（i）与网络中已有节点（称宿主节点）连接，再在宿主节点与其它网内节点之间添加一条内部连接；

（2）以概率q∈（0，1-p），加入一个新节点，并以概率∏（i）与网络中已有节点（称宿主节点）连接，再在宿主节点与其它网内节点之间添加两条内部连接；

（3）以概率1-p-q，加入一个新节点，并以概率∏（i）与网络中已有的两个宿主节点连接，再在其中一个宿主节点和网内其它节点之间添加一条内部连接。当p=0.3、q=0.1时，PFP模型生成的拓扑接近真实的AS拓扑。

3.1.7 MPA模型

MPA（Multiclass Preferential Attachment）模型［21］是由加州大学的Srinivas Shakkottai等在2010年提出。MPA模型仍然基于连接偏好的原理，其所有参数都可从测量数据中获取，这一点为模型的客观性和验证上带来了优势。与以往模型的不同，该模型的一个显著改进是注意区分节点的类型，分为ISP和非ISP节点，因此称为多类偏好连接。但这种区分仍然显得过于粗略，与我们在结构演化中的讨论存在差距。最后，作者基于对实际测量数据的分析，进一步肯定连接偏好性是Internet演变的驱动力。

3.1.8 HOT模型

前面介绍的各种演化模型，其生长机理都是基于偏好连接，而且只有新节点和新连接的加入，没有节点和边的减少、连接的重新调整，这是不符合In

ternet的实际运行情况的。基于节点度的模型都可以很好地吻合幂律分布这个特性，但它们的缺陷是，除MPA模型外，都忽视了AS之间连接建立的内在因素，即商业关系。基于度的模型尽管也有演化能力，但这种演化方式很大程度上是带主观的假设，其目的就是符合幂律，因此缺乏充分的解析能力。

Chang等［22］将HOT（Highly Optimized Tolerance）模型应用到AS级的拓扑建上。纯粹的HOT模型是一种多目标的优化方式：当一个新节点加入网络，它基于两种目标来选择它要连接的节点（称父节点），分别是最后距离（Last Mile）的连接成本和父节点核心度（node centrality）成本。前者以新节点和父节点之间的欧氏距离来计算，后者以父节点到其它节点的平均距离来计算。文中指出，provider-customer关系在拓扑的节点度分布特征中占主导地位，peer -peer关系可以忽略。另外，多穴（Multi-Homing）连接对于节点度分布也没有影响。基于这个分析，文中的建模主要针对provider-customer连接的。Internet的发展不是随意的，而是在收益、资源成本和对风险的承受这三者之间的一种平衡，是一种高度优化设计的结果。

3.2 基于结构的演化模型

自从1999年Faloutsos提出Internet节点度的分布也服从幂律后，基于节点度的拓扑模型的研究迅速发展起来。Internet拓扑结构主要由自治系统（AS）之间的连接关系来体现，这里AS被看成是节点。因此拓扑结构的演化要反映AS数量的增减、AS之间的连接关系的增减（或重连），以及不同类型的AS分布情况。图2为Internet典型的传统分层拓扑结构。

3.2.1 AS之间的关系分类

AS之间的关系可分为c2p（customer-provider）、p2p（peer-peer）、s2s（sibling-sibling）3类。在c2p关系中，customer AS需要向provider AS缴纳它们之间发生的流量费用；在p2p关系中，两个AS自身或它们的customer之间的流量可以在它们之间免费传输，但不能传输它们的provider及peer之间的流量；属于s2s关系的AS往往属于同一个管理组织，它们之间或它们的provider、customer之间的流量都可以在这些AS之间免费传输。s2s这种关系是随着Internet规模的扩大，一个大公司可以同时拥有多个AS时出现，它们之间的关系一般并不体现商业利益关系。正是由于提供商之间这种复杂的利益关系，最终体现在Internet拓扑的高度动态变化中。

3.2.2 AS的类型

在基于节点度的拓扑模型中，并不区分节点的类型，而实际的AS节点并不是等同的。AS节点的类型也决定了它在整个拓扑结构中的位置，如核心层、边缘层等。根据业务类型可分为5类。

（1）企业客户（EC）：处于网络边缘的组织、大学和公司，它们代表了大多数的用户，不会再有自己的客户AS。

（2）小型传输业务提供商（STP）：通常是区域ISP（包括国家传输网、科研网），提供Internet的接入服务和传输业务，目的是建立本地区域的客户群。这些ISP之间通过优化的对等连接，可以减少客户的上行链路的传输成本。

（3）大型传输服务提供商（LTP）：具有极大的地域分布的国际级ISP。它们与其它ISP的对等连接仅为了可达性的需要，因此对等连接采取限制性策略。

（4）接入／托管服务提供商（AHP）：提供Internet接入（如DSL、拨号连接、租用线路等）、服务器托管业务的ISP。它们的客户主要是没有AS号的本地用户和企业。

（5）内容提供商（CP）：以提供付费内容为业务的供应商，它们的目的是为了降低传输成本，所以采用开放的对等连接策略。

k-核的分解［23］是一种提取大规模网络核心区域的新方法。Guo-Qing Zhang等利用k-核分解的方法研究了Internet的演化趋势，发现：AS级的Internet规模增长很快，遵循摩尔定律，即N（t）～100.0283t～e0.0652t；与整个Internet拓扑规模的指数级增大相比，k值越大的k-核，其规模随时间变化得更稳定；2003年后，与配置模型的预测相比，最大核数kmax非常稳定；与主流Internet模型的预测相比，最大节点连接度相对稳定；与随机模型相比，Internet仍然属于松散连接结构；与随机网络相比，不管Internet整体上还是它的核心都呈现异配性。

最近由Hamed Haddadi等提出用带权谱分布（Weighted Spectral Distribution，WSD）这个度量来分析Internet拓扑结构。研究表明：WSD可以很好地区分Internet的核心层和边缘层；核心层与边缘层的界限随着Internet进化，开始变得模糊；从图3中可以看出，随着核数的增加，高连接度的节点数2008年比2004增加，这意味着Internet中的对等连接增加，也反映出Internet的层次结构的模糊化。

文献［5］在对BGP数据的测量分析基础上，对Internet拓扑的演化规律进行了有益的探索。作者提出两个概念，通过测量发现的拓扑（ObservedTopology，OT）和真实的网络拓扑（Real Topology，RT）。发现了一个重要的演化规律：临时性的路由动态变化对OT的影响随着时间的推移呈指数递减，而RT中的拓扑变化包含了恒速出生和恒速消亡两种过程。同时又发现Internet规模的扩大主要由处于AS拓扑边缘的用户网络节点的出生和消亡引起，边缘网络和核心网络存在不同的增长模式。核心网络节点的增长速度缓慢，但相互间的连接变化却非常频繁，这种变化主要来自AS之间的peer-to-peer链路连接的重新调整。因此，研究AS的出生率、死亡率和增长率以及路由器和链路的失效模型，有利于建立真实的拓扑发生器，用于有效地模拟Internet的端到端行为。

随着网络新应用的不断涌现，文献［24，25］通过对BGP路由和流量的测量，发现Internet结构出现新的变化趋势。文献［24］发现40%～80%的BGP路径经过tier-2 ISP，从而认为tier-2 ISP在拓扑连接性上开始扮演重要角色，区别于以往传统上认为树型分层拓扑结构（见图4）。文献［25］对域间流量的分析也得出相似的结论，流量从核心层向外层转移，也反映出拓扑结构的非树形变化。

从传统意义上的树型分层拓扑结构向非树型结构的演变，主要原因来自新应用、新的互联网盈利模式的出现。继web应用之后，最近社会网络和视频内容逐渐在Internet流量中居主导地位。经济因素的变化，包括IP地址租用费用的连续下降，以广告为支撑的信息量的增长，极大地改变了许多提供商的互连策略。新互联网经济的出现，大的内容提供商开始构建自己的全球骨干网，并直接与自己的客户网络连接，转移了超过5%的域间流量。由此可见，Internet的拓扑结构的演变，新应用和经济因素起到非常重要的作用。

4 拓扑模型的验证

在本文的第2节中提到了验证模型的正确性是其中的一大困难。通过比较不同模型生成的拓扑的统计特性，不一定能反映出模型的正确性。已有研究表明，相同的统计度量下，也可能存在不同的拓扑结构。同时，测量取得拓扑数据存在很多虚假信息，如节点和边的消失与出现不一定与实际拓扑结构变化相符合。Ricardo Oliveira提出了一种与真实Inter

net比较节点／边的生灭过程来验证模型的思路。理论模型的节点／边的加入是由连接偏好来决定的，那么真实Internet是怎么样呢？Ricardo Oliveira提出拓扑活性（liveness）的概念来说明该问题。我们将真实的Internet拓扑用Greal来表示，通过测量等手段提取出来的拓扑称为Gobsv。Gobsv对于我们是可见的，而Greal则是不可见的。如图5所示，箭头表示BGP路径或trace route探测方向。

由图5发现，Greal和Gobsv是不一致的，即使在同一个Gobsv中，t0到t1和t2到t3也是不一致的。其中t0到t1的不一致是由动态路由引起的，而t2到t3的不一致是由Greal拓扑结构发生变化引起的。同时又可观察到B-C这条边在Gobsv中，从t0到t3的过程中经历了消失-出现-消失的过程，而实际上它一直存在。因此我们希望能区分出这些边或接点在Gobsv的出现／消失是由于动态路由还是真实的拓扑改变引起的，这个问题就是拓扑活性问题。为了区分这两种不同，将Greal中的拓扑元素（节点／边）的加入／移除称为出生（birth）／死亡（death），而将Gobsv中的元素加入／移除称为出现（appearance）／消失（disappearance）。研究发现，Greal拓扑元素的出生／死亡和Gobsv中的元素出现／消失并不对应。因此我们要去发现真正由于元素“死亡”而“消失”、“出生”而“出现”的情况，筛除因动态路由等原因造成的同一个元素在不同时刻反复消失又出现的干扰情况（实际在Greal中一直存在）。通过观察Gobsv发现Greal中的节点／边的“死亡”和“出生”规律来验证理论上的拓扑模型的生长过程，才能取得合理的结论。

Srinivas Shakkottai等提出一个可以验证的模型应该符合如下的条件：模型尽可能简单，参数尽可能少；所有的参数必须是可测量的，排除主观假设；易用分析手段来处理。因此，作为拓扑建模者，在建模过程中始终能考虑这些最优阶段的验证要求，无疑对模型的有效性、真实性、合理性是有积极意义的。

5 存在的问题和发展趋势

Internet拓扑建模从最初的随机模型到结构模型，随着复杂网络的无标度性质的发现，基于度的模型应运而生。研究表明，基于度的模型不但很好地反映出了局部特征，同时也符合Internet的结构特征，但反之不成立。尽管有研究表明，网络的核心层与边缘层在结构上有模糊的倾向，但仍然不能忽视Internet整体上仍然是一个等级网络的事实。因此，一个好的拓扑生成器，不仅要考虑局部特征，也要兼顾整体的结构特征。

Internet拓扑在结构上的演变对我们以往的一些静态统计度量，如聚簇系数、平均距离等，也提出了挑战：这些统计度量是否还存在？在数值上又有哪些变化？这些都要求我们不断地去更新拓扑测量方法，获取更新的认识。对Internet拓扑研究的最终目的是能够预测未来，但这恰恰也是最难的。Internet拓扑对于网络领域的其它研究起着关键性的基础作用，可应用于网络模拟、研究网络病毒传播机理、网络协议性能等。

将统计物理的熵概念引入对Internet拓扑结构的统计特性研究，将是我们下阶段需要研究的方向。尤其是非广延量Tsallis熵［26］对于研究Internet这样具有明显异配性、幂律特征的系统，是一个非常合适的统计量。

最后，我们发现目前大量的工作集中在对物理拓扑结构的研究，这样的工作吸引了大量的数学、物理等学科的学者参与。从计算机网络学科看，Internet是由多层协议构成的异质网络，仅对物理连接性的研究是不够的，在不同的协议层需要的拓扑信息其实是不一致的。因此我们提出分层拓扑建模的思路，分别在物理层（物理介质连接性）、网络层（路由路径构成）、应用层（P2P、覆盖网、虚拟网路由路径构成）测量、分析和研究构建各种逻辑拓扑的方法，这样的研究成果会对网络研究界更具实用意义。我们希望这些研究成果可应用于下阶段关于大规模虚拟网模拟的研究。

6 结论

本文详细介绍了Internet的静态拓扑模型和动态拓扑模型，并对拓扑模型在节点度和结构方面的演化进行了详细的讨论，最后分析了存在的问题并提出了以后的发展方向，希望为Internet拓扑建模提供一定的参考。

［1］FaloutsosM，Faloutsos P，Faloutsos C.On power-law relationships of the internet topology［C］／／Proceedings of the Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication.New York：ACM，1999：251-262.

［2］Barab′asi A，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509-512.

［3］Zhou S，Mondragon R J.The rich-club phenomenon in the Internet topology［J］.IEEECommunication Letters，2004，8（3）：180-182.

［4］Mahadevan P，Krioukov D，Fall K，etal.Systematic topology analysis and generation using degree correlations［C］／／Proceedings of the Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication. New York：ACM，2006：135-146.

［5］Oliveira R，Zhang B，Zhang L.Observing the evolution of Internet AS topology［C］／／Proceedings of the Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication.New York：ACM，2007：313-324.

［6］Shakkottai S，Fomenkov M，Koga R，et al.Evolution of the Internet AS-Level Ecosystem［J］.European Physical JournalB，2010，74（2）：271-278.

［7］Zhang GQ，Yang Q F，Cheng SQ，et al.Evolution of the Internet and its cores［J］.New Journal of Physics，2008，10（12）：123027.

［8］Krioukov D，Chung F，Claffy K，et al.2007 The workshop on Internet topology（WIT）report［J］.ACM SIGCOMM Computer Communication Review，2007，37（1）：69-73.

［9］Li L，Alderson D，WillingerW，etal.A first-principlesapproach to understanding the Internet′s router-level topology［J］.ACM SIGCOMM Computer Communication Review，2004，34（4）：3-14.

［10］Haddadi H，Uhlig S，Moore A，et al.Modeling internet topology dynamics［J］.Computer Communication Review，2008，38（2）：65-68.

［11］MahadeVan P，Krioukov D，Fall K.Systematic topology analysisand generation using degree correlations［J］.SIGCOMM，2006，36（4）：135-146.

［12］Réka Albert，Albert-LászlóBarabási.Topology of Evolving Networks：Local Events and Universality［J］.Physical Review Letters，2000，85（24）：5234-5237.

［13］Tian Bu，Don Towsley.On Distinguishing between Internet Power Law Topology Generators［C］／／Proceedings of the Twenty First Annual Joint Conference of the IEEEComputer and Communications Societies.New York：IEEE，2002：638-647.

［14］Chen Q，Chang H，Govindan R，etal.The Origin of Power Laws in Internet Topologies Revisited［C］／／Proceedings of the Twenty First Annual Joint Conference of the IEEE Computer and Communications Societies.New York：IEEE，2002：608-617.

［15］BianconiG，CaldarelliG，Capocci A.Number of h-cycles in the Internet at the autonomous system level［EB／OL］. 2003-10-15［2003-10-16］.http：arxiv.org／condmat／0310339.

［16］Zhou S，Mondragon R J.Towards modeling the Internet topology：the interactive growth model［J］.Teletraffic Science and Engineering，2003（5）：121-130.

［17］Zhou S，Mondragon R J.Accurately modeling the Internet topology［J］.Physical Review E，2004，70（6）：106-108.

［18］Pastor-Satorras R，V′azquez A，Vespignani A.Dynamical and Correlation Properties of the Internet［J］.Physical Review Letters，2001，87（25）：1-4.

［19］V′azquez A，Pastor-Satorras R，Vespignani A.Largescale topological and dynamical properties of Internet［J］. Physical Review E，2001，65（6）：1-13.

［20］Chen Q，Chang H，Govindan R，etal.The origin of power laws in internet topologies revisited［C］／／Proceedings of the Twenty-First Annual JointConference of the IEEEComputer and Communications.［S.l.］：IEEE，2002：608-617.

［21］Shakkottai S，Fomenkov M，Koga R，etal.Evolution of the Internet AS-Level Ecosystem［J］.European Physical Journal B，2010，74（2）：271-278.

［22］Chang H，Jamin S，WillingerW.Internet connectivity at the AS-level：An optimization-driven modeling approach［C］／／Proceedings of the ACM SIGCOMM 2003Workshops. Karlsruhe，Germany：ACM，2003：33-46.

［23］Pittel B，Spencer J，Wormald N.Sudden emergence of a giant k-core in a random graph［J］.Journal of Combinatorial Theory B，1996，67（1）：111-151.

［24］Hiroshi Fujinoki，Andrew Hauck.Analysis on the Trend of Recent Changes in the Internet Structure：Departing from the Long-Assumed Tree-Structure Model［C］／／Proceedings of the 8th International Conference on Computing，Communication and Control Technology.Orland，Florida，USA：［s.n.］，2010.

［25］Craig Labovitz，Scott Iekel-Johnson，Danny McPherson，et al.Internet Inter-Domain Traffic［C］／／Proceedings of the ACM SIGCOMM 2010 Conference on SIGCOMM.New York：ACM，2010：75-86.

［26］Tsallis C.Introduction to nonextensive statisticalmechanics—approaching a complex world［M］.New York：Springer，2009.

GUANXiao-huiwas born in Luohe，Henan Province，in 1977. She received the M.S.degree from Zhejiang University in 2005.She is now a lecturer.Her research direction is networkmultimedia.

Email：guanxh＠zjwchc.com

钱亚冠（1976—），男，浙江嵊州人，2005年于浙江大学计算机学院获硕士学位，现为讲师，主要从事计算机网络建模方面的研究；

QIAN Ya-guan was born in Shengzhou，Zhejiang Province，in 1976.He received the M.S.degree from Zhejiang University in 2005.He is now a lecturer.His research concerns computer networkmodeling.

周志敏（1966—），女，河北保定人，硕士，副教授，主要从事计算机硬件的研究和开发。

ZHOU Zhi-min was born in Baoding，Hebei Province，in 1966.She is now an associate professor with the M.S.degree.Her research concerns R＆D of computer hardware.

A Survey of Internet Topology Modeling and Evolution

GUAN Xiao-hui1，QIAN Ya-guan2，ZHOU Zhi-min1
（1.Department of Computer and Information Enginering，ZhejiangWater Conservancy and Hydropower College，Hangzhou 310018，China；2.Science College，Zhejiang University of Science and Technology，Hangzhou 310023，China）

It iswell known that clearly learning the realistic Internet topology and its evolution trend will play an important role in the research of next generation network and the operatingmanagement.This papermakes a comprehensive survey of the topology evolution based on node degree and structure，and reviews static topology models and dynamic topology models.Finally，it proposes the future research directions，that are using Tsallis entropy to explore the topology statistics and using layered fashion to study the topology structure.

next generation network；Internet topologymodel；power-law；evolution；node degree；Tsallis entropy

Scientific Research Foundation of Zhejiang Educational Committee（Y201017457）

TP393.02

A

10.3969／j.issn.1001-893x.2011.11.025

关晓惠（1977—），女，河南漯河人，2005年于浙江大学计算机学院获硕士学位，现为讲师，主要研究方向为网络多媒体；

1001-893X（2011）11-0121-08

2011-07-11；

2011-08-15

浙江省教育厅科研项目资助（Y201017457）