东北大学学报:自然科学版   2015, Vol. 36 Issue (9): 1237-1241   PDF (655 KB)    
互联网宏观拓扑结构的耗散性分析
刘 晓, 赵 海, 王进法, 何 璇    
(东北大学 信息科学与工程学院, 辽宁 沈阳 110819)
摘要:互联网宏观拓扑中涌现着既机械又灵活的结构秩序.明确该秩序的耗散过程及相关方面的研究,对预测网络拓扑演化的方向及再设计互联网具有重要意义.择取CAIDA机构IPv4、IPv6与AS级网络拓扑数据,对比分析网络结构秩序的耗散行为,并探讨网络结构秩序同网络规模及网络基本连通性的相关关系.结果显示3种网络均为兼具集权式秩序性与均权式无序性的耗散结构,且其秩序在耗散过程中不断演化;3种网络规模以及网络基本连通性与网络结构秩序呈正相关关系,说明网络结构秩序在互联网发展过程中逐渐耗散.
关键词互联网拓扑演化     结构秩序     耗散     IPv4     IPv6     互联网AS级    
Dissipation Analysis of Internet Topology Structure
LIU Xiao, ZHAO Hai,WANG Jin-fa,HE Xuan    
(School of Information Science & Engineering, Northeastern University, Shenyang 110819, China. Corresponding author: LIU Xiao, E-mail: liuxiao@neuera.com)
Abstract: Mechanical and flexible structural orders emerge in the Internet topology. The researches describing the dissipative structural order and related topics are very important in the redesign of the Internet, and it is also of great importance in the field of predicting the evolution of Internet topology. IPv4, IPv6 and AS-level network topologies data which authorized by cooperative association for Internet data analysis (CAIDA) are used in this paper, and the relationships among the network structural orders and the size and connectivity of the network are discussed, the results show that all the 3 kinds of network are of dissipative structures, which behave both centralization and equalization, and their orders are continuously evolving in the process of dissipation. The positive correlativity among the network structural orders and the size and connectivity of the network size shows that the network structural order is gradually dissipated in the development process of the Internet.
Key words: Internet topology evolution     structural order     dissipation     IPv4     IPv6     Internet AS-level    

互联网作为一个复杂的生命巨系统在演化过程中表现出极强的生命力[1],其宏观拓扑结构表现出极强的复杂网络特性[2,3].因此,互联网的复杂结构不仅仅是可互操作的机械结构,亦是具有完备演化秩序的可融合有机生命耗散结构.Kevin预言,互联网会逐渐摆脱集权式的中心化控制[4],但对于“集权”是否让位于“均权”,“有序”是否真的让位于“无序”,国内外学者尚未从IPv4,IPv6与AS级网络结构入手对其耗散性进行相关研究.对此,本文分析了表征网络结构秩序状态的幂指数和标准网络结构熵的耗散行为,并对其耗散性与网络规模及网络基本连通性的相关关系进行探讨,以期客观深入地理解互联网耗散结构秩序性,指导网络结构演化态势相关研究,为再设计互联网提供建设性意见,并为预测网络演化方向提供理论依据[5].

1 实验基础:数据来源与相关定义

本文基于CAIDA (cooperative association for Internet data analysis)_Ark探测项目,取2009年~2013年共60个月IPv4,IPv6与AS级互联网宏观拓扑数据,数据量级约为107,以月为探测单元,对3种网络结构秩序进行比较分析.根据Barab ási等[6]的研究,数据探测源点的平等性简化了IP级拓扑探测及研究的过程,通过测量较少的目的源点便足以获取互联网结构秩序演化的本质特性.分析之前,首先给出如下定义.

定义1 网络结构秩序:本文将网络结构秩序描述为网络结构混乱度.以幂指数量化网络结构层级秩序,以标准网络结构熵量化网络宏观结构秩序.

定义2 网络结构熵(Internet structure entropy)[7]:其宏观意义描述了复杂网络拓扑结构分布状态的均匀程度,结构分布越不均匀,熵越小,反之越大;从微观层面,它是系统组成单元混乱和无序程度的度量,即系统秩序性愈强,熵愈小;系统愈无序,熵愈大[8].

式中:N为网络中节点总数;p(k)为网络节点度分布;H表示网络结构熵.从公式可知,网络结构熵是由网络节点的度分布决定的,根据网络结构熵的极值性,可得如下定理[8]

定理1 当网络拓扑结构呈完全均匀状态时,各个节点连接状况大致相当,则认为此时网络最无序,网络结构熵最大,即Hmax=lnN.

定理2 当网络为星形结构时,结构最不均匀,形成一种极端“专制”的集权式网络,然而此种网络拓扑具有强秩序性,此时网络结构熵达到极小值,即Hmin=lnN-[N/(N-1)]ln(N-1).

定义3 标准网络结构熵:文献[8]定义了标准网络结构熵,对网络结构熵进行归一化处理,以消除数据样本对统计结果的影响.

归一化处理消除了网络中节点数目对网络结构熵值的影响,即标准网络结构熵与统计所采用的数据样本无关,因此本文即通过标准网络结构熵的变化规律研究网络宏观拓扑结构的演化趋势[9].

定义4 网络规模包括网络中节点数N和连边数E,是互联网最基本的拓扑结构.网络规模演化是最简明、最直观的网络演化,是随时间增长网络中节点与边的增长情况.

2 IP级,AS级互联网结构耗散性分析

根据定义1,本文所述的结构秩序指网络结构混乱程度,分为结构层级秩序与宏观拓扑结构秩序.客观评价IPv4,IPv6与AS级网络拓扑状态有序与否,并根据其5年探测时间内的演化规律分析网络拓扑耗散特性,有助于理解互联网复杂结构层级秩序的演化规律,指导网络演化态势相关研究.

2.1 互联网拓扑层级结构耗散性分析

对2009年~2013年的探测数据,每年取2个探测单元(1月与7月),对IPv4,IPv6与AS级网络拓扑层级秩序演化进行分析.图1a,1b,1c分别为IPv4,IPv6和AS级互联网度分布频度图,为观察分析之便,取对数坐标,并对度分布进行幂律拟合,用幂指数量化3种网络层级秩序,其演化分别如图2a,2b,2c所示.对于幂律分布有p(k)~k-α,其中k为节点度值,p(k)是度值为k的节点出现的概率,α即为幂指数[10].

图 1 不同时间单位下IPv4,IPv6与AS级网络度分布频度 Fig. 1 Degree distribution of IPv4,IPv6 and AS-level
within different time units
(a)—IPv4; (b)—IPv6; (c)—AS.

如图1所示,IPv4,IPv6及AS级网络中存在少数具有很多边的“中心节点”(HUB),同时大多数节点的度值k较低,且对数坐标下,不同观测时间及不同探测尺度的3种网络度分布均明显服从幂律分布[6,11].幂律描述的正是从HUB到低度值节点的层级分布规律,并借由幂指数量化这种网络拓扑的扭曲层级现象.

网络度分布p(k)以幂律拟合后,幂指数α演化如图2所示,图2a中IPv4的幂指数大于2,演化趋势平缓,说明网络中大度值的HUB节点只占节点总数相当少一部分,而其余大量小度值节点具有更相近的度值;图2b中IPv6与图2c的AS级幂指数在1.8左右,说明网络中HUB节点略多,对于技术类网络,这意味着实现并维持这样的网络需要持续注入巨大成本.

图 2 IPv4,IPv6与AS级网络度分布幂指数时序演化 Fig. 2 Evolution of the degree distribution exponents
for IPv4,IPv6 and AS-level
(a)—IPv4; (b)—IPv6; (c)—AS级.

综上,幂指数分布结果展示了真实的互联网兼具集权式的秩序与均权式的无序两种属性.一方面,为了保证通信效率,必须存在HUB节点;另一方面,由于受到成本制约,HUB节点又不能太多,因此互联网的幂指数经过长时间的演化会更倾向位于2~3之间.可见,互联网的拓扑层级秩序既不会存在大量HUB而导致极端专制,也不会存在所有节点度值相近的情况而导致均权和无序,故是一个耗散的层级结构.

2.2 互联网宏观拓扑秩序耗散性分析

依据式(1)~式(2)及定理1和2对IPv4、IPv6与AS级互联网2009年~2013年内60个探测时间单元的标准网络结构熵进行计算,其时序演化情况如图3所示.

图 3 IPv4,IPv6与AS级网络标准网络结构熵演化 Fig. 3 Evolution of the Internet structural entropy for
IPv4,IPv6 and AS-level
(a)—IPv4; (b)—IPv6; (c)—AS级.

由图3可知,不同协议及不同探测尺度下互联网标准网络结构熵均为时序上增大.图3a中IPv4网络结构熵从0.072波动至0.077;图3b的IPv6结构熵较稳定,未呈现明显波动,仅在2013年下半年从0.014上升至0.0155;图3c中AS级结构熵增长明显,60个月内从0.16升至0.173.将这3种网络结构熵进行对比,结果为AS级>IPv4>IPv6,说明IP级互联网宏观拓扑较AS级更具秩序性.对IP级网络进行比较,发现IPv6网络拓扑较IPv4表现更强的有序性.可见,上层互联网的宏观拓扑不及微观尺度的IP级互联网有序.但这只是相对而言,根据定理1,标准网络结构熵最大值为1,此时网络为均匀网络,最为无序.如图3所示,即便是标准网络结构熵值最大的AS级网络,量级亦仅为10-1,远非均匀网络,互联网仍是宏观有序的拓扑结构,所观察到的熵值增大趋势只是在网络结构演化耗散过程中的一次相变,即互联网结构的秩序是在不断耗散不断演变的过程中发展的.

3 网络规模、平均度与网络结构秩序

网络演化是由网络内部微观扰动引起的[12],表现在外部为网络规模的节点与边的演变,而表现在网络连通性上则为网络平均度的动态演化.以此为基础,探究IP级与AS级网络的网络规模以及基本连通性的演化规律与网络结构秩序间的关系,分析其耗散特性,可以为客观有效评价和预测网络演化方向提供依据.

3.1 网络规模与网络结构秩序

下面对 IPv4,IPv6与AS级网络规模(节点数N与连边数E)时序演化,以及节点N与标准网络结构熵关系进行观察与分析.图4为最简明、直观的网络演化,即随着时间网络中节点与边的变化情况.其中图4a,4b,4c分别为互联网IPv4, IPv6与AS级网络节点与边的演化,其中圆点曲线代表节点数,圆圈曲线代表连边数.

图 4 IPv6与AS级网络规模时序演化 Fig. 4 Evolution of the network size for IPv4,IPv6
and AS-level
(a)—IPv4; (b)—IPv6; (c)—AS级.

图4为节点与边的直观时序演化,由图4可以看出,IP级网络中节点与边增长情况存在明显同升同降的伴随关系,甚至演化过程中的特征点都一一对应.图4a中IPv4网络节点与边的数量级已突破105,演变过程在小涨落中增长缓慢平稳;图4b中IPv6节点与边的数量级仅为104,但IPv6节点与边数增长明显,在5年的探测范围内,节点数从5545增长至58510,连边数从5765增长至65678,5年间节点与边数涨幅均在10倍以上;图4c为AS级节点与边增长情况,两者增长趋势并未像IP级呈现一致性,其节点数量级为104,在探测期间连边数量级由104升至105.

互联网网络内部深层次的变化最终都会表现在网络节点与边的变化上[9],将网络规模的节点数做横坐标,衡量网络宏观秩序的标准网络结构熵做纵坐标,网络规模与网络拓扑秩序相关性如图5所示.

图 5 IPv4,IPv6与AS级网络节点数与熵关系 Fig. 5 Relation of the nodes and Internet structural
entropy for IPv4,IPv6 and AS-level
(a)—IPv4; (b)—IPv6; (c)—AS级.

图5a中节点数与网络结构熵并未呈明显相关性,说明IPv4网络规模与网络结构的秩序性并无关系;图5b,5c中IPv6与AS级网络中两者呈现相关性,IPv6网络节点数与标准网络结构熵相关性如图中虚线拟合所示并不明显,但AS级网络其两者呈明显伴随增长关系.该相关性可总结为:对于IPv6与AS级网络拓扑结构,随网络节点不断增多,网络规模在小涨落中扩大,网络结构熵也随之增大,网络结构秩序在该过程中逐渐耗散.

3.2 网络平均度与网络结构秩序

图6a,6b,6c分别为 IPv4,IPv6与AS级网络中全部节点度值平均数随时间演化情况.

图 6 IPv4,IPv6与AS级网络平均度时序演化 Fig. 6 Evolution of the average degree for IPv4,
IPv6 and AS-level
(a)—IPv4; (b)—IPv6; (c)—AS级.

由图6可知3种网络平均度在探测期间呈增长趋势,说明网络中每个节点对其邻居节点个数的期望不断增大,网络的连接紧密度提高.图6a所示IPv4网络节点平均度值从2.6平稳增长至2.9,期间偶尔出现涨落;图6b的IPv6网络平均度值通过明显的小涨落,从2.07最终升至2.25并基本稳定在其上下;图6c中AS级网络平均度从5.6震荡升至6.8.由此可知,3种网络的基本连通性有AS级>IPv4>IPv6,即AS级网络较IP级网络具有更强连通性,AS级网络内部节点与其邻居节点连接紧密程度更高,且IP级网络平均度的增长也不及AS级明显.另外,IPv4网络的平均度略大于IPv6网络,参考前述研究结果(如3.1节),发现IPv4网络增长放缓,各特征参数趋于平稳,IPv4网络的连通性更高,说明IPv4网络较成熟.

网络内部结构之变借由网络基本连通性体现出来,那么随着网络连通性的演化,网络宏观拓扑秩序亦进行着演变.为研究两者关系,将代表网络基本连通性的网络平均度值做横坐标,衡量网络结构宏观秩序的标准网络结构熵做纵坐标,观察两者的耗散过程如图7所示.

由图7可知,IPv4,IPv6与AS级网络平均度与网络结构熵线性相关,相关关系如图中虚线,随网络结构熵增长,网络结构秩序逐渐消陨,网络连通程度增强.图7中拟合直线斜率即为网络平均度对网络结构熵的影响程度,结果为IPv4>AS>IPv6,说明IPv4网络结构熵受平均度影响较大,其平均度的改变映射到网络结构秩序中会引起较大变化.

图 7 IPv4,IPv6与AS级网络平均度与熵关系 Fig. 7 Relationships of the average degree and
Internet structural entropy for IPv4,IPv6
(a)—IPv4; (b)—IPv6; (c)—AS级.
4 结    论

1) 通过分析IPv4,IPv6与AS级网络度分布幂指数与标准网络结构熵的耗散行为,发现3种网络兼具秩序与无序两种属性,但其既不会存在大量HUB节点,也不允许所有节点度值相近.3种网络秩序的演变只是在网络结构演化耗散过程中的一次相变,互联网仍为宏观有序的拓扑结构.

2) 观察网络规模及网络基本连通性对网络结构秩序的影响,发现IPv4,IPv6与AS级网络规模及平均度均与标准网络结构熵正相关.网络结构熵会随网络规模的扩大,网络连通性的增强而增大,网络结构秩序在诸多特征参量的演化过程中耗散.但根据2.2节的相关结论,3种网络结构秩序在耗散之后,仍为宏观有序的拓扑结构.

互联网的建设在追逐高经济效益的同时也争 取获得较高网络连通性,网络跨层间连接增多,各 城域网直接与骨干网互连,实现网络传输最高性价比.互联网的拓扑既要灵活组织又要保证固有秩序,这一秩序耗散规律与相关性的发现可丰富人们对互联网宏观与微观秩序的探求,为预测互联网发展提供方向,并为再设计互联网提供理论依据.

参考文献
[1]Oliveira R V,Zhang B,Zhang L.Observing the evolution of Internet AS topology[J].ACM SIGCOMM Computer Communication Review,2007,37(4):313-324. (1)
[2]Albert R,Jeong H,Barabási A L.Internet:diameter of the world-wide web[J].Nature,1999,401(6749):130-131. (1)
[3]Pastor-Satorras R,Vespignani A.Evolution and structure of the Internet:a statistical physics approach[M].Cambridge:Cambridge University Press,2007. (1)
[4]Kevin K.Out of control:the new biology of machines,social systems,and the economic world[M].New York:Basic Books,1994:349-351. (1)
[5]Ai J,Zhao H,Kathleen M,et al.Evolution of IPv6 Internet topology with unusual sudden changes[J].Chinese Physics:B,2013,22(7):078902-078909. (1)
[6]Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512. (2)
[7]Ted G L.Network science:theory and applications[M].New York:John Wiley & Sons,2009:124-126,136-137. (1)
[8]谭跃进,吴俊.网络结构熵及其在非标度网络中的应用[J].系统工程理论与实践,2004,24(6):1-3.(Tan Yue-jin,Wu Jun.Network structure entropy and its application to scale-free networks[J].Systems Engineering Theory & Practice,2004,24(6):1-3.) (3)
[9]Zhang G Q, Quoitin B, Zhou S.Phase changes in the evolution of the IPv4 and IPv6 AS-level Internet topologies[J].Computer Communications,2011,34(5):649-657. (2)
[10]郭世泽,陆哲明.复杂网络基础理论[M].北京:科学出版社,2012:41-72.(Guo Shi-ze,Lu Zhe-ming.The basic theory of complex network[M].Beijing:Science Press,2012:41-72.) (1)
[11]Newman M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256. (1)
[12]赵海,刘怡文,艾均,等.IP级拓扑新生与消亡节点的特征[J].东北大学学报:自然科学版,2013,34(9):1232-1235.(Zhao Hai,Liu Yi-wen,Ai Jun,et al.Characteristics of birth and death nodes with IP-level topology[J].Journal of Northeastern University:Natural Science,2013,34(9):1232-1235.) (1)