大规模网络拓扑数据处理技术研究【毕业论文】.doc

1、本科毕业设计（20届）大规模网络拓扑数据处理技术研究所在学院专业班级计算机科学与技术学生姓名学号指导教师职称完成日期年月摘要【摘要】INTERNET作为当今人类社会信息化的标志，其规模正以指数级的速度高速增长。这种增长不仅表现在了其节点和连接的数量的增长，还表现在了INTERNET的复杂性以及在现今社会中所发挥的作用，甚至其地理位置几乎遍布了世界的每一个角落。正因为INTEMET的重要性及复杂性，网络拓扑结构已经成为计算机研究领域的专家和学者研究的焦点。尽管互联网迅速增长，但是其拓扑结构的某些特点保持不变。分析和理解这些不变量可能有助于未来互联网研究和发展，如新的协议设计。本文在对INTERN

2、ET网络拓扑研究大量的调研的基础上，将其分为四个部分INTERNET网络拓扑数据收集，INTERNET网络拓扑数据特征，INTERNETT网络拓扑数据处理分析和演示实现。针对每一部分都对该研究领域中的研究成果及方法给与了比较详尽的分析与讨论。【关键词】INTERNET网络拓扑，拓扑数据，拓扑特征，演示ABSTRACT【ABSTRACT】THEINTERNETHASEXPERIENCEDATREMENDOUSGROWTHINITSSIZEANDCOMPLEXITYSINCEITSCOMMERCIALIZATIONTHISGROWTHINITSNOTONLYSHOWSTHENUMBEROFNODE

3、SANDLINKS,BUTALSOINTHEGROWTHOFTHECOMPLEXITYOFTHEPERFORMANCEINTERNETANDINOURSOCIETYTODAYTHEROLE,EVENITSLOCATIONISFOUNDALMOSTEVERYCORNEROFTHEWORLDBECAUSEOFTHEIMPORTANCEANDCOMPLEXITY,INTEMETTOPOLOGICALSTRUCTUREOFCOMPUTERRESEARCHFIELDHASBECOMETHEFOCUSOFRESEARCHEXPERTSANDSCHOLARSALTHOUGHTHEINTERNETRAPIDG

4、ROWTH,BUTITSTOPOLOGICALSTRUCTURECHARACTERISTICSOFSOMEREMAINUNCHANGEDANALYZEANDUNDERSTANDTHESEINVARIANTSMAYHELPFUTUREINTERNETRESEARCHANDDEVELOPMENT,SUCHASTHENEWPROTOCOLDESIGNINTHISPAPER,WEMAKEALARGENUMBERSOFINVESTIGAFIONSANDCLASSIFYTHEINTERNETTOPOLOGYRESEARCHINTOTHREETYPESINTERNETTOPOLOGYDATACOLLECTI

5、ON，INTERNETTOPOLOGYCHARACTERISTICS，THETOPOLOGYOFTHENETWORKDATAPROCESSINGANALYSISANDDEMOREALIZEHERE，WEANALYZEANDDISCUSSTHEIRRESEARCHWAYSANDRESEARCHFMDINGSFOREACHTYPES【KEYWORDS】INTERNETTOPOLOGY,TOPOLOGYDATA,TOPOLOGYCHARACTERISTIC，DEMONSTRATE目录1绪论111引言112INTERNET网络拓扑数据研究的重要性113INTERNET网络拓扑数据处理研究的内容214I

6、NTERNET网络拓扑研究背景315本论文的主要研究内容316论文整体结构与章节安排32INTERNET网络拓扑数据研究综述与分析421INTERNET网络拓扑数据获取4211IP级网络拓扑数据收集4212AS级网络拓扑数据获取722INTERNET网络拓扑数据特征8221出度与出度频率8222成长性与优先附着9223小世界特性9224网络恢复10225其他度量值1023INTERNET网络拓扑数据结构10231总线拓扑结构（图23）11232星型拓扑结构（图24）11233环形拓扑结构（图25）11234树型拓扑结构（图26）12235网状拓扑结构（图27）12236混合型拓扑结构（图28）

7、123INTERNET网络拓扑数据类型分析与处理模型的建立1231ASLINKS数据集1332ITDK数据集1533SKITTER_AS_LINKS数据集184INTERNET网络拓扑数据处理结果的演示2041ASLINKS数据集处理2042SKITTER_AS_LINKS数据集处理315总结和展望39参考文献40致谢错误未定义书签。11绪论11引言INTERNET作为当今人类社会信息化的标志，其规模正以指数级的速度高度增长。这种增长不仅表现在了其节点和连接的数量的增长，还表现在了INTERNET的复杂性以及在现今社会中所发挥的作用，甚至其地理位置INTERNET几乎遍布了世界的每一个角落。图

8、11给出了近些年来中国网民规模与普及率状况。从侧面说明了互联网的增长情况。正因为INTERNET的重要性及复杂性，其已经成为计算机研究领域的专家和学者研究的焦点。图11中国网民规模与普及率状况12INTERNET网络拓扑数据研究的重要性目前，INTERNET网络拓扑结构的研究已经吸引了越来越多的国内外计算机领域专家和学者的目光，并引起了他们了重视。而在最近几年里相关的研究已经取得了很大的进展。一般来说，INTERNET网络拓扑结构研究的重要性主要体现在以下几个方面（1）对INTERNET网络拓扑的了解有助于设计更好的协议来控制网络。对网络进行有效的控制一直是网络领域中的一个重点，怎么样才能让I

9、NTERNET网络更好地运行，进行网络控制所要解决的一个很大的问题是怎么样才能让INTERNET网络按照我们所构想的方式运行。INTERNET网络拓扑的研究首先可以帮助我们了解INTERNET网络结构，进而发现INTERNET网络运行存在的缺陷，最后设计出新的INTERNET网络控制协议并去验证它。（2）对INTERNET网络拓扑的研究有利于更加准确的模拟INTERNET。由于各种因素的影响，目前直接在INTERNET网络上研究是极其困难的，所以对一般的研究来说，我们都要建立INTERNET网络拓扑模型，借助模型来研究INTERNET网络拓扑结构。值得一说的是INTERNET网络拓扑研究领域中

10、的一个重要的分支就是研究INTERNET网络拓扑的建立。3对INTERNET网络拓扑研究有助于维护网络安全。计算机病毒不但本身具有破坏性，更有害的是具有传染性，一旦病毒被复制或产生变种，其速度之快令人难以预防。而对INTERNET网络拓扑进行研究了解其中的结构对控制计算机病毒在网络上的蔓延有重要的作用。4对INTERNET网络拓扑特征的研究有利于设计有效的网络测量参数，更方便的来测量和刻画整个INTERNET。5对INTERNET网络拓扑研究有助于维护国家安全性。网络安全是国家安全的一个重要的方面，因此有必要控制好整个网络的行为，而控制INTERNET网络行为首先要做的就是进行INTERNET

11、网络拓扑的研究。13INTERNET网络拓扑数据处理研究的内容INTERNET网络拓扑研究是一项长期的复杂的工作，其中不但包含了很多的内容，而且甚至涉及多个领域。一般来说，我们可以将INTERNET网络拓扑数据研究的主要内容可以归为下面三个部分1INTERNET网络拓扑数据获取获取一份完整的全面的准确的INTERNET网络拓扑数据是一项非常困难和复杂的。由于INTERNET规模庞大而且结构复杂，就现有的技术来说，获取一份完整的INTERNET网络拓扑数据几乎是不可能完成的任务。研究到今，专家和学者们已经提出并应用了许多方法，但怎样才能更快更全面地收集一份更加完整的INTERNET网络拓扑数据在

12、研究领域中仍然是值得研究和解决的一个问题。2INTERNET网络拓扑数据特征发现INTERNET网络拓扑数据虽然是庞大而复杂的，但它自身仍然存在着某些规律和特征。在过去的几年里，INTERNET网络拓扑数据特征发现一直是研究人员热衷的工作，而经过研究人员几年的不断探索分析，逐渐的探索出一些新奇的特征。3INTERNET网络拓扑数据结构建模INTERNET网络拓扑数据在结构上与INTERNET网络拓扑结构是一样的，所以分析网络拓扑结构能对我们进行网络拓扑数据处理的研究有重大意义。14INTERNET网络拓扑研究背景INTERNET网络拓扑研究经历了从经验假设到客观分析，从单纯的计算机网络拓扑结构

13、研究到复杂系统特征研究的发展过程。最初的INTERNET网络拓扑研究由于缺乏真实的数据支持，只能进行经验假设，现在已经可以针对相对完整的数据进行统计分析，并可对各种假设进行验证。从1995年开始，大规模的INTERNET拓扑结构测量工作逐渐展开，到目前为止已经收集到了大量的网络拓扑数据。这些拓扑数据相对比较完整，为INTERNET网络拓扑研究者提供了大量的真实的实验数据支持。早期对INTERNET网络拓扑的特征更是无从认识，现在一些研究成果已经把INTERNET网络与复杂系统特征研究结合起来。INTERNET网络拓扑的建模工作也取得了长足的进展，从相对简单的随即模型到复杂的幂率模型，其结果都越

14、来越接近真实的INTERNET。对于节点间关系的理解更是有了质的突破，从原来对关系的一无所知到现在对关系进行定义和区分。所有这些都说明了INTERNET网络拓扑研究在过去的一些年里取得的一些成果。即便如此，如果想准确回答INTERNET网络拓扑所提到的几个问题，仍然还有一定的差距，而且一些新的发现也对已有的成果提出了挑战。15本论文的主要研究内容本文主要包含以下内容1对INTERNET网络拓扑数据获取、拓扑数据特征、拓扑结构进行分析与讨论。详细考察了INTERNET网络拓扑在研究中的发展过程和国内外的当前研究现状。2简单介绍目前利用网络拓扑结构数据模拟网络结构的可视化工具。3针对每一种网络拓扑

15、数据类型，作一个详细的分析，并建立相应的处理模型。4根据处理模型，开发一个简单的演示工具。16论文整体结构与章节安排第L章即本章分别介绍了INTERNET现状，INTERNET网络拓扑的研究意义、分类以及背景。第2章针介绍了INTERNET网络拓扑数据处理研究的内容，并分别进行比较详细的分析与讨论。第3章针对每一种网络拓扑数据类型，作一个详细的分析，并建立相应的处理模型。第4章根据处理模型，开发一个简单的演示工具。第5章对全文进行了总结。分析作中的不足，并提出了将来要做的工作。2INTERNET网络拓扑数据研究综述与分析21INTERNET网络拓扑数据获取网络层的目的是实现两个端系统之间的数据

16、透明传送，具体功能包括寻址和路由选择、连接的建立、保持和终止等。因此，INTERNET网络拓扑研究通常集中在网络层。在网络层上研究INTERNET网络拓扑，才能更加真实地反映和了解INTERNET网络的实际结构。IP级路由级和自治系统ASAUTONOMOUSSYSTEMS级是在网络层上的INTERNET网络拓扑研究的主要的两个方面。INTERNET网络拓扑数据的获取主要是指获取网络节点资源，以及节点间的连接关系。IP级的网络拓扑节点资源主要是指路由器，即获取路由器资源以及路由器间的连接关系。AS级的网络拓扑数据的获取主要是指获取AS资源，以及AS间的连接关系。如图21中，A为IP级拓扑图，B为

17、AS级拓扑图。图21IP级拓扑图和AS级拓扑图211IP级网络拓扑数据收集互联网主要的节点设备就是路由器，可以说是INTERNET的枢纽。路由器有两大典型功能，即数据通道功能和控制功能。数据通道功能包括转发决定、背板转发以及输出链路调度等，一般由特定的硬件来完成；控制功能一般用软件来实现，包括与相邻路由器之间的信息交换、系统配置、系统管理等。正是因为路由器在INTERNET中的重要性，在该层研究进行INTERNET网络拓扑和获取网络拓扑数据就变得非常的重要。而数据的收集主要有以下几种方法。1SNMP方法SNMP是一种网络设备间交换管理信息的应用层协议。SNMP主要由MIB管理信息库、SMI管理

18、信息的结构和标识和SNMP简单网络管理协议组成。各个路由器代理所维护的MIB管理信息库中包含了网络拓扑的主要信息，如表21所示。由表可以看出，只要分析“与端口相连的下一跳路由器IP地址”、“目的IP地址”和“端口IP地址”这三项就可以基本确定路由器之间的连接信息，收集和分析这些信息，便可以得到相关的拓扑数据。SNMP还可以根据网络的状况自动更新，因此我们获得的数据都会是最新的。表21MIB信息变量名称接口索引值路由类型子网掩码与端口相连的下一跳路由IP地址目的IP地址端口IP地址IP路由表IPROUTEIFINDEXIPROUTETYPEIPROUTEMASKIPROUTENEXTHOPIPR

19、OUTEDSETIP地址表IPADENTIFINDEXIPADENTNETMASKIPADENTADDR2TRACEROUTE方法TRACEROUTE是用来侦测主机到目的主机之间所经路由情况的重要工具，也是最便利的工具。前面说到，尽管PING工具也可以进行侦测，但是，因为IP头的限制，PING不能完全的记录下所经过的路由器。所以TRACEROUTE正好就填补了这个缺憾。TRACEROUTE的原理是非常非常的有意思，它受到目的主机的IP后，首先给目的主机发送一个TTL1的UDP后面就知道UDP是什么了数据包，而经过的第一个路由器收到这个数据包以后，就自动把TTL减1，而TTL变为0以后，路由器就

20、把这个包给抛弃了，并同时产生一个主机不可达的ICMP数据报给主机。主机收到这个数据报以后再发一个TTL2的UDP数据报给目的主机，然后刺激第二个路由器给主机发ICMP数据报。如此往复直到到达目的主机。这样，TRACEROUTE就得到了所有的路由器IP。避开了IP头只能记录有限路由IP的问题。3DNS方法DNS是域名系统DOMAINNAMESYSTEM的缩写，它是由解析器和域名服务器组成的。域名服务器是指保存有该网络中所有主机的域名和对应IP地址，并具有将域名转换为IP地址功能的服务器。其中域名必须对应一个IP地址，而IP地址不一定有域名。域名系统采用类似目录树的等级结构。域名服务器为客户机/服

21、务器模式中的服务器方，它主要有两种形式主服务器和转发服务器。将域名映射为IP地址的过程就称为“域名解析”。在INTERNET上域名与IP地址之间是一对一（或者多对一）的，域名虽然便于人们记忆，但机器之间只能互相认识IP地址，它们之间的转换工作称为域名解析，域名解析需要由专门的域名解析服务器来完成，DNS就是进行域名解析的服务器。DNS命名用于INTERNET等TCP/IP网络中，通过用户友好的名称查找计算机和服务。当用户在应用程序中输入DNS名称时，DNS服务可以将此名称解析为与之相关的其他信息，如IP地址。DNS系统除了进行网络设备口地址到名字的映射外，还管理和维护一些其他的信息，如设备的硬

22、件平台和操作系统等。这些信息对于我们收集INTERNET网络拓扑数据有着非常重要的作用，从这些信息中，我们还可以提取到相关的路由资源信息和连接信息。4PING方法PINGPACKETINTERNETGROPE，因特网包探索器，用于测试网络连接量的程序。PING发送一个ICMP回声清求消息给目的地并报告是否收到所希望的ICMP回声应答。它是用来检查网络是否通畅或者网络连接速度的命令。作为一个生活在网络上的管理员或者黑客来说，PING命令是第一个必须掌握的DOS命令，它所利用的原理是这样的网络上的机器都有唯一确定的IP地址，我们给目标IP地址发送一个数据包，对方就要返回一个同样大小的数据包，根据返

23、回的数据包我们可以确定目标主机的存在，可以初步判断目标主机的操作系统等。单独依靠PING命令是无法获得完整的INTERNET网络拓扑信息的，甚至连路由器间连接信息的获取都非常困难。一般来说，PING工具是要配合其他方法一起来收集INTERNET网络拓扑数据的。但是，PING方法与TRACEROUTE一样存在着类似的缺陷。而且由于广播PING操作会产生很多的数据包，因此对网络带宽会造成一定的压力。以上是获取IP级的INTERNET网络拓扑数据主要的几种方法。但在实际的数据获取中，由于各种方法都存在着一些缺陷和困难，因此通常来说都是使用几种方法共同来完成数据的收集工作的。在CORNEU大学的OCT

24、OPUS项目针对SNMP、PING、DNS和TRACERONTE分别设计了域内的网络拓扑数据获取算法，并进行了比较，比较结果如表22所示。而且还针对INTERNET网络拓扑数据收集设计并使用了TRACEROUTE的算法，并说明了使用SNMP、PING和DNS一般只适用于一个域内路由拓扑数据的发现和获取，对于大规模的INTERNET网络拓扑数据收集并不合适。在INTERNET网络拓扑数据收集中，主要使用TRAEEROUTE的方法，但是很多研究者为了更好更完整的获取INTERNET网络拓扑数据通常采用多种方法混合的方式。即便如此，由于INTERNET规模庞大，结构复杂而且设备数量巨大，想要获取更加

25、完整的IP级INTERNET网络拓扑数据仍然需要解决许多难以克服的困难。表22获取算法的结果比较CUCSNETWORKSPEEDOVERHEADCOMPLETENESSACCURACYSNMPDNSZONETRANSFER/BROADCASTPINGDNSZONETRANSFERTRACEROUTEPROBINTRACEROUTETIMEMINUTES1114812858PINGS5119584061LTRACES00480336NORMALIZEDOVERHEAD5119517521249HOSTS482994851004809931765POUTERS5100510051005100SUB

26、NETS7100686710071001001009999CORNELLNETWORKSPEEDOVERHEADCOMPLETENESSACCURACYSNMPDNSZONETRANSFER/BROADCASTPINGDNSZONETRANSFERTRACEROUTEPROBINTRACEROUTETIMEMINUTES19328801080PINGS139102048532TRACES073672735NORMALIZEDOVERHEAD1394298720702HOSTS60281007367100273493ROUTERS1399010015510014493SUBNETS9315866

27、221005121001009090212AS级网络拓扑数据获取一个自治系统就是处于一个管理机构控制之下的路由器和网络群组。它可以是一个路由器直接连接到一个LAN上，同时也连到INTERNET上；它可以是一个由企业骨干网互连的多个局域网。在一个自治系统中的所有路由器必须相互连接，运行相同的路由协议，同时分配同一个自治系统编号。自治系统之间的链接使用外部路由协议，例如BGP协议。1BGP路由表信息法BGP是一种AS自治区域外部路由协议，主要负责本自治区域和外部的自治区域间的路由可达信息的交换。与其它路由协议一样，BGP维护路由表、发送路由更新信息且基于路由METRIC决定路由。BGP系统的主要功

28、能是交换其它BGP系统的网络可达信息，包括AS路径的列表信息，此信息可用于建立AS系统连接图，以消除路由环，及执行AS策略确定。每个BGP路由器维护到特定网络的所有可用路径构成的路由表，但是它并不清除路由表，它维持从对等路由器收到的路由信息直到收到增值INCREMENTAL更新。BGP设备在初始数据交换和增值更新后交换路由信息。当路由器第一次连接到网络时，BGP路由器交换它们的整个BGP路由表，类似的，当路由表改变时，路由器发送路由表中改变的部分。BGP路由器并不周期性发送路由更新，且BGP路由更新只包含到某网络的最佳路径。BGP用单一的路由METRIC决定到给定网络的最佳路径。这一METRI

29、C含有指定链路优先级的任意单元值，BGP的METRIC通常由网管赋给每条链路。赋给一条链路的值可以基于任意数目的尺度，包括途经的AS数目、稳定性、速率、延迟或代价等。因此通过BGP路由表我们可以收集到我们想要的数据。2TRACEROUTE方法TRACEROUTE方法不但可以用于IP级的INTERNET网络拓扑数据收集也可以用于AS级的INTERNET网络拓扑数据收集。收集的原理和方法是一样的，与IP级的最大不同是收集到的地址信息表示为AS号。而IP间的连接关系表示为AS间的连接关系。22INTERNET网络拓扑数据特征由于在INTERNET网络拓扑研究的早期缺乏真实的实验数据，所以对INTER

30、NET网络拓扑研究只能停留在经验假设的基础上，更不用说发现和研究INTERNET网络拓扑数据的特征了。近几年来INTERNET网络拓扑数据的收集工作进行得比较顺利，并已经收集到了大量的网络拓扑数据。经过研究者的不断分析和研究，已经在网络拓扑数据中发现了许多原来不为人所知的有趣规律和特征。而且，也在一定程度上去验证并部分否定了过去的经验假设。1999年，FALOUTSOS等人发现INTERNET网络拓扑中存在着幂率POWERLAW分布。幂率分布的发现将INTERNET网络拓扑特征发现带上了一个新的层次。幂率分布是复杂系统中“无尺度SCALEFREE”网络的一个重要特征。INTERNET网络拓扑中

31、幂率的发现，使其成为复杂系统中“无尺度”网络的一个实例，在INTERNET网络拓扑研究与系统学研究之间架起了一座桥梁。幂率的发现也使“无尺度”网络的一些重要特征纳入到INTERNET网络拓扑中来研究。INTERNET网络拓扑特征的研究在某种程度上说也是衡量和刻画INTERNET网络度量的提出和引入过程。为了更好的理解和计算INTERNET网络拓扑，一些新的度量被不断的发现和提出，并用数学的语言进行了描述。研究人员根据度量之在INTERNET网络拓扑所表现出来的值来对其特征进行描述。下面分别介绍几个重要的度量值。221出度与出度频率出度与出度频率是反映网络拓扑结构的最基本的度量。对于无向图，节点

32、出度一般定义为与该节点相接相邻的节点的数量。对于有向图，则节点出度定义为由该节点出发到与该节点直接相连的节点中的连接的数量。出度频率定义为出度为NUM（NUM表示0到N）的节点的数量。对出度和出度频率进行研究是INTERNET网络拓扑研究中很重要的特征发现方式。对出度以及出度频率的分布进行研究最主要的一个方向是研究INTERNET网络拓扑幂率分布。222成长性与优先附着1999年，美国圣玛丽亚大学UNIVERSITYOFNOTREDAME物理系自组织系统研究组的BARABDSI与ALBERT16在对无尺度网络进行研究时提出了幂律产生的两个系统根源成长性GROWTH和优先附着PREFERENTI

33、ALATTACHMENT。成长性是用来描述无尺度网络可以不断的扩张和增长的。优先附着描述了无尺度网络在成长过程中所遵循的规律。当新节点出现时，其连接建立的对象并非所有的节点都是平等的。比如在选择将网页连结到何处时，人们可以从数十亿个网站中进行选择。然而我们大部分人只熟悉整个万维网的一小部分，这一小部分中往往包含那些拥有较多连结的站点，因为这样的站点更容易为人所知。只要连结到这些站点，就等于造就或加强了对它们的偏好。在网络中节点的建立也有这一种特性。在图22中，模拟了INTERNET网络拓扑的成长性和优先连接两个特征，无尺度网络的节点从2个成长到11个。当新节点决定联结时，总是倾向于已经拥有较多

34、联结的节点相连接。图22成长性和优先连接223“小世界”特性所谓小世界现象，或称六度分离（SIXDEGREESOFSEPARATION），是社会网络（SOCIALNETWORKS）中的基本问题，即每个人只需要很少的中间人（平均6个）就可以和全世界的人建立起联系。在这一理论中,每个人可看作是图（GRAPH）的节点，并有大量路径连接着他们，相连接的节点表示互相认识的人。这是一个涉及社会学，数学和计算科学问题的多学科交叉问题。该问题源于社会心理学家STANLEYMILGRAM上世纪60年代作的实验追踪美国社交网络中的最短路径。他要求每个参与者寄信给一个住在波士顿附近的目标人物，规定每个参与者只能转发

35、给一个他们认识的人。MILGRAM发现完整的链平均长度为6个人。虽然MILGRAM的结果还很难说是定论，因为绝大部分的信件并没有送到最终的收信人手里。不过科学家最近发现，社会网络、互联网和基因网络都呈现小世界网络的特征。224网络恢复网络的鲁棒性是评价网络能力大小的一个重要的指标。对于INTERNET网络来说，网络的鲁棒接性尤其重要。因为我们希望INTERNET网络能在部分设备出现故障时仍然能够正常的工作。好的鲁棒性网络即使遭受病毒和黑客的恶意攻击仍然能够在不影响全网的情况下正常工作。网络恢复NETWORKRESILIENCE描述备用路径的存在性。将一个连通图划分为近似相等的两个连通图的最小割

36、集大小，反映拓扑图对于连接故障的鲁棒性。225其他度量值2002年TANGMUNARUNKIT等人在对层次模型与幂律模型进行比较的过程中引入了3个度量，这其中就包括网络恢复RESILIENCE，除此外还有1膨胀EXPANSION，描述扩散速度对每个节点计算其在有限跳内可达的节点数量，然后取平均值，再用节点总数来规格化。2扭曲DISTORTION，描述一个图像一棵树的程度对图G的一棵生成树T，G中相邻两点在T上距离的平均值就是DT值，这表示如果把路径限定在T上，G中相邻的两点需要走多少额外的跳数，图G的扭曲值D就是所有生成树的DT值中最小的。2003年，GKANTSIDIS等人采用谱过滤技术对A

37、S级拓扑邻接矩阵进行正规拉普拉斯谱分析，反映出拓扑结构中节点群及其等级的高低。23INTERNET网络拓扑数据结构INTERNET网络拓扑数据结构和INTERNET网络拓扑结构是一样的。而INTERNET网络的拓扑结构是指网络中各个站点相互连接的形式，在局域网中明确一点讲就是文件服务器、工作站和电缆等的连接形式。现在最主要的拓扑结构有总线型拓扑、星型拓扑、环型拓扑以及它们的混合型。顾名思义，总线型其实就是将文件服务器和工作站都连在称为总线的一条公共电缆上，且总线两端必须有终结器星型拓扑则是以一台设备作为中央连接点，各工作站都与它直接相连形成星型；而环型拓扑就是将所有站点彼此串行连接，像链子一样

38、构成一个环形回路；把这三种最基本的拓扑结构混合起来运用自然就是混合型了。最基本的网络拓扑结构有环形拓扑、星形拓扑、总线拓扑三个。目前网络中常见的拓扑结构有以下几种231总线拓扑结构（图23）是将网络中的所有设备通过相应的硬件接口直接连接到公共总线上，结点之间按广播方式通信，一个结点发出的信息，总线上的其它结点均可收听到。优点结构简单、布线容易、可靠性较高，易于扩充，是局域网常采用的拓扑结构。缺点所有的数据都需经过总线传送，总线成为整个网络的瓶颈；出现故障诊断较为困难。最著名的总线拓扑结构是以太网（ETHERNET）。232星型拓扑结构（图24）每个结点都由一条单独的通信线路与中心结点连结。优点

39、结构简单、容易实现、便于管理，连接点的故障容易监测和排除。缺点中心结点是全网络的可靠瓶颈，中心结点出现故障会导致网络的瘫痪。233环形拓扑结构（图25）各结点通过通信线路组成闭合回路，环中数据只能单向传输。优点结构简单，适合使用光纤，传输距离远，传输延迟确定。缺点环网中的每个结点均成为网络可靠性的瓶颈，任意结点出现故障都会造成网络瘫痪，另外故障诊断也较困难。最著名的环形拓扑结构网络是令牌环网（TOKENRING）。图23总线拓扑结构图24星型拓扑结构图图25环形拓扑结构图26树型拓扑结构图27网状拓扑结构图28混合型拓扑结构234树型拓扑结构（图26）是一种层次结构，结点按层次连结，信息交换主

40、要在上下结点之间进行，相邻结点或同层结点之间一般不进行数据交换。优点连结简单，维护方便，适用于汇集信息的应用要求。缺点资源共享能力较低，可靠性不高，任何一个工作站或链路的故障都会影响整个网络的运行。235网状拓扑结构（图27）又称作无规则结构，结点之间的联结是任意的，没有规律。优点系统可靠性高，比较容易扩展，目前广域网基本上采用网状拓扑结构。缺点结构复杂，每一结点都与多点进行连结，因此必须采用路由算法和流量控制方法。236混合型拓扑结构（图28）就是两种或两种以上的拓扑结构同时使用。这种网络拓扑结构在实际中使用最多。优点可以对网络的基本拓扑取长补短。缺点网络配置挂包那里难度大。3INTERNE

41、T网络拓扑数据类型分析与处理模型的建立由于网络拓扑数据收集的工具和方式不一样，所以收集到的网络拓扑数据集的结构也不一样，所以我们在分析研究网络拓扑数据之前，还要首先分析每一种数据集的存储结构。以下给出几种常见的网络拓扑数据集的分析。31ASLINKS数据集确切来说，这一种数据集并不是真正的原始网络拓扑数据，而是从ROUTEVIEWS快表中提取所有的AS连接，并通过每对连接对，确定两个AS之间的关系。数据文件的格式如下文件是线性单向的，第一行表示一对AS连接或者注解，如果表示是注解，那么行是以“”开始的。如果是AS连接对，那么格式如下和表示AS的编号，而表示两者之间的关系，它们之间有四种关系，分

42、别如下1表示AS1是AS2的一个顾客，即连接由AS2指向AS1；0表示AS1和AS2是平等的关系，AS1和AS2不处于相同的组织结构；1表示AS1是AS2的供应者，即连接由AS1指向AS2，与关系“1”相反；2表示AS1和AS2是平等的关系，不过这种平等是AS1和AS2处于同一个组织结构中。例如3300124911当然，如果有一对连接是由AS1指向AS2，关系说明为1；另一对连接由AS2指向AS1，关系说明为1。那么这两对AS连接对是相同的。例如3300124911和1249133001。因此在处理数据的时候，为了方便后续研究的使用，把所有为“1”的AS关系对转换成为“1”AS关系对。对于这一

43、种数据，我们并不用做太多的处理。但由于数据集中存在着大量重复的AS连接对或者表示相同的AS连接对，因些我们主要的工作就是把这些AS连接对找出来，并为每一对AS连接对加上一个标记，用于指示当前的AS连接对的个数，并保存到数据库中，方便查询和后续研究的使用。处理这一种数据集，我们首要做的是统计好数据集中所有的结节的数量（ASSNUM），所有的节点的度的数量（DEGREESNUM）和节点的平均度（AVERAGEDEGREES）是多少。他们之间的关系如下NUMADEGREESNUMREESAVERAGEDEGSS在此基础上还要统计好每一个AS出现的次数，在这里用ASNUM表示。研究和分析每一个AS的出

44、现频率，我们可以得知当前的AS在这个数据集中是否为核心AS；研究每一个AS的出度和入度数，我们可以得知当前的AS在网络中是处于信息发送中心还是信息的接收中心还是信息转发中心。如果当前AS的出度远远大于入度，那么当前的AS有可能是网络中信息发出比较集中的节点。而如果当前AS的入度远远大于出度，那么当前的AS有可能主要是接收来自网络中的信息的。而如果当前的AS的出度和入度相差不大，那么当前的AS的主要作用就有可能是用于信息的转发，当然也有可能是发送节点或者接收节点。对于这一点，我们还要做最后的研究来确定了。统计好当前数据集所有的关系为平等关系的AS对（EQUALNUM）有多少，还应该分别统计处于同

45、一组织结构的平等关系对的数量（SAMENUM）和不处于同一组织结构的平等关系对的数量（DIFFERENTNUM）。这三者之间的关系应该为MIFFERENTNUAMENUMQUALNUMDSE研究他们之间的比例我们可以得知，平等的AS关系对的分布情况。如果说同一组织结构的AS平等连接对所占的比例比较大，那么一方面可以反映同一组织结构的规模比较大，另一方面也可以看出同一组织结构内的AS连接比较密切。研究ASLINKS数据集，我们还可以分析出当前数据集内的局部的AS结构。例如假设中心AS为N1，局部层次设置为2，那么就可以把所有与N1直接相连的AS节点（节点集定义为NODESET1）和所有与节点集N

46、ODESET1中的节点直接相连的节点通过它们之间的关系，以拓扑结构方式展示出来。如图31所示图31局部AS结构其中中心AS用红点表示；黑点表示与红点直接相连，在图中黑点表示层次为1；蓝点与黑点直接相连而不能与红点直接相连，在图中蓝点表示层次为2。当然这是一种比较理想的局部拓扑图，还有可能是黑点与黑点之间也有连接，蓝点与蓝点之间也有连接。这样就能比较真实地发映局部的网络拓扑结构了。这种情况如图32所示图32局部AS结构所演示的层次都深，那么模拟出来的局部AS网络拓扑结构就越真实。AS之间的拓扑关系越清楚，对我们对现实中的网络拓扑结构进行调整和对研究出新型的拓扑结构协议都非常有帮助。32ITDK数

47、据集同样的，这种数据集也不是最原始的数据，而是经过收集工具简单处理的网络拓扑数据集，这种数据集由三个文件组成。“NODES”文件列出了在路由中存在的接口的集合；“LINKS”文件列了每一条连接通过的节点；“NODESAS”文件说明了每个节点的接口方式。还有一个“NODESGEO”文件用于说明每个AS的地理位置。各个文件的格式如下（1）“NODES”文件列出了在路由中存在的接口的集合。格式NODE在“NODES”文件中，每一行表示一个节点与其有接口的节点的集合。其中“NODE”只是一个标记，表示此行为一个节点记录；“”表示当前节点的编号；“”表示与当前节点有接口的IP地址。例如NODEN3338

48、247146619289660423332接口地址为“0000/8”形式的地址是无效的，它们是为了识别在路由路径中存在的独特的不作出应答的接口而人为生成的。由于这些地址是无效的，所以在处理的时候要把这些地址忽略掉。与当前的节点直接相连的接口的数量直接反映出当前节点的度是多少。分析对比节点的度的大小，有助于我们了解当前的数据集中核心的节点是那一些，在这里，我们定义度比较大的节点为核心节点。在本文中所分析的“NODES”文件中N234N241节点的度如表31所示表31节点的度节点N234N235N236N237N238N239N240N241度3543405548926041由表可以看出，如果当前

49、的数据集只有这几个节点的话（当然那是不可能的），那么节点N239就是这个数据集反映的网络拓扑的核心。（2）“LINKS”文件列出了每一条连接通过的所有的节点。要注意的是这些连接都是IP层连接，而不是物理连接或者图的边缘连接。如果所有的节点都连接到同一层开关，那么将超过两个节点可以共用同样的IP连接。格式LINKI1I2I3IM在“LINKS”文件中，每一行表示一条连接，同时给出连接通过的节点。其中“LINK”只是一个标记，表示此行为一条连接记录。如果知道是那个路由器接口连接到当前的连接，那么在此节点后面给出接口地址；如果不知道，那么就只说明节点。例如LINKL104N2424842117948158N18472117948157N5849773“LINKS”文件的数据量一般比较大，如果把所有的数据都存储都数据库中去，那是不太现实的，因为数据太过于庞大，就算利用数据库，后续的研究也会非常的烦锁。所以我们只要从中获取对我们后续的研究最有用的，最核心的信息就可以了。而其他的信息则暂不作处理。在本文中“LINKS”数据集文件的处理方式为提取每一条连接的源地址和目的地址，并统计每一条连接所经过的节点数，把这三项内容存储到数据库中。而为什么只提取这些信