（计算机应用技术专业论文）重端口交换结构及其调度算法.pdf

摘要 摘要 交换结构是分组交换机，路由器的核心部件，直接决定了交换机路由器的性能。典型的交换 结构有输出队列结构和输人队列结拇。输出队列结构由于需要缓存工作于n 倍的线路速率，可 扩展性差。输入队列结构由于存在转发冲突，需要复杂的调度算法来配置交换阵列。导致这两种 结构均不能胜任高性能交换的应用。目前，在高性能交换结构的设计领域，如何在交换结构的可 扩展性、性能和调度复杂性三者间进行折中仍是有待解决的的富有挑战性的课题。 针对这一问题，本文设计了重端口交换结构，该交换结构利用空分并行思想有效降低了对缓 存工作速率的需求。通过对重端口交换结构与输出队列结构的行为等价性和各种调度算法下的稳 定性判据的研究，论证了该结构的合理性与有效性。为了使重端口交换结构更趋于实用，本文进 一步研究了重端口交换结构的低复杂度并行调度算法。为此本文首先给出了一个分组延迟分析的 模型，并在此基础上设计能提供时延保证的r o u n d - r o b i n 调度算法。其次，本文将差分技术引入 r o u n d r o b i n 调度算法中，设计了只需一步迭代的调度算法i s l o t 。最后本文通过详尽的仿真比 较了各种极大匹配调度算法和i s l o t 算法在重端口结构下的性能。 文中的理论分析和仿真结果均显示重端口交换结构在可扩展性、性能和调度算法复杂性三个 方面基本能满足高性能交换的需求。 关键词分组交换交换结构输入队列输出队列调度算法二分图匹配稳定性转发时延 分类号t p 3 9 3 a b s “a c l a b s t r a c t t h es w t c h i n gf a b r i ci s 也ec e n 删p a no fs w i t c h e so rr o u t e r s ，w h c hd e t e m l i n e st h ep e r f b m l a n c e o fs w i t c h e so rr o u t e r so u t p u t q u e u p i n ga n di n p u t q u e u e i n ga r et w ot y p i c a ls w i t c h i n gf a b r i c sw h i c h a r ew j d e l yu s e di ns w i t c h e so rr o u t e r s h o w e v e lt h es c a l a b i l j t yb fo u t p u t q u e u e i n gi sp 0 0 rf o ri t s b u 丘b r sm u s tw o r ka tt h er a t ent i m e st 1 1 a nt h el i n er a t e a s s a c l a b l ei si n p u t q u e u e i n 岛t h e r ei sa c o m p l e xs c h e d u l e rn e e d e df o rr e s o l v i n gt h es w i t c l l i n gc o n t e n t i o no fi n p u t - q u e u e i n g a sar e s u l t n e i t h e ro u t p u t q u e u e i n gn o rj n p u t - q u e u e i n gi sf i tf o rh i g h _ p e r f b r n l a n c es w i t c h i n g s o ，h o wt om a k ea t r a d e o f fa l n o ”gt h es c a l a b j l i 吼p e r f b r h l a l l c ea 1 1 dc o m p l e x i t yo fs c h e d u l e ri sac h a l l e n g i n gp r o b l e mi n t h ed e s i g no f h i g h - p e r f o m a n c es w i t c h e s i n t h i sp 印e la nn o v e ls w i t c h i n gf 曲r i c ，n a r n e dd u p l i c a t e dp o r t ss w i t c h i n gf a b r c ( d p s ) ，i s p r o p o s e d l tu i t i l i z e st h es p a c em u l t i p l e x i n gt e c h n i q u et ol o w e rd o w nt h eb u 行b r sw o r k i n gr a t e i t s v a l j d l 时a n dr a t i o n a l i t yi sv e n e db yt h ep r o o fo fm es t a b l er e s u l t sa n di d e n t i c a lb e h 删i o r b e t 、v e e n d p sa n do qt h e 印p l i e da l g o 订t h m sf o rd p ss c h e d u l e ra r ea l s oi n v e s t i g a t e di nt h ep 印e lf i r s t l ma q u e u e i n gm o d e lf o rp a c k e td e l a ya 1 1 a l y s i si sp r e s e n t e d 1 1 w od e l a y g u a r 蛐t e e ds c h e d u l i n ga l g o r i t h m sa r e p m p o s e d 卸dt h e i rd e l a yb o u 力d e d n e s sj sg i v e nu s j n gt h eq u e u e i n gm o d e l t h 吣j s l o ta 】g o r ；t h mj s d e s j g n e dw h j c hc o m b i n e sm er o u n d r o b i na n dd i 行b r e n t i a t et e c h n j q u e s a t1 a s e x h a u s t i v es i m u l a t i o n s a r em a d ef o rt h ep e r f b m l a n c ec o m p a r i s o no fk i n d so fm a x i m a lm a t c h i n ga l g o n 也m sa n di s l o ta s s c h e d u l e ro f d p s t h et h e o r e t i c a la n ds i m u l a t i o nr e s u l 乜i nt h i s p 印e r s h o wt h a td p si s c o m p e t e n t f o r h i g h p e r f 0 丌n a n c es w i t c h i n gi nt e r m so fs c a l a b i l i t y p e d b m a l l c ea n dc o m p l e x i t yo fs c h e d u l i n g a l g o r i t h m s 1 “y w o r d sp a c k e ts w i t c h i n g ；s w i t c h i n gf a b r i c ；i n p u t q u e u e i n g ；o u t p u t - q u e u e i n g ；s c h e d u l l n g a l g o t l m ；m a t c h i n go f b i p a r t i t eg r 印h ；s t a b i l i t y ；s w i t c h i n gd e l a y 插图索引 图l 1 一个简单的分组交换网络2 图1 2 路由器逻辑示意图3 图1 _ 3 输出队列结构示意图一4 图1 4 输入队列交换结构及h o l 阻塞问题5 图1 5 虚输出队列及二分图模型6 图1 6 二分图1 5 ( b ) 的两种匹配7 图1 7 二分图转换为网络流的过程1 0 图】8c i o q 交换结构示意图一1 6 图1 9c i c q 交换结构示意图1 9 图1 1 0p p s 交换结构示意图一2 0 图1 1 1 负载均衡的布科夫一冯诺依曼交换结构2 1 图2 1 榕树交换阵列2 5 图2 2 纵横制交换阵列2 5 图232 2 的d p s - 2 交换机示意图2 7 图2 4d p s 与c i o q 的能力差异示意图2 9 图25 存储器、网络链路和交换阵列的带宽发展状况示意图2 9 图2 6d p s 的一种队列组织雨匹配模型3 1 图31 d p s - d 的输入r r 分路算法3 6 图3 2 一个3 3 的d p s - 2 中的缓存状态及其服务请求的二分图3 7 幽3 3n n d p s - 2 的凋度算法3 8 图34 图3 2 状态r 的凋度算法产生的匹配及调度斤的状态3 9 幽4 1 输入端口f 的d r r 分路算法一4 6 目录 图4 21 b s i u l a s 算法4 8 国4 3 改进的t 如s i u l a s 算法4 8 图5 1 输入缓存i 分组时延问题的一个直观排队模型5 4 图52d p s ( d ，s ) 分组交换时延的排队分析模型5 4 图5 3 极大匹配调度算法不能傈证分组转发时延的原因示意一一5 6 图5 4f b r r 算法5 8 图5 5c b r r 算法6 l 图5 6v o q j 的分组到达曲线和c b r r 算法的服务曲线6 2 图6 1 算法1 采用时隙间迭代策略的r o u n d r o b i n 算法6 7 图62 算法1 与e d r r 的区别6 8 图6 3 算法l 在均匀i i d 流量下的性能一6 9 图6 4 算法1 在对角流量下的性能6 9 图6 5i s l o t 算法7 1 图6 6i s l o t 算法工作过程，7 2 图7 1 均匀i i d 流量下i s l o t 算法与其它r r 算法的队长一负荷曲线比较7 7 图7 2 突发流量下i s l o t 算法与其它r r 算法的队长一负荷曲线比较7 8 图73 弱对角流量下i s l o t 算法与其它r r 算法的队长一负荷曲线比较7 8 图7 4 对角流量下i s l o t 算法与其它r r 算法的队氏一负荷曲线比较7 9 图7 5 均匀i id 流量下i s l o t 算法与i l q f 算法的队长一负荷曲线比较7 9 图7 6 突发流量下i s l o t 算法与i l q f 算法的队长一负荷曲线比较8 0 图7 7 对角流量下i s l o t 算法与i l q f 算法的队| 圭一负荷曲线比较8 0 图7 8 弱对角流量f i s l o t 算法与其它i l q f 算法的队长一负荷曲线比较8 1 幽7 9 采_ l j 不同极人匹配算法的d p s ( 2 ，1 ) 在均匀i i d 流量r 的性能8 2 幽7 1 0 采川不同极人匹配算法的d p s ( 2 ，1 ) 在非均匀流量r 的性能8 2 图7 1 1 采用不同极大匹配算法的d p s ( 2 ，1 ) 在突发流量下的性能8 3 图7 1 2d p s ( 2 s ，s ) 在不同的参数s 下的性能比较8 4 图7 1 3 弱对角流量下d = 2 ，d s = 1 3 时采用i s l i p 和i s l o t 算法的d p s 性能比较8 5 图7 1 4 对角流量下d 2 2 ，d s = 1 3 时采用i s l i p 和i s l o t 算法d p s 性能比较8 5 图7 15 采用i s l o t 的d p s 在不同并行度下的性能比较( 对角流量) 8 6 表格索引 表1 1 三种r o u n d r o b i n 算法指针更改的区别9 表51 公式5 4 与实验结果的对照表5 7 表6 1 几类调度算法的比较6 5 表7 1 各种r r 算法在不同流量下的吞吐率 表8 1 几种能模仿o q 行为的交换结构比较 缩略词 缩略词 t d m t i m ed i v i s i o nm u l t - p l e x i n g w d m w a v ed i v j s i o nm u l t i p l e x i n g d w d m d e n s ew a v ed i v i s i o nm u l t i p l e x i n g o b s op f j c a ib u r s ts w i t c h j n g o q o u t p u t q u e u e i n g l q i n p u t - q u e u e i n g c l o q c o m b i n e di 叩u ta n do u t p u tq u e u e i n g c 】c q c o m b i n e di n p u ta n dc m s s p o i n tq u e u e i n g p p s p a r a l l e lp a c k e ts w i t c h d p s d u d l i c a t e dp o r t ss w i t c h h o l h e a do f l i n e v o q v i r t u a lo u t p u tq u e u e i n g f i f o 一f i r s t1 nf j r s to u t p i f o p u s hi nf i r s to u t q o s r ( ) u a l i t yo f s e r v i c e r r _ r o u n d r o b i n p i m p a r a l l e l i t e r a t i v em a t c h i n g d r r d u a lr o u n dr o b i n f i r m f c f si nr o u n d r o b i nm a t c h i n g m s m m a x i m u ms i z em a t c h i n g m w m m “i m u mw e i 曲t e dm a t c h i n g l q f l o n g e s tq u e u e l e n g t hf i r s t l p f l o n g e s tp o r t - 1 e n g t hf i r s t o c f o l d e s tc e l lf i r s t s s b s l o ts e l la n db u y e d d 一e a r l l e s td u et od a t e f b r r f r a r n eb a s e dr o u n dr o b j n c b r r c r e d i tb a s e dr o u n dr o b i n i s l o t i t e r a t eb e t w e e ns l o t s d t m c d i s c r e t et i m em a r k o vc h a i n j id i n d e p e n d e n ta n di d e n t i c a ld l s 仃i b u t e d s l l n s t m n gl a wo 儿a r g en u m b e r s 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 己经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 研究生签名：拯f 盗：日期：兰堕：1 2 ，占 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅 和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：缝! 鍪导师签日期：t 时，o 东南大学博士论文 1 1 研究背景 第一章引言 二十世纪九十年代以来，光通信技术得到了长足发展，尤其是随着密集波分多路复用 ( d w d m ) 技术的成熟，网络链路的速率已高达每秒t e r a b i t s ，且更高速率的通信链路业已处于实 验阶段1 1 j 。现有i p o v e r l a t m 技术的网络底层的光通信层采用电路交换，而上面的i p 层采用分 组交换”1 ，由于需要将数据经过多次复接，链路的利用率较低。因此，i p o v e r w d m 的思想 应运而生l l ”j 。i p 数据具有突发特性，为了获得高的链路利用率这就要求数据交换时要具有数据 缓存能力。然而由于目前缺乏可用的光存储器，如何高效利用光纤链路的带宽成为迫切需要解决 的问题。目前解决这一问题的思路大致有两种：一种如c q i a 0 等提出的光突发交换( o p t i c a l b u r s t s w i t c h i n g ) 。”】。o b s 将信令和数据分开，信令采用电信号处理而数据则全部采用光信号，由 信令信号为每个数据块( b u r s t ) 在其所经路径的每个交换结点上预定好数据块的服务时间，这样当 数据块到达时将无须缓存可以直接发送到光链路上去。o b s 是一种采用软状态的轻权 f | l g h t ，w e j g h t ) 电路交换，o b s 的链路利用率虽然比电路交换的利用率有所提高，但无法从根本上 克服电路交换链路利用率较低的弊病。另一种思路是仍然采用分组交换，变革现有的交换结 构的设计使其能够支持高的链路速率。本文将沿用后一种思路，利用空分并行技术来设计具有低 缓存带宽需求的分组交换结构。 1 1 1 分组交换概述 萌芽于1 9 7 0 年前后的i n t e 鼢忸t 作为满足长途数据通信需求的产物，与传统电信网络相比 最大的区别在于两者所用的交换技术。后者采用的是适合语音通信的电路交换技术，而 i n t e r n e t 则是按照分组交换的原则构建的。 分组交换”“1 “1 中，数据以小的数据块为单位被传输，这样的块被称为分组或包( p a c k e t ) 。分 组长度一般是可变的，但有一个上限。如果一个源主机有很长的报文要发送，此报文就要被划分 为一系列的分组。每个分组包括用户的数据和一些控制量l 、。路由器根据分组的控制售叠、为：葚选 择路由进行分组交换，因此路臼器的两个主要功能是路田和交换。 分组交换网络由一组路由器和互连路由器的相关链路组成。图1 1 描绘了一个简单的分组交 换网络。设想b 站要发送一个分组到服务器d 。分组的控制信息指出了目的站是d 站。分组从 b 站被送到：甘点( 路由器) 1 ，”1 ，点1 存储这个分绸，决定f 一步的路径( 比如”1 ，点2 ) ，然后让分组 在通往节点2 的链路队列中排队。当这个链路可用时分组就被传送至节点2 ，然后分组再从节点 2 转发至节点3 ，直至最终到达服务器d 。这种交换方式与电路交换相比有许多的优点： a 线路利用率更高，因为节点到= 育点的单个链路由很多个分组动态共享，可以实现链 第一章引言 路资源的统计时分复用； b 对终端接入的速率支持更灵活。两个不同数据率的站之间能够交换分组，因为每个 站以它的自己的数据率连接到网络节点上； c 减小呼损率。当电路交换网络上通信量变得很大时，一些呼叫就被阻塞了。但在分 组交换网络上，分组仍然将被接受，只不过交付时延会有所增加： d 可以使用优先级。这导致分组交换网络对业务的支持更灵活。 尽管分组交换具有这些优点，但这些优点的获得是有代价的。由于数据分组的到达是突发性 的，为了不致突发到达的分组丢失，分组交换网中的节点必须能缓存部分分组。这导致分组路 由器在设计时不得不精心设置分组缓存器并设计与之相应的缓存管理和分组调度算法。 m “阳f h 。眦， 1 1 2 路由器组成 图1 1 一个简单的分组交换网络 在分组交换网络中，分组的寻径和交换是由路由器完成的，它是分组交换网络的核心组件。 路由器一般有网络接口卡，交换阵列，处理模块和缓存模块等几部分组成。其逻辑结构如图1 2 所示，当输入链路有分组经过网络接口 到达路由器斤，处理模块根据分组携带的控制信息查找 路由表( 路由表通过处理模块运行的路由协议进行动态刷新) 以确定该分组将被转发的输山链路， 然后将分组放入相应的缓冲区中进行排队。处理模块运行一定的分组调度算法决定当前的调度决 策来配置交换阵列将缓存中的分组交换到对应的输出端，输出端的分组在经过重装配后被发送到 输出链路上。 2 东南大学博士论文 路由器的性能与路由器采用的交换和缓存机制密切相关。交换阵列和缓存机制是一个有机的 整体，称为交换结构( s w i t c h i n gf a b r i c ) 。交换阵列可以采用总线、白切尔一榕树结构、c l o s 结构或 纵横制交换阵列( c r o s s - b a r ) 。纵横制交换阵列由于其无阻塞特性被现代高速路由器所广泛采用， 因此本文交换结构的研究主要针对纵横制交换阵列。另外，虽然抵达路由器分组的分组长度是可 变的，但为了处理的方便现代路由器中通常将变长分组切分成定长的信元( c e l l ) 。因此本文假设 通过交换结构的分组是定长的，若未加特殊说明将不区分的使用术语分组和信元。并且，假定链 路和交换机的工作时间均匀的分成时间片，每个时间片的长度等于一个信元的传输( 或发送) 时 间，称为时隙f s l o t ) 。 1 1 3 交换结构设计问题 i u 生j 燮换绻i ；】| 1 _ ：| ! 。ji 。”j 1 _ 图1 2 路由器逻辑示意图 传统的交换结构采用输出队列来组织缓存，即将分组的缓存设置在交换阵列的输出端。如图 l3 ( a 1 所示，输出队列结构为每一输出链路设置一个缓存。当分组到达后根据分组的目的地址通 过交换阵列进入胡应的缓存排队。不难看出，输出队列结构在简单的f i f o r f i mf nf i r s to u i ) 队列 服务规则下即可获得链路1 0 0 的吞吐率。同时，若采用p g p s 卧9 2 1 或v c 等复杂些的调度算 法，输出队列结构还能提供服务的带宽和时延保证，能够满足语音、视频等实时多媒体数据传输 的需求。网此在很艮的一段时间内输出队列结构在路由器或交换机设计中得到了广泛的应用。 然而，输出队列结构本身存在着可扩展性问题。幽1 3 ( b ) 解释了这一问题的成因，若在同一 时刻交换机的n 个输入端到达的分组均将由同一个输出端口转发，为了不致分组不必要的丢失 就必须将这n 个分组同时写入该输出端口的缓存中，这要求交换阵列内部互连链路的速率是外 部链路速率的n 倍，更为严峻的是输出端缓存的速率也必须是外部链路速率的n 倍。 3 第一章引言 而目前通信链路和缓存器发展现状是：通信链路在1 9 9 5 年以前基本采用t d m 技术，t d m 链路基本按照m o o r e 定律的速度发展，1 9 9 5 年后随着d w d m 技术的成熟，光纤链路的速率以 每1 8 个月2 2 倍的速度发展j ，而商品存储器由于是针对容量进行优化的，其工作速率每1 8 个 月却只能提高到1 1 倍。这造成在交换机设计领域对存储器带宽需求和存储器带宽实际发展间的 巨大落差，导致存储器成为高性能交换机设计实现的主要瓶颈。显然，缓存需要n 倍加速比的 输出队列结构难以适应这种高性能交换。 - - - 一 j ll l l l i l l i ill + h * 十 l | | i - - - - - - - - j t r b ；“ l 开肠r 一一一一? 7 “l 。f l p r a 输出队列交换结构b 输出队列的可扩展性问题 图1 3 输出队列结构示意图 另一方面，随着多媒体技术的进步目前i n t e m e t 承载的流量包括了文本、图形图像、音频视 频等多种信息，支持音视频点播，网络会议，i p 语音等等多种业务。这些不同的业务对网络带 宽、分组延迟和抖动等性能指标的要求不同，这要求网络对其所提供的服务提供一定的o o s 保 证。而这种q o s 保证的提供必须由构成网络基础交换结构的交换机路由器来实现。因此，高性 能交换结构设计迫切需要解决的是： 设计对缓存带宽需求较低的交换结构 设计满足一定性能( 如吞吐率、q o s 保证等) 要求的调度算法 1 2 研究现状 1 2 1 输入队列结构 输入队列结构是与输出队列结构对偶的一种交换结构，它将分组的缓存设置在交换阵列的输 入端( 图14 ( a ) ) ，这样每个缓存每个时隙至多只有一个分组写入，使得存储器和交换阵列可以工 作在链路速率下。与需要n 倍加速比的输出队列结构想比输入队列结构的可扩展性得到了很大 提高。但如文献”1 揭示的，输入队列结构存在着严重的队头阻塞( h e a do f l i n e 引o c k i n g ) 。所谓 队头阻塞是指当采州f i f o 调度策略时，当两个以上队列头元素具有相同的输出端口时，只能由 其中一个队列接受服务；其它队列即使非队头元素有去往其它输出端口的分组，由于f i f o 的性 质，该分组也将阻塞在队列中不会得到转发。图1 4 ( b ) 说明了h o l 阻塞对吞吐率的影响：输入 4 东南大学博士论文 端口1 和2 的队头分组都去往输出端2 ，由于输出端口2 一个时隙只能接受一个分组，因此输入 端2 的队头分组在竞争失败后将在这一时隙内得不到服务，尽管输入端2 的第二个分组去往输出 端4 ，但由于队列服务的f i f o 特性纵然输出端口4 在当前时隙空闲也不能服务于输入端口2 ， 这将导致交换阵列的吞吐率下降。正是因为h o l 阻塞的存在，输入队列结构在使用兀f o 调度 策略时，即使在均匀的输入流量下吞吐率也只能达到5 8 6 。因此，输入队列结构在很长的一段 时间内未得到人们的重视。但进入1 9 9 0 s 后，随着链路速率与存储带宽矛盾的日益尖锐，输入队 列又重新进入研究人员的视线并成为高性能交换领域的一个研究热点。 巫固 l 二! ! 二= 二一 b u f f b r c r 口s s b a r a 输入队列交换结构 c r o s s b a r b 输入队列的h o l 阻塞问题 图l4 输入队列交换结构及h o l 阻塞问题 输入队列研究的主要课题是设计调度算法以克服h o l 阻塞所造成的性能缺陷。h o l 阻塞的 成因是由于f i f o 调度时每个队列只有队头元素参与调度决策。因此解决h o l 阻塞的一个自然 的想法是在每次调度时，每个队列多取些元素参与决策，例如p 1 中取每个队列的前w 个分组参加 调度，这时w 称为窗口尺寸，当w = l 时窗口策略将退化为纯粹的f i f o 策略。正如i ) 1 所示，只要 w 取值适当窗口策略可以在一定程度上减轻h o l 阻塞。l b l 提出一种旁路队列的窗口策略方案， 使得窗口策略调度算法可以并行执行。同时，f “q 也对窗口策略作了近一步研究，提出了一些窗 口策略的改进方案。但窗口策略并不能从本质消除h o l 阻塞对交换结构吞吐率的负面影响，即 使取较大的窗口尺寸，交换结构在均匀流量下的吞吐率也只能达到9 0 左右“。“。并且，由于窗 口策略破坏了队列的f i f o 特性使得缓存的管理变得很困难导致窗口策略难以付诸实现。 a l 提出了所谓的虚输出队列r v i m a lo u t p u tq u e u e i n g ) 鸭盼1 1 卅中在v o q 的基础上将f q 的 词度问题转化为二分圈匹配问题，这一里程碑式的成果为输入队列结构彻底解决h o l 阻塞闫题 带来了希望。 第一章引言 12 1 1 虚输出队列及二分图匹配 虚输出队列是输入队列交换结构中的一种缓存管理策略。设交换阵列的规模是n n 的，如 图1 5 ( a ) 所示，虚输出队列为每个输入端的缓存设置n 个逻辑队列，每个队列对应一个输出端口， 因此总共有n 2 个逻辑队列。当某个输入端口有分组到达时，根据分组的目标地址将其放入该端 口缓存相应队列的末尾排队，而调度时调度器将只考虑每个逻辑队列的队头分组，因此每个逻辑 队列按f i f o 方式工作。v o q 不仅简化了缓存管理而且使得每个端口所有的分组转发可能均出 现在了逻辑队列的队头中，使彻底克服h o l 阻塞成为可能。 廿 器 阵 c r o s s b a r a 3 3 虚输出队列 a b c b 二分图模型 图1 5 虚输出队列及二分图模型 2 采用虚输出队列后，输入队列的分组调度问题可以用二分图的匹配来建模。构造二分图的做 法是：设二分图g = ( ，v ) ，n 1 对应交换结构的输入端，n 2 对应交换结构的输出端，若输 入端口n 的缓存中第m 条队列非空，则将边( n ，m ) 添加至v 中，图1 5 ( b ) 给出了与图15 ( a ) 中虚输 出队列相对应的二分图模型。显然如此构造出的二分图中，每一条边表示一个输入端口对某个输 出端口的服务请求。任意时隙的调度决策是一组服务请求的集合，其中没有任意两个请求有相同 的输入端也没有任意两个请求有相同的输出端。这就等价于在二分图g 上寻找一个匹配。这样， 输入队列的分组调度问题就转化为二分图匹配问题。 二分图的匹配主要有极大匹配f 图i6 ( a ) ) 不能进一步扩展的匹配和最大匹配拥有最 多边数的匹配( 圈j 6 l b j ) 两大类，输入队列调度研冗的重点是考察各种匹配在不同流量模型下的 吞吐率性能以及相应的高效算法。目前这一领域的研究己取得较为丰富的成果，这些算法大致可 以分为：并行极大匹配算法、最大匹配算法和差分算法。 6 东南大学博士论文 b 。 a 极大匹配 1212 并行极大匹配算法 p l m 算法 a - l 2b 2 3 c 3 b 最大匹配 图1 6 二分图1 5 ( b ) 的两种匹配 t a n d e r s e n 在中利用虚输出队列( 咖a 1o u t p mq u e u e i n 曲和i q 调度问题的二分图模型设 计了并行迭代匹配算法p v i ( p a m l l e li t e r a t i v em a t c h i n g ) ，该算法首次将输入队列结构在均匀流量 下的吞吐率提高到9 5 以上，使得在高性能交换机中使用输入队列结构成为可能。p i m 算法在 一次迭代时每个端口执行三个步骤： s t e p l ：( r e q u e s t ) 每个输入端口为每个非空的v o q 发送服务请求至相应的输出端； s t e p 2 ：( g r a i l t ) 每个输出端口在所有收到的请求中一致随机地选择一个将响应发回至输 入端； s t e p 3 ：( a c c e p t ) 每个输入端口在所有收到的响应中随机选择一个输出端接受并通知该 输出端。 算法的第2 步保证了，每个输出端只为一个输入端服务而第3 步保证了每个输入端只接受一 个输出端的服务，因此确保了算法的输出是一个匹配。同时，算法在输入端口间没有信息交互， 无须集中控制器，各端口的处理可以分步并行执行。对于n n 的交互结构p i m 算法找到极大 匹配所需的平均迭代步是o ( 1 0 9 n ) ，因此可用于高速交换场合。仿真结果表明在均匀一致的流量 下p i m 算法具有较好的性能，吞吐率接近1 0 0 。 给出了一种只需两次握手的并行迭代算法l e p i m ( l o g i ce q u i v a l e n c eo f p i m ) 。该算法在每 个迭代步的第一阶段由每个输入端口随机选择一个非空v 0 q 为其发送服务请求至相应输出端 口；每个输出端口随机选择一个收到的请求进行服务。由于l e p j m 每个输入端只发出一个服务 请求，因此可以省去p i m 算法的第三步接受阶段。这使得调度器的通信复杂度减少了1 3 ，因而 可以以更快的速度执行。但两阶段的并行迭代算法由于输出端收到的服务请求少，每个输出端的 选择范同小，当算法已经找到一个极火匹配的火多数边时，随后的迭代找到新的边的概率也比 p i m 算法小，冈此，l e - p i m 算法需要较多的迭代步才能保证算法收敛到极大匹配。 网络中的实际流量具有突发性的特点，因此凋度算法在突发流量下的性能比在一致均匀流量 下的性能更有参考价值。但p i m 算法在突发流量下的表现不尽如人意，延迟一负荷性能较差。为 7 第一章引言 了解决这一问题，g i p 印a d i m i t r i o u 在i 叫对p i m 做了改进，提出了l a b s a 算法。l a b s a 算法采 用与p i m 算法相同的三次握手方式，它对p i m 最大改进在算法第二步输出端对请求响应的选择 概率上。l a b s a 的每个输出端口为每个输入端设定一个请求响应概率p 。，算法的第二步依据请 求响应概率和输出端所收到的请求计算出正规化响应概率并按照正规化响应概率来决定对哪个 输入端做出响应。然后算法在第三步后对请求响应概率p 。进行更新。更新时采用了一个学习自 动机，若输出端j 对输入端i 的响应在s t e p 3 被输入端i 接受，那么p 。将增加一个基数1 l ( ；若未 被接受p 。则减少一个基数1 l ( 。由于l a b s a 采用了一种自适应的选择概率，使得l a b s a 更能 适应突发流量的非线性特性，因此l a b s a 在突发流量下的性能比之p i m 有了很大提高。仿真实 验显示，对于1 6 + 1 6 的交换结构l a b s a 算法仅需两次迭代即可获得较为令人满意的延迟负荷性 能。 r o 机n d r 0 b 溉类算法 并行迭代算法的关键是解析输出和输入端的冲突从而保证每个输入( 输出) 端只匹配一个输 出( 输入) 端。p i m 类算法利用随机仲裁器( a r b i t e r ) 来解决这种冲突。但随机仲裁器在实现时面临两 个问题：首先，设计一个在时变集合上产生满足特性要求的随机数发生器是困难且昂贵的；其次， 现有的伪随机数产生算法复杂度过高导致随机数发生器难以高速产生伪随机数。 r o u n d - r o b i n ( 循环优先) 仲裁器也通常用来解析冲突，并且r o u n d r o b i n 仲裁器具有简单、高 速、易实现等优点，加之成本低廉，因此r o u n d r o b i n 仲裁器受到了开发研究者的青睐。 r o u n d - r o b i n 仲裁的原则是每个仲裁器设有一个优先指针，若等待仲裁的元素集合的模为n ，指 针的移动按递增( 对n 取模) 的方向进行，那么优先级最高的元素是在指针移动方向上最靠近指针 的元素。 b r r ( b a s i cr o u n d - r o b i n ) 算法o “1 是最基本的r 0 u n d r o b i n 算法。b r r 算法输出端 r o u n d r o b i n 仲裁器优先指针的更改策略是：若输出端收到服务请求则按r o u n d r o b i n 优先级对 优先级最高的请求发出响应，并将优先指针移到被响应元素的下一个位置，若没有收到请求则优 先指针位置不变。输入端的仲裁器r o u n d r o b i n 指针的更改办法是：若v o q 都为空则指针不变， 否则指针移到被响应元素的下一位置。仿真研究发现b r r 算法性能很差，在一致均匀的流量下 吞吐率不到6 5 。n m c k e o w n 在“中对b r r 性能低下的原因作了详细的分析。指出造成b r r 性能差的主要原因是输出端的指针移动存在同步的现象。在均匀流量下负荷较高时，几乎每个的 输入端口的所有v o q 都非空，此时每个输出端将收到来自所有输入端的服务请求，根据b r r 的指针修改策略所百输出端的指针移动几乎以一种锁定的方式侈动，即不同输出端的指针相对 位置几乎不发生变化，这称为指针的同步。指针同步将导致输入端不被响应的概率为 ( 一1 ) “，因此b r r 在均匀流量下的吞吐率只能达到1 1 ，p z6 3 。 仔细分析指针同步的起冈，不难香出，之所以发生各输出端指针移动锁定是由丁f 输出端的在 指针更改时不管发出的响应是否被输入端接受都将指针移动剑被响应元素的 一位置造成的，冈 此口8 ”3 】提出了一个新的指针更改方案，将响应是否被接受区分开米从而来避免指针同步的出 现，该算法称为j s l i p 。具体做法是，若响应未被接受指针将保持不变，只有当响应被接受指针 才移动到被响应元素的下一位置。另一个去指针同步的r o u n d r o b i n 算法f i r m r f c f si n 8 东南大学博士论文 r o u n d r o b i nm a t c h i n g ) ，由d n s e r p a n o s 在文献。川1 中提出。表1 1 归纳了三种r o u n d r o b i n 算法 指针修改策略异同【j “。i s l i p 算法中当响应未被接受时，输出端指针保持不变。下一时隙，若此 指针和上一时隙间的某个v o q 由空变为非空，由于该队列更接近优先指针那么它将会得到响应， 而它的到达时刻晚于上个时隙响应的队列，这就破坏了服务的f c f s 原则，因此可能导致服务的 公平性下降。f i r m 即是根据这一观察对i s u p 做出了改进。f i r m 在输出端指针更改时，当响 应未被接受时指针将移动到被响应的位置而不是保持不变，这将更符合f c f s 服务策略。若将一 个v 0 0 队头元素在最坏情况等待服务的时隙数作为r o u n d r o b i n 算法的公平性衡量指标，i s l i p 需要n 2 + ( n 1 ) 2 时隙，而f i r m 只需要n 2 个时隙。这表明f i r m 算法这种接近f c f s 的指针更改 策略改善了r o u n d r o b i n 算法的公平性。同时，仿真结果表明i s l i p 和兀r m 在一致均匀流量下 都具有良好的性能，仅需一次迭代即可达到1 0 0 吞吐率，这使i s