（计算机应用技术专业论文）多优先级队列分组调度研究.pdf

摘要 随着网络技术的发展，各种新的业务相继出现。这些业务在带宽 和延迟等方面有着不同的要求。如何支持这些业务的q o s 要求，是当 前网络研究的一个热点。流量整形和分组调度都是实现网络q o s 的重 要内容。 本文对流量整形的常用方法：令牌桶算法，进行了研究，分析了 令牌桶算法中各参数在流量整形中的作用，还讨论了i e t f 的两种令 牌桶算法，单速率三色标记算法和双速率三色标记算法，在这些研究 的基础上，提出了一种与调度器相配合的令牌桶算法的设想。 分组调度机制能保证不同业务的q o s 要求。本文在分析相关调度 算法的基础上，详细介绍了一种将优先级和时延相结合的动态优先级 调度算法：p q b e d f ( p r i o r i t yq u e u eb a s e do ne d f ) 算法。同时提出 了p q b e d f _ r ( p q b e d f r e t u r n ) 算法。在p q b e d e r 算法中，为每个队 列引入一个计数器，对队列处于最高优先级时获得的服务次数进行计 数，并根据相应规则将队列的优先级返回到初始值。这样就避免了优 先级长时间相同的可能，使优先级具有一定的相对性，从而为各业务 提供既有一定保证又有所区别的服务，具有一定的公平性。 在以上研究的基础上，提出了结合令牌桶的p q b e d f r 算法。它 为每个队列增设一个令牌桶来对数据流进行流量整形，经流量整形后 再进行调度。根据调度器的需要对令牌桶算法作了适当的修改，在令 牌桶之间引入了互相通讯的机制，根据缓冲队列中分组数目来对令牌 桶的参数进行动态调整。文中对令牌桶与p q b e d f r 算法相结合的方 法进行了模型设计，分析了性能。结合令牌桶的p q b e d l r 算法能限 制各业务流对带宽的占用，有利于各流公平合理地共享网络资源，从 而保证不同业务的服务质量。 最后，利用0 p n e t 瑚1 0 o 进行仿真实验，在实验的基础上分析 p q b e d f 算法、p q b e d f r 算法，以及结合令牌桶的p q b e d f _ r 算法等在 公平性、分组丢失率和延迟等方面的性能，验证了上述理论。 关键词：服务质量，分组调度，p q b e d f 算法，流量整形 i i a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g y ， v a r i o u sn e w a p p l i c a t i o n s c o m et oe x i s t t h e s ea p p l i c a t i o n s o f t e nh a v e d if f e r e n tq o sr e q u i r e m e n t so nb a n d w i d t ha n dd e l a y i ti sah o t r e s e a r c ht o p i ch o wt os u p p o r tt h e s er e q u i r e m e n t s 1 nn e t w o r k t r a f f ics h a p i n ga n dp a c k e ts c h e d u l in ga r eo f t e ne m pl o y e dt o s 0 1 v et h e s ep r o b l e m s i nt h i sp a p e r ，t o k e nb u c k e ta l g o r i t h mi sd i s c u s s e d i nd e t a i1 ， e s p e c i a l l yi t sp a r 锄e t e r sf 。rt r a f f i cs h a p i n g t h e ns i n 9 1 er a t e t h r e ec o l o rm a r k e ra n dt w or a t et h r e ec 0 1 0 rm a r k e rp r o v i d e db y 工e t fa r ei n t r o d u c e d b e s i d e s ，an e wt o k e nb u c k e ti d e ac o m b i n i n g w i t hs c h e d u l e ri sg i v e n p a c k e ts c h e d u li n gc a np r o v i d ed i f f e r e n tq o sg u a r a n t e e sf o r d i f f e r e n tb u s i n e s s e s b a s e d o nt h ea n a l y s i s o fa s s o c i a t e d s c h e d u li n ga l g o r i t h m s ，ap q b e d f ( p r i o r i t yq u e u eb a s e do ne d f ) a l g o r i t h m ( ad y n a m i cp r i o r i t ys c h e d u l i n ga l g o r i t h mc o m b l n l n g ti m ed e l a y ) is i n t r o d u c e d a n d ap q b e d f r ( p q b e d f r e t u r n ) a l g o r i t h mi sp r o p o s e d i nt h ep q b e d f ra l g o r i t h m ， ac o u n t e rl s i n t r o d u c e df o re a c hq u e u e t h ec o u n t e risu s e dt oc o u n t t h e s e r v i c et i m e so ft h eq u e u ei nt h es t a t eo ft h eh i g h e s tp r i o r i t y ， a n dt h ep r i o r i t yo ft h eq u e u er e t u r n st o i t si n l t l a 上v a 上u e a c c o r d i n gt or e l e v a n td i s c i p l i n e s t h ea l g o r i t h m c a na v o i dt h e p o s s i b i l i t yo fp r i o r i t i e sb e i n gi d e n t i c a lf o ra1 0 n gp e r i o da n d m a i n t a i nc e r t a i nr e l a t i v i t i e sf o rp r i o r i t i e s ，s oi tc a np r o v l d e g u a r a n t e e da n dd i f f e r e n t i a t e ds e r v i c e sf o rv a r i o u sk i n d so f b u s i n e s s e st oc e r t a i ne x t e n t t h u sac e r t a i nf a i r n e s s c a nb e a r h je v e d i i l b a s e do nt h ea b o v es t u d y ，ap q b e d f ra 1g o r it h mw i t ht o k e n b u c k e tf o rs h a p i n gi sp r o p o s e d at o k e nb u c k e ti sa d d e df o re a c h q u e u et os h a p e t h ep a c k e tsa r es c h e d u le da f t e rs h a pin g a c c o r d i n gt ot h en e e d o ft h es c h e d u l e r ，t o k e nb u c k e ti sm o d i f i e d c o m m u n i c a t i o nm e c h a n i s mb e t w e e nt o k e nb u c k e t si sp r o p o s e da n d t h e i rp a r a m e t e r sa r ed y n a m i c a l1 ya d j u s t e dw i t ht h en u m b e ro f p a c k e t si nt h e i rb u f f e r s am o d e ld e s i g ni sp r o v i d e da n d a n a l y s e df o rt h em e t h o dc o m b i n gt h et o k e nb u c k e ta n dp q b e d fr a l g o r i t h m a sar e s u l t ，t h ep q b e d f rw i t ht o k e nb u c k e tc a nli m i t t h eb a n d w i d t h so fi n d i v i d u a lf l o w sa n db eb e n e f i c i a lt ot h e f a i r n e s so fb a n d w i t h ss h a r i n gf o rt h e m t h u si tg u a r a n t e e st h e q u a l i t yo fs e r v i c ef o rv a r i o u sd i f f e r e n tb u s i n e s s e s f i n a l l y ，t h es i m u l a t i o ni si m p l e m e n t e dw i t ho p n e t f a i r n e s s ，p e r c e n to fp a c k e t1 0 s s ，a n dti m ed e l a ya r ea n a l y s e df o r p q b e d f ，p q b e d f ra n dp q b e d f rw i t ht o k e nb u c k e t ，a n dt h et h e o r y a b o v ejsv e r jf je d k e yw o r d s ：q u a li t yo fs e r v i c e ， p a c k e ts c h e d u l i n g ， p q b e d fa l g o r i t h m ， t r a f f i cs h a p i n g i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：鬃佩馘沙7 ，年岁月扣日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 名：暂州稚絮露诜 导师签名：乞之鸽 日期：跏罗年多月哆日 多优先级队列分组调度研究 1 绪论 1 1 研究背景 随着计算机网络技术的迅速发展，大量的新业务新应用相继出 现，如远程教育、语音i p 、视频会议、视频点播、实时业务、分布 式多媒体等，现在计算机互联网已经发展成为能够承载不同种类的业 务，服务不同用户群体的信息传输平台。但是传统的互联网对所有业 务不进行区分，任其抢占网络资源，提供的是一种尽力而为服务 ( b e s t e f f o r ts e r v i c e s ) 的工作方式，基本上无任何质量保证。 然而，这些新应用要求计算机网络在带宽、时延、延迟抖动和分组丢 失率等方面提供一定的服务保证。这在传统的计算机网络上是难以满 足的，也难以实现。随着这些要求的不断增加，这一矛盾也将进一步 加剧，因此，在计算机网络中提出了网络服务质量的要求，研究如何 在现有网络资源的情况下对新业务的支持，满足用户在带宽、时延、 丢失率等性能上的要求，提高计算机网络的服务质量( q u a l i t yo f s e r v i c e ，q o s ) 【l 】。这一研究具有重要的意义，也是当前网络研究的 热点问题。 在网络中，由于速率之间的不匹配，存在大量的网络瓶颈现象， 比如企业网与广域网之间，校园内网与外网之间等局域网与广域网之 间，局域网与局域网之间，以及某一交换节点等都是网络瓶颈经常发 生的地方，在这些地方经常造成网络拥塞和分组丢失的现象，如果不 对分组进行合理的调度，将会造成一些实时数据和重要业务得不到及 时服务，导致时延、抖动过大，甚至丢失，给这些重要业务造成极其 不利的影响。因此对各业务流实现合理的调度，对网络运行进行有效 的管理，从而满足各业务对带宽、时延等的要求，为各业务提供有保 障的q o s 服务，是十分重要的，这也有利于降低网络运营的成本，具 有一定的经济效益。 硕十学位论文 分组调度算法是实现网络q o s 的核心技术之一，它通过合理地安 排和控制分组流入下一个节点的时间和顺序来实现对网络资源的有 效分配，从而对各业务的预留带宽或延时进行较为严格的保证。同时， 分组调度还可以使各业务共享网络带宽，使带宽资源得到充分合理的 利用。因此，对分组调度进行研究是非常必要的，具有十分重要的意 义。 本文主要围绕分组调度进行研究，对不同优先级的业务研究如何 进行有保证的、公平合理的，同时又简单有效的调度，以满足各业务 对网络带宽和时延的要求，为各业务提供更好的q o s 服务。在研究调 度算法的同时，为了更好地进行调度服务，保证不同业务的q o s 要求， 还根据调度的需要，对流量整形技术作了相关的研究。对各业务流进 行监控，以限制某些业务流对网络资源的大量占用，保证各业务流公 平地共享带宽，从而提高网络的运行质量。 1 2 研究状况 分组调度算法一直是研究的重点问题，对分组调度有非常多的研 究，提出了很多的分组调度算法。到目前为止，产生的算法有几十种， 它们有着不同的服务规则和控制目的，主要有如下的调度算法。 最早期限优先( e d f ) 【2 】及其相关的一些算法d e l a y e d d 3 1 、 j it t e r e d d 【4 1 、r c e d f ( r a t e c o n t r o ll e d e d f ) 【5 1 、d c e d f ( d e a d li n e c u r v ee d f ) 并口e e d f ( e a r li e s te f f e c ti v ed e a d li n ef i r s t ) 等。还有 h z h a n g 等人提出r c s ( r a t e c o n t r o l l e ds e r v i c e ) 【6 】调度算法，在e d f 的基础上，引入整形机制。 基于轮循的算法有r r 、w r r 、d r r 7 】、u r r 等。基于g p s 模型的算 法w f q 、w f 2 q 、w f 2 q + 【8 1 、v c 9 1 、s f q 【1 0 1 、s c f q 等。分层链路共享算法 c b q 1 1 1 、h p f q ，核心无状态算法c s f q 1 2 】、c j v c ，基于服务曲线的算 法s c e d 和h f s c 【1 3 】，比例区分算法p a d 【1 4 1 、w t p 和h p d 【1 4 1 ，以及结合 缓冲管理的算法c d b p d e l a y l o s s 【1 5 】和j o b s 等等。 网络向着带宽高速化和业务多样化的方向发展，分组调度算法也 顺应这个趋势而发展，在追求简单、易于实现的同时，还将包括时延 多优先级队歹0 分组调度研究 在内的服务质量和公平性等综合性能考虑进来。 流量整形的算法主要有漏桶算法 1 6 1 和令牌桶算法【1 1 ， s h r i k 订s h n a 等提出的t c r 算法以及h u a n y u nw e i ，y i n gd a rl i n 等 提出的p o s t a c k 【1 7 】等等。围绕令牌桶整形已经提出了很多种整形方法 【1 8 】以控制输出业务流的突发量和带宽。g r e e n b e r g 和r o x f o r d 将令 牌桶整形和s c s f 调度机制相结合实现了公平令牌桶整形等。令牌桶 算法应用比较广泛，l i n u x 内核整形模块就采用令牌桶算法。 现在，国外很多的机构和组织在分组调度和流量整形方面作了大 量的研究，一些厂商还把流量整形、监测和分组调度等模块整合在一 起，形成自己的产品，如p a c k e t e e r 公司等。然而国内这种产品却很 少，对这方面的研究也有待加强，因此对这方面的研究具有重要的意 义。 1 3q o s 概述 1 3 1q o s 介绍 q o s 即服务质量，一般专指计算机网络的服务质量。它的最初定 义由c c i t t 给出：“q o s 是一个综合指标，用于衡量使用一个服务的满 意程度”。q o s 是一个十分广泛的概念，并没有一个十分确切的定义。 在r f c 2 3 8 6 【2 0 】中对q o s 的描述是：q o s 是网络在传输数据流时要求满 足的一系列服务请求，具体可以量化为带宽、延迟、延迟抖动、丢失 率、吞吐量等性能指标。对q o s 进行的另外一种描述【1 】是：q o s 是指发 送端和接受端的用户之间以及用户与传输信息的综合服务网络之间 关于信息传输的质量约定。也可以理解为服务提供者与用户之间的一 份服务契约。 为i n t e r n e t 应用提供服务区分和性能保证是q o s 控制的目标。 服务区分是根据不同应用的需求来提供不同种类的服务；性能保证则 主要解决一系列性能指标的保证问题，比如带宽、延迟、延迟抖动和 丢失率等。 1 3 2q o s 量化指标 q o s 量化指标主要包括延迟、抖动、丢包率和带宽等。 ( 1 ) 延迟( d e l a y ) ：是指分组从发送端到接收端所需要的时间， 硕十学位论文 它又可分为处理延迟、排队延迟、传送延迟和传播延迟等。处理延迟 主要对分组进行相关检测，以决定转发目的地所耗费的时间。排队延 迟主要指分组在缓冲队列中等待发送出去的时间，它通常受不同队列 管理和队列调度机制的影响。传送延迟是指分组从队列综合服务模型 到完全发送到输出链路上所用的时间。传播延迟主要指分组沿链路到 达下一个中继点或者目的地所需要的时间。 ( 2 ) 抖动( ji t t e r ) 是指相邻分组之间端到端传输时延的变化， 也就是相邻的两个分组到达接收端的时间间隔与发送端发送这两个 分组的时间间隔之间的差值。产生抖动的原因可能是由于排队，也可 能是由于不同的分组走不同的路径。 ( 3 ) 丢包率( 1 0 s sr a t e ) 是指分组在传输过程中，丢失的分组数 目与源端发送的分组数目之比。造成分组丢失的原因可能是出错，也 可能是网络拥塞。分组的丢失将严重地影响网络的服务质量。 ( 4 ) 带宽( b a n d w i d t h ) 是网络设备或通信链路的理论容量【2 l 】，用 来对给定介质、协议或链接等的额定吞吐量( t h r o u g h p u t ) 进行描述。 实际上是指应用程序在网络上进行通信所需要的“容量大小”，主要 用来衡量用户从网络中取得业务数据的能力。 1 3 3q o s 的两种模型 i e t f 在q o s 控制方面作了大量的研究，提出了综合服务 ( i n t e g r a t e ds e r v i c e s ，i n t s e r v ) 【2 2 】和区分服务( d i f f e r e n t i a t e d s e r v i c e s ，d i f f s e r v ) 【2 3 】两种不同的i n t e r n e tq o s 体系结构。 1 3 3 1 综合服务模型 i n t s e r v 的基本策略主要是基于资源预留的方式，按各业务的 q o s 要求对网络资源进行分配。资源预留协议r s v p ( r e s o u r c e r e s e r v a t i o np r o t o c 0 1 ) 【冽是i n t s e r v 结构中的主要信令协议，用来 完成综合服务的呼叫接纳控制功能和资源预留功能。资源预留协议 r s v p 负责逐点( h o p - b y - h o p ) 地建立或拆除每流的资源预留状态。此 外，r s v p 还提供流量控制和传输策略控制。 i n t s e r v 服务模型主要由四个模块构成，包括信令协议r s v p 、接 多优先级队列分组调度研究 纳控制器( a d m i s s i o nc o n t r 0 1r o u t i n e s ) ，分类器( c l a s s i f i e r ) 和分组调度器( p a c k e ts c h e d u l e r ) 。接纳控制器根据链路和网络节点 的资源使用情况以及q o s 请求的具体要求等来决定是否接受一个资 源预留请求。分类器则对传输的分组进行分类，决定所要求的q o s 级 别。调度器则根据不同的调度算法对各个队列中的分组进行调度转 发。 i n t s e r v 服务的类型主要有如下三种：( 1 ) 尽力而为服务，它是 类似当前i n t e r n e t 网上提供的服务，基本上无任何质量保证。( 2 ) 质量保证型服务2 5 1 。它主要针对实时性要求很高的应用，只要数据流 在传输参数范围内就不会被丢弃，提供带宽、时延限制和分组丢失率 来满足应用程序的要求，保证在规定的时间内到达。( 3 ) 可控负载服 务 2 6 1 。它是一种定性的服务，让用户感觉网络具有很大容量，负载很 轻的条件下运行，对延迟的要求在可忍耐的范围之内。它根据用户服 务指标来进行接纳控制处理，以限制流的数目，保证网络处于非重载 模式下。 7 持续传输速率和偶然出现的突发峰值速率，在可控负载型服务中 能够得到保证。这两个速率可以采用令牌桶的方式进行描述，避免了 纠缠于具体而复杂的网络流量的精确描述，给服务描述的具体实现机 制带来了灵活性。 1 3 3 2 区分服务模型 。 针对i n t s e r v 可扩展性差、难于实现的问题，i e t f 提出了一种 可扩展性好的区分服务模型( d i f f e r e n t i a t e ds e r v i c e s ，d i f f s e r v ) 【2 7 】【2 8 】 d i f f s e r v 具有简单有效、扩展性强的特点，它将具有相似要求 的一组业务归为一类，然后对这一类业务采取一致的处理。在 d i f f s e r v 中主要分为边界节点和内部节点。边界节点根据用户的流 规格和资源预留信息对业务流进行分类、整形、标记、聚合为不同的 流聚集，并将流聚集信息存储在i p 包头的d s 标记域，称为d s 标记 ( d i f f e r e n t i a t e ds e r v i c e sc o d e p o i n t ，d s c p ) 2 9 】。内部节点只是进 硕十学何论文 行简单调度转发，它根据包头的d s c p 选择提供特定质量的调度转发 服务，其外在特性称为逐点行为( p e r h o b _ b e h a v i o r ，p h b ) 3 0 】【3 1 1 ， 内部节点是状态无关的。 边界节点根据传输协议，对数据流进行分类和调节，其逻辑上又 可分为分类器( c l a s s i f i e r ) 和调节器( c o n d i t i o n e r ) 。分类器遵照 特定规则，根据包头的某些域将包划归到某一类别，然后交由相应的 调节控制模块处理。调节器在逻辑上又分为计量器、标记器、整形器 和丢包器。计量器测量分类器所选定的业务流的某些实时属性( 如速 率) ，并将结果传递给调节器的其它部分，标记器根据计量器传递的 状态信息来标记分组的d s c p ，并将标记好的分组添加到一个特定的 d s 行为聚集中，整形器和丢包器通过缓存或丢弃分组，使业务流符 合约定的流量规格。 调节器的实现技术比较成熟，可以通过令牌桶和漏斗桶等算法来 实现，并且通过合理地设置参数使调节器可以实现奖赏服务( p r e m i u m s e r v i c e s ，p s ) 和确保服务( a s s u r e ds e r v i c e s ，a s ) 【3 2 】这两种典型的 d i f f s e r v 服务类型。 奖赏服务为用户提供低延迟、低抖动、低丢包率、保证带宽的端 到端或者网络边界到边界的传输服务。奖赏服务是目前区分服务模型 中定义的级别最高的服务种类。 确保服务是从统计意义上保证用户的带宽，它的最初目的是：即 使在网络出现拥塞的情况下，也能保证用户有一定量的预约带宽。 目前，奖赏服务己经比较成熟、稳定，而确保服务仍然处于发展 之中，如何保证聚流之间的公平性以及聚流内各单流之间的公平性， 如何使得确保服务能够真正起到确保的作用，还有待进一步研究。 i n t s e r v 和d if f s e r v 各有所长，d if f s e r v 可扩展性强，但其灵 活性和带宽的利用率等方面又不及i n t s e r v 。 1 4 论文主要研究内容及组织 目前的调度算法有很多种，它们适应于不同的网络环境。本文主 要是围绕多优先级队列的分组调度来进行研究，由于分组调度的需 多优先级队列分组调度研究 要，对流量整形技术也作了相关研究。论文的组织如下： 第一章阐述了研究的背景、研究状况、q o s 概述以及q o s 的两种 服务模型：综合服务模型和区分服务模型。 第二章对流量整形技术作了研究，并对流量整形的常用方法令牌 桶算法进行了研究，还讨论了i e t f 的两种令牌桶算法，单速率三色 标记算法和双速率三色标记算法，进行了相关的仿真实验，在此基础 上，提出了一种与调度器相配合的令牌桶算法。 第三章研究了分组调度及其相关概念，并对与本文相关的几种分 组调度算法( 先来先服务调度算法、基于优先级的调度算法、基于时 延的调度算法) 进行了研究，为后文对分组调度进行研究奠定了基础。 第四章对p q b e d f 算法进行了研究，提出了p q b e d f _ r 算法，分析 了算法的性能。为了限制各业务流对带宽的不合理占用，将令牌桶算 法与p q b e d f _ r 算法相结合，提出了结合令牌桶的p q b e d l r 算法。根 据调度的需要，将令牌桶算法的参数改为动态设置，令牌桶之间可以 进行通讯。给出了结合令牌桶的p q b e d f _ r 算法的模型，对其性能作 了分析。 第五章0 p n e t 仿真模型的设计与仿真结果的分析。对令牌桶算法 及相关算法、p q b e d f 算法、p q b e d f _ r 算法和结合令牌桶的p q b e d f _ r 算法等构建了仿真模型，进行仿真实验，在实验的基础上，分析了 p q b e d f 算法、p q b e d f r 算法和结合令牌桶的p q b e d f _ r 算法的性能。 结语，总结本文所做的研究，明确了进一步的研究工作和主要方 向。 最后是参考文献和致谢。 多优先级队列分组调度研究 2 流量整形和令牌桶算法 因后文研究的需要，本章对流量整形技术和令牌桶算法进行研 究。本章将对流量整形的基本原理进行介绍，对令牌桶算法进行研究， 分析令牌产生速率、桶深、缓冲队列长度等参数与输出流量、延迟之 间的关系。还将讨论i e t f 的两种令牌桶算法：单速率三色标记算法 和双速率三色标记算法。在这些研究的基础上，针对调度器的需要， 对令牌桶算法提出修改的设想，提出了一种与调度器相配合的令牌桶 算法，其具体设计和实现将在第四章给出。 2 1 流量整形简介 流量整形( t r a f f i cs h a p i n g ) 【1 】也称速率整形、流量控制、传输 整形、流量引导等。它负责控制进入网络的分组的速率和数量，通过 对超出约定速率的那部分分组进行排队、缓存或丢弃，使突发的数据 流平缓下来，符合承诺访问速率的要求。流量整形的常用方法有漏桶 算法和令牌桶算法【1 】。 流量整形最早出现在处于网络交换与网络转发节点位置的网络 设备中，该技术的主要目的是为了解决突发数据流对网络所带来的拥 塞问题。流量整形限制某些业务流对整个网络带宽的占用，使得突发 流量对带宽的占用率控制在一个预先设定的范围之内，降低了流量的 突发性，使其变得可预测性。另外，经整形的数据流将变得更加平滑 缓和，这也有利于减少网络拥塞的发生和不必要的分组丢失。 2 1 1 通用流量整形 通用流量整形( g e n e r i ct r a f f i cs h a p i n g ，简称g t s ) 【3 3 】是对不 规则流或不符合约定流量规格的流量进行整形。它缓存超出流量规格 的那部分数据流，然后在适当的时候再将缓存的分组发送出去，从而 使输出流量平滑缓和，使分组的输出速率与下游网络设备相匹配。 流量整形的基本处理过程如图2 一l 所示，其中g t s 队列是用来对 分组进行缓存的。进行g t s 处理时，用分组的长度与令牌桶中的令牌 硕十学位论文 数进行比较。如果分组的长度小于令牌桶中的令牌数量则分组可以发 送出去，同时令牌桶中令牌的数量按分组的长度作相应的减少。如果 分组长度大于令牌桶中的令牌数，则分组不能被发送。令牌桶按照流 量规格约定的速率往令牌桶中源源不断地放置令牌。如果令牌桶中有 足够数量的令牌用来发送分组，则分组被继续发送下去，并且桶中的 令牌数量按发送分组的长度作相应的减少。当令牌桶中的令牌数少到 不能进行发送分组时，分组将在g t s 队列中缓存。g t s 队列的容量是 有限的，当g t s 队列没有剩余缓存空间时，新到达的分组因无法缓存 而被丢弃。只要g t s 队列中有分组，g t s 就按照一定的周期从队列中 取出分组进行发送，每次发送都将与令牌桶中令牌的数量进行比较， 直到桶中的令牌数量减少到g t s 队列中的分组不能再发送或队列中 的分组完全发送完为止。 雨重一日 2 1 2 流量监管 流量监管( c o m m it ta c c e s sr a t e ，简称c a r ) 【3 3 】主要对流入网络 节点中的某一连接的流量与突发进行控制，如图2 2 所示。流量监管 与流量整形相似，都采用令牌桶来进行。当数据流达到时，首先对分 组进行分类，对于那些不需要进行监管的分组，直接进行发送，令牌 桶不对其进行处理。如果是需要进行监管的分组，则按照流量整形的 方法，用分组的长度与令牌桶中令牌的数量进行比较，来决定分组是 否被发送。与流量整形不同的是，在流量监管中得不到令牌的分组将 不再采用缓存的方式，而是被直接丢弃。由于令牌产生速率是一定的， 因此获得令牌的分组也将是有限的，超出流量的那些分组将无法获得 令牌而被丢弃，从而达到限制流量的目的。当然在实际应用中，为了 提高网络资源的利用率，c a r 还可以对分组采取标记( m a r k ) 或重新标 记( r e m a r k ) 的方式，允许未得到令牌的分组先流入网络，当网络发 生拥塞时再抛弃带标识的分组。 多优先级队列分组调度研究 蕙霖一日 由于c a r 与g t s 对超出流量部分的分组采取的方式不同，c a r 不对分组进行缓存，因此c a r 几乎不会带来额外的延迟。 2 2 漏桶算法 漏桶算法【l6 】广泛应用于网络流量的监测与控制。它的基本原理 是，假设有一个容量有限的漏桶，桶的深度是一定的，到达的分组进 入漏桶，无论进入漏桶中的分组的速率有多大，但经漏桶后流出的分 组的速率是恒定的，即漏桶中单位时间内允许流出的分组长度是固定 的。如果漏桶中没有分组则没有分组流出漏桶，如果漏桶中装满分组， 则新到达的分组将被丢弃。 漏桶相当于一个分组队列( 缓冲区) ，先入队列的分组被送入网 络，并且队列中流出的分组的速率是恒定的。当数据流量超过队列的 容量时，多余的分组将被丢弃。 漏桶算法的优点是可以将突发的分组流变成一个恒定的数据流， 还可将速率控制在一定的范围内，保证传送到网络中的分组速率不会 高于规定的要求。它的缺点是，当漏桶满时，分组将被丢失，特别是 在经常存在突发现象的网络中，分组丢失现象严重。 2 3 令牌桶算法 令牌桶算法【l 】是流量整形和速率限制中常用的算法，它的基本原 理如图2 3 所示，令牌桶中装的是令牌，并且桶的容量是有限的，每 隔单位时间，产生一个令牌放入桶中，令牌桶装满后，新产生的令牌 将被丢弃。分组能否被发送出去是根据令牌桶中令牌数量的多少来决 定的，当桶中的令牌数大于分组的长度时就可以发送分组，并且将消 耗令牌桶中相应个数的令牌。当令牌桶中的令牌数为o 时，停止发送 数据。新到达的分组将在缓冲区中等待或被溢出。 硕十学位论文 li 数据二二盈口口口口口 图2 3 令牌桶不恿图 在令牌桶算法中，由于令牌产生速率是一定的，且令牌桶的容量 也有限，那么在单位时间内获得令牌而输出的分组也是有限的，因此 令牌桶能够限制数据的输出速率，且在长时间内输出的平均速率限定 在令牌产生速率之内。此外，令牌桶算法还允许某种程度的突发传输。 设令牌产生速率用r 来表示，深度为b ，突发数据的最大速率( 即峰 值速率) 为u e a k ，突发时间为t ，假设突发数据到达时令牌桶为 满，则有v _ p e a k t = b + r t ，那么令牌桶中的最大突发时 间1 1 为 t = b ( v _ p e a k r ) 假设数据流在一段时间t 内的平均速率为v _ a v r ，数据缓冲队 列长度为l 。下面来具体分析令牌桶各参数对输出流的影响。 ( 1 ) 令牌产生速率 当r v _ p e a k 时，分组将获得峰值的速率流向网络，而多余的令 牌将被积累，使得后面到达的数据流可以超过峰值的流速流向网络， 这对网络将是十分有害的。在这种情况下，令牌桶根本没有起到流量 整形和限制速度的作用。 当r = v _ a v r 时，如果数据缓冲区足够长，那么分组可以以v a v r 的速率流向网络。 当r l a v r 时，桶中的令牌将不断地被耗尽，而产生令牌的速 率又不及输入流的平均速率，由于没有足够多的令牌，分组在数据缓 冲区中将会溢出，分组的丢弃现象比较严重。 当v a v r r c b s 。 设承诺访问速率为c i r ，令牌的添加方式如下：每隔1 c i r 个单位时 间产生一个令牌，先往c 桶中添加令牌，c 桶满后再往e 桶中添加 令牌，若e 桶满则新产生的令牌被丢弃。在该算法中对分组的处理也 不是简单的允许通过或丢弃，而是采用标记的方式，将分组标记为不 同的颜色，标记的方式如下：如果到达的分组长度未超过c b s 则把它 标记为绿色，如果超过c b s 而未超过e b s 则把它标记为黄色，若超过 e b s 则标记为红色。在算法中，先允许标记好的分组流入网络，在网 络拥塞发生时，再对分组进行丢弃，先丢弃标记为红色的分组，然后 再丢弃标记为黄色的分组，最后才是标记为绿色的分组。 设t c ( t ) 为t 时刻c 桶中的令牌数，t e ( t ) 为t 时刻e 桶中的令牌 数，s i z e 为分组的长度。下面是单速率三色标记算法中添加令牌的 示意代码： i n i t i a l i z a t i o n ： t c ( t )= c b s ，t e ( t )= e b s f o r e a c hl c i r i ft c ( t ) = o m a r k y e l l o w t e ( t ) ：t e ( t ) 一s i z e e 1 s e m a r kr e d 感色模式： i n i t i a l i z a t i o n ： t c ( t )= c b s ，t e ( t )= e b s i f p a c k e tm a r k e dg r e e na n dt c ( t ) 一s i z e = 0 m a r k g r e e n t c ( t ) = t c ( t ) 一s i z e e l s ei fp a c k e tm a r k e dg r e e na n dt e ( t ) 一s i z e = oo rp a c k e t m a r k e dy e l1 0 w m a r k y e l l o w t e ( t ) = t e ( t ) 一s i z e e 1 s e m a r kr e d 在单速率三色标记算法中桶深的设置相当重要，不同的值代表不 同的突发尺寸大小。它可以根据具体的网络环境进行不同的设置。 c is c o 推荐的参数初始值的设置值是： c b s = c i r l b y t e b i t s 1 5 s e c o n d s ： e b s = 2 c b s 。 单速率三色标记算法在令牌桶算法的基础上增加了一个尺寸更 大的e 桶，因而它有更大的超额突发尺寸。因此，单速率三色标记算 法能更好的应用在突发尺寸变化范围较大的网络环境。此外，单速率 三色标记算法中用三种不同的颜色来区分丢弃的优先级，而令牌桶算 法则是采取丢弃的方式，因此，单速率三色标记算法更有利于提高网 络资源的利用率。但是这也增加了算法的复杂性。 硕十学何论文 2 4 2 双速率三色标记算法 双速率三色标记算法( t w or a t et h r e ec o l o rm a r k e r ，t r t c m ) 【3 5 】 主要是针对突发速率变化范围较大的网络环境。它也设置两个令牌 桶，其中一个是c 桶，桶深为c b s ( 即承诺突发尺寸) ，令牌产生的 速率为c 工r ( 即承诺访问速率) ；另一个是p 桶，桶深为p b s ( 即峰值 突发尺寸) ，令牌产生的速率为p i r ( 即峰值信息速率) 。在双速率三 色标记算法中令牌的添加方式如下：以不同的速率往两个桶中添加令 牌，往c 桶添加令牌的速率为c i r ，若c 桶满则新产生的令牌被丢弃； 往p 桶添加令牌的速率为p i r ，若p 桶满则新产生的令牌被丢弃。初 始时c 桶中令牌的个数为c 桶深的大小，p 桶中令牌的个数为p 桶深 的大小。 设t c ( t ) 为t 时刻c 桶中的令牌数，t p ( t ) 为t 时刻p 桶中的令 牌数，s i z e 为分组的长度。下面是双速率三色标记算法中添加令牌 的示意代码： i n i t i a li z a t i o n ： t c ( t )= c b s ，t p ( t )= p b s f o r e a c h1 c i r i ft c ( t ) c b s t c ( t ) = t c ( t ) + l f o r e a c h1 p i r i f t p ( t ) p b s t p ( t ) = t p ( t ) + 1 在双速率三色标记算法中对分组的标记方式如下，如果到达的分 组速率未超过c i r 则把它标记为绿色，如果超过c i r 而未超过p 工r 则 把它标记为黄色，若超过p i r 则标记为红色。算法中先允许标记好的 分组流入网络，当拥塞发生时，再对分组进行丢弃，先丢弃标记为红 色的分组，然后丢弃标记为黄色的分组，最后才是标记为绿色的分组。 双速率三色标记算法也有两种工作模式：( 1 ) 色盲模式，假设所 有的分组都是未标记的；( 2 ) 感色模式，假设所有的输入分组已经被 标记。下面是对分组进行标记的算法示意代码。 多优先级队列分组调度研究 色盲模式： i n i t i a l i z a t i o n ： t c ( t )= c b s ，t p ( t )= p b s i f t p ( t ) 一s i z e o m a r kr e d e 1 s ei ft c ( t ) 一s i z e o m a r ky e l l o w t p ( t ) = t p ( t ) 一s i z e e 1s e m a r kg r e e n t c ( t ) = t c ( t ) 一s i z e t p ( t ) = t p ( t ) 一s i z e 感色模式： i n i t i a l i z a t i o n ： t c