（计算机应用技术专业论文）internet自治域层拓扑特性研究与建模.pdf

人造理i ：人学硕1 ：学f 论文 摘要 i n t e m e t 懿逐猛发襞带寒了一系捌翅题，鲷翔鼹垂、资源预戳嚣网络管瑗等阂题。由 于在i n t e m e t 上实验非常昂贵，且因为一些商业戮索的限制，研究者不可能纛接在i n t e m e t 上模拟和仿真实验，一般都利用网络拓扑模型进行实验。i n t e m e t 拓扑建模熊为网络问题 的分析提供一个抽象模型结构，使缀多| 商题易予分析。所以，对于 n t e r n e t 撼扑建模豹研 究一妻舔楚露络研究豹熬点闯题。 i n t e m e t 拓扑模黧的研究经历了从随机型到屡次型，再到秃尺度网络的过程。然而目 前为止，研究者们没肖找到公认统一的理论去解释i n t e m e t 的演化机理，都只能根据自己 熬分掇建立演纯模型，然嚣对尽霹熊多戆参数遴行实验谔售，希望模型驻受好遗“遥遥” i n t e m e t 的实际拓扑。戳及更合理溅解释i n t e r n e t 拓扑的形成原因。 本文首先介绍了强前i n t e m e t 拓扑的四个基本统计特性：咒尺度、小世界、集聚性及 异配性，筹就这些特性对当前i n t e m e t 拓扑做了统计分析。 箕次，本文簪 究帮分橇了尼静囊流豹i n t e r a c t 缀矜模型爱羹筹法，雹菇b a 、a b 、i n e t 、 p l r g 和g l p 模型，并对他们做了仿真分析。结果显示，这些模型都能得到岛i n t e m e t 某 些特性相符的拓扑图，不过都还存在不足之处，尤其是集聚稔度都低于i n t e m e t 。 然麓，具薅分擀了这些模型豹演纯算法存在筑局限。i n e t 髑p l r g 棱黧是静态豹， 嚣斡是产生一戤与现裔i n t e r n e t 幂律特性相符会的拓扑图，这种模型不髓解释i n t e r n e t 的动态演化过程。动态模型如b a 、a b 和g l p 通过建立演化机制来模拟i n t e m e t 的发展 过程，假这些模型的增长都是人为假设的均匀增长，与i n t e m e t 规模的指数增长现象不 苍会，纛建连疆澍其蘩毪。 最艏，根据对i n t e m e t 层次性和规模增长特性的分析，掇出了基于生灭过程的层次 模型( h i e r a r c h i c a lm o d e lb a s e do nb i r t ha n dd e a t hp r o c e s s ，b d h m ) 。与传统横溅不同的是， b d h m 考虑了i n t e r a c t 孛a s 节煮之阅豹螽韭关系以及两络裁摸的撞数增长。b d h m 用 最大度冀配子瓣冗余带点算法构遮静干网来实魂i n t e m e t 的努麓；置；| 入象灭过程理论 计算新带点的产生概率，从而用均匀时间步实现了规模的指数增长。另外，借助生灭过 程理论推导出了网络特征路径长度随时间的极限值。实验结果表明，b d h m 模型的拓扑 骜薤与突嚣i n t e r n e t 较德合，基褒黛蒙毪秘特鬣鼹经长度上跑囊滚摸型表褒受磐。 关键词：i n t e r n e t 拓扑；骨干网；指数增长；觅尺度 人连理i ：入学硕十学f t 论文 t o p o l o g i c a lc h a r a c t e r i s t i cr e s e a r c ha n dm o d e l i n gf o r a s - l e v e li n t e r n e t a b s t r a c t 1 1 l er a p i dd e v e l o p m e n to fi n t e r n e th a sb r o u g h tas e r i e so fp r o b l e m s ，s u c ha sr o u t i n g , r e s o u r o er e s e r v a t i o na n dn e t w o r km a n a g e m e n t ，a n do t h e ri s s u e s a se x p e r i m e n t i n go nt h e i n t e r a c ti sv e r ye x p e n s i v e , a n da l s of o rs o m ec o m m e r c i a lf a c t o r s ，t h er e s e a r c h e r sc a n n o t e x p e r i m e n td i r e c t l yo ut h ei n t e r a c t , b u to f t e no i ln e t w o r kt o p o l o g ym o d e l s i n t e r n e tt o p o l o g y m o d e l i n gp r o v i d e sa l la b s t r a c tm o d e ls t r u c t u r ef o rt h en e t w o r ka n a l y s i s ，a n dm a k e sm a n yo f p r o b l e m si se a s yt ob ea n a l y z e d t h e r e f o r e ，t h er e s e a r c ho fm o d e l i n gt h e i n t e r a c tt o p o l o g yh a s b e e na no p e n i n gt o p i c n ei n t e r n e tt o p o l o g ym o d e l i n gs t a r t e df r o mt h er a n d o mm o d e lt ot h eh i e r a r c h i e a lm o d e l 。 t h e ni td e v e l o p e dt oam o r er e a l i s t i co n e ，t h es c a l e f r e en e t w o r km o d e l b u tn o w , r e s e a r c h e r s h a v en o tp r o p o s e dau n i f i e dt h e o r yt oe x p l a i nt h ee v o l u t i o no ft h ei n t e r a c t t h e ye s t a b l i s h e v o l u t i o nm o d e l si na c c o r d a n c ew i t ht h e i ro w na n a l y s i s , a n dt h e n e v a l u a t et h e i rm o d e l s a c c o r d i n gm a n yp a r a m e t e r s , t om a k et h e i rm o d e l sa p p r o x i m a t e t ot h ea c t u a li n t e r n e tt o p o l o g y , a sw e l la se x p l a i ne v o l u t i o no fi n t e r n e tr a t i o n a l l ya sc a na sp o s s i b l e t h i sp a p e rf i r s ti n t r o d u c e sf o u rb a s i cs t a t i s t i c a lc h a r a c t e r i s t i c so ft h ei n t e r n e tt o p o l o g y ： s c a l e - f r e e , s m a l lw o r l d , c l u s t e r i n ga n dd i s a s s o r t a t i v em i x i n g a n dt h o s ec h a r a c t e r i s t i c sh a v e b e e nt e s t e do nc u r r e n ti n t e m e ti nt h i sp a p e r s e c o n d l y ，t h i sp a p e ra n a l y z e sm a n yd o m i n i c a lt o p o l o g yg e n e r a t o r sa tp r e s e n t ，i n c l u d i n g b a , a b 。i n e t p l r ga n dg l pm o d c l ，a n dt h e nu s e ss o m ea u t h o r i t a t i v em e t r i c st oe v a l u a t e t h e m r e s u l t ss h o wt h a tt o p o l o g i c a lm a p sg e n e r a t e db yt h e s em o d e l sc a 萎e x h i b i ts o m e t o p o l o g i c a lf e a t u r e so ft h ei n t e r a c t , b u tt h e r ea a l s oc e r t a i nd e f i c i e n c i e s , e s p e c i a l l y t h e c l u s t e r i n ga l la r ei n f e r i o rt oi n t e r a c t t h i r d l y , t h i sp a p c ra n a l y z e st h el i m i t a t i o n so ft h ee v o l u t i o na l g o r i t h m su s e db yt h o s e m o d e l s i n e ta n dp 琢gm o d e la l es t a t i c , a n dt h e i ra i mi st og e n e r a t e 鑫曩a p p r o x i m a t em a p w i t hp o w e fl a wc h a r a c t e r i s t i c s t a t i cm o d e l sc a n n o te x p l a i nt h ee v o l u t i o np r o c e s so ft h e i n t e r n e t d y n a m i cm o d e l s ，s u c ha sb 氏a b a n dg l pm o d e l ，e s t a b l i s he v o l u t i o nm e c h a n i s m s t os i m u l a t et h ed e v e l o p m e n to ft h ei n t e r a c t b u tt h o s em o d e l sm a d eu n i f o r mg r o w t h a s s u m p t i o n s , w h i c hd i d n tm e e tt h ee x p o n e n t i a lg r o w t ho ft h ei n t e r n 攘a n dt h e i ra t t a c h m e n t m e c h a n i s m sa r es i m p l e x f i n a l l y , a c c o r d i n gt ot h ea n a l y s i so ft h ei n t e r n e tg r o w t hi nt h es c a l ea n dh i e r a r c h i c a l c h a r a c t e r i s t i c , ah i e r a r c h i c a lm o d e lb a s e do nb i a ha n dd e a t hp r o c e s s c a l l e db d h ms h o r t l y , i s p r o p o s e d 。d i f f e r e n tf r o mt h et r a d i t i o n a lm o d e l s ，t h eb u s i n e s sr e l a t i o n s h i pb e t w e e na sa n d t h e i l i i n t e m e t 白治城层拓扑特性研究与建模 e x p o n e n t i a lg r o w t hb o t h a r ec o n s i d e r e di nb d h m b d h ml a y e r sn e t w o r kt h r o u g h r e d u n d a n c yn o d e sa l g o r i t h mo ft h eg r e a t e s td e g r e e a n dt h r o u g l lc o m p u t i n gn o d e sb i r t h p r o b a b i l i t yb yb i r t ha n dd e a t hp r o c e s s ，b d h ma c h i e v ee x p o n e n t i a lg r o w t ho fn e t w o r ki n u n i f o r mt i m es t e p s i na d d i t i o n ，t h r o u g hb i r t ha n dd e a t hp r o c e s st h e o r y ，b d h mg e t st h el i m i t w i t ht i m eo fc h a r a c t e r i s t i cp a t hl e n g t h t h es i m u l a t i o ns h o w st h a tt h et o p o l o g yc h a r a c t e r i s t i c s g e n e r a t e db yb d h mm o d e la r ca l lc o n s i s t e n tw i t he m p i r i c a le v i d e n c et os o m ee x t e n d a n d t h ec l u s t e r i n gc h a r a c t e r i s t i ca n dc h a r a c t e r i s t i cp a t hl e n g t hb o t hh a v eb e t t e rp e r f o r m a n c et h a n t r a n d i t i o n a lm o d e l s k e yw o r d s ：i n t e m e tt o p o l o g y ；b a c k b o n es u b n e t ；e x p o n e n t i a lg r o w t h ；s c a l e 。f r e e i v 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：盔圣：! 生日期：! ! ! ! ：12 人造理i ：人学硕十研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文 乍者及指导教卿完全了解“大连瑾王大学颁士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文麓复印件和电子叛，允许论文被查阕和借溪。本人授权大连囊 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 俸者签名：童塑釜 一 黝懿i 錾! 咝 豳年上月且阿 人连理j ：人学硕十学位论文 1绪论 1 1 in t e r n e t 拓扑研究的背景和意义 i n t e r a c t 作为当今人类社会信息化的标志，其规模正以指数速度迅猛增长。如今 i n t e m e t 的“面貌”已与其原型a r p a n e t 大相径庭，根据其高度的复杂性，可以将它 看作一个由计算机构成的“生态系统”。i n t e r n e t 拓扑建模研究就是探求在这个看似混 乱的网络之中蕴含的还不为人所知的规律。发现i n t e r a c t 拓扑的内在机制是认识i n t e r n e t 的必然过程，也是在更高层次上开发利用i n t e r n e t 的基础。然而，i n t e r a c t 与生俱来的异 构性、动态性、发展的非集中性以及如今庞大的规模都给拓扑建模带来巨大挑战【“。 i n t e r n e t 拓扑建模至今仍然是一个开放性问题，在计算机网络研究中占有重要地位。 n t e r n e t 拓扑作为i n t e m e t 这个自组织系统的“骨干”，与流量、协议共同构成模拟 i n t e r n e t 的3 个组成部分，即在拓扑网络中结点间执行协议，形成流量。i n t e r a c t 拓扑模 型是建立i n t e r n e t 系统模型的基础，由此而体现的拓扑建模意义也可以说就是i n t e r n e t 建模的意义，即作为一种工具，人们利用其对i n t e r n e t 进行分析、预报、决策或控制。 i n t e m e t 模型中的拓扑部分刻画的是i n t e m e t 在宏观上的特征，反映一种总体趋势，所以 其应用也都是在大尺度上展开的。 对i n t e r n e t 拓扑模型的需求主要来自以下几个方面： ( 1 ) 许多新应用或实验不适合直接应用于i n t e r n e t ，其中一些具有危害性，如蠕虫 病毒在大规模网络上的传播模拟1 2 】。 ( 2 ) 对于一些依赖于网络拓扑的协议( 如多播协议【3 j ) ，在其研发阶段，当前i n t e r n e t 拓扑只能提供一份侧试样本，无法对协议进行全面评估，需要提供多个模拟拓扑环境来 进行实验。 ( 3 ) 从国家安全角度考虑，需要在线控制网络行为，如美国国防高级研究计划局 ( d a r p a ) 的n m s ( n e t w o r km o d e l i n ga n ds i m u l a t i o n ) 项目。 i n t e m e t 拓扑建模是一项复杂的工作，涉及网络测量、图论、算法设计、统计学、 数据挖掘、可视化以及数学建模等多个研究领域。i n t e r a c t 拓扑建模研究内容可归结为3 个问题： ( 1 ) 如何获得一份完整而准确的i n t e r a c t 拓扑数据。 ( 2 ) 如何对i n t e m e t 网络拓扑特征进行描述。 ( 3 ) 如何构造一幅类似于i n t e m e t 的拓扑图。 i n t e m e t 白 f 域层拓扑特性研究与建模 这3 个问题分别对应于3 个研究方向，即拓扑结构测量、拓扑特征发现和拓扑生成 器丌发。其中拓扑结构测量是拓扑建模的基础：拓扑特征发现是拓扑建模的核心；拓扑 生成器就是拓扑模型的软件实现。 1 2 i n t e r n e t 拓扑研究现状 i n t e m e t 拓扑研究经历了从经验假设到客观分析，从单纯的计算机网络研究到复杂 系统特征化研究的过程。在研究早期，由于缺乏真实测量数据支持，拓扑模型都是研究 人员基于经验假设建立的。最早的i n t e m e t 拓扑模型是1 9 8 8 年w a x m a n 提出的w a x m a n 模型1 4 1 。这是一种随机模型，沿用了很多年。直到1 9 9 6 年，d o a r 提出了t i e r s ( 等级) 模 型1 5 1 。该模型刻画了i n t e r a c t 所具有的层次特征。1 9 9 7 年，z e g u r a 等人【6 j 提出了另一种 层次模型- t r 赫s i t s t u b 模型。此时，从1 9 9 5 年开始的大规模i n t e m e t 拓扑测量工作 已经逐步展开，采集到了大量拓扑数据。这些数据对科研机构都是免费开放的，极大地 推动了拓扑研究的发展。i n t e m e t 拓扑研究也进入了一个成果不断累加的阶段，发现多 于改进，新旧成果共同描绘了i n t e m e t 拓扑图景。在所有研究成果中，最重要的是，1 9 9 9 年f a l o u t s o s 等人发现i n t e r a c t 拓扑结构中存在幂律( 幂指数) l 。”。幂律的发现将i n t e m e t 拓扑与一些生物学、社会学中的复杂网络联系起来，使其成为“无尺度( s c a l e f r e e ) ”网 络的一个实例，在i n t e r n e t 拓扑研究与系统学研究之间架起了一座桥梁。2 0 0 0 年以来， 研究人员开发了许多遵循幂律的拓扑生成算法 8 - 1 5 1 以及拓扑生成裂1 6 - 1 s 1 ，为i n t e m e t 模拟 提供了有利的支持。不过，现有成果距离前面提到的3 个问题的答案还有一定距离，而 且新的发现【1 9 , 2 0 l 也对现有成果提出了挑战。 1 2 1 拓扑模型 下面就拓扑模型和拓扑生成器逐一展开讨论，探讨其研究进展与关键技术。 i n t e m e t 拓扑模型可分为两类：一类是描述i n t e r a c t 拓扑特征，包括w a x m a n 模型、 t i e r s 、t r a n s i t s t u b 和幂律型模型如b r i t e 等；另一类是描述拓扑特征形成的机理，包 括b a r a b a s i 与a l b e r t 提出的b a 和e s f 以及一种改进模型g 等。 ( 1 ) 描述i n t e r a c t 拓扑特征的模型 对于第1 类模型来说，i n t e m e t 拓扑特征的发现，实际上就是刻画特征的度量( m e t r i c ) 的发现。一个属于第一类的拓扑模型就是包含若干已存在的或新发现的度量，然后根据 实际的i n t e r a c t 拓扑数据求出这些度量的值。因此，对这类模型进行评价需要从两方面 入手：一方面，对它所采用的拓扑数据进行评价；另一方面，对其度量进行评价。在所 有已经发现的i n t e m e t 拓扑度量中，最为基本的就是结点出度频率觑( 通常也叫节点度) ， 其分布是判断一幅拓扑图是否与i n t e r a c t 拓扑相类似的最重要的依据。在研究早期，研 人迮理i ：人学硕十学位论文 究人员或者认为i n t e m e t 结点出度是完全随机的( 如w a x m a n 模型) ，或者认为结点出度 是j 下规的( 如t i e r s 模型1 5 j ) 。而幂律的发现证明了i n t e m e t 拓扑结构介于两者之间，呈幂 律分布n 根据对出度频率分布的刻画，可将i n t e m e t 拓扑模型分为以下3 类： 随机型，即认为i n t e r n e t 拓扑处于一个完全无序的状态，在大尺度上是均一的。 w a x m a n 模型【4 j 是一种类似于e r d 6 s r 6 d n y i 模型的随机模型，出度频率呈泊松分布。 层次型，来自对i n t e r n e t 结构所具有的层次特征的认识，在同一层上的结点出度 接近，不同层间结点出度差别很大。对同一层上的结点布置借用w a x m a n 模型方法。例 如，t i e r s 模型1 5 j 将i n t e r n e t 划分为l a n ( 局域网) 、m a n ( 城域网) 和w a n ( 广域网) 3 个 层次。在该模型中，w a n 只有一个，通过指定l a n 和m a n 数量以及各自内部所包含 结点的数量来构造拓扑图。t r a n s i t s t u b 模型将a s 域划分为t r a n s i t 域和s t u b 域两类【6 】。 在该模型中，t r a n s i t 结点彼此互连构成一个结点群，一个或多个t r a n s i t 结点群构成拓 扑图的核心，而s t u b 结点分布在t r a n s i t 结点群四周与t r a n s i t 结点相连。t r a n s i t s t u b 是g t i t m ( g e o r g i at e c hi n t e r n e tw o r kt o p o l o g ym o d e l s ) 软件包的一部分，有时g t 1 t m 也就是指t r a n s i t s t u b 模型。 幂律型( 或幂指数型) ，1 9 9 9 年，f a l o u t s o s 等人对n l a n r ( n a t i o n a ll a b f o ra p p l i e d n e t w o r kr e s e a r c h ) 在1 9 9 7 1 9 9 8 年间的3 份b g p 数据以及1 9 9 5 年的一份t r a c e r o u t e 测量 数据进行分析，发现i n t e r n e t 的a s 级拓扑中存在着4 条幂律r “。幂律是指形如yo cx c 的 方程，对于两个变量x 和y ，存在一个常数c ，使得l ，与x 的c 次幂成比例。幂律的发 现也给出一个启示：i n t e r n e t 中某个属性值的平均值不能准确地刻画这一属性，应该尝 试用某个指数来进行刻画。因为本文提出的新模型涉及到幂律的使用，所以对于幂律的 规律的详细说明将在下一章着重介绍。 对幂律的概念化形象描述是2 0 0 1 年t a u r o 等人针对幂律1 和幂律2 提出的一种概 念模型2 1 j 。这个模型将a s 级拓扑图看作一只水母：水母的帽子代表i n t e r n e t 的核心， 随着与核心的远离，结点重要性逐渐下降，中间的腿比两边的长表示出度为1 的结点具 有聚集性；网络对随机故障是鲁棒的，而若在核心出了故障却是灾难性的。幂律的发现 激发了研究人员在i n t e m e t 拓扑结构中寻找更多的规律，也引起了学术界的广泛关注。 2 0 0 1 年，m a g o n i 和p a n s i o t 对n l a n r 在1 9 9 7 2 0 0 0 年间的b g p 数据进行更细致的分析， 提出了i n t e m e t 拓扑发展的5 条经验规律和4 条关于结点间最短路径和树结构的幂律1 2 2 t 。 2 0 0 3 年，c h a l m e r s 等人发现，在多播树的某些特征中也存在类似幂律的分布【3 】o ( 2 ) 描述i n t e r n e t 拓扑特征形成机理的演化模型 描述拓扑特征形成的机理，包括b a r a b a s i 与a l b e r t 提出的b a 和e s f 以及其他改进 模型如g l p 等。这类模型的目的在于探索i n t e r n e t 拓扑的形成原因，对认识i n t e r n e t 的 n t e m e t 自| ；f i 域层拓扑特性研究与建模 拓扑演倪过程其存熬簧意义，建立动态演化模穗也成为当静研究i n t e r n e t 拓 的主流方 法。本文的主要目的之一也是发现i n t e r n e t 拓扑形成的一些内在机制，对此类模型及其 算法的详细研究分析将放在第三警。 。2 2 搔 生成嚣 拓扑生成器是拓扑模型的软件实现，设计目标可归纳为3 点： ( 1 ) 代表性，卸生成的人工拓扑圈要能够准确反映实际i n t e m e t 拓扑酌各个方面。 ( 2 ) 惫含毪，露穆许多生残攘整合著在一麓，提供一令遴焉戆楚羚象袋工兵。 ( 3 ) 兼容性，即为网络模拟威用程序( 如n s ，2 ) 以及可视化工具( 如( 瑚d a 的o t t e r ) 提供接口。 为实现这些嚣掭，一个拓扑擞成器主要怠括3 个功能摸块： ( 1 ) 格式转换。出于器翦没裔统一盼掭羚数据文侔格式稀准，所戳拓矜生成器要暴 有在备种拓扑测量数据、拓扑生成器输入输出数据以及模拟软件输入数据之间进行文件 格式转换的功能。 ( 笏强羚生成。这莛慈势雯成器夔菝心。除了稷撂己鸯豹薤羚生藏舅法实瑷攀律之 外，还装依据其他度量来产生拓扑图。 ( 3 ) 拓扑分析。根据拓扑生成模块中所采用的度量来对拓扑数据进行统计分析，绘 出度羹静篮。 瓣耨，专门酶掇矜生成器舂淤- f4 释： ( 1 ) 波士顿大学的b r i t e 通用拓扑产生器 b r i t e ( b o s t o nu n i v e r s i t yr e p r e s e n t a t i v ei n t e r n e tt o p o l o g yg e n e r a t o r ) 【1 6 1 ，是波士顿大 学予2 0 0 1 年秀发豹一令逶蔫据羚产生器。英特焦在予“逶臻”：善宠，宅安瑗了w a r , m a n 模型和b a 算法，并可以用自顶向下和自底向上两种方法来产生g t - i t m 朦次模型；其 次，窀为多个网络模拟程序提供接口，包括n s 2 、s s f 、o m n e t + + 和j a v a s i m ，并支持可 视化王其o t t e r 。b r i t e 产生路由器级帮a s 级妊扑图，并碍为连接分配带宽帮延迟，具 有图形爝户接日。 ( 2 ) 法国u l p s 犬学的n e r o 拓扑产生器 h e m ( n e t w o r km a n i p u l a t o r ) b 8 1 是法国u l p s 大学( u n i v e r s i t yo fl o u i sp a s t e u r s 蚋热。毽f 垂手2 0 0 2 攀嚣发豹。獒特煮是吴毒邋鬻毪，著怼援羚鹜在最短鼹经长度窝键 结构方面的度量进行优化。n e m 实现了除早期3 种算法与6 ”之外的全部5 种拓扑生 成算法。n e r o 将拓扑特征分为5 类：树、距离、连通性、结点对最短路径数以及类别( c l a s s ， 包括时上结点数、环上结点数等) ，可对这5 类特征进行分橱。n e r o 为网络横拟软件n s 2 ， g l o m o s i m _ 饔o p n e t 箍供嫠日，戳我处理文本文件作为蘑产臻口。 人迮理i ：人学硕十学位论文 ( 3 ) 密歇根大学的i n e t 拓扑产生器 i n e t ”j 是密歇根大学于1 9 9 9 年至2 0 0 2 年问丌发的一个a s 级拓扑产生器，最新发 行的是2 2 版本。其特点是利用r o u t e v i e w s o r e g o n i x n e t 上1 9 9 7 年1 1 月至2 0 0 2 年2 月 白j 的大量b g p 数据来确定拓扑度量的值，可信性很高。i n e t 采用p l g r 算法与优先附 着实现幂律，重视连通性( 最小结点覆盖) ，并针对最大聚团数和群集参数做了优化。i n e t 使用简便，只需在命令行输入拓扑图中结点总数即可。 ( 4 ) 乔治亚大学的g t - i t m 拓扑生成器 g t i t m ( g e o r g i at e c hi n t e m e tw o r kt o p o l o g ym o d e l s ) 是美国乔治亚大学研究开发的 网络拓扑生成器，它包含了t r a n s r s t u b 模型和其他一些工具。t r a n s i t - s t u b 模型是基于 层次结构的拓扑模型。g t - i t m 是用c 编写的，使用了s t a n f o r d g r a p h b a s e ( s g b ) 平台作 图，g t r r m 里面包含了s g b ，用户可以直接使用，而不用另外下载。 1 3in t e r n e t 建模的难点问题与研究路线 i n t e m e t 拓扑研究目前面临的主要困难来自于两个方面：一方面是i n t e r a c t 自身复杂 的特性；另一方面是缺乏进行系统研究的方法论。 i n t c m e t 自身性质带来的问题主要集中在拓扑测量上，具体表现在：拓扑结构动态 变化影响测量准确性；其庞大的规模影响了测量数据的完整性；异构性与管理的非集中 性增加了测量的技术难度1 1 】。因此客观地说，目前的网络测量技术无法获得完整而准确 的i n t e m e t 拓扑图，现有的i n t e r a c t 拓扑模型都存在一定的局限性。由此引发的问题是： i n t e r a c t 拓扑中真的存在幂律吗? 这个疑问的产生来自于两点： ( 1 ) q i a nc h e n 等人【1 9 】质疑f a l o u t s o s 等人1 1 2 j 在发现幂律时所用的a s 拓扑数据丢失 了2 0 - 5 0 的物理连接，与真实的网络拓扑之间存在很大差异，也就是说，幂律并不能 严格地刻画i n t e r n e t 拓扑。 ( 2 ) 1 a k h i n a l 2 0 1 也对幂律的正确性提出了挑战，指出由少数探测源点和庞大的目标 结点构成的探测体系由于最短路径原理的作用而存在采样偏见。采用这种存在采样偏见 的技术对w a x m a n 模型产生的拓扑图进行测量，实验结果同样会满足幕律【捌。另外， i n t e m e t 的动态性也缩短了拓扑模型中静态元素的寿命，使得拓扑建模研究不能仅仅描 述当前i n t e m e t 的表象，还要发现其背后的驱动机制。 随着研究的不断深入，人们发现i n t e r n e t 不只是硬件加上软件，而是在一定意义上 进行“新陈代谢”的自组织系统。i n t e m e t 拓扑与万维网( 通过u r l 连接) 、细胞网络( 通 过化学反应连接) 、人际关系网、科学文献引用网络等具有共同的内在特征自相似 性，并且认识到对i n t e m e t 拓扑缺乏了解并不只是一个计算机科学问题，而是源于缺少 i n t e m e t 臼治域层拓扑特性研究与建模 一个对复杂网络进行特征化的科学框架。因此，成功建立i n t e m e t 拓扑模型要依赖于科 学界在上述领域的共同努力，拓扑建模的研究成果也会促进这一科学框架的形成。 综上所述，今后i n t e m e t 拓扑建模的研究路线主要包括以下3 个方面： ( 1 ) 通过分析路由协议与协议栈来开发新的拓扑测量技术，提高数据完整性以及路 由器多接口合并比例，以求从新数据中发现新特征。 ( 2 ) 将数据挖掘与图论两者结合起来，从现有数据中发现新特征。 ( 3 ) 借鉴其他复杂网络的研究成果，特别是复杂系统中具有普遍性的原理，以发现 i n t e m e t 拓扑形成的内在机制。 1 4 本文工作 研究者利用网络拓扑生成器模拟实际网络进行仿真实验。目前，网络领域和图形理 论的研究者都没有找到公认统一的理论去解释i n t e m e t 的演化机理，也没有产生一份公认 与i n t e m e t 完全相符的拓扑图。研究者们只能根据自己的推断建立演化机制，然后对尽可 能多的参数分析和实验，希望模型能更好地“逼近”i n t e m e t 的实际拓扑，更合理地解释 i n t e m e t 的演化机理。 本文的主要工作主要包括以下几点： 第一，分析了当前i n t e m e t 的四个基本统计特性：无尺度、小世界、集聚性及异配性， 这四种统计特性被研究者们视为检验一个模型有效性的基本度量标准。通过分析现有 i n t e m e t 的统计特性，为下一步检验各演化模型的有效性做好了铺垫。 第二，研究和分析了几种主流的i n t e m e t 拓扑模型及其算法，包括b a 、a b 、i n e t 、 p l r g 和g l p 模型，并对他们的度分布幂律指数、特征路径长度和集聚系数做了评估。 模拟结果显示，这些模型都能在一定程度反映i n t e m e t 的拓扑特征，不过都还存在某些不 足。 第三，具体分析了各模型演化算法不足之处。目前主流模型可大致分为静态和动态 两大类，静态模型的目的是产生一副与现有i n t e m e t 幂律特性相符合的拓扑图，基本方 法是先预设好网络的规模，再根据幂律度分布给节点分配连边，这种模型的不足在于不 能解释i n t e m e t 的动态演化过程；目前动态模型的不足在于模型中网络的增长都是人为 假设的均匀增长，与i n t e m e t 的指数增长现象不符合，且模型中所有节点间都采用单一 的建连机制。 第四，分析了i n t e m e t 的层次特性，统计了i n t e m e t 的规模增长特性，在此基础上提 出了基于生灭过程的层次模型b d h m 。与传统模型不同的是，模型考虑了i n t e m e t 中 a s 节点之间的商业关系以及网络规模的指数增长，用最大度支配子网冗余节点算法构 人连理i ：人学硕十学位论文 造骨干网来实现i n t e m e t 的分层，并且通过引入生灭过程理论计算新节点产生概率的方 法，用均匀时间步实现了网络规模的指数增长。另外，用生灭过程理论推导出了网络特 征路径长度随时问的发展趋于稳定。最后将b d h m 与实际i n t e m e t 及传统主流模型做了 比较分析。 第五，对本文工作做了总结，并展望了下一步工作要点。 1 5 本文组织结构 本文余下部分组织如下： 第二章，i n t e r n e t 拓扑特性分析。主要分析当前i n t e r n e t 的四大基本拓扑特征：无尺 度特性、小世界效应、聚类特性和异配性。 第三章，i n t e m e t 拓扑模型的研究和性能分析。主要研究了现存主流的i n t e r n e t 拓扑 模型及其算法，并对他们的性能做了定性评估。模拟结果显示，这些模型都能在一定程 度反映i n t e r n e t 的拓扑特征，不过都还存在某些不足，特别是在集聚系数方面，各模型 的成簇程度都很低。 第四章，一种新的基于生灭过程的层次模型( b d h m ) 。首先分析了目前主流模型演 化算法存在的某些不足，然后对i n t e m e t 的层次性和规模增长做了分析，在此基础上提 出了一种新的模型。新模型通过构造骨干网的形式模拟i n t e m e t 的层次性，借助生灭过 程理论计算节点的产生概率，模拟网络规模的指数增长。最后，为检验模型的有效性， 将模型与实际i n t e m e t 及主流模型做了比较。比较结果显示，b d h m 模型的拓扑特征与 实际i n t e m e t 较符合，且在集聚性和特征路径长度上比主流模型表现更好。 最后是结论。对全文工作做简要总结，并提出下一步工作思路。 i n t e r n e t 白治域层拓扑特性研究与建摸 2in t e r n e t 拓扑特性分析 2 1 网络的表示 网络可以抽象为一个由节点集v 和边集组成的图g 一缈，e ) ，e 中的每条边都有 集合v 中的一对节点与之相对应。图g 的节点个数记为n = i v i ，边数记为m = l e l 。一 个图的画法并不是唯一的，表示节点的点和表示边的线的相对位置是无关紧要的。图2 1 表示了一个图g 的两种不同表示形式。图的多种表示形式适用于无地理位置信息的网 络，而对于大型电力网络等这样受地理位置限制的网络，图中的节点与边的相对位置应 该是固定的。如果一个图中既没有自环( 即不存在以同一个节点为起点和终点的边) ，也 没有两条边连接同一对节点的重边，则称该图为简单图。图2 1 所示的图中有自环，有 重边，则该图不是简单图；图2 2 所示的图中无自环且无重边，则为简单图【矧。 图2 1 图g 的多种表示形式 f i g 2 1 f o r m so f g r a p hg 按照边的性质，可以将图分为无向图、有向图及加权图。相应地，可以将网络定义 为无向网络、有向网络及加权网络。若集合v 存在一对节点 ，y ) 与o ，“) 对应e 中的同 一条边，则该网络称为无向网络( u n d i r e c t e d n e t w o r k ) ，否则，称为有向网络( d i r e c t e d n e t w o r k ) 。如果e 中的每条边都赋予相应的权值，则称该网络为加权网络( w e i g h t e d n e t w o r k ) ，否则称为无权网络( u n w e i g h t e dn e t w o r k ) 。图2 2 给出了几种不同类型的网络 例子。 目前对i n t e m e t 拓扑的研究尚不够成熟，大部分研究者都将i n t e r a c t 拓扑抽象成无权 无向网络，不考虑链路流量负载权重和流量传输的方向。本文中所涉及的网络，若无明 确说明，均为无权无向网络，并且是无重边和自环的简单网络。 一个网络图中，节点的度为与该节点直接相连的边的数量。对于有向图，节点的度 分为出度和入度，其中，出度为从该节点指出的边数，入度为指向该节点的边数。 人连理l ：人学硕十学仿论文 大部分网络研究工作只关注于节点及边的关系，而不依赖于节点的具体位置和属 性，这样的研究属于网络拓扑结构的研究。 ( 1 ) 无向网络( 2 ) 有向网络( 3 ) 加权网络 图2 2 不同类型的网络 f i g 2 2t y p e so f n