多约束条件下互联网骨干网路由器级拓扑生成方法*

吴元立，司光亚，罗　批

(1.国防大学 信息作战与指挥训练教研部, 北京　100091； 2.国防大学 研究生院, 北京　100091；3.中国人民解放军第309医院， 北京　100091)



多约束条件下互联网骨干网路由器级拓扑生成方法*

吴元立1,2,3，司光亚1，罗批1

(1.国防大学 信息作战与指挥训练教研部, 北京100091； 2.国防大学 研究生院, 北京100091；3.中国人民解放军第309医院， 北京100091)

摘要：互联网骨干网是网络流量的中枢传输系统，其路由器级拓扑结构对于网络抗毁性分析具有重要意义。由于难以获取互联网骨干网路由器级的真实拓扑，通过分析骨干网的形成因素，将地理位置、节点间联系强度、基础设施费用、鲁棒性等因素结合起来，提出一种多约束条件下的互联网骨干网路由器级拓扑生成方法。该方法既可以构造难以公开获取网络测量数据的骨干网，也可以用来生成某一骨干网的多种替身拓扑集。通过现实中的互联网骨干网作为实例，验证了方法的有效性。

关键词：互联网；拓扑生成；网络抗毁性

互联网实际上是多个网络互联而形成的覆盖全球的网络，大型网络运营商拥有并维护着由路由器和光纤组成的骨干网，这些骨干网是互联网流量的中枢传输系统，且国家关键基础设施越来越依赖这些骨干网实现业务协同，骨干网上的微小扰动会影响整个互联网甚至其他关键基础设施的运行[1-2]。由于无法直接在互联网骨干网上展开实验，人们通过构建路由器级拓扑，因此，依托建模仿真手段从网络安全视角研究网络抗毁性。骨干网路由器级拓扑是对骨干网的抽象表达，节点代表路由器，边代表路由器之间的一跳连接关系，路由器级拓扑既可以表示网络连接关系，也可以直接映射到地理信息系统，并可描述与其他国家关键基础设施的关联。由于种种原因，难以获取互联网骨干网路由器级的真实拓扑，因此，如何生成符合现实网络特性的互联网骨干网路由器级拓扑逐渐成为网络科学领域的研究热点，美军X计划[3]也把生成不同规模的符合真实网络特性的路由器级网络拓扑集作为重点研究方向。

一个自治系统通常由多个路由器通过网络链路相连组成，一些大型的自治系统(如中国电信)所包含的路由器级拓扑可以覆盖整个国家。不同于自治系统级的逻辑拓扑，路由器级拓扑受到地理位置、网络运营商经费限制以及用户需求等因素的约束，表现出一种多约束条件下追求目标优化的拓扑结构特性。但是，大型网络运营商不愿意公布其拓扑结构。为了获取研究互联网所需的路由器级拓扑结构，存在静态生成和动态生成两类方法，静态生成是指从拓扑测量得到的数据集(如互联网应用数据分析中心(CenterforAppliedInternetDataAnalysis,CAIDA)[4]和DIMES[5]项目)中去提取实际网络拓扑结构的方法，动态生成是指根据研究获得的拓扑特性，研究如何生成能够刻画互联网拓扑结构的方法。文献[6-8]给出了多种静态生成方法，例如，文献[6]在拓扑数据源上使用RocketFuel和SCAN项目的实际测量数据，选取了美国主要的网络运营商，构建其骨干网并确定骨干网间的互联节点，试图尽可能准确、细粒度地构建美国互联网路由器级骨干网络模型。但是由于互联网规模大、异构、非集中管理等特性[9]以及网络测量的局限性，这种方法不仅非常费时费力，且结果并不一定准确、全面。

因此，研究人员更多地依赖动态生成方法来构建路由器级拓扑结构，文献[10]提出了基于启发式的优化算法，在生成过程中主要考虑了路由器性能和网络绩效两个度量指标，生成的拓扑结构具有优化设计特点，但该模型缺乏对节点地理信息的考虑。文献[11]认为骨干网络拓扑构建的驱动因素由设施费用、预期性能、地理限制因素、节点/链路失效恢复四方面构成，提出了多项式时间的HINT拓扑生成算法，最后通过与AT&T等三个骨干网对比，该方法具有90%以上的相似性，但该方法在构造拓扑时所需数据源较多，在流量约束方面忽视了流量的非对称性。TopGen[12]把路由器的技术限制作为约束条件，提出了一种通用的路由器级拓扑生成方法，该方法依据带宽和路由器最大连接限制，将路由器节点分为核心节点、边界节点、网关节点和接入节点，并提出了这些路由器的约束条件和拓扑生成算法。KU-LocGen[13]在节点地理位置限制的基础上，提出了包含多种生成模型的路由器级骨干网络拓扑生成算法，在拓扑生成集合上进行了费用图谱分析，但缺乏对节点间强度和网络鲁棒性因素的考虑。以往的研究多是面向自治系统级的逻辑拓扑研究，或是在路由器级拓扑研究中忽视了地理限制、节点间联系强度、基础设施费用、鲁棒性等影响骨干网建设的重要因素。

综合文献[11]和文献[13]的思想，在Waxman模型的基础上考虑地理限制、基础设施费用、鲁棒性等因素，并引入节点间联系强度作为拓扑生成参数，本文研究提出一种多约束条件下的互联网骨干网路由器级拓扑生成方法。

1拓扑生成方法

1.1Waxman模型

不同于数万个节点的自治系统级拓扑所对应的BA[14]生成模型，拥有数十个节点的大型互联网骨干网路由器级拓扑往往与Waxman模型更为匹配[15-16]。Waxman模型是随机图拓扑生成的代表，类似于Erdös-Rényi模型，模型将节点按泊松分布放置在平面上，边的添加依赖于节点间欧几里得距离来决定的概率。对于节点A和节点B而言，其连边概率为：

(1)

其中：d是节点对之间的欧几里得距离；L是所有节点对之间的最大欧几里得距离；α和β的取值范围是(0,1)，α代表节点间连边的概率，β代表长边相对于短边的概率。

1.2骨干网形成因素分析

1)地理位置。BA[14]等传统算法是针对逻辑拓扑生成的，没有考虑网络拓扑节点的地理位置限制。对大型网络而言，核心路由器或接入点(PointofPresence,PoP)节点的位置受到多种经济和政策因素制约，通常部署在多个网络光纤交汇的人口密集处，而不是如Waxman模型中节点的随机分布。本算法面向大尺度的骨干网，用经纬度坐标表示节点的位置。一方面，在生成已有骨干网的不同特性的替身拓扑时，可直接使用其公开的路由器节点的地理位置。另一方面，对于难以获取拓扑地理位置的骨干网可通过人口密度数据集来估算骨干网路由器节点可能的地理位置[17]，而地理位置的粒度取决于骨干网的规模和人口密度数据集的精度。例如，国际地球科学信息网络中心(CenterforInternationalEarthScienceInformationNetwork,CIESIN)[18]提供了多种分辨率的全球人口密度数据集，在粒度选择上可根据骨干网规模灵活选择相应的分辨度，以国家级的骨干网络为例，可基于1km2分辨率的人口密度数据集并指定相应的路由器节点数量，采用k-means聚簇算法推算路由器节点的经纬度坐标。k-means算法是基于相似度的聚簇方法，目标是通过迭代计算，使得所有数据点与聚簇中心距离的距离总和最小化，此方法常被用来根据人口密度数据集和给定的聚簇中心数量(路由器节点数量)推测可能的聚簇中心点位置[16,19]，这些聚簇中心代表着人口密度的极值点，可用作估算路由器节点的地理位置。

2)节点间联系强度。路由器节点间的光缆布线与节点所在地区的互联网发展水平息息相关。一般来说，节点所在地区的互联网发展水平越好，地区之间互联网信息交换的强度就越大，从保证重要节点间的服务质量并节省整体建设费用的角度来说，重要节点间铺设光缆的可能性就越大。例如中国电信骨干网络在北京、上海、广州三个重要城市之间就采用了全互联的拓扑连接结构。本文基于Gravity模型计算网络联系强度，Gravity模型源于牛顿的万有引力定律，即两个物体之间的作用力与两个物体的质量乘积成正比，与两个物体的距离的平方成反比。这个物理学的定律通常被社会学家延伸到社会科学等领域用来对地区间人员、货物和信息的流动进行建模和分析。通常，根据公开的人口的数据和地理位置信息，用Gravity模型可以计算出两个地区之间联系的紧密程度，例如城市间的交通运输联系强度。Gravity模型也同样适用于地区之间互联网流量强度的预测[20-21]，但不同于实体货物的传输，由于网络的高速传输速度，地区之间的距离对互联网流量交换强度几乎没有影响，而地区的互联网发展水平成为地区间网络流量联系强度的主体因素[22]，因此选择互联网上网人数作为节点互联网发展水平的衡量标准。

3)建设费用。费用对路由器级拓扑影响很大，大型网络运营商希望通过有限的资金来满足网络通信服务的需要。所以，即使不把费用作为拓扑生成过程的一部分加以考虑，也要在拓扑生成集合的基础上进行费用分析，以筛选出满足特定费用约束的模型参数集，在这个参数集上可以进一步分析哪些模型参数会使网络效率更高，鲁棒性更好。一般来说，一对节点之间的光纤布线由两部分。分为一次性的基础设施投入(购买光缆、光交换设备、挖掘以及光缆的安装费用)和日常维护费用。挖掘费用与节点间的距离成正比，光缆的费用取决于其长度和质量。由于大型骨干网通常跨越辽阔疆域，普遍认为挖掘和铺设费用是光缆费用的主要组成部分[10,23]，即距离成为衡量光缆费用的主要因素。因此，骨干网络的总体费用C表达如下：

(2)

其中：di,j是节点i，j之间的距离，单位为km；vc为每千米所需费用。

4)鲁棒性。鲁棒性对承载着巨大流量的骨干网而言至关重要，互联网前身ARPANET的目的就是为了能够在部分节点或连边失效时在剩余节点之间仍然保持通信可达性。骨干网在设计时需要充分考虑网络鲁棒性，某个拓扑结构若在任意一个网络要素发生失效时仍然能够将受影响的网络流量重新转发，那么就可以认为这个网络拓扑结构具备一定的鲁棒性。在图论中，使得一对节点分属于不同的连通片所需去除的一组节点成为这对节点的点割集(vertexcutset)。包含节点数最少的割集称为极小割集(minimumcutset)。普遍认为，具有较好鲁棒性的网络拓扑应是一个二连通图(two-connectedgraph)[24]，即对图G(V，E)中的任意两个节点vi,vj，设k(vi,vj)是vi,vj的极小割集所包含的节点数量，那么应满足：

k(vi,vj)≥2,∀vi,vj∈V

(3)

算法1给出了二连接图的判断方法，即鲁棒性约束算法。

算法1　鲁棒性约束

1.3拓扑生成方法

节点间的连边概率由式(4)决定：

(4)

(5)

两个节点间的连接概率由其地理距离和互联网人数共同决定。对某一特定算法参数集(包括α，β和强度系数ω)而言，算法运行一次会得到一个拓扑，由于概率的作用，算法多次计算后会到一个拓扑集合。

2拓扑生成方法评估

2.1数据集

选择中国电信和美国高级网络服务(AdvancedNetworkService,ANS)两大互联网骨干网作为算法评估的样本(如图1所示)，其拓扑数据集来自TopologyZoo项目[25]，该项目认为网络测量方法无法获得准确、全面的网络拓扑和拓扑元信息，而网络服务提供商公布的网络结构往往较准确，且包含了节点和链路等多种元信息，通过图形处理手段将全球近百个网络服务提供商发布的骨干网络拓扑图转换成统一的拓扑数据表达。拓扑生成所使用的地理位置直接使用该拓扑数据中节点的经纬度坐标，例如位于北京的核心路由器节点的坐标为(东经116.397，北纬39.908)，基于经纬度坐标就可以计算得到城市间的距离。

(a) 中国电信(a) China Telecom

(b) 美国ANS(b) America ANS图1　骨干网拓扑结构Fig.1　Backbone network topology

对算法中节点联系强度计算所需的互联网人数数据，中国电信拓扑中各节点所在城市数据来自文献[26]，美国ANS拓扑中各节点所在城市数据来自文献[27]。以中国为例，文献[26]中北京IPv4地址数的比例为25.65%，上海为4.48%，然后通过式(5)即可算出北京与上海间的流量联系强度系数。

2.2拓扑评估指标

由于每个骨干网拓扑在设计上各有其特点，评估生成的拓扑结构是否与现实拓扑相匹配通常通过一些特定的、可量化的拓扑指标来计算[28]。选取以下三种拓扑参数作为评估指标：

1)节点度分布：节点度分布指网络中随机选择的节点度为k的概率[29]，是比较网络拓扑结构的重要指标。

2)最短路径跳数：指任意两个节点之间的最短路径跳数[30]，代表了数据包通过路由器转发的次数，可用来衡量网络效率。

3)链路长度：链路长度指两个路由器节点之间的链路(通常是光缆)的物理长度，决定着节点间的链路延迟和总体建设费用。

4)网络效率(全局连通效率)：网络效率是网络可靠性的主要指标。定义节点i到j的连通效率为：

(6)

其中，di,j是节点i到j的最短路径跳数，网络效率为：

(7)

其中N为网络节点总数。

2.3评估方法

通过Visualstudio2012对1.3节的算法进行了代码实现，在节点数据集上采用2.1节的数据。1.3节算法包含了α和β两个可变参数，针对某一个骨干网，在算法评估过程中循环遍历α和β的取值范围(0,1)，每次参数的增量设为0.01。为了消除随机数带来的偏差，在每个参数集α和β的计算上重复计算100次，计算并记录节点度、最短路径跳数和链路长度这三个拓扑指标的均值和方差，将其作为与真实拓扑结构比较的标准。因此，为了覆盖拓扑生成的整个参数空间，对每个骨干网络拓扑节点集合需进行100万次(100×100×100=1 000 000)指标计算。将生成的拓扑指标与现实网络拓扑指标匹配较好的参数集称为“匹配参数集”。表1给出了中国电信和ANS真实拓扑结构与“匹配参数集”拓扑结构的指标对比情况，μ为均值，σ为方差。其中，中国电信的“匹配参数集”为α= 0.31，β=0.19。可以看出，匹配参数集的节点度、最短路径以及链路长度均与真实拓扑较为匹配，可作为构建真实拓扑不同替身拓扑的参数指标。

表1　拓扑指标对比(μ/σ)

注：①匹配参数集为α= 0.31，β=0.19；

②匹配参数集为α= 0.14，β=0.66；

③匹配参数集为α= 0.38，β=0.15；

④匹配参数集为α= 0.27，β=0.49。

表2距离和流量联系强度影响对比

Tab.2Comparisonofdistanceandtrafficexchangestrength

节点对距离/km距离因子E流量强度因子γ连边概率P北京-广州18860.2280.1900.114北京-武汉10470.4390.0480.157北京-哈尔滨10570.4360.4360.146

可以看出，两点间的连接概率由距离和互联网人数共同决定，距离较近的城市间E值较大，使得E北京-武汉≈E北京-哈尔滨>E北京-广州；互联网人数更多的城市间连接强度系数更大，使得γ北京-广州>γ北京-武汉>γ北京-哈尔滨。在当前拓扑参数(α= 0.31，β=0.19，强度系数ω=0.69)的情况下、节点间的连接概率中，距离起主要作用，互联网人数起次要作用。相对武汉而言，尽管广州的互联网人数更多，但是由于北京到广州距离较长，综合使得P北京-广州

通过相关研究比较，选择了KU-Locgen[13]拓扑生成器的Waxman模型计算其“匹配参数集”，可以看出本文的拓扑生成算法在平均度指标一样的情况下，在链路长度这个指标上与现实拓扑更为匹配，这是由于考虑了节点间的联系强度对生成边的影响，而不是简单地考虑长短边的比例因素。同时，在网络效率指标的比较上，本文算法和KU-Locgen[13]算法较为接近，但均略低于真实网络拓扑的网络效率，这可能因为真实网络拓扑往往是经过设计部门的反复优化后确定的一次具有较高网络效率的拓扑，而本文算法由于拓扑生成中随机性因素的作用，取的是在某一匹配参数集下的网络效率均值，故该值略低于真实网络拓扑的网络效率。

以中国电信骨干网为例，如图2所示，在可用参数集α= 0.31，β=0.19的基础上，由于随机数的因素，算法每次都会生成不同的拓扑结构。通过对生成的拓扑集施加不同的约束可筛选得到不同性质的网络拓扑特例，例如，通过施加算法1中的鲁棒性约束算法，可得到具备较好鲁棒性的拓扑结构(如图2(b)所示)，该拓扑结构在单个节点失效的情况下可保证其他任意节点对之间的连通性；通过加入链路总长度约束，可得到具有较高延迟的拓扑结构(如图2(c)所示)。

2.4费用约束分析

费用是拓扑生成后的定量过滤。根据式(2)的费用计算方法，设vc为10万元，可计算得到中国电信和美国ANS骨干网的实际建设费用分别为60亿和28.2亿元。基于MATLAB R2009b对拓扑生成算法的参数空间进行总体建设费用分析，可得到如图3所示的费用在参数空间上的分布图。

(a) 实际拓扑结构(a) Actual Topology

(b) 鲁棒性拓扑(生成)(k(vi,vj)≥2)(b) Robustness topology(k(vi,vj)≥2)

(c) 高延迟拓扑(生成)(c) High latency topology图2　中国电信拓扑结构比较(α= 0.31，β=0.19)Fig.2　Alternative topology for China Telecom(α= 0.31，β=0.19)

(a) 中国电信(a) China Telecom

(b) 美国ANS(b) America ANS图3　生成算法参数集费用分布图Fig.3　Cost distribution for topology parameters

通常，骨干网络运营商的建设费用是有限的，假设中国电信和美国ANS在现有节点集基础上的建设费用约束分别为60亿～70亿元和25亿～30亿元，那么满足上述费用约束的参数集分布如图4所示。通过对参数集进行费用约束分析，可以筛选出符合特定费用约束的参数集，进而构造相应的拓扑结构。

(a) 中国电信(60亿～70亿元)(a) China Telecom (6 billions to 7 billions)

(b) 美国ANS(25亿～30亿元)(b) America ANS(2.5 billions to 3 billions)图4　满足费用约束的参数分布Fig.4　Parameters distribution under cost constraint

3结论

地理位置、节点间联系强度、基础设施费用和鲁棒性是互联网骨干网形成的关键因素，所提多约束条件下的骨干网路由器级拓扑生成方法，对需要依托路由器级网络拓扑进行研究的网络抗毁性分析研究等领域有重要意义。

参考文献(References)[1]Buldyrev S V, Roni P， Gerald P, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature, 2010, 464(7291): 1025-1028.

[2]International Cable Protection Committee (ICPC). Submarine cable network security[EB/OL]. (2009-01-01)[2015-06-31]. http://www.iscpc.org/.

[3]李健, 温柏华. 美军网络力量[M]. 沈阳: 辽宁大学出版社, 2013.

LI Jian, WEN Baihua. US network power[M]. Shenyang: Liaoning University Press, 2013. (in Chinese)

[4]Huffaker B, Plummer D, Moore D, et al. Topology discovery by active probing[C]// Proceedings of Symposium on Applications and the Internet (SAINT) Workshops, 2002: 90-96.[5]Shir E, Shavitt Y. DIMES: let the Internet measure itself[J]. Computer Communication Review, 2005, 35(5): 71-74.[6]Liljenstam M, Liu J, Nicol D M. Development of an Internet backbone topology for large-scale network simulations[C]// WSC′03 Proceedings of the 35th Conference on Winter Simulation: Driving Innovation, 2003: 694-702.

[7]Zhou S, Mondragón R J. Accurately modeling the Internet topology[J]. Physical Review E, 2008, 70(6): 066108.

[8]Tian Y, Dey R, Liu Y, et al. China's Internet: topology mapping and geolocating[C]// Proceedings of IEEE INFOCOM, 2012: 2531-2535.

[9]Sally F, Vern P. Difficulties in simulating the Internet[J]. IEEE/ACM Transactions on Networking, 2001, 9(4): 392-403.[10]Li L. A first-principles approach to understanding the Internet’s router-level topology[J]. Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 2004: 3-14.

[11]Ma X Z, Kim S, Harfoush K. Towards realistic physical topology models for Internet backbone networks[C]//Proceedings of 6th International Symposium on High Capacity Optical Networks and Enabling Technologies, 2009: 36-42.[12]Scholtes I， Botev J, Esch M, et al. TopGen-internet router-level topology generation based on technology constraints[C]// Proceedings of the 1st International Conference on Simulation Tools and Techniques for Communications, 2008.

[13]Jabbar A, Shi Q, Hameed M, et al. ResiliNets topology modelling[EB/OL]. (2012-05-03)[2015-06-31]. https://wiki.ittc.ku.edu/resilinets/Topology_Modelling.

[14]Albert R, Barabási A. Statistical mechanics of complex networks [J]. Reviews of Modern Physics, 2002, 74: 47-49.[15]Waxman B M. Routing of multipoint connections[J]. IEEE Journal on Selected Areas in Communications, 1988, 6(9): 1617-1622.

[16]Sterbenz J P G, Etinkaya E K, Hameed M A, et al. Evaluation of network resilience, survivability, and disruption tolerance: analysis, topology generation, simulation, and experimentation (invited paper)[J]. Telecommunication Systems, 2011, 52(2): 705-736.

[17]Lakhina A, Byers J W, Crovella M, et al. On the geographic location of Internet resources[J]. IEEE Journal on Selected Areas in Communications, 2003, 21(6): 934-948.

[18]Socioeconomic Data and Applications Center. Gridded population of the world (GPW), V3[EB/OL][2015-06-31].http://sedac.ciesin.columbia.edu/gpw, 2005.

[19]Mahmood A H, Jabbar A, Cetinkaya E K, et al. Deriving network topologies from real world constraints[C]// Proceedings of IEEE in GLOBECOM Workshops (GC Wkshps), 2010: 400-404.

[20]Crain J K. Assessing resilience in the global undersea cable infrastructure[R].DTIC Document, 2012.

[21]Omer M, Nilchiani R, Mostashari A. Measuring the resilience of the global Internet infrastructure system[C]//Proceedings of 3rd Annual IEEE International Systems Conference, 2009:156-162.

[22]Chang H, Roughan M, Uhlig S, et al. The many facets of Internet topology and traffic[J]. Networks and Heterogeneous Media, 2006, 1(4): 569-600.

[23]Bailey D, Wright E. Connecting fibers-practical fiber optics-5[J]. Practical Fiber Optics, 2003: 97-119.

[24]Habibi D, Nguyen H N, Phung Q V, et al. Establishing physical survivability of large networks using properties of two-connected graphs[C]// Proceedings of IEEE Region 10 on TENCON, 2005: 1-5.

[25]Knight S, Nguyen H X, Falkner N, et al. The internet topology zoo[J]//Proceedings of IEEE Journal on Selected Areas in Communications, 2011, 29(9): 1765-1775.

[26]中国互联网络信息中心. 2014年中国互联网络发展状况统计报告[EB/OL]. (2014-07-01)[2015-06-31]. http://www.cnnic.net.cn/gywm/xwzx/rdxw/2014/201407/W020140721559080702009.pdf.

CNNIC. Statics report for China Internet development in 2014[EB/OL]. (2014-07-01)[2015-06-31]. http://www.cnnic.net.cn/gywm/xwzx/rdxw/2014/201407/W020140721559080702009.pdf. (in Chinese)

[27]Internet World Stats. Internet usage statistics[EB/OL]. (2014-06-02)[2015-06-31]. http://www.internetworldstats.com/am/us.htm, 2015.

[28]Zegura E W, Calvert K L, Acharjee S B. How to model an internetwork[C]//Proceedings of INFOCOM'96 15th Annual Joint Conference of the IEEE Computer Societies, 1996, 2: 594-602.[29]汪小帆， 李翔， 陈关荣. 网络科学导论[M]. 北京：高等教育出版社， 2012.

WANG Xiaofan，LI Xiang, CHEN Guanrong. Network science: an introduction[M]. Beijing: Higher Education Press， 2012. (in Chinese)

[30]Haddadi H, Rio M, Iannaccone G, et al. Network topologies: inference, modeling, and generation[J]. IEEE Journal on Communications Surveys & Tutorials, 2008, 10(2): 48-69.

Router-level topology generation research for Internet backbone networks under multiple constraints

WU Yuanli1,2,3, SI Guangya1, LUO Pi1

(1.DepartmentofInformationOperation&CommandTraining,NationalDefenseUniversityofChina,Beijing100091,China；2.GraduateSchool,NationalDefenseUniversityofChina,Beijing100091，China;3.The309HospitalofPLA,Beijing100091,China)

Abstract：ThebackbonenetworkisthemainpartoftheInternettraffictransfersystem,andtherouter-leveltopologyofbackbonenetworkisofgreatsignificancefortheresearchonnetworksurvivability.Duetovariousreasons,itisdifficulttogetrealInternetbackbonerouterleveltopology.Byanalyzingtheformingdrivingfactorsofbackbonenetwork,thegeographicalconstraints,theexchangingstrengthofnodes,infrastructurecostandrobustness,etc.werecombined;therouter-leveltopologygenerationmethodforInternetbackbonenetworksundermultipleconstraintswasproposed.Themethodcangeneraterouterleveltopologyfornetworkwhichcannotbeinferredfrompubliclyaccessiblemeasurementdata,andcangeneratetopologysetthatconsistsofrealisticalternativesforabackbonenetwork.Finally,theeffectivenessofthemethodisverifiedbytworealInternetbackbonenetworks.

Keywords：Internet;topologygeneration;networksurvivability

doi:10.11887/j.cn.201603028

收稿日期：2015-04-08

基金项目：国家自然科学基金资助项目(U1435218，61273189，61403401，61174035)

作者简介：吴元立(1985—)，男，辽宁灯塔人，博士研究生，E-mail：dtnudt@126.com； 司光亚(通信作者)，男，教授，博士，博士生导师，E-mail：sgy863@sina.com

中图分类号：TP393

文献标志码：A

文章编号：1001-2486(2016)03-167-07

http://journal.nudt.edu.cn