（计算机应用技术专业论文）internet拓扑的社团特性分析及建模.pdf

l ，。 j _ 】_ _ ：一 at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e r a p p l i c a t i o nt e c h n o l o g y t h e a n a l y s i sa n dm o d e l i n go ni n t e r n e tt o p o l o g y ，s c o m m u n i t y s t r u c t u r e o m m u n i b yy u a ns h a o q i a n s u p e r v i s o r ：z h a oh a i n o r t h e a s t e r nu n i v e r s i t y d e c e m b e r2 0 0 7 ，、 、 独创性声明 所呈交的学位论文是在导师的指导下完成的。论文中取得的 以标注和致谢的地方外，不包含其他人已经发表或撰写过的 不包括本人为获得其他学位而使用过的材料。与我一同工作 究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 学位论文作者签名： 签字日期 ： 友南己z 妈 叼- y _ 7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：舭潺导师签名：确 签字日期 ：加 7 签字日期：姗z 切 f 摘要 曲线对几种简单网络模型的社团特性进行了分析，发现随机网络所具有的独特社团特 性。i n t e m e t 拓扑的社团结构进行了分析的显示，i n t e m e t 拓扑的模块度在0 4 0 左右，这 表明i n t e m e t 拓扑也是具有社团结构的网络。而当前流行的i n t e r n e t 拓扑模型的模块度大 多小于0 3 0 ，表明了这些模型在社团特性上与真实i n t e m e t 的不符合。 对i n t e m e t 拓扑的社团结构成因的分析发现，处于同一个社团内的a s 大多属于相 同或者邻近的国家，揭示了地理因素是i n t e r n e t 的社团结构形成的一个重要原因。而a s 类型对i n t e m 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 r n e t 连接的倾向性更强。为此设计了一种基于地理演化的a s 级拓扑模型电e o p f p 模型，该模型在建立节点连接时，考虑了地理距离的影响，优先在邻近节点之问建立连 接。实际的实验分析表明，该模型在大多数性质上都能重现i n t e r n e t ，并且具有和i n t e m e t 相接近的模块度，这在某种程度上也验证了本文的结论。 相对于当前的模型，g e o p f p 模型具有明显的优势，可以进一步的应用于与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 m e t a s 级拓扑；社团分析；i n t e m e t 拓扑社团结构；i n t e m e t 地理模型 一i i ， a b s t r a c t t o p o l o g y sc o m m u n i t y i n t e r n e tt o p o l o g y , r e s e a r c ho nt h e p e o p l e sc o n c e r n ，t h ea n a l y s i sa n d m o d e l i n go ni n t e r n e tt o p o l o g yi sap o p u l a rt o p i c t h e r ei sg r e a ta c h i e v e m e n ti n t h i sa r e ai n r e c e n ty e a r sa n dm a n yu n k n o w nt o p o l o g yc h a r a c t e r i s t i c sh a v eb e e nr e v e a l e di nr e c e n ty e a r s h o w e v e r , t h e r ei ss t i l ls o m eb l a n ki nt h i sa r e a , f o re x a m p l e ，c o m m u n i t ys t r u c t u r ei sac o m m o n p r o p e r t yi nm a n yr e a ln e t w o r k s ，b u tt h e r ei s n ta n yr e s e a r c ho nt h ec o m m u n i t ys t r u c t u r eo f i n t e r n e tt o p o l o g y , o rr e l a t e dm o d e l i n gm e t h o d i nt h i sw o r k ，t h ec o m m u n i t yp r o p e r t yo fi n t e m e tt o p o l o g yi sa n a l y z e d ，o nt h eb a s i so ft h e m a s st o p o l o g yd a t ap r o v i d e db yc a i d a f i r s t ，ab a s i ca n a l y s i so nc o m m u n i t yp r o p e r t yf o r s i m p l en e t w o r km o d e l su s i n gm o d u l a r i t yc u r v es h o w st h a tr a n d o mn e t w o r k h a sa v e r ys t r a n g e b e h a v i o r sc o m p a r e dw i t ho t h e rs i m p l en e t w o r km o d e l s a n dt h ea n a l y s i so nr e a li n t e r n e t t o p o l o g ys h o w st h a ti n t e r n e ta s - l e v e lt o p o l o g yh a sam o d u l a r i t ya r o u n do 4 0 w h i c hi n d i c a t e s t h a ti n t e m e ti sa l s oan e t w o r kw i t hc o m m u n i t ys t r u c t u r e ，w h i l ea tt h es a m et i m e ，m o s to ft h e p o p u l a ri n t e m e tm o d e l s m o d u l a r i t yi sl e s st h a n0 3 0 ，i n d i c a t i n gt h e i ri n c o n s i s t e n c ew i t ht h e r e a li n t e m e t t h ea n a l y s i so nt h eo r i g i no fc o m m u n i t ys t r u c t u r eo fi n t e m e tt o p o l o g ys h o w st h a tm o s t a s e si nt h es a m ec o m m u n i t yb e l o n g st ot h es a m ec o u n t r yo ra d j a c e n tc o u n t r i e s ，w h i c hm e a n s t h a tg e o g r a p h i c a lc o n s i d e r a t i o ni sa ni m p o r t a n tc a u s eo ft h ec o m m u n i t ys t r u c t u r ei ni n t e m e t t o p o l o g y t h ei n f l u e n c eo fa sc l a s s e so nt h i sp r o p e r t yi sr e l a t i v e l yw e a k af u r t h e ra n a l y s i so n i n t e r n e tc o u n 仃y - l e v e lt o p o l o g ys h o w st h a tt h es e v e r a lc o m m u n i t i e sc o r r e s p o n dt ot h es e v e r a l c o n t i n e n t si nt h ew o r l d ，w h i c hf u r t h e rs t r e n g t ho u rc o n c l u s i o n c o n n e c t i o nc o s ti s i m p o r t a n ta s p e c tw h i c hs h o u l db ec o n s i d e r e dw h e nd e p l o y i n gr e a l n e t w o r k s b e c a u s eo ft h ec o n s i d e r a t i o nt or e d u c et h ec o s t ，t h ep r o b a b i l i t yt oe s t a b l i s h c o n n e c t i o n sb e t w e e na d j a c e n ta r e a si sr e l a t i v e l yl a r g e an e wm o d e lw h i c hh a st a k e n g e o g r a p h i c a ll o c a t i o ni n t oc o n s i d e r a t i o ni si n t r o d u c e dt om o d e lt h ee v o l u t i o no fi n t e r n e t t o p o l o g y i nt h en e wm o d e l ，w h i c hi sc a l l e dg e o p f pm o d e l ，t h e r ei sm o r ep r e f e r e n c ef o rn e w n o d e st oc o n n e c tw i t hn e a r b yn o d e s a n dt h ee x p e r i m e n ts h o wt h a tt h en e wm o d e li si n c o n s i s t e n tw i t ht h er e a li n t e m e ti nm o s tg r a p hp r o p e r t i e s ，a n dh a sas i m i l a rm o d u l a r i t ya s i n t e m e t ，w h i c hf u r t h e rp r o v e do u rc o n c l u s i o n c o m p a r e dw i t hc u r r e n ti n t e r n e tm o d e l s ，g e o p f pm o d e lh a so b v i o u sa d v a n t a g e sa n dc a n b ef u r t h e ru s e di nt o p o l o g y - r e l a t e dr e s e a r c h e s ，s u c ha sb e i n gu s e dt od e v e l o pam o r ep r e c i s e t l i 东北大学硕士学位论文 a b s t r a c t t o p o l o g yg e n e r a t o r a l s o ，i ti ss i g n i f i c a n tf o rt h ed e v e l o p m e n to fn e x t - g e n e r a t i o ni n t e m e ta n d b e t t e rr o u t i n gp r o t o c o l s k e y w o r d s ：i n t e r n e ta s l e v e lt o p o l o g y ：c o m m u n i t ya n a l y s i s ；i n t e r n e tt o p o l o g y s c o m m u n i t ys t r u c t u r e ；i n t e m e tg e o g r a p h i c a lm o d e l i v r ， 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 目录v 第一章绪论1 1 1i n t e m e t 拓扑研究概述1 1 2i n t e r n e t 拓扑研究的意义2 1 3 本课题的背景2 1 4 论文组织结构3 第二章i n t e r n e t 拓扑社团分析概述5 2 1i n t e m e t 拓扑研究的基本方法5 2 1 1i n t e m e t 拓扑的定义5 2 1 2i n t e m e t 拓扑研究的方法。6 2 2i n t e m e t 拓扑生成模型8 2 2 1 随机图模型8 2 2 2i n e t 模型9 2 2 3a b 模型10 2 2 4g l p 模型lo 2 3 社团分析的基本方法l o 2 3 1 社团的概念1 l 2 。3 2 社团分解算法概述1 1 2 3 3g n 分裂算法一13 2 3 4c n m 快速社团分解算法1 4 2 4 数据的获取及处理方法1 5 2 4 1i n t e m e ta s 级拓扑数据1 5 2 4 2a s 属性数据l6 2 4 3i n t e r n e t 国家级拓扑数据1 7 2 5 小结1 8 第三章i n t e m e t 拓扑的社团特性分析1 9 3 1 网络模块度的定义1 9 3 2 几种简单网络的社团特性2 0 3 2 1z a c h a r y 网络2 0 一v 一 东北大学硕士学位论文 目录 3 2 2 规则网络2 l 3 2 3 随机网络2 2 3 2 4 小世界网络2 3 3 2 5 无尺度网络2 3 3 3i n t e m e t 拓扑的社团特性2 5 3 3 1i n t e m e ta s 级拓扑的模块度2 5 3 3 2i n t e m e t 拓扑模型的模块度2 6 3 3 3i n t e m e t 拓扑模块度增长原因分析2 7 3 4 小结3 0 1 第四章i n t e r n e t 拓扑的社团结构分析31 4 1i n t e r n e t a s 级拓扑的社团结构3 l 4 1 1 社团成员的国家分布统计3 l 4 1 2 社团成员的国家分布分析3 2 4 1 3 社团成员的类型分布情况分析3 4 4 1 4 富人俱乐部与社团结构的关系分析3 5 4 2i n t e m e t 国家级拓扑的社团结构3 6 4 3 分析结果讨论3 7 4 4 j 、结3 9 第五章基于地理演化的i n t e m e t 拓扑模型4 1 5 1 经典的p f p 模型介绍4 1 5 2 基于地理演化的g e o p f p 模型4 1 5 2 1 生成算法4 2 5 2 2 试验分析4 2 5 3g e o p f p 模型的拓扑特性分析4 4 5 3 1 基本属性分析4 4 5 3 2 节点度分布分析4 5 5 3 3 联合度分布分析4 5 5 3 4 聚类系数分析4 6 5 3 5 介度关联性分析4 7 5 3 6 富人俱乐部连通性分析4 8 5 3 7 网络跳数分析4 9 5 3 8 讨论4 9 5 4g e o p f p 模型的意义4 9 5 5 小结。5 0 第六章总结与展望5 1 6 1 本文贡献51 一v i 1 目录 一v i i 一 5l ! ；：； ! ；6 5 7 ， 、 东北大学硕士学位论文第一章绪论 第一章绪论弟一早珀了匕 1 1i n t e r n e t 拓扑研究概述 自然界中存在着的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的 网络由许多节点和连接两个节点的边组成，这里的节点用来表示真实世界中的实体，而 边则代表着实体之间的关系。人们对网络的研究由来已久，最早可以追溯到1 8 世纪伟 大的数学家欧拉对著名“k o n i g s b e r g 七桥问题”的研究。k o n i g s b e r g 是东普鲁士的一个 城镇，城中有一条横贯城区的河流，河中有两个岛，两岸和两岛之间共架有七座桥。两 岸居民经常讨论这样一个有趣的问题：一个人能否在一次散步中走过所有七座桥，而每 座桥只能经过一次，最后返回原地? 这个问题看似简单，但长期以来，小镇上没有任何 一个人能走出这样一条路径。欧拉对这一问题的研究，开创了数学中的一个很重要的分 支图论的研究【lj 。 图论通常只关注于小规模网络的性质，而对于大规模的网络，采用图论作为分析手 段就显得不再适用。而统计物理学则为大规模网络的分析提供了新的思路。复杂网络研 究的发展主要有三个阶段：首先是人们对规则网络的研究，人们最初认为对于真实世界 中的一些关系可以用规则网络来表示；其次是随机网络的发展，这个时候人们采用了一 种新的分析手段来对网络进行建模，在这一时期，同样也有基于随机网络的i n t e r n e t 模 型；而近几年，随着计算机处理能力的飞速发展，科学家们发现，很多真实的网络既不 是规则网络，也不是随机网络，而是具有与以上两种网络截然不同特性的网络。科学家 称这些网络为复杂网络，复杂网络研究的兴起，标志网络研究新纪元的到来【1 】。 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 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 幂律特性的发现 2 】，人们才认识到i n t e r n e t 也是具有某种 复杂特性的网络。 在复杂网络的研究中，网络被抽象成简单的“节点”与“边的集合，这里的“节 点”指的是复杂网络中参与交互的个体，它可以指社会网络中的一个人，也可以指蛋白 质交互网络中的一个蛋白质，对于i n t e m e t ，它指代的是一个路由器( 路由器级拓扑) 或一个自治域( a u t o n o m o u ss y s t e m ，后文将简称a s ，自治系统级拓扑则简称为a s 级 拓扑) ；而网络的“边 则代表着节点之间存在着的一种关系的表示，在不同的网络中 东北大学硕士学位论文 第一章绪论 同样有着不同的含义。通过这种抽象使得可以将i n t e m e t 和其他许多网络一样，都可以 用复杂网络的方法加以研究和探讨。 复杂网络研究的兴起也引起了人们对于i n t e m e t 拓扑研究的广泛关注，并吸引了来 自于不同领域的大量研究人员。一方面，i n t e m e t 作为当今世界上最大的一个人工网络， 是复杂网络研究的一个绝好的对象，因此也吸引了许多的物理学家和数学家对其进行研 究，在最近的几年有大量的相关论文发表在s c i e n c e 、p n a s 、p r l 等国际知名杂志上0 1 ； 而另一方面，工程领域的研究人员同样也关注于该研究，因为他们期望能从i n t e m e t 拓 扑的研究，得到对下一代路由协议的设计及网络基础架构的建设的启示，同样的，近年 在i n f o c o m 、s i g c o m m 、i e e et r a n so nn e t w o r k i n g 等权威杂志或会议上也有大量相 关论文的发表 1 1 19 1 ，足以说明该研究的热点程度。 1 2i n t e m e t 拓扑研究的意义 对于复杂网络及i n t e m e t 拓扑的研究，有以下几个方面的重要的意义 2 0 抛】： ( 1 ) 首先，对于复杂网络的研究，有助于加深我们对于网络本质的认识，并有望 建立一套相关的网络基础理论体系。对于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 的建设是有巨大帮助的。 ( 2 ) 其次，对i n t e m e t 拓扑的理解。可以帮助人们设计更好的i n t e r n e t 路由协议。 人们在最初设计i n t e m e t 协议的时候，并没有考虑网络的拓扑特性，而相同的网络协议 在具有不同拓扑特性的网络上，是否还具有一致的性能表现? 是否可以根据网络的拓扑 特性设计具有针对性的协议? 如何设计网络协议，以使其可以适应网络拓扑的演化? 都 是比较有应用前景的课题。而这方面的研究，已经有许多相关的论文发表。 ( 3 ) 最后，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 m e t 未来的发展也将产生深远的影响。 1 3 本课题的背景 当前的研究者们已经对i n t e m e 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 中，只有少数节点拥有很大 一2 一 ， 、 东北大学硕士学位论文第一章绪论 的度值，而大多数节点拥有很小的度值。目前的分析采用的主要度量方法可以分成几类： ( 1 ) 基本的统计量，比如平均度值、平均聚类系数、网络直径等； ( 2 ) 单个属性的分布，单个属性是与一个节点相关的属性，比如单个节点的度值、 介数、核数等，这些单个属性值的分布就构成了一种度量，比如节点度分布； ( 3 ) 单个属性的关联性，比如度和度的关联性、簇度关联性、介度关联性等； ( 4 ) 针对网络整体的一些度量，比如网络的富人俱乐部系数、网络谱分析及一些 变换分析所得出的结果。这种分类可以涵盖大多数当前所采用的分析方法，当然这也是 很粗略的一种分类。而从基本统计量的计算到网络关联性的分析，人们对i n t e m e t 拓扑 特性的研究越来越深入。 社团结构在复杂网络中是普遍存在的，它指的是在网络中，存在着若干的“群 或 “团”，每个群内部的节点连接非常紧密，而各个群之间的连接则相对比较稀疏，而网 络就是由这些群所组成。很多的实际网络都存在着社团结构，比如社会网络就可以看成 是存在着很多熟人集团的网络，而w w w 也被发现是由大量的网站社团组成，其中同 一个社团内部的各个网站一般都是关于一些类似话题的网站。了解网络的社团结构有助 于人们更深入的认识网络的拓扑性质，对于研究网络的形成和演化也非常的重要。 近来的文章【2 3 通过对i n t e r n e t 局部聚集特性的研究，表明了i n t e m e t 拓扑存在的“聚 团”的性质，初步的拨开了i n t c m e t 社团结构的面纱，然而其研究仅是人为的将i n t e r n e t 划分成几个子图，文 2 3 】也并未说明这种做法的合理性。 本文的研究来源于c a i d a ( t h ec o o p e r a t i v ea s s o c i a t i o nf o r i n t e m e td a t aa n a l y s i s ，一 个对全球范围i n t e m e t 结构及数据进行研究的国际合作机构) 面向i n t e m e t 拓扑测量的 s k i t t e r 项目。东北大学嵌入式技术实验室经该组织授权，成立c a i d a 中国第一节点( n e u n o d e ) ，成为该组织在中国的首家合作伙伴。n e u 节点不仅可以作为探测节点采集i n t e r n e t 拓扑数据，还可以以合作者的身份，获得c a i d a 遍布全球的三十余个探测节点所提供 的权威的、海量的、更新及时的数据。本文基于上面的数据，对i n t e r n e t 拓扑的社团特 性进行了全面的分析，并基于分析结果提出了基于地理演化的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 c m c t 拓扑研究的基本原理。介绍了i n t e r a c t 拓扑的定义，i n t e r n e t 拓扑研究的内容和方法，常见的i n t e r n c t 拓扑数据来源。介绍了复杂网络社团和社团分 解算法。着重介绍了本文所用到的所有分析数据，为后文做了铺垫。 一3 一 东北大学硕士学位论文第一章绪论 第三章对常见网络及i n t e m e t 拓扑的社团特性做了基本分析。首先介绍了模块度的 概念，对几种简单网络的社团特性进行了分析。对i n t e r n e t a s 级拓扑的社团特性进行了 研究，计算了i n t e r n e ta s 级拓扑的模块度和几种i n t e m e t 拓扑模型的模块度，并对i n t e m e t a s 级拓扑模块度随时间的变化做出了简单的分析。 第四章对i n t e m e t 拓扑的社团结构成因进行了分析。着重分析了i n t e m e ta s 级拓扑 的社团结构的成因。对a s 所属国家及a s 类型两方面可能对拓扑社团结构有影响的原 因进行了了分析。对i n t e r n e t 国家级拓扑的社团结构进行了分析。 第五章提出了一种基于地理演化的i n t e m e t a s 级拓扑模型。给出了该模型的设计思 路和生成算法，及相关的实验分析。并对该模型提出的意义做了说明。 第六章为全文的总结，对本文研究工作的意义作出了说明，并指出了进一步的研究 方向。 一4 一 、 ， 概述 e m e t 。接 绍本 实际 的物理连接，i n t e m e t 中的计算机可以在物理层面上构成一种拓扑；而在应用层面上， 比如在p 2 p 应用中，对等节点之间也构成一种拓扑，而这种拓扑与计算机在物理层面上 构成的拓扑是截然不同的。目前所讨论较多的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 路由器级拓扑，指i n t e m e t 中的路由器基于互联关系而构 成的一种拓扑。在该拓扑中的一个节点代表一个路由器，而边则表示两个路由器之间存 在着的连接关系。由于无法收集全球范围内路由器之间的实际物理连接情况，当前的 i n t e r n e t 路由器级拓扑数据的获得通常基于t r a c e r o u t e 类的工具。 t r a c e r o u t e 应用程序是vj a c o b s o n 于1 9 8 8 年开发的，最开始用于观察端到端的路 由连接状况和进行故障诊断。而1 9 9 6 年，j r i c k a r d 提出了利用t r a c e r o u t e 来探测网络 拓扑的设想。c a i d a 的s k i t t e r 2 4 】项目较早的开始了这方面的工作，s k i r e r 于1 9 9 8 年开 始运行，主要就用于探测全球的i n t e r n e t 路由器级拓扑，并进行相关的性能测量。而基 于t r a c e r o u t e 探测到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 中的一个自治系统( a u t o n o m o u s s y s t e m ) ，而图中的边则代表两个自治域之间通过b g p 边界网关协议存在着互联关系， 两个自治域之间可能通过多个边界路由器而有连接关系，但在自治系统级拓扑中，两个 自治系统之间的这种连接只用一条边来表示。 自治系统级拓扑通常由边界网络协议( b g p ) 获得。b g p 代表边界网关协议，是 i n t e m e t 自治域之间的路由协议。r o u t e v i e w s 2 5 】通过7 个不同的节点来收集全球的b g p 路由表。b g p 路由表中包含了不同的a s 路径，通过这些数据，就可以得到全球范围内 a s 之间的连接关系。r o u t e v i e w s 不仅收集静态的b g p 路由表，同时也收集动态的b g p 一5 一 东北大学硕士学位论文第二章i n t e m e t 拓扑社团分析概述 u p d a t e 数据，可以得到更多的a s 之间的连接关系。u c l a 的b e i e h u a n z h a n g 等人，通 过合并各个不同的b g p 数据来源，提供了目前最为完全的i n t e m e t a s 级拓扑数据。 通过t r a c e r o u t e 工具也可以得到i n t e m e t 自治系统级拓扑。这需要将t r a c e r o u t e 探测 到的路由器级拓扑映射到自治系统级拓扑，方法就是通过b g p 表，将相应路由器的i p 地址映射成a s 号，进而得到a s 之间的连接关系。c a i d a 2 6 】和d i m e s 2 7 1 就提供基于 t r a c e r o u t e 工具探测到的的i n t e m e t 自治系统级拓扑。 最后一种获取自治系统级拓扑的方法是通过w h o i s 2 8 】数据库。w h o i s 是一组关于 a s 联接关系的数据库集合，主要用来为网络管理员提供帮助。w h o i s 数据库是手工维 护的。当前公开的w h o i s 数据库中，r i p e 的w h o i s 数据库提供了最多的可靠数据。 当然在这三种数据源中，w h o i s 数据库包含的可用信息最少，并且由于手工维护，无 法保证其能反映最新的网络拓扑，所以本文不再对其进行探讨。 自治系统通常简称为a s ，而自治系统级拓扑则简称为a s 级拓扑。相对路由器级 拓扑，对i n t e m e ta s 级拓扑的研究，人们的关注程度更高一型3 , 2 0 , 2 9 - 3 2 】，本文的分析也 主要集中在i n t e m e ta s 级拓扑上。 2 1 2i 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 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 拓扑有关的研究，主要集中于以下几个方面【2 0 , 3 1 】： ( 1 ) 生成方法：如何有效的生成与真实i n t e m e t 接近的网络拓扑。该拓扑要求具 有一定的随机性，但在大部分拓扑特性上必须与真实i n t e m e t 相一致。而对于生成方法 的研究则包括实际数据的分析及拓扑生成器的设计。 ( 2 ) 仿真研究：鉴于人们对i n t e m e t 拓扑特性的不断深入的理解，采用最新的拓 扑研究成果，对路由协议或者网络应用进行仿真研究，以检验它们是否能在i n t e m e t 类 似的拓扑环境下表现出良好的性能。 ( 3 ) 演化分析：是否能理解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 r n e t 拓扑数据的获取或测量 是i n t e m e t 拓扑研究的一个重要部分【3 3 1 ，这也是当前的一个难点，对于当前拓扑数据的 一6 一 、 ， 、 东北大学硕士学位论文 第二章i n t e r n e t 拓扑社团分析概述 东北大学硕士学位论文第二章i n t e r n e t 拓扑社团分析概述 从图2 1 中可以看到当前的两种主要研究路线：基于图特性的分析和基于演化的分 析。 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 拓 扑进行比较分析。生成方法的研究，也是仿真研究的基础，同时也为演化研究提供重要 的分析思路。本文也主要立足于此。 c a i d a 组织提供的i n t e m e ta s 级拓扑数据，是当前研究领域常用的一个数据源， 具有一定的可靠性。本文以c a i d a 的数据作为分析数据，着重对i n t e m e t 拓扑数据的社 团特性进行了分析，发现i n t e r n e t 拓扑数据存在着明显的社团结构，而当前的模型并不 能反映这一特性，因此就提出了一种新的模型以刻画这一特性。 2 2i 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 m e t 拓扑产生器【l 】。i n t e m e t 拓扑建模是一项复杂的工作，涉及 网络测量、图论、算法设计、统计学、数据挖掘、可视化以及数学建模等多个研究领域。 正是由于其复杂性及高难度，吸引了大量专家在此领域展开研究。至今为止，i n t e m e t 拓扑研究经历了从经验假设到客观分析，从单纯的计算机网络研究到复杂系统特征化研 究的过程，大体上可按时间顺序分为三俐i 】： 第一代为2 0 世纪8 0 年代的随机图生成器【3 4 1 ，在研究早期，由于缺乏真实测量数据 支持，拓扑模型都是研究人员基于经验假设建立的。第二代为2 0 世纪9 0 年代的结构产 生器，如t i e r s ( 等级) 模型【3 5 】和t r a n s i t s t u b 模型【3 6 】。后者是明显的基于层次结构设计思 想的两类拓扑生成器；第三代始于1 9 9 9 年f a l o u t s o s 等人发现i n t e m e t 拓扑结构中存在 幂律( p o w 辨1 a w ) 【2 】从而产生基于网络节点度的拓扑模型与拓扑产生器。 这些拓扑生成算法及拓扑产生器为i n t e m e t 模拟提供了有利的支搏2 2 ，3 7 1 。不过，现 有理论模型大多只能体现网络的部分特征。但新的研究总是建立在已有研究成果的基础 之上，充分吸收已有经验及设计思想，解决现有模型问题，才能提出更优秀的模型。因 此本文下面就