（通信与信息系统专业论文）多级交换结构及其调度算法研究.pdf

摘要 摘要 交换网络处理的业务流量增长要求交换网络的容量需要不时地进行升级，单 级交换机由于受芯片的管脚和i c 实现复杂度的限制，无法应用于大规模可扩展交 换机，因此，采用由多个交换单元构成的多级网络是目前常用的解决方案。另一 方面，用于多级交换结构的传统调度算法往往忽略了输入业务的特性，如：不同 业务的相对优先级、时延、时延抖动或不同的服务等级等特性，在支持可扩展性 和满足各种业务特性方面，还有待改进。 针对以上问题，本文的主要贡献和创新在于：通过对d u n e n e t w o r k s 公司某交 换芯片的研究，对m s m 型三级c l o s 结构做出了改进；设计了以业务特性为导向 的两种调度算法：a c b s ( a s y n c h r o n o u sc r e d i t b a s e ds c h e d u l i n g ) 算法和c b s t d m ( c r e d i t b a s e ds c h e d u l i n g w i t h t d m ) 算法；搭建了通用的仿真模型实现两种算法， 对其进行了多方面的仿真实验并对算法性能进行了分析和讨论。仿真表明，改进 结构和两种调度算法能取得较好的性能。 首先，本文从交换机的作用和地位，交换技术的基本理论，交换结构和调度 算法在交换机中的作用几个角度出发介绍了本文的背景知识，并展望了交换网络 的技术发展趋势。然后分析了分组交换结构从单级结构到多级结构的演进历程， 分析当前大容量分组交换网络的现状，并研究讨论了用于单级结构和多级结构的 不同调度算法。 其次，本文对m s m 型的三级c l o s 结构做出了改进，改进的交换结构能支持 分布式的“拉”式调度算法，具有更加灵活的可扩展性。 再次，在改进结构基础上设计了两种调度算法a c b s 和c b s t d m ，两种算法 均属于流调度算法，采用分布式的调度方式，与传统的用于多级结构的集中式两 次匹配的调度算法有很大的区别，传统算法将输入端口的数据包“推”向交换结构的 输出端口，而a c b s 算法和c b s t d m 算法是通过输出调度器将数据包从输入端口 “拉”向输出端口。在a c b s 中，输入输出之间采用异步交互控制信息的方式进行 分布式的一次调度算法，仿真表明，它能充分考虑业务特性和输出带宽进行调度， 在均匀负载的情况下能取得较高的吞吐率，降低数据包的平均时延，较好地适用 于热点业务，同时能方便地支持负载均衡；c b s t d m 通过令牌进行调度，输入级 电子科技大学硕士学位论文 采用时分复用的方式共享链路，它能降低工程实践的复杂度，并且也能在考虑业 务特性基础上调度，能较好的支持不同的业务特性，对不同优先级业务表现出较 好的性能，也能有效而简易地支持负载均衡。 最后，为了考察基于改进m s m 型三级c l o s 结构的两种算法的性能，我们搭 建了基于这种交换结构的通用仿真模型，并在此基础上实现了上述两种算法，对 它们做了多方面的仿真实验和仿真结果分析，对目前系统的不足提出了下一步的 改进方向。 关键词：多级交换，三级c l o s ，a c b s 算法，c b s t d m 算法，业务特性 i i a b s t r a c t a b s t r a c t c o n f r o n t e dw i t ht h ee x p l o s i o no fc o m m u n i c a t i o nt r a f f i c i ni n t e r n e t ，t h e c o m m u n i c a t i o nn e t w o r k sa r c h i t e c t sm a k eg r e a te f f o r t st op r o v i d es c a l a b i l i t yf o rs w i t c h a r c h i t e c t u r ei nt h ec u r r e n tt o u t e r sa n ds w i t c h e s s i n g l e s t a g es w i t c h e sa r eh a r dt o i m p l e m e n ti n s c a l a b l es w i t c h e sf o rt h el i m i t a t i o no f p i n sa n dc o m p l e x i t i e so f i cd e s i g n t ob u i l dal a r g e rs w i t c h i n gf a b r i cb yu s i n gi n t e r c o n n e c t i o nn e t w o r k si n c l u d i n gs e v e r a l s w i t c he l e m e n t si sc o m m o n l yu s e da ss c a l a b i l i t ys o l u t i o n s n l et r a d i t i o n a ls c h e d u l i n g a l g o r i t h m sw h i c hu s e di nm u l t i s t a g en e t w o r k sm o s t l yi g n o r et h ef l o wa t t r i b u t e sl i k e r e l a t i v ep r i o r i t i e s ，d e l a y , j i t t e ra n ds oo n o nt h es t u d yo ft h ed a t a s h e e to fas w i t c h i n gc h i po fd u n en e t w o r k s ，t h i st h e s i s f o c u s e so ns e v e r a la s p e c t sa sb e l o w ：i m p r o v i n gt h ea r c h i t e c t u r eo ft h em s m3 - s t a g e c l o sn e t w o r k ，d e s i g n i n gt w os c h e d u l i n ga l g o r i t h m s ： a c b sa n dc b s t d m ， c o n s t r u c t i o no fag e n e r a lm o d e lf o rs i m u l a t i o n ，a n dd i s c u s s i n gt h es i m u l a t i o nr e s u l t s s i m u l a t i o nr e s u l t ss h o wt h a tt h i si m p r o v e da r c h i t e c t u r ea n ds c h e d u l i n ga l g o r i t h m sc a i l a c h i e v eh i g hp e r f o r m a n c e f i r s t t h i st h e s i sd e a l sw i mt h eb a s i ct h e o r i e so fs w i t c h i n gt e c h n o l o g i e si n c l u d i n g s w i t c hf a b r i c sa n ds c h e d u l i n ga l g o r i t h m sa n dl o o k sf o r w a r dt ot h ef u t u r eo ft h i sf i e l d t h e n ，t h ed e v e l o p m e n to fs w i t c hf r o ms i n g l e s t a g et om u l t i s t a g ei sd i s c u s s e d ；t h e d i f f e r e n c e so na r c h i t e c t u r ea n ds c h e d u l i n ga l g o r i t h mb e t w e e ns i n g l e - s t a g ea n d m u l t i s t a g ea r ea n a l y z e d s e c o n d ，i m p r o v e m e n t sh a v eb e e nm a d eo nt h em s m3 - t a g ec l o s ，w h i c hc a n s u p p o r td i s t r i b u t e d p u l l ”s c h e d u l i n ga l g o r i t h m sw i t hb e t t e rs c a l a b i l i t i e s t h i r d ，o nt h eb a s eo ft h ei m p r o v e da r c h i t e c t u r e ，t w os c h e d u l i n ga l g o r i t h m sh a v e b e e nd e s i g n e d ：a c b sa n dc b s t d m ，w h i c hb o t ha r ed i s t r i b u t e dt r a f f i cs c h e d u l i n g s c h e m e sa n dt o t a l l yd i f f e r e n tf r o mt h et r a d i t i o n a lf a b r i cs c h e d u l i n gs e t i c i t i e s t h e t r a d i t i o n a lf a b r i cs c h e d u l i n ga l g o r i t h m sp u s ht h ed a t at o w a r d se g r e s s ；h o w e v e r ，a c b s a n dc b s t d mp u l ld a t af r o mi n g r e s s i na c b s ，i n g r e s sa n d e g r e s s t r a n s f e r a s y n c h r o n o u sc o n t r o lm e s s a g e st of i n i s hd i s t r i b u t e d “o n e h o p ”s c h e d u l i n g s i m u l a t i o n 1 1 1 电子科技大学硕士学位论文 r e s u l t ss h o wt h a ta c b sc a l lt a k ef l o wa t t r i b u t e si n t oa c c o u n ta n da c h i e v eh i g h t h r o u g h p u tu n d e ru n i f o r mt r a f f i c s i ta l s op e r f o r m sw e l lu n d e rn o n u n i f o r mt r a f f i c sa n d c a ne a s i l ya c h i e v el o a db a l a n c ei nt h ef i r s t s t a g el i n k s c b s t d ma l s os c h e d u l e sw i t h c r e d i t s h o w e v e r , a l lt h ei n g r e s sm o d u l e ss h a r et h ef i r s t s t a g el i n k si nat d mw a y i t c a nr e d u c et h ec o m p l e x i t i e so f i m p l e m e n ta n dt a k et h ef l o wa t t r i b u t e si n t oa c c o u n t ，t o o s i m u l a t i o nr e s u l t ss h o wt h a tc b s t d mc a np e r f o r mw e l lw h e ni n p u t t i n gu n i f o r m t r a f f i c sa n dt r a f f i c sw j md i f f e r e n tr e l a t i v ep r i o r i t i e s f i n a l l y , ag e n e r a ls i m u l a t i o nm o d e li sb u i l tt o t e s tt h ep e r f o r m a n c eo ft h e i m p r o v e da r c h i t e c t u r ea n ds c h e d u l i n ga l g o r i t h m s s i m u l a t i o nr e s u l t sa r es h o w e da n d d i s c u s s e di nt h i st h e s i s t h r o n 曲t h er e s u l t s ，s o m ei m p r o v e m e n t sh a v eb e e np r o p o s e d i nt h ee n do f t h i st h e s i s k e yw o r d s ：m u l t i s t a g es w i t c h ，3 - s t a g ec l o s ，a c b s ，c b s t d m ，f l o wa t t r i b u t e i v 简略字表 a c b s a s f a t m 简略字表 a s y n c h r o n o u sc r e d i t b a s e ds c h e d u l i n g a t ms w i t c h i n gf a b r i c a s y n c h r o n o u st r a n s f e rm o d e c b s t d mc r e d i t b a s e ds c h e d u l i n gw i t ht d m c r r dc o n c u r r e n tr o u n d r o b i nd i s p a t c h i n g d e m u x d e m u l t i p l e x e r d w d md 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 e d f f i f 0 h o l i l b i l c i p i q i i t r m i s l i p m m m m p l s m s m m u x e a r l i e s td e a d l i n ef i r s t f i r s ti nf i r s to u t h e a do f l i n e i n t e r n a ll i n eb l o c k i n g i n t e r n a ll i n ec o n t e n t i o n i n t e m e tp r o t o c o l i n p u tq u e u i n g i t e r a t i v er o u n dr o b i nm a t c h i n g i t e r a t i v er o u n dr o b i nm a t c h i n gw i t hs l i p m e m o r y - m e m o r y - m e m o r y 基于令牌异步调度 a t m 交换结构 异步传输模式 基于令牌时分复用调度 并发轮询分配算法 解复用器 密集波分复用 最早时限优先 先进先出 队头阻塞 内部连线阻塞 内部连线冲突 互联网协议 输入排队 迭代轮询匹配 使用s l i p 的迭代轮询匹 配 缓存一缓存一缓存 m u l t i p r o t o c o ll a b e ls w i t c h i n g多协议标签交换 m e m o r y - s p a c e m e m o r y m u l t i p l e x e r v i i i 缓存一空分一缓存 复用器 电子科技大学硕士学位论文 0 p c o q o s i r m p i m q o s r d r r s a r s l i p s s s t d m v o q w f q w r r o u t p u tp o r tc o n t e n t i o n o u t p u tq u e u i n g o p e ns y s t e mi n t e r c o n n e c t i o nr e f e r e n c em o d e l p a r a l l e li t e r a t i v em a t c h i n g q u e r y o f s e r v i c e r a n d o md i s p a t c h i n g r o h n dr o b i n s e g m e n t a t i o na n dr e a s s e m b l e s e r i a ll i n ei n t e r f a c ep r o t o c o l s p a c e s p a c e - s p a c e t i m ed i v i s i o nm u l t i p l e x i n g v i r t u a lo u t p u tq u e u e w e i g h t e df a i rq u e u i n g w e i g h t e dr o u n d r o b i n 输出端冲突 输出排队 开放系统互连参考模型 并行迭代匹配 服务质量 随机分配 轮询算法 分段重组 串行线路接口协议 空分一空分一空分 时分复用 虚拟输出队列 加权公平排队 加权轮询 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：选望 日期：渺l ，年易月，) 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：塑量 导师签名： 日期：确 第一章绪论 第一章绪论 网络业务的爆炸式增长促进了通信技术和计算机技术的迅速发展，人们对通 信带宽的需求也渐渐提高，同时，对i n t e m e t 的服务内容和服务质量也提出了更 高的要求。随着光传输技术的发展和成熟应用，传输链路和传送节点己不再是限 制骨干网发展的主要因素，而作为业务节点的交换机与路由器却成为制约网络性 能的“瓶颈”【l 】。为了适应网络流量和传输带宽的增长速度，大容量交换技术面临 着新的挑战，成为当前国内外研究的持续热点。下面，我们将详细介绍交换技术 的发展和研究现状，为后续章节的进一步展开做好铺垫。 1 1 分组交换技术概述 分组交换技术是在计算机技术发展到一定程度，人们除了打电话直接沟通， 通过计算机和终端实现计算机与计算机之间的通信，而产生的一种交换技术，它 源于数据业务，例如x 2 5 。从2 0 世纪末期以来，分组交换网络的设计得到极大 的发展，其技术己经超过电路交换技术，成为目前研究最广泛的交换技术，目前 的研究热点n g n ( n e x tg e n e r a t i o nn e t w o r k ) 就是基于分组的网络( i t u t y 2 0 0 1 2 0 0 4 ) ，在本文中，我们所提到的交换都指分组交换。分组交换节点中核 心的器件是交换矩阵( 又称为交换结构) ，本章将从交换结构和调度算法两个方面 进行概述。 1 1 1 交换结构概述 任何大型网络总体来讲都应该包括三大部分：网络终端设备、网络传输链路 和网络交换节点。现今的终端设备能够满足人们的要求，也正是它向整个网络提 出了更高的通信带宽要求；同时，密集波分复用( d w d m ：d e n s ew a v e l e n g t h d i v i s i o nm u l t i p l e x i n g ) 技术的应用，成倍地提高了光纤链路的传输能力，使其畅 通无阻；因而通信的瓶颈就集中在了中转处的交换设备上。 如今的交换机和路由器已经越来越融合，相互注入了对方的功能，难以区分。 一些文献把交换机和路由器统称为交换设备或交换机。但即使在一个设备中，按 电子科技大学硕士学位论文 功能也可以分为两部分：路由( r o u t i n g ) 、转发( f o r w a r d i n g ) 或交换( s w i t c h i n g ) 。 按照惯例，路由在o s i 参考模型( o s i r m ：o p e ns y s t e m i n t e r c o n n e c t i o n r e f e r e n c e m o d e l ) 中属于第三层；而交换( 又可以称作转发) 在分层模型中处于第二层。 在这里，我们研究的是处于二层的交换技术。 分组交换网络的交换能力在很大程度上决定着分组交换系统的性能，如吞吐 率，交换时延及其抖动、丢失和乱序等。如图1 - 1 给出了分组交换系统的参考模 型。交换系统包含输入输出接口和交换网络，交换网络又包括输入、输出端口和 将它们互连起来的连接网络( 又称交换结构) 。 输 出 图1 - 1 交换机参考模型 一般来说，交换结构处理的是定长的数据单元，即信元( c e l l ) 。如果交换结 构传递变长的分组，则要求输入输出接口具有分段重组功能( s a r ：s e g m e n t a t i o n a n dr e a s s e m b l e ) ，s a r 功能一般在交换结构外部完成【2 。这里所说的信元泛指定 长的分组，不仅限于a t m 信元。交换结构接收或者发送一个信元的时间称为一 个时隙( t i m e s l o t ) 。 在交换结构中，有一些关键问题需要解决，如图1 2 所示。在分组交换结构 中，当多个信元要同时去往一个输出端口，会造成输出端冲突( o p c ：o u t p u tp o r t c o n t e n t i o n ) ，解决冲突的办法是选择一个信元从输出端口发出，将其余信元暂时 缓存或丢弃。当多个信元要同时经过一条内部连线时，就会造成内部连线冲突 ( i l c ：i n t e r n a ll i n ec o n t e n t i o n ) ，或称为内部连线阻塞( i l b ：i n t e r n a ll i n e b l o c k i n g ) ，解决冲突的办法是暂时缓存信元或丢弃信元。 信元丢弃势必引起交换结构性能的下降，因此，针对以上问题，传统的路由 2 第一章绪论 器一般采用对信元进行缓存的办法，例如基于输出排队( o q ：o u t p u tq u e u i n g ) 。在 这种结构下，到达输入端口的信元马上被交换到相应的输出端口。o q 的优点是 能够提供最优的吞吐量和延迟控制，其调度算法在理论上己得到深入的研究且实 现简单。但为了保证o q 的正常运行，交换结构的内部带宽和输出队列的存储器 访问速率必须是输入端口链路速率的倍( 如果输入速率不同，则为端口速率之 和) ，即要求倍的加速比，这里，是输入端口数。随着链路速率或端口数的 增加，在现有的工艺水平下很难实现高速的基于o q 的交换结构。 为了克服o q 结构的可扩展性问题，高速路由器考虑采用输入排队( i q ：i n p u t q u e u i n g ) 。到达的信元首先被保存在输入端口的缓冲区中，然后通过调度算法决 定信元何时通过交换结构传送到输出端口。i q 的优点是不需要加速比，但当资源 冲突引起信元暂时缓存，如果缓存里只有一个f i f o ( f i r s ti nf i r s to u t ) 队列， 就会产生队头阻塞( h o lb l o c k i n g ：h e a do fl i n eb l o c k i n g ) 问题：如果队列头 部的信元被阻塞，同队y , j n 其他输出端口的信元就不能被转发。研究表明，当端 口数较多时，在所有输出均匀分布的b e m o u l l i 到达下，i q 只能达到5 8 6 的吞吐 率【3 】。采用虚拟输出排队( v o q ：v i r t u a lo u t p u tq u e u i n g ) 可解决这个问题【4 】，获 得高吞吐率。v o q 即是在输入缓存中为每个输出端口设一个单独的f i f o 缓存队 列。 电子科技大学硕士学位论文 萎 - 请求 + 应答，接受 请求应簪接受 图2 - 1 0 第一次匹配示意图图2 1 1 第二次匹配示意图 1 r d 算法 r d 算法的思想源自于单级交换的p i m 算法。其各次匹配中的选取都采用随 机的方式。算法步骤如下： 一、第一次匹配( 输入模块内) ： 步骤一：有排队的v o q 向本模块中的所有出端发出请求； 步骤二、步骤三：与p i m 算法的步骤二、步骤三相同。出端随机地选取有请 求的v o q 来一一配对。 二、第二次匹配( 中间模块内) ： 步骤一：某个中间模块入端如果得知对应输入模块的出端在第一次匹配中得 2 2 kfy 第二章交换结构与调度算法研究 到了接受，这个入端将向输入模块的v o q 所要求的中间模块出端发出请求； 步骤二：出端从可能的多个请求中随机选取一个来承认。并且将这个承认传 回相对应的输入模块中的v o q ，允许其下一个时段发包。 尽管r d 算法的第一次匹配能够确保输入模块的所有出端得到最大匹配，但 不同输入模块之间相互独立，会在中间模块的匹配中产生竞争。这种竞争就限制 了整个交换的吞吐量。文献【2 6 中给出了在输入均匀分布的业务量时，r d 算法的 吞吐量公式： 。扣( 1 - 州 协z ， 其中的m 是中间级模块的个数，也就是输入模块的出端的个数；n 是输入模 块入端的个数，也就是一个输入模块所包含的输入端口个数；k 是输入级模块的 个数。令m , k 8 ，可得到：乙缸0 6 5 6 4 。 即使k 趋于无穷大，当m = n 时有： k = 您乖( 1 - 扪小e 一2 - s ， 2 c r r d 算法 从式( 2 2 ) 可以看出，r d 算法必须采用一定的加速比才能获得高的吞吐率， 加速比策略是用硬件条件减少队首阻塞，从而改善性能的方法。如果交换体的处 理速度与输出端口的速度是输入端口传输速度的c ( c 1 ) 倍( c 称为加速比， 也叫加速因子) ，则允许最多c 个分组无阻塞地同时通过交换体到达同一输出端。 加速比的实现依赖于高速硬件或并行处理的技术2 7 1 。 而c r r d ( c o n c u r r e n tr o u n d r o b i nd i s p a t c h i n g ) 算法则克服了这个缺点。 c r r d 算法在文献【2 6 】中提出，其基本思想是将单级c r o s s b a r 的i s l i p 算法扩展 到三级交换中。使得不需要r d 算法中的扩展比，以及用r o u n d r o b i n 窗口轮询 的方式代替r d 算法中的随机选取方式，以简化仲裁算法的硬件实现。算法的具 体步骤如下： 一、第一次匹配( 输入模块内) ： 1 第一次迭代： 电子科技大学硕士学位论文 步骤一：有排队的v o q 向本模块中的所有出端发出请求； 步骤二：每个出端取本处的窗口位置寄存器值，按照r o u n d r o b i n 方式，选 择一个请求，并向该v o q 发回承认； 步骤三：v o q 的仲裁器取自己的窗口位置寄存器值，依照r o u n d r o b i n 方式， 从可能的众多出端的承认中选取一个来接受； i 第i 次迭代( i 1 ) 步骤一：上一次迭代没有匹配的v o q 再向所有没有匹配的出端发出请求； 步骤二、步骤三：如同第一次迭代操作； 二、第二次匹配( 中间模块内) ： 步骤一：中间模块某个入端如果从对应输入模块的出端得到信息有包在该出 端得到了转发允许，该入端将向该包的目的地址所决定的出端发出请求； 步骤二：出端取本处的窗口位置寄存器的中，仍然按照r o u n d r o b i n 方式， 从可能的多个入端请求中选取一个来承认； 步骤- - - - ：第二次匹配得到承认以后，对应的输入模块的v o q 发送排队的数 据包。但是，只更新输入模块第一次迭代并且中间模块匹配得到承认的所对应的 输入模块的v o q 、出端和中间模块的出端的窗口位置寄存器值( 即循环加1 ) 。 前文已经对三级交换所采用的协议匹配的基本思路做了分析，指出与单级交 换存在两处不同的地方。c 硒算法采用的就是这种协议匹配的思路，并且如同 i s l i p 算法，使用了多次迭代，以使得在输入模块中得到最大匹配。按照其中一 个不同点所说的，c r r d 算法在中间级的第二次匹配时不需要入端的接受选取， 而只要出端的窗口寄存器来进行承认的轮询选取。文献【2 6 提到，c r r d 可以取 得1 0 0 的吞吐量。 2 3 4 三级结构调度算法小结 在单级调度上引申出目前多级交换调度算法的普遍做法，介绍r d 算法、 c r r d 算法了的步骤和工作流程。r d 算法的两次匹配采用随机选取的方式，必 须采用一定的扩展比才能获得高的吞吐率；而c r r d 算法将单级c r o s s b a r 的i s l i p 算法扩展到三级交换中，用轮询代替随机选取机制，使得不需要r d 算法中的扩 展比，并且硬件实现较随机方式更为简单。因此，本文将c r r d 算法作为a c b s 和c b s t d m 算法性能比较的依据。 第二章交换结构与调度算法研究 2 4 本章内容小结 本章首先研究了交换结构的演进历程，介绍了从最初的单级交换结构到可扩 展的多级交换网络的结构。单级结构能够达到比较高的吞吐率，但是共享内存结 构可扩展性比较差，当线路接口卡数量较多时，性能将受到一定的影响；而 c r o s s b a r 能够达到比较高的速率，需要设计完善的调度算法并用高速硬件实现调 度器，但是很难应用于可扩展性强的交换结构中。多级结构由于其灵活的可扩展 性而广泛应用于大容量可扩展交换机中，我们介绍了典型的b a n y a n 网络，三级 c l o s 网络，为下一章对c l o s 结构作出改进奠定了基础。 其次，本章研究了用于单级c r o s s b a r 的几种经典算法。p i m 算法由于采用随 机选择，实现起来比较简单，也不会产生“饿死”现象，但是，如果迭代次数少， 网络吞吐率将会较低。i r r m 算法用轮循调度代替随机选择，但由于其应答指针 在每个时隙都同时更新，指针值存在同步现象，不能很好的解决竞争问题，吞吐 率较低。而i s l i p 算法中，应答指针等到接收到输入端的认可信号时才改变，指 针更新方式打破了i r r m 中存在的同步现象，从而提高了吞吐率。 最后，在单级调度算法上引申出目前多级交换调度算法的普遍做法，介绍、 分析了r d 算法、c r r d 算法。r d 算法必须采用一定的扩展比才能获得高的吞吐 率，而c r r d 将单级c r o s s b a r 的i s l i p 算法扩展到三级交换中，使得不需要r d 算法中的扩展比。 本章的背景研究为后续章节中对于多级结构的改进和调度算法的设计奠定了 基础。 电子科技大学硕士学位论文 第三章对m s m 型三级c l o s 结构的改进 在前面一章，我们已经提到过，三级c l o s 结构是采用基本交换单元来搭建大 型交换网络的最常用的拓扑。当前使用的交换网络拓扑多采用这种结构。其中， 研究得最多的是m s m 型的三级c l o s 结构。因为这种结构既能够有效地避免h o l ， 又能够缓存无法及时交换到指定输出端口的分组。 另一方面，传统的用于多级结构的调度算法是基于交换结构的集中式两次调 度方式。这类算法简单，易于实现，但集中调度的方式不够灵活，两次匹配的方 式也未能充分考虑输入业务特性，如不同的服务等级、相对优先级、时延和时延 抖动等。 为了解决以上的问题，根据d u n en e t w o r k s 公司的某交换芯片介绍，我们在 m s m 型三级c l o s 结构上做出了改进，并设计出了基于业务特性的分布式的a c b s ( a s y n c h r o n o u sc r e d i t - b a s e ds c h e d u l i n g ) 算法1 2 副和c b s t d m ( c r e d i t b a s e d s c h e d u l i n gw i t ht d m ) 算法【2 ”，将分别在后面的章节一一介绍。 3 1 结构概述 在前面一章，我们已经介绍过m s m 型的结构，这种结构在第一级交换单元 一般采用基于v o q 输入缓存或共享缓存的结构，即输入级缓存针对交换网络的 不同输出端口构建不同的v o q ，这样既能保证到达不同输出端口和优先级的分组 能够公平利用交换资源，避免h o l 阻塞；第三级缓存又可对当前时隙无法传送 到其目的输出端口的分组进行缓存，降低获取无阻塞特性所需要的内部连接数。 为了更好地支持交换结构的可扩展性，我们改进了m s m 型的三级c l o s 结构 ( 以下简称为改进结构) ，在输入增加了队列管理器，输出增加了令牌发生器和输 出调度器，如图3 1 所示。在这个三级结构中，我们将这三级分为输入级模块( i m ： i n g r e s sm o d u l e ) 、中间级和输出级( e g r e s sm o d u l e ) 。每一级都有多个模块 ( m o d u l e s ) ，每个模块又有多个入端( i p ：i np o r t ) 和出端( o p ：o u tp o r t ) 。这 里只有中间级是纯粹的c r o s s b a r 交换结构，没有缓存器件；而输入级和输出级模 块中都含有缓存队列。输入级包含v o q 以消除h o l 阻塞，输出级的输出队列用 2 6 第三章对m s m 型三级c l o s 结构的改进 于当多个数据包竞争同一输出端口和信元重组的缓存。在输出级当中，每个输出 端口都拥有一个输出端口调度器( 0 s ：o u t p u t s c h e d u l e r ) ，如图3 1 。 图3 - i 改进的m s m 型三级c l o s 结构 图3 2 改进的三级结构详细示意图 电子科技大学硕士学位论文 另外，实际交换机应该是n n 的对称结构，所以规定三级结构中输入级和 输出级模块的个数是相等的，并且每个输入模块的输入端口数和每个输出模块的 输出端口数也应该是相等的。而中间级c r o s s b a r 模块个数和每个模块的端口数是 可以调整的，但应该是输入端和输出端相等的“方形”结构。如图3 2 所示。 本文中在后续章节所使用的交换结构都是基于图3 ，2 ，为了表述准确，清楚， 表3 1 将常用到的结构参数和术语进行了定义： 表3 1 本文中的常见术语和参量含义 术语参量 含义参数取值范围 s m ( o 编号为i 的输入级模块 0 f k 一1 e m ( j ) 编号为j 的输出级模块 0 j k 一1 o p ( j ， ) e m ( j ) 中编号为h 的输出端口0 j k j o s ( j ，h )e m ( j ) 中编号为h 的出端口调度器 0 h n 一1 d f _ j 一j i p ( i h )s m ( o 中编号为h 的输出端口 d h n 一1 存放来自1 m ( i ) 去往在e m ( j ) 处的 v o q q ，j ，h ) 输出端口o p ( j ，h ) 的数据包的v o q q u e u e l ( i ，j ，h )v o q ( f ，j ，h ) 的队列长度 o s i s k j s t a t u s m s g ( i ，j ，h )来自v o q ( i ， ) 的队列状态信息 c r e d i t ( i ，j ， j来自o s ( j ，h ) 去往i m ( i ) 的令牌 0 j k j 0 h s n 一1 c c ( i ，j ，v o q ( i ，j ，h ) 的令牌计数器 t 。( i ，j ， )v o q ( f ，h ) 发送分组的起始时间 t 。d ( f ，j ，h )v o q ( i ，j ，h ) 发送分组的持续时间 3 1 1 输入级( i n g r e s s ) 每一个输入级模块1 m 包括n 个输入端口和m 个输出端口，其中，输入端口 是直接输入端口，而输出端口是间接输出端口，因为其输出只作为下一级的输入， 并不直接作为整个交换结构的输出。输入级中最重要的组成部分是虚拟输出队列 ( v o q ：v i r t u a lo u t p u tq u e u e ) 和队列管理器( q c t ：q u e u ec o n t r o l l e r ) 。 第三章对m s m 型三级c l o s 结构的改进 v o q 的作用是防止在输入级产生“队头阻塞”。与单级结构不同的是，在这个 多级结构中，n 个输入端口不仅要共享一个输入级模块，还要共享一组完整的 v o q 。而在单级结构中，每个输入端口都分别维持一组完整的v o q ，因而到来 的数据包可以根据输出端口号直接存储到相应的v o q 。三级交换中一个输入模块 才有组完全的v o q ，而每个输入模块连接了多个输入端口，所以同一个输入时 刻可能有多个输入端口需要将数据包存储到同一个v o q 。交换的第一个过程便要 完成这个工作。这些包在v o q 中的排队顺序可以由输入端口自由竞争决定。 输入级的另一个重要部分是队列管理器。在每个输入级模块中，都需要有 一个队列管理器来管理v o q 的状态，并根据当前状态及时向位于输出端口的输 出调度器发出队列状态信息来请求输出带宽。每当队列状态发生变化时，队列管 理器就向输出调度器发送信息，通知调度器及时更新队列数据库。为了减少控制 信息的流量，以避免控制信息过多地占用数据通道，我们设定，每当队列的长度 超过一个事先设置好的门限时，才进行发送队列信息的操作。 同时，当队列控制器接收到来自输出调度器返回的令牌( c r e d i t ) 之后，要根 据令牌所携带的信息将得到令牌的v o q 中的数据包发送到中间级，如果数据包 是变长分组( v a r i a b l e l e n g t hp a c k e t ) ，需要将其按照一定的方法处理之后再发送， 详细方法我们将在下两章介绍调度算法的时候详细描述。 综上所述，输入级在三级结构中起到非常重要的作用： 1 去往特定目的端1 ：3 的数据包在输入端的v o q 中排队，等待发送： 2 v o q 避免了队头阻塞； 3 队列控制器将队列的状态通知其相应输出端口的输出调度器； 4 根据输出调度器返回的信息发送存储的数据包。 3 1 2 输出级( e g r e s s ) 我们已经提到过，在每个输出级模块e m 中，不仅包含用于缓存暂时无法交 换到目的端口分组的输出队列o q ，还包含了与输出端口一一对应的输出端口调 度器o s 。输出级的主要作用在于支持队列进行输出带宽的竞争，输出调度器根 据队列状态信息向输入队列发出指挥发包的控制信息，我们称之为令牌。令牌是 由专门的令牌发生器产生的，每个输出级拥有一个令牌发生器，它根据各个输出 端口的带宽来产生令牌，并把令牌分配到各输出端口供输出调度器调配。由于目 电子科技大学硕士学位论文 前我们所研究的交换结构的所有输入端口和输出端口速率相等，所以，各个输出 调度器能够获得相同的令牌。 单级交换中输出排队在交换路径的仲裁中没有作用，而主要是为了支持变长 i p 包交换时在输出端的包重组。而在三级交换中，传向相同输出端口的，而来自 不同输入模块的输入端口的数据包经过不同的中间模块将在输出模块中出现竞 争。所以，它将主要用于解决去往同一输出级模块中的竞争冲突和用于数据重组。 输出级模块需要将信元先缓存起来再根据其目的地址将其放入对应的输出队列等 待重组，输出端一旦检测到属于同一数据包的信元全部到达之后，便将其重组为 完整的数据包并发送出去。 在上一章中，我们介绍过的用于三级交换结构的调度算法，如r d 、c r r d 算法等，都是采用集中式调度，在三级之间进行两次匹配完成的。尽管这样的算 法简单，较易实现，但是集中式的调度算法不易于扩展，而分布式的调度算法更 容易扩展，更适合于可扩展的多级结构。因此，我