[硕士论文精品]internet路由级宏拓扑结构的tl模型

东北大学博士学位论文摘要INTEMET路由级宏拓扑结构的TL模型摘要INTEMET作为一个典型的复杂网络实例，对其宏观拓扑结构的特征分析及建模研究是目前研究的热点问题，受到学术界广泛关注。近年来人们在该领域的研究取得了长足的进展，尤其是在INTCRNET拓扑结构的分析中发现了幂律分布规律之后，提出了许多遵循幂律特征的拓扑生成算法以及拓扑模型，完成了从早期纯粹的经验假设到客观数据分析，从单纯的计算机网络研究到复杂系统特征化研究的建模过程的飞跃。但这些提出的模型大多为自治系统层面AUTONOMOUSSYSTEM,AS1EVEL的INTEMET拓扑模型，而在相对更细粒度的，更能表现INTEMET本质特征的路由器层面ROUTERLEVELINTEMET拓扑建模，由于规模巨大，以及获取完整的路由级拓扑方面的困难，目前研究还较少。揭示路由级INTEMET宏观拓扑结构的特征规律并建模，是帮助人们用其来对INTEMET进行分析、预报、决策或控制的需要，也是进行INTEMET相关的研究的基础，因此必然具有重要的意义。INTERACT拓扑研究与复杂网络学术界将INTEMET拓扑建模研究的内容大致归结为三个问题1如何获得一份完整而准确的INTERNET拓扑数据；2如何对INTERNET网络拓扑特征进行分析并建立模型；3如何使用模型构造一幅类似于INTEMET的拓扑图。这三个问题分别对应于三个研究方向，即拓扑结构测量、拓扑特征发现与建模以及可视化拓扑生成器开发。其中拓扑特征发现与建模是重点，拓扑特征发现指针对INTERACT测量拓扑结构的特征分析与特征参量提取，建立模型指根据特征参量建立拓扑模型，即本文提出的TL模型，这是本文研究的核心内容；拓扑结构测量作为拓扑特征分析与建模的基础与前提，也是本文中比较重要的部分；而拓扑结构的可视化问题由于涉及范围较广，可单独做为研究课题，因此不在本文中做为重点研究内容。本文首先针对分布在世界范围内的21个CAIDA监测点通过主动探测方法得到的路由级INTERNET拓扑测量结果，分别进行同名M解析与单点测量导致的采样偏见问题分析。在使用CAIDAIFFMDER同名口测量结果集对多组INTEMET测量数据解析时，发现每组中合并的路由数占总路由数的308，边数则从7QO不等。合并路由数增长比较平缓，说明测量结果集数量庞大，基本上已经完全覆盖了IFFMDER提供了同名解析空间。在单点测量问题分析中发现，随着测量点数的增加，新测量到的路由增量呈东北大学博士学位论文摘要Y88782018993INX的对数曲线分布形式。进一步分析表明，以目前CAIDA监测点的分布情况，只有当测量点数达到至少107个时才可能完全解决采样偏见问题，即没有路由器在测量中遗失。而本文测量结果集中CAIDA监测点数为21，因此需要在未来工作中对拓扑测量问题做进一步研究。其次，本文对INTERNET拓扑结构特征进行了不同层面的分析与研究。首先论述了INTEMET测量拓扑的幂律分布特征，包括FREQUENCYDEGREE幂律分布、DEGREERANK幂律分布与CCDFDDEGREE幂律分布等，发现INTERNET测量拓扑具有非常明显的FREQUENCYDEGREE幂律分布与DEGREERANK幂律分布规律。其中FREQUENCYDEGREE幂律分布符合幂律指数为21406的分布规律，而DEGREERANK幂律分布则分为两部分，主体节点服从幂律指数为O84639的分布，而度值最大的部分节点却符合幂律指数为029981的分布规律。在CCDFD一DEGREE幂律分布研究中发现，WEIBULL分布要比幂律分布拟合效果更好，也就是说，对于本文INTEMET拓扑来说，其节点度的CCDF不一定符合幂律分布。其次研究了INTEMET平均度值分布情况，并统计得出叶子路由在INTERNET测量路由总数所占比重平稳地保持在17附近的结论，说明INTEMET拓扑结构中，叶子路由的分布具有一定规律性；之后研究了INTEMET拓扑结构的谱密度分布与无符号拉普拉斯谱SLS分布结果，通过对拓扑结构各异的五种采样拓扑图，分别进行谱密度特征值分布分析，发现五组分析结果表现出高度的一致性，证明了INTERNET拓扑结构的自相似性。而通过四组3000点采样拓扑进行SLS分布分析，发现尽管四组3000点采样路由与连接互不相同，但SLS谱分布却非常相似，四组采样拓扑在特征值21处重数均较高，重数次高的特征值都群聚在旯2处。在特征值从2103变化过程中表现出较明显的幂律分布特性，其幂指数值保持在32813至38013之间，特征指数接近。这同样从另一个角度证明了INTEMET拓扑结构的自相似性。之后，本文根据INTEMET拓扑特征分析结果特征参量提出了一个基于三层THREELEVEL路由节点的TL模型。针对部分源于INTEMET拓扑统计分析的模型特征参数，进行了以无符号拉普拉斯谱密度SLS分布结果的为校验值评估函数的遗传优化。对优化后模型，本文从定性分析、定量分析与可视化结果的直观视觉角度予以了分析与评价。定性分析结果表明，TL模型兼具纯静态与纯动态模型的优点，即避免了纯静态模型下过多的人为干预与控制，也避免部分纯动态模型不能产生叶子节点的问题。在定量分析III东北大学博士学位论文摘要部分，对两份3000节点的TL生成拓扑分别进行了幂律分布分析、谱密度分布分析及规格化拉普拉斯谱NLS分析，分析结果表明，TL生成拓扑表现了INTERACT拓扑特征，TL模型可接受。本文最后给出了TL模型的生成算法。关键词INTEMET拓扑特征分析拓扑建模同名M解析采样偏见幂律分布谱密度无符号拉普拉斯谱SLSIV东北大学博士学位论文ABSTRACTATLMODELFORROUTERQEVELINTERNETMACROSCOPICTOPOLOGYABSTRACTINTEMCTISACLASSICALH皓TANCEOFCOMPLEXNETWORKANDTHERESEAREHANDMODELINGONITSTOPOLOGYHASBECOMEAHOTTOPICALPRESENTRECENTLY,RESEARCHESINTHISFIELDHAVEACHIEVEDGREATDEVELOPMENTSESPECIALLYAFICRTHEPRINCIPLEOFPOWERLAWDISTRIBUTIONHASBEENFOUNDINTHEINTERNETMACROSCOPICTOPOLOGY,QUITEAFEWTOPOLOGYMODELSWEREPUTFORWARDINTHESYMBOLOFASPANFROMTHEONLYEXPERIMENTALASSUMPTIONINEARLYTIMESTOOBJECTIVEDATAANALYSISNOWADAYS，FROMTHESIMPLEEOMUTERNETWORKSRESEALEHTOMSEALCHESBASEDONCOMPLEXNETWORKHOWEVER,MOSTOFTHEMODELSMENTIONEDABOVEARERESTRICTEDINTOTHEAUTONOMOUSSYSTEMASLEVELTOPOLOGYOFINTEMET，BUTNOTTHEROUTERLEVELTOPOLOGYOFINTEMETWHICHISCOMARETIVELYINFINERPARTICLESIZETHEPRINCIPLEOFRESEARCHANDMODELINGONMUTERLEVELINTEMETTOPOLOGYWASOFGREATSIGNIFICANCEFORITSHELPNOTONLYINANALYSIS，FORECAST,DECISIONANDCONTROLOFINTERNET,BUTINTHEINTERNETRELATIVERESEARCHFIELDSMODELINGONINTERNETTOPOLOGYCOULDBEDEVIDEDINTOTHREEQUESTIOM1HOWTOACQUIREACOMPLETEANDEXACTSAMPLEOFINTEMETTOPOLOGY2HOWTOANALYSIZETHETOPOLOGYANDCONSTRUCTTHEMODEL3HOWTOVISIUALIZETHEMODELINTOATOPOLOGYGRAPHLIKETHEREALINTEMETTHETHREEQUESTIONSAREACTUALLYTHREERESEARCHFIELDSWHICHALETOPOLOGYMEASUREMENT,TOPOLOGYCH部嗡CTERDISCOVERYANDTOPOLOGYMODELING,TOGETHERWITHTOPOLOGYVISIUALIZATIOMTOPOLOGYCHA“KTCRDISCOVERYANDTOPOLOGYMOILINGARETHEMOSTIMPORTANTPARTINTHISDISSERTATION,ANDTHEFOUNDATIONOFTOPOLOGYCBA糟CERDISCOVERYANDTOPOLOGYMODELINGTOPOLOGYMEASTTRCMENTISALSOANIMPORTANTPARTTHETHIRDONE，HOWEVER,ISNOTREGARDEDASKEYSECTIONINTHISDISSERTATIONSINCEITSSUCHACOMPLEXSUBJECTASTOBEATOTALLYSINGLERESEARCHSUBJECTINTHISDISSERTATION,THEINTERNETTOPOLOGYMEASURINGRESULTSBY21CAIDAMOMTORSAROUNDTHEWORLDWEREFIRSTLYPROCESSEDBYIPALI鹊RESOLUTIONANDSAMPLINGBIASRESOLUTIONHIPALIASRESOLUTION,WEFOUNDTHATTHENUMBEROFUNIONEDROUTERSINALL21GROUPSOFMEASURINGTOPOLOGIESREMAINEDTOBE398AGAINSTTHENUMBEROFTOTALROUTERS，WHERASLINKSV东北大学博士学位论文ABSTRACTREMAINSTOBEBETWEEN7AND30111EGENTLEIMPROVEMENTOFUNIONEDROUTESILLUSTRATEDTHATTHEMEASURINGTOPOLOGYSAMPLESWE犯SUFFICIENTLYCOVEREDANDPROCESSEDBYTHEIPALIASRESOLUTIONDATASETINSAMPLINGBIASRESOLUTION,THEINCREMENTNUMBEROFTHENEWLYFOUNDLITERSAGREEDWITHALOGFUNCTIONY88782018993INX，ANDFTLRTHERRESEARCHSHOWEDTHATTHEREWOULDBEATLEAST107CAIDAMONITORSFORACOMPLETEMEASURINGOFROUTERLEVELINTERNETTOPOLOGYHOWEVER,THENUMBEROFCAIDAMONITORSINTHISDISSERTATIONISTWENTYONE，MOREWORKWOULDHAVETOBEDONEINTHERESEARCHFIELDOFINTEMETTOPOLOGYMEASURINGINFUTURESECONDLY,CHARACTEROFINTEMETTOPOLOGYWASANALYSIZEDINTHREEWAYSONEWAYISPOWERLAWDISTRIBUTIONANALYSIS，INCLUDINGFREQUENCYDEGREEPOWERLAWDISTRIBUTION,DEGREERANKPOWERLAWDISTRIBUTIONANDCCDFD一DEGREEPOWERLAWDISTRIBUTIONRESULTSSHOWEDTHATTHEREWASOBVIOUSPRINCIPLEOFPOWERLAWDISTRIBUTIONININTEMETTOPOLOGY,ANDTHEFREQUENCYDEGREEPOWERLAWDISTRIBUTIONHADAPOWERLAWEXPONENTOF21406ANDINTHEANALYSISRESULTOFDEGREERANKPOWERLAWDISTRIBUTION，THENODESWEREDEVIDEDINTOTWOPARTS，ONEPARTAGREEDWITHPOWERLAWDISTRIBUTIONWITHANEXPONENTOFO84639THEOTHERPARTWHICHHASVERYLARGEDEGREESAGREEDWITH029981INCCDFD一DEGREEPOWERLAWDISTRIBUTIONANALYSIS，WEFOUNDTHATWEIBULLDISTRIBMIONFUNCTIONWASBEAERTHANPOWERLAWDISTRIBUTIONFUNCTIONMEANINGTHATINTERACTTOPOLOGYMIGHTPROBABLYNOTAGREEWITHTHEPRINCIPLEOFPOWERLAWDISTRIBUTIONONCCDETHESECONDWAYFORCHARACTERANALYSISOFINTEMETTOPOLOGYISTHEANALYSISOFTHEAVERAGEDEGREEOFINTERACTTOPOLOGYANDTHEPERCENTAGEOFLEAFMUTERINTHETOPOLOGYRESULTSSHOWEDTHATTHEPERCENTAGEOFLEAFNODESREMAINSTOBEAROUND17INALL21GROUPSOFMEASURINGTOPOLOGYTHELASTWAYFORCHARACTERANALYSISISTHEANALYSISOFSPECTNMADENSITYANDSLSSIGNLESSLAPLACIANSPECTRAWEFOUNDINEXPERIMENTSTHATFIVEANALYSISRESULTSOFSPECTRUMDENSITYONFIVESAMPLINGTOPOLOGIESSHOWEDHIGHLYSIMILARI够PROVINGTHATINTERACTISASYSTEMOFSELFSIMILARITYANDANALYSISOFSLSONFOURGROUPSOFSAMPLINGTOPOLOGYWITH3000NODESSHOWEDTHATSLSDISTRIBUTIONRESULTSWEVERYMUCHSIMILARWITHEACHOTHERTHOUGHTHETOPOLOGYSAMPLESWEREQUITEDIFFERENTALLFOURANALYSISRESULTSHADHIGHTUPLESATALANDSECONDHIGHTUPLESAT22BESIDESPRINCIPLEOFVI东北大学博士学位论文ABSTRACTTHEPOWERLAWDISTRIBUTIONWASOBSERVEDFROMSLSANALYSISWHENEIGENVALUEINSLSRANGEDFROM2TOLOJPROVMGINANOTHERASPTCTTHATINTEMCTTOPOLOGYHADPROPERTYOFSELFSIMILARITYTHENAMODELNAMED髂TLTHREELEVELMODELINTHISDISERTATIONWASPUTFORWARDBYTHERESULTSOFANALYSISOFINTONERMEASURINGTOPOLOGYANDGENETICOPTIMIZAFIONSWEREEXERTEDOLLSONDEOFPARAMETERSOFTHETLMODCLFINALLY,ABAPPRAISALONTLMODELWASPERFORMEDFROMQUALITATIVEANDQUANTITATIVEPOINTOFVIEWTHEQUALITATIVEANALYSISSHOWEDTHATTLMODELHADMERITSOFBOTHSTATICMODELANDDYNAMICMODELSINCEITCOULDPRODUCEDYNAMICNODESANDLINKSINTOGROWINGTOPOLOGY鸫WELLASSTATICLYADDLEAFNODESINTOTHETOPOLOGYINTHEQUANTITATIVEANALYSIS，WEMADEUSEOFBOTHSPECCLLUINDENSITYANDNORMALIZEDLAPLACIANSPECTRANLSANALYSISONTWOGROWING幻POLOGYWITH3000NODES，ANDFOUNDTHATTLMODELISVALUABLEINPRODUCINGTOPOLOGYWITHHIGHSIMILARITYOFREALINTEMETTOPOLOGYANALGORITHMFORPRODUCINGINTERNETTOPOLOGYBASEDONTLMODELWASPUTFORWARDINTHEENDOFTHISDISSERTATIONKEYWORDSINTEMETTOPOLOGYANALYSIS，TOPOLOGYMODELING，IPALIASREL砸。玑SAMPLINGBIAS。POWERLAWDISTRIBUTION,SPCCTL“LLMDENSITY,SLS独创性声明本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚的谢意。学位论文作者签名签字日期匆P77厂学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。如作者和导师同意网上交流，请在下方签名；否则学位论文作签字导师签名签字日期哆7碜砂名期加戤期东北大学博士学位论文第一章绪论第一章绪论11INTERNET宏拓扑建模概述111INTEMET研究现状INMET是一个人工的而且数字的复杂系统。从研究的角度看，相对于经济系统或生态系统，INTEMET中的统计数据的质量要高得多。我们可以非常方便地从收集数据包或分析日志文件等中获得系统准确的运行记录。然而把INTEMET看作一个计算机网络，甚至是一群相互连结的计算机网络都是不全面的。计算机网络只是简单的传载信息的媒体，而INTERACT的优越性和实用性则在于信息本身。INTERNE不仅是一个计算机网络，更重要的是它是一个庞大的、实用的、可享受的信息源；同样也可以把INTEMET当作一个面向芸芸众生的社会来理解。世界各地上亿的人可以用INTERNET通信和共享信息源，可以送出或接受电子邮件通信；可以与别人建立联系并互相索取信息；可以在网上发布公告，宣传你的信息；可以参加各种专题小组讨论；可以免费享用大量的信息源和软件资源。因此，INTEMET远非一个计算机网络或者一种信息服务所能比拟。HNCMCT已经证明，当人们能自由、方便地通信时，他们将变得社会化，变得无私。目前，INTERNET的规模正以指数级增长，文献1】的研究表明，INTCL删【2L的节点数大约每两年翻一番。各国在注重发展信息产业的同时，不断地完善INTCRNCT基础设施的建设，网络带宽不断增加，服务质量不断提高，收费价格不断降低。INTERACT所提供的服务种类多样、方便快捷、安全可靠，世界上使用INTEMET的人数不断增加。INTERNET已经成为人类生活不可分割的一部分。对INTEMET的研究自INTEMET的诞生开始【31145，一直是层出不穷，经久不衰。在早期，人们更多关注的是INTERNCT的体系结构、网络协议嘲，计算机互联以及INTERNET所提供的服务等方面的研究。随着信息技术的飞速发展和人类对INTERNET的依赖程度不断提高，人们开始在INTEMET所提供服务的安全性、QOS、TCP流量分析【871、拥塞处理、路由算法以及拓扑建模【7】【1叫【1叫【1071N3】【114】【125】【126】【133】【1蚓F135】【13司等方面开始了新的探索和研究，并取得了相应的研究成果。特别是近几十年来人们在复杂性科学和复杂网络等领域取得的研究成果，使国内外的研究者认识到INTEMET也是复杂网络之一，由此人们开始1东北大学博士学位论文第一章绪论了从复杂性和复杂网络的角度对INTEMET的研究。目前，对INTEMET的理论研究主要集中在拓扑建模7】【8】【38L【102】【104L【114】、QOS、流量分析、路由算法、拓扑演化【581等热点问题上。哈尔滨工业大学的张宇博士等对INTEMET拓扑建模【1刀问题进行了比较系统的研究，提出了目前对INTEMET研究的一些比较新颖的观点；复旦大学的刘岩等人对INTEMET上TCP流自相似性与网络性能关系【9】进行了较深入的研究，使人们充分认识到了TCP流的复杂性；清华大学的周晋博士设计了基于INTEMET小世界效应的无组织P2P系统的路由算澍”8】，该方法充分考虑了INTEMET所具有的小世界效应；GEORGOSSIGANOS等人对INTEMET的演化【”研问题进行了研究，尤其是对INTEMET路由节点变化的研究，使人们深入地认识到了INTEMET的变化；当然还有相当多的研究者，从不同的角度开展了对INTEMET的研究”401川】【142】【143】，如对INTEMET的鲁棒性和脆弱性的研究，对INTEMET分割度的研究，对INTEMET提供的服务的QOS的研究等等。112INTEMET拓扑建模的研究现状INTEMET作为当今人类社会信息化的标志，其规模正以指数速度高速增长。与其原型ARPANET相比，如今的INTEMET已经大相径庭，由于其具有高度的复杂性，因此可以将其视为一个由计算机构成的“生态系统”。虽然人类亲手建造了这个“生态系统”，但由于它的复杂多变，没有人能说出它看上去到底是个什么样子，运作得如何INTEMET拓扑建模研究就是探求在这个看似混乱的网络之中蕴含着哪些还不为我们所知的规斟埘。发现INTEMET拓扑的内在机制是认识LNTERNET的必然过程，是在更高层次上开发利用INTEMET的基础。然而，INTEMET与生俱来的异构性、动态性、发展的非集中性以及如今庞大的规模都给拓扑建模带来巨大挑战【1441。但同时，INTEMET拓扑结构是INTEMET这个自组织系统的“骨骼”，它与流量、协议在一起，决定了INTEMET本质特征。对INTEMET拓扑结构进行建模，即是刻画INTERACT在宏观上的特征，反映INTERNET的总体趋势的需要；也是作为一种工具，人们可用其来对INTEMET进行分析、预报、决策或控制的需要。因此具有重大意义。INTEMET拓扑建模是一项复杂的工作，涉及网络测量、图论、算法设计、统计学、数据挖掘、可视化以及数学建模等多个研究领域N71。正是由于其复杂性及高难度，吸引了大量专家在此领域展开研究。至今为止，INTEMET拓扑研究经历了从经验假设到客观分析，从单纯的计算机网络研究到复杂系统特征化研究的过程，大体上可按时间顺序分2东北大学博士学位论文第一章绪论为三代【1711041第一代为20世纪80年代的随机图产生器。在研究早期，由于缺乏真实测量数据支持，拓扑模型都是研究人员基于经验假设建立的。最早的INTERNET拓扑模型是1988年WAXMAN提出的WAXMAN模型阎。这是一种随机模型，沿用了很多年，直到90年代第二代INWMET拓扑模型出现。第二代为20世纪90年代的结构产生器，如啊ERS等级模型1051与TRANSITSTUB模型006是明显的基于层次结构设计思想的两类拓扑生成器；1996年，DOAR提出了TIERS模型，该模型刻画了INWNMCT所具有的层次特征。1997年，ZEGURA等AT1061提出了另一种层次模型胁NSITSTUB模型。此时，从1995年开始的大规模INTEMET拓扑测量工作已经逐步展开，采集到了大量拓扑数据。这些数据对科研机构都是免费开放的，极大地推动了拓扑研究的发展。INTCRNCT拓扑研究也进入了一个成果不断累加的阶段，发现多于改进，新旧成果共同描绘了INTERNET拓扑图剥171。第三代始于1999年FALOUTSOS等人发现INTERNET拓扑结构中存在幂律PO、砌。LAW口31，从而产生基于网络节点度的拓扑模型与拓扑产生器。幂律的发现将INTERNET拓扑与一些生物学、社会学中的复杂网络联系起来，使其成为“无尺度SCALEFREE”网络的一个实例，在INTCMET拓扑研究与系统学研究之间架起了一座桥梁【109。2000年以来，研究人员开发了许多遵循幂律的拓扑生成算法以及拓扑模型，如MEDINA等人使用WAXMAN概率与线性优先结合的方法研究的BRITE模型【10_7】、WINIEK等人根据非线性优先原则研究的LNET模型【1171、以及AB模型1131、GLP模型1141、PFP模型133】【L蚓、DP模型1翊、TANO模型125】【1261与MLW模型1蚓等。这些拓扑生成算法及拓扑产生器为INTERNET模拟提供了有利的支持。不过，新的发现墙1【211也对现有成果提出了挑战“71104IINTEMET拓扑建模至今仍然是一个开放性问题，在计算机网络研究中占有重要地位。本文也将就INTERNET拓扑建模的问题展开研究。113拓扑建模的层次INTEMET拓扑建模可以分为自治系统层面AUTONOMOUSSYSTEM,AS1EVEL或路由器层面ROUTERLEVELL拘拓扑建模】。【定义11】路由级INTERNET拓扑建模在路由器级INTEM或拓扑中，节点为路由器，边为路由器之间的物理连接如双绞线、光纤等；路由级INTEMET拓扑建模指针对路由3东北大学博士学位论文第一章绪论级H缱CMET的拓扑结构进行建模。【定义12】AS级INTEMET拓扑建模在AS层面的HITEMA拓扑中，每个AS也称为域，DOMAIN是节点，它是由单一行政部门所管理的子网络，可由高达数以百计的路由器组成。两个域边界路由器间的一个或多个连接作为一条边。与路由级HTEMA拓扑建模相比，AS级HTEMET拓扑建模是相对更粗粒度的拓扑建模。INTEMET复杂性直接导致其拓扑结构的复杂难控，尤其是在路由层面，面对数以百万、千万计的HTERNET路由器，摆在面前的首要难题就是如何从HTERNM中将它们测量出来。鉴于路由层面的路由测量与拓扑描述难度较大，因此大量研究集中在相对测量与拓扑描述更容易一些的AS级层面的HTER删，而对路由层面的ET拓扑研究较少1叫。2005年初，东北大学嵌入式技术实验室经CAIDA111ECOOPERATIVEASSOCIATIONFORINTERNETDATAANFLYSIS，一个对全球范围INTERNET结构及数据进行研究的国际合作机构1授权，成立CAJDA中国第一个节点NEUNODE之后，积极参与了CMDA关于I魄釉ET拓扑结构的相关研究IM。CAIDA中国第一节点NEU，做为CAIDA分布在全球三十余节点中唯一位于中国地区的监测节点，对全球INTERNET拓扑结构、流量特征、网络安全性【161】【162】等一系列问题开展了有效的测量与分析。尤其是面向路由级INT锄ET拓扑测量的CAIDASL【ITTER项目16Q163】【164】【1651，作为项目的参与者之一，NELL节点不仅可获取分布在世界范围内近三十个CAIDA监测点测量INOEMET所得的海量数据，还做为数据提供者，将由NELL节点测量得到的，数以GB计的关于中国地区范围内更为精确的路由分布拓扑结果，向全部CAIDA参与的研究机构共享。因此，东北大学嵌入式技术实验室不仅可以获取全球范围内关于KTERNET拓扑结构的海量TB级数据，还可以实时地、动态地分析位于NEU节点上的第一手拓扑资料，这为路由级HTEMET拓扑结构特征的研究提供了丰富的数据背景与便利条件，可以说，这部分地解决了路由级HNCRILCT拓扑研究的测量难题。IN_CCRNET拓扑建模研究的另一个难题是如何将INTEMET拓扑特征抽取出来并做数学式或模型描述，东北大学嵌入式技术实验室对此也做了充分的准备。早在2004年初东北大学嵌入式技术实验室与CAIDA进行实验性科研合作接触时，嵌入式技术实验室复杂网络研究小组就已经从复杂网络145角度出发，分别对INTEM武的分割度的时间敏感性问题【143】、HTEMET访问直径、MTERNET的网络密度和HTEMET拓扑结构熵及拓扑结构演化【“91等问题进行了比较深入的研究，获得了包括CAJDA在内的国内外同行的认可，并进行1东北大学博士学位论文第一章绪论了充分的学术交流。因此可以说，这为解决路由级INTERACT拓扑的理论研究难题提供了丰富的技术储备与支持。综上所述，CAIDA中国第一节点的背景对本文研究提供了充分的支持，不仅可以获取丰富的拓扑测量数据集合，也有丰富的研究成果做为拓扑研究的理论支持。在这种情况下，本文将对路由级INTERNET拓扑结构特征做尝试性分析，并对路由层面上的INTEMET拓扑结构的建模方法做初步研究。由于在路由层面上的INTEMET拓扑研究在国内外还相对较少，因此研究过程与研究结果均带有试探性，其目的在于为今后在该领域展开更广泛的科学研究提供有益的帮助。本文之后行文中未标明是AS级INTEMET或路由级INTEMET拓扑时，均表示为路由层面的INTEMET拓扑结构。12本文研究目标和主要研究内容INTEMET的宏观拓扑结构研究231146】【14711删【149115川是将INTEMET作为一个整体，利用统计学的方法对其整个拓扑结构特性进行的研究。需要强调的是，本文所研究的INTEMET宏观拓扑结构，是对INTEMET拓扑结构的一种抽象，即忽略一些与INTEMET拓扑结构无关的属性，如网络协议、INTEMET上的服务、网络带宽等，而重点考虑其拓扑结构的相关属性，如节点的连接度、度分布等。INTEMET作为当今人类社会信息化的标志，其规模的增长非常迅速。但现在人类对其宏观拓扑结构”1】的研究还处于初级阶段，在这个看似混沌的网络之中还蕴涵着一些不为人知的规律有待进行深入的挖掘。对INTEMET宏观拓扑结构演化及其内在机制的研究，是在较高层次上开发利用INTEMET的基础。虽然INTERNET的形成被认为是无限定原则的，但是它却展现了一些重要而且普适的宏观拓扑结构特征。因此，对INTEMET宏观拓扑结构的研究，是进一步认识INTEMET规律，有效地发现并利用INTEMET资源和高效开发INTEMET应用的基石。另外，对INTERNET宏观拓扑的研究是计算机网络152】【153】【154自身发展的要求。计算机网络经过几十年的发展，传统的网络技术已经日趋成熟，人们已经不再关注网络的微观细节，而更注重网络的宏观整体性能，而传统的计算机网络无论从网络协议还是从体系结构上来说，已经成为束缚INTEMET未来发展的桎梏。人类对未来INTERENT所提供的服务提出了更高的要求，因此，通过对INTEMET宏观拓扑结构的研究，从中发现INTEMET拓扑5东北大学博士学位论文第一章绪论结构演化的宏观规律，可为设计新一代INTEMET的体系结构和网络协议栈等工作提供有价值的参考。INTERNET是一个复杂网络【123】【1551156】【”7J，对其进行定量研究具有很大的可操作性。网络作为系统的抽象，虽然每一个系统的网络都有其自身的特殊性质，有其紧密联系在一起的独特现象，有其自身的演化机制，但是由于都可以使用网络分析的方法，所以有其共性。例如关于定点度值、介数的分析方法以及大量不同网络中存在的相同的统计特征，再如随机去点与选择性攻击对网络拓扑结构的影响及其分析方法。最新研究趋势表明，研究网络的几何性质、网络的形成机制，网络演化的统计规律以及网络的结构稳定性，并把它的拓扑结构与具体系统结合起来是复杂网络研究的中心内犁74】【158】【159】【1删。因而，对INTERNET宏观拓扑结构的研究，可以为其它类型复杂网络的相关研究提供一个有价值的原型基础。此外，对INTEMET这个高度复杂的系统，发现INTEMET拓扑的内在机制是认识INTEMET的必然过程，是在更高层次上开发利用INTERNET的基础【17】【20】。构建INTERNET拓扑结构模型，刻画INTEMET拓扑结构在宏观上的特征，反映一种总体趋势，也是帮助人们用其来对INTEMET进行分析、预报、决策或控制的需要F171。因此INTEMET拓扑建模问题已经成为INTEMET研究领域中迫切需要解决的重要问题。目前，INTEMET拓扑研究与复杂网络学术界将INTEMET拓扑建模研究的内容大致归结为三个问题【17】【问题1】如何获得一份完备而准确的INTEMET拓扑数据。包括测量INTEMET的方法、数据采集、同名IP解析IPALIASRESOLUTIONIH题11751176、单点测量导致的采样偏见问题171181的解决方法。测量INTEMET方法有很多种，根据测量的方式，分为主动测量和被动测量；根据测量所采用的协议，分为基于BGP协议的测量、基于TCPIP协议的测量以及基于SNMP协议的测量；根据测量点的多少，分为单点测量与多点测量；根据被测量者知情与否，分为协作式测量与非协作式测量；据测量的内容，分为拓扑测量与性能测量。在上述测量方法中，以基于主动探测方法的动态测量为主，目前CAIDA1吲、BOSTONUNIVERSITY的ROCKEFFUEL项目40L、国家信息安全中心哈尔滨工业大学的INTERNET测量平台10J【1691均使用了这种方法。测量数据样本的同名IPIPALIASRESOLUTION问题、单点测量导致东北大学博士学位论文第一章绪论的采样偏见问题是当前INTEMET测量中的常见问题，对于同名问题，可采用CAIDA提供的算法及工具IFFMDER、以及ROCKETFUEL项目中提出的算法及工具SCRIPTROUTE进行预处理；对于单点测量问题，需要使用多个监测点，且要较合理地分布在INTCRNET网络中后，对INTERNET进行测量而解决。【问题2】如何对INTEMET网络拓扑特征进行描述，包括INTEMET拓扑结构图的幂律分布特征、度分布特征以及INTEMET拓扑结构图谱的谱密度包括无符号拉普拉斯谱及规格化拉普拉斯谱。这是本文研究的重点问题之一。对INTERNET拓扑结构图进行包括FIEQUENCYDEGREE幂律分布、DEGREERANK幂律分布、EIGENVALUERANK幂律分布以及CCDFDDEGREE幂律分布特征研究，揭示NTEMET拓扑结构的幂律分布规律。此外，度分布特征及FNTNET拓扑结构图谱的谱密度包括无符号拉普拉斯谱及规格化拉普拉斯谱的特征分析，是FIIITCMET路由级拓扑建模的关键核心内容。【问题3】如何构造一幅类似于MCMET的拓扑图，这是可视化INTERNET的关键问题。可视化INTEMET包括基于地理坐标的可视化及基于拓扑模型的抽象可视化方法。在基于地理坐标的可视化方面，有CAIDA提供的MAPNET工具1166】，它将实际INTEMET路由器与其地理经纬度联系在一起，可以对INTERNET路由器分面按照地理坐标绘图。对基于拓扑模型的抽象可视化问题，可以使用二维的可视化工具，如东北大学嵌入式技术实验室开发研制的复杂网络生成器；与三维可视化工具，如东北大学嵌入式技术实验室开发研制的三维复杂网络生成器，及CAIDA提供的三维FMTEMET拓扑可视工具WALMS【167。在上述三个问题中，拓扑特征分析与建模是核心内容，也是当前大量专家主要进行研究的方面。但该问题要以问题一为基础，只有较好地解决了INTERNET拓扑结构的测量问题，并对测量结果进行合理的精化处理，才能为进一步研究拓扑建模问题提供有价值的数据集，否则在错误的数据集上进行研究，得出的结果很难是正确的。因此第一个问题也是本文中比较重要的部分。虽然模型的可视化工作具有非常重要的意义，而且该研究领域也出现了大量的文献和丰富的成果，具有广阔的研究空间。但就本文而言，将研究重点放在了拓扑模型的构建之上。在可视化方面，本文针对某些可视化算法需要人工安排节点可视化位置的问题，7东北大学博士学位论文第一章绪论使用了一种新的算法SPRINGEMBEDDINGALGORITHM，动态均衡地布点、连边，并根据算法写了简单的二维可视化工具，给出了部分可视化结果。相对上述两个问题而言，可视化部分在本文中所占比例稍少。本文下面将在介绍INTEMET拓扑研究的基础方法与理论之后，从数据分析与预处理着手，进行INTEMET拓扑结构的特征分析及建模研究。13论文的章节安排根据论文研究的内容和方法，全文共分六章。第一章首先分析了INTEMET及INTERNET拓扑研究现状，论述了对INTERNET宏观拓扑结构进行建模研究的意义以及本文将要研究的重点问题与内容，最后介绍了本文组织结构。第二章介绍INTEMET拓扑研究的基本方法。首先根据网络理论和复杂网络理论，论述了从复杂网络角度研究INTEM酐一复杂网络典型实例的基本方法，给出了从图论角度研究INTEMET拓扑的基本概念和技巧；然后给出了几种经典的INTEMET拓扑建模思想，最后介绍了从真实INTEMET网络中采集路由器层面拓扑信息，即INTEMET测量的方法与测量结果，并将测量结果做为本文路由级INTEMET拓扑研究的基本样本集。第三章对INTEMET拓扑测量数据进行数据分析与预处理。首先是同名IP地址解析MALI勰RESOLUTION，由于INTEMET中单个路由器一般拥有多个端口，而每个端口一般配有独立的M地址。这些IP地址在INTEMET测量中被记录在路由信息中，被误认为是单独的路由器，导致在拓扑描述中将一个路由器拆分成了多个路由，产生误差。同名口地址解析部分地解决了该问题。单点测量一节对单点测量产生的采样偏见进行了分析，并针对本文研究，提供了一份基于21个CAIDA监测点的INTERNET测量结果集，极大限度地降低了采样偏见现象。第四章从多方面分析了INTEMET拓扑结构特征，并对拓扑结构进行建模研究，提出了TL拓扑模型。首先论述了INTEMET测量拓扑的幂律分布特征，包括FREQUENCYDEGREE幂律分布、DEGREERANK幂律分布与CCDFDDEGREE幂律分布等，发现INTEMET测量拓扑具有非常明显的FREQUENCYDEGREE幂律分布与DEGREERANK幂律分布，但在CCDFD一DEGREE幂律分布研究中，WEIBULL分布要比幂律分布拟合效果更好，也就是说，对于本文INTEMET拓扑来说，其节点度的CCDF不一定符合幂律分布。其次研究了INTERNET平均度值分布8东北大学博士学位论文第一章绪论情况，并统计了叶子路由在MET测量路由总数所占比重。之后研究了砌砌CT拓扑结构的谱密度分布与无符号拉普拉斯谱SLS分布结果。最后根据上述分析结果提出了一个三层THREELEVEL路由节点的TL模型并给出了生成算法。第五章从定性分析、定量分析与可视化结果的直观视觉角度对TL模型及生成算法进行了分析与评价。定性分析结果表明，TL模型兼具纯静态与纯动态模型的优点，即避免了纯静态模型下过多的人为干预与控制，也避免部分纯动态模型不能产生叶子节点的问题。在定量分析部分，对两份3000节点的TL生成拓扑分别进行幂律分布分析、谱密度分布分析及规格化拉普拉斯谱NLS分析，分析结果表明，TL生成拓扑表现了HLTEMET拓扑的关键特征，TL模型可接受。第六章总结了全文并对未来的工作进行了展望。东北大学博士学位论文第二章INTERNET拓扑特征分析第二章INTERNET拓扑特征分析21INTEMET的复杂网络特征211网络的拓扑特征量对于网络的研究，最早是从数学家开始的，其基本的理论就是图论。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的等等，这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。目前，图论、尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一H111421143114445】脚】。因此，了解图论中基本概念及符号，将帮助加速复杂网络研究过程和理解复杂网络研究成果。本文下面对其重点概念进行简单介绍闱【47】嗍。2111图的基本概念【定义21】图一个图G是一个二元组，这个二元组包括一个顶点集VG，一个边集EG，V与G之间的关系使得每一条边和两个顶点不一定是不同的点相关联，并将这两个顶点称为这条边的端点。图G中的两个集合N毋，其中集合矿是图G的顶点集，被用来代表实际系统中的个体；集合E是集合VXV的一个子集，被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若工，力E，就称图G中有一条从X到Y的弧有向边，记为善一Y，其中顶点X叫做弧的起点，顶点Y叫做弧的终点。根据定义，从任意顶点石到Y至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，其关系将在多个图中分别表示，从而不使这种复杂的关系而给解析带来困难。假设图G中不含自己到自己的弧，我们就称图G为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G中顶点数为YGIVI，边数为8GIEI，分别叫做图G的阶和规模，显然有GGSYGYG一1。图21A给出了两个图及其表示为顶点集和边集的形式，其中图A是具有10个节点的有向图，B是一个具有6个节点的无向图。东北大学博士学位论文第二幸INTEMET拓扑特征分析8Z韧LB6图21网络拓扑结构示意图。图A是10阶有向图，顶点集为1，2，3，45678910，边集为12，13，L一4，2一S0627，36，47，4一B，69，79，SLO；图B是6阶无向图，顶点集为1，2，3,4，56，边集为13，14，15，23；24,26，36，56FIG21FIGUREOFNETWORKTOPOLOGYINWHICH,FIGAISADIRECTEDGRAPHWITH10ORDERS，ANDFIGBISANONDIRECTEDGRAPHWITH6ORDERS从定义中可以看到，从任意顶点X到Y不能连接两条或以上边，本文所讨论的图，均符合上述要求，即均为不含多重边的图。【定义221无向图如果在一个图G中，弧X一，与弧尸X要么同时存在，要么同时不存在，我们就把这两条弧