（计算机软件与理论专业论文）网络自拓扑（多子网）算法研究与实现.pdf

摘要 摘要 网络拓扑发现技术已经广泛地应用在各种项目软件中。然而，随着网络结构 复杂度升级，这给拓扑发现带来了挑战。所以我们越来越需要一种高效，准确的 网络拓扑算法自动发现网络拓扑结构。目前的拓扑算法主要集中在：( 1 ) 路由层 的发现。这个层面的发现算法在技术上比较简单，只需要寻找路由与路由之间， 或路由端口与子网之间的连接关系，利用路由器的自身特性，很容易实现。( 2 ) 链路层的发现。直到目前为止，已有的厂商工具难以准确发现网络拓扑，己发表 的理论文献知识也只是理论上阐述，实际应用难度比较大。 本论文认真分析了链路层拓扑的重要性、现状以及进一步研究链路层拓扑的 意义，讨论了网络拓扑发现模型，重点阐述了伪装网络包源地址、探测包、减低 块成熟度、辅助结构树等在网络拓扑算法中应用到的四项关键技术。 本文基于网络拓扑中的关键技术，提出了基于链路层的o t i ( o u t s i d e t o i n s i d e ) 网络拓扑算法，并给出了算法的伪代码及其描述，最后通 过仿真模拟，对算法进行分析与对比。结果表明，本文提出的算法与相关文献中 拓扑技术比较，主要具有准确性更强，网络负载低，实用性更好的特点。 最后，对研究工作做了总结，并对下一步工作做了展望。本论文0 t i 算法对 网络自拓扑算法的进一步研究有一定的参考意义。 【关键词】信任节点、悬挂弧、共享段、块、连接域、成熟度 a b s t r a c t a b s t r ac t t o p o l o g yd i s c o v e 巧s y s t e m sa r es t a n i n gt o b ei n t r o d u c e di nt h ef o r mo fe a s i l y a n dw i d e l yd e p l o y e ds o r 、v a r e h o w e v e r ，r o d a y si pn e t w o r ki sc o m p l e xa n d d y n a m i c k e e p i n gt r a c ko ft o p o l o g yi n f o n n a t i o ne m c i e n t l yi sad i f j e i c u l tt a s k s o ，、v e n e e da ne 矗 e c t i v ea l g o r i t l nf o ra u t o m “c a l l yd i s c o v e 巧i n gp h y s i c a ln e t w o r kt o p o l o g y e a u r l i e r 、o r kh a st y p i c a l l yf o c u s e do n ：( 1 ) l a y e r - 3 ( n e t w o r kl a y e r ) t o p o l o g y w h i c hc a n o n l y d i s c o v e rr o u t e r t o r o u t e ri n t e r c o n n e c t i o n sa 皿dr o u t e ri n t e r f a c e - t o - s u b n e t r e l a t i o n s h i p s t h i sw o r ki sr e l a t i v e l ye a s y 锄di t c a nb ed o n eb yl o t so fs y s t e m s e x i s t i n g ( 2 ) l a y e 卜2 ( 1 i n kl a y e r ) ，t i l ln o w ，n ot o o l sc a i ld i s c o v e rt h en e t w o r kt o p o l o g y e x a c t l yd u e t op o o ra l g o r i m mp e r f o n n a n c e a r e ra 1 1 a l y z i n gt h ei m p o i r t a j l c ea i l dr e c e n ta d v a n c eo ft h el i n l ( 1 a y e r t o p o l o g y d i s c o v e r y ，t h i st h e s i sf o c u s e do ne l a b o r a t i o no ft 1 ek e yt e c l l n i q u e su s e di n a u t o n e t w o r kt o p o l o g yd i s c o v e r y ，s u c ha sd i s g u i s i n gt h es o u r c ea d d r e s s ，p r o b i n gp a c k e t s ， l o w e rt h em a t u r i t ya n dt h ea s s i s t a n tt r e e b a s e do nt h o s ek e yt e c h n i q u e s ，a no t i ( o u t s i d e t o i n s i d e ) a l g o r i t h mo fal i n k l a y e rt o p o l o g yd i s c o v e r yi sp r o p o s e di nt h et h e s i s ，i t sp s e u d oc o d ea l o n gw i t ht h e d e t a i l e dd e s c p t i o ni sa l s og i v e n b ye x p e r i m e n t 、v o r k ，t h es i m u l a t i o nr e s u l t ss h o w e d t h es c h e m es u c c e s s f u l l yi n f e r st h ec o m p l e t et o p o l o g yi nt h ev a s tm 面o r i t yo ft h ec a s e s f i n a l l y s o m ec o n c l u s i o n sw e r ed e n v e d t h er n u r ew o r ki nt h i sa r e aw a sa l s o p o i m e do u t t h es t u d y i ss i g n i 矗c a n tt on e t w o r ks e c u r i t yr e s e a r c h 【k e y w o r d s 】 t r u s t - n o d e ，a p p e n d a r c ，s e g m e n t ，b 1 0 c k ，l i n k f i e l d ，m a t u r i t y 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： ( 注：手写亲笔签名) 学位论文使用授权说明 如净驴月，日 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ： ( 注：手写亲笔签名 沁f 口b 月cc 7 日 第一章绪论 1 1研究背景 第一章绪论 e t h e m e tl o c a la r e a n e t w o r k s ( l a n s ) 是指在一个区域内将不同的网络设备 通过传输电缆连接起来，实现网络资源共享的网络。但是由于网络设备种类众 多，而且同类产品产自不同厂家也会有各自的产品特性，网络管理员要能够高 效管理维护日益膨胀、复杂的网络已经变得十分困难。因而需要一种高效、准 确的网络拓扑发现技术，尽可能真实地反应不同设备之间的物理连接关系。 但是，根据目前已有的厂商工具和国内外研究者的理论研究文献，不难发 现网络拓扑算法主要集中在：( 1 ) 路由层的发现。这个层面的发现算法在技术上 比较简单，只需要寻找路由与路由之间，或路由端口与子网之间的连接关系， 利用路由器的自身特性，比较容易实现。( 2 ) 链路层的发现。直到目前为止，已 有的厂商工具很难准确发现网络拓扑，已发表的理论文献知识也只是理论上阐 述，实际应用难度比较大。 在链路层，设备之间的物理连接关系比较复杂，综合考虑，要准确发现网络 拓扑结构存在以下几个难点： 第一，二层网络设备的透明性。二层拓扑困难其原因是多方面的，主要是 建立这些网络十分容易。因为交换机可以透明地连接，甚至于插上线缆就可以 建立一个局域网。而这种连接的简便性使得局域网对网络管理软件都是透明的。 但这并不意味着第二层发现功能将无所作为。关键基础设施的厂商们已经开发 出了自有的发现协议，可将数据存储于s n m p i l j ( s i m p l en e t w o r km a n a g e m e n t p r o t o c o l s ) 企业版，例如c i s c o 公司的c d p 协议( c i s c od i s c o v e r yp r o t o c 0 1 ) 、 e x t r e m en e t w o r k s 的e d p 协议( e x t r e m ed i s c o v e 巧p m t o c 0 1 ) 、e n t e r a s y sn e t w o r k s 的c d p 协议( c a b l e t r o nd i s c o v e r vp r o t o c 0 1 ) 以及n o n e ln e t w o r k s 的n d p 协议 ( n o n e ld i s c o v e r yp r o t o c 0 1 ) 等。这罩的一个明显问题是，这些协议都不能工作 在混合厂商设备集成的网络环境下。2 层网络设备交换机、网桥、集线器等与 终端的主机或上层的路由设备都是直接互联，而且设备不记录相邻的设备信息， 仅有二层交换机上维护着一张表，记录着接收的数据包应该从哪个端口转发出 去，这张表即为a f t ( a d d r e s sf o n a r dt a b l e ) 。 第二，二层网络中设备缺乏统一的标准。2 层网络中存在哑元设备，所谓 哑元设备是指有些设备通过s n m pb r i 姑em i b ( m a n a g e m e n ti n f o h n a t i o nb a s e ) 0 2 j 很难实现获取a f t s 信息，甚至不支持s n m p ；有些设备比如集线器( h u b ) ， 河海大学硕士学位论文 不具有类似于交换机的”智能记忆”能力和”学习”能力，它也不具备交换机所具 有的m a c ( m e d i aa c c e s sc o n t r 0 1 ) 地址表。所以要想发现网络中这些设备，是网 络拓扑算法设计的一大挑战。 第三，多子网网络结构。目前的l a n s 都支持划分多子网，在同子网内 的设备可以直接通讯，不需要经过路由器。而不同子网内的设备之间通讯需要 经过路由器数据转发( 即使物理上是直接连接) 。同一个设备也可能属于多个子 网。 由于这些困难所在，因此，网络拓扑发现也称为网络的第二层( 链路层) 拓 扑发现。网络拓扑信息对于网络性能监测与评估、故障发现与定位、资源分配 与管理等一系列维护工作具有重要的实用意义。 1 2 研究现状 从2 0 0 0 年开始，国内外研究人员开始对交换式以太网的物理拓扑发现进 行了较为深入的研究。在标准制定方面，2 0 0 0 年9 月，i e t f 发布了关于物理拓 扑m i b ( p t o p o m i b ) 的r f c l l j 用于指导网络层以下拓扑结构的发现。它定义 了标志网络端口之间连接和发现s n m p 代理的网络地址的统一标准。该i u c 没有规定物理拓扑的发现机制。它需要拓扑发现方法来完成相关m i b 变量的 填充。在发现方法方面，研究人员提出了基于交换机生成树( s p 姗i n gt r e e ) 的 算法【3 6 1 、基于地址转发表( a d d r e s sf o n a r d i n gt a b l e ，a f t ) 的算法【7 9 1 。由 于交换机一般均采用地址转发表进行数据帧的转发，基于地址转发表的算法成 为目前适用范围最为广泛的通用方法。 从目前国内外文献来看，主要有以下三种网络拓扑发现方法，不加特殊说 明。下面所提到的网络拓扑均是指网络物理拓扑。 1 2 1基于生成树信息的方法 为了保证节点间能够正常通信，避免广播风暴的发生，交换式以太网的拓 扑结构必须是树型的；然而为了提高网络的可靠性，网络管理员有时会在局域 网段之间设置并行的两条或多条路径，这就会在拓扑结构中产生回路。交换机 之间会通过协商( 如使用文献 3 】中生成树协议) 阻塞部分路径保证整个网络拓 扑是一个树型结构。这就是生成树。交换机生成树信息可以从a f t 表中的 d o t l d s t pm i b 组1 4 j 中获取。国内外研究人员提出了多种方法利用生成树信息发 现局域网的网络拓扑。这些方法在基本原理上是一致的，均是利用生成树中的 根端口、指派端口及指派网桥之间的关系确定交换机之间的连接关系。比较有 代表性的有李涛等人提出的方法【5 】和m y u n g h e es o n 等人提出的方法l6 。文 第一章绪论 献 6 指出，利用生成树信息可以发现网络中的备用链路信息。下面以文献【6 】为 例说明如何采用生成树信息构造网络拓扑结构。图1 一l 是一个带有备用链路的 网络拓扑结构，运行生成树协议后，网桥c 的( c ，2 ) 端口被阻塞，形成了以网桥 旦为根的一棵树；( c ，2 ) 端口被阻塞后，不会发送任何数据包，并且丢弃除s t p b p d u ( b r i d g ep r o t o c o ld a t au n i t ) 之外的任何数据包。 i 图1 1 带有备用链路的拓扑结构 文献 6 给出了网桥连接定理。对于网桥彳和b ，如果( 彳，f ) 端口有一个指 派网桥b ，则彳和b 直接连接在一起。利用这个定理，文献【6 】给出了建立网桥 之问连接关系的方法。以图1 1 为例，端口( b ，1 ) 的指派网桥是彳，指派端口是 ( 彳，1 ) 。根据定理可以判断出( b ，1 ) 和( 彳，2 ) 相连；同样可以判断出( c ，1 ) 和( 么，2 ) 相 连。上述方法对于阻塞端口( c ，2 ) 同样适用。它的指派网桥是b ，指派端口是 ( b ，2 ) 。因此可以判定( c ，2 ) 和( b ，2 ) 相连。对于端口( b ，3 ) 和( c ，3 ) ，由于连接 的不是网桥设备，不参与生成树协议，要想判断这些端口的连接关系，必须借 助于地址转发表。基于生成树信息的方法的优点在于时间和空间消耗较小，可以 发现局域网中的备用链路；缺点是许多交换机不支持生成树协议，适用范围受 到一定限制，并且该方法不能发现交换机与主机之间的连接关系。 1 2 2 基于地址转发表的方法 在每个交换机上都维护着一张表，记录着接收的数据包应该从哪个端口转 发出去。这张表就是地址转发表。忽略掉与拓扑发现无关的信息，地址转发表 河海人学硕上学位论文 的记录格式可以简单地表示为一个二元组：( p d 力，慨) 。其中：助力称为转发端 口；胁c 称为转发地址。地址转发表通过超时老化机制把一段时间内没有用到 的转发条目删除掉。交换机4 的地址转发表中关于f 拌端口的m a c 地址集合记 为只p 只，是交换机从f 拌端口收到的所有数据帧的源m a c 地址。如果只，包 含了；菇端口能够收到的所有数据帧的m a c 地址，称e ，是完全的或完整的。地 址转发表信息可以从d o t l d t pm i b 组中获取。 1 2 2 1 基于完整的地址转发表 yb r e i t b a n 等人【9 1 提出了一种根据完整的地址转发表信息确定交换机端 口之问直接连接关系的算法。由图1 2 可以观察到，如果易：和b 均是完整 的，即只，2 = b ，d ，e ) ，圪，。= 彳，c ，f ) ，则b ，2n 最，。= 1 2 f ，e 2ub ，。= ( n 为全 集) ，即图1 2 中所示，这并不是偶然的。因为如果两个交换机的端口，如( 彳，2 ) 和( b ，1 ) 直接连接，中间没有任何其他设备，那么以相连处为中线，网络中的设 备可以划分成两部分：一部分在端口( 彳，2 ) 所对的一侧，即乃：；另一部分在端 口( b ，1 ) 所对的一侧，即吒，。所以，e ：u 磊1 = 。该命题的逆命题也成立。 日，= 日，d ，量) 只，= f ) 最l = 4 c 毋 最，= d 兄：= ( 量 足1 = 4 丘d ，噩j - f d i = 4 日，c ：量，f 最l = 4 且ed ，f 耳= ( 4 ，且cd ，日 图1 2 地址转发表 文献【6 】中提出直接连接定理。如果乃，和磊y 均是完整的，那么交换机端口 第一章绪论 ( 彳，工) 和交换机端口( j 6 f ，y ) 直接相连的充要条件是兄，n 尼，= a 且e ，u 毛，= ( n 是全集) 。根据直接连接定理，可以遍历局域网中交换机的地址转发表，对 不同交换机端口的转发集执行并操作的结果为全集且交操作的结果为空，则这 两个端口就是直接连接的。直接连接定理只适用于单子网的拓扑发现。比如在 图1 3 中，么、b 、c 、d 是交换机，蜀、r 是路由器，爿、d 、r 属于同一个 子网m ，b 、c 、恐属于另一个子网2 。e ，：n ，。= g 且巴，：u 晶，。= j。根 据直接连接定理，爿和d 应该直接相连，实际上并非如此。 日- = r i ) 乃，= d 见= 似足 五，= ( cd 兄。= 墨) 尼i = 4 且，r ，r ， 耳2 = d 昂t = 4 丑 图1 3 多子网拓扑 在单一子网中，任一交换机的地址转发表均包含网络内其他所有节点的地 址。对于多子网拓扑来说，一个交换机肯定包含自己所属子网的其他节点，也有 可能包含其他子网的节点。多子网拓扑中交换机的地址转发表具有如下性质： 假设彳和口是两个分属于不同子网的节点，包含b 当且仅当满足如下条件：存 在一个与b 属于同一子网的节点c ；在生成树上有一条路径且，彳，c 【6 1 。 2 0 0 3 年，贝尔实验室的y i g a lb e j e r a n o 等人在i n f o c o m 2 0 0 3 上首次提 出了基于完整的地址转发表的多子网拓扑发现算法【8 j ，并证明了该方法是完备 的。该方法首先根据地址转发表和子网信息构造出不同节点之间的粗略路径 ( s k e l e t o np a t h s ) ；然后进一步为每一条路径构造出一组路径约束( p a t h c o n s t r a i n t s ) ，利用路径约束信息不断细化s k e l e t o np a t h s ；最终确定一条唯一的 路径。该算法用初始s k e l e t o np a t h s 集合q 来表示可能的网络拓扑；然后对q 进行递归的细化，从而提供更为精确的拓扑信息。计算初始q 由过程 i n i t s k e l e t o n p a t h s 完成，然后算法进入一个迭代的s k e l e t o np a t h 细化过程。其核 河海大学硕+ 学位论文 心思想是使用路径约束信息把每一个q ，q 中的内部子集u 进一步划分成更 小的子集，直到可以获得一个完整的端口顺序或不能进一步细化为止。路径细 化工作通过两个关键过程来实现：c o m p u t e c o n s t r a i n t s 过程用于计算路径约束 集s ；r e n n e p a t h 过程使用约束集s 进一步细化q ，。 1 2 2 2 基于非完整的地址转发表 基于完整地址转发表的拓扑发现算法必须解决如何保证地址转发表的完整 性。在实际网络中，由于：a ) 地址转发表老化机制的存在，每隔一段时间交换 机就会把没有用到的转发条目从地址转发表中清除出去；b ) 地址转发表长度 的限制，对于一个大规模网络，地址转发表不能容纳网络内所有节点的地址；c ) s n m p 采用无连接的u d p 进行通信，不能提供可靠的数据传输，在采集地址 转发表时可能会丢失一些数据。因此，交换机地址转发表的完整性是难以保证 的。 为了克服上述缺点，威廉玛丽学院的b r u c el o w e k 锄p 1 9 】提出了一种利用 非完整的地址转发表就能判断交换机直接连接的方法。该方法的基本思想是利 用反证法排除不可能的连接关系。首先假设交换机a 和b 通过某两个端口间 接连接；然后判断该连接是否与交换机彳、b 的a f t 中已有信息相矛盾。如 果找不到矛盾，则这个连接是可能存在的；如果矛盾，则这条连接是肯定不存 在的。 文献 9 引入了通过集概念：交换机爿上端口石的通过集( 用l ，表示) 是 指该交换机上除去x 以外的其他端口地址转发表的并集。并给出了间接连接定 理，对于交换机彳、曰，如果两个交换机仅有一对端口( 彳，x ) 和( 8 ，y ) 的通过集 相交为空，即l ，n ，= 乃，则这对端口必然相连；如果这对端口相连，则 兀+ ，n 乃，= a 。利用这种方法判断交换机之蒯的连接关系并不需要交换机端口 的转发集是完整的，只要已有信息能够排除掉所有不存在的连接关系就足够 了。 文献【9 】利用非完整地址转发表就可以把整个网络拓扑构建出来，大大弱 化了拓扑发现的条件。这在实际环境中更具有应用价值，是基于地址转发表的 拓扑发现算法的一个大的进步。但是所提出的方法还存在一定问题，在对m k r 规则必要性的证明中，把“两个节点只有一对端口的通过集交集为空”错误地 等价于“两个端口间接连接”。m k r 规则给出的是基于两个节点的地址转发表 推导两者连接关系的充分必要条件。该规则不能利用多个( 大于两个) 节点的 6 第一章绪论 地址转发表推导连接关系，如 a u c l ，c 2 b v ) 】a u b v 这样使用传递律i 的推 导。在该推导中用到了ab 和c 三个节点的转发表。再举一个复杂的例子( 图 1 4 ) ，要推导爪口之间的连接关系，也必须用到节点爿、口和c 的地址转发表。因 此m k r 规则具有一定的局限性，它不是一个完备的方法。 m d 譬 燕| i b x c 1 d x 舀2 e x b l c 譬 c 2 三i 图1 4 基于多个节点的转发表推导连接关系 文献 1 1 】提出一个称为连接推理技术( c o m l e c t i o n sr e a s o n i n gt e c h n i q u e ) 的谓词逻辑推理方法推导节点问的连接关系。该方法把交换机地址转发表翻译 成一组谓词公式，把拓扑发现问题转变为一个谓词逻辑推理的数学问题，借助 数学工具对拓扑发现问题进行研究。交换机s 的一个地址转发条目( p ，d ) 可以 表示为一个三元组( s ，p ，d ) 。所有交换机的地址转发表构成一个三元组( s ，p ，d ) 的 集合。用四元谓词l i n l ( ( 彳，j ，曰，_ y ) 表示设备a 的x 端口和设备b 的y 端口问接 相连，简记为a x b y 。其中a ，b ，x ，y 都是变元。因此三元组( s ，p ，d ) 可以表示为 l i n k ( s ，p ，d ，j ) 。地址转发表的三元组集合可以表示为一组谓词公式的集合 ( f o 肌u l a ss e t ，f s ) 。地址转发表和谓词公式集两者是等价的、一一对应的关系， 因此可以抛丌地址转发表，从谓词公式集出发，推导设备之间的连接关系。连接 推理技术( c o r u l e c t i o n sr e a s o n i n gt e c l u l i q u e ，c i 汀) 由一组的基本推理规则组成。 但是需要下一步继续研究，并证明该方法的正确性和完备性。 上面提出的两种方法均可以应用于多子网的拓扑发现。它们需要计算任意 一对节点之间的连接关系，计算量比较大。 本文提出了基于o t i ( o u t s i d e t o i n s i d e ) 算法，以无向树为抽象模型，利 用伪装数据包源地址、探测包、降低块成熟度和辅助树存储结构等技术，由外 向内地拓扑发现，提高网络拓扑的准确性、效率，降低网络负载，特别是在处 理亚元设备和h u b 等设备的环节上，发现准确率可达到9 2 以上，这些在本文 中都有具体阐述。 7 河海大学硕士学位论文 1 3论文内容 1 网络拓扑的研究背景及其研究现状。 2 建模：针对目前网络以及网络中的设备的特性，把实际网络抽象成图论 中具有拓扑性质的网络图原型。 3 重点详细介绍伪装数据包源地址、探测包、降低块复杂度和辅助结构树存 储技术。 4 基于四个关键技术，具体阐述网络拓扑o t i 算法。 5 网络拓扑o t i 算法仿真与算法的正确性、复杂度分析。 6 算法总结与迸一步研究工作。 1 4 论文组织 论文共分五章。 第一章绪论：主要介绍选题的背景、研究现状及存在问题，然后针对性地 导出论文的内容，以及在此领域中的贡献。 第二章相关定义与网络拓扑模型：主要分析网络中的各种类型的设备对 象，以及网络结构这个f r a m e ，以物理对象为模型，彻底抽象成具有拓扑性质 的网络图，该章节是算法实现的基础。 第三章关键技术与o t i 算法：主要介绍伪装网络包源地址、探测包、降低 块成熟度和辅助树存储结构四项网络拓扑中用到的关键技术，并基于这些技术 详细阐述网络拓扑o t i 算法。 第四章网络拓扑o t i 算法的实现：通过试验，并与有代表性的算法比较， 分析网络拓扑o t 工算法的在复杂度和对网络t r a f f i c 的影响方面是否有所提高。 第五章总结与展望：网络拓扑算法研究全文总结并提出进一步的工作。 第二章相关定义与网络拓扑模型 第二章相关定义与网络拓扑模型 本章首先介绍生成树协议s t p ( s p a r u l i n gt r e ep r o t o c a l ) 。网络拓扑模型的前 提条件就需要网络中所有交换机遵循s t p 。然后对网络模型中相关的概念、专 业术语和符号给出详细的定义，最后详细阐述网络拓扑模型。 2 1 生成树协议( s t p ) 生成树协议s p a n n i n gt r e e 【1 2 】定义在i e e e8 0 2 1 d 中，是一种桥到桥的链 路管理协议，它在防止产生自循环的基础上提供路径冗余。为使以太网更好地 工作，两个工作站之间只能有一条活动路径。网络环路的发生有多种原因，最 常见的一种是故意生成的冗余，万一一个链路或交换机失败，会有另一个链路 或交换机替代。所以，s t p 协议的主要思想就是当网络中存在备份链路时，只 允许主链路激活，如果主链路因故障而被断开后，备用链路才会被打开。 生成树协议基于以下几点：1 有一个唯一的组地址( 0 1 8 0 c 2 0 0 o o 一0 0 ) 标 识一个特定l a n 上的所有的交换机。这个组地址能被所有的交换机识别；2 每 个交换机有一个唯一的标识( b m g ei d e n t i f i e r ) ；3 每个交换机的端口有一个唯一 的端口标识( p o i r ti d e n t i f i e r ) 。对生成树的配置进行管理还需要：对每个交换机协 调一个相对的优先级；对每个交换机的每个端口协调一个相对的优先级；对每 个端口协调一个路径花费。 具有最高优先级的交换机被称为根( r o o t ) 交换机。每个交换机端口都有一个 根路径花费，根路径花费是该交换机到根交换机所经过的各个路段的路径花费 的总和。一个交换机中根路径花费的值为最低的端口称为根端口，若有多个端 口具有相同的根路径花费，则具有最高优先级的端口为根端口。 在每个l a n 中都有一个交换机被称为指定( d e s i g n a t e d ) 交换机，它属于 该l a n 中根路径花费最少的交换机。把l a n 和指定交换机连接起来的端口就 是l a n 的指定端口( d e s i g n a t e dp o r t ) 。如果指定交换机中有两个以上的端口连 在这个l a n 上，则具有最高优先级的端口被选为指定端口。拓扑结构如图2 1 所示。 由于交换机a 具有最高优先级( 桥标识最低) ，被选为根交换机，所以交换 机a 是l a na 和l a nb 的指定交换机；假设交换机b 的根路径花费为6 ，交 换机c 的根路径花费为4 ，那么交换机c 被选为l a nc 的指定交换机，亦即 l a nc 与交换机a 之间的消息通过交换机c 转发，而不是通过交换机b 。l a n c 与交换机b 之问的链路是一条冗余链路。 9 河海大学硕士学位论文 d ：选墩端口 r ：根端口 图2 1 根交换机与根端口 2 2 相关概念、专业术语和符号的定义 首先给出2 层( 链路层) 网络设备的有关定义，以及网络拓扑算法中引用到 的专业术语。 2 2 1网络设备概念定义 交换机：从设备固有的特性角度来说，以太网交换机每一端口相连设备的 m a c 地址，并将地址同相应的端口映射起来存放在交换机缓存中的m a c 地址 表中，这是交换机的学习【1 0 】功能。当一个数据帧的目的地址在m a c 地址表中 有映射时，它被转发到连接目的节点的端口而不是所有端口( 如该数据帧为广播 组播帧则转发至所有端口) 。具体的说，如果交换机的某端口c 接收到来自么的 数据包，交换机立即就会把数据包丢给地址表中含有彳的端口。本文中用x 表 示交换机。 集线器( h u b ) ：是所有端口共享一个通道，在星型结构中，它是连接的中间节 点，一旦接收到数据包，就会转发给所有的端口。h u b 的所有端口共享一个m a c l o 第二章相关定义与网络拓扑模型 地址。本文中用h 表示集线器。 2 2 2 专业术语定义 地址转发表( a f l ) n 钔：a d d r e s sf o n ) ，a r d i n gt a b l e 。在每个交换机上都维护 着一张表，记录着接收的数据包应该从哪个端口转发出去，这张表就是地址转发 表。 网络杂乱模式n5 j ：在网络中，杂乱模式允许一个网络装置侦听而且阅读抵达 的每个网络包。这个运行模式有时在网络侦听服务器上运行，用来捕获及保存所 有的数据包，以便分析。( 比如，对于监听网络使用情况) 。在一个以太区域网络 ( l a n ) 中，杂乱模态是指被传输的每个数据小包都能被一个网络转接器接到而且 阅读的操作模式。杂乱模态必须被每个网络转接器支持，也必须被主机操作系统 的输入输出驱动器支持。杂乱模态时常用来监督网络使用率。杂乱模念是和非 杂乱模态相对的。当一个数据小包在非杂乱模态传输时候，所有的区域网络装置 “听到”数据并且判断被包含在数据小包之中的网络地址是否是他们的。如果它不 是，数据小包进入下一个区域网络装置，直到到达具有正确网络地址的装置。然 后那个装置接收而且读取数据。 共享段旧3 ：假定网络设备a 连接某个h u b 或类h u b 设备，则a 存在于以此h u b 形成的共享段上，记为p 。如果共享段不存在任何h o s t s ，那么称之为低度共享 段。反之，称之为高度共享段。如果高度共享段连接至少两个交换机，那么称之 为混合共享段。 _ 。 - 。 共享树呻3 ：当父共享段p 上的h o s t 可以接收到子孙共享段矿上h o s t 发出 q q 的数据包，在树形结构中，那么就把p 放在p 。的上方。称以这种方式形成的树 为共享树。 块：由一个或多个高度共享段通过交换机组成的最大连接子图并且不存在 低度共享段称之为块，记作锣? ( i _ 0 n ) 。 连接域：是由一个或多个低度共享段构成的域，连接域可以连接多个块， 记作，。 段头：每个共享段中选择任意一个h o s t ，通过这个h o s t 利用探测包，判断 共享段与交换机的连接情况，这个h o s t 称为段头。 块的成熟度：块的成熟度用0 到1 衡量。在调用块的发现算法后，如果可以 j 下确拓扑出块的内部节点及其连接关系，那么块的成熟度是彤b = 1 。如果块的 河海大学硕十学位论文 内部节点及其关系都没有被发现，那么称块的成熟度。= o 。 2 2 3 符号定义 为了下面章节讨论网络拓扑算法的方便，这里首先介绍网o t i 算法中常用 的符号及其表达含义，如表2 1 所示。( 部分符号引用文献【8 】) 表2 1 基本符号定义 符号定义 域表示任意节点，y 的所有活动端口集合。 矿 表示g ( y ，e ) 中的所有节点，包括所有的交换机和h o s t s 。 n t 表示g ( 矿，e ) 中的所有叶节点，即所有的h o s t s 。 只t 表示节点v y 的第尼曲个端口。 e 表示节点1 ，y 的第七m 个端口的a f t 地址转发表，引用文献6 1 。 n 子网s u b n e t 的集合。 s u b n e t 是最大的i p 网络设备集合，其中任意两设备通信都不要 经过路由器。 丁( y ，e ) 是任意子网l 厂所确定的连接树。 e ，) 。：任意一对网络节点 l 圳 s ，的路径集合。所以丁( y ，e 。) = u 只，) m ，矿，e 是 f = l ，) v 中所有网络节点与边的集合。 n 任意一个交换机v y ，如果子网f 包含v ，则匕= q ，且 y 化。所以给定节点v 的a f t s 信息是在匕中可达的节点 的集合。 表示节点v 的根端口。 1 l ，( ，) 1 2 第二章相关定义与网络拓扑模型 r 连接树丁的根节点。 鼠 一系列节点y ，且在丁中以v 为根节点。l 鼠i 表示鼠中的 数量。 c r 辅助结构树中顶点y 所包含的节点集合。 2 3 网络拓扑模型 本论文所考核的二层网络是一个由大量的网络元素，如交换机( 或称网桥) ， 主机，h u b 构成的连接体。由于是一个连接的网络实体，任意两个网络元素之 间总存在一条路径，且这条路径上包含有大量的交换机、h u b s 等设备。本论文 假设二层网络中的所有交换机都遵循s t p 协议，通过s t p 协议可以判断交换机 上的活动端口【19 1 。这样二层网络中每对元素之间的路径构成了树状的布局，即 建模这个树状布局为图论中的无向树g ( y ，e ) ，其中的节点集合y 中的元素代表 网络设备，e 集合中的边代表网络中设备之间的物理连接。交换机，h u b 在无 向树g 中代表内部节点，h o s t s 代表叶节点。交换机活动端口七的地址转发表 户：t 是由该端口上接收到数据包的源m a c 地址构成。节点集合y 中任意节点 元素v 的所有活动端口用q 表示。元素v 的第个活动端口用七表示。 网络中任意一个交换机都连接着一个或多个子网。子网是网内元素的最大 集合，任意两个设备都可以直接相连，不需要路由器；如果不同子网之间需要 通讯，则必须经过路由器。所以，子网内任意设备都有一个唯一的i p 地址和一 个子网掩码固定了子网内i p 地址范围。无向树g 中子网集合用表示，每个 子网在无向树g 中代表一个无向子树g 。( 矿，e ) 。 无向子树中如果存在一个h u b ，且h u b 上连接有h o s t s 或交换机，那么称 之为共享段。如图2 2 所示彳，b ，c ，d ，e ，f ，g ，日，j r ，是十个h o s t s ，分别连接在不 同的h u b 上，由共享段定义可知，图2 2 包括四个高度共享段 彳，b ) ， c ，研， e ，f ， g ， ( 实线阴影区域表示) ，一个低度共享段( 虚线阴影区域表示) ，一 个混合共享段 ， ( 点线阴影区域表示) 。 河海大学硕上学位论文 图2 2 共享段 在网络中不同的高度共享段之间通过交换机连接后组成最大的连接体，这 个连接体在无向树中称之为块。如图2 3 所示， h ，构成的共享段 爿，口) 是高度 共享段，h ：构成的共享段 f ，刃) 是高度共享段，而h 。构成的共享段不存在h o s t ， 故是低度共享段。由块的定义，块是由高度共享段构成的最大的连接子图，且 不包含低度共享段，l 区是一个块曰，。同样h 。过程的共享段 口，川也是一个高 度共享段，通过x 。与h 。构成的低度共享段相连接，所以l il 区也是块，。h 。 构成的低度共享段两端连接交换机x ：和x 。，其它都是高度共享段，所以h 。构成 的低度共享段单独构成了一个连接域0 ，0 连接两个块毋和。 第二章相关定义与网络拓扑模型 ；x ：代发交换帆 ih ：代表榘线器h u b 2 4 本章小结 l i i i i 图2 3 块与连接域 本章详细阐述了网络设备的概念、网络模型中的专业术语、以及网络拓扑 算法中涉及到的符号定义。基于网络中所有交换机都遵循s t p 协议的基础上， 详细给出了网络拓扑模型，本章节是网络拓扑o t i 算法实现的基础。 河海大学硕士学位论文 第三章关键技术与0 tl 算法 本章讨论网络拓扑o t i 算法。所谓的o t i 算法是指采用一定的拓扑技术， 以由外向内的方式，以达到发现网络拓扑的目的。”由外向内”：在网络拓扑模型 中，共享段是最外层。通过交换机相连接构成的块是中间层，余下的骨干交换 机、h u b 构成的连接域是内层。所以o t i 是指：发现共享段一发现块一发现连 接域一合并辅助结构树，这样一种发现网络拓扑的方式方法。 在介绍o t i 算法之前，本章首先介绍了远过程调用协议r p c ，在算法实现 架构中，服务器可以通过r p c 直接操作客户端的脚本程序。o t i 算法是基于四 项关键技术，简称4 t 。4 t 与o t i 算法中发现步骤有对应关系。如下表3 1 所 示。 表3 14 t 与发现算法过程的对应关系 技术名称发现算法 1 t伪装源地址 发现共享段、发现共享段之间交换机 2 t探测包 发现共享段之问交换机( 发现块) 3 t降低块成熟度 发现连接域 4 t辅助结构树 发现连接域 所以本章在详细介绍4 t 关键技术之后，再详细给出网络拓扑o t i 算法过 程。最后基于理论对o t i 算法进行理论分析。 3 1远过程调用协议( r p c ) 远过程调用协议i 冲c ( r e m o t ep r o c e d u r ec a l lp r o t o c 0 1 ) 【1 5 16 1 。本算法的实 现程序框架采用客户机月艮务器模式架构，服务器上运行主网络拓扑算法服务进 程，每个h o s t 端都运行数据收集s c r i p t s ，服务上调用客户端脚本采用r p c 协 议，就相当于在本机上运行脚本。 3 1 1r p c 概念 一种通过网络从远程计算机程序上请求服务，而不需要了解底层网络技术 的协议。r p c 协议假定某些传输协议的存在，如t c p 或u d p ，为通信程序之 间携带信息数据。在o s i 网络通信模型中，r p c 跨越了传输层和应用层。i 冲c 使得丌发包括网络分布式多程序在内的应用程序更加容易。r p c 采用客户机 1 6 第三章关键技术与o t i 算法 服务器模式。请求程序就是一个客户机，而服务提供程序就是一个服务器。首 先，调用进程发送一个有进程参数的调用信息到服务进程，然后等待应答信息。 在服务器端，进程保持睡眠状态直到调用信息的到达为止。当一个调用信息到 达，服务器获得进程参数，计算结果，发送答复信息，然后等待下一个调用信 息，最后，客户端调用过程接收答复信息，获得进程结果，然后调用执行继续 进行。 3 1 2r p c 远程过程调用流程 i 冲c 调用信息：每条远程过程调用信息包括以下无符号整数字段，以独立 识别远程过程，i 冲c 调用信息主体形式如下： s t r u c tc a ll b o d y u n s i g n e di n tr p c v e r s ： u n s i g n e di n tp r o g ： u n s i g n e di n tv e r s ： u n s i g n e di n tp r o c ： a p a q u e a u t hc r e d ： o p a q u e a u t hv e r f ： ： r p c 答复信息：i 冲c 协议的答复信息的改变取决于网络服务器对调用 信息是接收还是拒绝。答复信息请求包括区别以下情形的各种信息： 1 ) r p c 成功执行调用信息。 2 ) i 冲c 的远程调用实现不是协议第二版，返回i 冲c 支持的最低和最 高版本号。 3 ) 在远程系统中，远程程序不可用。 4 ) 远程程序不支持被请求的版本号。返回远程程序所支持的最低和最 高版本号。