（微电子学与固体电子学专业论文）基于交叉开关的可扩展交换结构及其调度算法研究.pdf

摘要 因特网的迅速发展要求路由器必须不断地提高内部交换能力。交换结构和调 度算法作为高性能交换机和路由器的核心技术，其性能直接影响甚至决定了路由 交换设备的性能。 三级交换结构由于可以将多个小型的交换单元互连在一起，具有良好的模块 化及非阻塞特性，比起传统的交换结构能够提供更大的交换能力。这类交换结构 已经广泛应用于商用核心路由器中，基于该结构的输入排队调度算法也成为研究 热点。但是，由于工程应用千差万别，标准三级交换结构的c l o s 连接及相应的调 度算法不能直接应用于具体工程中，必须对其进行扩展改进才能得到较好的交换 性能。 传统的调度算法是针对交换结构的输入输出端口进行匹配，从而建立各输入 模块和输出模块之间的连接，但这是以输出模块个数与交换结构的输出端口个数 相等为基础的。当输出模块的个数与交换结构的端口个数不相等时，如果还用传 统调度算法的话，就会造成资源浪费，并且无法满足系统容量要求。本文在研究 交叉开关结构和输入排队调度算法的基础上，针对上述应用问题，提出了两种解 决方案：捆绑解决方案和拆分平面解决方案。通过理论分析和数学公式推导，提 出了改进的三级交换结构的组网方式，并且在单级c r o s s b a r 网络调度的研究成果 基础上，通过算法改进提出了适用于三级交换结构的调度算法实现方案。最后通 过在交换性能仿真平台中进行仿真，得出两种解决方案的性能曲线，经分析，两 种方案完全解决了该工程应用面临的问题，系统吞吐率达到1 0 0 。 关键词：输入排队交叉开关三级交换调度算法 i s l i p a bs t r a c t r o u t e rm u s tp r 0 v i d em o r es w i t c hb a n d w i d mt ok e e pu pw i t ht h ed e v e l o p m e n to f h l t e m e t s w i t c ha r c l l i t e c t u r ea n ds c h e d u l i n ga l g o n t h m ，a st h ec o r et e c h n o l o g yo f 硒曲 p e r f o m a l l c es w i t c ha 1 1 dr o u t e r ，t h ep c r f o m l a n c eo fw 1 1 i c hc a l la 舵c td i r e c t l yo re v e n d e t e m i n et h ep e r f o m l a l l c eo ft h er o u t i n gs w i t c 王l i n gd e v i c e s t h em r e e - s t a g es w i t c m n ga r c l l i t e c t u r e ，c o m p a r e dw i t hm e 仃a d i t i o n a ls w i t c h i n g a r c m t e c t u r e ，c a i lp r o v i d em o r cb 锄d w i d 血，f o ri t sc 印a b i l i t yo fc o 皿e c t i n gm u l t i - s m a l l s w i t c hl l i l i t t o g e t l l e r a 1 1 di t s 9 0 0 dm o d u l 撕z a t i o na 1 1 dn o n - b l o c l 【i n gc h a r a c t 耐s t i c t h e r e f o r e ，t 1 1 ea r c l l i t e c t u r ei 3u s e di i lc o m m e r c i a lc o r cr o u t e r sb r o a d l y ，龇1 dm e s c h e d u l i n ga l g o r i m mb a s e do ni n p u t q u e u e dc r o s s b a rh 嬲b e c o m ear e s e a r c hh o t p o t e v e i lm o u 曲，t h es t a l l d a r dc l o sc o 曲e c t i n go f 缸e e - s t a g es w i t c h i n ga r c h i t e c n 鹏锄dt h e c o n i e s p o n d i l l gs c h e d u l i n ga l g o 打也m ，f o rt l l e 印p l i c a t i o i 岱v a 巧疗o mp r o j e c tt 0p r o j e c t ( w i lt l l ep r o je c t s ) ，c a nn o tb eu s e di i la 百v e i lp r o j e c td 沁c t l y ，a n di ti n u s tb ei i n p r o v e d t 0o b t 抽ag o o ds w i t c l l i n gp e r f b 功 1 a n c e t h e 仃a d i t i o n a ls c h e d u l i n ga l g o n t l l mi sd e s i g n e dt om a t c ht 1 1 ei 1 1 p u tp o r ta n do u t p u t p o r to fm es w i t c hf a b r i c ，t 1 1 e r e b yt 0m a k et h ec o m e c t i o n 丘o mi 1 1 p u tm o d u l et oo u t p u t m o d u l e b u t 血i si sb a s e do nt h a tm en u i 】曲e ro f o u t p u tm o d u l e si se q u a lt 0t h a to f t h e o u t p u tp o r to fs w i t c hf i a b r i c ，a n dw h e l lt l l ep r e c o n d i t i o ni sr 1 0 te x i s t ，t h e r em a yb ea r e s o u r c ew a s t ea i l dar e d u c e o ft l l e s y s t e mc a p a c i t yi fm e 伽i t i o n a ls c h e d u l i n g a l g o r i t h mi su s e da su s u a l t w os 0 1 u t i o n st 0t h ep r o b l e ma r ep r o p o s e d ：p o r t g r o u p i n g s c h e m ea n dm u l t i - p l a l l es c h 锄e ，b a s e do n 廿l er e s e a r c hi n t on a d i t i o n a lc s s b a rf 如r i c a 1 1 d i i l p u t q u e u e ds c h e d u l i n ga l g o r i t h m 1 、叩i r n p r 0 v e dn e t w o r ka r c l l i t e c n l r e sa r e p r o p o s e d ，t h r o u 曲t h e o r e t i c a la n a l y s i s 锄dm a m 锄a t i c a lf o m u l ad 鲥v a t i o n ，a n dw e a l s op r e s e n tt 、oi i n p r o v e ds c h e d u l i n ga l g o 五t l l i l l sw m c ha r ea p p l i c a b l er e s p e c t i v e l yt o t 1 1 en e 似r o r ka r c l l i t e c t u r e s p r o p o s e d a t1 a s t ，s i m u l a t i o ni s u s e dt oe v a l u a t em e p e r f b 衄a 1 1 c eo ft l l es c h e m e ，t h er e s u l ts h o wt l l a tm et w os c h e m e sa r ea b s o l u t e l ys o l v e m e p r o b l e 锄【lr e s p e c t i v e l y ；a n dp r o v i d ea10 0 一t h r o u g h p u t k e y w o r d ：i n p u tq u e u i n g c r o s s b a r t h r e e s t a g es w i t c h i n g s c h e d u i i n ga l g o r i t h m i s l i p 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人 在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究 成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的 说明并表示了谢意。 申请学位论 本人签名： 不实之处，本人承担一切的法律责任。 日期剑：三：! 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 蒜霎鹫张黼适篇鍪生生 导师签名：= 端日期j 且烨 第一章绪论 第一章绪论 随着因特网朝着高速化、宽带化的日益发展，人们对核心路由器的处理能力、 交换容量、吞吐率等性能提出了越来越高的要求：路由器一方面要求支持越来越 高的链路速率，另一方面还要提供一定的服务质量保证。而交换结构及调度算法 是限制路由器性能的关键因素，对交换结构和调度算法的研究一直是网络领域的 研究热点。 1 1 研究背景 自从1 9 5 6 年第一个计算机网络建立以来，网络技术得到了迅猛的发展。各种 通信网络，如用于数据传输的分组交换网络( p s d n ) 、用于话音通信的公共业务 电信网络( p s t n ) ，综合数字业务网( i s d n ) 、陆地和卫星移动通信网络等，使人 们的生活方式和工作方式发生了巨大的变化。 作为高性能交换网络的重中之重，路由交换设备必须适应信息容量的急剧膨 胀和网络业务的多样化需求。当前，高性能的大容量路由器和交换机所用核心交 换技术都可以归结为交换结构( s 埘t c hf a b r i c ) 和调度算法( s c h e d u l e 灿g o r i t h m ) 两个方面。交换结构是宽带d 路由器中的关键部分，是解决高速报文转发的主要 方式，它的性能直接决定了路由器的性能。路由器的调度是按照一定的规则对交 换节点的不同业务进行缓存、调度和服务，同时实现流量的管理与控制、冲突处 理、带宽的分配与管理等功能。 虽然交换结构和调度算法一直是网络领域的研究热点，并且许多成果己经在 当前商用路由交换设备中得到广泛应用，但是随着互联网高速化和宽带化步伐的 加速以及各种新型应用的兴起，现有技术面临着严峻的挑战，传统的路由调度方 案主要面临以下问题： ( 1 ) 商用存储器的随机访问速率限制了部分传统调度结构的应用。 随着传输技术的飞速发展，路由器尤其是核心路由器的线路接口速率越来越 高。当高速路由器的端口速率大于o c l 9 2 ( 1 9 g b p s ) 达到o c 7 6 8 ( 4 0 g b p s ) 甚至 o c 3 0 7 2 ( 1 6 0 g b p s ) 时，路由器几乎不可能对分组包进行缓存【。而部分传统调度 结构如输出排队和集中共享存储器结构，其理论上存储器的访问速率要求至少是n 倍于线路速率甚至是2 n 倍于线路速率( 对于n x n 的交换结构) 1 2 j ，因此高速路 由器限制了此类传统调度结构的直接使用。 ( 2 ) 部分传统调度算法的实现速度使其在高速路由器中的应用受到限制。 路由器端口速率的提高，不仅使商用存储器的访问速度成为高速路由器的瓶 2 基于交叉开关的可扩展交换结构及其调度算法研究 颈，同时还要求调度算法易于高速实现。因为对于一定长度包的调度，当路由器 的端口速率提高n 倍时，可用于调度包的时间就会缩减为提高前的1 n ，这样使 得原本实现时间充裕的调度算法在高速情况下可能无法完成对包的调度p j 。如已提 出的一些基于最大权重匹配考虑的调度算法，在t 比特路由器中通常很难实现【4 】。 ( 3 ) 部分成熟商用调度算法在一些应用场景下效率较低或者其性能根本无法 支持该种特殊的应用场景。 目前，虽然各种研究文献中提到了多种调度算法【5 。，但是实际商用的并不多 甚至很少；另一方面，一些在商用路由器中应用较广泛的调度算法成熟度较高， 并且性能好。在面临一些新的应用场景时，考虑到a s i c 芯片对半导体工艺的依赖、 以及调度算法用硬件实现的风险等问题，路由器生产厂商不愿意冒风险使用一个 与该应用场景配合度较好的但是未商用化的调度算法，而是希望通过实施某种方 案，使得某种商用化程度较高的调度算法能够满足给定应用场景的要求。 对于高性能路由器的设计，上述问题变得更为严重，现有成熟的商用调度算 法在某些应用场景下几乎不能实现高性能路由器对调度的要求。为了更好的支持 当前互联网的各种应用需求，需要对传统调度方案进行改进或提出新的调度策略。 1 2 研究现状 1 2 1 交叉开关型结构及其调度算法 1 ) 交叉开关型( c r o s s b a rs w i t c h ) 交换结构 交换结构是宽带口路由器的关键部分，它的性能直接决定了路由器的性能。 传统的交换结构包括总线型和共享存储器型。从高端交换机、高端路由器的发展 来看，共出现了4 种交换网络形式：总线交换、环形交换、共享内存交换和c r o s s b a r 交换。其中，前三种早期的数据交换方式都是某种程度上的共享带宽：总线交换 共享背板总线带宽( 不能避免内部冲列1 3 】) ，环形交换共享环形总线带宽，共享内 存交换共享r a m 带宽。而交叉开关交换结构( c r o s s b a rs w i t c h ) 完全突破了这种限 制，该结构采用了一种矩阵结构实现了无阻塞交换。交叉开关型交换结构如图1 1 所示，线路卡实现m a c 层的功能，将系统连接到外部链路。s w i t c hf a b r i c 为交换 网芯片，c r o s s b a rs w i t c h 为交换结构，s c h e d u l e 以讪i t e r 为调度器仲裁器( 在交叉 开关型交换网中，用于做转发判决、配置c r o s s b a r 矩阵打开或者关闭的控制器称 作调度器或者仲裁器，在此背景下，调度器与仲裁器两者概念一致。) ，它作为控 制逻辑，控制交叉开关的打开或者关闭，从而实现输入到输出的连接。 第一章绪论 图1 1 交叉开关型( c r o s s b 甜s w i t c h ) 交换结构 c r o s s b a r 交换网络在数据平面没有任何瓶颈，可以支持高带宽，其原因主要是： c r o s s b a r 引入了交换矩阵这种新的交换方式，摒弃了共享带宽的交换方式，在数据 交换方式上是一种革命性的变化。它采用硬件的交叉开关式的互连网络实现交换。 交换控制主要由交叉开关和控制逻辑实现，交叉开关负责提供从源端口到相应目 的端口信息交换的物理链接，而控制逻辑则用以控制这些物理链接的建立和拆除。 所以c r o s s b a r 交换结构是宽带路由器、交换机中的一个核心部分，保持它的高效 率非常重要。 c r o s s b a r 交换网的扩展能力非常强，交换容量可以做的很大，基本不受硬件条 件限制，目前单颗芯片交换容量在2 5 6 g 7 0 0 g 之间，多颗芯片可以构建t 级乃至 几t 容量的大型交换网络，足以满足当前和未来几年网络对交换容量的需求，并 且随着硬件集成技术的进步，单颗c r o s s b a r 芯片支持的容量会更大。 目前思科、e x t r e m e 、网捷网络、港湾网络等厂商都推出了基于c r o s s b a u r 的核 心交换机产品，但市场上也有很多内部仍然采用千兆端口互联的产品，主要是面 向对性能要求一般、对价格比较敏感的用户群体。 交叉开关结构可以实现无阻塞的交换，因为在该结构内部可以同时并行实现 多路数据的输入输出。但是，由于同一时隙可能有多个输入要求去往同一输出， 而一个输出一次只能连接一个输入，因此输出冲突不可避免。为了解决这种冲突， 就必须在交换结构之前( 即交换结构的输入端) 对信元进行缓存。即在交差开关 型交换网络中，必须采用输入排队( i n p u tq u e u i n g ) 机制。 输入排队机制是指，信元在交换网( s w i t c hf a b r i c ) ( 采用交叉开关结构实现) 4基于交叉开关的可扩展交换结构及其调度算法研究 的输入端排队，等待交换网“同意 其通过后再进入交换网进行交换，最后通过 交换网输出到下一级。即信元在进入交换网之前，先进行缓存，并向交换网提出 交换请求，待交换网批准后再通过交换网输出。 图1 2 给出了输入排队交换结构模型，在交换网的每个输入模块设置一个f o 队列对信元排队，每次只有队头的信元能够被调度出队，并且同一个时隙，一个 输出至多只能选择一个输入：如果队头信元被阻塞，那么排在后面的信元即使与 队头信元的目的模块不同，也仍然没法被调度出队，即出现h o l 阻塞( h e a do f l i n e b l o c l ( i n g 队头阻塞) ，从而使系统性能明显下降。 s i n g i ef i f o s i n g i ef i f o 图1 2 输入排队交换结构模型 输入排队的主要优点在于，对交换网的速度要求不高，交换网可以根据输出 模块数确定一定的速率来进行信元交换；但是缺点也比较突出，就是存在队头阻 塞，严重影响了交换系统的性能。 对于用硬件实现的交换网络而言，人们更关注的是将要使用的交换结构对于 硬件的要求是否容易满足，显然，输入排队是一种其硬件实现要求较易满足的交 换结构。 输出排队机制对硬件速率要求太高，如果要在既定的技术下实现最高的数据 传输速率，只能考虑用输入排队交换( i n p u t q u e u e ds w i t c h ) ，同时解决h o l 阻塞 问题【9 1 。 v o q ( r t u a lo u t p u tq u e u i n g ，虚拟输出排队) 解决了h o l 阻塞，即在输入模块 按照信元要去的目的输出模块的不同，对信元分别进行排队。以下给出h o l 阻塞 的解决方法： 在每个输入模块，不再只用一个f o 来对信元排队，而是每个输入模块都对 每个输出模块维护一个独立的队列( 即v o q 的概念) ；这样，在一个输入模块内 部，同一个v o q 队列中的信元都是去往同一个目的输出模块的，于是一个信元就 不会被同一队列中排在它前面的与它目的输出模块不同的信元所阻塞。在输入排 队中引入v o q 概念后，输入排队交换的结构模型成为图1 3 所示： 第一章绪论 v o q _ o l v o q n i i n p u tn v o q - 0 i i | v o q n li 图1 3 引入v o q 概念后的输入排队交换结构模型 用上述v o q 方法解决输入排队的队头阻塞，虽然有点复杂，要求每个输入缓 存维护n 个( n 为输出模块个数) f o ；但是相比输出排队交换而言，没有额外 的加速要求( 输出排队对交换网的交换速度要求较高) ：平均来看，一个信元最多 会在一个信元时隙到达并离开每个输入。 2 ) 输入排队交叉开关型交换结构的调度算法 交叉开关型交换结构能够达到比较高的速率并且扩展性好，已经被广泛地用 在高速路由器、交换机中。但是c r o s s b a rs 谢t c h 的速度需要完善的调度算法并用 。高速硬件实现调度器( s c h e d u l e ) 来实现。执行高效调度算法的调度器是c r o s s b a r 交换结构的核心，它在每个调度时隙内收集各输入端口有关数据包队列的信息， 经过相关调度算法得到输入端口和输出端口之间的一个匹配，提供输入端口到输 出端口的通路。 目前，适用于输入排队交叉开关型交换网络的典型调度算法包括以下几类： a 、最大尺寸匹配算法( m a ) 【i m 啪s i z em a t c l l i n g ) 这类算法的目的是寻找边数最多的匹配，可以直接利用图论里的二分图m s m 算法( 最大匹配算法) 来解决调度中的匹配问题，目前己知的渐近复杂性最好的 算法，其时间复杂度为d 烈2 5 ) 【5 1 。仿真实验表吲6 1 ，最大尺寸匹配算法可以在均匀 贝努利独立同分布( u 血f o mb e m o u l l “i d ) 的通信量模型下达到1 0 0 吞吐率。但是 这类算法也具有以下缺点：在容许的非均匀流量下，可能导致不稳定和不公平； 在非容许的流量下，可能导致饿死情况的发生；算法的复杂度较高并且不利 于硬件实现。所以最大尺寸匹配算法的实用性较差，人们转而研究具有实际意义 的极大匹配型算法。 b 、极大匹配算法 极大匹配是指此匹配不会真包含在任何一个匹配中，即无法通过简单的增加 边来扩大匹配，除非换掉已有的边。在实际应用中，一般用启发式算法来解决二 6基于交叉开关的可扩展交换结构及其调度算法研究 分图的匹配问题。这些算法具有实现简单、运算速度快等优点，但只能实现极大 匹配。 各种类型的极大匹配算法包括：p ( p a r a l l e li n t e r a t i v em a t c m n g ) 算法、砌之m ( r o 衄dr o b i nm a t c l l i n g ) 算法、i s l d 算法、f 刚m ( f c f si 1 1r o u n d r o b i nm a t c h i n g ) 算法等。其中，f 洲算法解决了i s l 口算法的不公平性问题。f 瓜m 对i s l d 中 应答指针的更新规则进行了改进：如果应答信号没被接受，应答指针不是不变， 而是指向没认可应答信号的输入端口。通过指针更新方式的改进，f w 比i s l d 具有更大的公平性和服务保障。尽管如此，由于i s l 口算法的成熟度较高、且商用 化程度也很高，所以本文的解决方案中仍然采用了i s l p 算法。 p m 、i s l 口和f m m 等算法通过多次迭代实现对m s m 算法的近似，因此具 有和m s m 算法类似的性能，如在容许的通信量模型下、在加速比为2 的支持下都 可以达到1 0 0 的吞吐率【7 】【8 】。 c 、最大权重匹配算法( m a ) 【i m 啪w 西曲tm a t c 蛐唱) 最大权重匹配是对最大尺寸型匹配( m s m ) 的扩展，每一条边都有一权重与之 对应，通常以v o q 的长度或者信元的排队时间作为权重。对于一个n n 的交换 机来说，共有n ! 个匹配( 每一匹配对应一个排列) ，m 礓d 算法是从所有n ! 个匹配 中选取具有最大权重的匹配，如果有多个这样的匹配，则任选其一。目前，解决 这类问题的算法的渐进复杂度是o ( n 3 ) 。 m c k e o w l l 在1 9 9 5 提出了l q f ( l o n g e s tq u e u ef i r s t ) 与o c f ( o l d e s tc e u f i r s t ) 两种最大权重匹配的算法【9 】，这两种算法的不同在于边的权重定义不同。理论证明， 在信元独立到达模式下，这两种算法都能达到1 0 0 的吞吐率，并且发现l q f 算 法有可能导致长度较小的队列饿死，而o c f 则可以避免该情况的发生，但是却会 带来较长的延时。此外，通过改变权重函数的定义，m e k l ( i t t i k u l 在1 9 9 8 年提出了 l p f ( l 0 n g e s tp o r tf i r s t ) 算、法【1 0 】，它的权重定义为端口占有。与l q f 相比，l p f 算法在硬件实现上稍易于l q f 算法。 d 、极大权重匹配算法 最大权重匹配型算法在硬件实现上相当复杂，并且算法的时间复杂度太高， 为了改善这两种情况，m c k e o w n 于1 9 9 5 年提出了两种启发式算法：i l q f 和 i o c f p j 。这两种算法采用基于p m 的多次迭代的方法。此外，m a u r s a i l 于1 9 9 9 年 提出了) a ( r e s e r v a t i o nw i m p r e e m p t i o na 1 1 da c l ( 1 1 0 w l e d g e m e n t ) 算法，它是一种 基于预留向量的启发式算法【1 1 】。m a r s a l l 于2 0 0 1 年指出，对最大权重匹配算法性能 影响最大的是如何计算权重，而对算法复杂度影响最大的是实现匹配的启发式算 法【】。下面是几种极大权重匹配算法的比较【1 9 】： 第一章绪论 表1 1 极大权重匹配算法比较 a l g o r i t i nw e i 曲tm a t c l l i n gm e m o dc o m p l e x 时 i l q fq u e u es i z e i t e r a t i v em a t c h i i l g d ( 21 0 9 2 ) i o c f c e l l a g e i t e r a t i v em a t c l l i l l g d ( 2l 0 9 2 ) i l p fp o r to c c u p 锄c y p r e o r d e r i n ga n da r b i 仃a t i o nd ( 2 ) 腓 p o r ts i z er e s e r v a t i o nv e c t o r d ( 2 ) 上表分别从算法权重的定义、匹配方法、和复杂度等三个方面，针对几种常 见的极大权重匹配算法：i l q f 、i o c f 、i l p f 和砌) a 进行了比较。其中，从权重 定义来区分，三种算法分别采用：队列长度、信元年龄、端口占有和端口大小； 从匹配方法区分，三种算法分别采用：迭代匹配、迭代匹配、基于预排序和仲裁 的匹配、以及基于预留向量的匹配。 1 2 2 三级交换结构及其调度算法 对于n n 的单级交叉开关型交换结构来说，共有2 个交叉点( c r o s s - p o i n t ) ， 随着交换规模的增大，交叉点的个数呈平方级增长，所以单级交叉开关型交换结 构不适合构建端口数较多的大型交换结构。而三级c l o s 交换结构可以将多个小型 的交换单元( 例如c r o s s b a r ) 互联在一起，具有良好的模块化及非阻塞特性，并且 可以有效减少交换单元的个数，所以该交换结构比较适合构建大容量的交换机。 目前有两种三级c 1 0 s 交换结构，三级c 1 0 s 无缓冲区的交换结构和三级c l o s 有缓 冲区的交换结构，本文重点研究后者，下文中提到的三级交换结构都是指三级c 1 0 s 有缓冲区的交换结构。 如图1 4 所示，文献【2 0 】提出的交换结构将缓冲区分别设置在输入交换模块与输 出交换模块，中心交换模块采用了多个无缓冲区的交叉开关型交换结构，所以该【2 0 】 交换结构为m 锄。驴s p a c e m e m o r y 三级( t l l r e e s t a g e ) 交换结构。该交换结构包括 以下几部分：l 个带缓冲区的输入交换模块( i n p u tm o d u l e ，简称蹦s ) ；k 个 中心交换模块c r o s s b a r ( f a b r i cm o d u l e s ，简称f m s ) ；l 个输出交换模块( o u 印u t m o d u l e s ，简称o m s ) 。其中每一个输入模块包括n 个输入端口与k 个输出端口( 分 别与各个中心交换模块相连) ；每个中心交换模块包括l 个输入端口与l 个输出端 口；每个输出模块包括k 个输入端口( 分别与每个中心交换模块相连) 及n 个输 出端口。 实际上，可以把中心交换模块看作是路由资源，因为到达第一级交换结构的 信元，必须选择合适的中心交换模块才能到达目的输出端口。于是三级交换结构 下的调度包括以下两部分：输入端口与目的输出端口的匹配；路由的分配。 8 基于交叉开关的可扩展交换结构及其调度算法研究 由于硬件设计上的原因，输出端口的缓冲区容量相对较小，为了提高其可扩 展性，三级交换结构采取了将大容量的缓冲区设置在输入端口处，如果输出端口 的缓冲区长度超过了一定的阈值( t l i r e s h 0 1 d ) ，为了防止输出缓冲区溢出，则发送 “反压”( s e l e c t i v eb a u c l c p r e s s u r e 【2 1j ) 信息通知相应的输入端口调整其调度策略来避 免拥塞。此外，由于每个输入模块都有多个输入端口，在一个时隙内，输入模块 的缓冲区需要支持多次存取，则随着线速率的提高，对输入缓冲区的带宽要求也 就越来越高，所以该交换结构的可扩展性会有较大的限制。 图1 4 有缓冲区的三级交换结构 文献 2 0 提出了该交换结构下的一种调度算法i m ( m d o md i s p a t c l l i n g ) ，该算 法主要包括以下几个步骤：每个输入模块根据输入队列的状态，最多生成k 个 请求( 每个请求对应一个中心交换模块的交叉开关型交换结构) 。为了减少输入模 块之间的同步( 即同时都向同一个中心交换模块发请求) ，请求的生成是随机的。 中心交换模块的交叉开关型交换结构根据s e l e c t i v e b a c k p r e s s u r e 消息，将对应于 目的输出端口缓冲区己发生拥塞的请求删除掉。为了保持公平性，在剩余的有冲 突的请求( 指发往相同的输出模块) 中，根据轮转指针选中一个请求。最后，中 心交换模块将授权信息( 目a 1 1 t ) 发送到各个输入模块。输入模块根据授权信息， 将信元发往相应的中心交换模块的交叉开关型交换结构，最后到达目的输出端口 缓冲区。 有缓冲区的三级交换结构由于具有良好的模块化及非阻塞的特性，所以该结 构在提高交换容量的可扩展性方面具有优势。与单级交换结构相比，三级交换结 构不仅包括端口的匹配而且还包括路由的分配，从而增加了调度算法设计的难度。 此外，多级复杂的交换结构给算法性能的分析带来了较大的困难，服务质量保证 方面( 延迟、抖动等) 也缺乏全面而深入的研究。 第一章绪论 9 1 3 本文主要工作 本文基于交叉开关交换结构，重点研究了三级c 1 0 s 有缓冲区的交换结构在特 定应用场景下i s l p 调度算法存在的问题，提出了新的实现方案，并通过构建专门 的调度性能评价系统，将该调度算法应用在一个模拟真实交换系统的仿真环境中， 对新算法的性能进行了仿真验证和性能分析。本文的特点如下：不是从理论角 度来分析，而是重点从工程应用的角度出发来研究；不单纯介绍调度算法，而 是从整个交换网络的角度出发，研究具体工程应用场景，针对该具体工程应用， 提出改进的交换网组网方式以及适用于该交换结构的调度算法。以下具体说明本 文的主要研究工作： 首先提出本文的研究背景：由于工程应用千差万别，标准三级交换结构的c 1 0 s 连接及相应的调度算法，不能直接应用于具体工程中，必须对其进行扩展改进才 能得到较好的交换性能。传统的调度算法是针对交换结构的输入输出端口进行匹 配，从而建立各输入模块和输出模块之间的连接，但这是以输出模块个数与交换 结构的输出端口个数相等为基础的。当输出模块的个数与交换结构的输出端口个 数不相等时，如果还用传统调度算法的话，就会造成资源浪费，并且无法满足系 统容量要求，传统的调度算法不再适用。 本文在研究交叉开关结构和输入排队调度算法的基础上，针对上述应用问题， 通过对传统三级交换结构进行改进，分别提出了两种具有良好可扩展性的三级交 换结构的组网方式，并且在单级c r o s s b a r 网络调度算法的研究成果基础上，通过 算法改进提出了适用于该三级交换结构的调度方案，最终通过对上述交换结构和 调度算法进行有机整合，提出了两套整体解决方案：捆绑解决方案和拆分平面解 决方案。本文针对两种方案所作的具体研究工作包括以下几个方面： 首先，通过在交换性能仿真平台中进行仿真，得出两种解决方案的性能曲线， 仿真结果表明两种方案完全解决了该工程应用面临的问题，表现出良好的系统吞 吐率和时延特性。 其次，本文结合仿真结果，分别针对两种解决方案在不同交换容量下的时延 特性进行了研究。在低负载条件下，系统容量大小对于两种方案的性能影响并不 大。在高负载条件下，对于捆绑方案，随着捆绑个数增大系统性能急剧变差；对 于拆分平面方案，随着拆分平面个数增多系统性能反而变好。针对两种方案的以 上性能表现，本文通过理论分析，说明了该性能产生的原因。 最后，本文还比较了两种方案在不同负载下的时延特性。在低负载下，虽然 两种方案的平均时延有所差异( 捆绑方案的平均时延略小于拆分平面方案的) ，但 1 0 基于交叉开关的可扩展交换结构及其调度算法研究 是整体而言，两种方案的平均时延都比较小；随着负载增大，当负载大于约9 0 时，两种方案表现出与低负载下不同的性能相对关系，拆分平面方案的信元平均 时延明显小于捆绑方案的。针对两种方案这种随负载变化而性能相对关系发生变 化的现象，本文经过对比分析，发现该现象源于两种方案对原始请求矩阵的不同 处理。这种不同处理会导致：随着负载的变化，中间交换结构的各个输入端口对 不同输出端口的竞争关系也发生变化，从而引起了上述现象的发生。 综上，本文从实际工程应用的角度出发，在对传统三级交换结构和调度算法 分析研究的基础上，运用理论分析和数学公式推导相结合的方法，提出两种改进 的三级交换结构组网方式以及适用于该结构的调度算法，并通过对两种组网方式 和调度算法进行有机整合提出两套交换网整体解决方案。仿真结果证明，该方案 具有良好的可扩展性和实用性。 本文研究的不足在于，在已经得到两种解决方案的性能相对关系的基础上， 只分析了两者之间的性能差异的原因，而没有再做进一步的研究，比如提出一种 融合两种方案的优点为一体的方案。 下一步研究工作可以基于上述两种方案在不同负载下的性能相对关系的变化 展开，分析两种方案在不同负载下各自的优缺点，本着充分发挥不同负载下两种 解决方案捆绑方案和拆分平面方案各自优点的原则，取长补短，设计出 一种捆绑和拆分平面相结合的方案。由于时间有限，本文没有再针对该设想进行 研究。 1 4 论文结构安排 根据本文的主要工作，安排文章结构如下： 第一章：绪论部分，分析交换网学科背景，比较各类交换结构和排队机制， 分析其优点和缺点：重点分析了交叉开关型交换网络采用的交换结构、排队机制 以及相应的几类输入排队调度算法的优势与不足；并在此基础上，分析了本文的 研究重点三级交换结构及其调度算法。 第二章：分析了p 蹦、删、s l p 以及多次迭代的i s l 口算法等几种典型的 交叉开关输入排队调度算法，分别针对各算法讨论了其实现机制以及算法性能。 第三章：通过对交换系统建立统一的模型，采用系统级设计方法和面向对象 技术设计实现了交换系统仿真平台。 第四章：针对具体工程应用，提出两种改进的三级交换结构捆绑结构和 拆分平面结构，并分别针对两种交换结构在i s l 口算法的基础上提出了改进的调度 算法，综合以上交换结构和调度算法，提出两套完整的交换网解决方案。并结合 第一章绪论 性能仿真结果分别对两种方案的性能进行了分析。 第五章：对本课题的工作和内容进行了总结，提出了论文的不足和下一步的 工作计划。 第二章输入排队交换结构调度算法 第二章输入排队交换结构调度算法 在上一章中，列举了输入排队交换结构的几种类型的调度算法，本章重点介 绍其中的几种典型的极大匹配类型的调度算法，并着重介绍种商用化程度很高 的调度算法一s l 邛。 基本调度机制包括：随机选择( r a l l d o ms e l e c t i n g ) 、先进先出和轮询 ( r o u n d r o b i l l ) 。 2 1 1p 算法 2 1 并行迭代匹配算法( p i m ) 并行迭代匹配算法p 刀m ( p a r a l l e li t e r a t i v em a t c 蛐唱) 【2 2 】由d e c 系统研究开发 中心开发，用于1 6 端口，1 g b s 的a n 2 交换系统。由于本章后面介绍的几种极大 匹配调度算法都是基于p m 算法发展起来的。因此先对它进行描述及性能分析。 p 蹦是第一个采用多次迭代实现输入排队调度的算法。它利用随机的方法选 择请求或响应信号，从而避免端口饿死( 端口闲置) ，并减少算法收敛所需的迭代 次数。p 蹦通过多次迭代来使算法快速收敛，从而得到输入输出端口间的无冲突 的匹配，其中每次迭代包括三步。所有的输入输出端口初始化为不匹配，只有在 一次迭代中未匹配的输入输出端口才有资格在下一次迭代中进行匹配。 每次迭代分如下三步，每次迭代的这三步之间是并行进行的： 第一步请求( r e q u e s t ) ：每一未匹配的输入端口向存在信元的所有v o q 队 列对应的输出端口发送请求( r e q u e s t ) ) 信息。 第二步许可( g r a n t ) ：如果未匹配的输出端口接收到请求，则随机地选择一 个请求进行许可操作，每个请求信号被选择的概率相同。 第三步接受( a c c 印t ) ：如果输入端口接收到许可信号，则它在所有许可了 该输入端口的输出端口中随机地选择一个进行接受操作。 图2 1 和图2 2 为给出了上述三个步骤的一个实例。 如图2 1 ，“l ( i ，j ) = m 表示输入端口i 的v o q j ( 对应输出端口j ) 队列中 有m 个信元；输入端口i 向输出端口j 提了请求。 1 4基于交叉开关的可扩展交换结构及其调度算法研究 i n p u t 4 l 乎4 3 图2 1p 算法迭代三步骤第一步请求( r e q u e s t ) 如图2 2 ，在本例中，许可( g r a n t ) 过程中，输入端口1 、3 都向输出端口2 提了请求，输出端口2 随机选择许可了输入端口3 的请求；同样的，输出端口4 随机地选择许可了输入端口3 的请求；在接受( a c c 印t ) 过程，输入端口3 随机地 在两个许可中，选择了输出端口2 的许可。在这一轮迭代结束时，建立了c ( 1 ，1 ) 和c ( 3 ，2 ) 两个连接( c ( i ，j ) 表示建立了输入端口i 到输出端口j 的连接c o 皿e c t i o n 。 i n p u to u t p u ti n p u t0 u t p u t 2 3 p i m 算法迭代三步骤一一第二步许可( g r a n t )p i m 算法迭代三步骤一一第三步接受( a c c e p t ) 2 1 2p m 算法性能 图2 2p 算法迭代三步骤第二步第三步 图2 1 和图2 2 举例说明了p m 调度算法一次迭代过程的三个步骤。在本例中， 第一次迭代虽然没有匹配输入端口4 和输出端口4 ，但是第一次迭代的结果起码没 有建立彼此冲突的连接。并且在第二次迭代中建立了输入端口4 和输出端口4 之 间的连接( 图2 2 中的灰色连接) 。 在第二步中，各个独立的输出端口各自从竞争的请求中随机地选择一个请求。 这有三种影响：第一，每一次迭代平均至少匹配3 4 的未匹配端口：第二，可以保 证所有请求最终会被许可。因此，不会出现某些输入端口饿死的情况。：第三，不 必保存过去建立的连接。在每个信元时隙的开始，匹配都重新独立地开始进行， 第二章输入排队交换结构调度算法 1 5 而不必考虑上一个时隙的匹配结果。这使得算法容易理解，并且使算法分析比较 直观。 但是使用随机也有一些问题。第一，在高速硬件中实现随机很困难且代价很 高：每个调度器必须在变化的集合中做随机的选择。第二，在非容许的流量下， 随机会导致连接间的不公平。有一种不公平的极限情况，对于一个2 2 的交换， 在不容许( i n a 血1 i s s i b l e ) 的负载下，p m 算法以及其他一些算法在容许的流量下 也会不公平。第三，单次迭代的p 蹦算法性能并不好：吞吐率仅为6 3 ，仅略高 于f o 输入排队。这是由于，某个输入不会被许可的概率为( ( 一1 ) ) ，因此 随着n 的增大，吞吐率趋于1 1 店6 3 。尽管如此，经过多次迭代，算法仍然会 收敛并得到很好的匹配结果，收敛的时间会影响交换机工作的速率。 2 2 1 删算法 2 2i u 蝴调度算法 删( b