1、毕业设计开题报告计算机科学与技术大规模网络拓扑数据处理技术研究一、选题的背景与意义INTEMET作为当今人类社会信息化的标志，其规模正以指数级的速度高度增长。这种增长不仅表现在了其节点和连接的数量的增长，还表现在了INLEMET的复杂性以及在现今社会中所发挥的作用，甚至其地理位置几乎遍布了世界的每一个角落。正因为INTEMET的重要性及复杂性，网络拓扑结构已经成为计算机研究领域的专家和学者研究的焦点。尽管互联网迅速增长，但是其拓扑结构的某些特点保持不变。分析和理解这些不变量可能有助于未来互联网研究和发展，如新的协议设计。1、项目背景网络拓扑结构的研究是一个新的领域。对于网络拓扑结构的研究，不太
2、可能直接从现实的拓扑结构入手，为了更好地理解和分析网络拓扑的特点，我们可以分析海量的网络拓扑数据，从中提取对我们有用的信息。然而一般来说收集到的网络拓扑数据存在着大量的冗余和大量对我们无用的信息，为了更加方便的研究网络拓扑结构，我们首先要对这些大量的网络拓扑数据进行处理。对大量的网络拓扑数据的处理关键关于数据的处理技术。我们从网络中收集来的数据集样式不是唯一的，如基于AS的数据集，基于路由结点的数据集等等。各种对于拓扑结构模拟的软件所需要的数据样式也是不一样的，因此对大量的网络拓扑数据的处理技术必须是高效的，实用的，能够处理各种不同类型的网络拓扑数据集，并能根据要求提取不同的有用的信息。2、项
3、目的意义网络拓扑结构的研究最重要的是首先对网络拓扑结构进行模拟，要模拟就必然要知道实际网络中的拓扑结构。目前，在权威的CAIDA上，针对不同研究有不同的数据集，每个数据集的数据量从几G到上百G不等，且每年都在不断增加。对于这样庞大的数据集的处理在科学研究过程中显得非常重要，急需好的处理方案。对数量的网络拓扑数据进行基处理，分析其中的结构，得知数据传送的源地址、目的地址的，所通过的路径，可以分析出具体的地理位置，对网络拓扑结构研究的便利，成本，效果有很大的帮助。二、研究的基本内容与拟解决的主要问题基本内容1首先对网络拓扑数据处理技术的相关资料进行阅读，收集各种不同类型的网络拓扑数据集。2分析每一
4、种类型的网络拓扑数据集的结构，并做详细的记录。3为每一种类型的网络拓扑数据集结构设计处理模型。4原始数据库的建立。5根据处理模型设计并实现相关的网络拓扑数据处理程序。解决的主要问题1掌握网络拓扑数据集处理技术。2网络拓扑数据集的收集和整理。3数据集结构的分析和研究。4处理模型的建立。5原始数据库的建立。6程序的编码实现。三、研究的方法与技术路线先对目前的网络拓扑数据处理的情况的资料进行收集，然后再进行了解和分析，熟悉各种对网络拓扑进行模拟的程序的使用，并分析其对所需输入数据的结构。记录和整理以上所得的结果，并以此为基础设计出程序的大体框架，最后根据程序的框架，编写程序的代码，完成编写后进行相关
5、的测试，然后分布。这里用MICROSOFTVISUALC平台环境下结合SQL数据库进行开发。数据集的收集数据集的预处理处理模型的建立数据库的建立程序的实现确立处理指标选择数据集设置处理指标处理结果流程图中，数据集的收集主要是从彩达网上下载，预处理是分析数据集的结构，并根据结构建立基于目的地址、从属关系、跳数等不同的处理模型。数据库也是基于目的地址、从属关系、跳数等分类建立起来的。四、研究的总体安排与进度20101220111开题阶段，熟悉课题，收集资料，2011220113理论研究阶段，搜集资料，文献综述，设计理论模型；2011420115结合理论模型实现具体方案，并予以验证。20116完成毕
6、业论文并参加答辩五、主要参考文献1NS仿真实验多媒体和无线网络通信电子工业出版社柯志亨等2网络技术实践教程电子工业出版社金光3THECOOPERATIVEASSOCIATIONFORINTERNETDATAANALYSISHTTP/WWWCAIDAORG/HOME/4MILLER,MH,POWELL,JI,SHARROW,SO,SCHULTZ,ARRAPIDDATACOLLECTION,ANALYSIS,ANDGRAPHICSFORFLOWMICROFLUOROMETRYINSTRUMENTATIONDIVISIONOFCOMPUTERRESEARCHANDTECHNOLOGY,NATIONA
7、LINSTITUTEOFHEALTH,BETHESDA,MARYLAND2009113711425AWMOORE,DZUEVINTERNETTRAFFICCLASSIFICATIONUSINGBAYESIANANALYSISTECHNIQUESINPROCOFTHEACMSIGMETRICSBANFF,20056MFALOUTSOS,PFALOUTSOS,ANDCFALOUTSOS,“ONPOWERLAWRELATIONSHIPSOFTHEINTERNETTOPOLOGY,”PROCOFACMSIGCOMM99,CAMBRIDGE,MA,AUG1999,PP2512627HCHANG,RGOV
8、INDAN,SJAMIN,SSHENKER,ANDWWILLINGER,“TOWARDSCAPTURINGREPRESENTATIVEASLEVELINTERNETTOPOLOGIES,”PROCOFACMSIGMETRICS2002,NEWYORK,NY,JUNE2002,PP2802818DVUKADINOVIC,PHUANG,ANDTERLEBACH,“ONTHESPECTRUMANDSTRUCTUREOFINTERNETTOPOLOGYGRAPHS,”INHUNGERETAL,EDS,INNOVATIVEINTERNETCOMPUTINGSYSTEMS,LNCS2346BERLINSP
9、RINGERVERLAG,2002,PP83969MMIHAIL,CGKANTSIDIS,ANDEZEGURA,“SPECTRALANALYSISOFINTERNETTOPOLOGIES,”PROCOFINFOCOM2003,SANFRANCISCO,CA,MAR2003,VOL1,PP36437410JCHEN,LTRAJKOVIC,“ANALYSISOFINTERNETTOPOLOGYDATA“,CIRCUITSANDSYSTEMS,MAY2004IV62932VOL4ISBN078037752411SHALABIANDDMCPHERSONINTERNETROUTINGARCHITECTU
10、RES,SECONDEDITIONCISCOPRESS,201WEST103RDSTREET,INDIANAPOLIS,IN46290,USA,2EDITION,2000ISBN157870233X12GUNNARCARLSSON,TOPOLOGYANDDATA,BULLETINNEWSERIESOFTHEAMERICANMATHEMATICALSOCIETY,VOLUME46,NUMBER2,APRIL2009,PAGES255308,ARTICLEELECTRONICALLYPUBLISHEDONJANUARY29,200913KCLAFFY,TMONK,“WHATSNEXTFORINTE
11、RNETDATAANALYSISSTATUSANDCHALLENGESFACINGTHECOMMUNITY“,PROCEEDINGSOFTHEIEEE,OCT1997,PAGES15631571毕业设计文献综述计算机科学与技术大规模网络拓扑数据处理技术研究摘要发现网络拓扑对分析路由协议和互联网的鲁棒性和弹性是很重要的。最近处理网络拓扑结构的研究结果，如POWERLAWS的发现和应用正规拉普拉斯网络拓扑数据分析，增加了更完整的数据集和更严格的解释。本文主要介绍网络拓扑数据的内容。关键词网络拓扑数据，分析，研究3、背景INTEMET网络拓扑研究也经历了发展的过程。最初的INTEMET网络拓扑研究由
12、于缺乏数据，只能进行经验假设，现在已经可以针对相对完整的数据进行统计分析，并可对各种假设进行验证。从1995年开始，大规模的INTERNET拓扑测量工作逐渐展开，到目前为止已经收集到了大量的拓扑数据。这些拓扑数据相对完整，为INTEMET网络拓扑研究者提供了有利的实验数据支持。早期对HTEMET网络拓扑的特征更是无从认识，现在一些研究成果已经把INTERNET网络与复杂系统特征研究结合起来。INTEMET网络拓扑的建模工作也取得了长足的进展，从相对简单的随即模型到复杂的幂率模型，其结果都越来越接近真实的INTEMET。对于节点间关系的理解更是有了质的突破，从原来对关系的一无所知到现在对关系进行
13、定义和区分。所有这些都说明了INTEMET网络拓扑研究在过去的一些年里取得的一些成果。即便如此，如果想准确回答INTEMET网络拓扑所提到的几个问题，仍然还有不小的差距，而且一些新的发现也对已有的成果提出了挑战。4、INTEMET网络拓扑数据研究分类网络拓扑研究是一项复杂的工作，其中包含很多的内容，甚至涉及多个领域。一般来说，我们可以将INTEMET网络拓扑研究内容归为下面四个部分1INTEMET网络拓扑数据获取如何获取一份完整而且准确的INTEMET网络拓扑数据是一项困难而复杂的工作。由于INTEMET庞大而且复杂，如果现有的技术条件下获取一份完整的拓扑数据几乎是不可能的。目前来说，虽然已经
14、提出了多种方法，但怎样获得一份更加完整的INTEMET网络拓扑数据仍然是研究领域中需要进一步解决的问题。2INTEMET网络拓扑特征发现INTEMET虽然是庞大而复杂的，但它自身仍然存在着某些规律和特征等待我们去探索。在过去的几年里，INTEMET网络拓扑特征发现一直是INTEMET网络拓扑研究领域中的热点问题，通过研究人员的不断努力，一些新奇的网络拓扑特征逐渐的探索出来。3INTEMET网络拓扑建模INTEMET网络拓扑建模是利用已经发现的拓扑特征把INTEMET描述和刻画出来。通过拓扑建模，我们也更直观的认识了INTERACT。4INTERNET网络内部关系分析当我们得到一幅INTEMET
15、网络拓扑图后，如何理解和认识图内节点关系也是目前INTEMET网络拓扑研究的热点问题。三、拓扑研究新问题INTEMET网络拓扑研究是一项非常有挑战性的工作，其原因主要是（1）TNTERNET规模巨大，结构复杂，要想获得完整的拓扑数据相当匿难。（2）INTEMET在本质上具有动态性，协议版本升级、设备更新、新主机接入等；同时INTEMET流量也具有突发性，不再像传统的电信业务流量那样符合POISSON模型。（3）INTEMET本身具有很强的异构性，其各个部分是在不同的时期由不同的部门或团体所建，具有分散式管理的特点，不同的LSP具有不同操作和安全策略，发现INTERNET拓扑需要跨越不同的网络和
16、不同的管理域，获得拓扑信息受到大量的接入限制。（4）零知识，即人们对INTEMET拓扑结构本身了解甚少，其本质的动态性也使人们不能作较多的前提假设，只能依靠探测手段。四、结论不管是数据的收集还是分析和特征的发现，都存在着一点的缺陷。这些缺陷将是下一步工作的努力方向。而在基于AS间关系的网络拓扑研究中，虽然将拓扑进行了分层，但是分层后，层次属性分析还不够，基于层次的实验工作相对较少。试图去发现基于层次的更多的INTEMET网络拓扑属性，是下一步努力和工作的目标和重点。在AS间关系的INTEMET网络拓扑可视化工具中，工具的可视化算法并不理想，缺乏足够的清晰和美观。在功能上也存在一定的欠缺。修改和
17、完善可视化算法和功能这项工作中是仍有许多工作要做。参考文献1NS仿真实验多媒体和无线网络通信电子工业出版社柯志亨等2网络技术实践教程电子工业出版社金光3THECOOPERATIVEASSOCIATIONFORINTERNETDATAANALYSISHTTP/WWWCAIDAORG/HOME/4MILLER,MH,POWELL,JI,SHARROW,SO,SCHULTZ,ARRAPIDDATACOLLECTION,ANALYSIS,ANDGRAPHICSFORFLOWMICROFLUOROMETRYINSTRUMENTATIONDIVISIONOFCOMPUTERRESEARCHANDTECHN
18、OLOGY,NATIONALINSTITUTEOFHEALTH,BETHESDA,MARYLAND2009113711425AWMOORE,DZUEVINTERNETTRAFFICCLASSIFICATIONUSINGBAYESIANANALYSISTECHNIQUESINPROCOFTHEACMSIGMETRICSBANFF,20056MFALOUTSOS,PFALOUTSOS,ANDCFALOUTSOS,“ONPOWERLAWRELATIONSHIPSOFTHEINTERNETTOPOLOGY,”PROCOFACMSIGCOMM99,CAMBRIDGE,MA,AUG1999,PP25126
19、27HCHANG,RGOVINDAN,SJAMIN,SSHENKER,ANDWWILLINGER,“TOWARDSCAPTURINGREPRESENTATIVEASLEVELINTERNETTOPOLOGIES,”PROCOFACMSIGMETRICS2002,NEWYORK,NY,JUNE2002,PP2802818DVUKADINOVIC,PHUANG,ANDTERLEBACH,“ONTHESPECTRUMANDSTRUCTUREOFINTERNETTOPOLOGYGRAPHS,”INHUNGERETAL,EDS,INNOVATIVEINTERNETCOMPUTINGSYSTEMS,LNC
20、S2346BERLINSPRINGERVERLAG,2002,PP83969MMIHAIL,CGKANTSIDIS,ANDEZEGURA,“SPECTRALANALYSISOFINTERNETTOPOLOGIES,”PROCOFINFOCOM2003,SANFRANCISCO,CA,MAR2003,VOL1,PP36437410JCHEN,LTRAJKOVIC,“ANALYSISOFINTERNETTOPOLOGYDATA“,CIRCUITSANDSYSTEMS,MAY2004IV62932VOL4ISBN078037752411SHALABIANDDMCPHERSONINTERNETROUT
21、INGARCHITECTURES,SECONDEDITIONCISCOPRESS,201WEST103RDSTREET,INDIANAPOLIS,IN46290,USA,2EDITION,2000ISBN157870233X12GUNNARCARLSSON,TOPOLOGYANDDATA,BULLETINNEWSERIESOFTHEAMERICANMATHEMATICALSOCIETY,VOLUME46,NUMBER2,APRIL2009,PAGES255308,ARTICLEELECTRONICALLYPUBLISHEDONJANUARY29,200913KCLAFFY,TMONK,“WHA
22、TSNEXTFORINTERNETDATAANALYSISSTATUSANDCHALLENGESFACINGTHECOMMUNITY“,PROCEEDINGSOFTHEIEEE,OCT1997,PAGES15631571本科毕业设计（20届）大规模网络拓扑数据处理技术研究摘要【摘要】INTERNET作为当今人类社会信息化的标志，其规模正以指数级的速度高速增长。这种增长不仅表现在了其节点和连接的数量的增长，还表现在了INTERNET的复杂性以及在现今社会中所发挥的作用，甚至其地理位置几乎遍布了世界的每一个角落。正因为INTEMET的重要性及复杂性，网络拓扑结构已经成为计算机研究领域的专家和学者研
23、究的焦点。尽管互联网迅速增长，但是其拓扑结构的某些特点保持不变。分析和理解这些不变量可能有助于未来互联网研究和发展，如新的协议设计。本文在对INTERNET网络拓扑研究大量的调研的基础上，将其分为四个部分INTERNET网络拓扑数据收集，INTERNET网络拓扑数据特征，INTERNETT网络拓扑数据处理分析和演示实现。针对每一部分都对该研究领域中的研究成果及方法给与了比较详尽的分析与讨论。【关键词】INTERNET网络拓扑，拓扑数据，拓扑特征，演示ABSTRACT【ABSTRACT】THEINTERNETHASEXPERIENCEDATREMENDOUSGROWTHINITSSIZEANDC
24、OMPLEXITYSINCEITSCOMMERCIALIZATIONTHISGROWTHINITSNOTONLYSHOWSTHENUMBEROFNODESANDLINKS,BUTALSOINTHEGROWTHOFTHECOMPLEXITYOFTHEPERFORMANCEINTERNETANDINOURSOCIETYTODAYTHEROLE,EVENITSLOCATIONISFOUNDALMOSTEVERYCORNEROFTHEWORLDBECAUSEOFTHEIMPORTANCEANDCOMPLEXITY,INTEMETTOPOLOGICALSTRUCTUREOFCOMPUTERRESEARC
25、HFIELDHASBECOMETHEFOCUSOFRESEARCHEXPERTSANDSCHOLARSALTHOUGHTHEINTERNETRAPIDGROWTH,BUTITSTOPOLOGICALSTRUCTURECHARACTERISTICSOFSOMEREMAINUNCHANGEDANALYZEANDUNDERSTANDTHESEINVARIANTSMAYHELPFUTUREINTERNETRESEARCHANDDEVELOPMENT,SUCHASTHENEWPROTOCOLDESIGNINTHISPAPER,WEMAKEALARGENUMBERSOFINVESTIGAFIONSANDC
26、LASSIFYTHEINTERNETTOPOLOGYRESEARCHINTOTHREETYPESINTERNETTOPOLOGYDATACOLLECTION，INTERNETTOPOLOGYCHARACTERISTICS，THETOPOLOGYOFTHENETWORKDATAPROCESSINGANALYSISANDDEMOREALIZEHERE，WEANALYZEANDDISCUSSTHEIRRESEARCHWAYSANDRESEARCHFMDINGSFOREACHTYPES【KEYWORDS】INTERNETTOPOLOGY,TOPOLOGYDATA,TOPOLOGYCHARACTERIS
27、TIC，DEMONSTRATE目录1绪论1311引言1312INTERNET网络拓扑数据研究的重要性1313INTERNET网络拓扑数据处理研究的内容1414INTERNET网络拓扑研究背景1515本论文的主要研究内容1516论文整体结构与章节安排162INTERNET网络拓扑数据研究综述与分析1621INTERNET网络拓扑数据获取16211IP级网络拓扑数据收集17212AS级网络拓扑数据获取2022INTERNET网络拓扑数据特征21221出度与出度频率21222成长性与优先附着22223“小世界”特性22224网络恢复23225其他度量值2323INTERNET网络拓扑数据结构2323
28、1总线拓扑结构（图23）24232星型拓扑结构（图24）24233环形拓扑结构（图25）24234树型拓扑结构（图26）25235网状拓扑结构（图27）25236混合型拓扑结构（图28）263INTERNET网络拓扑数据类型分析与处理模型的建立2631ASLINKS数据集2632ITDK数据集2933SKITTER_AS_LINKS数据集324INTERNET网络拓扑数据处理结果的演示3441ASLINKS数据集处理3442SKITTER_AS_LINKS数据集处理455总结和展望54参考文献55致谢错误未定义书签。1绪论11引言INTERNET作为当今人类社会信息化的标志，其规模正以指数级的
29、速度高度增长。这种增长不仅表现在了其节点和连接的数量的增长，还表现在了INTERNET的复杂性以及在现今社会中所发挥的作用，甚至其地理位置INTERNET几乎遍布了世界的每一个角落。图11给出了近些年来中国网民规模与普及率状况。从侧面说明了互联网的增长情况。正因为INTERNET的重要性及复杂性，其已经成为计算机研究领域的专家和学者研究的焦点。图11中国网民规模与普及率状况12INTERNET网络拓扑数据研究的重要性目前，INTERNET网络拓扑结构的研究已经吸引了越来越多的国内外计算机领域专家和学者的目光，并引起了他们了重视。而在最近几年里相关的研究已经取得了很大的进展。一般来说，INTER
30、NET网络拓扑结构研究的重要性主要体现在以下几个方面（1）对INTERNET网络拓扑的了解有助于设计更好的协议来控制网络。对网络进行有效的控制一直是网络领域中的一个重点，怎么样才能让INTERNET网络更好地运行，进行网络控制所要解决的一个很大的问题是怎么样才能让INTERNET网络按照我们所构想的方式运行。INTERNET网络拓扑的研究首先可以帮助我们了解INTERNET网络结构，进而发现INTERNET网络运行存在的缺陷，最后设计出新的INTERNET网络控制协议并去验证它。（2）对INTERNET网络拓扑的研究有利于更加准确的模拟INTERNET。由于各种因素的影响，目前直接在INTER
31、NET网络上研究是极其困难的，所以对一般的研究来说，我们都要建立INTERNET网络拓扑模型，借助模型来研究INTERNET网络拓扑结构。值得一说的是INTERNET网络拓扑研究领域中的一个重要的分支就是研究INTERNET网络拓扑的建立。3对INTERNET网络拓扑研究有助于维护网络安全。计算机病毒不但本身具有破坏性，更有害的是具有传染性，一旦病毒被复制或产生变种，其速度之快令人难以预防。而对INTERNET网络拓扑进行研究了解其中的结构对控制计算机病毒在网络上的蔓延有重要的作用。4对INTERNET网络拓扑特征的研究有利于设计有效的网络测量参数，更方便的来测量和刻画整个INTERNET。5
32、对INTERNET网络拓扑研究有助于维护国家安全性。网络安全是国家安全的一个重要的方面，因此有必要控制好整个网络的行为，而控制INTERNET网络行为首先要做的就是进行INTERNET网络拓扑的研究。13INTERNET网络拓扑数据处理研究的内容INTERNET网络拓扑研究是一项长期的复杂的工作，其中不但包含了很多的内容，而且甚至涉及多个领域。一般来说，我们可以将INTERNET网络拓扑数据研究的主要内容可以归为下面三个部分1INTERNET网络拓扑数据获取获取一份完整的全面的准确的INTERNET网络拓扑数据是一项非常困难和复杂的。由于INTERNET规模庞大而且结构复杂，就现有的技术来说，
33、获取一份完整的INTERNET网络拓扑数据几乎是不可能完成的任务。研究到今，专家和学者们已经提出并应用了许多方法，但怎样才能更快更全面地收集一份更加完整的INTERNET网络拓扑数据在研究领域中仍然是值得研究和解决的一个问题。2INTERNET网络拓扑数据特征发现INTERNET网络拓扑数据虽然是庞大而复杂的，但它自身仍然存在着某些规律和特征。在过去的几年里，INTERNET网络拓扑数据特征发现一直是研究人员热衷的工作，而经过研究人员几年的不断探索分析，逐渐的探索出一些新奇的特征。3INTERNET网络拓扑数据结构建模INTERNET网络拓扑数据在结构上与INTERNET网络拓扑结构是一样的，
34、所以分析网络拓扑结构能对我们进行网络拓扑数据处理的研究有重大意义。14INTERNET网络拓扑研究背景INTERNET网络拓扑研究经历了从经验假设到客观分析，从单纯的计算机网络拓扑结构研究到复杂系统特征研究的发展过程。最初的INTERNET网络拓扑研究由于缺乏真实的数据支持，只能进行经验假设，现在已经可以针对相对完整的数据进行统计分析，并可对各种假设进行验证。从1995年开始，大规模的INTERNET拓扑结构测量工作逐渐展开，到目前为止已经收集到了大量的网络拓扑数据。这些拓扑数据相对比较完整，为INTERNET网络拓扑研究者提供了大量的真实的实验数据支持。早期对INTERNET网络拓扑的特征更
35、是无从认识，现在一些研究成果已经把INTERNET网络与复杂系统特征研究结合起来。INTERNET网络拓扑的建模工作也取得了长足的进展，从相对简单的随即模型到复杂的幂率模型，其结果都越来越接近真实的INTERNET。对于节点间关系的理解更是有了质的突破，从原来对关系的一无所知到现在对关系进行定义和区分。所有这些都说明了INTERNET网络拓扑研究在过去的一些年里取得的一些成果。即便如此，如果想准确回答INTERNET网络拓扑所提到的几个问题，仍然还有一定的差距，而且一些新的发现也对已有的成果提出了挑战。15本论文的主要研究内容本文主要包含以下内容1对INTERNET网络拓扑数据获取、拓扑数据特
36、征、拓扑结构进行分析与讨论。详细考察了INTERNET网络拓扑在研究中的发展过程和国内外的当前研究现状。2简单介绍目前利用网络拓扑结构数据模拟网络结构的可视化工具。3针对每一种网络拓扑数据类型，作一个详细的分析，并建立相应的处理模型。4根据处理模型，开发一个简单的演示工具。16论文整体结构与章节安排第L章即本章分别介绍了INTERNET现状，INTERNET网络拓扑的研究意义、分类以及背景。第2章针介绍了INTERNET网络拓扑数据处理研究的内容，并分别进行比较详细的分析与讨论。第3章针对每一种网络拓扑数据类型，作一个详细的分析，并建立相应的处理模型。第4章根据处理模型，开发一个简单的演示工具
37、。第5章对全文进行了总结。分析作中的不足，并提出了将来要做的工作。2INTERNET网络拓扑数据研究综述与分析21INTERNET网络拓扑数据获取网络层的目的是实现两个端系统之间的数据透明传送，具体功能包括寻址和路由选择、连接的建立、保持和终止等。因此，INTERNET网络拓扑研究通常集中在网络层。在网络层上研究INTERNET网络拓扑，才能更加真实地反映和了解INTERNET网络的实际结构。IP级路由级和自治系统ASAUTONOMOUSSYSTEMS级是在网络层上的INTERNET网络拓扑研究的主要的两个方面。INTERNET网络拓扑数据的获取主要是指获取网络节点资源，以及节点间的连接关系。
38、IP级的网络拓扑节点资源主要是指路由器，即获取路由器资源以及路由器间的连接关系。AS级的网络拓扑数据的获取主要是指获取AS资源，以及AS间的连接关系。如图21中，A为IP级拓扑图，B为AS级拓扑图。图21IP级拓扑图和AS级拓扑图211IP级网络拓扑数据收集互联网主要的节点设备就是路由器，可以说是INTERNET的枢纽。路由器有两大典型功能，即数据通道功能和控制功能。数据通道功能包括转发决定、背板转发以及输出链路调度等，一般由特定的硬件来完成；控制功能一般用软件来实现，包括与相邻路由器之间的信息交换、系统配置、系统管理等。正是因为路由器在INTERNET中的重要性，在该层研究进行INTERNE
39、T网络拓扑和获取网络拓扑数据就变得非常的重要。而数据的收集主要有以下几种方法。1SNMP方法SNMP是一种网络设备间交换管理信息的应用层协议。SNMP主要由MIB管理信息库、SMI管理信息的结构和标识和SNMP简单网络管理协议组成。各个路由器代理所维护的MIB管理信息库中包含了网络拓扑的主要信息，如表21所示。由表可以看出，只要分析“与端口相连的下一跳路由器IP地址”、“目的IP地址”和“端口IP地址”这三项就可以基本确定路由器之间的连接信息，收集和分析这些信息，便可以得到相关的拓扑数据。SNMP还可以根据网络的状况自动更新，因此我们获得的数据都会是最新的。表21MIB信息变量名称接口索引值路
40、由类型子网掩码与端口相连的下一跳路由IP地址目的IP地址端口IP地址IP路由表IPROUTEIFINDEXIPROUTETYPEIPROUTEMASKIPROUTENEXTHOPIPROUTEDSETIP地址表IPADENTIFINDEXIPADENTNETMASKIPADENTADDR2TRACEROUTE方法TRACEROUTE是用来侦测主机到目的主机之间所经路由情况的重要工具，也是最便利的工具。前面说到，尽管PING工具也可以进行侦测，但是，因为IP头的限制，PING不能完全的记录下所经过的路由器。所以TRACEROUTE正好就填补了这个缺憾。TRACEROUTE的原理是非常非常的有意思
41、，它受到目的主机的IP后，首先给目的主机发送一个TTL1的UDP后面就知道UDP是什么了数据包，而经过的第一个路由器收到这个数据包以后，就自动把TTL减1，而TTL变为0以后，路由器就把这个包给抛弃了，并同时产生一个主机不可达的ICMP数据报给主机。主机收到这个数据报以后再发一个TTL2的UDP数据报给目的主机，然后刺激第二个路由器给主机发ICMP数据报。如此往复直到到达目的主机。这样，TRACEROUTE就得到了所有的路由器IP。避开了IP头只能记录有限路由IP的问题。3DNS方法DNS是域名系统DOMAINNAMESYSTEM的缩写，它是由解析器和域名服务器组成的。域名服务器是指保存有该网
42、络中所有主机的域名和对应IP地址，并具有将域名转换为IP地址功能的服务器。其中域名必须对应一个IP地址，而IP地址不一定有域名。域名系统采用类似目录树的等级结构。域名服务器为客户机/服务器模式中的服务器方，它主要有两种形式主服务器和转发服务器。将域名映射为IP地址的过程就称为“域名解析”。在INTERNET上域名与IP地址之间是一对一（或者多对一）的，域名虽然便于人们记忆，但机器之间只能互相认识IP地址，它们之间的转换工作称为域名解析，域名解析需要由专门的域名解析服务器来完成，DNS就是进行域名解析的服务器。DNS命名用于INTERNET等TCP/IP网络中，通过用户友好的名称查找计算机和服务
43、。当用户在应用程序中输入DNS名称时，DNS服务可以将此名称解析为与之相关的其他信息，如IP地址。DNS系统除了进行网络设备口地址到名字的映射外，还管理和维护一些其他的信息，如设备的硬件平台和操作系统等。这些信息对于我们收集INTERNET网络拓扑数据有着非常重要的作用，从这些信息中，我们还可以提取到相关的路由资源信息和连接信息。4PING方法PINGPACKETINTERNETGROPE，因特网包探索器，用于测试网络连接量的程序。PING发送一个ICMP回声清求消息给目的地并报告是否收到所希望的ICMP回声应答。它是用来检查网络是否通畅或者网络连接速度的命令。作为一个生活在网络上的管理员或者
44、黑客来说，PING命令是第一个必须掌握的DOS命令，它所利用的原理是这样的网络上的机器都有唯一确定的IP地址，我们给目标IP地址发送一个数据包，对方就要返回一个同样大小的数据包，根据返回的数据包我们可以确定目标主机的存在，可以初步判断目标主机的操作系统等。单独依靠PING命令是无法获得完整的INTERNET网络拓扑信息的，甚至连路由器间连接信息的获取都非常困难。一般来说，PING工具是要配合其他方法一起来收集INTERNET网络拓扑数据的。但是，PING方法与TRACEROUTE一样存在着类似的缺陷。而且由于广播PING操作会产生很多的数据包，因此对网络带宽会造成一定的压力。以上是获取IP级的
45、INTERNET网络拓扑数据主要的几种方法。但在实际的数据获取中，由于各种方法都存在着一些缺陷和困难，因此通常来说都是使用几种方法共同来完成数据的收集工作的。在CORNEU大学的OCTOPUS项目针对SNMP、PING、DNS和TRACERONTE分别设计了域内的网络拓扑数据获取算法，并进行了比较，比较结果如表22所示。而且还针对INTERNET网络拓扑数据收集设计并使用了TRACEROUTE的算法，并说明了使用SNMP、PING和DNS一般只适用于一个域内路由拓扑数据的发现和获取，对于大规模的INTERNET网络拓扑数据收集并不合适。在INTERNET网络拓扑数据收集中，主要使用TRAEER
46、OUTE的方法，但是很多研究者为了更好更完整的获取INTERNET网络拓扑数据通常采用多种方法混合的方式。即便如此，由于INTERNET规模庞大，结构复杂而且设备数量巨大，想要获取更加完整的IP级INTERNET网络拓扑数据仍然需要解决许多难以克服的困难。表22获取算法的结果比较CUCSNETWORKSPEEDOVERHEADCOMPLETENESSACCURACYSNMPDNSZONETRANSFER/BROADCASTPINGTIMEMINUTES11148PINGS51195TRACES00NORMALIZEDOVERHEAD51195HOSTS48299485100POUTERS510
47、05100SUBNETS7100686100100DNSZONETRANSFERTRACEROUTEPROBINTRACEROUTE1285884061L48033617521249480993176551005100710071009999CORNELLNETWORKSPEEDOVERHEADCOMPLETENESSACCURACYSNMPDNSZONETRANSFER/BROADCASTPINGDNSZONETRANSFERTRACEROUTEPROBINTRACEROUTETIMEMINUTES19328801080PINGS139102048532TRACES073672735NORM
48、ALIZEDOVERHEAD1394298720702HOSTS60281007367100273493ROUTERS1399010015510014493SUBNETS9315866221005121001009090212AS级网络拓扑数据获取一个自治系统就是处于一个管理机构控制之下的路由器和网络群组。它可以是一个路由器直接连接到一个LAN上，同时也连到INTERNET上；它可以是一个由企业骨干网互连的多个局域网。在一个自治系统中的所有路由器必须相互连接，运行相同的路由协议，同时分配同一个自治系统编号。自治系统之间的链接使用外部路由协议，例如BGP协议。1BGP路由表信息法BGP是一种AS
49、自治区域外部路由协议，主要负责本自治区域和外部的自治区域间的路由可达信息的交换。与其它路由协议一样，BGP维护路由表、发送路由更新信息且基于路由METRIC决定路由。BGP系统的主要功能是交换其它BGP系统的网络可达信息，包括AS路径的列表信息，此信息可用于建立AS系统连接图，以消除路由环，及执行AS策略确定。每个BGP路由器维护到特定网络的所有可用路径构成的路由表，但是它并不清除路由表，它维持从对等路由器收到的路由信息直到收到增值INCREMENTAL更新。BGP设备在初始数据交换和增值更新后交换路由信息。当路由器第一次连接到网络时，BGP路由器交换它们的整个BGP路由表，类似的，当路由表改变时，路由器发送路由表中改变的部分。BGP路由器并不周期性发送路由更新，且BGP路由更新只包含到某网络的最佳路径。BGP用单一的路由METRIC决定到给定网络的最佳路径。这一METRIC含有指定链路优先级的任意单元值，BGP的METRIC通常由网管赋给每条链路。赋给一条链路的值可以基于任意数目的尺度，包括途经的AS数目、稳定性、速率、延迟或代价等。因此通过BGP路由表我们可以收集到我们想要的数据。2TRACEROUTE方法TRACEROUTE方法不但可以用于IP级的INTERNET网络拓扑
