（通信与信息系统专业论文）多级分组调度的性能仿真研究.pdf

摘要 随着因特网业务持续高速增长，新的用户不断接入因特网，用户要求 有更高的带宽并具有一定的q o s 保证。这种趋势对网络元素提出了新的要 求。为了适应这些要求，必须提供尽可能多的输入输出端口以满足大量用 户的连接，同时还要为这些连接提供一定的主要基于i p 网络的 q o s ( q u a l i t yo fs e r v i c o ) 服务。分组队列调度算法作为保障这些目标的重 要一环，特别是在q o s 的实现上目前具有不可取代的重要作用，因此有着 广泛的应用。在这类应用中，有很多采用了对目前通用的分组调度算法( 如 w f q 、p q 、m w r r 等，本文中称为单级分组调度算法) 进行组合，来满足用户 或网络灵活的q o s 要求，这就产生了复杂的多级分组调度算法( m u l t i - s t a g e p a c k e ts c h e d u l i n g ) ，由于目前关于多级分组调度算法的理论模型还不成 熟，因此多是采用单级分组调度算法的理论来确定多级中各级的调度算法， 这样的结果是在每一级的调度中取得了相对最优，但在多级联合以后却不 一定是性能最优的。所以分析多级分组调度算法的性能具有重要的工程意 义，本文的主要工作都以此展开。 我们在对因特网中q o s 服务的一般方案进行分析的基础上，尝试设计 了一种能较好满足因特网q o s 要求的两级分组调度模型。然后通过仿真， 具体测试此模型的性能，包括模型的分组时延( d e l a y ) 、时延抖动( d e l a y j i t t e r ) 、缓存分组所需要的存储器大小( b u f f e rc a p a c i t y ) 以及同样大小 的存储器时分组丢失情况( 丢失率1 0 s sr a t e ) ，从而通过仿真分析确定出优 选的两级调度方案为d w r r m w r r 。 为完成多级分组调度模型的仿真分析。我们编写了o p n e t 平台上的单 级分组调度通用仿真程序。这是在分析各种常用的单级分组调度算法基础 上，提取各个分组调度算法实现的共同点，然后通过数据结构的封装和不 同算法函数的重载来实现。它是本文工作的一个重要组成部分，多级分组 调度模型即以此通用模块为基础搭建。这个通用模块也为以后的分组调度 算法研究，以及这方面的通信设计提供了一个快速的仿真测试实现工具。 关键词：分组，多级调度，仿真 a b s t r a c t w i t ht h ec o n t i n u o u s l yr a p i di n c r e a s i n go fi n t e r n e ts e r v i c e s ，a sm o r ea n dm o r e u s e ra c c e s si n t e r n e t ，c o n s u m e rn e e dm o r eb a n d w i d t ha n dq o s t h i sl c a dan e w r e q u i r e m e n tt o t h e e q u i p m e n ti n i n t e r n e t t os u i tt h et e n d e n c y ，t h ee q u i p m e n t m u s th a v eal o to fp o r tt ol i n km a n yu s e r s ，a n dh a v et oo f f e ro o ss e r v i c ef o r t h e s eu s e r s t oo b t a i nt h e s e g o a l ，p a c k e ts c h e d u l i n ga l g o r i t h mi s o n eo ft h e m o s t i m p o r t a n tm e t h o d ，e s p e c i a l l y i nq o sg u a r a n t e ei ni pn e t w o r k n o w ， m a n u f a c t u r e r sa l w a y sc o m b i nt h eg e n e r a lp a c k e ts c h e d u l i n ga l g o r i t h m ，s u c ha s w f q ，p q ，m w r ra n ds oo n ，t os u i tt h ea g i l er e q u i r e m e n to fq o ss e r v i c e t h i s l e a dac o m p l e xm e t h o d ，w ec a l li t m u l t i - s t a g ep a c k e t ss c h e d u l i n g ( m s p s ) ， b e c a u s et h e t h e o r y a b o u tm s p si s n t m a t u r e ，d e s i g n e ru s u a l l y u s et h e o n e - s t a g es c h e d u l i n gt h e o r y t od e t e r m i n et h e p a r a m e t e r t h o u g h t h e p e r f o r m a n c e o f e v e r ys t a g e i st h e b e s t ，b u t t h e p e r f o r m a n c e o fw h o l e m u l t i s t a g es c h e d u l e ri s n o t s ow en e e dt oa n a l y s et h ep e r f o r m a n c eo ft h e m u l t i - s t a g es c h e d u l e r ，a n dt r yt of i n dt h eb e s ta l g o r i t h mo f i t w eh a v ed e s i g n e da t w o s t a g ep a c k e t s s c h e d u l e rt os a t i s f yt h eo o s r e q u i r e m e n t i ni n t e r n e t t h i si sb a s e do nt h ea n a l y s i so ft h eq o ss c h e m ei n i n t e r n e t b y e m u l a t i n gt h et w o - s t a g es c h e d u l e ra n da n a l y s i n gt h ep e r f o m a n c e o fi t ，s u c ha s p a c k e t sd e l a y ，d e l a yj i t t e r ，p a c k e t sl o s sa n d b u f f e rc a p a c i t y ，t r yt of i n dab e t t e r s c h e m e a tl a s t ，w ef i n dt h ed w r r m w r r i st h eb e s ts c h e m e t oc o m p l e t et h es i m u l a t i o no fm s p s ，w ed e s i g n e dag e n e r a lo n e s t a g ep a c k e t s c h e d u l i n g s i m u l a t i o nm o d u l e ro no p n e t t h em o d u l e ri sb a s e do i lt h ea n a l y s i s o fv a r i o u s g e n e r a lo n e s t a g ep a c k e ts c h e d u l i n g ，p i c k - u p t h ec o m m o n c h a r a c t e r i s t i co ft h e m ，t h e ne n c a p s u l a t et h ed a t as t r u c t u r et or e a l i z e d i t sa n i m p o r t a n tp a r to f t h i sp a p e r ，w ec o n s t r u c tt h em s p sm o d e l b y i t k e yw o r d s ：p a c k e t ，m u l t i s t a g es c h e d u l i n g ，s i m u l a t i o n l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料a 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：障玉 日期：加年ff j ee l 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：砼蠢导师签名：奎堑：垒! 堇 1 日期：舢 ( 年f 月，de l b e i p q o s t o s l l q g p s p q w f q c q d w r r m w r r m d r r r e d i q o q v o q c i o q m i o q i e t f i n t s e r v d if f s e r v d s c p p h b b e s t e f f o r t s i n t e r n e tp r o t o c 0 1 简略字表 q u a l i t yo fs e u v i c e s t y p eo fs e r v i c e s l o wl a t e n c yq u e u e 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 p r i o r i t yq u e u i n g w e i g h t e df a i rq u e u i n g c u s t o mo u e u i n g d e f i c i tw e i g h t e dr o u n dr o b i n m o d e f i e dw e i g h t e dr o u n dr o b i n m o d e f i e dd e f i c i tr o u n dr o b i i i r a n d o me a r l yd e t e c t i o n i n p u tq u e u e i n g o u t p u tq u e u e i n g v i r t u a lo u t p u tq u e u e i n g c o m b i n e di n p u to u t p u tq u e u e m u l t i p l ei n p u to u t p u tq u e u e d i n t e r n e t e n g i n e e r i n gt a s kf o r c e i n t e g r a t e ds e r v i c e d i f f e r e n t i a t e ds e r v i c e d i f f e r e n t i a t e ds e r v i c ec o d e p o i n t p e r h o p b e h a vio r v 尽力( 传输) 因特网协议 服务质量 服务类型 低传输延迟队列 广义处理器共享 优先级队列调度 权重公平队列调度 用户队列调度 赤字权重轮循调度 修改的权重轮循调度 修改的赤字轮循调度 随机早期检测 输入排队输出排队 虚拟输出排队 组合输入输出队列 并行输入输出队列 因特网工程任务组 综合服务 区分服务 区分服务标记 逐点行为 电子科技大学硕士学位论文 1 1 研究背景 第一章概述 目前电信业务发展迅猛，以因特网为代表的新技术革命正在深刻地改 变着传统电信的概念和体系，电信业正在进行场巨变：新业务层出不穷， 数据业务快速发展，以音频和视频服务为目标的大流量业务需求成为主要 的业务增长点。这些直接导致了近年来电信业的网络结构发生了根本的变 化，从原来的主要支持语音通信的网络转变为提供以数据业务为主的多媒 体综合宽带业务网。综合宽带业务网目前已经从异步传输模式( t m ) 为主发 展为异步传输模式和因特网协议模式( i p ) 混用共存的局面，并显现出将进 一步演变为以i p 为主的趋势。随着由i p 协议为基础的因特网( i n t e r n e t ) 以新的公共网络的角色出现，用户要求并期待提高因特网的可靠性和稳定 性，并以此支持紧要事务应用。因特网不能再继续只提供时好时坏的不稳 定的b e 服务，它们已经被期望成为象公共电话交换网( p s t n ) 一样，用户只 要进行通信就能受到高质量的服务。因此用户和电信商都希望能进一步的 提高i p 网络的性能，其中主要就是对o o s 保证的要求。为此而推动着传输 和分组交换技术的进步，新的核心技术如软交换、多协议标签交换( m p l s ) 、 标签分发协议( l d p ) 、资源预留协议( r s v p ) 等i p 交换技术大量出现。参考 文献 1 。 在核心网络大幅度增加所能提供的服务带宽的同时，接入网也向i p 宽 带的方向飞速发展。为此，中国以及环太平洋地区的电信服务公司将继续 对基础设施投入巨额资金，构建自己的高速i p 网络。并采用备种方法来解 决“最后一公里”( 也称“最初一公里”) 的问题。据估计未来千年内中国宽 带接入将以平均每年2 1 0 0 万线的速度增长。 接入网可分为有线和无线两大类。有线分光纤接入，同轴电缆接入和 双绞线接入；无线分移动无线和固定无线接入。不论是鄢种接入方式，接 入设备中希望能有尽可能好的q o s 支持。 从上面的分析中，我们可以看到q o s 的支持能力在未来的网络中有非 电子科技大学硕士学位论文 常重要的影响和需要。当前，q o s 保障已经成为网络设计中十分重要的一一环， 不同的业务对网络要求不同的q o s 。q o s 参数包括分组时延( d e l a y ) 、时延 抖动( d e l a yj i t t e r ) 、预约带宽、吞吐量( t h r o u g h p u t ) 、丢失率( 1 0 s sr a t e ) 等。为了使i p 能够支持o o s ，i e t f 定义了综合服务和区分服务两种服务模 型。综合服务模型的特征是资源预约。在数据传输前，通过r s v p ( r e s o u r c e r e s e r v a * i o dp r o t o c 0 1 ) 信令协议建立路径和预约带宽。区分服务模型通过 对分组的d s 域设置不同的值和对不同的d s 域的分组进行不同的处理，可 以产生多种服务类别。例如低时延和低时延抖动的特级服务( p r e m i u i l l s e r v jc e ) 、比b e s t e f f o r t 可靠性高的确定服务( a s s u r e ds e r v i c e ) 、具有 金银铜三个等级的奥林匹克服务( o l y m p i cs e r v i c e ) 。区分服务相较于综合 服务，容易实现且易于扩展到大型网络，是研究和开发的重点。而分组调 度算法作为对i p 网络具备q o s 支持具有非常重要的影响，是目前在i p 网 络中实现q o s 支持的基本方法之。 分组调度就是以。定的规则在等待服务的分组中选择服务对象的过 稃。通过在各个转发设备中( a t m 交换机、i p 路由器) 采用合适的分组调度 方案，可以使特定业务流在其他业务流影响的情况下仍然能获得其所需的 服务质量。分组调度还可以使多个业务流分级共享链路带宽，使宝贵的带 宽资源得到合理充分钓利用。具体参考文献 2 。 目前对分组调度算法有非常多的研究，提出了很多的分组调度算法， 并有详细的实现和性能分析。在工业上广泛使用的就有w f q 、p q 、m w r r 、d w r r 、 m d r r 等，对这些算法的研究通常是在一次调度的基础上进行的( 本文称为单 级分组调度算法) 。但是在工业或者实际设计中，我们常常需要对这些单级 分组调度算法进行组合来满足用户或网络的一- 些灵活的q o s 要求，这就产 生了复杂的多级分组调度算法( 蟠u l t i s t a g ep a c k e ts c h e d u li n g ) ，由于目 前并没有关于多级分组调度算法的成熟理论模型，因此很多都是采用了单 级分组调度算法的理论来确定多缀中各级的调度算法，这样的结果是在每 一级的调度中取得了相对最优，但在多级联合以后却不一定是性能最优的。 所以分析多级分组调度算法的性能具有重要的工程意义。本文于是为此做 了专门的分析工作。希望能得到一些有价值的结果。 电f 科技人学硕十学位论文 1 2 单级分组调度算法 我们在网络中遇到的很多问题都和用户对有限的共享资源( 比如缓存、 出端的带宽) 进行竞争有关，为了解决这些问题，我们需要对资源进行合理 分配和管理。队列调度算法就是和这种分配紧密相关的技术，它通过从队 列中选择下一个将从某端口分发出去的分组来完成对固定的输出端带宽的 分配。现在已经有众多的不同类型的调度算法，每一个都在试图找到在复 杂性、可控性和公平性三个方面取得平衡的方法。任何一个调度算法都应 该完成的任务有以下几方面： ( 1 ) 支持公平分配前往同一输出端口的不同服务等级的分组对带宽的 请求。如果一种服务需要比其它服务更多的带宽，能通过给它们分配不通 的权重来实现公平性。 ( 2 ) 同一输出端口的不同服务类型之间应该有隔离保护，从而防止因 为其中某个队列的不良行为( 对带宽和延迟的影响) 影响到其它队列。 ( 3 ) 有可通过硬件实现的算法，从而可以在高速路由器中可以应用而 不会给整个路由器带来消极的影响。 分组调度算法主要包括两种技术，流调度( f l o ws c h e d u l i n g ) 和交换矩 阵调度( s w i t c hm a t r i xs c h e d u l i n g ) 。前者依据公平性决定对各个流服务 的顺序，后者将交换机的输入和输出端匹配，解决交换结构( s w i t c hf a b r i c ) 中的竞争，用于交换结构为c r o s s b a r ( 交叉连接矩阵) 的情况。通常，网络 设备中的分组调度方案要综合这两种技术同时加上“反压”等手段。从数 据源的角度来看，既包括定长分组调度，也包括变长分组调度。 本文的工作主要针对其中的流调度算法，而队列管理算法是其中的主 要技术。通常队列管理算法分为基于时标算法、基于轮转算法以及基于优 先级队列等。基于时标的分组调度算法都有相同的形式，它们为每个分组 维持两个时标，一个命名为起始时标，一个命名为完成时标。路由器根据 上述时标来决定下一个转发数据包。基于时标的算法最常用的有w f q 、 w f 2 q ( w o r s t - c a s ef a i rw e i g h t e df a i ro u e u e i n g ) 等。基于轮转调度机制的 工作原理与操作系统里的多任务的轮转调度有类似之处。基于轮转的调度 电子科技大学硕 = 学位论文 算法通常有w r r ( w e i g h t e dr o u n dr o b i n ) 、d w r r 、c q 、m w r r 、m d r r 等。基 于优先级的队列管理能根据预先规定或用户指定的优先级，调度不同队列 的数据包转发，主要为p q 。这些调度算法都有大量的文献可以参阅，在这 里就不在赘述。本文在单级调度中的工作重点是建立一个在o p n e t 仿真平 台上通用于这些调度算法的程序模块，为多级调度的性能分析搭建一个易 于实现的程序框架结构。这将在本文的第二章中详细介绍。 1 _ 3 多级分组调度 上面提到的这些流调度算法，都是分组到达调度器的输入端口以后， 只需要经过一次队列调度就可以转发到出端口，所以在本文中称为单级分 组调度算法。而在很多设备中，当分组从输入端口进入开始到分组最终从 输出端口转发出去，中间会经过多次调度，每次的调度都有可能是不同的 单级分组调度算法，于是在考察整个设备的时候就会发现这是一个多级调 度的情况( 图卜1 描述了一个常见的多级调度模型) 。本文的多级分组调度 就是指从入端口到出端口分组经过多次调度的情况。 图卜1 多级调度模型 在多级分组调度中，各级调度的性能是相互影响的，比如：在后一级 hf 科技大学硕士学位论文 调度器发7 e 了阻塞，那么前一级调度成功的分组也可能需要丢弃，从而以 单级调度算法得到的包丢失率就不能准确描述整体的调度算法的性能了： 还有当后一级调度能完全无阻塞的转发分组，并且具有非常小的时延的情 况下，也叮能因为前一级调度器发生了阻塞而使整个的调度过程的性能发 生变化。同时在多级的情况下，各级之间还有反压等q o s 实现手段的影响。 所以多级分组调度的性能分析要远比单级分组调度的性能分析复杂。 那我们每一级的调度都使用最好的调度算法( 通常实现起来也就更复 杂) ，是不是也就获得了最好的多级调度性能呢? 理论上也许这是正确的， 但是在一个复杂的多级调度中，如果都采用某一种调度算法就可能付出更 多的构造成本，甚至成为不可能实现的工程方案。通过在必要的调度级中 使用性能更好但实现复杂的单级调度算法，而在可以用实现相对简单又同 样能满足需要的地方使用成本较低的单级调度算法，这在工程应用中更有 实际价值。 本文在多级调度算法的性能分析中，就是通过对不同的单级调度算法 进行组合，分析其在时延( d e l a y ) 、时延抖动( d e l a yj i t t e r ) 、队列缓存分 组所需要的存储器大小( b u f f e rc a p a c i t y ) 以及同样大小的存储器时包丢失 情况( 丢失率l o s sr a t e ) 等参数，希望能得到一些具有工程应用价值的仿真 结果。 1 4 本文的工作 本文的工作主要由两个部分组成： 第一部分：通过分析o p n e t 中未公开的函数包o m s q m e x c 和i p q o s s u p p o r t e x c ，获得函数包中分组队列调度算法实现框架结构，并在这个 框架基础上完善具体的程序实现，建立一个实现通用的分组队列调度算法 的o p n e t 仿真模块。这部分工作的贡献和意义主要是把以前每个仿真中都 需要单独编写的调度和队列管理算法集成在一个通用的o p n e tm o d u l e r 中， 为以后通信仿真和本文的第二部分工作节省了大量的编程工作，这在网络 规划、交换模块等的设计方面都有相当的应用价值。同时，项目组的下一 级同学也将利用这个通用的分组调度仿真模块，测试普然通讯技术( 上海) 有限公司开发的m u l t i s e r v i c ea c c e s sp 1 a t f o r mm o d e l 芯片中单级和多级 电子科技人学硕 ：学位论丈 调度的性能，并据此确定其中的参数。 第二部分：从各种多级分组调度应用中抽象出一个多级分组调度算法 架构，然后利用我们建立的通用的分组调度算法模块，在o p n e t 平台上建 立此分组调度算法的仿真模型。通过仿真，测试在各种配置下，多级调度 算法的性能，得到大量的仿真数据。通过对仿真数据的分析，包括时延 ( d e l a y ) 、时延抖动( d e l a yj i t t e r ) 、队列缓存分组所需要的存储器大小 ( b u f f e rc a p a c i t y ) 以及同样大小的存储器时包丢失情况( 丢失率l o s sr a t e ) 等数据的比较，获得多级调度算法较优的结构。 电子科技大学硕士学位论文 第二章单级分组调度通用仿真模块实现 2 1 单级分组调度算法原理 由于实际中的网络由有限带宽且有一定量延迟的共享连接组成。网络 设讨者都力图在平均和峰值传输速率间平衡开销。因此网络设备如路由器， 采用了多种缓冲排队机制以处理高于均值的暂时突发状况。为管理这些队 列就需要应用各种调度算法来满足o o s 的要求。 通常使熠两种o o s 管理来满足传输的要求：拥塞管理与拥塞避免。 拥塞管理功能的作用是一旦发生拥塞，可对拥塞进行控制。文献 3 提 到的拥塞管理算法对我们的设计提供了很大启示。拥塞管理假定报文在队 列中等待，尝试依据报文服务级别顺序出队以减少队列的影响。网络组件 处理接收通信量溢出的一个方法是：先使用排队算法给通信分类，然后， 对通信采用定的调度算法排在输出链路上。每一种调度算法都能解决某 个特殊的网络通信问题，并且对网络的性能有特殊的作用。目前在工业 应用中常见的分组调度算法有很多。其中在分组调度算法中属于基础类型 的主要为p q 、w f o 、c q 、m d r r 、m w r r 、d w r r 等。本节是对这些算法的简要 介绍，详细描述见文献 4 ，然后在本章第二节介绍作者建立的通用分组调 度算法仿真模块，并阐述其中各个调度算法的程序实现方法。 2 1 1p r i o r i t yo u e u i n g ( p 0 ) p q 是种基础的队列调度算法，它可以通过相对简单的实现方法来支 持不同服务等级的需要。在典型的p q 算法中，分组首先由系统进行分类， 然后放入不同优先级的队列中。只有当所有比当前队列具有更高优先级的 队列都为空的时候，当前队歹i j 的分组才会被调度。在同一个队列中，分组 则采用先进先出( f i f o ) 方式进行调度。见图2 - i 。 p q 算法的两个优点： 对基于软件的路由器，p q 和其它更复杂的队列算法相比，所需要 的计算负担较低。 电子科技大学硕士学位论文 p o 让路由器有机会组织缓存的分组，从而可以按照不同的服务级 别来处理不同的流。比如，你可以把实时应用如交互的音频视频流 设置较高的优先级，从而得到比非实时数据更好的服务质量。 图2 - 1p q 队列 但p q 算法也因为其简单而带来诸多限制： 如果高优先级的流( t r a f f i e ) 在网络边界没有合理的管理和约束， 低优先级的流可能因为一直等待高优先级的队列服务而超过所能 允许的最大延迟。并导致缓存溢出，从而大大增加低优先级队列的 包丢失率。 在共享同一个队列的不同流之间可能因为某个流的不端行为，而大 大增加延迟和时延抖动。 p q 也不能解决因为u d p 流和t c p 流在f i f o 队列中竞争而导致的阻 塞。如果你试图通过给t c p 流分配比u d p 流更高的优先级，则t c p 流的窗口管理和流控制策略会把输出端口的所有带宽消耗掉，从而 导致低优先级的u d p 流出现饥饿。 p q 算法的实现方式和应用： 典型的，飓可以被设置成两种模式：s t r i c tp r i o r i t yq u e u i n g ( s t r i c t 电子科技人学硕十学位论文 p q ) 和r a t e c o n t r o l l e dp r i o f i t yq u e u i n g ( r a t e e o n t r o l le dp q ) 。s t r t c t p q 保证高优先级的队列中的分组总是在低优先级队列中的分组之前被调 度。这会导致低优先级分组出现不能得到带宽的情况。但有时候这种方式 是必须的，比如为了携带v o l p 流，也许服务提供者必须要同意这种调度模 式。另外一种p q 模式是r a t e c o n t r o l l e dp q ，这种模式中，只有当高优 先级的队列流量在用户设置的极限以内时，才允许按照s t r i c tp q 方式进 行分组调度。当流量超过极限后，则先调度低优先级队列中的流，然后在 调度高优先级队列中的相应分组。 p q 在网络边界和核心网络中主要有两种应用，即： p q 可以通过允许你将有关路由协议和其它种类网络控制的流定义 为高优先级队列，从而在网络阻塞的时候提高网络的稳定性。 p q 支持对高吞吐能力、低延时、低时延抖动以及低丢失率的服务 要求的分类。这种能力使得你可以在网络上传送实时应用，比如交 互的音频或视频，或者支持t d m 的电路仿真等，实现这些服务只需 要把它们定义为比其它流更高的优先级就可以了。 但是，支持这些服务要求网络规划的人必须有效的设置网络边界的流 量参数以防止服务被超额订购，如果忽视了这部分的规划和设置，就不可 能实现对这些服务的支持。对某些应用，比如v o i p ，因为很容易得到分组 大小、流量大小、流的行为，所以很容易完成参数的设置：但对另一些应 用，比如交互的音频、视频服务，因为它们有太多的变量，而且很难得到 准确的值，这就导致了对约束条件比如高优先级队列的流量极限、最大的 队列长度以及流量控制无法正确设置。因此也就使得p q 不能应用。 2 ，1 2w e i g h t e df a lro u e u i n g ( w f q ) w f q 调度算法是为了突破f q ( f a i rq u e u e i n g ) 的局限而发展出来的最基 本的一类调度算法，它按占用输出端口带宽的不同比例来确定权重，然后 给相应队列设置相应的权重，从而实现不同数据流对带宽的要求。同时与 f q 相比较，w f q 支持变长的分组，这样分组较大的流就不会占用更多带宽。 但是为了支持变长分组对带宽的公平分配，大大的增加了队列调度算法的 复杂性。这也是变长分组的队列凋度算法比固定长度( 如a t mc e l l ) 信元调 电子科技大学硕士学位论文 度实现复杂的原因。 w f q 能支持变长分组公平的占用带宽，是使用了对g p s ( g e n e r a l i z e d p r o c e s s o rs h a r i n g ，一种理想化的调度算法，实际不可能实现) 系统的近 似。w f q 通过计算每个分组的分发完成时间来近似得到g p s 这中理论上的调 度算法。当给出了输出端口的比特率、所有活动的队列中分组数量、每个 队列的权重以及新到队列分组的长度，就可以计算出每个新到来的分组的 调度完成时间。这里的时间不一定是实际的时间，也可以是比例于分组调 度完成时间的一个数字。w f q 的原理图如图2 2 。 图2 - 2w f q 队列调度 当一个分组到达的时候，经过分类后放入自己的队列中，调度器同时 为分组计算完成时间。当w f q 进行调度时，从所有分组中选择完成时间最 早( 也即是分组较小) 作为下一个从输出端口传输出去的分组。 因为w f q 的特殊算法，它具有两个突出的优点： 由于给每个类型的数据流都分配了不同比例的输出带宽，因此能保 证每个流都能得到服务。 通过在网络边缘和流控制策略的结合，w f q 可以提供在可接受延迟 f 的带宽公平分配。 但是，w f q 这种算法也因此带来了一些限制，包括： 目前w f q 实现方法主要是软件方式，而不是硬件方式，所以限制了 它在网络边界的低速接口上的应用。 虽然服务类型不同的数据流之间不会互相影响，但是同一服务分类 电子科技大学硕十学位论文 中的流却仍然会相互影响。 w f q 复杂的实现算法要求更大存储空问来保存必要的状态信息。这 些状态信息随着分组的到达或离开，都要求进行更新。 复杂的计算削弱了对高速接口中大量不同类数据流的支持。而且有 时候为了得到有保障的延迟要求而牺牲的用于计算的代价也许比 略为增加的延迟大得多。 w f q 的实现和应用： w f q 一般配置在网络边界，用来实现对不同服务类型的公平分配出口带 宽。它的一般用途为： w f q 可用来支持将分组按某种方法分类放入数量相对较多的队列 中，这些分类可按分组的源目的地址对、源目的u d p t c p 端口号 或者是i pt o s 来进行。 w f q 配置为运行系统对一定数量携带有流控制信息的队列的调度。 调度器使用q o s 规则或者是i p 分组中的t o s 字节来决定将分组放 入哪个队列中。每个队列占用不同比例的输出带宽，所占比例由系 统根据每一类服务类别而计算的权重来确定。并且这种配置模式中 还允许当一个队列中的i p 分组优先级增加时，相应增加其带宽。 2 1 3c u s t o mo u e u i n g ( c 0 ) c q 算法是在w r r 上发展的一种支持变长分组的轮循调度算法。基本原 理是为一个接口中的每种流类型保留一定比例的带宽，从而实现对列的优 先级调度，以提供对有服务质量要求的流的服务保障。如果某种类型的流 没有使用分配给它的带宽，则其他类的数据流就可以使用这部分带宽。理 想的c q 算法是希望能将所有的带宽刚好分配给所有的队列。 在c q 算法中，对每个队列设定一个参数“b y t e c o u n t ”，这个参数决 定了这个队列实际占用的带宽在总的出口带宽中的比例，也即当前队列的 b y t e c o u n t 所有队列的b y t e - c o u n t 总和就是此队列所用的带宽比例。 电子科技大学硕士学位论文 c q 调度的优点是为每个类型的流都能提供一定的带宽，避免了因为高优 先级队列占用过多带宽而带来的低优先级的饥饿问题。但是对变长分组调 度来说，确定一个合适的b y t e c o u n t 参数很困难，所以不容易得到精确的 对带宽的分配。图2 - 3 示出了c q 调度算法的原理。 图2 - 3c q 调度算法原理 2 1 4d e f j c i tw e i g h t e dr o u n dr o b i n ( d w r r ) d w r r 也是设计用来改善w f q 和w r r 调度算法缺陷的最基本的一类队列 调度算法。当队列中包含有变长分组时，d w r r 通过简单设置队列的权重就 能精确的实现对带宽的公平分配，而不会象w r r 长分组队列实际占用比分 配带宽更多资源的情况。同时，和w f q 比较，d w r r 算法的计算要简单得多， 这样就利于以硬件的方式实现。这使得d w r r 能支持高速接口中几乎任意大 的出口带宽，所以可以同时应用于网络边界和核心部分。 在d w r r 调度算法中，每个队列都需要设置一系列参数，包括： w e i g h t 一定义相应的队列所占带宽的比例 d e f i c i t c o u n t e r - - 定义了每次调度器访问一个队列的时候允许从 该队列中传送的最大字节( b y t e ) 数。如果当前队列最前面的分组大 电子科技大学硕士学位论文 小超过了d e f i c i t c o u n t e r 值，则本轮不传送，而将这个值保留给 下一轮，直到累积的d e f i e i t c o u n t e r 值超过此分组字节数，然后 再传送此分组。 q u a n t u m 一这个参数决定了相对应队列的权重，它的单位也是 b y t e s 。每当一个队列被轮循到的时候，就会在d e f i c i t c o u n t e r 值 上加上此队列的q u a n t u m 值。比如一个队列的q u a n t u m 值为另一个 队列的两倍，则此队列所分配到的带宽也就是另一个队列的两倍。 在经典的d w r r 算法中，调度器轮循每一个非空的队列并计算队列头部 分组的字节大小。d e f i c i t c o u n t e r 变量根据固定的q u a n t u m 值增加。如果 队列头部的分组大于当前的d e f i c i t c o u n t e r 值，则调度器移动到下个队列 为其服务。如果分组比d e f i c i t c o u n t e r 值小或者刚好相等，则传送该分组， 同时将d e f i c i t c o u n t e r 值减去所传送分组的字节大小。然后重复对此队列 进行判定和传送操作，直到d e f i c i t c o u n t e r 值小于队列中头分组的大小或 者队列为空的时候，调度器就移动到下一个队列。图2 4 为d w r r 调度算法 原理。 2 1 5m w r r 和m d r r 图2 - 4d w r r 调度算法原理 m w r r 和m d r r 这两种调度算法的基本原理都和d w r r 一样，所以这里将 它们放在一起，并简单介绍。它们都是给每个队列设定一个q u a n t u m 参数， 电子科技大学硕士学位论文 用来决定队列所占带宽的权重，另外每个队列也同时保持一个变量 d e f i c i t c o u n t e r ，用来决定当前是否允许传送分组。m w r r 、m d r r 和d w r r 的不同在于，d w r r 中每轮循到一个队列的时候，首先判断当前队列头部分 组大小是否小于d e f i c i t c o u n t e r 值，而m v r r 、m d r r 则是不论头部分组的 大小，只要d e f i c i t c o u n t e r 大于0 就将当前分组传送出去，然后从 d e f i c i t c o u n t e r 值减去所传送的分组大小，也即在m w r r 、m d r r 判断是否传 送的条件是0 ，而在d w r r 中的判定条件是当前队列中头部分组的大小。 m w r r 和m d r r 调度算法的不同则在于它们中设定的q u a n t u m 参数的含义 不一样。其中，m d r r 中的q u a n t u m 参数的含义是和d v r r 中相应参数一致的， 也即是以字节数为单位。而m w r r 中q u a n t u m 参数是以a t m 信元个数为单位 ( 也即是分组字节数5 3 ) ，所以在每次增加d e f i c i t c o u n t e r 值的时候也是 增加的信元个数值，而每传送一个分组后从d e f i c i t c o u n t e r 中减去的也不 是分组的字节数，而是分组的信元数( 即分组字节数5 3 ) 。 2 2 单级分组队列调度算法通用仿真模块实现 前面我们已经指出分组调度算法在目前通信网络中具有广泛应用。因 此我们在网络规划、网络设备( 如交换设备、复接设备等) 设计的对候，都 有可能涉及到对分组调度算法的性能分析。两o p n e t 的仿真是目前主流的 网络性能分析工具，所以建立一个在o p n e t 上的通用分组调度算法模块具 有相当的工程实用价值，可以在以后涉及到分组调度仿真的时候节约大量 的程序编写工作。同时，在本文的多级调度算法中需要测试各种分组调度 算法组合的性能，因此建立一个通用的分组调度算法模块也是非常必须的。 下面就详细介绍作者所建立的仿真模块。 在我们着手开发自己的仿真模块的时候，发现o p n e t 公开的关于队列 调度管理方面的核心仿真函数包( s i m u l a t i o nk e r n e l 中的qp a c k e t ) 功能 过于简单，要做出复杂的队列调度将使程序过于复杂并且缺少可读性和移 植性。但我们发现在o p n e t 8 i a 中新增加了一个函数包o m s q m e x c ( 以后 简称为o m s q m ) ，其主要功能就是完成各种调度算法的运算。但是这个函数 包并不是一个成熟完整的函数包，所以o p n e t 没有将其列入可供直接调用 的函数集，同时也没有在其说明文档中公开。本文作者在详细阅读和分析 电子科技人学硕十学位论文 此函数包的数据结构和实现方法的基础上，通过完善其中需要用户自定义 的函数，建立了一个通用的分组调度算法和队列管理的模块。 2 2 1 模块中关键数据结构说明 在我t 1 引入基于o m s q m 函数包所创建的分组调度算法通用模块前，首 先必须阐明有关队列管理的关键数据结构。 2 2 1 ，1 队列中分组的存储结构 在o p n e t 中，所有队列中进入的分组都存储在内存中分配的缓存 ( b u f f e r ) 中，缓存是按层次结构进行组织的。图2 5 描述了一个接口中缓 存的结构。 图2 - 5o m s q m 中队列的存储 在o m s q m 中，每一个接口都对应有一个主缓存池( m a s t e rp 0 0 1 ) 。然 后在此缓存池中为每一个队列分配了一个专用的缓存( b u f f e r ) 。有时候为 了使用的方便，我们在主缓存池中再分配子缓存池( s u b p 0 0 1 ) ，然后在子缓 存池中为相同服务类型的队列分配各自对应的缓存。因此，在主缓存池中 可以既有直接存放队列分组的缓存，也有包含有很多缓存的子缓存池。这 是一个层次结构，还可以在子缓存池中在形成和主缓存池类似的结构。而 电子科技人学硕士学位论文 每一个缓存就是一个队列。对于缓存，定义了一个结构o m s t b u f f e r 存放 关于这个缓存的信息。然后把这个结构的地址指针定义为一个新的数据类 型