（物理电子学专业论文）大容量ip交换机输出排队模块的研究.pdf

华中科技大学硕士学位论文 摘要 目前i n t e r n e t 的发展趋势是具有更高的带宽和提供有差别业务的能力，传统的 面向无连接的“尽力传送”模型已经无法满足这一需求。i p 交换将第二层交换和 第三层路由很好地结合起来，是构筑下一代i n t e r a c t 的理想方案。本文首先分析了 基于a t m 的i p 交换机输出排队模块在均匀和突发业务下的性能( 时延和信元丢失 率) ，然后用f p g a 实现模块的逻辑设计，最后完成了系统在高频下的硬件设计。 第一章介绍了目前各种i p 交换技术，产生背景及发展前景。分析了在i p 交换 机中引入自由空间光互连的技术优势。 第二章阐述了两种常用的交换结构：时分交换结构和空分交换结构。重点介绍 了一种基于k n o c k o u t 原理的具有最佳时延和吞吐量性能的交换系统。给出了系统 详细模块图，并在此基础上得到模块在均匀和突发两种业务下的时延和信元丢失 率图。 第三章主要研究了f p g a 实现过程中出现的时序问题、流水线技术和f i f o 。 在复杂的时序电路中由于器件内部固有时延特性参数的不同，使得信号沿不同的 路径传输存在不可控的时钟歪斜，从而导致系统的不稳定。本文分析了时钟歪斜 产生的原因，并提出了很好的解决方案：对于高速电路设计中能够提高系统整体 时钟性能的流水线技术作了讨论，对采用前后的性能作了比较；利用v h d l 语言 实现了同步f 1 f 0 。 第四章综合考虑高速印刷电路板( p c b ) 镱d 作过程中应该注意的问题，包括电源 分配、噪声滤除、串扰以及地线毛刺的消除。着重分析了滤除噪声的去耦电容类 型选取及容值大小的计算，与噪声源的端接；高速信号线必须作为传输线考虑的 判断准则，对源端和终端失配条件下产生的信号来回反射衰减现象作了描述，给 出了消除反射现象的具体方法；对于可能严重影响信号输出质量的地线毛刺作了 相应地探讨。、 ，一一l 第五章讨论了本设计中用到的高速芯片问不同电平接口互连的问题。 7 关键词：i p 交换，光互连，k n o c k o u t 原理，时钟歪斜，流水线技术，印刷电路板 华中科技大学硕士学位论文 a b s t r a c t h i g h e rb a n d w i d t ha n dt h ec a p a b i l i t yo fp r o v i d i n gd i f f e r e n ts e r v i c ea r et h ec u r r e n t t r e n do fd e v e l o p m e n to fi n t e m e t ，b u tt h et r a d i t i o n a lc o n n e c t i o n l e s so r i e n t e d “b e s to f e f f e c t m o d e lc a n tm e e tt h i se x p e c t a t i o n c o m b i n i n gl a y e r - 2s w i t c hw i t hl a y e r - 3r o u t e a p p r o p r i a t e l y , i ps w i t c h i n gb e c o m e st h ei d e a ls c h e m eo fn e x ti n t e m e tc o n s t r u c t i o n i n t h i st h e s i s ，a tf i r s t ，t h eo u t p u t q u e u e i n g m o d u l eo fi ps w i t c hb a s e do na t m s p e r f o r m a n c e ( i n c l u d i n gt i m ed e l a ya n dc e l ll o s sr a t e ) i sa n a l y z e di nt h eu n i f o r mt r a f f i ca n dt h eb u r s t t r a f f i c ，t h e ni m p l e m e n tt h em o d u l e sd e s i g n ，f i n a l l yt h eh a r d w a r es y s t e mi nt h eh i g hs p e e d c o n d i t i o ni sg i v e n i nc h a p t e ri ，t h eb a c k g r o u n da n dt h ep r o s p e c to fi ps w i t c h i n ga r ei n t r o d u c e d ，a n d t h e a d v a n t a g e s o f i n t r o d u c i n g f r e e s p a c eo p t i c a l i n t e r c o n n e c t i o nt oi ps w i t c ha r e a n a l y z e d i n c h a p t e r2 , t w oc o m m o n l yu s e ds w i t c h i n ga r c h i t e c t u r e s a r ee x p a t i a t e d ：t h et i m e d i v i s i o na n dt h es p a c ed i v i s i o n t h ee m p h a s i si sf o c u s e do nt h es w i t c ha r c h i t e c t u r eb a s e d o nt h ek n o c k o u tp r i n c i p l ew h i c hh a st h eb e s tt i m ed e l a ya n dt h eh i g h e s tt h r o u g h p u t p e r f o r m a n c e b a s e do nt h i s ，t h et i m ed e l a ya n d t h ec e l ll o s sr a t ei nt h eu n i f o r mt r a f f i ca n d t h eb u r s tt r a f f i ca r eg i v e ni nd r a w i n g s c h a p t e r3r e s e a r c h e so nt h et h r e em a i np r o b l e m s ：c l o c ks k e w , p i p e l i n i n gd e s i g na n d f i f ow h i c ha p p e a ri nt h ed e s i g n d u et ot h ei n t e m a lc h a r a c t e r i s t i cd i f f e r e n c eo ft h e d e v i c e s t i m e d e l a yp a r a m e t e r s ，u n c o n t r o l l a b l ec l o c ks k e w sw i l la p p e a rw h e ns i g n a l s t r a v e l t h r o u g h d i f i e r e n tr o u t e s t h o s ec l o c ks k e w sw i l lr e s u l ti n i n s t a b i l i t y i n t h i s c h a p t e r , t h ec a u s ew h i c hr e s u l t sc l o c ks k e wi sa n a l y z e d ，t h eb e t t e rs o l u t i o ni sp r o p o s e da s w e l l ；t h ep i p e l i n i n gt e c h n i q u ew h i c hc a ni m p r o v et h et o t a ls y s t e m sc l o c kp e r f o r m a n c ei s d i s c u s s e d ，t h er e s u l t su s i n gt h et e c h n i q u eo rn o ta r ec o m p a r e dt o o ；if i n a l l yi m p l e m e n t s y n c h r o n a lf i f o w i t hv h d l c h a p t e r 4s y n t h e t i c a l l yd i s c u s s e st h e p r o b l e m sw h e n w em a k et h eh i g hs p e e d p r i n t e d c i r c u i t b o a r d ，i n c l u d i n gp o w e rd i s t r i b u t i o n ，n o i s ef i l t e r i n g ，c r o s s t a l k a n d g r o u n d b o u n c e t h e e m p h a s i s i so nt h es e l e c t i o no ft h e b y p a s sc a p a c i t o r s t y p e a n d m a g n i t u d e ，c o n n e c t i o nw i t ht h es o u r c eo ft h en o i s e t h ep r i n c i p l e ，t h es i g n a ll i n eb e i n g l l ， i 华中科技大学硕士学位论文 t r e a t e da sat r a n s m i s s i o nl i n ei nh i g hs p e e dc o n d i t i o n ，i sc o n c l u d e d t h e nd e s c r i b e st h e r e f l e c t i o na n da t t e n u a t i o np h e n o m e n aw h e nm i s m a t c h i n ga ts o u r c eo rl o a d ；a c c o r d i n g l y , h o wt oe l i m i n a t et h e s ep h e n o m e n ai sg i v e n s o m es o l u t i o n sa r ed i s c u s s e df o rt h eg r o u n d b o u n c ew h i c h m a ys e v e r e l y a f f e c tt h es i g n a lq u a l i t y c h a p t e r 5m a i n l yf o c u s e so nt h eh i g hs p e e dc h i p s i n t e r c o n n e c t i o n - k e y w o r d ：i ps w i t c h ，o p t i c a l i n t e r c o n n e c t s ，k n o c k o u tp r i n c i p l e ，c l o c ks k e w , p i p e l i n i n g d e s i g n ，p r i n t e dc i r c u i tb o a r d i i i 华中科技大学硕士学位论文 1 1i p 交换技术研究进展 第一章绪论 近年来出现了许多用于提高传统i n t e r n e t 速率，使其适用于宽带多媒体通信应 用的交换技术。如t o s h i b a 公司的信元交换路由器( c e l ls w i t c h i n gr o u t e r ：c s r ) 、 l p s i l o n 公司的i p 交换机、c i s c o 的t a g 交换机、i b m 公司的基于累积路由的i p 交换技术( a g g r e g a t er o u t e b a s e di ps w i t c h i n g ) 。i e t f 的m p l s ( m u l t i p l ep r o t o c o ll a b e l s w i t c h i n g ) 贝i 是汇在制定的定位于大型网络的i p 交换标准i l - ”。所有这螳技术均摹 r 一组共同的思想，它们均采用一种称为标签置换( l a b e ls w a p p i n g ) 的标签交换技 术胁送数据。非常巧合的是在a t m 交换机旱也是采用这种标签交换的技术l j h 送数 锯，所不同的是这些i p 交换技术力图保留传统i n t e r n e t 协议组的控制部分，它们 均采用i p 地址和标准的i n t e m e t 路由协议如o s p f 、b g p 等。在许多方面这些i p 变换技术综合了a t m 和i p 的最好方面，即a t m 的快速、简单交换：i p 的普遍性、 r 扩展性和灵活性。值得注意的是所有这些i p 交换机均可以通过增加适合的软件， 使a t m 交换的硬件设备用作快速路由器。i p 交换目前极具吸引力，但已有了更广 泛的涵义口i 。 ( d i ps w i t c h i n g 。i p s i l o nn e t w o r k 公司的i ps w i t c h i n g 是一种高速路由器。它 将转发助能映射到硬件交换机，如a t m 交换机。从逻辑上可以看作是个附有第 ：层转发功能的第二层交换设备，与第j 三层的数据转发模块高速互连。 i p s w i t c h i n g 采用低层流交换。在i ps w i t c h i n g 中所有的流被分为两类， 类是持续时问长、业务量大的数据流，在a t m 交换机硬件中直接进行交换，快速、 低延时；另类是持续时间短、业务量小、呈突发分布的数据流类型，通过i p 交 换控制器中的路由软件进行h o p b y h o p 转发。流分类过程动态选择流。流在交换 d 0 ，必须标记。一个流只有在七行、下行链路都标记过后，爿能直接通过a t m 交 换机进行交换。 ( 2 ) t a gs w i t c h i n g 。t a gs w i t c h i n g 由转发部分和控制部分组成的，两者互相独 华中科技大学硕士学位论文 1 1 。转发机制是一种简单的标记交换机制，通过使用定长的标记来作出决定，并 对标记蘑写。控制机制通过一组模块来维持保留n f 确的标记传播信息，以第三层 协议为基础，每个模块具有一定的控制功能，它解决了i p 与b i s d n 之州不致 的问题。 t a gs w i t c h i n g 系统中处于边缘的路由器将每个输入帧的第三层地址映射为简 单的标l _ g ( t a g ) ，然后把帧转化为打了标记的a t m 信元；打了标记的信元被映射到 v c ( v i r t u a lc h a n n e l ) 上，在网络核心，由支持t a gs w i t c h i n g 的a t m 交换机进行标 记交换。目的地边缘路由器去掉信元中的标记，把信元转换为帧并将其送往接收 者。 ( 3 ) 几种i p 交换技术的比较。不同i p 交换技术的区别在于：相关地址的建立、 存网络中分布的方法、网络中运载数据的方法。 t a 2s w i t c h i n g 、i pn a v i g a t o r 与a r i s 的不同之处在于：标记指向f i 刷。i p n a v i g a t o r 标记i 出i - - i 节点柏关，a r i s 和t a gs w i t c h i n g 的柏i u 则! - j i 山w ：d 0 缀十l i 火 防止路由环路的方法不同。i pn a v i g a t o r 采用直接路山方法来防1 f ：路i t ：懈。a r i s 和t a gs w i t c h i n g 在v c 建立时采用防止路由坏协议作为信令的部分。初始标 记交换不同。a r i s 和i pn a v i g a t o r 从出口节点处进行初始标记交换，保证了网络 上与标记相关的削隔是一致的。t a gs w i t c h i n g 使用“c h a o t i c ”标记分配方法，各 节点不需要确定上行标记与下行标记是否一致，就可以与相邻节点交换标记。 t a gs w i t c h i n g 、i pn a v i g a t o r 、a r i s 与i ps w i t c h i n g 的区别比较大。i ps w i t c h i n g 是数据驱动的，a r i s 、t a gs w i t c h i n g 和i p n a v i g a t o r 则是控制驱动的。i ps w i t c h i n g 分配标汜有间隙，这要求在建立交换路径前采用i p 转发，这会降低系统性能。 a 杯也转发第。次建立时，标记转发的数据包可能追上先前i p 转发的数据包，造 成包的系新排序。 ( 4 ) 多标记交换( m p l s ) 。上述几种i p 交换技术虽然存在不少不同之处，f i l 是它们的出发点和目的是相同的。i e t f 结合这些i p 交换技术的特点，主要以t a g s w i t c h i n g 为基础成立了m p l s 工作组来将网络层路由标记交换算法技术标准化。 m p l s 采用标汜的包转发技术来实现简单、高性能的包转发机制。它通过用 标记转发代替标准的基于目的端的h o pb yh o p 转发，从而简化了包转发机制，这 利t 标记交换是第三层交换，却具有第二层的速度。 华中科技大学硕士学位论文 m p l s 是控制驱动的，通过交换标记，网络中所有节点都会知道每个节点相 对应的标记。这样就可以根据这些标记快速与目的地建立连接。由于转发机制与 柠制机：削相互独立，而路由则属于控制机制的一部分，所以整个m p l s 路由的基 f i i | | 是在数据还没到达之前，网络的可及性已经知道。而目，入：3 与出门标记的对 应关系也可以得到建立。所以它不需要外界信息的触发来建立路由衷，这就避免 了网络的可扩展性问题。 1 9 9 7 年由美国千兆位以太网的后起之秀f o u n d r y 公司率先推出了第三层交换 机，随后各大网络厂商如b a y 、3 c o m 、c i s c o 、h p 等纷纷推出自己的第三层交换 机，掀起了一股第三层交换的浪潮，不少已获得了实际应用。国内也已经丌始采 用。 美国d a t ac o m m u n i c a t i o n s 联合欧洲网络实验室( e n l ) 进行了业界首次符合工 、i p 标准的第三层交换机测试，对以下项目进行了评估：传输速率、基本延时、部 分个 i 连情况f 的延时、阻塞条件下的流量再分配以及重新计算路由。纠i 粜i _ m a d g en e t w o r k s 公r d 的3 l s 路由模块除了仅一项外在所有的测试项h 中鄙扶得了 坛f 旬分，f o u n d r yn e t w o r k s 公司的n e t i r o n 显示了最低的延时帛i 抖动，b a yn e t w o r k s 公t 司的a c e e l a r l 0 0 在网络出现阻塞时显示了良好的流量分配特性。 3 c o m 公司新推出的c o r e b u i d e r 3 5 0 0 是篼一个支持i p 、i p x 、a p p l et a l k 协议 的第三层交换机，具有线速功能h p 公司的a d v a n c es t a c ks w i t c h 2 0 0 0 采用自动 广播控制技术和三层交换技术能使i p i p x 子网络间的话务流以第二层的速度进行 变换c i s c o 公司的t a gs w i t c h i n g 也于最近问世，其它众多网络厂商也将陆续推出 第三层交换机。 i 2 自由空间光互连技术 u - 前电子交换系统设备的硬件都是由大规模集成电路芯片和旺连j u 线鲫i 成 的。 + 段电线由于存在着r l t c 分布参数，导致传输带宽1 分有限，j i 速率价 弓通过互连线时，存在着信号的严重失真畸变，互连线之i 日j 严重串活，系统中的 时钟歪斜引起的严重误码和高传输功耗等无法克服的固有缺点1 6 】- 1 ”，故宽带、高速、 华q - 科技大学硕士学位论文 大容量的交换系统设备中的高速信息数据传输仍然采用“线互连”作为信息载体 是十分困难的。近十年以来，人们一直研究采用自由空间微光学互连网，用光作 为信息载体传输高速信息，目前该技术己十分成熟。自由空间光互连网络作为信 息载体，在高速信息传输中具有以下一些优点： ( 1 ) 时间和空f a j 带宽积近似为无穷大，信息传输无失真，无畸变。 ( 2 ) 自由空阳j 光互连网络作为信息载体传输信息，相互之间无干扰。 ( 3 ) 互连密度高，互连数大。 ( 4 ) 光作为信息载体，功耗极低，不随信号传输速率的增加而增加。 自由空间微光学互连主要用的o e v l s l 灵巧象元来实现，灵巧象元集成器件 包括三个部分：a ) 输入光信号接收部分，它将来自光互连交换网络的光信息快速地 转变为电信息，并交给c m o s 电路处理；b ) 信号处理部分，c m o s 芯片可以完成 十分复杂的逻辑处理功能和缓冲存储功能；c ) 输出光信号发射部分，c m o s 芯片完 成逻辑处理功能后将驱动相应的光调制象元和光发射象元，快速完成电光的转换， 将光信号输送剑光互连交换网上进行传送。 i i | 1 i c m o s s e e d i i io i 器佴：是种较成熟的灵巧像元技术，简单地况足将s i w 氐的c m o sf 乜路和g a a s 基底的s e e d 单元通过倒装焊：艺结合起米。c m o s s e e d 的阔制速率：e 耍取决于c m o s ：芭= 片，采用o 3 5um 一【：艺，可以搿剑2 4 g b s 的i 二作速率。c m o s s e e d 另一个特点是功耗较低，但山于s e e d 光敏山j 较小， 需要单模光纤耦合，同时c m o s - s e e d 是无源器件，需要有泵浦光源，因而需要 一套比较复杂的光学系统。 与之相比，v c s e l m s m t “i 圳3 l 器件则具有一定的优势。其中v c s e l 用作光输 出单元。v c s e l 与其它半导体激光器的根本区别是光束沿晶片垂直方向发射。 v c s e l 的一个优点是由于它的腔长较短，因而纵模间距可能大于有源材料的增益 带宽。从而获得单纵模特性；由于腔面垂直，器件的大小应不超过所需光斑的尺 | j ，因此，v c s e l 所要求的芯片面积小于普通的电子器件( 般是3um x 3um ) ： j 外，这种器件可以殴汁为小数值孔径、圆形输出光束，以便1 j 光纤的模式匹配， 从町尤须额外的光学系统就司实现高效率的耦合：最后，v c s e l 超、f 耐的几何结 构允i ：晶片级的测试，使其在并行处理和数掘链路应用中具有优势。 平面结构的m s m 光探测器包括一个半导体吸收层。在其上淀积了两个交错电 华中科技大学硕士学位论文 极以形成背靠背肖特基二极管。这种探测器易于制造。平面m s m 交错电极结构使 探测器单位面积内具有较低的电容。一个电极宽1 um 、间距2 1 1m 的典型探测器 填有的电容为4 0 f f ，这在负载电阻为5 0 欧姆时r c 充电时间为1 9 p s ，这小于光生 找流f 的渡越时间。因而，m s m 工作频率范围很宽。 日f j 有几种高密度光互连的方法可制作v c s e l m s m 器件。其一是在同一基 片匕制作v c s e l 和光电探测器件，将它们的电极作于同一平面上，然后再通过外 i ! 剁移或倒装焊技术将上述芯片与微电芯片组装在一起的单片集成法：另一种方 泄址尚先将芯片制作成兼有逻辑功能和m s m 光电探测器的：占片，这些m s m 探测 器尢须外延制作，然后采用倒装焊或外延生长技术将v c s e l 添加到陔芯片卜。从 l 岂上柬漉，后一种方法要相对容易一些。 1 3 本课题的研究目的和意义 采用i p 交换，将交换机的速度和路由器的可扩展性融合在一起，是解决i n t e r n e t 网络规模和性能问题的关键技术。i p 交换技术大大推动了i n t e m e t 网络的发展，越 来越受剑网络通信界的重视。i p 交换虽然有了不少提议、方法甚至产品，们仍然 九m 小少问题有待进一步解决。 j ：朱束的i p 交换机要求有很大的端口数或极高的端速率，完全采瑁纯f 乜 f 的技术来实现这样的大容量i p 交换机是非常因难，甚至不太可能的。采j h 纯i 乜 子技术束实现大容量的1 p 交换机时，必须采用高度并行的方法把输入输出线的高 速信号在交换机内部降为电互连线能够有效传输的低速并行信号，并通过互连大 帚的小容量模块来实现较大的总交换容量。但采用这种方法，一方面会引起交：换 机体积、成本的迅速增长，另一方面也会引起整体性能的下降。 实现大型交换节点系统有两种不同的方法。一是使用端口数相对较小，端口 速率很高的交换系统；二是使用端口数很多，端口速率低的交换系统。第一种方 法使用高速的公共通路接口，对防止突发阻塞有较好的统计复用效应。假定为 v b r ( 1 1 j 。，叟比特率) 视频电昏悭务，其峰值速率为5 0 m b s ，平均速率为2 0 m b s 。则 世f 杖1 0 “信兀丢失率，与1 5 5 m b s 的端口速率相比。采用2 4 g b s 的链路时其带 华中科技大学硕士学位论文 宽利用率呵增加1 6 0 ，而采用1 0 g b s 的链路时- j 增加2 4 0 。这是山j ：俯儿肚小 统计复用效应的结果。使用传统电子技术实现较大容量的i p 交换系统，只能采刷 第一种方法，即通过大规模的低速模块来实现较大的吞吐量。这将导致很高的成 本，且如上所分析的，性能也较差。 因此，为了克服电互连线传输速率难以提高的固有缺点，未来的大容量i p 交 换系统必然要引入光互连光交换技术。光互连具有极高的空间时间带宽积，抗干 扰能力强、互连通道等程、低功耗等优点，因此在高速大容量的交换机中采用光 丁i ：连光变换技术是发展的必然趋势4 i i ”i 。 ) 匕j 连。般足指在1 m m 到1 m 之间的范围采用光波作为载体传送信l 1在极 l “向趴离( l m m ，即：芯片内部) 町采用电互连实现很好的性能，而史艮距离的系统 内光纤连接，人们一般称之光传输。人们通过理论和实验研究已经证j ，m 系 统内芯片到芯片和电路板到电路板间采用光互连，从性能到性价比均将比i u 忆连 盐；优越得多1 1 6 1 啦”。可见，光互连主要是解决系统中高密度芯片到：签片和板到扳之 删的连接问题。目前主要的光互连技术有光纤互连1 2 2 l - 2 “、光波导互连”7 i _ 1 3 1 和自由 空间光互连”2 p ( 3 9 1 等等。 山j 二光器件的限制，目前要实现全光交换还不太可能。本实验室课题组在电 交换系统中引入光技术，充分利用光的高速、宽带优势，结合电的灵活的逻辑控 制与高密度缓存技术以及成熟的器件，实现了光电混合交换机，其容量和速率都 仃很人的提高。 华中科技大学硕士学位论文 第二章输出排队模块的结构与性能分析 2 1 交换结构概述 本课题组采用i p a t m 聚合技术保持a t m 交换的硬件不变，改变a 1 、m 交换的控 制软件，以使其在前送i p 包时，不再需要i p 和a t m 的映射，而a t m 交换仍然采 用基于标签置换的方法前送数据包，但其建立前送表和资源分配的机理将全部由i p 控制协议来完成。a t m 交换本身是基于标记的交换，a t m 信元机制能非常有效地支 持i ps w i t c h i n g 中的标记对换机制，充分利用了a t m 的交换能力，另一方面，面 向现有的a t m 局域网和未来的a t m 广域网。核心交换模块采用基于光互连的可扩 腱纳构，充分发挥自由空间光学互连网络的信号传输优势和带光窗口的超大规模 妮成u 路0 f 、一v l s i 的强大逻辑处理优势。可扩展型中心网设计使陔交换机i 有良 好的扩展能力。中心交换阵列模块提供6 4 * 1 5 5 m b s 的带宽，并r q + ，便地 rj 挺硎 2 5 6 * 2 5 ( ；h s 。 人们对a t m 交换系统已进行了大量的研究，提出了多种a t m 交换结构。这 ”j 交换结构总的浇来可以分为两大类：时分交换和空分交换结构。 2 1 1 时分交换结构 f ：输入接口o f ：输出接口 ( b ) 环删( c ) 中央存储器 | 生| 2 i - 1 时分交换结构 时分结构是指所有的输入输出端口共享一条高速的信元流通路，这条共享的 高速通路可以是共享介质型的( 如总线型、环型) ，也可以是共享存储器型的( 中央 华中科技大学硕士学位论文 存储器) 。图2 1 1 表示了常见的几种时分交换结构，图中i f 表示输入接口单元， o f 表示输出接口单元。整个交换矩阵的交换容量由这个共享通路的吞吐昔( 如总 线述艘、存储器容量和存取速度等) 所限制。时分交换有一个设备吞吐量的固定 5 l i ! ，这种交换能力的限制不能随端口的增加而增加。因此、公建资源的需求增 加时，网络性能会受到影响。交换机的吞吐量是由公共资源的速度确定的， 般 不易扩展，所以无法满足交换容量非常大的情况。 2 1 2 空分交换结构 空分交换结构是指在输入和输出端之间有多条通路，不同的a t m 信元流可以 从不同通路上同时通过交换结构。空分结构按其在任意一对输入输出端口间的路 径数又可分为单路径和多路径两大类，其中的多路径是针对单路径中网络对突发 业务应变能力差的弱点提出的，它通过增加单元的串联级数和并行数来达到提高 性能的门的。空分结构一般具有较好的硬件扩展性，可以增加端口而不影i 响变换 内件l i ：最端j i 不必竞争单一的共享资源。由于交换机性能町随端的增加而 捉崩所以在理沦上空分交换机应能容纳更多的端口。但山j 二多路径。卜分交换机 往往采用多级和多平面的结构，其硬件复杂度一般较高，特别是刈路拎制j ，| j 。出 求很高。空分交换结构可以采用中央控制的方式，也可以采用分布武路山控制力 j ，也称为“自路由”方式( s e l f - r o u t i n g ) ，来实现交换网络的路出控制。当刚络姚 模很大时，需要为大量的信元同时建立路由，控制器的压力将非常大，因此， 个互连性能很好的空分网络必须要有一个高效的寻径控制算法才能实用。 对于空分交换结构，有两种情况会导致信元的丢失：一是交换机构( 或分配网 络) 内部的连接阻塞导致的信元丢失：另外一种情况是由于同一信元时隙内两个 或名个信元经过交换单元竞争同一输出端口引起目的地冲突而导致的信元玉火。 第。种情况町利用充裕的分配网络( 节点和链路) 来解决，即在输入端口和 输端j1 之间没置多条通路。若在同一信元时隙内有两个或多个a t m 信几蚓键利 川分配嘲络内相同的资源( 节点和链路) ，则它们可以利用f i l q n 突的通路f 输， 以消除恻络的内部阻塞。对于第二种情况，为了有效控制凶竞争失败| ：造成的化 元丢失，交换机必须提供缓存功能，对竞争失败的信元进行缓存排队。 华中科技大学硕士学位论文 信元缓存是基本交换单元的主要功能之一，缓存的设计是实现a t m 交换机中 的一项关键技术。目前存在三种最基本的排队缓存方法：输入缓存、输出缓存和 中间缓存( 如图2 1 2 ( a ) ，( b ) ，( c ) 所示) 。这几种基本排队方法也可以在一个系统中混合 ( a ) 输入缓存( b ) 输山缓存 输 ： 输 八 出 接 接 口 口 ( c ) 中间缓存 幽2 1 2 空分交换结构的儿种排队缓存方法 从广：，l i 输入一输出缓存、输入一中间一输出缓存和中 、h j 一输“i 缓存等方 棠 基本的输入排队是在交换单元的每个入口端都配簧一个专用的“先入先” ( f i f o ) 缓存来存储输入信元。输入排队的最大缺陷是存在排头阻塞h o l ( h e a do l l i n eb l o c k i n g ) ，即当一个队列的队首信元没有输出权限时，其后面的所有信元都 必须在队列中等待，即使它们的目的端口是空闲的。由于存在排头阻塞，交换系 统的最大吐吞量t p 。只能达到o 5 8 4 0 】。为了克服排头阻塞，提高系统吞吐量， 人们住输入端采用了各种不同于简单先入先出的仲裁策略，由仲裁逻辑控制每个 队列中信元的选择输出。仲裁逻辑对信元竞争的裁决可有不同的方法，如对所有 输入队列采取轮流优先的办法；或者根据输入队列的长度来选择优先者等等。捉 “输入缓存性能最有效的方法足“丌窗算法”( w w i n d o w sm a c h a n i s m ) ：拒雠个时 瞰| j 、j ，“1个输入端的缓存队列的第一个信7 i 因目的地冲突无法传输州，它会尝 i j _ i = 化队列中的第i 个信元传输传输到其目的输出端，如果仍被阻摩，| j ! i j 尝试队列 t ，的第三个信元，这样直到第w 个信元( 显然，当w = l 时，目】表示简坼的f w o 缀 华中科技大学硕士学位论文 存) 。w 值越大，则越能有效的消除排头阻塞的影响，模拟表明在n = 1 2 8 ，w = 8 时， f 叮实现t p 。产o _ 8 8 ，如果取w = 。，则t p 。= 1 【4 2 】。 输出缓存是在交换单元的每个出口端都配置一个专用的缓存，多个同时要求 到达某一一出端的来自不同输入端的信元在该输出端的缓存排队 4 0 1 1 4 1 i 。如果要在竞 争最激烈的情况下在一个信元时隙内将n 条入线上的信元送往同一输出队列，传 输媒体的速率必须是入线速率的n 倍，另外，输出缓存的写入速度必须为读取速 f _ 的n 亿。输出队列的读以基于f i f o 的原则，以确保信元的正确次序。当输出缓 打址够人时，采用输出缓存队列的交换系统可实现t p 。，= l 。 中f 日j 缓存是在交换单元的内部各节点处设置缓存队列，对在内部j ；! l l 蝈n 信元进行排队缓存，并按f i f o 的原则读耿这些信元。由于从不同输入端术剑小川 输出端的信元都可能混在一个缓存队列中，因此存储空间的管理和读写控制都比 较困难。中间缓存的位置而对于多路径的空分网络，同一序列信元到达输出的次 序有可能混乱，要保持信元次序就需要复杂的控制算法或在输入端重排序1 4 4 “。 如粜中f h j 缓存合起来用一个很大的共享存储器，就成了共享介质型的中央存储交 换结构。中间缓存在各种不同空分交换结构中的位冕可以不同，其性能也与具体 的交换结构相关，由于控制上非常复杂，因此在大容量的情况下会难以实现或成 本很r 岛。 对州川规模相同速率的交换单元，若负荷相同，容许的信元丢失率也相州， l j i i j 一 l 火排队的变换币元所需存储空间最小，输出队列其次，输入队列最人。对交 懿n 厄内部的传输媒体而吉，采用中央队列和输出队列的变换单，i 要求传输媒仆 的速率为出入线速率的n 倍，而采用输入队列的交换单元不需提高输媒体的速；辑。 对存储器的访问时问而言，输入队列对存取速度要求最低。输出队列其次，中央 排队要求最高，控制逻辑也最复杂。此外，采用输出队列的交换单元较易实现点 到多点和广播通信( 每输入端的信元都能够同时传送到很多输出端) ，而采用中央 排队和输入排队的交换单元较难实现这种功能( 点到多点和广播通信会导致信元 祚：输出端冲突) ，需附加控制逻辑来解决。 本课题采用基于空分交换结构的广义k n o c k o u t 原理实现。k n o c k o u t 交换网络 ”y c h 等人在1 9 8 7 年提出的一种优秀的交换结构，其结构如图2 卜3 所，j 。它 1 “川j k n o c k o u t 原理”，即不考虑缓存的具体实现方法，我们做出以p 的简币m 华中科技大学硕士学位论文 父键的l 值定义：如果到达不同输入端口的分组是相互独立的，那么订多jl ( t 。 1 e i t = 1 + j 而p ； ( 2 蚴 9 ； ，j dlg口，tlt 8e#pilj 华中科技大学硕士学位论文 其中，s 为缓冲队列容量。 从输出队列的出端来看该排队系统，该队列有k 种状态，其中只有k = 0 的状 态输出端没有信元输出，因此该缓存队列的吞吐量为： r = l po xo ( 2 3 3 ) 而信元丢失率为： p h 。= 1 二_ ( 2 3 4 ) p 由上述结果可知，要求得输出排队缓存的统计特性，关键是求输出队列为空 的概率p 。，而p 。值可由式( 2 3 1 ) 迭代求出。 当交换系统处于突发业务流时，输出模块的排队性能不易推出简单的公式来 计算。本文采用计算机模拟的办法来仿真这独立输出排队中输出模块的性能。同 时对它们在均匀业务流下的性能也进行了模拟，以检验理论计算的正确性。相应 模拟子程的流程图见附录l ，2 。 图2 3 1 为均匀业务下输出模块排队中的平均信元时延随负载的变化曲线图。 如图所示，排队引起的平均时延对业务负载的变化并不十分敏感。 图2 3 2 为突发业务下( 突发序列长度为b l = 8 ) 输出排队模块中的平均信元时延 曲线。为便于比较，图中用虚线画出了均匀业务下的平均时延。从图中可以看出， 突发业务对排队的平均时延影响很大，控制突发强度的大小是减小排队延时的有 效手段。 图2 3 3 为在突发序列长度( b l ) 不同的业务流下输出排队中的平均时延曲线。 可以看到，当突发序列的平均长度增加时，会显著增加输出排队模块中的平均时 延。这是由于突发序列的增长使得同一输入端到达的信元时域上的相关性也增强 了。 。 图2 3 4 为在混合业务流下，输出排队的平均时延曲线。从图中可以看出，在 突发负载p 。= o 4 ，总负载为0 6 时，平均时延约为8 个信元长度，当突发负载降至 o 2 5 时，在总负载为0 6 时，平均时延降至约6 个信元长度。与此同时，突发业务 下在总负载为0 6 时平均时延为1 3 个信元长度。从上面的分析可以知道，为了保 证输出排队具有较小的时延，必须控制业务总量中突发负载( p 。i ) 的大小。 j l l l i 华中科技大学硕士学位论叉 现在来看信元丢失率性能。图2 3 5 为均匀业务下输出模块出端独立排队时， 在不同负载下的信元丢失率随排队缓存长度的变化曲线。即使当负载达到0 9 ，增 加缓存到6 0 个信元长度就可使信元丢失率达到1 0 。6 量级。负载越小，则增加缓存 长度对降低信元丢失率的效果越明显。 图2 3 - 6 为突发业务 = 0 ) 下输出模块出端独立排队时，在不同负载下的信元 丢失率随排队缓存长度的变化曲线。从图中可以看出，突发业务负载对信元丢失 率的影响很大，在负载p = o 4 时，每个输出端的缓存容量要达到1 8 0 个信元单位才 能使信元丢失率降至1 0 。7 量级。 华中科技大学硕士学位论文 3 0 2 5 2 0 里 口 m1 5 巴 皇 1 0 o n ：1 1 2 8 ： s i m u l a t i n g ! 。 一一一一一一一一j 一一一一一一一一i 一一一一一一一一 ii i i ii 一一一4 一一一一1 一一一一一一一一t 一一一一一一一一一一一一一直一 li il j il if 一一一一一一j 一一一一。一一一二一一一一一一一一童一 1 一 li ，ee 。6 ；。呻矿。1 0 图2 3 2 均匀业务下输出排队平均时延c 1 图2 3 3 纯突发业务下输出排队平均时延、们 华中科技大学硕士学位论文 耍 d 曼 掌 卫 。 已 宝 l o a dp 图2 3 - 4 不同突发序列长度下平均时延 】 l o a dp 图2 3 5 混合业务流下的平均时延c t l 】 华中科技大学硕士学位论文 图2 3 6 均匀业务下输出模块出端独立排队信元丢失率【1 图2 3 7 突发业务下输出模块出端独立排队信元丢失率c 叼】 2 4 华中科技大学硕士学位论文 第三章输出排队模块的逻辑设计 3 1 可编程逻辑器件 p l d ( p r o g r a m m a b l el o g i cd e v i c e ) 是可编程逻辑器件的总称，早期多e e p r o m 工艺，基于乘积项( p r o d u c tt e r m ) 结构。f p g a ( f i e l dp r o g r a m m a b l eg a t ea r t y ) 是指现场可编程门阵列，最早由x i l i n x 公司发明。多为s r a m 工艺，基于查找表( l o o k u pt a b l e ) 结构，要外挂配置用的e p r o m 。x i l i n x 把s r a m 工艺，要外挂配置用的 e p r o m 的p l d 叫f