（粒子物理与原子核物理专业论文）基于共享存储结构的高速交换系统.pdf

中国科学技术大学博士学位论文 基予燕享存储结构的高逋交换系统 摘要 互联网是2 0 潋纪9 0 年代快速发展起来躲一项重要翡售惠产艘技本。专足年来，互联秘 舟勺掰户数餐呈指数增加，互联网的通讯量目盏迅猛地增长。用户对网络带宽的要求不断地上 升，远远超出了互联网现有的连接和交换容量。随着多媒体技术和实时视频点播的出现，用 户对互联嘲服务质整的要求也越寒越薅刻。因戴，对互鼗网中路幽秘交换竣备戆职究已变 霉 越来越热门，并且取得了许多引入注疆的成果，狠多国际著名的两络设备商和服务商都竞相 开发和配溉了越来越快的交换器和路由器。 在高遮路由嚣韵研髑中，交换技术占据了核心的蟪像。虽然备类交换器静结构及相应的 调度算法五花八门，但其发展却有着定的规律可循。从共享总线式交换器到交叉开关结构 的出现曾一度掀起了交换结构研究的新潮漉。变叉开关不但可以使褥多个端日之闻劳行地进 行信怠魏传递，也霹秘蒿效遣进行一对多的多猜传输。翻予对交叉开关静调度必然怒集中式 蜱法，所以在端口数扩展方筒会引起报大的困难。随着高速随机存储技术的突破，熟享存储 式的交换器在大容懿交换结构的设计中有着逐濒取代交叉开关结构的趋势。共享存糖技术以 缀离存褚带宽静代债来换取简荸的调度算法。 第一章是对高速交换系统研究的练述。首先介绍了赢联网路由器的结构和功能，接着对 本骚究领域孛常觅匏概念帮术语趣殴瓣释稻说锈，然磊讨论了交换结梅帮赢联网通信藿翡摸 型，并指出互联网通信量模型对交换结构的设计和性能测试具有非常重要的意义，最后概述 了世界上几个著名公司推出最新的交换设备所采用的技术和所具有的特色。 第二章讨论了基于交叉开关的高速交换系统。考虑到调度器设汁的难度，绝大多数交换 结构都是假定所处理的信息靓是已经被线路卡拆分好的定长包，假v s c 8 7 0 8 8 0 系统以简单 壁裹速遗传裁斡策酸瑟支持不定长的僖惠包交换。本章鄹按辑瑟对信惠毽怒否定长瓣分兔琵 个部分。在第一部分中，介绍了面向定长信元的交叉开必，并着麓介绍了e s l i p 算法及其 仿真结果，并讨论了交叉开头的多位耐扩展技术。在第二二部分中，详细介绍了面向不定长信 崽包的v s c 8 7 0 8 8 0 系统及葵位囊结聚。 第三章是本文的重点，详细讨论了基于共享存储结构的f e l 6 4 g 交换系统。首先，介绍 了共享存档结誊每交捩系统设杰的嚣令荚键技术：共享存镶器的分熬和毫带爨存穗爨鲍设计援 术。接着描述了f e l 6 4 g 的总体及各个子模块的功能。然后介绍了f e l 6 4 g 在单片f p g a 上 的实现和仿真结果。展后，介绍了f e l 6 4 g 单擞测试系统设计的原理和相芙技术，并且详细 地说明了利用线性爱馈移位辩存器续毒奄在f p g a 杰宣接产生爨隧梳数躲藤理。 第四章对各种交换系统进行了对比，并给出了并行交换系统的相关研究结果。 土疆堂垫娄查兰竖主堂垡堡苎 苎王茎皇查堡墅塑塑壹鎏塞垫墨堡 a b s t r a c t i n t e r a c tl so n eo ft h em o s ti m p o r t a n ti n f o r m a t i o nt e c t m o l o g i e sd e v e l o p i n ga tah i 曲s p e e di n t h el a s tm o r et h a nt e ny e a r s 。善bu s e r so fi n t e m e ti n c r e a s ee x p o n e n t i a l l y , a n dt h ei n t e m e tt r a f f i c i n c r e a s e sd r a m a t i c a l l ys o ，t h ed e m a n df o rn e t w o r kb a n d w i d t hc o n s t a n t l yr i s e sa n di sa l r e a d vf a r b e y o n dt h er e a c ho f c u r r e n tl i n ka n ds w i t c h i n gc a p a c i t y a l o n gw i t ht h ec m e r g e n c eo f m u l t i m e d i a a n dr e a lt i m ev i d e o o n d e m a n d t l ei n t e m e t u s e r s r e q u e s tt oq u a l i t yo f s e r v i c ea l s ob e c o m e sm o r e a n dm o r er i g o r o u s t h e r e f o r e - t h er e s e a r c ha r e ao fi n t e m e tt o u t e r sa n ds w i t c h e sh a s a l r e a d y b e c o m em o r ea n dm o r ep o p u l a r i tr e s u l t si nm a n yr e m a r k a b l ea c h i e v e m e n t s s o m ei n t e m a t i o n a l f a m o u sn e t w o r ke q u i p m e n ta n ds e r v i c ec o r p o r a t i o n sh a v ec o m p e t i t i v e l yd i s t r i b u t e df a s t e rt of a s t e r r e u t e r so rs w i t c h e s i nm er e s e a r c ho nh i g h - s p e e dr o u t e r s h i g h - s p e e ds w i t c ht e c h n o l o g i e sa r et h eb a s i ca n dc o r e s u 垮e c t s a l 也o u g h t h e r ea r e m a n yd i f f e r e n t s w i t c hf a b r i c sa n d s c h e d u l i n ga l g o r i t h m s 。i t s d e v e l o p m e n th a sc o m p l i e dw i t hs o m ec e r t a i nw a y s i tw a sam i l e s t o n et h a ts h a r e db u ss w i t c h f a b r i c sh a db e e nr e p l a c e db yc r o s s b a rf a b r i c s s e v e r a lp a i ro f p o r t sc a ne x c h a n g ei n f o r m a t i o n s i m u l t a n e o u s l yo bc r o s s b a rf a b r i c ，a n da l s oo n ep o r tc a ne f f i c i e n t l yt r a i l s f e rm e s s a g e st os e v e r n l o t h e r p o r t so ni t o w e v e r , w h e nt h en u m b e ro f p c r t se x p a n d s ，f a 键ld i 撬c u l t i e sw i l lo c c u rs i n c ea l l s c h e d u l i n ga l g o r i t h m sf o rc r o s s b a rf a b r i cs h o u l db ec e n t r a l i z e db e n e f i tf r o mt h eb r e a k t h r o u g ho f v e r yh i g hs p e e dr a n d o ma c c e s sm e m o r i e s ，s h a r e dm e m o r yf a b r i c ss e e mt ot a k ep l a c ec r o s s b a r f a b r i co nd e s i g n i n gh i g hc a p a c i t ys w i t c h e si nt h en e a rf u t o r e 。f o rt h es a k eo f e x t r e m e l yh i g h b a n d w i d t ho fr a n d o ma c c c s sm e m o r i e s ，t h es c h e d u l i n ga l g o r i t h m st os h a r e dm e m o r yf a b r i c sa r e r e l a t i v e l ys i m p l e c h a p t e ro n ei s a no v e r v i e wt ot h er e s e a r c ho f h i g h - s p e e ds w i t c h i n gs y s t e m s a tf i r s t w e b r i e f l yi n t r o d u c et h ec o n s t r u c t i o na n df u n c t i o n so fi n t e r a c tr o u t e r st h e ns o m ec o m n o nc o n c e p t s a n dt e r m sa r ei n t e r p r e t e d w h e r e a f t e r , w ed i s c u s st h em o d e l so fs w i t c hf a b r i c sa n di n t e m e tt r a f i l e 羊h ep r e c i s ei n t e m e tt r a f f i cm o d e l sa r ev e r yi m p o r t a n tt od e s i g na n dt e s ts w i t c hf a b r i c sr e a s o n a b i y , f i n a l l y , w eg i v e t h e i n v e s t i g a t i o nr e s u l t s t os e v e r a lm o d e ms w i t c h e sd i s t r i b u t e d b ys o m e i n t e m a t i o n a in o t e dc o r p o r a t i o n s i nc h a p t e rt w o ，w ed i s c u s sc r o s s b a rb a s e dh i g h - s p e e ds w i t c h i n gs y s t e m s 。c o n s i d e r i n gt h e d i f f i c u l t i e so ns c h e d u l i n ga l g o r i t h m s t h eg r e a tm a j o r i t yo fs w i t c hf a b r i c sa s s u m et h a tt h et r a m c p a c k a g e sh a v ef i x e dl e n g t h b u tt h ev s c 8 7 0 8 8 0s y s t e m ，a l s ob a s e do nc r o s s b a ra n dd e s i g n e db y v i t e s s e ，s u p 夺o s 韩f o r m a t i o np a c k a g e sw i t hv a r i a b l el e o g h s 。a tt h ef i r s tp a r t ，w ei n t r o d u c e c r o s s b a rf a c e dt o n x l e n g t hp a c k a g e s ，s oc a l l e d ”c e l l ”，a n d ，w ed e s c r i b ee s l i ps c h e d u l i n g a l g o r i t h ma n dg i v ei t ss i m u l a t i o nr e s u l t s i no r d e rt oe x p a n dt h ec a p a c i t yo fc r o s s b a rs w i t c h e s 。 m u l t i p l a n et e c h n e l e g yi sb m u g h to u t 。a tt h e s e c o n dp a r t ，t h ev s c 8 7 0 8 8 0s y s t e ma n di t s s i m u l a t i o nr e s u l t sa r ep r e s e n t e d c h a p t e r t k r e ei st h ec o r eo f 出i sd i s s e r t a t i o n + i td e v e l o p sa r o u n dd e t a i l e dd i s c u s s i o nt os h a r e d m e m o r yb a s e df 毫l 6 4 g s w i t c hf a b r i c a tf i r s t ，w ei n t r o d u e et w ok e ys u b j e c t a ，m e m o r y d i s t r i b u t i o na n dh i g hb a n d w i d t hm e m o r yd e s i g n i n g ，o ns h a r e dm e m o r yt e c h n o l o g y t h e n ，w e i n t r o d u c et h et o pa r c h i t e c t u r ea n de v e r ys u b - m o d u l eo ff e l 6 4 gs w i t c hf a b r i c w h e r e a f l e r , w e d e s c r i b et h er e a l i z a t i o no ff e 糙4 go ns i n g l ep l a t f o r mf p g aa n ds o m es i m u l a t i o nr e s u l t s l a s tb u t n o ti e a s t w ep r e s e n tt h ep r i n c i p l ea n dr e l a t e dt e c h n o l o g i e s 协也ea l p h at e s ts y s t e mo f f e l 6 4 gw e g i v eas i m p l i f i e da n de f f i c i e n tw a yo f p r o d u c i n gp s e u d or a n d o mn u m b e r sd i r e c t l yb vf p g au s i n g l i n e a rf e e d b a c ks h i f t r e g i s t e r s i n c h a p t e rf o u r , w ep r e s e n tt h ec o m p a r i s o nb e t w e e nd i f f e r e n ts w i t c h i n gs y s t e m s w ea l s o s h o wt h er e s e a r c ha n da c h i e v e m e n t so np a r a l l e ls w i t c h i n gs y s t e m si nt h i sc h a p e r , 中国科学技术大学博士学位论文 基于共享存储结构的高速交换系统 引言 随着i n t e m e t 的飞速发展和宽带技术的不断出现，对i n t e m e t 互连的核心设备路由 器的性能提出了越来越高的要求，传统的基于总线和中央处理器结构的路由器由于其体系结 构上的局限，已经无法满足组建高速主干网络的需求。近年来，国际上对宽带i p 路由器技 术的研究也日益活跃，提出了用交换结构( s w i t c h f a b r i c ) 提高各接口单元之间的数据通信 速度的基本思想。事实上，多处理器交换式体系结构的第三代路由器和共享并行处理器交换 式体系结构的第四代路由器中的核心模块就是交换结构。交换技术已经成为高速路由器的核 心技术。 目前最好的网络交换器己达到每秒t e r a b i t ( 1 0 “) 的数据交换速度：未来几年中，进一步 的研究可望把总数据率提高到每秒1 0 ”b p s 的级别。网络交换器数据率的提高可从两个方面 着手：单个交换结构的容量的提高和并行交换规模的提高。 对于单个交换结构而言，容量的提高体现在所支持的端口数n 的增加和每个线路上的 数据传输率的提高。交换结构的端1 2 数n 从8 8 到1 7 2 8 1 7 2 8 ( 女f lo n e x 的i t s e ) ，线路上 的数据率从o c 1 2 ( 6 2 2m b p s ) 、o c - 4 8 ( 24g b p s ) 发展到o c 1 9 2 ( 1 0 g b p s ) 和o c 7 6 8 ( 4 0 g b p s ) 。 端口数和线路速率的增加受限于硬件环境所容许的条件和交换结构调度算法的决策效 率。端口数的增加会影响交换结构所采用的交换算法的性能和效率；而线路速率的增加，会 直接缩短交换结构仲裁器的仲裁周期。所以对交换系统所采用的体系结构及其交换算法的设 计与优化的研究是非常重要的课题。 i n t e r n e t 上的i p 数据包是不定长的，理论上t c p 1 p 协议所支持的晟大包长是6 5 5 3 5 b y t e s ，但实际上最大包长要受到数据链路的限制。在以太网中一个i p 数据包的长度在 4 0 b y t e s 到最大长度1 5 0 0 b y t e s 之间变化，并且短包占了非常大的比例。交换算法的优劣是 与用来检验它的互联网通信量直接相关的。不同的交换算法在不同模型的通信量下可能会各 有利弊。所以，建立精确的、能够反映真实情况的互联网通信量模型对交换算法的设计是很 重要的部分。 本篇论文大体上是按照高速交换系统的发展历史和趋势，介绍了基于交叉开关和共享存 储结构的交换系统。其中基于交叉开关的交换系统又分为面向定长信元交换的e s l i p 算法 及多位面扩展的原理和直接面向不定长i p 包的v s c 8 7 0 8 8 0 系统。基于共享存储结构的交 换系统代表了交换系统的最近研究方向，也是本文的重点。 我所参加的相关工作主要有：互联网通信量模型的建立：e s l i p 算法的仿真；多位面扩 展技术的探讨与仿真：v s c 8 7 0 8 8 0 系统的仿真；基于共享存储结构的f e l 6 4 g 交换系统的 绝人部分研究工作。其中为了研制f e l 6 4 g 交换结构，本文提出了具有创新性的c 语言与 v h d l 语言的混合仿真技术、基于平台f p g a 的单板测试技术、利用l f s r 结构在f p g a 内 部实现伪随机数发生器的技术。关于本人的工作和本文的创新点在本文末尾的结论部分有更 为详细的说明。 中国科学技术大学博士学位论文 基于共享存储结构的高速交换系统 第一章高速交换系统综述 路由器技术是融合现代通信技术、计算机技术、网络技术、微电子芯片技术、大规模集 成电路技术，光电子技术及光通信技术的核心技术，是衡量一个国家通信技术水平的重要标 志。高速高性能路由器是高速网络的核心，自1 9 9 7 年第一个g b p s 级的路由器面世以来， 高速高性能路由器迅速成为了市场瞩目的热点。目前，人们正致力于开发高速、高性能、高 吞吐量、低成本的新一代路由器，以满足网络的不断发展。 新一代路由器内部结构所展现出的主要发展趋势为：第一，越来越多的使用基于硬件的 交换和分组转发引擎。c m o s 集成技术的提高使很多功能可以在专用集成电路( a s i c ) 芯 片上实现，原来由软件实现的功能可由硬件完成，速度更快、成本更低，大大地提高系统性 能。第二，向并行处理的方向发展，逐渐抛弃易造成拥塞的共享式总线，采用交换背板结构 或共享存储式的结构。第三，进一步发展在光纤连接上进行的线速选路技术，实现g b d s 、 y b p s 速率，为i n t e r a c t 过渡到全光基础设施奠定了基础。 随着业务提供者和大型i s p 不断升级，骨干网路由器的高速接口速率从最初的o c 1 2 升级到o c - 4 8 ，最近又掀起了向o c 1 9 2 升级的浪潮。具有高速o c 1 9 2 光接口的高速路由 器是网络向i po v e ：rd w d m ( d e n s ew a v e l e n g t hd i v i s i o nm u l t i p l e x i n g ) 结构发展的关键。 对运营商来说，高的端口密度具有重要意义。因为大型骨干网的核心节点一般在大城市， 中心局和入网点的空间资源不但有限而且成本很高，业务提供者必须考虑节约空间的问题。 而具有高密度端口的高速路由器是解决空间压力的一个重要举措。 1 1 互联网路由器的结构和功能 i p 路由器的般结构，如图1 1 所示。 一 图1 1路由器的一般结构示意图 从图1 1 可见，路由器的功能一般可以划分为以下两类p j ： 1 数据照径功鳇( d a t a p a t hf u n c t i o n s ) ：每个通过路由器的数据报( d a t a g r a m ) 都必须 进行该操作。它包括转发判决( f o r w a r d i n gd e c i s i o n ) ，背板( b a c k p l a n e ) 和输出链路调度 ( o u t p u tl i n ks c h e d u l i n g ) 。为了保证系统性能，数据路径功能通常使用硬件实现。 2 控制功能( c o n t r o lf u n c t i o n s ) ：这部分功能相对进行很少的操作。它包括和邻近路 由器的路由表信息交换，以及系统配置和管理，一般用软件实现即可。 因此，当我们希望提高路由器对王p 数据报( 也称信息包，p a c k e t ) 的处理性能时，自然 主要着眼于改善路由器的数据路径功能。下面我们跟踪一个信息包，通过分析它经过一个口 路由器的典型路径来仔细了解数据路径功能： 转发判决：当i p 数据报到达时，在转发表中查找它的目的地址。如果发现了其目 的地址( m a c 地址) ，下一段的m a c 地址附在数据报前端，i p 数据报头的t t l ( t i m e t o 1 i v e ) 域被减少，一个新的头校验被计算出来。 背板：数据报转发后通过背板到达它的输出端口( 或多个输出端e 1 ) 。数据报在等 2 里型兰垫查奎堂竖主堂垡堡苎 苎王苤皇童堡笙塑竺壹堕奎垫墨竺 待被传送过背扳时，可能需要排队。如果没有足够的队列空间，数据报可能会被丢 弃，或者被用来替换其它的数据报而使其它的数据报被丢弃。 输出链路调度器：当数据报到达输出端口后，它等候被传送到输出链路。目前大多 数路由器，输出端口保留单一的先来先服务( f i r s t c o m e f i r s t s e r v e d ) 队列，按照数 据报到达的顺序传送。更高级的路由器将数据报分成不同的流或者优先级，通过特 定的算法来调度每个数据报的离开时间以满足服务质量( q u a l i t yo f s e r v i c e ) 的要 求。 在网络环境中，离不开对众多路由器的正确布局和配置，每台路由器都担负着一种特定 的职责与功能。按这些功能可将路由器分为核心层( 骨干级) 路由器，分发层( 企业级) 路 由器和访问层( 接入级) 路由器。 骨干级路由器是实现企业级网络互连的关键设备，它的数据吞吐量非常大。骨干级路由 器要求具有高速度和商可靠性。为了获得高可靠性，网络系统普遍采用诸如热备份、双电源、 双数据通路等传统冗余技术。 企业或校园级路由器连接许多终端系统，连接对象较多，但系统相对简单，且数据流量 较小，对这类路由器的要求是以尽量便宜的方法实现尽可能多的端点互连，同时还要求能够 支持不同的服务质量。用路由器连接的网络系统因能够将机器分成多个碰撞域，所以可以方 便的控制一个网络的大小。此外，路由器还可以支持一定的服务等级，允许将网络分成多个 优先级别。当然，路由器的每端口造价要贵些，在使用之前要求用户进行大量的配置工作。 企业级路由器的成败在于是否可提供大量端口且每端口造价很低，是否容易配置，是否支持 q o s ，是否支持广播和组播等多项功能。 接入级路由器主要应用于连接家庭或i s p 内的小型企业客户群体。将来的接入路由器还 要支持许多异构和高速端口，并能在各个端口运行多种协议。 本文研究对象主要定位于互联网骨干级的高速路由器。 1 2 相关的技术和概念 本小节先介绍一下几个常用的概念和术语。 1 2 1 路由器与交换结构 复杂的网络数据通信系统无法使用单一的协议来处理所有的传输任务，必须由一整套相 互合作的协议所组成的集合，这个集合又被叫做协议族或协议套件。为了便于管理和对协议 族的研究，国际标准化组织o s l ( o p e ns y s t e mi n t e r c o n n e c t ) 将这些网络协议共分为七层，称 为o s i 七层模型。这七层从低到高分别为：物理层，数据链路层，网络层，运输层，会话 层，表示层和应用层，如下图所示： 图1 20 s i 七层模型 路由器：路由器在o s i 七层模型中位于第三层网络层，作为连接广域网w a n 的端 口设备，简单地说，路由器的主要功能是连接多个独立的网络或子网，实现互联网间的最佳 寻径及数据包传送。有些特殊用途的路由器也可能会支持三层以上的协议，甚至包括第七层 协议。 交换结构：交换结构在o s i 七层模型中位于第二层数据链路层，也有的交换结构 介于第二二层与第三层之间。它负责将一些端1 3 的数据流( 包，信元) 传送到另一些端口的器件， 它并不限定交换的内部的实现方式，可以是交叉点( c r o s s p o i n t ) 开关，也可以是存储转发式， 墨二兰查望奎垫墨竺堡堕 或别的结构。 图1 3 s w i t c hf a b r i c 是将输入传送到输出的一种器件 区别：路由器是根据口地址来完成数据转发的，而交换结构是根据映射于m a c 地址 的端口地址进行数据的传送。路由器必须处理不定长的i p 数据包，而交换结构往往只考虑 定长信元的交换。交换结构是路由器的交换核心，它通过背板与线路卡和控制设备相连接， 才能构成完整的路由器。本文以下的内容仅限于交换结构的讨论。 1 2 2 信元与包( c e l l l p a c k e t ) 通过交换信息包分为两种，一种是定长的信息包，一种是变长的信息包。高性能路由器 往往采用定长信息包。称为”信元”( c e l l ) 。 如果采用定长信息包，将会给调度器的设计带来方便。可以以定长信息包通过背板的时 间( 我们称为时隙) 为单位来实现调度，在每个时隙结尾时输入与输出均空闲，这样调度器 设计将会简单，只须对有请求的端口进行调度并根据调度结果配置交叉开关即可，易于实现 性能较好的调度算法。 若使用变长信息包，则必须随时跟踪输入输出连接与端口状态，为保证性能须在变长信 息包传输完毕与提出连接请求时进行下一次调度，而这些时间是不易预知的，这会给调度器 的设计带来相当大的复杂性。 另一方面，使用定长信息包即信元传输也有一定的缺点。首先，将不同长度的信息包拆 成定长的信元，有可能造成带宽的浪费，因为通常信息包的长度不会都是信元长度的整数倍， 一般在最后一个信元中会有空闲填充：其次，拆包和组包也会带来一些额外的工作量和麻烦， 如果采用某些调度算法，或者采用多个交叉开关，可能这些额外的问题还比较突出。 1 2 3 单播与多播 如果信息包仅从一个端1 2 传输到另一个输出端口，则称为单播( u n i c a s t ) 。如果信息包需 要从一个端口同时传输到多个输出端口，则称为多播或者组播( m u l t i c a s t ) 。需要输出的端口 数称为多播的扇出系数( f a n o u t ) 。多播是交换结构必须支持的一项功能。多播的表示一般采 j “b i t m a p ”的方法，因为这种方法最简单。而且单播可以看成扇出为i 的多播的特例来统 一表示。以1 6 1 6 的交换结构为例，我们用1 6 b i t 的“b i t m a p ”来表示多播，如果一个端1 2 有多播的扇出，则对应的b i t m a p 位置l ，否则置0 。b i t m a p 中l 的个数就是扇出系数。 但是，如果端口数比较大( 3 2 ) 的话，将使得在设计信元( c e l l ) 的表头格式时无法对全 部端口使用位映射模式( b i t m a p ) 。常用的解决方法是将端口进行分组，对组内的多播采用位 映射模式，而对跨组的多播则采用组间复制的方式。基于这种方案，我们可以假定：端口总 数为，将个输入输出端口分成k 组，每组n 个端口，一般情况下n 为2 的方幂。 1 2 4 服务质量( q o s ) 在传统i p 网络中，数据的传送是“尽力而为”的。数据在网络上的传输时间，根据网 络上的流量情况不同，是不确定的。随着i p 电话( v o t e ) 、视频点播w o d ) 等实时网络业务的 出现，要求网络应满足保证的带宽以及一定的传输延时和延时变化等需求。这些要求可以通 过服务质量( q o s ) 来表述和实现。q o s 也是一种能力，具有实际的度量指标，包括业务可用 性、延迟、延迟抖动、吞吐量( 或带宽) 和丢包率等几个方面。通过这些指标，即可完全定义 网络的服务特性。 交换结构的调度算法一般通过不同的优先级设置以支持4 级或者8 级不同级别的q o s 。 4 中国科学技术大学博士学位论文 基于共享存储结构的高速交换系统 而不同的调度算法对q o s 的支持方式也会有所不同，有的对各个优先级的信息包按照严格 的优先级等级顺序来传递，有的则采用对不同优先级进行加权的方法来保证低优先级的信息 包不会被饿死。 1 2 5 加速i ：p , ( s p e e du p l 为了提高系统的交换性能，往往采用了使交换结构的信元交换速率高于线路卡信元传输 速率的方法。假设线路卡的信元传输速率为v ，交换结构的信元交换速率为线路卡的s 倍， 即其速率为s v ；s 便称为加速比( s p e e d u p ) 。在有加速比的系统中( s 1 ) ，因为虽然输出端口 的平均线速v ，但其瞬时速率可能会达到s v ，所以在输出端口必须有一定长度的f i f o 作 缓冲之用。 1 2 6 反压( b a c kp r e s s u r e l 反压也称流控( f l o w c o n t r 0 1 ) 。如果各个线路卡的信元在一段时间内都拥向同一个输出端 口，则可能会使交换结构发生阻塞。为了避免交换结构被阻塞的情况发生，交换结构在接近 阻塞之前便应该通知相关的输入端口，令其降低传送信元的速率或者暂停信元的传送。这种 交换结构向线路卡报告阻塞情况的信号便称为反压信号。按照是否占用有效的通信带宽来 分，有带内( 1 1 1b a n d ) 和带，b ( o u tb a n d ) 两种不同类型的反压策略。带内反压会降低交换器的 有效吞吐量，而带外反压会增加额外的硬件连线，所以它们各有利弊。 1 2 7 虚拟输出队列( v o q ) 输入队列中只有第一个信元可以被调度的策略称为输入排队( f i f o ) 。这一方法被证明是 低效的，原因在于它可能造成队列头( h e a do f l i n e ，h o l ) 阻塞：如果队列中第一个信元被阻 塞，那么后面的信元即使目的端口与第一个信元不一样，也无法得到调度。由于对交换结构 和输入排队的争用引起了延迟的变化，所以输入排队交换器通常不能控制延迟。对于一个输 入排队交换器，信元分布为目的端口均匀分布( u n i f o r m l yd i s t r i b u t e ) 的贝努里独立一致到达 ( b e m o u l l ii i da r r i v a l s ) ，当端口数很大时，晟大可以得到的吞吐量仅仅为5 8 j 。对于其它 的分布，可能会导致更糟糕的结果。 在同一时刻，| v 个信元可以同时转发到同一个输出并且在那里排队等候传输到输出链路 上的策略称为输出排队。输出排队的主要优点是所有信元被延迟一个固定量，可以通过交换 器来控制延迟。输出排队的主要缺点是对于一个端口交换器，内部互连和输出队列必须 运行在倍线速率上。当端口数大或者线速率高的应用中，输出排队会面临很大的困难。 在输入排队调度器中，队列头阻塞可能浪费近一半的带宽。经过改进后的虚拟输出队列 ( v i r t u a lo u t p u tq u e u i n g ) 方案可以完全消除队列头阻塞。在每个输入，为每个输出保留一个 单独的f i f o ，如下图所示： 图1 4虚拟输出队列示意图 一个刚到达交换器的信元被置于对应其输出端口的f i f o 队列中。在每个时隙的开始， 调度算法检查所有输入端口中各个f i f o 队列的内容，在输入和输出间发现一个不冲突的匹 配。理论上，一个精心设计的调度算法可以使交换器的吞吐量从输入排队的5 8 增加到使用 虚拟输出排队的l o o 2 ”。这是因为队列头阻塞已经完全被消除：没有信元被它前面通向一 个不同输出的信元所阻塞。 第一章高速交换系统综述 1 2 8 结合的输入和输出排队( c t o q ) 输出排队在保证通信量的服务质量方面比输入排队和虚拟输出排队要强。在输出排队交 换系统中，到达的信元被立刻转发到相应的输出端口，从而消除了输入阻塞，这样做有两个 好处：( 1 ) 只要存在目的地为某输出端口的信元，该端口就不会空闲；( 2 ) 可以对信元的离开 时间调度从而满足不同服务质量要求信元对时延的限制。然后很不幸，输出排队对硬件的速 度要求很高，在交换带宽很高( 几十g b p s 甚至几百o b p s ) 时很难实现。在输出队列的性能优 越性和输入队列的易实现性之间做个折衷，就有了结合的输入和输出排队c i o q ( c o m b i n e d i n p u ta n do u t p u tq u e u i n g ) 。 i n p u t l i n p u t n v o q v o q v o q 1 丽 图1 5c i o q 排队结构示意图 如图1 5 ，c i o q 在输入端设计有虚拟输出队列，在输出端设计有输出队列。由于有输 入缓存，对于端口数为n 的交换系统，c i o q 不要求输出队列和内部交换互联的速度达到端 口速率的n 倍，从而大大降低了设计的难度。 1 3 交换结构调度算法的模型描述 考虑在下图中连接m 个输入到n 个输出的具有虚拟输出队列的交换器，并假定它所交 换的信息包是定长的。在输入i 的到达进程( a r r i v a lp r o c e s s ) a ( f ) ，1 i m ，是一个被 称为信元的固定长度信息包的离散时间进程( d i s c r e t e t i m ep r o c e s s ) 。( 除非特别声明，我们 假设a ，( t ) 是稳态的( s t a t i o n a r y ) ，各态历经的( e r g o d i c ) ) 在每个时隙的开始，在每个输入 到达0 个或者是1 个信元。每个信元包含着一个标志，表明它的目的输出j ，1 j sn 。当 一个目标为输出j 的信元到达输入i 时，他被放置到f i f o 队列q ( i ，_ ，) 中，它的占有 ( o c c u p a n c y ) 是“( f ) 。我们应该将到达进程a “( t ) 定义为在输入i 以概率 ，到输出j 的到达进程，到达进程的集合a ( t ) = a ，( f ) ；l f m ) 。如果一( f ) 没有输入和输出被超额使 _ 【_ j 就是说 l 五， ：a l ，那个它就是允许的( a d m i s s i b l e ) ，否则就是不允许的 i ， ( i n a d m i s s i b l e ) 。 i n p u t l 一 也世蝴l ! 喘缈 l - 图1 6具有虚拟输出队列交换器示意图 f i f o 队列按照下面的方式被服务。一个调度算法在一批输入和输出中选择一个不冲突 - 6 堂： ! 望型! ! ! 堕奎堂苎主堂垡堕苎 苎至茎主查堕堕塑竺塞鎏銮垫墨竺 的匹配m ，每个输入连到最多一个输出，同时一个输出最多连到一个输入。在时隙结尾， 如果输入i 被连接到输出j ，一个信元从q ( i ，j ) 中移出，送到输出j 。很显然，从输出j 的离 开进程( d e p a r t u r ep r o c e s s ) d j ( t ) ，概率为，也是一个离散时间进程，在每个时隙结尾 或者是0 或者是1 个信元从一个输出离开。我们应该将离开进程d “( t ) ，概率为，定义 为从输入i 接收，从输出i 离开的进程。 为了找到一个匹配m ，调度算法需要解决一个偶图( b i p a r t i t eg r a p h ) 匹配问题。偶图的 一个例子示于f 图中。 i 】| ：x l u n p l e “g t a r l i 卜m - - l j i - n b i e i 郴嘶r m _ 蚺i 雌m - g ， 图1 7偶图的一个例子 定义g = f v ，e 】为一个使用边e 来连接顶点v 的无向图( t m d i r e c t e dg r a p h ) 。连接顶点 i ，l f 0 ，在图g 中输入i 输出j 之间有一个边。权重的定 义根据算法有所不同。举个例子，在一些算法中。权重总是等于1 ，表明队列是空或非空。 在其他的算法中，权重，可能是整数值，譬如等于上，( f ) 。 对于所有的调度算法都有很多我们需要的特性： 熬室一个有效的算法是在每次匹配中可以服务尽可能多输入队列的算法。通常，极 大匹配问题没有个可以在硬件中快速计算的解决方案，因此我们描述的每个算法找到一个 弧极大匹配m m ，这里i m ，图m 。i 。 直蚕堕量一个保证虚拟输出排队的积压很低的算法。理想情况下，算法将保证每个 输入和输出可提供的负载达到1 0 0 。 氇定：眭对于一个给定的允许的通讯模式，如果每个输入队列o ( i ，) 的期望的占有 是有限的，就是说研厶( 咖 o 。，我们定义这个算法是稳定的。对于一个给定的算法，如 果一个稳态的通讯模式不引起交换器的不稳定，我们称之为可以支撑的( s u s t a i n a b l e ) 。 玉避理如果对于一个给定的通讯模式和调度算法，一个非空输入队列无限期地未被 服务，我们称之为饿死。 雠为了获得最高的交换带宽，调度算法不成为性能的瓶颈是非常重要的。因此算 法要尽快地找到个匹配。 易塞强如果算法在实用上快速运行，它必须在专用硬件中实现，最好在单芯片中。 实现的复杂度包括调度器必须保持的状态量，基于状态做出一个判决所需要的逻辑量。在每 个信元时间的开始和结尾更新状态所需要的通讯量。 7 蔓= 里塑垄銮垫墨竺堡垄 1 4 互联网通信量 在过去三十年里，互联网的应用得到了飞速发展。从早期单纯的文件传输、远程登录、 电子邮件和网络新闻到后来出现的视频会议、多媒体传输和电子商务，网络的带宽有了巨大 的增长，互联网通信量也变得越来越复杂。 1 4 1 互联网通信量的特征 经过对互联网骨干上路由器的统计，互联网通信量主要有以下特征”“： 1 t c p ( t r a n s f e rc o n t r o lp r o t o c 0 1 ) 占据了网络的主要流量 九十年代初期的网络流量研究显示t c p 协议是互联网上的主要协议。近年来出现了很 多如视频流、口电话和多播等主要使用u d p 协议的网络应用，这些应用可能会逐渐地削减 t c p 通信量的比例。然而研究显示，t c p 仍然是造成互联网通信量的主要因素，并且在可 预见的将来还是这样。主要的原因是w w w ( w o r l dw i d ew e b ) 的巨大发展。w w w 用户数量 的增加、易于使用的w w w 浏览器的普及和网站中越来越丰富的多媒体内容使得t c p 的流 量量指数增长。 2 数据流是双向的，但通常是非对称的 互联网上大部分的应用都是双向交换数据的，因此网络的流是双向的。但是两个方向上 的数据率有很大的差异，这是因为从网站下载时会导致从网站到客户端方向的数据量比另外 一个方向多。 3大部分t c p 会话是短期的 研究显示，超过9