（计算机软件与理论专业论文）以太网交换机快速生成树协议的研究与实现.pdf

西南交通大学硕士研究生学位论文第1 页 捅晏 生成树协议是网络二层设备的基础协议之一，它通过分布式计算使得网 络活动拓扑为树型结构，从而有效地防止了网络中回路的出现，避免了由于 帧的无限循环和重复接收所导致网络风暴的发生。从最初的s t p ( 基本生成树 协议) 到r s t i ( 快速生成树协议) 再到后来的m s t p ( 多生成树协议) ，生成树协 议演化出了很多版本，网络活动拓扑的形成和收敛速度也越来越快。目前 般的交换机或者交换式桥接器上都实现了s t p ，s t p 的收敛时间在几十秒钟 以内，而且运行该协议所需要的系统资源较少，能满足一般的网络需要。但 随着网络速率和规模的越来越大，多媒体的应用越来越普及，几十秒的等待 对闻对用户来说难以忍受。为此很多交换机厂商都采取了特有的技术来缩短 这个时间，但这些技术之间缺乏兼容性和互操作性。在这种情况下，i e e e 委 员会制定了r s t p 标准，称为i e e e 8 0 2 1 w ，r s t p 的收敛时间能控制在秒级。 本文以某公司的实际产品开发为背景，对这一技术进行了系统、深入、全面 的分析，并在特定的软硬件环境下对r s t p 的实现进行了详细的介绍，主要 工作如下： 1 介绍了实现r s t p 协议的软硬件载体( 以太网交换机、v x w o r k s 嵌入 式操作系统、t m s 2 0 软件包) 。 2 对r s t p 理论进行了深入的探讨，包括其工作原理、状态机、优点和 缺陷等，着重在对i e e e 8 0 2 1 w 标准文档的分析上。并在此基础上给 出一个仿真模型，详细描述了r s t p 计算一个简单的八节点局域网络 的根网桥、根端口、指定网桥、指定端口、备份端口和替换端口的全 过程。 3 对特定平台下r s t p 的实现进行了介绍，包括模块设计、数据结构设 计、子程序设计等内容。分析了r s t p 与t m s 2 0 框架中其它协议模 块的关系，并设计了它们之间的重要接口。 4 对本设计进行了客观分析，提出了优化和改进的方法，并进行了比较 测试。 关键词：交换机；生成树协议；快速生成树协议 西南交通大学硕士研究生学位论文第1 i 页 a b s tr a c t s p a n n i n g t r e ep r o t o c o li st i l eb a s i cp r o t o c o lo fn e t w o r k e q u i p m e n ti nl a y e r t w o i tm a k e st h es t r u c t u r eo fn e t w o r k sa c t i v e t o p o l o g y l i k e at r e e b y c o m p l i c a t e dc o m p u t i n g s o i tc a na v o i dn e t w o r ks t o r mb r o u l g h tb yl o o p sa n d r e p e a t e dr e c e i v i n go ff r a m e f r o mt h es t p t or s t pa n dt h e nm s t p e t c ，m a n y s p a n n i n g t r e e p r o t o c o l c o m ei n t o b e i n g t h es p e e d o fa c t i v e t o p o l o g y c o n s t r i n g e n c yi sm o l ea n d m o r e r a p i d n o r m a ls w i t c ho rb r i d g eh a si m p l e m e n t e d s 他w h i c hc a l l c o n s t r i n g e i ns e v e r a lt e ns e c o n d sa n di tn e e dl i t t l e s y s t e m r e s o u r c e s t pc a n s a t i s f ym o s ta p p l i c a t i o n o fn e t w o r k b u tg o i n gw i t ht h e d e v e l o p m e n t o fn e t w o r k sv e l o c i t ya n dt h ea p p l i c a t i o no f m u l t i m e d i a ，t h i st i m ei s o p p r e s s i v et ot h eu s e lt or e s o l v et h i sp r o b l e m ，m a n yf a c t o r i e so fs w i t c ht a k e s p e c i a lt e c h n o l o g y , b u tt h e i rp r o d u c t sa r es h o r to fc o m p a t i b i l i t y i nt h i sc a s e ，t h e c o m m i t t e eo fi e e es t a n d a r db e 沓n st oe s t a b l i s ht h er s t p s t a n d a r d ，i ti sn a m e d 8 0 2 1 ws t a n d a r dd o c u m e n t ，t h et i m eo f c o n s t r i n g e n c y i ss e v e r a ls e c o n d n o wi ti s t h em a i nt e c h n o l o g yo f s p a n n i n gt r e ep r o t o c 0 1 i ns o m ea d v a n c e ds w i s h i t g e t s w i d ea p p l i c a t i o n t h i st h e s i sb a s e so na c t u a lp r o d u c to f s w i t c h ，e x p a t i a t e sr s t p s y s t e m i ca n de m b e d d e d a n d i ti n t r o d u c e sd e t a i l e dt h ei m p l e m e n t i o no fr s t po n s p e c i f i c a l l yp l a t f o r m m y m a i nw o r ka sa l l o w s ： 1 i n t r o d u c et h eh a r d w a r ea n ds o f t w a r e e n v i r o n m e n t ( s w i t c h ，v x w o r k s r t o s ，t m s 2 0p a c k a g e ) 2 a n a l y z e t h et h e o r yo f r s t p ，i n c l u d i n gt h e o r y , s t a t em a c h i n e ，a d v a n t a g e ， a n dd e f e c t g i v eam o d e lo f8n o d e sl a nt o s i m u l a t e e x p l a i nt h e p r o c e s so fa c t i v et o p o l o g yc o m i n gi n t ob e i n g 3 i n t r o d u c et h e i m p l e m e n t i o n o f r s t p , i n c l u d i n g m o d e l d e s i g n ，d a t a s t r u c t u r ed e s i g na n ds u b p r o c e d u r ed e s i g ne t c e s p e c i a l l yt h ei n t e r f a c e b e t w e e nr s t pa n do t h e rm e d u l e e 4 a n a l y z e t h i si m p l e m e n t i o n ，b r i n gf o r w a r dam e t h o do fe n h a n c e m e n t ，a n d g i v et h et e s t k e yw o r d s ：s w i t c h ，s t p ，r s t p 西南交通大学硕士研究生学位论文第1 页 绪论 1 1 课题背景 交换机是网络的核心设备之一，其技术发展非常迅速。以太网交换机已 经走出了当初的桥接框架，广泛应用到汇聚层和骨干层，交换机和路由器逐 渐融合的趋势越来越明显。而且当前我国的经济形势良好，持续稳定发展， 各行各业对信息化、网络建设和升级的需求都很迫切，这是以太网交换机设 备市场强大的驱动力。尤其是电信、金融、政府和教育等大型行业信息化工 程的开展、宽带城域网建设力度的加大，对网络和网络设备提出了更高的要 求，大大促进交换机市场的增长，特别是高端路由交换机市场的增长。据统 计显示，高端路由交换机销量占到以太网交换机总销售量的五分之一，而销 售额占市场总销售额的一半，可以看出高端市场是以太网交换机市场的主要 利润区。本文来源于某公司的实际项目，在其高端以太网交换机上实现 r s t p 。该项目成员共三人，笔者参与了项目开发的全过程，与项目组成员一 道，完成了方案设计、详细设计、编码和测试的工作。 1 2 国内外研究现状 目前生成树协议已经演化出许多版本，性能越来越好，对硬件资源的要 求也越来越高。以m s t p 为例，它是基于多生成树的协议，是当前研究的热 点之一，但由于该技术较复杂，主要掌握在国外大公司手中，对于国内的交 换机生产厂商来说，r s t p 才是主流技术。一些低端的设备，比如二层交换 机，为了控制成本，一般只要实现s t p 就行了。对于高端的交换机，比如三 层交换机，甚至是路由交换机，一般要求实现r s t p 。r s t p 的收敛速度能控 制在秒级，对于大多数网络应用来说，这个收敛时间都能满足需求。从1 9 9 9 年i e e e 委员会开始制定该标准以来，历经许多专家学者的修改和完善，r s t p 协议经受住了实践检验，得到了广大交换机设备厂商的认可和支持。但是我 们也应该认识到每一项技术都不是十全十美的，r s t p 理论也有它的缺陷， 还需要继续研究。i e e e 8 0 2 1 w 文档中定义了r s t p 的内核即8 个状态机，至 于如何实现r s t p 并不象s t p 一样有示例代码。目前能查到的国内外的各种 文献也都是对r s t p 理论的研究，没有具体实现的例子。不同的厂商硬件种 类多种多样，软件构架也各不相同，如何在具体的软硬件环境中有效的实现 西南交通大学硕士研究生学位论文第2 页 r s t p ，发挥出r s t p 的优越性能，有很强的实用意义。 1 3 研究内容 本文主要的研究内容如下： ( 1 ) 深入理解r s t p 协议，分析其核心算法。 ( 2 ) 用一个计算实例对该算法进行验证。 ( 3 ) 在t m s 2 0 框架中实现r s t p 协议。 1 4 论文组织结构 本文的后续章节主要反映了笔者所涉及的工作，按照以下方式进行组织： 第一章：绪论，介绍了本课题的背景、国内外的研究现状、作者的研究 内容、论文的组织结构。 第二章：软硬件环境，主要介绍了v x w o r k s 操作系统和t m s 2 0 软件包 以及交换机的一些基础知识。 第三章：快速生成树协议介绍，对生成树协议的发展、r s t p 的理论、 i e e e 8 0 2 1 w 参考文档等进行了分析，并在此基础上给出了一个仿真实例。 第四章：快速生成树协议的实现，介绍了具体软硬件环境下r s t p 的实 现，包括其模块设计、数据结构设计，子程序设计等内容。 第五章：优化和改进，针对本设计，提出了一些优化和改进的方法并做 了一些对比测试。 西南交通大学硕士研究生学位论文第3 页 第二章软硬件环境介绍 2 1v x w o r k s 操作系统简介 嵌入式系统是以应用为中心，以计算机技术为基础，并且软硬件可裁剪， 适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算 机系统。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及用 户的应用程序等四个部分组成，用于实现对其他设备的控制、监视或管理等 功能。w r s 是国际著名的嵌入式实时操作系统的供应商，其产品v x w o r k s 操 作系统是专门为实时嵌入式系统设计开发的操作系统软件，为程序员提供了 高效的实时任务调度、中断管理、实时的系统资源以及实时的任务间的通信。 应用程序员可以将尽可能多的精力放在应用程序本身，雨不必再去关心系统 资源的管理。嵌入式软件开发是一种比较复杂的劳动，操作系统性能再好， 仅仅依靠人工编程调试很难发挥它的功能，要设计出可靠、高效的嵌入式系 统，必须要有与之相适应的开发工具，t o r n a d o 就是为开发v x w o r k s 应用系 统提供的集成开发环境。针对通信行业的特定应用，v x w o r k s 还有相应的软 件支持包t m s ( t o r n a d of o rm n a n g e ds w i t c h e s ) ，在此基础上用户可以快速 地开发网络通信产品。 2 。1 。1v x w o r k s 任务 软件设计时通常将应用划分成独立的、相互作用的程序，当这些程序执 行时，我们称之为任务。g x w o r k s 的任务可以直接或共享访问大多数系统资 源，这些任务共同合作来实现整个系统的功能。多任务提供一种机制，使得 应用程序可以控制响应多重的、离散的事件，v x w o r k s 实时内核提供基本的 多任务环境。每个任务有自己的上下文( c p u 环境、系统资源等) ，任务由系 统内核调度运行，在任务切换时，任务的上下文保存在任务控制块( t c b ) 中。 需要注意的是，与? i n d o w s 操作系统不同，v x w o r k s 操作系统的内存是线性 的，所有代码执行在单一的公共地址空间内，因而内存地址空间不属于任务 上下文，每个任务各自的地址空间需要虚地址到物理地址的转换映射。 2 1 i 1 任务状态转换 任务状态反映任务当前在系统中所处的情形。内核负责维护系统中所有 任务的当前状态，一个任务从一个状态变为另一个状态是内核调用的结果。 西南交通大学硕士研究生学位论文第4 页 同一时刻，只有一个任务在执行。v x w o r k s 内核状态有四种基本状态和若干 种复合状态。 就绪( r e a d y ) 处于这种状态的任务除了等待c p u 外，不需要等待其他资源。 阻塞( p e n d ) 处于这种状态的任务等待的资源目前不可用。 睡眠( d e l a y ) 处于这种状态的任务由于某时间点未到而休眠。 挂起( s u s p e n d ) 处于这种状态的任务不能执行，主要用于出错时的调试。 2 1 1 2 任务调度 任务调度是根据一定的规则，将c p u 的使用权分配给符合条件的任务， 这些规则称为调度算法。v x w o r k s 内核默认采用基于优先级的抢占式调度算 法，同时还可以选用时间片轮转调度算法。 如果使用基于优先级的抢占式调度算法，系统中的每个任务都有一个优 先级，任一时刻，内核将c p u 分配给处于就绪状态的优先级最高的任务执行。 如果系统内核发现有一个任务优先级比当前正在运行的任务的优先级高的任 务转变为了就绪态，内核立即保存当前运行任务的上下文，将当前任务变为 阻塞态，插入到阻塞队列，并切换到这个高优先级的任务上下文运行。v x w o r k s 内核提供2 5 6 个优先级( 0 2 5 5 ) ，优先级0 最高，2 5 5 最低。任务的优先级 在仓o 建时指定，可以动态改变。 轮转调度算法让优先级相同的、处于就绪态的任务公平地分享使用c p u 资源。如果不使用轮转调度，当系统中存在多个相同优先级的任务共享c p u 时，第一个获得c p u 的任务将独占c p u ，如果没有阻塞出现，它将不会给其 他相同优先级的任务运行的机会。轮转调度是使用时间片来实现这种相同优 先级任务公平分配c p u 资源。一组任务中的每个任务执行一个预先确定的时 间片，然后另一个任务执行相等的时间片，依次进行，机会均等。 2 1 2v x w o r k s 任务间的通信 要想多任务间相互同步和通信以协调各自活动，任务间的通信机制必不 可少。v x w o r k s 提供的任务间通信手段包括信号量、消息队列、管道、套接 字等。本文主要涉及前两种通信方式。 西南交通大学硕士研究生学位论文第5 页 2 1 2 1 信号量 y x w o r k s 信号量是提供任务闻通信、同步和互斥的最优选择，它提供任 务间的最快速通信，是任务间同步和互斥的主要手段。v x w o r k s 有三种类型 的信号量，用于解决不同的问题。 二进制信号量 最快最常用的信号量，可以用于同步和互斥。 互斥信号量 为解决具有互斥问题、优先级继承问题、删除安全问题和递归问题等 情况而优化了的特殊的二进制信号量。 计数器信号量 类似于二进制信号量，但是随信号量释放的次数的改变而改变，适合 于一个资源的多个实例需要保护的情形。 为了简化程序设计，v x w o r k s 信号量提供一套单一的接口用于控制信号 量，而不是为每种信号量定义一套完整的信号量控制函数。信号量的类型仅 仅由创建函数确定，其他接口根据需要处理的信号量的类型自动完成相应的 操作。信号量在创建的时候，队列类型就已经确定。等待一个信号量的任务 可以按优先级( s e m - q p r i o r i t y ) 或按先进先出( s e mqp i f o ) 的顺序排队。信 号量的控制函数主要有：s e m b c r e a t e ( ) ，分配并初始化一个二进制信号量； s e m m c r e a t e0 ，分配并初始化一个互斥信号量；s e m c c r e a t e ( ) ，分配并初始 化一个计数器信号量；s e m d e l e t e 0 ，终止并释放一个信号量；s e m t a k e0 ， 获取一个信号量；s e m g i v e0 ，释放一个信号量；s e m f l u s h0 ，解锁所有等待 该信号置的任务。 2 1 - 2 2 消息队列 信号量提供高速的任务间同步和互斥机制，但是常常还需要一种较高级 的合作任务之间相互通信的机制。7 x w o r k s 提供任务通信的全局消息队列， 消息队列允许长度可变、数目可变的消息排队。任何任务可以发送消息到消 息队列，任何任务可以从消息队列接收消息。多个任务可以向同一个消息队 列发送消息或接收消息。消息队列由函数m s g q c r e a t e 0 创建，以它能够排队 的最大消息数目以及每个消息的最大字节长度作为参数。任务调用 m s g q s e n d ( ) 来向消息队列发送消息。此时如果没有任务在等待该队列中的消 息，那么该消息进入消息队列的缓冲。如果有任务等待该队列的消息，那么 西南交通大学硕士研究生学位论文第6 页 这个消息立即提交给第一个等待的任务。任务调用m s g q r e c e i v e ( ) 从消息队 列接收消息。如果队列缓冲中有可用的消息，那么第一个消息立即出队，并 返回给调用者。如果没有消息可用，调用者将阻塞，进入等待该消息的任务 队列排队。任务调用m s g q d e l e t e 0 来删除消息队列。 2 1 3t m s 2 0 简介 t m s 的全称是t o r n a d of o rm a n a g e ds w i t c h e s ，它是、 ，i n d r i v e r 为快速开 发网络产品而提供的一个软件包，目前的版本是t m s 2 0 。t m s 是一个可裁 剪的组件结构，定义了从底层硬件驱动到上层协议软件的全套解决方案。 t m s 上层协议部分实现了大部分的t c p i p 协议栈，支持大部分的i e t f 、i e e e 等标准和s n m pm i b 库，为用户开发各种产品提供了便利。t m s 定义了一 种l 2 的构架允许将一个物理端口映射为逻辑端口，许多概念如v t a s ( 虚拟 局域网，8 0 2 。l q ) 、l i n k a g g r e g a t i o n ( 链路聚合，8 0 2 3 a m 、s p a n n i n gt r e e ( 生成 树，8 0 2 d w s ) 都能够被支持，这种构架也支持v l a n 间的路由和l 3 路由。 t m s 中对端口的操作都是基于逻辑端口的，不是物理端口，这就实现了硬件 和协议间的独立。其构架如图2 - 1 所示： ( 1 ) h a r d w a r e e n d ，即h w 层，与硬件的物理端口一一对应。 ( 2 ) a g g r e g a t i o np o r ts u b e n d ，即a p 层，在t m s 中对应交换机t r u n k 的 物理端口。 ( 3 ) a g g r e g a t o rs u b e n d ，即a g 层，在t m s 中对应交换机t r u n k 的逻辑端 口。r s t p 协议通过m u x 直接绑定到a g 层，即从a g 层收取报文。 f 4 1s w i t c hs u b e n d ，即s w 层，在t m s 中对应交换机的接口。 ( 5 ) m u x ( v x w o r k s p r o t o c o lm u l t i p l e x e r ) ，即v x w o r k s 协议复用器。s w 层、 a g 层、a p 层通过m u x 与相关的协议模块( 如i p 、b o o t p 、d h c p ， g v r p 、g m r p 、r s t p 、8 0 2 1 x ) 相连接。这些协议模块就可以通过m u x 提供的接口从不同的层次收取报文。 ( 6 】l 2 、l 3 + ，即二层协议、三层协议和其他上层协议。本文的将要介绍 的r s t p 协议就位于l 2 上。 西南交通大学硕士研究生学位论文第7 页 圈2 一i t m s 端口映射 2 2 交换机关键技术简介 以太网交换机，英文为s w i t c h ，也有人翻译为开关，交换器或交换式集 线器。我们首先回顾一下局域网的发展过程。计算机技术与通信技术的结合 促进了计算机局域网络的飞速发展，从六十年代末a l o h a 的出现到九千年代 中期1 0 0 0 m b p s 交换式以太网的登台亮相，短短的三十年间经过了从单工到双 工，从共享到交换，从低速到高速，从简单到复杂，从昂贵到普及的飞跃。 八十年代中后期，由于通信量的急剧增加，促使技术的发展，使局域网的性 能越来越高，最早的i m b p s 的速率已广泛地被今天的i o o b a s e - - t 和i o o c g - - a n y l a n 替代，但是，传统的媒体访问方法都局限于使大量的站点共享对一个 公共传输媒体的访问，即c s 姒c d 。九十年代初，随着计算机性能的提高以 及通信量的聚增，传统局域网已经愈来愈超出了负荷，交换式以太网技术应 运而生，大大提高了局域网的性能。与现在基于网桥和路由器的共享媒体的 局域网拓扑结构相比，网络交换机能显著的增加带宽。交换技术的加入，就 可以建立地理位置相对分散的网络，使局域网交换机的每个端口可平行、安 全、同时的互相传输信息，而且使局域网可以高度扩充。局域网交换技术的 西南交通大学硕士研究生学位论文第8 页 发展要追溯到两端口网桥。桥是一种存储转发设备，用来连接相似的局域网。 从互联网络的结构看，桥是属于第二层的连接：从协议层次看，桥是在逻辑 链路层对数据帧进行存储转发；与中继器在第一层、路由器在第三层的功能 相似。两端口网桥几乎是和以太网同时发展的。以太网交换技术是在多端口 网桥的基础上于九十年代初发展起来的，实现o s i 模型的下两层协议，与网 桥有着千丝万缕的关系，甚至被业界人士称为“许多联系在一起的网桥”，因 此现在的交换式技术并不是什么新的标准，而是现有技术的新应用而已，是 一种改进了的局域网桥，与传统的网桥相比，它能提供更多的端口、更好的 性能、更强韵管理功篦以及更便宜的价格。 2 2 1 交换机基本工作原理 局域网交换技术是o s i 参考模型中的第二层数据链路层( d a t a l i n k l a y e r ) 上的技术，所谓“交换”实际上就是指转发数据帧( f r a m e ) 。在数据通 信中，所有的交换设备( 即交换机) 执行两个基本的操作： ( 1 ) 交换数据帧，将从输入介质上收到的数据帧转发至相应的输出介质。 ( 2 ) 地址学习过程，用以构造和维护交换地址表，以便维护交换操作。 下面，我们探讨一下这两个基本搡作的具体细节。 2 2 1 1 数据帧转发 交换机根据数据帧的m a c ( m e d i aa c c e s sc o n t m l ) 地址( 即物理地址) 进行 数据帧的转发操作。交换机转发数据帧时，遵循以下规则： ( 1 ) 如果数据帧的目的m a c 地址是广播地址或者组播地址，则向交换机 所有端口转发( 除数据帧来的端口) ： ( 2 ) 如果数据帧的目的地址是单播地址，但是这个地址并不在交换机的地 址表中，那么也会向所有的端口转发f 除数据帧来的端口) ； ( 3 ) 如果数据帧的目的地址在交换机的地址表中，那么就根据地址表转发 到相应的端口； ( 4 ) 如果数据帧的目的地址与数据帧的源地址在一个网段上，它就会丢弃 这个数据帧，交换也就不会发生。 2 2 1 2 地址学习过程 交换机的交换地址表中，一条表项主要由一个主机m a c 地址和该地址所 位于的交换机端口号组成。整张地址表的生成采用动态自学习的方法，即当 交换机收到一个数据帧以后，将数据帧的源地址和输入端口记录在交换地址 西南交通大学硕士研究生学位论文第9 页 表中。图2 2 为交换枫收到帧时的转发及学习过程。当一个帧从交换机某个 特定端口x 到达，交换机根据这两个信息可以得出：从端口x 可以到达帧源 地址域所指定的工作站，因此，交换机能够为该m a c 地址更新转发数据库。 为允许网络拓扑结构发生变化，数据库的每一项都配有寿命定时器，当一个 新项加到数据库时，就启动定时器，定时器的缺省值是3 0 秒，如果定时器时 间到，该项就从数据库搜索是否存在地址字段值和该帧源地址相同的项，如 果数据库已存在这样的项，项的内容被更新，重新设置定时器值。如果数据 库中不存在这样的项，将在数据库中添一新项，该新项中的地址为收到数据 帧的源m a c 地址，端口号为收到数据帧的端口，定时器值被设置成初值。 图2 2 网轿转发帧和地址学习流程 西南交通大学硕士研究生学位论文第1o 页 2 2 2 交换机的转发模式 交换机在交换数据帧时可以选择三种不同的交换模式： ( 1 ) 存储转发模式 存储转发( s t o r e a n d - f o r w a r d ) 模式是指交换机收完整个数据帧， 并在c r c 校验通过之后，才能进行转发操作。如果c r c 校验失败， 即数据帧有错，交换机则丢弃此帧。这种模式保证了数据帧的无 差错传输，当然其代价是增加了传输延迟，而且传输延迟随数据 帧的长度增加而增加。 ( 2 ) 快速转发模式 快速转发( f a s t f o r w a r d ) 模式是指交换机在接收数据帧时，一旦 检测到目的地址就立即进行转发操作。但是，由于数据帧在进行 转发处理时并不是一个完整的帧，因此数据帧将不经过校验、纠 错而直接转发，造成错误的数据帧仍然被转发到网络上，从而浪 费了网络的带宽。这种模式的优势在于数据传输的低延迟，但其 代价是无法对数据帧进行校验和纠错。 ( 3 ) 自由分段模式 自由分段( f r a g m e n t f r e e ) 模式是交换机接收数据帧时，一旦检 测到该数据帧不是冲突碎片( c o l l i s i o nf r a g m e n t ) 就进行转发操 作。冲突碎片是因为网络冲突而受损的数据帧碎片，其特征是长 度小于6 4 字节。冲突碎片并不是有效的数据帧，应该被丢弃。因 此，交换机的自由分段模式实际上就是一旦数据帧已接收的部分 超过6 4 字节，就开始进行转发处理。这种模式的性能介于存储转 发模式和快速转发模式之间。 2 2 3 多层交换技术 局域网交换技术的实现通常采用硬件方式。在局域网的数据帧格式中， 目的m a c 地址的位置是固定的，而且帧头信息的检查和校验非常简单，便于硬 件交换的实现。因此传统的局域网交换都是指第二层交换，即根据第二层的 信息目的m a c 地址进行。在交换模式的介绍中，我们可以看到交换机在进 行交换操作前需要接收一定长度的数据进行相应的转发检测，如果将检测数 据的长度适当增加，即可将二层交换技术扩展为三层交换技术，乃至四层交 换技术。三层交换技术就是将检测数据扩展到i p 分组头标部分，通过检测其 西南交通大学硕士研究生学位论文第11 页 中的i p 地址进行交换，实际上是基于硬件的路由。四层交换技术则是进一步 检查i p 分组头标中的通信协议类型和端口号，可以看作是基于应用的交换。 现在广泛应用的多层交换技术就是将二层、三层和四层交换技术结合起来， 实现“一次路由、多次交换”的功能。 2 2 4 交换机与其它网络通信产品的比较 与交换机联系最紧密的网络通讯设备有交换式集线器和路由器，他们擅 长于不同的领域，相互之间又有一定的交叉。 2 2 4 1 交换机和交换式集线器 交换式集线器都能给终端提供独占带宽，自动建立、维护站表，并且根 据站表内容在输入和输出端口间建立交换通路。交换机由交换式集线器发展 而来，不仅提供了上述功能，并且提供了很多的现在网络所要求的功能：信 息流优先级、服务分类、虚拟网、远程监测、自动流控制、内嵌网络管理代 理等。这些功能构成了高速、灵活、智能、可靠、扩充性好的现代网络，不 仅能提供高速的数据传输能力，而且提供良好的服务质量，把纯粹的数据传 输网延伸到适合多媒体应用、实时数据传输等新的领域。 2 2 4 2 交换机和路由器 传统交换机从网桥发展而来，属于o s i 第二层链路层设备。它根据m a c 地址寻址，通过站表选择路由，站表的建立和维护由交换机自动进行。路由 器属于o s i 第三层即网络层设备，它根据i p 地址进行寻址，通过路由表选择 路由，路由表由路由协议产生。交换机最大的好处是快速，由予交换机只须 识别帧中m a c 地址，直接根据m a c 地址选择转发端口，算法简单，便于a s i c 实现，因此转发速度极高，在l o o m b i t s 和g b i t s 通信链路上能做到线速转 发。但交换机的工作机制也带来回路、负载集中、广播等问题。随着技术的 发展，这些问题现在也都得到了比较好的解决。随着三层交换机的出现，交 换机的作用显得越来越重要。三层交换机与传统路由器相比有如下优点： ( 1 ) 每个接口连接一个子网，子网通过路由器进行传输的速率被接口的 带宽所限制。而三层交换机则不同，它可以把多个端口定义成一个虚 拟网，把多个端口组成的虚拟网作为虚拟网接口，该虚拟网内信息可 通过组成虚拟网的端口送给三层交换机，由于端口数可任意指定，子 网间传输带宽没有限制。 ( 2 ) 合理配置信息资源：由于访问子网内资源速率和访问全局网中资源 西南交通大学硕士研究生学位论文第12 页 速率没有区别，子网设置单独服务器的意义不大，通过在全局网中设 置服务器群不仅节省费用，更可以合理配置信息资源。 ( 3 ) 降低成本：通常的网络设计用交换机构成子网，用路由器进行子网 间互连。目前采用三层交换机进行网络设计，既可以进行任意虚拟子 网划分，又可以通过交换机三层路由功能完成子网间通信，为此节省 了价格昂贵的路由器。 ( 4 ) 交换机之间连接灵活：作为交换机，它们之间不允许存在回路，作 为路由器，又可有多条通路来提高可靠性、平衡负载。三层交换机用 生成树算法阻塞造成回路的端口，但进行路由选择时，依然把阻塞掉 的通路作为可选路径参与路由选择。 相比较而言，路由器的功能较交换机要强大，但速度相对也慢，价格昂 贵。第三层交换机既有交换机线速转发报文能力，又有路由器良好的控制功 能，因此得以广泛应用。 西南交通大学硕士研究生学位论文第1 3 页 第三章快速生成树协议分析 生成树协议是一种二层管理协议，它通过有选择性地阻塞网络冗余链路 来达到消除网络二层环路的耳的，同时具各链路的备份功能。由于生成树协 议本身比较小，所以并不像路由协议那样广为人知，但是它却掌管着端口的 转发大权。真实情况也确实如此，特别是在和别的协议一起运行的时候，生 成树就有可能断了其他协议的报文通路，造成种种奇怪的现象。“生成树协议” 是一个广义的概念，并不是特指i e e e8 0 2 1 d 中定义的s t p 协议，而是包括 s t p 以及在s t p 基础上经过改进了的各种生成树协议。比如本文要介绍的 r s t p 就是通过提供快速的重新配置功能，改进了s t p 。这两种标准都支持、 保持和维护局域网或介质访问控制( t v t a c ) 服务的质量，但支持r s t p 的网络 具有更高的恢复性和可用性。随着越来越多的基于局域网的语音和多媒体应 用的部署，局域网基础设旋底层的可靠性和性能变得至关重要。每一个网络 部件的可用性都是不可缺少的。不仅广域网链路、路由网络应当具有冗余性， 而且桥接路径也应当具有冗余性。桥接器或交换机必须能够检测故障并立即 重新配置，r s t p 就是以此为设计目的。 3 1 生成树协议的发展 网桥在网络发展初期扮演了重要的角色，它会把发向它的数据帧的源m a c 地址和端口号记录下来，下次碰到这个目的m a c 地址的报文就只从记录中的 端口号发送出去，除非目的m a c 地址没有记录在案或者目的m a c 地址本身就 是多播地址才会向所有端口发送。通过网桥，不同的局域网之间可以实现互 通，网络可操作的范围得以扩大，而且由于两桥具备髓c 地址学习功能而不 会像集线器那样造成网络报文冲撞泛滥。但是网桥也有它的缺陷，它的缺陷 就在于它的透明传输。网桥并不能像路由器那样知道报文可以经过多少次转 发，一旦网络存在环路就会造成报文在环路内不断循环和增生，甚至造成的 “广播风暴”，网络将变得不可用，而且在大型网络中故障不好定位，所以 广播风暴是二层网络中灾难性的故障。在这种大环境下，i e e e 委员会制定了 s t p 协议，即8 0 2 1 d 标准文档。s t p 协议的基本思想十分简单，大家知道， 自然界中生长的树是不会出现环路的，如果网络也能够像一棵树祥生长就 不会出现环路。于是，s t p 协议中定义了根桥、根端口、指定端口、路径耗 西南交通大学硕士研究生学位论文第14 页 费等概念，目的就在于通过构造一棵自然树的方法达到裁剪冗余环路的目的， 同时实现链路备份和路径最优化。用于构造这棵树的算法称为生成树算法 ( 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 l d a t a u n i t ) ，该报文的数据区里携带了用于生成树计算的所有有用信息。要了解生 成树协议的工作过程也不难，首先进行根桥的选举。选举的依据是网桥优先 级和网桥m a c 地址组合成的桥i d ，桥i d 最小的网桥将成为网络中的根桥。 图3 - 1 生成树工作过程 在图3 - 1 所示的网络中，各网桥都以默认配置启动，在网桥优先级都一 样( 默认优先级是3 2 7 6 8 ) 的情况下，m a c 地址最小的网桥成为根桥，例如图 3 一l 中的s w l ，它的所有端口的角色都成为指定端口，进入转发状态。接下来， 其他网桥将各自选择一条最优的树枝作为到根桥的路径，相应端口的角色就 成为根端口。假设图3 - 1 中s w 2 和s w 2 、s w 3 之间的链路是千兆链路，s w l 和 s w 3 之间的链路是百兆链路，s w 3 从端口l 到根桥的路径开销的默认值是1 9 ， 而从端口2 经过s w 2 到根桥的路径开销是4 + 4 = 8 ，所以端口2 成为根端口， 进入转发状态。同理，s w 2 的端口2 成为根端口，端口l 成为指定端口，进 入转发状态。根桥和根端口都确定之后一棵树就生成了。下面的任务是裁剪 冗余的环路。这个工作是通过阻塞非根桥上相应端口来实现的，例如s w 3 的 端口l 的角色成为禁用端口，进入阻塞状态( 图中用“x ”表示) 。生成树经 过一段时间( 默认值是3 0 秒左右) 稳定之后，所有端口要么进入转发状态，要 么进入阻塞状态。s t p 的b p d u 仍然会定时从各个网桥的指定端口发出，以维 护链路的状态。如果网络拓扑发生变化，生成树就会重新计算，端口状态也 西南交通大学硕士研究生学位论文 第15 页 会随之改变。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 于1 9 9 9 年推出了8 0 2 1 w 标准，作 为对8 0 2 i d 标准的补充。在i e e e8 0 2 1 w 标准里定义了快速生成树协议r s t p 。 r s t p 协议在s t p 协议基础上做了三点重要改进，使得收敛速度快得多( 最快1 秒以内) 。第一点改进：为根端口和指定端口设置了快速切换用的替换端口和 备份端口两种角色，当根端口指定端口失效的情况下，替换端口备份端口 就会无时延地进入转发状态，无需等待两倍f o r w a r dd e l a y 时间。第二点改进： 在只连接了两个交换端口的点对点链路中，指定端口只需与下游网桥进行一 次握手就可以无时延地进入转发状态。如果是连接了三个以上网桥的共享链 路，下游网桥是不会响应上游指定端口发出的握手请求的，只能等待两倍 f o r w a r dd e l a y 时间进入转发状态。第三点改进：直接与终端相连而不是把 其他网桥相连的端口定义为边缘端口。边缘端口可以直接进入转发状态，不 需要任何延时。由于网桥无法知道端墨是否是直接与终端相连，所以需要人 工配置。 可见，r s t p 协议相对于s t p 协议的确改进了很多。为了支持这些改进， b p d u 的格式做了一些修改，但r s t p 协议仍然向下兼容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 g t r e e ) ，有它自身的诸多缺陷，比如由于整个交换网络只有一棵生成树，在 网络规模比较大的时候会导致较长的收敛时间，拓扑改变的影响面也较大： 而且当链路被阻塞后将不承载任何流量，造成了带宽的极大浪费，这在环行 城域网的情况下比较明显。这些缺陷都是单生成树s s t 无法克服的，于是支 西南交通大学硕士研究生学位论文第16 页 持v l a n 的多生成树协议出现了，常见的有p v s t 、m s t p 等协议。本文着重 讨论r s l 曙协议。 3 2 快速生成树协议概述 快速生成树协议是一种分布式算法，它选择台桥接器或交换机作为生 成树的树根，算法为每台桥接器或交换机上的不同端口分配端口的角色。端 口的角色决定端口是作为将这台桥接器或交换机连接到根桥接器( 根端口) 的 活动拓扑结构的一部分，还是通过这台桥接器或交换机将局域网连接到根桥 接器( 指定的端口) 。无论端口承担什么角色，它们都可以在发生故障的情况 下( 当桥接器、交换杌、端口或局域网发生故障或被拆除时) ，成为提供连接 的替代端口或备用端口。桥接协议数据单元用来计算一个端口的角色，并且 数据单元还包含有关交换机和端口的信息。每个端口还有其端口状态，可以 为丢弃( d i s c a r d i n g ) 、学习( l e a r n i n g ) 或转发( f o r w a r d i n g ) ，只有处于f o r w a r d i n g 状态的端口才可以转发帧。8 0 2 1 d 的关闭( c l o s i n g ) 、阻塞( b l o c k i n g ) 和收听 ( l i s t e n i n g ) 状态已经被合并到一个特定的8 0 2 1 w 丢弃状态中。状态被分配给 端口，以支持和维护m a c 服务的质量。r s t p 协