（计算机应用技术专业论文）基于vxworks操作系统的mstp的研究与实现.pdf

南京邮电学院硕士研究生学位论文 摘要 摘要 交换机在第二层即m a c 层必须具有转发功能。目前交换机上普遍使用的m a c 层交换方 式是i e e e 8 0 2 1 组织发布的标准：基于生成树算法的交换。为加速网络融合并解决与生成树 和虚拟l a n ( v l a n ) 交互相关的地址可扩展性限制问题，l d s t p 应运而生。m s t p 将环路网络修 剪成为一个无环的树型网络，避免报文在环路网络中的增生和无限循环，同时还提供了数据 转发的多个冗余路径，在数据转发过程中实现v l a n 数据的负载均衡。 本文首先扼要介绍了生成树协议的演进过程，着重论述了多生成树协议的运行机理和重 要概念，接着通过对多种协议进行分析，阐明了多生成树协议的软件架构，给出了多生成树 协议在实时嵌入式操作系统v x w o r k s 下的实现方案，包括需求分析，系统建模，模块内部状 态机等，也包含了笔者所从事的相关项目研发工作的总结。最后从功能方面对本文所实现的 协议系统进行了测试并且提出了今后的工作方向。 关键词：生成树协议多生成树协议协议实现v x w o r l s 系统 南京邮电学院硕士研究生学位论立 a bs t r a c t t h el a y e ri io ft h es w i t c h ，i e ，t h em a cl a y e r , m u s th a v et h ef u n c t i o no f f o r w a r d i n g t h ef o r w a r d i n gm e t h o do f m a cl a y e ri nn o w a d a y ss w i t c hi sb a s e do n t h es t a n d a r do fi e e e 8 0 2 1 ：s p a n n i n g t r e ea l g o r i t h m m s t pc u t st h en e t w o r kt h a t h a sc i r c u i tt oat r e e m o d en e t w o r kt h a th a sn oc i r c u i ta n da v o i d st h em e s s a g et o i n c r e a s ea n df o r w a r di n f i n i t e l y ，i ts t i l lp r o v i d e ss e v e r a lr e d u n d a n c yp a t h sf o rd a t a f o r w a r d i n g i nt h ep r o c e s s i n go fd a t af o r w a r d i n gm s t pc a r r y so u tt h eb a l a n c eo f v l a nd a t a i nt h i sp a p e r , ii n t r o d u c et h ep r o c e s s i n go f s p a n n i n g _ t r e ed e v e l o p m e n tf i r s t l y ， t h e nd i s c u s s et h eb a s i cp r i n c i p l eo fm u l t i p l es p a n n i n gt r e ep r o t o c 0 1 s e c o n d l y t h r o u g ht h ea n a l y s i s a n d c o m p a r i s o no ft h ep r o t o c o lm o d e l s ，i tp r e s e n t st h e i m p l e m e n t a t i o ns c h e m eo fm s t pi nt h eo p e r a t i n gs y s t e mv x w o r l ( sf o re m b e d d e d r e a l t i m es y s t e m s ，i n c l u d i n gt h er e q u i r e m e n ta n a l y s i s ，s y s t e mm o d e l i n ga n ds t a t e m a c h i n e 。f i n a l l yi ta n a l y z e st h ef u n c t i o no ft h ep r o t o c o ls y s t e m k e y w o r d s ：s t pm s t p p r o t o c o li m p l e m e n t a t i o nv x w o r k s 南京邮电学院硕士研究生学位论文参考文献 缩写词表 n o缩写词英文全文译文 l s t p s p a n n i n gt r e ep r o t o c o l 生成树协议 2 r s t p r a p i ds p a n n i n gt r e ep r o t o c o l 快速生成树协议 3 m s t p m u r i p l es p a n n i n g t r e ep r o t o c o l 多生成树协议 4 s 1 a s p a n n i n gt r e ea l g o r i t h m 生成树算法 5b p d u b r i d g ep r o t o c o ld a t au n i t 网桥协议数据单元 6v l a nv i r t u a lb r i d g e dl o c a la r e a n e t w o r k s 虚拟局域网 7m a cm e d i aa c c e s $ c o n t r o l 媒体访问控制 8 c i s tc o m m o na n di n t e r n a ls p a n n i n gt r e e公共和内部生成树 9c s tc o m m o ns p a n n i n gt r e e 公共生成树 1 0i s ti n t e r n a ls p a n n i n gt r e e 内部生成树 1 lm c i dm s tc o n f i g u r a t i o ni d e n t i f i e r 多生成树配置i d 1 2 m s t l m u i t i p l es p a n n i n gt r e ei n s t a n c e 多生成树实例 1 3s s t si n g l es p a n n i n gt r e e 单个生成树 1 4 m s t m u l t i p l es p a n n i n gt r e e 多生成树 南京邮电学院学位论文独创性声明 y7 6 5 0 7 2 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电学院或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：牲日期：边耳 南京邮电学院学位论文使用授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。，除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电学院研究生部办理。 研究生签名：牲导师签名： 眯飙 南京邮电学院硕士研究生学位论文引言 引言 早在网络发展初期透明网桥是一个不得不提的重要角色，它比只会放大和广播信号的h u b 聪明得多，它会把发向它的数据帧的源m a c 和i 端口记录下来，下次碰到这个目的m a c 的报文就 只从记录中的端口号发送出去，除非目的m a c 没有记录或者目的m a c 就是多播地址才会向所有 端口发送。通过透明网桥不同的局域网之间可以互通而且出于具备m a c 地址学习功能而不会像 h u b 刃b 样造成网络报文冲撞泛滥。但是透明网桥也有它的缺陷，它的缺陷就在于透明传输。透 明网桥并不能像路由器那样知道报文还可以经过多少次转发，一旦网络存在环路就会造成 报文在环路内不断循环和增生，甚至造成恐怖的广播风暴。在这种大环境下s t p ( s p a n n i n g t r e ep r o t o c 0 1 ) 协议出现了，其中以i e e e 的8 0 2 1 d 版本最为流行。 s t p 协议给透明网桥带来了新生，但是随着应用的深入和网络技术的发展，它的缺点在 应用中也被暴露了出来。s t p 协议的主要的缺陷表现在收敛速度上，于是在 e e e8 0 2 1 w 标准 里定义了一种快速生成树协议r s t p ( r a p i ds p a n n i n gt r e ep r o t o c 0 1 ) ，对s t p 协议进行了部 分改进，基本满足了组网的要求。 但是近些年i e e e8 0 2 1 q 大行其道逐渐成为交换枧的标准协议。在网络结构对称的情况下 单生成树没什么大碍，但是在网络结构不对称时单生成树就会影响网络的连通性。原有单生 成树的诸多缺陷便逐步暴露出来：由于整个交换网络只有棵生成树，在网络规模比较大的 时候会导致较长的收敛时间，拓扑改变的影响面也较大，当链路被阻塞后将不承载任何流量， 造成了带宽的极大浪费。 多生成树协议m s t p ( m u l t i p l es p a n n i n gt r e ep r o t o c 0 1 ) 是i e e e8 0 2 1 s 草案中定义的一种 新型生成树协议，采用多生成树，可以通过干道( t r u n k s ) 建立多个生成树，关联v l a n s 到 相关的生成树进程每个生成树进程具有独立于其他进程的的拓扑结构：m s t 提供了多个数 据转发路径和负载均衡。提高了网络容错能力。 本论文对m s t p 协议进行较为深入的研究。首先介绍m s t p 协议的运行机理和技术，接着 给出了m s t p 协议在实时嵌入式操作系统v x w o r k s 下的实现方案，并从功能上对本文所实现的 协议系统进行了组网测试 南京邮电学院硕士研究生学位论文第一章m s t p 技术概述 第一章m s t p 技术概述 m s t p ( m u l t i p l es p a n n i n gt r e ep r o t o c 0 1 ) 是多生成树协议的英文缩写，该协议兼容s t p ( s p a n n i n gt r e ep r o t o c 0 1 ) 和r s t p ( r a p i ds p a n n i n gt r e ep r o t o c 0 1 ) 。s t p 不能快速迁 移。即使是在点对点链路或边缘端口，也必须等待2 倍的f o r w a r dd e l a y 的时间延迟，端口 才能迁移到转发状态。r s t p 可以快速收敛，但是和s t p 一样存在以下缺陷：局域网内所有网 桥共享一棵生成树，不能按v l a n 阻塞冗余链路，所有v l a n 的报文都沿着一棵生成树进行转 发。m s t p 可以弥：i b s t p 和r s t p 的缺陷，它既可以快速收敛，也能使不同v l a n 的流量沿各自的 路径分发，从而为冗余链路提供了更好的负载分担机制。 本章首先对m s t p 进行简要介绍，主要是m s t p 的相关概念和基本知识，然后具体介绍m s t p 的技术，主要是m s t p 相对于原有单生成树协议的新特性和工作方式。 i 1s t p 和r s t p 概述1 t 2 3 s t p 协议的基本思想十分简单，大家知道自然界中生长的树是不会出现环路的，如果网络 也能够像一棵树一样生长就也不会出现环路。于是s t p 协议中定义了根桥r o o t b r i d g e ，根端 i r o o tp o r t ，指定端t 3 d e s i g n a t e dp o r t ，路径开销p a t hc o s t 等概念，通过构造一棵自 然树的方法达到裁剪冗余环路的目的，同时实现链路备份和路径最优化。用于构造这棵树的 算法就叫做生成树算法s t a ( s p a n n i n gt r e ea l g o r i t h m ) 。用这种算法构造网络树的协议也 就被称为“生成树协议”。 要实现这些功能，网桥之间必须要进行一些信息的交流，这些信息交流单元就称为配置 消息b p d u ( b r i d g ep r o t o c o ld a t au n i t ) ， s t pb p d u 是一种二层报文，目的m a c 是多播地 址叭一8 0 - c 2 0 0 - 0 0 一0 0 ，所有支持s t p 协议的网桥都会接收并处理收到的报文，该报文在数据 区里携带了用于生成树计算的所有有用信息。 生成树协议首先进行根桥的选举，选举的依据是网桥优先级和网桥m a c 地址组合成的桥 i d ，桥i d 最小的网桥将成为网络中的根桥。在如图l 所示的网络中各网桥都以默认值启动，在 网桥优先级都一样默认优先级是3 2 7 6 8 的情况下。m a c 地址最小的网桥成为根桥。假设是图中 的s w i ，这样s w l 的所有端口都成为指定端口进入转发状态。 2 南京邮电学院硬上研究生学位论文 第一章m s t p 技术概述 图l 生成树工作示意图 接下来其他网桥将各自选择一条最粗壮的树枝作为到根桥的路径，相应端口的角色就成 为根端口。假设在图中s w l 和s w 3 之间链路是百兆f e 链路，其他链路是千9 5 g e 链路，那么s w 3 从端口1 到根桥的路径开销按照默认值就是1 9 ，而从端口2 经过s w 2 至t j 根桥的路径开销是4 + 4 = 8 ， 所以端口2 成为根端口，进入转发状态。s w 2 至t j 根桥有两条路径开销相等的路径，它将根据发 送端的端口i dp o r ti d 来确定优先级，优先级高( 数值小) 的将成为根端口，假设是端 3 2 。 s w 2 的端口1 将成为指定端口。 根桥和根端口都确定之后一棵树就已经构造出来了，如图中实线所示。下面的任务是裁 剪冗余的环路，这个工作是通过阻塞非根桥上相应端口来实现的。例立u s w 2 的端口3 和s w 3 的端 口l 的角色成为禁用端口，进入阻塞状态。 经过一段时间( 默认值是3 0 秒左右) 生成树稳定之后，所有端口要么进入转发状态，要 么进入阻塞状态，s t pb p d u 仍然会定时从各个网桥的指定端口发出，以维护链路的状态。如 果网络拓扑发生变化，生成树就会重新计算，端口状态也会随之改变。 s t p 协议给透明网桥带来了新生，但是随着应用的深入和网络技术的发展，它的缺点在应 用中也被暴露了出来。s t p 协议的主要的缺陷表现在收敛速度上，当拓扑发生变化，新的配置 消息要经过一定的时延才能传播到整个网络，这个时延称为f o r w a r dd e l a y ，默认值是1 5 秒。 在所有网桥收到这个变化的消息之前，若旧拓扑结构中处于转发的端口还没有发现自己应该 在新的拓扑中停止转发，则可能存在临时环路。为了解决临时环路的问题，生成树使用了一 种定时器策略：即在端口从阻塞状态到转发状态中间加上一个只学习m a c 地址但不参与转发的 中间状态，两次状态切换的时间都是f o r w a r dd e l a y ，这样就可以保证在拓扑变化的时候不会 产生临时环路，但是这个看似良好的解决方案实际上带来的却是至少两倍f o r w a r dd e l a y 的收 敛时间! 为了解决s t p 协议的这个缺陷，在世纪之初i e e e 推出t 8 0 2 1 w 协议标准作为对8 0 2 1 d 标准 的补充。在i e e e8 0 2 1 v 标准里定义了一种快速生成树协议r s t p ( r a p i ds p a n n i n gt r e e p r o t o c 0 1 ) 。r s t p 协议在s t p 协议基础上作了三点重要改进。收敛速度快得多( 最快1 秒以内) 。 堕室堂皇兰垦堡主堑塞兰兰垡堕兰 兰二至竺! 里望查塑鋈 第一点改进：为根端口和指定端口设置了快速切换用的替换端口( a 1 t e r n a t ep o r t ) 和 备份端口( b a c k u pp o r t ) 两种角色，当根端口指定端口失效的情况下，替换端口备份端口 就会无时延地进入转发状态。如图l ，如果所有网桥都运行r s t p 协议，s w 2 的端d 3 将能够识别 这种拓扑结构，成为替换端口。当端口2 的链路失效的情况下，端口3 就能够立即进入转发状 态，无需等待两倍f o r w a r dd e l a y 时间。 第二点改进：在只连接了两个交换端口的点对点链路中，指定端口只需与下游网桥进行 一次握手就可以无时延地进入转发状态。如果是连接了三个以上网桥的共享链路，下游网桥 是不会响应指定端口发出的握手请求的，只能等待两倍f o r w a r dd e l a y 时间进入转发状态。 第三点改迸：直接与终端相连而不是和其他网桥相连的端口定义为边缘端口( e d g ep o r t ) ， 边缘端口可以直接进入转发状态，不需要任何延时。由于网桥无法知道端口是否是直接与终 端相连，所以需要人工配置。 可见r s t p 协议相对于s t p 协议的确改进了很多，为了支持这些改进，b p d u 的格式作了一些 修改，但仍然向下兼容s t p 协议，可以混合组网。虽然如此，r s t p 和s t p 一样同属于单生成树 s s t ( s i n g l es p a n n i n gt r e e ) ，有它自身的诸多缺陷，主要表现在三个方面。 第一：由于整个交换网络只有一棵生成树，在网络规模比较大的时候会导致较长的收敛 时间，拓扑改变的影响面也较大。 第二：近些年i e e e8 0 2 i q 大行其道，逐渐成为交换机的标准协议。在网络结构对称的情 况下，单生成树也没什么大碍，但是在网络结构不对称的时候，单生成树就会影响网络的连 通性。 图2 非对称网络示意图 如图2 所示，假设s w l 是根桥，下面链路是v l a n1 0 ，上面链路是8 0 2 i q 的t r u n k 链路，t r u n k 了v l a nl o 和v l a n2 0 。当s w 2 的t r u n k 端口被阻塞的时候，显然v l a n2 0 的通路就被切断了。 第三：当链路被阻塞后，将不承载任何流量，造成了带宽的极大浪费。这在环行城域网 中比较明显。 4 南京邮电学院硕士研究生学位论文 第一章m s t p 技术概述 图3 带宽利用率低下示意图 如图3 所示，假设s w l 是根桥，s w 4 的一个端口被阻塞，这种情况下s w 2 $ 1 s w 4 之间铺设的光 纤将不承载任何流量，任何s w 2 和s w 4 之间的流量都将经过s w l 和s w 3 转发，增加了这几条链路 的负担。 这些缺陷都是单生成树s s t 无法克服的，于是支持v l a n 的多生成树协议出现了。 1 2m s t p 概述 多生成树协议m s t p ( m u l t i p l es p a n n i n gt r e ep r o t o c 0 1 ) 是i e e e8 0 2 1 s 中定义的一种 新型生成树协议，这个协议目前仍然在制定过程中，现在只有草案d r a f t 版本可以获得，但 是m s t p 的基本工作原理已经比较固定。 1 2 1m s t p 中的几个概念 在图4 中有四个m s t 域，每个域都由四台交换机构成。交换机都运行m s t p 。下面将结合图 形解释m s t p 的几个概念。 图4m s t p 的基本概念示意图 堕塞坚皇兰堕堡：! 竺圣竺兰垡丝苎苎二皇坚! ! 垫查塑垄 1 m s t 域 3 m s t 域( m u l t i p l es p a n n i n gt r e er e g i o n s ) ：多生成树域，是由交换网络中的多台交 换机以及它们之间的网段所构成，这些交换机都启动t m s t p 、具有相同域名，具有相同v l a n 到 生成树映射配置，具有相同m s t p 修订级别配置，并且物理上直接相连。一个交换网络可以存 在多个m s t 域。用户可以通过m s t p 配置命令把多台交换机划分在同一个m s t 域内。例如图4 中的区域a o ，域内所有交换机都有相同的m s t 域配置：域名相同，v l a n 与生成树的映射关系 相同( v l a n i 映射到生成树实例1 ，v l a n 2 映射到生成树实例2 ，其余v l a n 映射蛩j c i s t ) ，相 同的m s t p 修订级别( 此配置在图中没有体现) 。 2 v l a n 映射表 5 m s t 域的一个属性，是描述v l a n 和生成树实例关系的对应表。例如图4 中，域a o 的v l a n 映射表就是：v l a n1 映射到生成树实例i ，v l a n 2 映射到生成树实例2 ，其余v l a n 映射n c l s t 。 3 i s t 3 i s t ( i n t e r n a ls p a n n i n gt r e e ) ：内部生成树，是m s t p 域内的一棵生成树，它和c s t ( c o m m o ns p a n n i n gt r e e ) 共同构成整台交换机网络的生成树c i s t ( c o m m o na n di n t e r n a l s p a n n i n gt r e e ) 。i s t 是c i s t 在一个m s t 域中的片断。例如图4 中c l s t 在每个m s t 域内都 有一个片断，这个片断就是各个域内的i s t 。 4 c s t c s t ( c o m m o ns p a n n i n gt r e e ) ：公共生成树，连接交换网络内所有m s t 域的单生成树。 如果把每个m s t 域看作是一个“交换机”，c s t 就是这些“交换机”通过s t p 协议或r s t p 协议 计算生成的一棵生成树，如图4 。 5 c i s t c i s t ( c o m m o na n di n t e r n a ls p a n n i n gt r e e ) ：公共和内部生成树，由i s t 和c s t 共同 构成，是连接一个交换网络内所有交换机的单生成树。例如图4 中，每个域内的i s t 加上域间 的c s t 就构成整个网络的c i s t 。 6 m s t i m s t i ( m u l t i p l es p a n n i n gt r e ei n s t a n c e ) ：多生成树实例，一个m s t 域内可以通过m s t p 生成多棵生成树，各棵生成树之间彼此独立。每棵生成树都称为一个m s t i ，即多生成树实例。 例如图4 中，每个域内可以存在多棵生成树，每棵生成树和相应的v l a n 对应。这些生成树就 被称为m s t i 。 6 南京邮电学院硕士研究生学位论文 第一章m s t p 技术概述 7 域根 m s t 域内i s t 和m s t i 的树根就是域根。m s t 域内各棵生成树的拓扑不同，域根也可能不 同。例如图4 中，区域d 0 中，生成树实例l 的域根为交换机b ，生成树实例2 的域根为交换机 c 。 8 c o m m o nr o o tb r id g e c i s t 的根交换机就是c o m m o nr o o tb r i d g e ，即总根。例如图4 中，总根为区域a o 内的某 台交换机。 9 域边缘端口 域边缘端口是指位于m s t 域的边缘，连接不同m s t 域、或者连接m s t 域和运行s t p 的区域、 或者连接m s t 域和运行r s t p 的区域的端口。在进行m s t p 计算的时候，域边缘端口在m s t 实例上 的角色和c i s t 实例的角色保持一致，即如果边缘端口在c i s t 实例上的角色是m a s t e r 端口， 则它在域内所有m s t 实例上的角色也是m a s t e r 端口。例如图4 中，如果区域a 0 的一台交换机 和区域d o 的一台交换机的第一个端口相连，整个交换网络的总根位于a o 内，则区域d o 的这 台交换机上的第一个端口就是区域d 0 的域边缘端口。 1 0 端口的角色 在m s t p 的计算过程中，端口的角色有指定端口、根端口、m a s t e r 端口、a l t e r n a t e 端 口、b a c k u p 端口等。根端口是负责向树根方向转发数据的端口；指定端口是负责向下游网段 或交换机转发数据的端口；m a s t e r 端口位于整个域n c o m m o nr o o tb r i d g e 的最短路径上， 它是连接域n c o m m o nr o o tb r i d g e 的端口；a 1 t e r n a t e 端口是m a s t e r 端口的备份端口。如 果m a s t e r 端口被阻塞后，a l t e r n a t e 端口将成为新的m a s t e r 端口。当同一台交换机的两个 端口互相连接时就存在一个环路，此时交换机会将其中一个端口阻塞，b a c k u p 端口是阻塞的 那个端口。端口在不同的生成树实例中可以担任不同的角色。 1 2 2m s t p 工作方式 b i s t p 协议精妙的地方在于把支持m s t p 的交换机和不支持m s t p 交换机划分成不同的区域。分 别称作m s t 域和s s t 域在m s t 域内部运行多实例化的生成树，在m s t 域的边缘运行r s t p 兼容协 议 南京邮电学院颁士研究生学位论文 第一章m s t p 技术掇述 图5m s t p _ t _ 作方式示意图 如图5 所示，中间的m s t 域内的交换机间使用m s t pb p d u 交换拓扑信息，两边的s s t 域内的交 换机使用s t p r s t pb p d u 交换拓扑信息，m s t 域与s s t 域之间的边缘端口上，m s t p 的处理稍微复 杂一些。当边缘端口收到其他交换机发来的s t pb p d u 的时候，端口会进入s t p 兼容状态，发送 s t pb p d u 。当边缘端口收蛩j r s t pb p d u 的时候，端口会进入r s t p 兼容状态，但仍然发送m s t p b p d u 。由于r s t p 在设计的时候就考虑了扩展，所以对端的r s t p 设备可以把m s t p 报文理解成正 确的r s t p 报文。 8 南京邮电学院硕士研究生学位论文第二章m s t p 的摹本原理 第二章m s t p 的基本原理 m s t p 内部需要维护的生成树包括i s t 和由若干个m s t i 确定的m s t p 生成树。i s t 个数和连接 了多少个s s t 域有关，m s t p 生成树个数是可以配置的。m s t p x b 对于之前的种种生成树协议而言， 优势非常明显。m s t p 具有v l a n 认知能力，可以实现负载均衡，可以实现类似r s t p 的端口状态 快速切换，可以捆绑多个v l a n 到一个实例中，以降低各种资源的占用率。最难能可贵的是m s t p 可以很好地向下兼容s t p r s t p 。 本章首先介绍了m s t p 的基本工作原理，然后举例说明各个要素的计算方法，最后指出本 论文的课题背景和主要工作。 2 1 t s t p 的基本原理 m s t p 将整个二层网络划分为多个m s t 域，各个域之间通过计算生成c s t ：域内则通过计 算生成多棵生成树，每棵生成树都被称为是一个多生成树实例。其中实例0 被称为i s t ，其他 的多生成树实例为m s t i 。m s t p 同r s t p 一样，使用配置消息进行生成树的计算，只是配置消 息中携带的是交换机上m s t p 的配置信息。 2 1 1 生成树的计算原理 c i s t 生成树的计算3 ，1 0 , 1 2 1 通过“配置消息”的比较在整个网络中选择一个优先级晟高的交换机作c i s t 的树根。在 每个m s t 域内m s t p 通过计算生成i s t , 同时m s t p 将每个m s t 域作为单台交换机对待，通过计 算在域间生成c s t 。c s t 和i s t 构成了整台交换机网络中连接所有交换机的c i s t 。 m s t i 的计算 3 6 ，1 1 在m s t 域内，m s t p 根据v l a n 和生成树实例的映射关系，针对不同的v l a n 生成不同的生 成树实例，即鹏t i 。每棵生成树独立迸行计算。下面对单个生成树的计算过程进行举例介绍。 生成树的基本原理是，通过在交换机之间传递一种特殊的协议报文( 在i e e e 8 0 2 1 d 中这 种协议报文被称为“配置消息”) 来确定网络的拓扑结构。配置消息中包含了足够的信息来 保证交换机完成生成树计算。 9 南京邮电学院硕士研究生学位论文第二章m s t p 的基本原理 配置消息中主要包括以下内容： ( 1 ) 树根的i d ：由树根的优先级和m a c 地址组合而成： ( 2 ) 到树根的最短路径开销； ( 3 ) 指定交换机的i d ：出指定交换机的优先级和g a c 地址组合而成； ( 4 ) 指定端口的i d ：由指定端口的优先级和端口编号组成： ( 5 ) 配置消息的生存期：m e s s a g e a g e ： ( 6 ) 配置消息的最大生存期：m a x a g e ； ( 7 ) 配置消息发送的周期：h e l l o t i m e ： ( 8 ) 端口状态迁移的延时：f o r w a r d d e l a y 。 2 1 2 生成树协议算法实现 结合例子说明生成树协议算法实现的计算过程，具体的组网如图6 所示： 9 i i e n b 优先缀为1 图6 以太网交换机组网图 为描述方便，在举例中仅给出配置消息的前四项 h ，1 5 ：树根i d ( 以以太网交换机的优 先级表示) ，根路径行销，指定交换机i d ( 以以太网交换机的优先级表示) ，指定端口i d ( 以 端口号表示) 。如上图所示，s w i t c ha 的优先级为0 ，s w i t c hb 的优先级为l ，s w i t c hc 的 优先级为2 ，各个链路的路径开销如图中所示，分别为5 、1 0 、4 。 ( 1 ) 初始状态 各台交换机的各个端口在初始时会生成以自己为根的配置消息，根路径开销为0 ，指定交 换机i d 为自身交换机i d ，指定端口为本端口。 s w i t c ha ： 1 0 南京邮电学院硕士研究生学位论文第二章m s t p 的基本原理 端i a p i 配置消息： 0 ，0 ，0 ，a p i ) 端口a p 2 配置消息： 0 ，0 ，0 ，a p 2 s w i t c hb ： 端口b p l 配置消息： 1 ，0 ，1 ，b p l 端口b p 2 配置消息： 1 ，0 ，1 ，b p 2 s w i t c hc ： 端口c p 2 配置消息； 2 ，0 ，2 ，c p 2 ) 端口c p l 配置消息： 2 ，0 ，2 ，c p i ( 2 ) 选出最优配置消息 各台交换机都向外发送自己的配置消息。当某个端口收到比自身的配置消息优先级低的 配置消息时，交换机会将接收到的配置消息丢弃，对该端口的配置消息不作任何处理。当端 口收到比本端口配置消息优先级高的配置消息的时候，交换机就用接收到的配置消息中的内 容替换该端口的配最消息中的内容。然后以太网交换机将该端口的配置消息和交换机上的其 它端口的配置消息进行比较，选出最优的配置消息。 配置消息的比较原则是： 树根i d 较小的配置消息优先级高： 若树根i d 相同，则比较根路径开销，比较方法为：用配置消息中的根路径开销加上 本端口对应的路径开销之和( 设为s ) ，则s 较小的配置消息优先级较高： 若根路径开销也相同，则依次比较指定交换机i d 、指定端口i d 、接收该配置消息的端 口i d 等。 为便于表述，本例中假设只需比较树根i d 就可以选出最优配置消息。 ( 3 ) 确定根端口，并阻塞冗余链路，然后更新指定端口的配置消息，交换机接收最优配 置消息盼那个端口定为根端口 7 ，9 | 端口配置消息不作改变；其它端口中，如果某端口的配 置消息在过程“选出最优配置消息”中更新过，则交换机将此端口阻塞，端口配置消息不变， 此端口将不再转发数据，并且只接收但不发送配置消息：如果某端口的配置消息在过程“选 出最优配置消息”中没有更新，则交换机就将其定为指定端口，配置消息要作如下改变：树 根i d 替换为根端口的配置消息的树根i d ：根路径开销替换为根端口的配置消息的根路径开销 加上根端口对应的路径开销；指定交换机i d 替换为自身交换机的i d ；指定端口i d 替换为自 身端口i d 。 例子中各台交换机的比较过程如下： 南京邮电学院硕士研究生学位论文 第二章m s t p 的基本原理 s w i t c ha ： 端u a p i 收至i s w i t c h8 的配置消息，s w i t c ha 发现本端口的配置消息优先级高于接收 到的配置消息的优先级，就把接收到的配置消息丢弃。端e i a p 2 的配置消息处理过程与端口 a p i 类似。s w i t c ha 发现自己各个端口的配置消息中树根和指定交换机都是自己，则认为自 己是树根，各个端口的配置消息都不作任何修改，以后周期性的向外发送配置消息。此时两 个端口的配置消息如下： 端i a p i 配置消息： 0 ，0 ，0 ，a p i ) 。 端d a p 2 配置消息： 0 ，0 ，0 ，a p 2 ) 。 s w i t c h8 ： 端口b p i 收到来自s w i t c ha 的配置消息，经过比较后s w i t c hb 发现接收到的配置消息 的优先级比端k i b p i 的配置消息的优先级高，于是更新端i b p i 的配置消息。 端口b p 2 收到来自s w i t c hc 的配置消息，s w i t c hb 发现该端口的配置消息优先级高于 接收到的配置消息的优先级，就把接收到的配置消息丢弃。则此时各个端口的配置消息如下： 端d b p i 配置消息： 0 ，0 。0 ，a p i ，端口b p 2 配置消息： 1 ，0 ，1 ，b p 2 。s w i t c hb 对各 个端口的配置消息进行比较，选出端i b p i 的配置消息为最优配置消息，然后将端口b p i 定 为根端口，整台交换机各个端口的配置消息都进行如下更薪： 根端口b p i 配置消息不作改变： 0 ，0 ，0 ，a p i 。端 3 b p 2 配置消息中树 根i d 更新为最优配置消息中的树根i d ，根路径开销更新为5 ，指定交换机i d 更新为本交换机 i d ，指定端口i d 更新为本端口i d ，配置消息变为： 0 ，5 ，1 ，b p 2 。 然后s w i t c hb 各个指定端口周期性向外发送自己的配置消息。 s w i t c hc ： 端d c p 2 先会收到来自s w i t c hb 端口b p 2 更新前的配置消息( 1 ，0 ，i ，b p 2 ， s w i t c he 触发更新过程，更新后的配置消息如下： i ，0 ，1 ，b p 2 。 端口c p i 收到来自s w i t c ha 的配置消息 0 ，0 ，0 ，a p 2 ) 后s w i t c hc 也触发更新过程， 更新后的配置消息如下： 0 ，0 ，0 ，a p 2 。 经过比较，端d c p i 的配置消息被选为最优的配置消息，端d c p i 就被定位根端口，它 的配置消息就不作改变；而端i c p 2 就会被阻塞，端口配置消息也不作改变，同时该端口不 接收从s w i t c hb 转发的数据( 不包括s t p 的协议报文) ，直到新的情况发生触发生成树的重 新计算，比如从s w i t c hb 至l j s w i t c h c 的链路d o w n 掉，或者端口收到更优的配置消息。 接着端i c p 2 会收至i s w i t c hb 更新后的配置消息 0 ，5 ，l ，b p 2 ，由于收到的配置消息 南京邮电掌院_ 哦上研咒生学位论文 第一帚m s t p 的基本壕理 比原配置消息优，则s w i t c hc 触发更新过程，更新后的配置消息为： 0 ，5 ，l ，b p 2 ) 。同时 端口c p l 收到来自s w i t c ha 配置消息，比较后s w i t c hc 不会触发更新过程，配置消息仍然 为：f 0 ，0 ，0 ，a p 2 。经过比较，端d c p 2 的配置消息被选为最优的配置消息，端d c p 2 就 被定为根端口，它的配置消息就不作改变，而端d c p i 就被阻塞，端口配置消息不变，同时 不接收从s w i t c ha 转发的数据，直到新的情况触发生成树的计算。 比如从s w i t c hb 到s w i t c hc 的链路d o w n 掉。此时生成树就被确定下来，形状如图7 ， 树根为s w i t c ha ： 8 w i t c h b 优先缀为1 图7 最终稳定的生成树 本例为了描述方便，简化了很多计算、操作内容( 比如树根i d 和指定交换机i d 在实际 运算的过程中应该是由交换机的优先级和m a c 地址共同组成的，指定端口i d 则是由端口优先 级和端口姒c 地址共同构成；在配置消息的更新过程中，除了前四项会改变以外，其它配置 消息也会按照一定的原则进行改变) ，但计算过程基本如此。 2 1 3 生成树协议的配置消息传递机制 当网络初始化时，所有的交换机都将自己作为树根。交换机的指定端口以h e l o t i m e 为 周期，定时发送本端口的配置消息：接收到配置消息的端口如果是根端口，则交换机将配罱 消息中携带的m e s s a g e a g e 按照一定的原则递增，并启动定时器为这条配置消息计时。如果某 条路径发生故障，则这条路径上的根端口不会再收到新的配置消息，旧的配置消息将会因为 超时而被丢弃，从而引发生成树的重新计算，得到一条新的通路替代发生故障的链路，恢复 网络连通性。 3 堕塞塑皇兰堕竺主旦塞圭兰垡堡兰蔓三童竺! ! ! 塑茎查堕墨 不过，重新计算得到的新配置消息不会立刻就传遍整个网络，因此那些没有发现网络拓 扑已经改变的旧的根端口和指定端口仍旧会按照原来的路径继续转发数据，如果新选出的根 端口和指定端口立刻就开始数据转发的话，可能会造成暂时性的路径回环。为此s t p 采用了 一种状态迁移的机制，根端口和指定端口重新开始数据转发之前要经历一个中间状态，中间 状态经过f o r w a r d d e l a y 延时后才能进入转发状态，这个延时保证了新的配置消息已经传遍整 个网络。这样一个v l a n 的报文将沿着如下路径进行转发：在m s t 域内将沿着其对应的m s t i 转 发，在域间则沿着c s t 转发。 2 2 课题背景和论文工作 2 2 1 项目背景 本文的主要工作是在中兴通讯网络事业部z x r i o 项目组进行的，项目组为本文的工作提 供了良好的实验条件和工作环境。z x r i o 高端路由器是中兴通讯承担的国家8 6 3 项目的研发 成果，作为国内首家获得信息产业部高端路由器入网证的设备，在众多国内外运营商及企业 网中得到广泛应用。 m s t p 是交换机和路由器等数据产品中需要实现的重要协议功能，是整个网络应用的基 础，本文对n s t p 的研究是作为l 2 协议系统的一部分而展开的。 2 2 2 本文工作 本文工作主要包括以下几个方面： 1 本文确定了m s t p 需要实现的功能集，完成了m s t p 功能模块的划分，并给出了系统设计方 案。 2 在对i e e e 8 0 2 1 d ，8 0 2 1 w ，8 0 2 1 s 阅读分析的基础上，完成了m s t p 在实时嵌入式操作系统 v x w o r k s 下的实现工作，并考虑了与z x r i o 系列三层高性能交换机的其他底层模块的交互。 这是本文最主要的工作之一。 3 立足于现有的条件，对协议实现了基本功能的测试，并给出具体测试环境， 1 4 南京邮电学院硕士研究生学位论文第三章m s t p 在v x w o r k s 下的设计与实现 第三章m s t p 在v x w o r k s 下的设计与实现 多生成树协议软件在实现中，应用多生成树算法，以i e e e 8 0 2 1 组织发布的标准8 0 2 i s 为基本框架，在大型网络的不同网络部分，通过m s t 来定位不同v l a n s 和生成树进程的分配， 从而可以更容易的管理网络和使用冗余路径，一个树进程只能存在于具有一致的v l a n 进程分 配的桥中。m s t p 的实现影响着整个网络的拓扑，却又独立于三层路由协议。本章着重介绍了 m s t p 在实时嵌入式操作系统v x w o r k s 的实现方案。 3 1 需求分析 m s t p 模块在利用普通生成树所提供的应用基础之上，增加了端口权限的分配，修改端口 状态集以及增加优先级向量的概念，利用状念机的迁移，增加对带有v l a ni d