（电路与系统专业论文）公平可扩展网络交换调度算法及其fpga实现.pdf

摘要 摘要 随着i n t e r a c t 的迅速发展，对网络交换技术也提出了越来越高的要求。下一代网络 交换的核心技术就是高性能的网络交换设备，优良的性能主要表现在具有较大的交换容 量、较高的吞吐率、较小的延迟时间并且能够在任意流量下都具有较低的丢包率。目前， 虽然交换机和调度器都有成功开发的集成电路芯片，但大多都是由国外厂商研制开发 的，其核心技术和知识产权也掌握在国外开发商的手中，而且受到半导体制造工艺限制， 单个芯片在电路规模、i o 管脚数及处理速度上都受到了限制，要想实现多端口、大规 模的交换和调度芯片十分困难。因此，有必要对网络交换和调度技术作进一步研究，寻 求一种可扩展的网络交换结构以适应下一代网络发展的需要。 在多个网络交换方式中，输入队y 0 ( i q ) 交换方式由于其速度不受存储器存取速度的 限制成为网络交换的主要方式。i q 交换采用虚拟输出队列( v o q ) 机制，将每个到达的 包按照其目的地址的不同存放存在相应的输入缓冲中，有效地降低了头部阻塞( h o l ) 给 i o 交换带来的，从而使系统的最大吞吐率达到1 0 0 。i q 调度算法主要分为两大类： 最大权匹配算法o 讧w m ) 和极大尺寸匹配算法( m s m ) 。前者以l q f 算法为代表，拥有优 秀的性能，但其硬件复杂度高达0 ( 妒1 0 9 7 ) ，使其很难实际应用；后者以i s l i p ，f i r m 和r d s r r 等算法为代表，拥有较低的硬件复杂度，其性能却逊于前者，尤其在非均匀 流量及大负载情况下算法不稳定。自1 9 9 9 年提出了i s l i p 算法之后，近年来不断有新 的i o 调度算法提出，其目的都是为了改善m s m 算法在非均匀流量下性能不理想的状 况。本文对这一问题也作了研究，提出了一种自适应双门限算法s a t r r 。该算法通过 为输入队列旌加队列长度闽值和队首包等待时间阙值，使得具有较大权重的队列得到优 先调度，从而在控制硬件复杂度的前提下，改善了算法的性能。仿真结果表明，在均匀 流量模式和非均匀流量模式下，s a t r r 算法的延迟特性均优于其它m s m 算法，取得 了性能与硬件复杂度的良好折中。 在设计高性能调度算法的基础上，本文研究了可扩展网络调度系统f s s a 的硬件实 现。f s s a 是在国家自然科学基金资助下提出的一种公平可扩展网络交换调度结构，它 由若干片容量较小的调度器串联而成，在中心控制器的控制下，各子调度器并行工作完 成大容量、多端口的调度任务。在实际应用中，f s s a 可根据需要扩展成不同容量和端 口数的调度器，不仅速度高，而且规模可扩展，从根本上解决单个调度器容量和端1 ：3 受 限的问题。研究采用x i l i n xf g p a 设计实现了6 4 x 6 4 的基于f s s a 的调度器。该调度器 由4 片x i l i n xv i r t e x - 4 芯片级联构成，每片完成1 6 x 6 4 的子调度器任务。设计中充分合 理地应用了x i l i n x v i r t e x - 4 f p g a 的新特性以及其内嵌的口核及功能模块，如高性能输 入输出串并、并串转换器i s e r d e s 和o s e r d e s 、数字时钟控制器d c m 等，从而节 省了大量宝贵的逻辑资源，提高了芯片的速度和性能。仿真和验证结果表明，本设计功 能正确，每个子调度器可以同时处理1 6 路8 0 0 m b p s 的数据，满足设计要求。 文章第一章主要介绍课题背景及意义，第二章介绍s a t r r 算法的原理及性能仿真 结果，第三章详细给出f s s a 系统的结构设计方案，第四章介绍设计开发工具以及器件 特性，第五章是基于f p g a 的系统实现方案和结果。第六章给出验证方案，最后是结论 部分。 关键词：路由器，输入队列交换，网络调度，调度算法，f p g a ，实现 摘要 a b s t r a c t a si n t e r n e tg r o w sw i t ha l li n c r e d i b l es p e e d , l a i g h - p e r r o r m a n e es c h e d u l e r sw i t hl a r g e r c a p a c i t y , t l a r o u g h p u t ，a n dl o w e rl a t e n c ya sw e l la sas a t i s f a c t o r yl o s sr a t eu n d e ra n yt r a f f i cp a t t e r n 黜r e q u e s t e d o nt h eo n cb a n 正t h es w i t c h i n gc a p a c i t y , s p e e da n df om m a b e r so fas i a g l ec h i p a l i r n i l e ab yc u r r e n tr , e m i , o n d u e t o rl e c h n o l o g y o nt h eo t h e rh a n d , a l t h o _ i l g hr e v i s i n gp o i n t e r s s e t t i n gt h r e s h o l d s ，i n e r e a s i r * ga n dd e c r e a s i n gs c h e d u l i n gp h a s e s ，c a na c h i e v el o w e rl a t e n c ya n d h i g h e rt h r o u g h p u tt h ei m p r o v e m e n ti sn o td i s t i n c t t h e r e f o r e ，t h es c h e d u l i n ga r c h i t e c t u r e sr a t h e r t h a ns c h e d u l i n ga l g o r i t h mi t s e l fn e e dm o l ec o n s i d e r a t i o ni no r d e rt oa c h i e v et h er e q u i r e m e n to f n e x tg e n e r a t i o nn e t w o r k f o ra nn x n i n p u tq u e u e d ( i q ) s w i t c h , e a c hi n p u tb u f f e rr e , s o l y e sc e l l si nns e p a r a t e q u e u e sa c c o r d i n gt ot h e i rd e s t i n e do u t p u t sb e f o r es c h e d u l i n g , w h e r es u c hq u e u e sa r ec a l l e d v i r t u a lo u t p u tq u e u ec e o q ) u s i n gv o qa n da p p r o p r i a t es c h e d u l i n ga l g o r i t h m , i qs w i t c h e s c a ne f f e c t i v e l ye l i m i n a t et h eh e a do f l i n ef f o l ) b l o c k i n ga n da c h i e v et o o * , t l l r o u g t t p t t tu n d e r s o m ei x a f f i cp a t t e r n s o v e rt h ed e c a d e s ，m a n ys c h e d u l i n ga l g o r i t h r mh a v eb e e np r o p o s e d a m o n gt h e m , m a x i m u mw e i g h tm a t e h i a g ( m w m ) a l g o r i t h m s ，e g l q fw i t hh i g he o m p l e r j t y o f o ( n 3 l o g , v ) ，c a l la c h i e v e ar e l a t i v el o w e rl a t e n c y m a x i m a ls i z em a t c h i n g ( m s m ) a l g o r i t h m s s u c h 粕i s l p , f i r ma n dr d s r rh a v el o w e rc o m p l e x i t yb u ta r ep r a c t i c a lf o ri m p l e m e r t t a d o m h o w e v e r , 击e i rp e f f 研m c 嚣a n o t 醛g o o d m w m t h ed e s i g np r e s e n t san o v e la l g o r i t h m s a t r r w h i c hm a k e sh e a v yq u e u e ss c h e d u l e df i r s tt l l r o u g ha d d i n gt h r e s h o l d sf o rb o t ht h e m a x i m a lw a i tt i m eo f h c a dc e l l sa n dt h em a x i m a lq u g l e n g t ha n dt h u si * e a l i z 酷ag o o dt r a d e o f f b e t w e e nc o m p l e x i t ya n dr e r f o r m a n e e b a s e do nd e s i g n e dh i g hp e r f o r m a n c ea l g o r i t h m , t h i sp a p e rp r o p o s e st h ef a i r $ e a i a b l e s c h e d u l i n ga r c h i t e c t u r e ( f s s a ) ，w h i c h 虹s u p p o r t e db yn a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o n f s s ad e c o m p o s e daf o r m e r l yl a r g e - s c a l en e t w o r ks c h e d u l e ri n t os e v e r a lc a s c a d e ds m a l l e r m o n o l i t h i cs u b - s c h e d u l e r s ，t h u st h ec a p a c i t yl i m i t a t i o no f s i n g l ec h i pi so v c l r c a l m b ye m p l o y i n g p a r a l l e lc o m p u t a t i o n , f s s ar e a l i z e dab e t t e rl a t e n c yr , c r f o r m a n e e 删a l l yu n d e rl a e a , “s , t r a f f i c l o a da n dx 】o n - u n i f o r m 仃a 衢cp a t t e r nt h l o l l g l lt h ef r o n t c n d 日, l g o r i t h ms i m u l a t i o n t h i sd e s i g ni m p l e m e n t sa6 4 x 6 4s c h e d u l e rc o n s i s t i n go f 4s u b - s c h e d u l e r sw i t hf o u rc h i p so f x i l i n xv t r t e x - 4f p g a s a n di tc a l lb ee a s i l ye x t e n d e d 幻l a r g e ra p p l i c a t i o nw h e nn e c e s s a r y i n o r d e rt o 1 v cp r e e i o ml o g i cr e s o l l l c e sa n dt h er e l i a b i l i t y , l a r g ea m o u n to fe m b e d d e dm o d u l e s s u c ha sl s e r d e s o s e r d e s ，d i g i t a lc l o c km a n a g e m e n t ( d c m ) ，f i f o sa n db l o c kr a m sa r e e m p l o y e d t h ev e r i f i e a t i o tr e s u l t si n d i c a t et h a tt h ed e s i g t lw o r k sw i t hc o r r e c tf t m e t i o n a l i t ya n d e a c hs u b - s e l a e d u l e r sc a c h i e v e8 0 0 m b p sd a t ar a t ef o ri t s1 6d a t ac h a n n e l s ， t h ep a p e ri so r g a n i z e da s ：c h a p t e rli n ( x o d u c e st h eb a c k g r o u n do fd e s i g na n dt h et h e o r yo f b a s i cn e t w o r ks c h e d u l i n g c h a p t e r2p r e s e n t st h ed e s i g no fs a t r rw i t hi t ss i m u l a t i o nr e s u l t s c h a p t e r3i n t r o d u c e st h eh a r d w a r ed e s i g no ff s s af o ra l li qs w i t c hi nd e t a i l c h a p t e r4 i n t r o d u c e sx i l i n xv i r t e x - 4d e v i c e sa n dt h e i rr e l a t e d ( ：l e v e l m e r i tt o o l s c h a p t e r5i sa b o u tt h e f p g ai m p l e m e n t a t i o na n ds i m u l a t i o nr e s u l t s c h a p t e r6p r o p o s e sv e r i f i c a d o np r o g r a mf o rt h e s y s t e r n f i n a l l y , v # ep r e n te o n e l u s i o mi nc t a a p t e r7 k e y w o r d s ：r o u t e r , i n p u tq u e u e ds w i t c h i n g , n e t w t , r ks c h e d u l i n g ，s c h e d u l i n ga l g o r i t l m l , f p g a ，i m p l e m e n t a t i o n m 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公 布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生 院办理。 研究生签名：亟遂导师签名：皇i 她乌日期：翟丝 研究生签名：塑整 导师签名：皇i 蝼骂日期：经丝 第一章绪论 第一章绪论 本章首先介绍了课题背景及意义，接下来介绍目前网络通信中的典型调度结构，然后 概述了调度算法的两种主要类型即最大尺寸匹配算法( m s m ) 和最大权匹配算法( m w m ) ， 最后给出作者在攻读硕士学位期间的研究工作的主要内容和论文的结构安捧。 1 1 课题背景及意义 计算机网络是将多个具有独立工作能力的计算机系统通过网络节点设备和通信链路及 功能完善的网络软件实现的资源共享和数据通信的系统。其中，通信链路负责将数据从一 台通信设备传输到另外的一台通信设备，路由器、交换机等网络节点设各则负责存储、路 由查找，转发与处理数据。 图1 1 所示为一种计算机网路的连接方式，来自各个局域网的信元溅包) ，首先经过局 域网交换机进行汇聚集中，之后经由边缘路由器送往骨干路由器，在骨干路由器的调度下， 按照目的地址被交换到到相应的局域网中。其中的路由器或交换机可构成一个规模为n x n 的独立交换体系。 1 l j 图1 1 分组交换子网互连结构 一般说来，异种网络互联与多个子网互联都应采用路由器来完成。路由器工作在o s i 模型中的第三层即网络层，它的主要工作就是为经过路由器的每个数据帧寻找一条最佳传 输路径，并将该数据有效地传送到目的站点。由此可见，选择最佳路径的策略即路由算法 是路由器的关键所在。为了完成这项工作，在路由器中保存着各种传输路径的相关数据一 路由表( r o u t i n g t a b l e ) ，供路由选择时使用。路径表中保存着子网的标志信息、网上路由器 的个数和下一个路由器的名字等内容。路径表可以是由系统管理员固定设置好的，也可以 由系统动态修改，可以由路由器自动调整，也可以由主机控制。 路由器的典型功能可以归纳为两类，即数据通道功能和控制功能。数据通道功能包括 转发决定、背板转发以及输出链路调度等，一般由特定的硬件来完成；控制功能一般用软 件来实现，包括与相邻路由器之间的信息交换、系统配置、系统管理等。 构成路由器的主要部件是输入端口、输出端口、交换开关和路由处理器。输入端口是 东南大学硕士学位论文 物理链路和输入包的进口处。端口通常由线卡提供，一块线卡一般支持多个端口，一个输 入端口具有许多功能，1 ) 数据链路层的封装和解封装；2 ) 在转发表中查找输入包目的地 址从而决定目的端口( 称为路由查找) 等，路由查找可以使用一般的硬件来实现或者通过 在每块线卡上嵌入一个微处理器来完成；3 ) 当需要提供服务质量( q o s ) 保证时，端口还要 对收到的包分成几个预定义的服务级别；4 ) 端口可能需要运行诸如s l i p ( , 串行线网际协议) 和p p p ( 点对点协议) 等数据链路级协议或者诸如p p ，r p ( 点对点隧道协议) 等网络级协议。一 旦路由查找完成，必须用交换开关将包送到其输出端口。如果路由器是基于输入队列方式 的，则有几个输入端共享同一个交换开关。这样输入端口的最后一项功能是参加对公共资 源( 如交换开关) 的仲裁协议。 交换开关可以使用多种不同的技术来实现。迄今为止使用最多的交换开关技术是总线、 交叉开关和共享存贮器。最简单的开关使用一条总线来连接所有输入和输出端口，总线开 关的缺点是其交换容量受限于总线的容量以及为共享总线仲裁所带来的额外开销。交换开 关中交叉点的闭合与打开由调度器来控制，因此，调度器限制了交换开关的速度。在共享 存贮器路由嚣中，进来的包被存贮在共享存贮器中，所交换的仅是包的指针，这提高了交 换容量，但是，开关的速度受限于存贮器的存取速度。尽管存贮器容量每1 8 个月能够翻一 番，但存贮器的存取时间每年仅降低5 ，这是共享存贮器交换开关的一个固有限制。 输出端口在包被发送到输出链路之前对包存贮，可以实现复杂的调度算法以支持优先 级等要求。与输入端口一样，输出端口同样要能支持数据链路层的封装和解封装，以及许 多较高级协议。路由处理器计算转发表实现路由协议，并运行对路由器进行配置和管理的 软件。同时，它还处理那些目的地址不在线卡转发表中的包。 9 0 年代中期，传统路由器由于采用软件进行存储和转发。速度远远不能满足i n t e m e t 迅速发展的需要从而被a t m 交换机取代，到了9 0 年代末期，i n t e m e t 规模进一步扩大，流 量每半年翻一番，a t m 又成为互联网发展的瓶颈，路由器东山再起，尤其当o b p s 速率的 路由交换机在1 9 9 7 年面世后，人们又开始以g b p s 路由交换机取代a t m 交换机，架构以 路由器为核心的骨干网。 1 2 网络调度算法简介 目前，路由器采用的交换方式主要有三神：输入队列( i q ) 交换、输出队列( o q ) 交换和 输入输出组合( c i o q ) 交换。传统的路由器大多采用输出队列结构，即包缓存在交换机的输 出端。虽然基于o q 的交换具有最优的性能，但由于缓存器的工作速率必须n 倍于输入链 路的速度，很难适应高速交换的场合。另一方案是采用i q 交换，图1 2 所示为协( 的i q 交换。在i q 交换中，交换结构( 如图1 2 中的c r o s s b a r ) 实际上就是一组物理开关，实现任 意n 个输入到任意n 个输出的连接和断开，开关的开和关则是由调度器产生的控制信号控 制的。通常在一个信元时间( c e l lt i m e ) 里，一个输入只能与一个输出相连，由于常常会有多 个来自不同输入端的包去往同一个目的地的现象，从而引起输入队列的线头( ( h e a d o f l i n e ， h o l ) 阻塞问题。所谓h o l 阻塞就是位于队列头部的包由于必须种种原因没能及时转发而 它阻塞了对它后面包的处理，即使后面的包可以转发。h o l 现象会导致整个i o 交换的吞 吐率( t h r o u g h p u t ) 受限。研究表明，若不采用特殊处理，系统的最大吞吐率只能达到5 8 6 略“。 为此，在i q 交换方式中，需要为每个输入端口保存一组虚拟输出队列v o q m l , m l o u t p u t q u e u e ) 。图1 2 中来自线卡的输入i n p u t l 一i n p u t n 分别与交换机构的n 个输入端相 连。各线卡所接收的数据包根据其输出目的地的不同被分别存放在相应的虚拟输出队列 v o q l l - v o q m ，v o q n l v o q w 中，在调度器的控制下。通过c r o s s b a r 被交换到n 个不同的输出端口。与传统的调度结构相比，这种虚拟输出队列机制解决了困扰i q 交换 2 第一章绪论 方式的h o l 阻塞问题，可以使系统的晟大吞吐率达到1 0 0 。随着对i q 交换研究的不断 深入和新算法的不断提出，i q 交换因其硬件实现简单和不受存储器存取速度限制的特点而 逐渐成为网络交换结构的主要方式。 v o q 图1 2 输入队列交换( i q ) 结构 n 近年来，针对i q 交换已经提出了诸多有效可行的调度算法。评价一个调度算法的优劣， 主要从下几个方面进行： ( 1 ) 算法的调度延迟 算法的调度延迟是衡量算法性能最为重要的指标，代表调度器在相应算法下完成一轮调 度的平均时间，即从信元到达交换机，到所有信元被送达目的地之间的时隙差。 ( 2 ) 最大吞吐率 吞吐率( t h r o u g h p u t ) 是衡量交换结构性能的主要指标之一，它被定义为每个时隙交换结 构每个输人端上成功传送信元到达其目的输出端口的数目。最大吞吐率是指在最大负荷下的 吞吐率的值。交换机的稳定性与1 0 0 吞吐率是一种因果关系。1 0 0 吞吐率可定义为：如果对 于所以相互独立的并且是可接受的信元到达，交换是稳定的，则可以认为交换机能达到1 0 0 的吞吐率。 ( 3 ) 无饥饿 饥饿( s t a r v a t i o n ) 是指对于给定的业务流模式和算法，一个非空的输入队列处于无服务 的不确定状态。良好的算法应消除这种队列饥饿现象。 ( 4 ) 算法稳定性 对于一个任意的到达过程，如果预期的输入队列的长度不是无界的增加，则这个交换系 统是稳定的。也就是说，对于给定的业务流模式和算法，交换机如果能承受在固定范围内变 化的流量则，认为交换机处于稳定状态。 ( 5 ) 算法的迭代性 为在输人与输出端口间实现最大匹配我们把算法中基本操作重复执行的次数( 或步骤) 称为迭代( i t e r a t i o n ) 。迭代可分为申行或并行迭代两种形式，并行迭代是指同时发生在每个端 口的操作重复执行次数。在一个时隙内匹配算法可以迭代多次，算法的迭代性可以使交换结 构在一个时隙内完成更多的端口匹配。 3 东南大学硕士学位论文 ( 6 ) 硬件实现复杂度 一个交换结构的实现复杂度主要体现在控制逻辑和硬件数目上，交换结构规模的扩充 对硬件数目的增长速度是硬件数目上的复杂度表现。在v o q 算法中，硬件复杂度一般呈 现多项式阶d 口咖。硬件实现的复杂度包括需保持大量的时序状态、由状态作出的逻辑请 求与决定、在每一个时隙开始和结束时的用通信请求去更新的状态。 目前，i q 交换中基于v o q 结构的调度算法主要分为两大类：极大尺寸匹配算法 ( m a x i m a ls i z em a t c h i n g ：m s m ) 和极大权匹配算法( m a x i m a lw d g h tm a t c h i n g ：m w m ) 。 前者以p d 2 】，r r _ n 4 3 ) ，i s l i p t 4 ) ，和f i r m 5 1 等为代表，硬件实现简单，然而与极大权匹配 算法相比，其性能表现却不容乐观。后者以l q # j ，o c f 【1 以及l p f 【8 1 等算法为代表，他们 在绝大多数流量模式下都能很好的满足低延迟与大吞吐量的性能要求，然而由于硬件电路 难以实现，很难在实际中应用。 1 2 1 极大尺寸匹配( m s m ) m s m 是指匹配边数达到极大的匹配算法，这些算法具有实现简单、运算速度快等优点， 但算法一般要经过多次迭代才能找到极大匹配，每次迭代包括3 个步骤。调度开始时，所有 的输入和输出都初始化为未匹配，只有那些一次迭代后尚未实现匹配的输入和输出才能留到 下一次迭代。这3 个步骤是： ( 1 ) 请求( r e q u e s t ) ：每个未完成匹配的输入端口向它的队列中包需要到达的输出端口发 送请求信号。 ( 2 ) 应答( g r a n t ) ：一个输出端口可能收到多个输入端口发来的请求信号。每个尚未完成 匹配的输出端口从收到的请求中选择一个输入端口并向其发送应答信号。 ( 3 ) 接受( a c c e p t ) ：每个未完成匹配的输入端n 可能收到多个输出端口的应答信号。输 入端口从应答信号中选择一个输出端口并向其发送接受信号。 m s m 中的p i m - a r a l l e li t c r a f i v em a 埘1 j n g ) 例是第一个采用多次迭代实现输入捧队调度 的算法。它利用随机方法选择请求或应答信号。p i m 平均经过o ( 1 0 9 n ) 次迭代后收敛到极 大匹配，并且能够保证所有的请求会被响应。但存在以下不足：首先，在高速情况下实现 随机选择存在一定的困难9 j 。其次，对非容许的通信量，它可能导致连接闻的不公平。最 后，在单次迭代的情况下，只能达到6 3 的吞吐率，仅略高于f i f o 队列。 r r m ( r o u n dr o b i n m a t c h i n g ) 算法采用轮转优先算法调度输入和输出端口。在r r m 算法 中，每个输出入端口有一个跟踪最高优先级输入出端口的响应艘受指针。r r m 算法的主 要机制是：在上述的第( 2 ) 步，输出端口按固定轮转顺序从它的优先级列表中选择当前优先 级最高的元素，然后通知所有输入它的请求是否被响应。指向最高优先级的响应指针增加 1 ( 模n ) ，移到下一个位置。在第( 3 ) 步，输入端口按固定轮转顺序从它的优先级列表中选择 当前优先级最高的元素，然后发出接受信号。指向晟高优先级的接受指针增加l ( 模n ) ，移 到下一个位置。r r m 解决了p i m 中的两个问题：过于复杂和不公平。但是在高负载下， r r m 会变得不稳定，原因在于输出端口响应指针更新的规则不够合理，在负载较高的情况 下会出现同步现象，所谓同步现象就是多个输出端的响应仲裁器指针指向同一输入端的现 象，由于一个输入端1 次只能接受多个输出应答中的一个，从而导致调度效率下降，r r m 的最大吞吐率只能达到5 0 。 i s l i p ( i t e r a t i v es l i p ) 算法在r r m 的基础上进行了改进，主要是减少同步现象的发生。 i s l i p 与r r m 不同之处在于第( 2 ) 步：输出端口的响应指针只有在被输入端接受后才移到下 一个位置。与p i m 算法相比，i s l i p 算法的主要优点是均匀流量下具有高吞吐率且实现简 4 第一章绪论 单。实验结果表明，在均匀的独立贝努利流量分布( b u m o u l l ii i d ) 下，即使是单次迭代，i s l i p 算法也能达到1 0 0 的吞吐率，明显高于p i m 算法。 其它m s m 算法还有f i r m 和d r r m ( d u a lr o u n dr o b i nm a t c h i n g ) t o l 。f i r m 与i s l i p 的 不同之处在于：当输出端口的响应信号被输入端口拒绝时，响应指针将指向该输入端口， 从而保证该输入端口的请求信号在下一个时问片内被优先响。d r r m 算法只需要两次信号 交换，即请求和响应。 1 2 2 极大权匹配( m w m ) m w m 顾名思义，即每轮调度从若干组匹配组合中选取权值最大的一组组合做为调度 结果的匹配算法。根据权值计算标准的选择，主要的m w m 算法分为l q f f l o n g e s iq u e u e f i r s t ) a p 晟长队列优先，o c f ( o l d e s tc e l lf i r s t ) e p 最久信元优先以及l p f ( l o n g e s tp o r tf i r s t ) 的最久端口优先三种。 设s 撕) 为t 时刻的匹配矩阵，s 0 t ) = l 代表在t 时刻调度器输入端口i 与输出端口j 之 间存在连接。w ( 0 为匹配s 0 ( t ) l 臼权，则w ( f ) = z 口s a t ) + q ( t ) t , j o ，其中q ( 力为定义的权值。 例如，l q f 中q ( f ) 代表当前待匹配队列的长度，o c f 、l p f 中q ( f ) 代表当前各匹配队列的 等待时间等。在计算出一组匹配的权值w ( 0 后，算法对各权值进行比较，从中选取权值最 大的一组作为调度结果。 对于按b u r n o u l l ii i d 方式到达的均匀流量，m w m 算法可以实现1 0 0 o 的吞吐量，具 有很低的调度延迟，但是其算法复杂度高达o ( 砘昭“) ，其中n 为交换端口数，在高速电 路中尤其难以硬件实现。 1 3 本文主要研究内容和结构安排 本课题的研究背景是国家自然科学基金项目。高性能可扩展网络调度系统”+ 。众所周 知，下一代网络不仅需要更大的容量和更多的端口，而且对交换的延迟、吞吐率和公平性 等性能也提出了更高的要求：一是要能处理更多的端口，二是能实现更高的端口速率，三 是能支持更高级的服务方式。因此，在调度算法更新的同时，有必要研究发展具有更高性 能的网络调度系统。目前，虽然交换机和调度器都有成功开发的集成电路芯片，但大多都 是由国外厂商研制的，其核心技术和知识产权也掌握在国外开发商的手中，而且受到单个 芯片规模、i o 管脚数、功耗等集成电路工艺因素的限制，单片i c 上所能实现的交换容量 和调度容量都是有限的( 如通常只能实现3 2 x 3 2 ) ，要想在单片集成电路上实现更大规模的交 换和调度功能( 如2 5 6 x 2 5 6 ) 就十分困难。因此，有必要研究出一种新的调度结构以满足下一 代网络交换所需的多端口、大容量的要求。高性能可扩展网络调度系统f s s a j 1 正是针对 这一问题提出的。f s s a 甩若干较小规模的调度器实现了难以在单片电路上实现的大规模 调度器。 本文研究的主要内容之一就是高性能公平可扩展网络调度结构f s s a 的f p g a 实现， 具体为采用4 片x i l i n xv e r t e x - 4 系列f p g a 实现了基于f s s a 的高速6 4 x 6 4 可扩展网络调 度系统，仿真结果表明该系统功能正确，单通道速率可达$ 0 0 m b p s 。 本文的另一主要工作就是在对目前调度算法充分分析的基础上，提出了自适应双阈值 的s a t r r ( s e l f - a d a p t i v et h r e s h o l d b a s e dr o u n d - r o b i n ) 算法，该算法使得具有较长等待时间 的包以及处在较长队列的包优先调度，从而降低了调度器的延迟尤其是非均匀流量模式下 田家自爨科学基金项目( 6 0 4 7 2 0 5 7 ) 5 东南大学硕士学位论文 的延迟，获得了性能和实现复杂度的良好折中。 本文的结构安排如下： 第二章介绍了本文提出的双阈值自适应调度算法s a t r r 及其仿真结果。 第三章先简单介绍了f s s a 及其工作原理。然后重点介绍了f s s a 各主要功能模块的 硬件结构设计。 第四章介绍x i l i a x 开发工具及v t r t e x - 4 系列芯片。 第五章介绍了基于v l r t e x - 4f p g a 的f s s a 硬件实现及实现结果分析。 第六章给出了f p g a 的测试验证系统。 第七章对全文进行总结，指出了待进一步要研究的工作及建议 最后是致谢和作者攻读硕士学位期间发表的论文。 参考文献 i l ln ，m c k e o w n , a m e k k i t t i k 【l l l va n a n t h a r a ma n dj w a l r a n & a c h i e v i n g1 0 0 t h r o u g h p u t i na ni n p u t - q u e 删s w i t c h c 】i e e e 删c o m , 1 9 9 6 【2 】n m e k e o w n , i s l ：as c h e d u l i n ga l g o r i t h mf o ri n p u t - q u e ds w i t c h e s 【qi e e e t r a n s a c t i o n s o n n e t w o r k i n g , a p r i l1 9 9 9 ，v o l7 。n o 2 ， 3 】d n s c r p a n o sa n dp l a n t o n i a d i s ，嗣 r m ：ac l a s so f d i s t r i b u f i o ns c h e d u l i n ga l g o r i t h mf o r h i g h - 删a t ms w i t c l m s 谢t l l m u l t i p l e i n p u t q u e u e s 【c 】i e e e i n f o c o m , 2 0 0 0 4 1t a b a m b a e e 、t a s s i u l a slm n c m ，ab o wc l a s so fe f f i c i e n ts c h e d u l i n ga l g o r i t h r u sf o ri n p u t b u f f e r e dg w i t c h e sw i t hn os p e e d u p 【c 】i e e ei n f o c o m s a nf r a n c i s c o ：i e e e c o m m u n i c a t i o n ss o c i e t y , 2 0 0 3 1 4 0 6 - 1 4 1 3 【5 】y m gj i a n ga n dm h a m d i ，af u l l yd e s y n c h r o n i z e dr o u n d - r o b i nm a t c h i n gs c h e d u l e rf o ra v o qp a c k e ts w i t c ha r c h i t e c t u r e c 】1 e e ew o r k s h o po nh i g hp e r f o r m a n c es w i t c h i n ga n d r o u t i n g , 2 0 0 1 ，p p 4 0 7 - 4 1 1 【6 】a n d e r s o nt ，o w i c k is ，s a x e sj ，t h a c k e rc h i g hs p e e ds w i t c hs c h e d u l i n gf o rl o c a l 蚴 n e t w o r k s 【j 】ja c m t r a n s a c t i o n so hc o m p u t e r s y s t e m s ，1 9 9 3 ，1 1 ( 4 ) ：3 1 9 - 3 5 2 【7 】as e l f - a d a p t i v et h r e s h o l db a s e ds c h e d u l i n ga l g o r i t h mf o ri n p u t - q u n e ds w i t c h e s c i e e e h p s r 2 0 0 6 p 3 2 9 ( 2 0 0 6 ) ( 第一作者) 【8 】m e k k i t t i k u ia ，m c k e o w nn as t a r v a t i o n - f r e ea l g o r i t h mf o ra c h i e v i n g1 0 0 0 6t h r o u g h p u ti n i n p u t - q u e u e ds w i t c h e s i n ：l e ed e d p r o c e e d i n g so f t h em e e i n t e r n a t i o n a lc o n f e r e a c e0 1 1 c o m p u t e rc o t r m a u n i c a t i o n sa n dn e t w o r k s c i e e ec o m m u n i c a t i o n ss o c i e t y , 1 ”6 2 2 每之3 1 【9 】c h a oi l l s a t u r n ：at e r a b i tp a c k e ts w i t c hu s i n gd u a lr o u n dr o b i n 阴i e e ec o m m u m c a a o n s m a g a z i n e , 2 0 0 0 ，3 8 ( 1 2 ) ：7 8 - 8 4 【1 0 】吴俊，陈晴，罗军舟，时隙间迭代的输入队列交换机r o u n d - r o b i n 调度算法【j 】嚣斧学 援, 2 0 0 5 ，1 8 ( 3 ) ：5 6 - 5 9 6 第二章s a t r r 算法的设计与仿真 第二章s a t r r 算法的设计与仿真宰 本章主要介绍作者提出的自适应双门限调度算法s a t r r 。首先对s a t r r 算法的设计 出发点作了简单描述，之后阐述了s a t r r 算法的基本原理。最后给出了s a t r r 该算法的 c 语言实现的仿真结果。结果表明，与其它m s m 算法相比，s a t r r 算法在多种流量模式 下均取得较好的性能且具有较低的实现复杂度。 2 1 引言 近年来，许多应用于i q 交换的调度算法相继被提出。在i q 交挟中，虚拟输出队列