（通信与信息系统专业论文）传统测量与层析成像结合的网络拓扑识别方法研究.pdf

摘要 摘要 传统的网络拓扑识别方法主要是基于各种协议的协作和中间节点反馈的信息 来推测网络的拓扑，但是随着对网络安全性的要求越来越高，得到协议的协作和 中间节点反馈的信息变得越来越困难。基于层析成像技术的网络拓扑识别可以在 不借助路由协议或者中间节点协作的条件下，完成网络拓扑识别，但需要发送大 量的探测包以计算链路的统计特性，计算过程也过于复杂。我们认为：传统网络 拓扑识别方法要求大量的中间路由器配合，这在实际的大型网络中往往是难以办 到的；基于网络层析成像的拓扑识别方法假设所有中间路由器均不协作，增大了 测量工作的难度。在实际的网络中必然存在一些不协作节点，也必然存在一些可 协作节点。因此本文提出了一类传统测量和层析成像结合的网络拓扑识别方法， 能够根据待测网络中协作的中间节点反馈的拓扑信息，加快识别速度和减少发包 量；对于不协作的部分，也能够动态的利用层析成像技术进行拓扑识别。 本文研究了基于协作的传统拓扑识别方法以及基于层析成像的网络拓扑识别 方法，做了三个方面的研究工作： ( 1 ) 在拓扑识别的算法方面，改进并提出了一套新的基于层析成像的拓扑识 别方法。该方法利用“三明治包作为探测手段，通过测量“三明治 包中两个 小包到达目的节点的时间差作为节点对的相似度以推测共享路径长度。该方法包 括基于最小相似度的分层聚类算法以及叶节点的划分算法，叶节点的划分算法又 根据所测拓扑的类型不同分为一般朴树的叶节点划分算法和二叉拓扑树的叶节点 划分算法。该方法使得拓扑识别的计算复杂度大为降低，精确度也有所提升。 ( 2 ) 在拓扑识别的测量方法方面，针对拓扑识别中普通“三明治 包测量方 法存在的问题，提出了t t l 可变的“三明治”包测量方法。普通“三明治包测 量方法只能得到节点对的相似度，然后再利用这些相似度数据去推测节点对的共 享路径长度，这样测得的共享路径长度的精度会受到相似度误差的影响。t t l 可变 的“三明治 包测量方法基于对同一拓扑树发送不同t t l 值的“三明治 包所得 相似度的比较，能够直接获得节点对共享路径准确的长度。该方法使得发包量减 少到只有原来的1 0 ，拓扑识别精确度也得到了很大的提高。 ( 3 ) 结合算法和测量方法的改进，提出一个综合的解决方案，即传统 摘要 t r a c e r o u t e 探测方法和层析成像结合的网络拓扑识别方法。该方法利用 t r a c e r o u t e 从被测网络的协作节点得到网络的部分拓扑信息，并利用初始拓扑构 造算法得到不完整的初始拓扑，然后结合相应的层析成像方法，利用匿名节点处 理算法对初始拓扑中不正确或不完整的部分进行识别，以得到最终拓扑。该方法 不仅可以识别包含不协作节点的网络拓扑，而且进一步减少了发包量，拓扑识别 的准确度也进一步提高。 本文通过n s 2 的仿真证明了这种结合传统测量的拓扑识别方法不仅在算法的 复杂度有所降低，而且发送探测包的数量大大降低，拓扑识别的准确度也有较大 的提升。 关键词：网络拓扑识别，网络层析成像，分层聚类，t t l ，t r a c e r o u t e a b s t r a ( x a b s t r a c t t r a d i t i o n a lm e t h o do fn e t w o r kt o p o l o g yi n f e r e n c ei s m a i n l yb a s e do nt h e c o l l a b o r a t i o no fp r o t o c o l sa n di n f o r m a t i o nf e e d b a c kb yt h et o u t e r s h o w e v e r , i t sm o r e a n dm o r ed i f f i c u l tt og e tt h ec o l l a b o r a t i o no fp r o t o c o l sa n di n f o r m a t i o nf e e d b a c kb yt h e r o u t e r sd u et ot h ed e m a n do fn e t w o r ks e c u r i t y n e t w o r kt o p o l o g yi n f e r e n c eb a s e do n n e t w o r kt o m o g r a p h yc a ni n f e rt h ew h o l et o p o l o g yo fn e t w o r kw i t h o u tt h ec o l l a b o r a t i o n o fr o u t e rp r o t o c o l sa n di n t e r n a ln o d e s h o w e v e r , t h em e t h o do fn e t w o r kt o p o l o g y i n f e r e n c eb a s e do nt o m o g r a p h yo r e nt a k e st o om u c ht i m ei nc a l c u l a t i n gb e c a u s eo ft h e n e e dt os e n dal a r g en u m b e ro fp r o b ep a c k e t st oc a l c u l a t et h es t a t i s t i c a lc h a r a c t e r i s t i c s i no u ro p i n i o n s ，t r a d i t i o n a lm e t h o d so fn e t w o r kt o p o l o g yi n f e r e n c ed e p e n do nt h e f e e d b a c ko ft h er e u t e r s ，w h i c hi so r e nd i f f i c u l tt oa p p l yi nt h ea c t u a ll a r g e - s c a l e n e t w o r k s ；t o m o g r a p h y b a s e d t o p o l o g y i n f e r e n c ea s s u m et h a ta l lr e u t e r sa r e u n c o o p e r a t i v e ，w h i c hm a k et h em e a s u r i n gw o r k m u c hm o r ed i f f i c u l t t h e r ea r en o to n l y c o l l a b o r a t i v er o u t e r sb u ta l s ou n c o o p e r a t i v er o u t e r si nt h ea c t u a ln e t w o r k s t h e r e f o r e ， t h i sp a p e ri n t r o d u c e sam e t h o do ft o p o l o g yi n f e r e n c ec o m b m et h et r a d i t i o n a lm e t h o d so f t o p o l o g yi n f e r e n c ea n dt o p o l o g yi n f e r e n c eb a s e do nt o m o g r a p h y , w h i c hn o to n l yb e a b l et os p e e du pt h ep r o c e s so ft o p o l o g yi n f e r e n c ea n dr e d u c et h en u m b e ro fp a c k e t s a c c o r d i n gt ot h ef e e d b a c ki n f o r m a t i o nf r o mt h ec o o r d i n a t en o d ei nt h en e t w o r k b u ta l s o b ea b l et om a k eu s eo ft o m o g r a p h yt e c h n o l o g yf o rt o p o l o g yi n f e r e n c ed y n a m i c a l l yt o t h en o n - c o l l a b o r a t i v ep a r to ft h en e t w o r k i nt h i sp a p e r ，w ei n t r o d u c et h r e ea s p e c t so fr e s e a r c hr e s u l t st h r o u g ht h es t u d yo n t r a d i t i o n a lm e t h o d so ft o p o l o g yi n f e r e n c ea sw e l la st o m o g r a p h y - b a s e dt o p o l o g y i n f e r e n c e ： ( 1 ) a tt h ea s p e c to fa l g o r i t h m t ot o p o l o g yi n f e r e n c e ，w ei m p r o v et h ee x i s t e d t o p o l o g yi n f e r e n c em e t h o d sa n di n t r o d u c ea n e wm e t h o do ft o p o l o g yi n f e r e n c eb a s e do n t o m o g r a p h yu s i n g “s a n d w i c h ”p r o b e ，w h i c hm e a s u r et h ed i f f e r e n c eo f t h ea r r i v et i m eo f t h et w os m a l lp a c k e t so ft h e “s a n d w i c h ”p a c k e t - g r o u pi no r d e rt oi n f e rt h el e n g t ho ft h e s h a r e dp a t h t h i sk i n do fm e t h o di n c l u d e st h eh i e r a r c h i c a lc l u s t e r i n ga l g o r i t h mb a s e do n t h es m a l l e s ts i m i l a r i t ya sw e l la st h ed i v i s i o no f1 e a fn o d e sa l g o r i t h m t h ed i v i s i o no f i i i l e a fn o d e sa l g o r i t h mc a l lb ed i v i d e di n t od i v i s i o no fl e a fn o d e sa l g o r i t h mf o rg e n e r a l t o p o l o g yt r e ea n dd i v i s i o no fl e a fn o d e sa l g o r i t h mf o rb i n a r yt o p o l o g yt r e ea c c o r d i n g t o t h et y p eo ft o p o l o g y t h i sm e t h o dr e d u c e st h ec o m p u t a t i o n a lc o m p l e x i t ya n di m p r o v e s t h ea c c u r a c ya sw e l l ( 2 ) a tt h ea s p e c to fm e a s u r em e t h o d ，w ei n t r o d u c et h en e w “s a n d w i c h p r o b e b a s e do nt t lv a r i a b l ep a c k e tt os o l v et h ep r o b l e mo fc o i n l n o n “s a n d w i c h p r o b e t h e c o m m o n s a n d w i c h p r o b ei n f e rt h el e n g t ho ft h es h a r e dp a t hb yu s i n gt h es i m i l a r i t y d a t a t h ea c c u r a c yo ft h el e n g t hw i l lb ea f f e c t e db yt h ee r r o ro ft h es i m i l a r i t yd a t a t h e “s a n d w i c h p r o b eb a s e do nt t lv a r i a b l ep a c k e tc a no b t a i nt h ee x a c tl e n g t ho ft h e s h a r e dp a t hb yc o m p a r eo ft h es i m i l a r i t i e sw h i c ha r eo b t a i n e db ys e n d i n g s a n d w i c h p r o b e 、析n ld i f f e r e n t 丌l t h i sm e t h o dr e d u c e st h en u m b e ro fp a c k e t st oo n l y10 c o m p a r e t ot h eo r i g i n a ln u m b e ra n dt h ea c c u r a c yi sa l s og r e a t l yi m p r o v e d ( 3 ) f i n a l l y , w ep r o p o s eac o m p r e h e n s i v es o l u t i o nb yt h ec o m b i n a t i o no ft h e t r a d i t i o n a li n f e r e n c em e t h o d sw i t ht r a c e r o u t ea n d i m p r o v e da l g o r i t h m s a n d m e a s u r e m e n tm e t h o d s t h i sm e t h o df i r s t l yo b t a i n ss o m eo ft h et o p o l o g yi n f o r m a t i o n f r o mt h ec o o r d i n a t en o d e si nt h en e t w o r ka n dt h e np r o p o s e sa l li n c o m p l e t ei n i t i a l t o p o l o g i c a ls t r u c t u r eb yu s i n gt h ei n i t i a lt o p o l o g yc o n s t r u c ta l g o r i t h m f i n a l l y , w eu s e a n o n y m o u sn o d ep r o c e s sa l g o r i t h mt oi d e n t i f yt h ei n c o r r e ：c to ri n c o m p l e t ep a r to ft h e i n i t i a lt o p o l o g i c a ls t r u c t u r et og e tt h ef i n a lt o p o l o g y t h i sm e t h o df b r t h e rr e d u c e st h e n u m b e ro fp a c k e t sa n df u r t h e ri m p r o v e st h ei n f e r e n c ea c c u r a c y u s i n gn s 2s i m u l a t i o n sw eh a v ep r o v e dt h a tt h ec o m b i n a t i o no ft r a d i t i o n a l m e t h o d sa n dt o p o l o g yi n f e r e n c eb a s e do nt o m o g r a p h yn o to n l yr e d u c et h ec o m p l e x i t y a n dt h en u m b e ro fp a c k e t st ob es e n db u ta l s oi m p r o v et h ei n f e r e n c ea c c u r a c yo f t o p o l o g y k e y w o r d s ：n e t w o r kt o p o l o g yi n f e r e n c e ，n e t w o r kt o m o g r a p h y , h i e r a r c h i c a lc l u s t e r i n g , t t l t r a c e r o u t e i v 图形目录 图形目录 图2 1 网络拓扑识别的过程。7 图2 2 端到端测量网络8 图2 3 物理拓扑及其逻辑抽象9 图3 一l “三明治 包发送示意图1 9 图3 - 2 中继设备的接收缓冲区和发送缓冲区2 0 图3 - 3 “三明治包组时间差变大原理解析2 1 图3 - 4 网络的真实拓扑2 3 图3 - 5 第一层分类2 3 图3 - 6 第二层分类2 4 图3 - 7 最小相似度聚类算法流程图2 5 图3 8 叶节点划分算法流程图2 7 图3 - 9 二叉树的叶节点划分算法流程图2 8 图3 - 1 0n s 2 的仿真过程2 9 图3 - 1 1 仿真采用的网络拓扑。3 l 图3 - 1 2 仿真拓扑图一3 2 图3 - 1 3n s 2 中的“三明治包( 1 ) 3 2 图3 - 1 4n s 2 中的“三明治 包( 2 ) ：3 3 图3 - 1 5 节点的划分过程及拓扑树形成3 6 图3 - 1 6 网络重载情况下节点的划分过程。3 9 图4 - 1i p 数据报格式4 0 图4 - 2 “三明治 包发送过程4 2 图4 3 共享路径长度为3 的拓扑树4 3 图4 - 4t t l = i 的等价拓扑4 3 图4 - 5t t l = 2 的等价拓扑4 4 图4 6t t l = 3 等价拓扑与实际拓扑一致4 4 图4 - 7t t l = 4 等价拓扑与实际拓扑一致4 5 图4 - 8 仿真所用拓扑图4 6 图4 - 9 大包在节点1 被丢弃4 6 v i l 图形目录 图4 - 1 0 节点对9 - 1 0 不同t t l 的相似度。4 7 图4 - 11 节点对9 - 5 不同t t l 的相似度。4 7 图4 - 1 2 节点对9 - 6 不同t t l 的相似度4 8 图4 - 1 3 节点对9 - 1 1 不同t t l 的相似度。4 8 图4 - 1 4 节点对1 0 - 5 不同t t l 的相似度4 9 图4 - 1 5 节点对1 0 - 6 不同t t l 的相似度4 9 图4 - 1 6 节点对6 - 11 不同t t l 的相似度5 0 图4 一1 7 节点对6 - 8 不同t t l 的相似度5 0 图4 一1 8 节点对1 1 1 2 不同t t l 的相似度一5 1 图4 1 9 节点对1 2 - 8 不同t t l 的相似度5 1 图4 2 0 节点对不同t t l 值的相似度比较5 2 图5 1 第一类或第二类匿名路由器带来的影响5 6 图5 - 2 第三类匿名路由器带来的影响。5 6 图5 - 3 初始拓扑树构造算法流程图5 8 图5 - 4 匿名节点归并算法流程图5 9 图5 - 5 仿真拓扑6 0 图5 - 6 初始拓扑树。6 1 图5 - 7 进行归并的子拓扑树6 2 图5 - 8 第三类匿名节点的识别6 2 图5 9 节点协作度和拓扑识别所需时间6 3 图5 - 1 0 节点协作度和发送的探测包数量6 3 表格目录 表格目录 表3 - 1 节点对的相似度数据3 3 表3 - 2 叶节点划分结果3 4 表3 3 最小相似度聚类结果3 4 表3 4 叶节点划分结果( 部分) 3 5 表3 5 重载情况下节点对的相似度数据3 6 表3 - 6 重载下叶节点划分结果。3 7 表3 7 重载下的最小相似度聚类结果3 7 表3 - 8 重载下的叶节点划分结果( 部分) 3 8 表5 1t r a c e r o u t e 探测结果6 0 i x 术语表 术语表 凇 a g g l o m e r a t i v el i k e l i h o o dt r e e凝聚似然树 b d t b i n a r yd e l a y - v a r i a n c et r e e二值延迟协方差树 c b rc o 娜t a n tb i tr a t e 固定比特速率 c t c o m p m e r i s e dt o m o g r a p h y 计算机层析成像 d t d e l a y - v a r i a n c et r e e延迟协方差树 f h t ef a s th i e r a r c h i c a lt o p o l o g ye s t i m a t i o n快速分层拓扑结构估计 f i f of i r s t i nf 豳t 0 u t 先进先出 g m mg a u s s i a nm i x t u r em o d e l 高斯混合模型 h t eh i e r a r c h i c a lt o p o l o g ye s t i m a t i o n 分层拓扑结构估计 t t lt i m e - t o l i v e生存周期 i c m pi n t e r n e tc o n t r o lm e s s a g ep r o p e l因特网控制报文协议 o s p f o p e ns h o r t e s tp a t hf i r s t 。 开放最短路径优先 s n m p s i m p l en e t w o r km a n a g e m e n tp r o t o c o l 简单网络管理协议 x 主要符号表 主要符号表 t 拓扑树 v 节点的集合 v i 中间节点的集合 e 边的集合 v r 叶节点集合 p a t h ( i j )从i 节点到j 节点的路径 a n c e s t o r ( i , j )节点i 和节点j 的最近公共祖先节点 c o m m o n _ p a t h ( i j ) 目标节点i 和节点j 的共享路径 l e n g t h ( p a t h ) 路径p a t h 的长度 x i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：廖叠毫 日期：枷7 年石月z 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：套监导师签名：塑呲 日期：2 9 。7 年6 月2 日 第一章引言 1 1 网络拓扑识别研究背景 第一章引言 网络拓扑识别是利用各种测量手段对所关心网络的逻辑拓扑进行推测。随着 网络与人们的生活联系越来越密切，不管是用户还是网络管理人员也越来越关注 网络的性能特征，关注网络服务质量能有多大程度的保障。这一方面要求现代网络 管理系统更完善地发展，更好地控制网络的行为。另一方面要求对网络性能参数进 行精确地检测和方便地调控。为此，学者们开发了各式各样的网络测量系统以测量 和推断网络性能参数的变化。网络拓扑识别是这些网络测量系统的主要基础，同时 也是现代网络管理系统的重要组成部分，在现代计算机网络科学发展中具有十分 重要的地位。 网络拓扑识别是指利用某种算法发现目标网络上的感兴趣的网络元素以及元 素之间的连接关系，并以适当的形式把这种拓扑结构呈现出来。我们所关注的网 络元素因我们的视角不同而有所不同。从这个角度上来说，我们可以把网络拓扑 分为逻辑拓扑和物理拓扑。 传统的网络拓扑识别的方法都是基于协议的协作，根据中间节点反馈的路由 信息来推测网络的拓扑结构。这种网络拓扑识别方法需要中间节点和路由协议的 完全协作。传统的网络拓扑识别方法的好处是：拓扑识别速度快，准确度高，被 测网络负载小。然而随着网络规模的不断扩大和对安全性的要求越来越高，要求 节点间的协作变得越来越困难，因而传统网络拓扑识别方法的应用也变得越来越 困难。 基于层析成像技术的网络拓扑识别方法是拓扑识别领域的新方法，近年来已 经得到了学术界越来越多的关注和研究。相比传统拓扑识别方法，基于网络层析 成像的拓扑识别方法只通过对网络端到端的测量来推测网络拓扑结构。因而基于 层析成像方法最大的优势在于可以不需要中间节点的协作就能完成网络拓扑结构 识别。然而基于层析成像的网络拓扑识别方法本身的缺点也非常明显：由于需要 发送大量的探测包来获取网络的统计特性，因此发包本身就会给被测网络带来很 大的负载；另一方面，由于测量误差的存在，该方法的算法设计和计算复杂度都 电子科技大学硕士学位论文 很高。 传统网络拓扑识别方法的缺陷是要求大量的中间节点配合以及相应的协议的 支持，这在实际的大型网络中往往是难以办到的：基于网络层析成像的拓扑识别 方法假设所有中间路由器均不协作，纯粹采用发送大量探测包的方法，增大了识 别工作的难度。我们认为在实际的大规模网络测量问题中，要求大量的中问路由 器协作是不现实的，假设所有中间节点均不协作也是没有必要的。在网络中必然 存在一些不协作节点，也必然存在一些可协作节点。因此，本文提出了传统测量 和层析成像结合的网络拓扑识别方法，利用中间节点所反馈的不完整的路由信息， 配合基于网络层析成像的主动探测手段，来获得一个精确的网络拓扑结构。 1 2 网络拓扑识别研究现状 网络是一个很好的系统，它有着分工明确又协助良好的体系结构，来完成每 一个信息的传递。就像需要给每一个城市绘制地图一样，从网络诞生的那一刻起， 世界上就有许许多多的学者在研究如何快速而准确的得到一个网络的拓扑。总的 来说，网络拓扑识别算法可分为两大类：基于协议支持的网络拓扑识别方法和基 于网络层析成像技术的拓扑识别方法。 基于协议支持的网络拓扑识别方法假定所有的中间节点都是可协作的，这种 方法研究网络中的协议并挖掘隐藏与这些协议中的网络拓扑信息。这类网络拓扑 识别的方法最早由r s i a m w a l l a ，r s h a r m a 和s k e s h a v 提出【i 】，利用p i n g ， t r a c e r o u t e 以及d n sz o n et r a n s f e r 等技术来探测网络的拓扑。基于协议支持的 网络拓扑识别技术主要是利用网络中的各种协议，首先通过向待测网络发送探测 包来获得网络中的部分端节点和中间节点，然后获取这些节点之间的连接关系， 最后把获取到的节点以及其连接关系构成网络拓扑。根据算法采用的协议的不同 可以将基于协议支持的网络拓扑识别方法分为基于i c m p 协议的方法和基于s n m p 协议【2 】【3 】的方法。目前这类方法研究比较成熟，常用的几个方法包括： ( 1 ) p i n g 与广播p i n g p i n g 操作主要用来检测目的主机是否存活在网络中，它采用异步方式发送和 接收i c m p 应答包。p i n g 通过一个存活的主机大约只需几十毫秒，一个c 类网可在 几秒钟内搜索完毕。但如果该主机关机或在i p 层上不可达，则将耗费较长时间。 广播p i n g 是将i c m p 包发向整个子网，但这种并发发送会增加网络流，甚至会引 2 第一章引言 起网络拥塞而且许多子网并不支持此操作。 ( 2 ) t r a c e r o u t e 可以探索i p 数据报从一台主机发送到另一台目的主机所经过的全部路径。i p 包首部有个t t l 字段( 生存周期) 开始信源发送一个t t l 值为1 的u d p 报文，第 一个路由器收到此报文后，将t t l 值减l 为0 ，便丢弃此报文，同时发回一个i c m p 超时错报文给信源。这样信源得到第一个路由器信息。然后信源第二次发i p 包时， 增加t t l 值为2 ，这样每重发一次时，t t l 值增l ，接收报文的路由器先将t t l 值 减1 ，若t t l 值不为o ，则继续向路由器的下一跳转发；若值为o ，便丢弃该报文， 并向源主机发送i c m p 超时应答报文，源主机便记下该路由器信息，在到达最终目 的主机时，返回信源一个i c m p 端口不可达报文。以此逐步探索可得到域内全部路 由器拓扑信息。 ( 3 ) d n s 的z o n et r a n s f e r i p 网络中每个节点有唯一的i p 地址，d n s 中包含有每个主机名字与i p 地址 转换表，z o n et r a n s f e r 4 】命令可以很快地发现域内主机和其它网络设备的名字， 通常它与广播p i n g 或t r a c e r o u t e 工具结合使用，搜索子网内的主机和设备或作 为其它发现算法的起点。这种技术简单快捷，但是出于安全考虑，有些d n s 服务 器并不提供这种工具。而且d n s 数据库存储数据是静态的，它不能随时更新，所 以信息有时并不准确。 网络拓扑识别的层析成像方法假定所有中间节点都是不协作的，通过发送端 到端的探测包，收集并分析探测包的统计特征( 如时间差的平均值，方差，以及 丢包率等) ，推测网络拓扑。r a t n a s a m y 5 】和d u f f i e l d 6 】等人在这种方法的研究上面 做出了先驱工作。他们主要识别网络的逻辑拓扑。网络的逻辑拓扑结构是只反映 不同路径的节点的物理拓扑的一种抽象。换句话说，一个只有单个入口和出口的 节点被抽象成连接相邻节点的链路。通过由源节点向目的节点端到端的发送探测 包计算在共享链路上的丢包率。他们利用向节点对广播发送多包组的方法收集共 享链路的丢包率信息，利用d b t 算法( d e t e r m i n i s t i cb i n a r yt r e e c l a s s i f i c a t i o na l g o r i t h m ) 实现二元逻辑状拓扑的识别r 7 1 。这个收敛算法选择一 个在共享链路上丢包最严重的节点对，然后将它们连接到一个新的父节点。然后 这个父节点将作为叶节点来代替原始的叶节点。两条新加的链路丢包也将重新计 算。这个过程不断的迭代只到最后只有一个叶节点。目前所有的收敛算法都和d b t 采用的方法类似。d b t 算法同样被用来利用多包组时延等测量度量的拓扑识别。 电子科技大学硕士学位论文 c a s t r o 8 】等人在单播网络测量方面提出很大改进，他们提出了一种利用共享链 路队列延迟的s a n d w i c h 探测方法，s a n d w i c h 包由中间的一个大包和两个小包组成， 大包和小包的目的节点不同。第二个小包在他们分开之前总是在队列中排在大包 后面。这个链路测量等同于共享链路上的队列延迟。c a s t r o 还提出a l t 算法 【9 】( a g g l o m e r a t i v et r e ea l g o r i t h m ) 实现拓扑重构，将d b t 进行修改以适应测量值 在概率密度函数( p r o b a b i l i t yd e n s i t yf u n c t i o n ) 上的分布。为使此方法不用 设定门限并适用于一般树结构，c a s t r o 等人继而提出了反转跳马尔科夫链蒙特卡 洛( r e v e r s i b l ej u m pm a r k o vc h a i nm o n t ec a r l o ) 算法进行最大似然估计的拓 扑识别【8 】，通过插入和删除节点建立一个侯选树，能够得到最大似然的候选树将作 为估计的结果。 m e n g f us h i h 等人通过建立有限混合模型【1 0 】获得“s a n d w i c h 包对均值的时 延差分布，进而采用图聚类【l l 】的方法获得网络拓扑结构。不同于以前的用启发式 ( h e u r i s t i c ) 或蒙特卡罗方法( m o n t e c a r l o ) 先估计一个二叉树然后扩充为普 通树，他们的方法直接估计一个普通树。方法的核心是把问题抽象成一个基于节 点对相似度测量的叶节点分层聚类问题。中间的每个节点代表了一个特定的聚类 团，这个聚类团里的叶节点有一个共同的祖先节点。并将在同一个类( c l u s t e r ) 里的节点称为类中( i n t r a - c l u s t e r ) ，将不再同一个类的节点称为类间 ( i n t e r c l u s t e r ) 。一对叶节点的相似度可以用和共享路径( 从根节点到两个叶 节点最近代共同的祖先节点的路径) 相关联的单调函数表示。任何可以准确估计 不同相似度度量的方法都可以用在这里。有三种不同的端到端的相似度度量方法： 使用三明治包测量的队列延迟( q u e u i n gd e l a y ) ，使用背靠背包( p a c k e tp a i r s ) 的延迟的方差( d e l a yv a r i a n c e ) 和使用背靠背的丢包率( 1 0 s sr a t e ) 。修改节 点对相似模型引入每个节点对最近的祖先节点对先验分布( p r i o rd i s t r i b u t i o n ) 。 推出一个有限混合模型，当中每个混合成份对应单源树中的一个中间节点。对由 中间节点和中间节点子节点分割的后代叶节点，混合模型中有最小均值的混合成 份对应类间( i n t e r c l u s t e r ) 的叶节点对。将这个成份叫做类间成份 ( i n t e r c l u s t e rc o m p o n e n t ) 。为了定义一个分类的相似度将每个类中的叶节点 分为类间对( i n t e r c l u s t e rp a i r s ) 和类中对( i n t r a - c l u s t e rp a i r s ) 等组合。 这个相似度表示为类间相似度和类中相似度的乘积。每个类中相似度符合有限混 合模型，类间相似度由类间成份决定。 相对于传统的拓扑识别方法，网络拓扑识别的层析成像方法存在的主要问题 4 第一章引言 是：由于假设中间所有路由器节点均不协作，造成探测包发送数量过多、求解不 稳定、多解性强等缺陷，严重影响了方法的实用性。 1 3 本文的研究内容与创新点 本文的研究内容是网络拓扑结构的识别算法，包括基于协议支持的网络拓扑 识别算法和基于网络层析成像技术的拓扑识别算法。本文的研究重点放在基于网 络层析成像技术的拓扑识别算法上面。 本文的研究内容包括以下几点： 第一，研究了基于传统测量的网络拓扑识别方法。t r a c e r o u t e 是基于传统测 量的网络拓扑识别方法中最典型的方法，如果待测网络上存在一些不协作的节点 匿名路由器，那么基于t r a c e r o u t e 的网络拓扑识别方法在识别这些节点方面 将遇到很大的困难。本文着重研究了匿名路由器给网络拓扑识别带来的影响以及 如何解决基于t r a c e r o u t e 的网络拓扑识别方法在遇到匿名路由器时面临的困境。 第二，研究了基于网络层析成像技术的网络拓扑识别方法，包括了拓扑识别 方法的算法以及测量方法的研究。在算法方面，本文研究了在单播网络上利用探 测包的时延特性以及丢包率特性推测网络拓扑的算法。在测量方法方面，本文着 重研究了“三明治 包探测技术以及如何将其更好的应用于网络拓扑识别的算法 中。 本文的研究工作及创新点包括以下几点： 第一，在拓扑识别算法方面，本文研究了前人利用网络层析成像的探测方法 以及利用图聚类算法来进行网络拓扑识别的技术，提出一系列改进的算法来实现 利用最小相似度分层聚类的网络拓扑识别方法。其核心思想包括：( 1 ) 分层次的 节点划分，即算法是一个递归的节点划分算法，只针对当前树的分支节点对叶节 点进行初步的划分，然后再对每个划分构成的树递归调用该算法进行划分。( 2 ) 最小相似度聚类算法，这个算法根据类内部离散程度变化的思想，用于得到具有 最小相似度集合。 第二，在拓扑识别的测量方法方面，针对拓扑识别中普通“三明治 包测量 方法存在的问题，提出了t t l 可变的“三明治 包测量方法。普通“三明治包 测量方法只能得到节点对的相似度，然后再利用这些相似度数据去推测节点对的 共享路径长度，这样测得的共享路径长度的精度会受到相似度误差的影响。t t l 可 电子科技大学硕士学位论文 变的“三明治一包测量方法基于对同一拓扑树发送不同t t l 值的“三明治包所 得相似度的比较，能够直接获得节点对共享路径准确的长度。具体方法是：设置 “三明治 包中大包的t t l 值，从t t l = i 开始，依次向目标节点对发送大包t t l 值 以1 为单位依次递增的“三明治 包，比较不同t t l 值下的相似度，以得到一个 精确的共享链路层次数。该方法使得发包量减少到只有原来的1 0 0 , 6 ，拓扑识别精确 度也得到了很大的提高。 第三，结合算法和测量方法的改进，提出一个综合的解决方案，即传统 t r a c e r o u t e 探测方法和层析成像结合的网络拓扑识别方法。该方法利用 t r a c e r o u t e 从被测网络的协作节点得到网络的部分拓扑信息，并利用初始拓扑构 造算法得到不完整的初始拓扑，然后结合相应的层析成像方法，利用匿名节点处 理算法对初始拓扑中不正确或不完整的部分进行识别，以得到最终拓扑。该方法 不仅可以识别包含不协作节点的网络拓扑，而且进一步减少了发包量，拓扑