（通信与信息系统专业论文）高速网络流量调度算法设计与实现.pdf

摘要 p 37 6 4 2 0 为了在高速网络中给用户提供可靠的端到端服务质量保证，通常需在网络的中继节点中 引入有效的流量调度机制。当前如何在f 一代路由器与a t m 交换机中实现基于硬件的高效 输出队列调度机制从而支持大量具有不同业务参数与q o s 需求的业务流对网络输出带宽等 资源的公平复用已受到广泛关注。在各种分组公平队列调度算法中，w f 2 q + 队列调度算法 是一种性能优异同时又易于实现的公平队列调度算法f 论文首先介绍了各种主要的流量调度算法以及调度算法研究的发展趋势，然后重点介绍 高速网络( 如i p 网络、a t m 网络) 中的流量调度算法的硬件高速实现机制。 r 在a t m 网络中，论文中提出一种基于流量整形的a t m 公平队列凋度器设计。该设计 通过引入速率f i f o 结构实现了整形器中的有效流聚类，从而降低了整形队列维护的复杂度。 同时智能分组移动策略的引入有效消除了整形器与调度器间的分组移动瓶颈。 针对支持变长分组的高速网络( 如i p 网络) 论文提出一种基r 离散预约速率与分组长 度组单元的公平队列调度器实现结构。该结构可根据不同预约速率需求，为其方便灵活的提 供不同的预约带宽实现精度。组单元的模块化设计结构与流水线设计技术使得硬件逻辑资源 得到更有效的利用。文中同时提出一种适用r 该实现结构的定点时标重构技术，利用该技术 可有效节约存储流时标的所需的外部存储空间。论文中同时提出了一种基于统计移位排序结 构的w f 2 0 + 算法高速硬件实现方法，该方法充分利用队列的统计信息，以相对少的硬件资 源实现统计意义上的快速完全排序。此外，论文中还提出一种适于硬件高速实现与维护的流 状态信息表设计方案。该表的数据结构设计可有效支持基于流的输出调度机制与缓存管理机 制。 论文的最后介绍了一个实际设计的w f 2 q + 调度器的算法仿真与f p g a 实现结构。该设 计使片ja l t e r a 公司的a p e x 2 0 k 4 0 0 e ：占片与c y p r e s s 公司的c y 7 c 1 3 5 0 静态r a m 芯片，可 支持3 2 k 流队列，支持的预约速率变化范围为6 4 k b s 至1 5 5 m b s 支持的分组长度变化范 围为2 3 字节至4 3 2 5 字节。集成服务间隔调度实现结构与时隙调度机制有机结合便于殴计中 采用定点时标表示与比较。时标的“刷新”机制有效解决了定点时标表示中存在的时标值“溢 出”问题。时序仿真结果表明该设计调度i p 分组的平均速率为1 2 g b s ，可支持2 个o c 1 2 的p o s 接口。为了提高速率，调度器中利用芯片的片内r a m 实现了一个查询表该表保 存了l ，“r 的各种数值，从而避免了实现一个复杂的乘法模块。此外，我们还提出r 一种利 用低速调度器合成高速调度器的方法，用以支持更高的链路速率( 如2 4 g b s ) 。 论文中的部分内容分别发表在通信学报、i e e e a p c c a s 与i f i p w c c 2 0 0 0 i c c t 2 0 0 0 等 国际会议中，并被计算机学报与小型微型计算机系统等学术刊物录用。、：、一 以、 a b s t r a c t t op r o v i d er e l i a b l ee n d 。t 0 - e n dq u a l i t yo fs e r v i c eg u a r a n t e e sf o rt h en e t w o r kb s e r s ，i ti s n e c e s s a r yt oi n t r o d u c es c h e d u l i n ga l g o r i t h m si n t ov a r i o t i sn e t w o r kn o d e s r e c e n t l ym u c hr e s e a r c h a t t e n t i o nh a sb e e nf o c u s e do ni m p l e m e n t i n ge f f i c i e n ts c h e d u l i n gm e c h a n i s mi nn e x tg e n e r a t i o n a t ms w i t c h e sa n dr e u t e r st os u p p o r tt h eh i g l ls p e e dm u l t i p l e x i n go f a l a r g en u m b e r o ff l o w sw i t h d i v e r s et r a f f i cp a r a m e t e r sa n dq o sr e q m r e m e n t so v e rt h es a m en e t w o r ki i n k a m o n ga l lo ft h e p a c k e t - f a i r - q u e u i n g - r e l a t e ds c h e d u l i n ga l g o r i t h m s ，w f o + h a st h em o s te x c e l l e n tp e r f o r m a n c e a n dc a l lb c e a s i l yi m p l e m e n t e d a tt h es a m et i m e i nt h i st h e s i s w ef i r s ts u r v e yt h ed i v e r s es c h e d u l i n ga l g o r i t h m sa s ；w e l l t h ef u t u r et r e a d si n t h er e s e a r c ho ft h i sa 陀a 1 r h e nt h i st h e s i sf o c u s e so nt h ed e s i g na n di m p l e m e n t a t i o no ft h e h a r d w a r e - e f f i c i e n ts c h e d u l i n g a l g o r i t h m s 1 na t ms c e n a r i o w ed e s i g naa t ms c h e d u l e r st os c h e d u l ea t mc e l l sw i t hf i x e di e n g r h s t h i s d e s i g nr e d u c e st h ee o m p l e x i t yf o rm a i n t a i n i n gs h a p i n gq u e u e sb yu s i n gr a t ef i f oa r c h i t e c t u r e st o i m p l e m e n tt h ee f f e c t i v ea g g r e g a t i o n so f t r a f f i cf l o w s t h eu s i n go f i n t e l l i g e n t l ym o v i n gp o l i c yo f p a c k e t se l i m i n a t e st h eb o r l e n e c kf o rm o v i n gp a c k e t sb e t w e e nt h es h a p e ra n dt h es c h e d u l e r 【nh i g h - s p e e dn e t w o r k ss u p p o r t i n gp a c k e t sw i t hv a r i a b l el e n g t h s ，s u c ha si p c e n t r i cn e t w o r k s ， w ef i r s tp r e s e n t sa ne f f e c t i v ei m p l e m e n t i n ga r c h i t e c t u r eo f p a c k e t - f a i rq u e u i n gs c h e d u l e r sb a s e d o nd i s c r e t eb a c k l o g g e dr a t e sa n dd i s c r e t ep a c k e tl e n g t h s t h i sa r c h i t e c t u r ec a nf l e x i b l yp r o v i d e d i f f e r e n tb a n d w i d t hg r a n u l a r i t i e sf o rv a r i o u sb a c k l o g g e df l o wr a t e s w i t ht h em o d u l a r i z a t i o n d e s i g na n dp i p e l i n et e c h n o l o g y , t h i sa r c h i t e c t u r em a k e s m o r ee f f i c i e n tu s i n go f h a r d w a r er e s o u r c e s w ea l s op r o v i d ean e wt e c h n o l o g yo f r e c o n s t r u c t i n gf l o wf i m e s t a m p sf o rt h i sa r c h i t e c t u r ew h i c h c a l le f f e c t i v e l yd e c r e a s et h es t o r a g es p a c e o f t i m e s t a m p s t h e n w e p r o v i d eah i g h - s p e e d w a r e i m p l e m e n t a t i o no fw f ( pa l g o r i t h m b a s e do ns t a t i s t i c a ls h i r - r e g i s t e r i n g - s o r t i n ga r c h i t e c t u r e s b y m a k i n gf u l l u s eo ft h es t a t i s t i ci n f o r m a t i o no fe a c hq u e u e , h i g h s p e e da n dc o m p l e t es o r t i n g o p e r a t i o n si ns e u s eo f s t a t i s t i c sc a l lb ei m p l e m e n t e dw i t hl e s sh a r d w a r er e s o u r c e 1 1 1 i st h e s i sa l s o p r e s e n t sah a r d w a r e - b a s e dd e s i g no fp e r - f l o ws t a t e i n f o r m a t i o nt a b l e t h ed a t as t r u c t u r eo ft h i s d e s i g nc a ne f f e c t i v e l ys u p p o r tt h em e c h a n i s m so f q u e u e ss c h e d u l i n ga n d b u f f e rm a n a g e m e n t a tl a s t ，w ef o c u so nt h es i m u l a t i o na n di m p l e m e n t a t i o no faw q + s c h e d u l e ru s i 雎 f i e l d - p r o g r a m m a b l e g a t e - a r r a y ( f p g a ) d e v i c e s o u rd e s i g nc a l ls u p p o r t3 2 k f l o wq u e u e sw i t h b a c k l o g g e dr a t e sr a n g i n gf r o m6 4 k b st o1 5 5 m b sa n dp a c k e t sl e n g t h sr a n g i n gf r o m2 3b y t e st o 4 3 2 5b y t e sb yu s i z a ga l t e r 丑a p e x 2 0 k 4 0 0 ed e v i c ea n dc y p r e s sc y 7 c 1 3 5 0s r a m d e v i c e s b y e f f i c i e n t t yc o m b i n i n gt h ei n t e g r a t e d s e r v i c ei n t e r v a l g r o u p a r c h i t e c t u r ew i t ht h et i m es l o t m e c h a n i s mt of a c i l i t a t et h e i n t e g e rp r e s e n t a t i o n o ft i m e s t a m p sa n dt h et i m e s t a m pp u r g i n g m e c h a n i s mt os o l v et h e o v e r f l o w p r o b l e mo fi n t e g e rt i m e s t a m p s ，t i m i n gs i m u l a t i o ns h o w so b r d e s i g nc a np r o c e s si pp a c k e t sa t1 2 g b sw h i c hi sc a p a b l eo fs u p p o r t i n gt w oo c l2p o sm e d i a i n t e f f a e e s t or a i s et h es p e e d al o o k u pt a b l ei si m p l e m e n t e di no n - c h i pr a mt os t o r ev “o u sv a l u e s o fl ，r ii n s t e a do f i m p l e m e n t i n gt h ec o m p l e xm u l t i p l i c a t i o nm o d u l e w ea l s op r o v i d eaw a y t o c o m b i n es e v e r a ll o w s p e e ds c h e d u l e r st os u p p o r tah i 曲- s p e e dl i n k , s u c ha s2 4 g b p s s o m e p a r t so f t h i st h e s i sh a v eb e e np u b l i s h e di nj o u r n a lo f c h i n e s e c o m m u n i c a t i o ni n s t i t u t e , t h e2 0 0 0i e e ea s i ap a c i f i cc o n f e r e n c eo nc i r c u i t sa n d s y s t e m ( a p c c a s2 0 0 0 ) ，n 1 6 “i f i p w o r l dc o m p u t e rc o n g r e s s 2 0 0 0i e e ei n t e r n a t i o n a lc o n f e r e n c eo nc o m m u n i c a t i o nt e c h n o l o g y a sw e l la sa c c e p t e db yc h i n e s ej o u r n a lo f c o m p u t e r sa n dm i n i - m i c r oc o m p u t e rs y s t e m 中国科学技术大学硕士学位论文第1 章引言 第1 章引言 近年来高速分组网络正逐步代替基于线路交换的电话服务网络而成为标准通信方式。随 着网络应用的多媒体化与高速化，作为传统的数据传输载体的计算机网络，其角色也正在发 生变化。视频会议、远程教学、实时音视频、电子邮件、传真与分布式系统等多种应用的普 及，链路速率与网络用户的急剧增长，以及高速网络体系结构本身由集成服务网络1 2 4 】 ( i n t s e r v ) 向区分服务网络m ( d i f f - s e r v ) 的演化等诸多因素在为现代通信体制带来深刻 变化的同时，也使得对高速网络中网络带宽等各种资源如何进行有效管理与控制成为一个挑 战性的课题。 这一领域的研究表明，很多资源管理策略的实施与改进都涉及一个关键的网络结构部件 流量调度器( t r a f f i cs c h e d u l e r ) 。因此解决这一课题的关键之一可归结为：如何设计并 高速实现一个可为网络中的各种应用提供可靠服务质量保证的公平且高效的流量调度算法， 这也正是本论文各章节所要论述的中心内容。 本章第1 节介绍当前高速网络中流量的公平调度算法及其研究的发展趋势：第2 节介绍 本论文在高速网络流量调度算法研究与实现方面的创新与贡献；第3 节简要介绍论文备章节 论述内容与组织结构。 1 1 高速网络流量调度算法介绍 传统的计算机网络特别是大型的广域互联网络( 如因特网) 只能支持无服务性能要 求的所谓“尽力型”( b e s te f f o r t ) 服务，这种服务模式是由传统的计算机网络传输技术及其 互连体系结构所决定的。8 0 年代中期以来，在国际计算机网络研究领域广泛的开展了以支 持实时多媒体传输为目标的新型网络体系结构研究。研究的主流集中在如何构造一种基于分 组交换技术的集成服务网络口“( i n t e g r a t e ds e r v i c en e t w o r k ) 这一核心问题上。在集成服务网 络中网络不仅可丝提供无服务性能要求的的传统“尽力型”服务模式，同时也能支持有完 全的服务性能保证( 确保型服务) 和一定服务性能保证( 部分确保型服务) ( 如因特网的 g u a r a n t e e ds e r v i c e s l c o n t r o l l e dl o a ds e r v i c e s ) 的服务模式，从而使网络用户的应用可以以一 定的端到端性能参数，如时延抖动、带宽、分组丢失率等，来要求网络提供其所需要的服务。 相关的研究表明，为了达到提供集成服务这一目标，必须对传统的计算机网络从功能到体系 结构上进行必要的扩展，包括引入端系统和中继系统的接入控制机制( a d m i s s i o nc o n t r o l m e c h a n i s m ) 和资源预留协议( r e s o u r c er e s e r v a t i o n p r o t o c 0 1 ) 引入描述网络流量的流量描述 模型及其描述参数( t r a 陌cm o d e l t r a t t t cs p e c i f i c a t i o np r o t o c 0 1 ) 并进行一定的网络流分类 ( f l o wc l a s s i f i c a t i o n ) 。除此之外，极为重要的一点就是要在网络的各中继系统中，实现对 不同流所属分组进行调度的分组调度机制( p a c k e ts c h e d u l i n gm e c h a n i s m ) ，以使得各个流的 分组之间不会相互干扰，避免网络性能和分组转发性能因网络拥塞而造成的下降，并同时使 得具有不同服务性能要求的流所属分组，在中继系统进行分组转发时，获得与其要求相适应 的分组转发性能。流量调度( t r a f f i cs c h e d u l i n g ) 算法研究就是上述分组调度机制理论研究 的核心问题。对于流量调度算法的研究已经开展了多年，其中先后主要存在两条不同的研究 思路，一是从网络的拥塞控制研究角度出发，研究中继节点的调度算法，以研究调度算法与 网络流量特性的相互影响为主要研究方向；而从9 0 年代以来特别是在集成服务网络相关 研究成为研究热点之后，产生了以研究调度算法对网络集成服务的不同服务模式提供性能保 证为出发点的另一研究思路。 中国科学技术大学硕士学位论文第l 章引言 1 1 1 相关的研究背景| 1 2 , 1 3 1 1 1 1 1 基本的网络模型与服务模型 基本的网络模型：研究集成服务网络所使用的基本网络模型是：假定网络由任意数目的 主机、链路与中继节点构成，其拓扑结构是任意的。排队行为只发生在中继节点的输出端口。 在最基本的情况下，假定所有的输出链路都是速率恒定且无差错的，中继节点输出端口的排 队输出由一个恒定速率的单服务器提供调度服务。网络中允许变长分组。 基本的服务模型：除了维持原有的传统“尽力型”服务外，还包括了确保型服务和部分 确保型服务。在提供确保型服务时，用户应向网络提交其应用的流量特性参数和服务性能参 数，网络通过接入控制机胄4 来确定是否允许用户使用其所需的服务。一旦达成约定，则这种 台约关系一直维持到应用数据传输结束为止。对于部分确保型服务来说它与确保型服务的 主要区别在于：1 ) 对于部分确保型服务而言，其所对应的接入控制算法使用的参数不是事 先确定的特征值而是依赖于对参数的观测值这样当网络负载发生变化时这些观测值也 发生改变。因此部分确保型服务的接入控制机制允许不是完全可靠的服务约定。2 ) 由于上 述接入控制的部分可靠性质，其所保证的服务性能参数往往只能满足一定的统计可靠性质， 即其服务性能参数完全符合服务约定的概率小于等于l 。 1 1 1 2 研究所使用的流量模型 在集成服务网络的相关研究中，提出了以流量的包络( t r a f f i ce n v e l o p e ) 来描述流量而 不是精确的描述流行为的一类流量描述模型。这样描述的好处在于避免了纠缠于具体而复杂 的网络流量精确模型问题，而能够以所使用的包络模型在一个有效的范围内讨论流的各种处 理性能。这类模型主要包括： 1 ) ( o ，p ) 模型【1 8 1 ( 也称漏桶模型，l e a k y b u c k e tm o d e l ) 。模型的含义是符合本模型 描述的流在任意时段u 内所产生的流量不太于o + p + 。因此口和p 可以看成是流的最 大突发尺度和产生流量的上界速率。 2 ) ( y ，t ) 模型口“。本模型的含义是符合本模型描述的流在任意时段内t 内，所产生 的流量不大于y + t 。 3 ) ( x 。- m x 。，i ，s 。) 模型【2 7 j 。本模型的含义是符合本模型描述的流中分组同时满足 以下条件：任意两相邻分组之间的到达时间间隔必须大于x 。：在任意的长度为i 的时段内， 相邻分组的到达时间间隔均值必须大于x 。：流中的最大分组长度必须小于s 。 4 ) d b i n d ( d e t e r m i n i s t i cb o u n d i n gi n t e r v a l l e n g t hd e p e n d e n t ) 模型p ”。在本模型描述 中可以使用系列的速率间隔对( r k ，i k ) 表示流的流量特性。每一个( 风，i k ) 对表示的 是在每个i k 时间段中流的晟坏情况速率大于凡。 5 ) s - b n d ( s t o c h a s t i c b o u n d i n g i n t e r v a l - l e n g t h d e p e n d e n t ) 模型”。本模型用 ( r t l 。t 1 ) ( r a j ，t 2 ) ( r 州，t 3 ) 来描述流j ，其中j 是随机变量t l q 2 o 2 中国科学技术大学硕士学位论文第1 章引言 均成立。其中a i r l t 2 】为表示流在时段ht 2 】内所产生的流量之和的随机变量。 7 ) f c ( f l u c t u a t i o n c o n s t r a i n e d ) 模型。一个流称为是满足具有参数为( c 6 ( c ) ) 的f c 模型的，当且仅当a ( t i ，t 2 ) c ( t 2 一t i ) 6 ( c ) ，其中a ( i ，t 2 ) 表示流在时段i t i ，t 2 】 内所产生的流量之和。 1 1 2 流量调度算法介绍 1 1 2 1 流量调度算法分类 根据网络节点中的调度器在流队列非空时是否处于持续工作的状态可将集成服务网络 中的流量调度算法分为两大类：1 ) 持续工作型( w o r k - c o n s e r v i n g ) 调度算法；2 ) 非持续 工作型( n o n w o r k - c o n s e r v i n g ) 调度算法。在持续调度算法规则下，当有分组要发送时， 调度器不会处于空闲状态。在非持续调度算法规则下，每个分组被赋予一个合格( e l i g i b i l i t y ) 时间。如果某个时刻调度器中没有合格分组，即使调度器处于空闲状态，分组也不会被发送。 这里两种规则影响了端到端延时分析，缓冲空间要求，以及延时抖动特性。 根据流量调度算法所采用的分组选择策略，调度算法分成以下三类i i m ：1 ) 采用s f f ( s m a l l e s tv i r t u a lf i n i s ht i m ef i r s t ) 规则。采用这种规则，算法从所有的队列的队头分组中 选出具有最小结束服务时间的分组进行服务。w f q ( w e 岫t e df a i rq u e u e i n g ) 算法“”采用 的就是这种方式。2 ) 采用s e f ( s m a l l e s tv i r t u a ls t a r tt i m ef i r s t ) 规则。采用这种规则算法 从所有的队列的队头分组中选出具有最小开始服务时间的分组进行服务。3 ) 采用s e f f ( s m a l l e s t e l i g i b l e v i r t u a lf i n i s h t i m ef i r s t ) 规则。在这种方式下，只有分组的开始服务时闻 小于等于p ( t ) ，分组才有资格被发送。算法从所有有资格被发送的分组中选出具有最小结束 服务时问的分组进行服务。 i i 2 2w o r k - c o n s e r v i n g 型调度算法 很多w o r k - c o n s e r v i n g 类算法都是采用类似的排序优先级队列机制。在这种机制中，采 用状态变量来管理各流队列。在对应的连接中的各分组到来时，状态变量根据下列因素来更 新：i ) 在连接建立时保留的资源：i i ) 该连接与或其他连接在数据传输时流量的到达历史。 在更新机制中，各算法在两个方面有很大的不同：i ) 计算仅基于速率参数还是既基于速率 参数又基于延时：i i ) 更新是独立于系统负载的参数还是依赖于系统负载的参数。只采用一 个速率参数将会导致带宽和延时上的耦合问题。 1 ) g p s 调度算法”“ g p s ( g e n e r a l i z e dp r o c e s s o rs h a r i n g ) 调度算法是一种理想化的流体模型，w f q 一类的 分组调度算法就是模拟这种工作模型而提出的。g p s 算法基于如下两个假设：( a ) 分组长度 无限可分：( b ) 所有的流可以同时接受服务。假定共有n 个流共享一个输出链路r ；表示数 据流i 预约的速率r 表示输出链路的总容量，b ( t ) 是时刻t 所有等待调度的流的集合，w 。 ( t ，t ) 是时间( t ，t ) 内流i 所接受的服务。g p s 算法要求满足以下两个条件： ( 1 ) 各个流预约的速率总和应该不超过链路总容量r 即y r r _ i = 1 ( 2 ) 彬( r ，t ) r , = h ( r , t ) r j v i ，b ( f ) 中国科学技术大学硕士学位论文第1 章引言 利用以上定义可证明g p s 具有如下性质： ( 1 ) 调度的公平性，保证流所获服务同各数据流间相对权值( 即预约速率) 成正比，权 值高的流获得的服务多于权值低的流，过剩的带宽在当前等待调度的数据流间按比例共享。 亦即 若i ，n l j w , ( r ，f ) 玎? ( r ，f ) v i ，丑( f ) ( 2 ) 预约带宽保证，保证各数据流能获得不少于其预约的带宽份额，从而保证端到端 时延。假定f 为流i 实际所获带宽，则 = r ( j = _ o ( t l o ) 2 ) w f q 调度算法” 在实际系统中，一个调度器一次只能为一个流服务，而且服务的最小单元为1 个分组， 因而g p s 算法的理想化条件是无法满足的。w f q ( w e i g h t e d f a i rq u e u i n g ) 调度算法就是在 实际系统中模拟g p s 算法而提出的。w f q 调度算法的基本思想是，当调度器准备发送一个 分组时。它在等待调度的所有分组中选取个与该w f q 调度系统相对应的g p s 调度系统 中晟先结束服务的分组进行发送( 两个调度系统是相应的指两个系统具有相同的输出链路带 宽预约的数据流也完全相同，只是它们各自以自己的假定进行调度) 。在w f q 算法的具 体实现过程中通常引入以下函数。函数v ( t ) 表示调度系统在时刻t 已经提供的服务( 该 函数也被称为系统的虚拟服务时间函数) 等待调度的流i 的队头分组为该数据流的第k 个 分组，其分组长度为l 。到达时刻为t ，s 。为分组在对应的g p s 系统中的开始接受服务的 时间计相应为结束服务时间。s 。、f , k 满足： = m a x ( f , k 。，y ( ，j ) ) f = + 肆， 当调皮器处r 空闲状态时系统的虚拟服务时间应该保持不变而在处j 。l ：作状态( 持续 发送分组的状态) 时的更新函数为： r ( + ) _ m a x ( 矿( ，) + 矿( ，+ r ) 枷m i + 1 n ( 墨( h f ) ) ) 可以证明w f q 调度算法能够保证分组结束服务的时间与相应的g p s 系统相比，至多 滞后发送该数据流的一个最长分组的时间在一个实际的系统中，仅仅从结柬服务时间而言。 w f q 调度算法已经具薪了毋住的性能参数。 3 ) w t 2 q 调度算法川 虽然w f q 调度算法可以保证对一个分组的调度不会滞后相应的g p s 系统很多。但是 却可能导致超前很多。因而从总体上而言，w f q 算法的调度结果会与相应的g p s 系统的调 度结果有搬人的筹异。其结果对于实时业务而言意味着虽然分组的延迟得到保证，但是却存 在很大的延迟抖动，也即数据流的突发度被增加了。这个影响对于一个中继性点是无所谓的， 但是互联网络是由许多中继节点构成的，如果每个肖点都采用这样的调皮器突发度增加的 累积效果就影响了最终的端到端的时延特性。w f i ( w o r s t - c a s ef a i ri n d e x ) 因子被用来来衡最 这个差异理想的g p s 系统的w f i 冈子为零。为了降低w f q 算法的w f i 因子， w f 2 q ( w o r s t - c a s e f a i r w e i g h t e d f a i r q u e u i n g ) 算法改变了w f q 算法选择分组的策略。与w f q 算法在所有等待调度的分组之中选择下一个要发送的分组不同，w f 2 q 算法首先需要对等待 调度的分组进行资格测试，只有开始服务时间小_ 丁系统的虚拟时间的分组才可以通过测试。 4 中国科学技术大学硕士学位论文第l 章引言 然后w f 2 q 算法在通过资格测试的分组中选择具有最小结束服务时间的分组进行发送，这 种策略称为s e f f ( s m a l l e s te l i g i b l ev i r t u a l f i n i s ht i m ef i r s t ) 分组选择策略。可以证明在从 w f q 衍生而得的各种算法中，w # q 算法具有最小的w f i 因子。从而可以使得由采用w f 2 q 算法的中继节点构成的网络，端到端的延迟抖动选到最小。 4 ) w f 2 0 一卜调度算法【1 0 j w f q 和w f 2 q 具有相同量级的复杂度从计算结束服务时间的公式可以看出，它们的 复杂度都为o f c ) v 为当前等待调度的流的数日，最坏情况下v = n 。为了简化算法的复杂 度。w l = z q + 算法重新定义了分组开始服务时间、结束服务时间以及系统虚拟时间的更新公 式。如下： 黔m a x ( v 。x 州r ”嬲嚣 f ( f ) = s ，( f ) + l ：i t , ：心( h 加= m “( ：口( 卅_ ，嚣斟e ( h r ) ) ) 其中f a t 一) 为该数据流的前一个分组的结束服务时间。w f 2 q + 算法的分组选择策略与w f 2 q 算法相同。通过重新定义各个参数的计算方法，w f 2 q + 算法将算法复杂度将为o ( i o g ( v ) ) 井且可以证明w f 2 q + 算法与w f 2 q 算法有一致的性能上界和公平度。 5 ) v c 调度算法p 2 1 v c ( v i r t u a lc l o c k ) 调度算法采用类似t d m 系统的方法来解决的。对每一个连接，系 统根据对带宽的请求米给到达的分组打卜标签( 即服务时间) ，按该标签值的排州顺序对备 队列进行服务。服务时间的计算不依赖于其他连接。如果一个连接有违规的现象，即使这种 违规没有影响到其他连接，该连接都可能会受到惩罚。 6 ) s c f q 调度算法p ” s c f q ( s e l f - c l o c k e df a i rq u e u i n g ) 是为了减少在w f q 与w f 2 q 中计算系统虚拟时间 的复杂性而提出的。算法的依据是：在任何时刻t 系统虚拟时间都可以由当前止接受服务 的分组的虚拟时标来情计。虚拟时间函数v ( t ) 定义为当前正在服务的分组的服务虚拟结求时 间f 9 。59 q 9 。s9 和f 9 分别代表开始和结束服务的时间。s c f q 采用一种导致其性能与 w f q 系统的性能产生差异的虚拟时间计算公式： 喘一m 。 k ( 。b ) ，叫了1 卜 杀 7 ) d e l a y - e d d 调度算法 d e l a y - e d d ( d e l a y - e a r l i e s t d u e - d a t e ) 算法是传统e a r l i e s t - d u e - d a t e f i r s t ( e d do r e d f ) 算法的扩展。传统的e d d 算法是给分组规定一个时限( d e a d l i n e ) 时限是分组到达时间与 流的周期之希。分组是按照时限递增的顺序来发送的。i ) e l a y - e d d 给的扩展是加上了延时限 制，即该策略将保证连接建立时用于协商过程的延时。计算方法是分组的期望到达时间与坼 定延时之和。例如，假定发送分组的时隙为o 2 s 调度器的协定延时为1 s 则第k 个分组的 时限为o 2 k + l 。这是在满负荷f 的计算。在非满负荷f 采用到达时间+ 延时，该值将会大 于上一种计算方式。因此计算公式为： 中国科学技术大学硕士学位论文 第1 章引言 1 1 2 3n o n - w o r k - c o n s e r v i n g 型调度算法 控制流量模式扭曲的一种方法是在各交换机上采甩* w o c b c o n s e r v 吨型讽度算法。 在n o n - w o r k - c o n s e r v i n g 规则下，即使在有分组等待发送的情况下调度器也可以处于空闲 状态。在先前的研究中之所咀没有注重n o n - w o r k - c o n s e r v i n g 规则是由于：i ) 先前的研究主 要侧重于平均延时和平均吞吐量；i i ) 先前的队列分析都是基于单个调度服务器的。在性能 保证业务下，更重要的性能是端到端的延时范围而非平均延时。 在高速集成业务网络中，已提出了多种n o n - w o r k - c o n s e r v i n g 规则。其中有：j i t t e r e a r l i e s t - d u e d a t e ( j i t t e r - e d d ) 算法p “、s t o p - a n d g o 算法、h i e r a c h i c a lr o u n dr o b i n ( h r r ) 算法【，以及r a t e c o n t r o l l e ds t a t i cp r i o r i t y ( r c s p ) 算法【”i 等。下面介绍前两种调度算法。 1 ) j i t t e r - e d d 调度算法i j ” j i t t e r - e d d ( j i t t e r - e a r l i e s t - d u e - d a t e ) 规则扩展了d e l a y e d d 以提供延时抖动范围。当 分组在每个调度器中被服务之后，头中的一个域就被贴上标签，标记其时限( d e a d l i n e ) 与 实际结束时间的差值。下一个服务器的 口处有一个整形器将保持该分组到直到相应时刻， 才进行调度。 2 ) s t o p a n d - g o 调度算法i ”1 s t o p - a n d g o 采用帧策略。在该策略中，时间轴被分割成帧，即一些固定时间长度t 。 s t o p - a n d - g o 为每个链路定义了离开和到达帧。在各交换机中，每个输入链路上到达的帧都 被映射到输出链路的离开帧中，并且带来固定延时0 ，o o t 。根据s t o p a n d g o 规则， 在帧f 期间从任意链路l 到达的分组其发送应总是被延时到下一帧的开始。由于在输出链路 的帧f 中到达的分组必须等到下一帧才适合发送，输出链路就有可能在有帧等待发送时仍保 持为空闲。因此s t o p - a n d g o 也是n o n w o r k - c o n s e r v i n g 策略。 1 1 3 流量调度算法研究发展趋势 1 1 3 1 为交换结构提供q o s 支持的分布式队列调度算法 目前支持q o s 的调度算法大都是基于输出缓冲的，排队只发生在输出链路上。输出缓 存结构有两个问题：1 ) 对输出卡的存储器大小和速度要求高；i i ) 控制逻辑必须能以极高的 速率操作。这些问题在所有的，包括使用f i f o 来调度的策略中都存在。为降低成本和简化 实现高速路由器大都采用输入缓冲的方式，但这样导致在输入和输出端口都会发生竞争。 如果输入端口采用f i f o 缓冲，则在输入端口没有竞争的问题，但是带来了队头阻塞 ( h e a d - o f - l i n e ，h o l ) 。通过在输入卡处为每个输出端口分别设置一个队列，就可以消除 h o l 阻塞。许多研究都是注重在交换调度或者匹配算法以使吞吐量最大，很少有研究如何 在输入缓存的结构中提供q o s 。此外，目前的许多研究都是基于定长信元的，而高性能的支 持变长分组的交换机( 包括i p 和e t h e m e t ) 同样必须。 因此有必要研究适用于输入缓冲的队列调度算法。该方法除支持q o s 以外，还应达到 如下两个目标：有效支持变长分组和最大化交换内核的吞吐量( t h r o u g h o u t ) 。分布式分组 6 中国科学技术大学硕士学位论文第1 章引言 公平排队( d - p f q ) 结构不需要全局同步，可以高速地流水线实现。 图i 1 给出一种分布式调度实现结构p ”采用c r o s s b a r 来连接接口卡。在一般的实现结 构中，缓冲位于所有的三个潜在竞争点上：输入端口，输出端口，c r o s s b a r 内部。尽管在各 输入端口处为每个输出卡提供独立的缓冲区可以达到1 0 0 的交换吞吐量而不需要在输入 或输出增加额外的加速，但并不能充分地为每一个s e s s i o n 提供q o s 保证。而在下图的结构 中，输入端口卡的每个进程都有一个队列。在c r o s s b a r 内部，为每一个输入输出端口对提供 一个缓冲，这些访问缓冲区相对较小，以便集成在c r o s s b a r 芯片上。采用简单的c r e d i tf l o w 控制技术来管理对访问缓冲区的访问。只要缓冲区空间还能够发送一个最大长度( 内部)