（计算机系统结构专业论文）千兆ip交换路由器体系结构及调度算法的研究.pdf

上海交通大学硕士学位论文 摘要 l 随着i n t e m e t 网络中多媒体、分布数据库和计算等应用需求的发 展，、网络交互流量的迅速增长，对骨干( b a c k b o n e ) 路由器的交换 能力也要求越来越高。骨干路由器所连接的子网速度现在已达到每 秒千兆位，这就要求路由器的交换速度为每秒n ( 端口数) 倍的千 兆位速率。传统路由器的结构已无法满足这个要求，于是基于交换 结构的高端路由器成为近两年路由器研究的热点。 从体系结构上来说，路由器已经经历了四个发展阶段：单处理 器结构、多处理器结构、基于并行处理的结构和基于交换背板的结 构。基于交换结构的路由器在两方面有重大改进：用交换式背板取 代共享总线式背板和用硬件实现路由查找功能。 本文主要针对以c r o s s b a r 为交换结构的路由器的体系结构和调 度算法展开了研究，所完成的工作有以下几点：分析了提高路由 器性能的三种方法，即提高线卡接入性能，加快路由查找速度以及 提高背板性能。详细讨论了设计一台高速、可扩展以及具有组播 和一定q o s 功能的路由器体系结构和调度策略的各种方案。根据 讨论结果，提出了一个设计方案。参与实现了一台路由器，并介 绍了它的体系结构。 关键词：路由器，交换，交换结构，c r o s s b a r ，调度算法 ar e s e a r c ho nt h ea r c h i t e c t u r e a n d s c h e d u l i n ga l o g r i t h m o fg i g a b i t ss w i t c h i n g r o u t e r s a b s t r a c t w i t ht h e d e v e l o p m e n to fa p p l i c a t i o nr e q u i r e m e n t s o fm u l t i m e d i a ，d i s t r i b u t e d d a t a b a s e sa n d c o m p u t i n g i nt h ei n t e r n e t t r a m cb e t w e e n n e t w o r ki n c r e a s e s i g n i f i c a n t l y t h i sn e e d sb a c k b o n er o u t e r sh a v em o r ea n dm o r ep o w e r f u ls w i t c h i n g c a p a b i l i t i e s t h es p e e do fs u b n e t sc o n n e c t e db yt h e s er o u t e r sh a se x c e e d e dg i g a b i t s p e rs e c o n d t h i sr e q u i r e st h a tt h e i rs w i t c h i n gr a t e se x c e e dn t i m e so fg i g a b i t sp e r s e c o n d w h e r eni st h en u m b e ro far o u t e r s p o r t s 、i t si m p o s s i b l e t ot r a d i t i o n a l s t r u c t u r e dr o u t e r s t h u s m o r ea n dm o r er e s e a r c h e r sc a s tt l l e i r e y e s o nt h e h i g h s w i t c h i n g r a t er o u t e r sb a s e do ns w i t c h i n gf a b r i c s a st ot h e i ra r c h i t e c t u r e s r o u t e r sh a v ead e v e l o p m e n t p r o c e s so f f o u rs t e p s t h e y a r ea sf o l l o w e d ：t h e s i n g l ep r o c e s s o rs t r u c t u r e ，t h em u h i p r o c e s s o rs t r u c t u r e ，t h e s t r u c t u r eb a s e do n p a r a l l e lp r o c e s s i n ga n d t h es t r u c t u r eb a s e do n s w i t c h i n gb a c k p l a n e s t h el a t t e rs t r u c t u r eh a st w o i m p r o v e m e n t s ：t h er e p l a c e m e n to f s h a r e b u s e db a c k p l a n e s b ys w i t c h e db a c k p l a n e sa n d t h er e a l i z a t i o no f r o u t i n g l o o k - u pb y h a r d w a r e i nt h i st h e s i s ，t h ea u t h o rf o c u s e st h er e s e a r c ho nt h ea r c h i t e c t u r ea n ds c h e d u l i n g a l g o r i t h mo fr o u t e r sb a s e do nc r o s s b a rs w i t c h i n gf a b r i c s m a l nw o r k so f t h i st h e s i s a r ea sf o l l o w e d ： 1 a n a l y z i n gt h r e em e t h o d su s e dt oi m p r o v e t h ep e r f o r m a n c eo f r o u t e r s t h e ya r e e n h a n c i n gl i n ec a r d s a b i l i t i e s ，e x p e d i t i n g t h e r o u t i n gl o o k u pp r o c e s sa n d i m p r o v i n g t h ec a p a b i l i t yo f t h e b a c k p l a n e 2 s t u d y i n gi n t e n s i v e l yo nm a n ys c h e m e su s e dt od e s i g nah i g hs p e e d ，s c a l a b l e r o u t e rt h a th a st h ea b i l i t i e so f m u l t i c a s ta n dq o s 3 d e s i g n i n g as c h e m eb a s e do nt h es t u d yo f i m m2 4 i n t r o d u c i n g t h ea r c h i t e c t u r eo far o u t e rt h a tw a s c o d e s i g n e db y t h ea u t h o r k e y w o r d s ：r o u t e r ，s w i t c h i n g ，s w i t c h i n gf a b r i c ，c r o s s b a r , s c h e d u l i n ga l g o r i t h m 上海交通大学硕士学位论文 第一章背景介绍 1 1 路由器的发展及现状 路由器是i n t e m e t 网络中的关键设备，它工作于t c p i p 协议的第三层一网络层，主要 功能是实现路由选择和网络互联。即能够通过一定的途径获知网络的部分或全部的拓扑信 息和各物理线路的网络特性。并在此基础上通过一定的路由选择算法，获知到达各个子网 的最佳路径，建立相应的路由表。从而将一个数据包正确地传送到目的地。其次，它必须 处理不同的数据链路层的协议。 在8 0 年代中后期，为了减小同一物理网络内的竞争冲突，提高网络容量，开始使用“网 桥”( b r i d g e ) 设备。但随着网络规模的扩展和广播流量的增加，以及网桥对广播流量的控 制能力有限，这种方式已不能满足网络的扩展需求。为了解决扩展问题，一些公司( 如c i s c o ， w e l l f l e e t ) 开始开发“路由器”。不同于网桥( 第二层设备) 的是路由器在第三层划分子网， 最初的设计遵守“8 0 2 0 规则”即8 0 的本地流量，2 0 的网间流量，通常一个子网占 用路由器的一个端口。但随着个人主机处理能力的提高和应用需求的快速发展，如多媒体、 分布式计算等，用户需求更高的带宽，“8 0 2 0 规则”变成了“5 0 5 0 规则”1 1 ，2 l 本地流 量和网间流量各占5 0 ，甚至变为倒8 0 2 0 规则。为了提高传输速率又再次引入了第二层 的交换技术，子网之间的连接方式发展成了“路由器+ 交换机”的模式。 随着i n t e m e t 网络中多媒体、分布数据库和计算等应用的发展，网络交互流量的迅速 增长，对骨干( b a c k b o n e ) 路由器的交换能力也要求越来越高。骨干路由器所连接的子网 速度现在已达到每秒千兆位，这就要求路由器的交换速度为每秒n ( 端口数) 倍的千兆位 速率。传统路由器的结构已无法满足这个要求，于是基于交换结构的高端路由器成为近两 年路由器研究的热点。 1 2 路由器的一般体系结构 路由器的一般结构可以描述为如图1 1 所示n ”】，它的执行功能主要划分为两类 趱僻( d a t a p a t h ) 动腊：这些操作执行于通过路由器的每个报文，包括：转发决策 ( f o r w a r d i n gd e c i s i o n ) 、背板和输出链路的调度( s c h e d u l h a g ) ，这些操作在高性能路 由器中通常由硬件实现。 控制( c o n t r 0 1 ) 功艟：这些功能的被调用频率相对较低，通常由软件实现。操作包括 与相邻路由器的路由器表交换、系统配置和管理等。 第6 页 上海交通大学硕士学位论文 由上面的描述可以看出，因为d a t a p a t h 部分的功能被频繁调用，所以提高路由器交换 能力的关键是要提高d a t a p a t h 功能的执行速度。d a a p a t h 的具体组成包括： ：劳发头蔗( f o r w a r d i n gd e c i s i o n ) ：当一个报文到达输入端口时，首先根据它的目的地 址查询转发表。如果在表中发现了这个地址，则将表项中下一跳的m a c 地址放在报 文首部，并将i p 报文的t t l 值减1 、并重新计算报头的校验和。 孝扳( b a c k p l a n e ) ：随后，报文通过背板转交给输出端口。在被交给背板的时候，报 文可能需要排队等待。而如果队列满了，报文有可能被丢弃或被其它报文( 优先级高 的) 替换。 糟凹锤路掘赛( t h eo u 舻u t - l i n ks c h e d u l e r ) ? 报文到达输出口的时候，受制于输出端 口的输出能力也要排队。当前大多数的路由器在输出端口采用f i f o 策略，但在一些 高端路由器中将根据流量、优先级区分报文的类型，并考虑报文离开的时间以满足q o s 需求。 图1 1 ：i p 路由器的一般结构 f i 9 1 1 t h e g e n e r a la r c h i t e c t u r eo f i pr o u t e r s 1 3 体系结构的发展趋势 路由器体系结构的设计方案一直受制于成本、端口数目、性能和可采用的技术等因素 这也是高端路由器和低端路由器的区别所在。 路由器的第一个发展趋势是d a t a p a t h 功能的硬件实现。近几年c m o s 技术的发展，使 得原先软件执行的功能可以大规模地集成在硬件中实现。这种集成不仅仅是能够低成本地 实现原先的功能，而且对整个系统的性能都有很大的提高。 第二个趋势是并行性，并行技术可以获得高性能，原先单一高性能运算单元的功能可 第7 页 上海交通大学硕士学位论文 以由多个低成本的单元完成。 第三个趋势就是摆脱共享总线的模式。在总线模式下，当总线带宽小于端1 3 和c p ui o 速率总和的时候，就造成了共享总线的执行功能之间的“瓶颈”。 第四个趋势是可编程性。路由器的各种接口可以通过软件配置，使得同一接口可以使 用多种不同结构和协议的部件啪。 1 4 路由器的体系结构及演变 图1 2 早期的路由器体系结构 f i g1 2t h e a r c h i t e c t u r eo f o r i g i n a lr o u t e r s 早期的路由器f q - _ - - 部分组成：输入输出端口、共享总线和通用处理器组成。如图1 2 所示。输入输出端口是物理链路的连接点。它主要完成网络层和数据链路层的功能，实现 系统和外部链路的联系。共享总线连接输入输出端口和通用处理器。通用处理器处理路由 协议、创建路由表及完成路由查找。当一个数据包到达输入端口时，它首先执行数据链路 层的解封装，将p 数据包通过共享总线传送给通用处理器。通用处理器查找路由表，决定 转发的输出端口，将该数据包再次通过总线发送给输出端口。这种体系结构的局限是通用 处理器必须处理每个数据包，且每个数据包必须通过总线二次。这最终限制了系统的吞吐 量。总线与c p u 都构成瓶颈。 第二种路由器的体系结构主要针对第一种路由器的瓶颈问题提出了采用多处理器并行 处理路由查找。如图1 3 所示。当数据包到达时，系统根据一定的调度原则决定哪一个c p u 来处理。例如由第一个可用的c p u 来处理该数据包的路由查找或同一目的地址的数据包由 同一c p u 处理。很明显，并行处理缓解了c p u 的瓶颈问题，增加了系统的吞吐量。但每 个数据包仍需通过总线二次，因而总线的拥塞问题仍然存在，仍然构成瓶颈。 第8 页 上海交通大学硕士学位论文 圈一 圈一 图1 3 多处理器的路由器体系结构 f i 9 1 3 t h ea r c h i t e c t u r e o f r o u t e r s b a s e do n m u l t i - p r o c e s s o r s 第三种体系结构进一步加强了并行性。它为每个端口设置一个c p u ，如图1 4 所示。 该c p u 专门用于路由查找，使数据包直接被转发到输出端口。这样每个数据包只占用一次 总线。使总线的利用率提高了一倍。通用处理器完成路由协议、维护端口c p u 上的路由表。 这种结构通过了并行化及减少占用总线的时间进一步提高系统的吞吐量。但这种体系结构 仍有二个缺陷。 图1 4 基于并行处理的路由器体系结构 f i g1 4 t h ea r c h i t e c t u r eo f r o u t e r sb a s e do n p a r a l l e l i s m ( 1 ) 首先路由查找是通过软件实现的，因此受到c p u 速度的限制。另外通用处理器的长 处在于计算而不是输入输出。通过研究，路由查找、队列管理等功能可设计成专用的a s i c 第9 页 上海交通大学硕士学位论文 芯片，因此每个端口上的c p u 可由这种a s i c 芯片来代替，且性能更好。 ( 2 ) 第三种路由器体系结构的第二个限制是共享总线。共享总线在某一时刻只允许有一个 端口可以发送数据因而影响了吞吐量。如果能允许多个端口同时发送数据，那么系统的吞 吐量将会大大增加。这就提出了用交换结构替代共享总线的想法。交换结构和专用a s i c ( 硬 件转发机制) 形成了第四种路由器的体系结构，如图1 5 所示。 图1 5 基于交换结构的路由器体系结构 f i g1 5 t h ea r c h i t e c t u r eo f r o u t e r sb a s e d0 ns w i t c h e df a b r i c 1 5 提高性能的方法及本文章节安排 回顾图1 5 ，我们可以知道，提高路由器性能可以在三个方面加以实现： ( 1 ) 改善线卡接入功能。使之能接入当前各种快速网络如e 1 ，f r a m er e l a y ，1 0 0 m 、 1 0 0 0 me t h e m e t ，a t m 以及光纤网等。 ( 2 ) 使用硬件实现路由功能。设置f o r w a r de n g i n e 硬件实现路由功能，使之具备第三 层交换功能。 ( 3 ) 提高背板性能。包括用交换式背板取代共享式背板，消除背板阻塞问题，改进背 板调度算法等。 本文将就以上这三方面分别展开。在第二章中，讲述了当前使用较为广泛的f r a m e r e l a y ，a t m 等。第三章参照o s i 参考模型，将当前的各种交换技术进行归类。第四章主 要叙述了三种交换结构的特点。第五章主要分析了c r o s s b a r 结构的几种调度算法，为后面 一章提供选择的依据。第六章对路由器的各种设计方案进行比较和选择，并总结了一个方 案。第七章根据作者参与实际项目，介绍了一个路由器的具体实现。第八章给出了问题的 展望。 第1 0 页 上海交通大学硕士学位论文 第二章高速网络技术 提高路由器性能首先必须使其能够接入多种高速网络，本章简单介绍了当前使用较为 广泛的各种高速网络技术，了解这些技术的特点是为了便于我们设计路由器端口接入线卡。 2 1x 2 5 x2 5 作为一种公用网技术，由c c i t t 在7 0 年代开发，能在公用分组交换网络和它们 的客户之间提供接口。 它在物理层的协议被称为x 2 1 ，用于定义主机和网络之间物理的、电子的和程序上的 接口。实际上极少的公用网络支持此标准，因为它要求电话线上使用数字信号而不是模拟 信号。于是定义了与r $ - 2 3 2 标准相似的模拟接口以作为中间过渡。 数据链路层标准有不少( 有些不兼容) 的变种。它们都设计来处理用户设备( 主机或 终端) 和公用网( 路由器) 之间的电话线上的传输错误。 网络层协议处理寻址、流量控制、递交确认、中断和相关的闯题。基本上，它允许用 户建立虚拟电路，然后在上面发送不超过1 2 8 字节的分组。这些分组被可靠地和有序地递 交。大多数x 2 5 网络工作在6 4 k b p s ，这使得它们对许多应用都显得过时了。但是，它们 仍然广泛存在。 x 2 5 是面向连接的，支持交换式虚电路和永久式虚电路。 交换式虚电路( s w i t c h e dv i r t u a lc i r c u i t ) 在一台计算机向网络发送分组要求与远程计算 机通话时建立。一旦建立好连接，分组就可以在上面发送，通常按次序到达。x 2 5 提供流 量控制，以避免快速发送方淹没低速或繁忙的接收方。 永久式虚电路( p e r m a n e n tv i r t u r a lc i r c u i t ) 在用法上和前者相同，但是它根据提前在客 户和运载方达成的协议建立连接，它一直存在，不需要在使用时设置，它与租用线路相似。 由于现在有大量的终端不使用x 2 5 协议，因此又定义了另外一套标准以描述普通的( 非 智能) 终端如何与x 2 5 公用网络通信。实际上，用户或网络经营者安装了一个“黑匣子” 来连接这些终端。这种黑匣子就是分组装配器和拆卸器p a d ( p a c k e ta s s e m b l e r d i s a s s e m b l e d ，它的功能在一个叫x 3 的文档中描述。终端和p a d 之间定义了一个标准协 议：x 2 8 ：另一个标准协议在p a d 和网络之间，即x 2 9 。合起来，这三个协议通常被成 为3 x ( t r i p l ex ) 6 , 7 1 。 第1 i 页 上海交通大学硕士学位论文 2 2 帧中继 2 2 1 帧中继特点 可以将帧中继技术归纳为以下几点1 6 7 1 ( 1 ) 帧中继技术主要用于传递数据业务，它使用一组规程将数据信息以帧的形式( 简 称帧中继协议) 有效地进行传送。它是广域网通信的一种方式。 ( 2 ) 帧中继所使用的是逻辑连接，而不是物理连接，在一个物理连接上可复用多个逻 辑连接( 即可建立多条逻辑信道) ，可实现带宽的复用和动态分配。 ( 3 ) 帧中继协议是对x 2 5 协议的简化，因此处理效率很高，网络吞吐量高，通信时 延低，帧中继用户的接入速率在6 4 k b p s 至2 m b p s ，甚至可达到3 4 m b p s 。 ( 4 ) 帧中继的帧信息长度远比x 2 5 分组长度要长，最大帧长度可达1 6 0 0 字节帧 适合于封装局域网的数据单元；适合传送突发业务( 如压缩视频业务、w w w 业务等) 。 2 2 2 帧中继业务 帧中继业务是在用户网络接n ( u n i ) 之间提供用户信息流的双向传送，并保持原顺序 不变的一种承载业务。用户信息流以帧为单位在网络内传送，用户网络接口之间以虚电 路进行连接，对用户信息流进行统计复用。 帧中继网络提供的业务有两种：永久虚电路和交换虚电路。目前已建成的帧中继网络 大多只提供永久虚电路业务，对交换虚电路及有关用户可选业务的研究正在进行之中。 f r 网络 匡圃1 至k i 三正丑囤 f i l d ：帧中继坦装和拆分t c ：永久虚电路l 埘：局域网 图2 1 永久虚电路业务模型 f i g 2lt h e w o r k i n g m o d e lo f t h ep e r m a n e n tv i r t u a lc i r c u i t 第1 2 页 上海交通大学硕士学位论文 2 3 a t m 异步传输模式a t m ( a s y n c h r o n o u st r a n s f e rm o d e ) 的基本思想是以小的、固定长度的 分组信元( c e l l ) 来传输所有的信息。信元长5 3 字节，其中5 字节为信元头，4 8 字节为 有效负荷1 8 , 9 , 1 0 。 a t m 网络是面向连接的。要进行对话，首先必须发出报文以建立连接。随后，信元可 以沿相同的路径传向目标。信元不保证一定被递交到目标，但保持顺序递交。如果按c e l l l 和c e l l 2 的顺序发送，如果两个信元都到达目标，决不会是c e l l 2 先于c e l l l 到达。 a t m 运行速度是1 5 5 m b p s 和6 2 2 m b p s ，以后可能达到千兆位以上。选择6 2 2 m b p s 的 原因是用了4 条1 5 5 m b p s 通道。 在i t u - t 的1 3 2 1 建议中定义了b q s d na t m 参考模型如下图m l 0 1 。它包括三个面： 用户面、控制面和管理面，而在每个面中又是分层的，分为物理层、a t m 层、a a l 层和 高层。协议参考模型中的三个面分别完成不同的功能： ( 1 ) 用户平面：采用分层结构，提供用户信息流的传送，同时也具有一定的控制功能 如流量控制、差错控制等： ( 2 ) 控制平面：采用分层结构，完成呼叫控制和连接控制功能，利用信令进行呼叫和连 接的建立、监视和释放： ( 3 ) 管理平面：包括层管理和面管理。其中层管理采用分层结构，完成与各协议层实体 的资源和参数相关的管理功能，如元信令。同时层管理还处理与各层相关的o a m 信息流； 面管理不分层，它完成与整个系统相关的管理功能，并对所有平面起协调作用。 图2 2b i s d na t m 参考模型 f i g 2 2t h eb i s d na t m r e f e r e n c em o d e l 第1 3 页 上海交通大学硕士学位论文 2 4 1 0 0 1 0 0 0 m 以太网 2 4 1l o o m 以太网技术 下 1 0 0 m 以太网又被称为快速以太网，它是从i o m 以太网发展而来的。它的基本特点如 采用载波侦听多路访问和冲突检 女i ( c s m a c d ) 技术 网络拓扑采用总线方式 传输介质为双绞线或光纤 遵循5 - 4 3 规则，即最大5 个网段、用4 个r e p e a t e r 相连、其中3 个网段上可以 连接计算机 1 0 0 1 1 快速以太网分类 ( 1 ) i o o b a s e t x 1 0 0 b a s e t x 是一种使用5 类数据级无屏蔽双绞线或屏蔽双绞线的快速以太网技术。 它使用两对双绞线，一对用于发送，一对用于接收数据。在传输中使用4 b 5 b 编码方式， 信号频率为1 2 5 m h z 。符合e 1 a 5 8 6 的5 类布线标准和i b m 的s p t1 类布线标准。使用同 1 0 b a s e t 相同的i u 4 5 连接器。它的最大网段长度为1 0 0 米。它支持全双工的数据传输。 ( 2 ) 1 0 0 b a s e - f x 1 0 0 b a s e f x 是一种使用光缆的快速以太网技术，可使用单模和多模光纤( 6 2 5 和 1 2 5 u m ) 。在传输中使用4 b 5 b 编码方式，信号频率为1 2 5 m h z 。它使用m i c f d d i 连接器、 s t 连接器或s c 连接器。它的最大网段长度为1 5 0 m 、4 1 2 m 、2 0 0 0 m 或更长至l o 公里，这 与所使用的光纤类型和工作模式有关。它支持全双工的数据传输。1 0 0 b a s e f x 特别适合 于有电气干扰的环境、较大距离连接、或高保密环境等情况下的适用。 ( 3 ) 1 0 0 b a s e - t 4 1 0 0 b a s e t 4 一种可使用3 、4 、5 类无屏蔽双绞线或屏蔽双绞线的快速以太网技术。它 使用4 对双绞线，3 对用于传送数据，1 对用于检测冲突信号。在传输中使用8 b 6 t 编码 方式，信号频率为2 5 m h z 。符合e i a 5 8 6 结构化布线标准。使用同1 0 b a s e t 相同的r j 4 5 连接器。它的撮大网段长度为1 0 0 米。 第1 4 页 上海交通大学硕士学位论文 2 4 2 千兆位以太网技术 千兆位以太网具有以太网的易移植、易管理特性，在处理新应用和新数据类型方面具 有灵活性，它是在赢得了巨大成功的i o m 和l o o mi e e e 8 0 2 。3 以太网标准的基础上的延 伸，提供了1 0 0 0 m b p s 的数据带宽。这使得千兆位以太网成为高速、宽带网络应用的战略 性选择。 千兆位以太网支持一种新的全双工模式，用于交换机( s w i t c h ) 和交换机、交换机和工 作站的连接。半双工操作模式用于使用中继器( r e p e r t e r ) 和载波侦听多路访问和冲突检测 ( c s m a c d ) 访问技术的共享连接1 1 2 , 1 3 1 。 千兆位以太网基本特征 1 0 0 0 m b p s 通信速率的情况下的全双工和半双工操作。 8 0 2 3 以太网帧格式。 载波侦听多路访问和冲突检测( c s m a c d ) 技术。 1 0 b a s e t 和1 0 0 b a s e t 向下兼容技术。 基于不同传输介质的1 0 0 0 1 1 以太网标准 1 0 0 0 b a s e - c x 一种基于铜缆的标准，使用8 b 1 0 b 编码解码方式，最大传输距离为2 5 米。 1 0 0 0 b a s e - l x 基于1 3 0 0 h m 的单模光缆标准时，使用8 b 1 0 b 编码解码方式，擐大传 输距离为3 0 0 0 米。基于5 0 微米或6 2 5 微米多模光缆标准，使用8 b 1 0 b 编码解码方 式，传输距离为3 0 0 到5 5 0 米。 1 0 0 0 b a s e - s x 基于7 8 0 r i m 的f i b r e c h a n n e l o p t i e s ，使用8 b 1 0 b 编码解码方式，使用 5 0 微米或6 2 5 微米多模光缆，最大传输距离为3 0 0 米到5 0 0 米。 1 0 0 0 b a s e - t 基于无屏蔽双绞线传输介质，使用1 0 0 0 b a s e - t c o p p e r p h y 编码解码方 式，传输距离为1 0 0 米。 第1 5 页 上海交通大学硕士学位论文 第三章各种交换技术 当前，交换在网络中极具吸引力，在任何一个网络和应用技术中的术语中加上“交换” 这个词，似乎就可以带来高性能、低费用、低复杂性。这种例子很多，如以太网变为交换 以太网，令牌环变成令牌环交换、i p 变为i p 交换等。本章参照o s i 七层模型，将各种交 换技术和产品对应到其工作的主要层次，以便说明这些技术和产品1 1 4 1 5 “。 提高路由器性能的另一方面在于用硬件交换实现以往用软件完成的路由功能，这对消 除路由器工作瓶颈意义重大。 3 1 第二层交换 第二层交换机是一个多端口的网桥。它不仅可以分隔局域网中的冲突域，而且可以连 接不同种类的局域网。但是，它不能阻止广播风暴。为了解决这个问题，人们提出了v l a n 的概念。其特征是通过第二层交换机把一个大的局域网分割为几个独立但可能有重叠的小 的局域网，可以通过在交换机中限制数据包的传递方式达到这个目的。通常有以下几种方 法： 基于端口的分组。从某个特定端口来的数据包只能被送到一部分特定的端口。 基于第二层地址的分组。数据包的输出端口由它的第二层地址所决定。 基于第三层协议的分组。数据包中有一个字段说明第三层协议的类型，可以利用 它来决定数据流的去向。 基于第三层子网的分组。对一些象i p 一类的第三层协议，网桥只能对在同一i p 子网中的其他端口传送数据。为此，它们必须数据包的第三层地址。 总之，v l a n 交换机可以通过各种信息来改变网桥数据流的传递。第三层v l a n 交换 机尽管使用一些第三层信息，主要还是工作在第二层。a t m 信元交换机尽管完全不同于传 统的局域网网桥，但是它仍然应该归类为第二层交换机。 3 2 第三层交换 “第三层交换机”并没有一致公认的定义，通常指很大一类产品。这些产品设备有一 个共同之处是它们都通过a s i c 使用第三层信息传递数据包。主要有以下一些种类。 第1 6 页 上海交通大学硕士学位论文 3 2 1v l a n 交换机中的第三层路由功能 前面已经提过，传统网络流量分布规律的“8 0 2 0 ”规则，已经不再适用。局域网网间 流量越来越大。对这部分流量，v l a n 交换机必须使用第三层路由功能。目前，v l a n 交 换机逐渐用硬件实现这部分功能。 3 2 2 利用i p 路由实现的第二层a t m 交换 目前，a t m 技术被广泛用于骨干网。有两种不同的方法将第三层流映射到a t m 电路。 第一种方法通过把网络控制信息流与正常数据流分开以改善路由性能。i p 交换技术和m p o a ( m u l t ip r o t o c o lo v e ra t m ) 就是采用这种方法。这里特别指出i p 交换不等于第三层交换。 i p 交换指利用第二层作为传送i p 分组通过一个网络的主要转发机制的一组协议和机制。有 关i p 交换的一般情况都使用a t m 作为交换组件【“1 ，特殊情况下，采用m p l s 等标记交换。 另外一种方法则采用w a n 路由可扩展性。在w a n 的入口出作一次路由选择，w a n 内部剩余的传输则利用交换技术完成。标签交换则是基于这种方法。目前，i e t f 正着手制 定一个标准，即多协议标签交换协议m p l s t l 5 , 1 6 1 。 3 , 2 3 路由高速缓存 由于i n t e m e t 中的计算机成指数速度增长，不可能对每台计算机在每个路由表中都保 留一项。所以，路由器通常把在路由表中许多下一步目的地相同的项目合并，但这使得本 已复杂的路由查找更为复杂。为了减少路由查找时间，许多产品为那些经常被访问的地址 保留一个路由高速缓存。如果在路由高速缓存中找不到所需地址，才采用较慢的基于软件 查找方法。许多产品被称为第三层交换机，多层交换机，路由交换机或者交换式路由器等 都具有这种功能，即把第二层交换与基于高速缓存的路由特性相结合。对骨干路由器来说， 网络拓扑结构和数据流方式改变过于频繁，采用路由高速缓存几乎不能带来任何好处。路 由器性能仍然受限制于较慢的路由查找速度。 3 3 第四层交换 第四层交换相对第三层交换来说是更新的概念，即它的a s i c 硬件可以解释传输层信 息，并且使用不同的服务层次来区分应用。解释该信息的作用在于允许设备为不同应用( 用 端口号区分) 分配各自的优先级。 第1 7 页 上海交通大学硕士学位论文 第四章交换结构的种类 背板是路由器的核心部件。设计出一块高效率的背板对提高路由器性能至关重要。本 章首先指出了共享总线式背板( s h a r e b u s e db a c k p l a n e s ) 无法适应应用的需要，然后着重 介绍了交换式背板( s w i t c h e db a c k p l a n e s ) 。 交换结构又是交换式背板的核心，本章讲述y _ - 种交换结构：b a n y a n 结构、并行共享 存储结构和c r o s s b a r 结构以及它们的特点。 4 1 共享总线式背板与交换式背板 近年来，随着从i s a 到e i s a 到p c i 的发展，总线传输速度越来越快。然而，相对路 由带宽的指数增长速度，总线带宽增加相对较慢。 目前，采用定技巧的总线速度能达到最大传输率为2 0 g b p s t ”】。相对那些只有几个 1 0 0 m b p se t h e m e t 端口的路由器来说，这个速度足够了。然而，对一台能同时交换1 6 个端 口且每个传输率有2 4 g b p s 的路由器来说，则需要最大传输率为3 8 4 g b p s 。一个具有总线 的共享式背板无法胜任。 快速共享式背板有以下两个缺陷 ( 1 ) 阻塞：总线带宽为所有端口所共享，冲突将导致数据包延时。一段时间内，如果 数据包到达率一直超过总线处理速度，缓存将溢出，从而导致数据丢失。 图4 1 共享总线式背板与交换式背板的比较 f i g4 1t h ec o m p a r i s o no f c o n v e n t i o n a la n ds w i t c h e db a c k f ，l a n e ( 2 ) 多端口共享总线的传输能力受限制于电气负载、一个信号所遭遇连接器的个数以 及从总线另一端传回的信号反射。 交换式背板则能够消除以上两个缺陷。在交换式背板中，每对输入和输出端口之间都 第1 8 页 上海交通大学硕士学位论文 能独享背板的带宽，能解决阻塞问题。另外，也不存在信号反射等问题。如图4 1 所示， 我们以一个传统共享总线式背板与个以c r o s s b a r 为代表的交换式背板为例，对两种结构 做了比较。 4 2 交换结构的种类 交换式背板( s w i t c h e db a c k p l a n e ) 的组成包括：输入线路控制器( i n p u tl i n ec o n t r o l l e r ， l c l ) 、交换结构( s w i t c h i n gf a b r i c ，s f ) 、输出线路控制器( i n p u t l i n ec o n t r o l l e r ，l c o ) 和控制处理器。其中线路控制器的功能是接收( 或发送) 线路并根据报文的优先级和当前 等待队列的状况，将输入( 或待输出) 的报文放入相应的队列中。交换结构的主要功能是 实现报文从输入端口到输出端口的无阻塞传输。控制处理器主要负责完成线路控制单元和 s f 单元的有关计算( 如调度算法、路由查找) ，并将计算结果返回请求单元。交换结构可 以用许多不同的技术实现。最常用的交换结构有b a n y a n 结构、c r o s s b a r 和并行共享内存。 b a n y a n 结构是早期的一种交换结构，在众多a t m 交换机和并行处理机中有着广泛的应用。 后两种是目前研究的热点。 其中，c r o s s b a r 结构的代表有 s t a n f o r d 大学的基于c r o s s b a r 的t i n yt e r a 交换模块 1 , 1 7 , 1 。 c i s c o 基于c r o s s b a r 的整体方案1 2 0 】。 而并行共享内存结构的代表有 i b m z u r i c h 实验室的基于并行存储访问的p r i z m a 交换核心芯片f 2 1 1 。 a l c a t e l 的基于并行存储访问的m p s r 交换核心芯片【2 2 】。 j u n i p e r 基于并行共享内存的整体方案1 2 , 2 s 1 。 4 3 b a n y a n 结构 b a n y a n 结构的基本交换单元称为交换元素，共有四种交换方式，如下图示 b a n y a n 结构是种自路由结构。根据信元头的路由信息，自动决定路由，而不需要集 中的控制器控制信元的路由。譬如，信元头路由信息由三位组成0 1 i ，最低位为i ；表示在 第一级交换元素中选择的交换方式为c r o s s ；第二位为1 ，表示在第二级交换元素中选择的 交换方式为c r o s s ；而第三位为0 ，表示在第三级交换单元素中选择的交换方式为b a r 。这 样，信元可以按照路由信息自动从输入端口交换到预定的输出端口。 第1 9 页 上海交通大学硕士学位论文 嚣宫蓉二尽 c r o s s 交换b a r 交换 上广播 下广播 图4 2 交换元素的四种交换方式 f i 酣2 f o u rs w i t c h i n gf o r m so f t h es w i t c h i n ge l e m e m 除此之外，b a n y a n 网络的优点有 单路径：任何输入端到输出端只有条路径。 相同延迟：任何输入到输出端的延迟相等。 同步与异步：可以支持多种同步与异步操作方式。 模块化：适合模块化方式，构成大的交换结构，同时适合大规模集成电路的实现。 信元传送次序不变：保证信元在网络中传送的次序不变。 复杂性低：复杂性为0 ( n l 0 9 2 n ) 。 但是，b a n y a n 结构是一种有阻塞的结构，两个信元在网络内部可能会争用同一路径而 发生冲突，从而降低交换机的效率，同时多级控制器的处理会造成的延迟较大。 4 4 并行访问共享内存结构 并行访问共享内存结构( p a r a l l e la c c e s ss h a r e dm e m o r y ) 是当前交换结构的一个研究热 点。i b m 、a l c a t e l 和j u n i p e r 等研究机构和厂商都有采用这种结构的产品。这种结构是从传 统的共享内存结构发展而来的。 4 4 1 传统共享内存结构 如图4 3 所示，传统共享内存是基于总线的结构，所有端口通过总线访问共享内存。 这种结构消除了h o l 问题并且内存利用率高。数据包交换时，只有指向数据包的指针被 交换。这迅速增加了交换能力。特别是对组播，不管数据包要发向多少地址，它在内存中 只需存储一份拷贝。然而共享内存的交换速度仍受到内存访问速度的限制以及受到连接输 入输出端口和共享内存问的总线的限制。通常其背板交换能力小于l o g b p s 。 第2 0 页 上海交通大学硕士学位论文 图4 3 基于总线的共享内存结构 f i g4 3t h es h a r e dm e m o r ys t r u c t u r eb a s e do nab u s 4 4 2 并行访问共享内存结构 共享内存受到总线仲裁机制和内存访问速度的限制。所有这些方法都难于达到完全的 无阻塞交换。最新的一种交换结构称为“并行访问共享内存”，主要就是针对这个问题。并 行访问共享内存的结构是一种共享内存的结构一一所有的端口共享同一中央存储器。然而 与传统的基于总线的共享内存结构不一样并行访问共享内存给每个模块上的每个端口一 条进出中央存储器的专用通路。这些通路可同时操作。这样消除了总线仲裁机制及总线容 量的限制。并行访问共享内存的结构以完全无阻塞的交换网络保证了所有端口的线速 ( w i r e s p e e d ) 性能。并行访问共享内存的结构有下列性能： 对组播：组播的内容在内存中只有一份拷贝。多个端口可同时存取该内存单元 信息的集中存储使复杂的输出队列机制成为可能。为了更好地为不同类型的信息服 务，每个端口可设置多个优先级队列。 并行访问共享内存的结构如图4 4 所示 图4 4 并行访问共享内存结构 f i g4 4 p a r a l l e la c c e s ss h a r e dm e m o r y 第2 l 页 上海交通大学硕士学位论文 1 输出缓冲队列 由于可能同时会有几个数据包竞争同一输出端口，所以有一些数据包必须进入输出队 列等待。理想状况下，交换机应该具有无限的缓冲能力。但是，现实中缓冲队列