（通信与信息系统专业论文）ip网络的qos技术研究.pdf

摘要 摘要 q o s 概念是网络上相互通信的用户之间关于信息传输与共享的质的约定，它 打破了传统口网络的f c f s 模式，使得网络对数据业务采取“区别对待 。这样， 不同的业务类型将根据其类型和要求占用网络资源。通过这种方式，既能够满足 不同业务的要求也能使网络资源得到充分的利用。 本文研究了m 网络的q o s 技术。首先，介绍了q o s 产生的背景，概念，参 数指标，目前较流行的q o s 网络模型及常用机制。研究的重点放在了最主要的排 队和调度机制上。在研究这两种机制时，采用了排队论中的m 瓜压，1 m 模型。结合 该模型的相关参数，给出了f c f s ，p q ，w r r 以及w f q 调度算法的q o s 指标。 并结合仿真图，指出了这些算法的优缺点。基于以上的研究成果，本文又对常用 的p q + w f q 调度算法的指标进行了研究，并提出了一种能避免其w f q 队列“饿 死 的改进算法。最后，对改进算法进行了f p g a 实现。 关键词：q o s 技术调度算法p q + w f q 算法 a b s t r a c t a b s t r a c t q o si sac o n c e p to fac o n t r a c to ni n f o r m a t i o nt r a n s m i s s i o n & s h a r i n gb e t w e e n n e t w o r ku s e r s t h ec o n c e p ts m a s h e dt r a d i t i o n a lf c f sm e c h a n i s mo fi pn e t w o r k s ，a n d m a k ed i f f e r e n td a t ad i f f e r e n t l yt r e a t e d i nt h i sw a y , d i f f e r e n ts e r v i c ed a t aw o u l de n j o y r e s o u r c eb a s e d0 1 1t h e i rs t y l ea n dr e q u i r e m e n t t h i sn o to n l ys a t i s f i e st h er e q u i r e m e n t o fd i f f e r e n ts e r v i c e s ，b u ta l s om a k e sr e s o u r c e sf u l l yu t i l i z e d t h i sp a p e rd e a l sw i t hq o s t e c h n o l o g i e so fi pn e t w o r k s f i r s t l y , i ti n t r o d u c e sq o s b a c k g r o u n dk n o w l e d g e ，c o n c e p t ，p a r a m e t e r s ，p r e s e n tp o p u l a rq o sn e t w o r km o d e l sa n d c o m m o nm e c h a n i s m s r e s e a r c he m p h a s i si sp u to nt h ek e ym e c h a n i s m s 一一q u e u i n ga n d s c h e d u l i n g i nt h er e s e a r c h , m m 1 mq u e u i n gm o d e li sa d o p t e d b a s e dt h em o d e l p a r a m e t e r s ，i tp r e s e n t sq o sp a r a m e t e r so ff c f s ，p q ，w r ra n dw f qs c h e d u l i n g a l g o r i t h m s f r o mt h es i m u l a t i o np i c t u r e s ，i ta l s o d i s c u s s e st h ea d v a n t a g e sa n d d i s a d v a n t a g e so ft h e s ea l g o r i t h m s o nt h eb a s i so fa b o v er e s e a r c hf i n d i n g s ，i ts t u d i e s t h ep a r a m e t e r so fc o m m o np q + w f qa l g o r i t h ma n dp r o p o s e sa ni m p r o v e do n e ，w h i c h c a ne l i m i n a t et h e “s t a r v a t i o n p h e n o m e n ao fw f qq u e u e f i n a l l y , a u t h o rd e v e l o p st h e i m p r o v e do n eb a s e d0 1 1f p g a k e y w o r d ：q o st e c h n o l o g i e ss c h e d u l i n ga l g o r i t h mp q + w f qa l g o r i t h m 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名：墨叠垄 导师签名：丕连至k 日期 ! 墨墨2 日期p z 咀 第一章绪论 第一章绪论 1 1i pq o s 产生的背景 2 0 世纪6 0 年代美国国防部( d o d ) 开展了a r p a n e t 计划。该计划的目的 是要基于网络通信协议( n c n ) 构建一个不会受单一或局部故障影响的高性能网 络。国防部的高级研究计划局( a r p a ) 承担了此计划，随后推出了a r p a n e t 网络。后来，a r p a n e t 与n s f n e t 相连后，用户数量成指数增长，最后又与北 美，欧洲和亚太地区的网络得到了互联。这就是现在广泛而深刻影响着我们的 i n t e m e t 。因此a r p a n e t 也成了i n t e m e t 的前身。 到2 0 实际7 0 年代，d o d 所属的国防通信局负责a r p a n e t 的运作。它将 a r p a 更名为d a r p a ，同时也逐渐将n c p 协议改换成t c p i p 的雏形。2 0 实际 8 0 年代，为了推广t c p i p 协议，d o d 以廉价的方式提供给社会。再加之，加州 伯克利大学成功的将t c p i p 植入到b s du n i x 系统，这使得t c p i p 协议走上了 使用的阶段。1 9 8 3 年，d o d 要求与a r p a n e t 互联的所有电脑都使用t c p i p 协 议。因此，该协议也成为互联网通信的基本机制。 然而，互联网的发展日新月异，其技术的难度，网络结构的复杂性及庞大的 网络规模都远远超出了人们的预料。伴随着互联网的迅猛发展，一些越来越严重 的问题也显现出来，其中一个就是服务质量( q o s ) 。 现在的互联网提供尽力而为( b e s t e f f o r t ) 的服务方式。在这种方式中，路由 器采用先到先服务( f c f s ) 的策略，最大限度的将口报文投送到目的地。所有数 据流都被“一视同仁 ，公平的竞争网络资源。这种方式较适合e m a i l ，邱等业 务，但对m 报文传递的可靠性，时延等却提供不了任何保证。 随着因特网的发展，其上的数据业务也得到了快速和多样的发展。特别是随 着多媒体和一些实时性要求高的业务的出现，对带宽，延时和抖动等也提出了更 高的要求。这就对现有的网络服务策略提出了挑战。 q o s 概念的提出有效地解决了现有网络在这方面的不足。它是对网络( 或网 络间) 的传输质量和服务可用性的测量，目的是为不同用户( 或数据流) 提供有 保障的服务。 i p 网络的q o s 技术研究 i 2 q o s 的概念及其参数 q o s 是网络上相互通信的用户之间关于信息传输与共享的质的约定”1 。传统 的i n t e m e t 网络中的各用户( 或数据流) 遵循f c f s 原则，公平的共享网络资源。 而q o s 则通过事先的约定对各用户( 或数据流) 采取不平等的对待方式，使它 们共享资源。口网络中，q o s 的概念采用时延，报文丢失率，抖动，带宽等参数 来衡量。 时延：数据报文从发送到被接收所经历的时间。 报文丢失率：在数据传输过程中，被丢弃的报文数与发送报文总数之间的比 率。 抖动：报文时延的变化量。 带宽：一个连接在单位时间内传输的最大字节数。 q o s 只是一项技术，它基于现有的网络资源，根据各用户( 或数据流) 提出 的服务要求和网络的拥塞程度，对网络资源进行灵活，动态及有效的管理。 1 3i p q o s 的研究现状 t pq o s 的人致发展经历可用下图来描述 圈llo o s 的发展 尽力服务模型为现在互联网上所采用的传输策略。它对各用户( 或数据流) 视同仁，尽自己所能将数据传递到目的地，因此各用户( 或数据流) 之间是平 第一章绪论 等的。这种服务方式虽能有效的利用网络资源，但对一些对服务有特殊要求的用 户( 或数据流如：语音，信令和一些视频等) 却不能提供有保证的服务。 综合服务模型克服了尽力服务模型不能提供有保证的服务质量的不足。它根 据用户( 或数据流) 提出的服务质量要求，采用资源预留的方式，为它们预订网 络资源，以此来保证服务质量。 差分服务模型采用对口报文分类的方法来实现有保证的服务质量。在差分服 务模型中，路由器分为边缘路由器和核心路由器。边缘路由器的主要功能是对疋 报文进行分类，并在拥塞发生时，在网络的边缘将p 报文丢弃。而核心路由器则 根据不同优先级为m 报文提供不同的q o s 保证。 多协议标签交换使用m p l se x p 字段来传送q o s 信息。它的边缘路由器可 根据不同的算法提供不同的分类粒度。在m p l s 网络内部，采用w f q w r e d 的 转发机制来提供q o s 保证。这也降低了网络的复杂性。 在q o s 发展的过程中，新的模型不断涌现。随着复杂度的增加，q o s 模型也 不仅仅限于最初为用户( 或数据流) 提供有保障的服务，它也用于网络的安全性， 并且其自身也更智能化，自动化。 自动化的q o s 可以让管理员通过输入一些命令来实现对q o s 的设置。c i s c o 公司在其l a n 和w a n 的c a t a l y s t 交换机和c i s c oi o s 路由器上都采用了自动化 的q o s 。其a u t o q o s 企业版的功能简化了q o s 的实现并加速了对c i s c o 网络上的 语音，视频和数据的q o s 保障，这既减少了人工错误，也降低了培训开销。a u t o q o s 创造了类别映射和策略映射n 1 。 q o s 虽然不能消除蠕虫对网络的攻击，但在一定程度上能降低他对网络的影 响和风险。作为安全工具的q o s 通过其管制器对网络上的流量进行监测，并在尽 可能接近攻击源的地方对异常流量做出反映。这种机制虽不能发现蠕虫的变体， 但却可以管制它们n 1 。 1 4 本文的主要工作 本文介绍了q o s 的发展过程和现有的模型，工具。在此基础上，着重研究了 q o s 的排队和调度算法，结合m m 1 m 排队模型的知识，给出了f c f s ，p q ，w r r 及w f q 调度算法的q o s 参数指标。在对这些调度算法研究的基础上，分析了是 目前常用的p q + w f q 算法及其改进算的q o s 参数指标。最后，用f p g a 实现了 改进的p q + w f q 调度算法。 3 4 口网络的q o s 技术研究 1 5 本文的结构安排 本文共分五章。第一章为绪论部分，介绍了i pq o s 产生的背景，概念，参数 指标，研究现状，主要工作和文章的结构安排。在第二章中，详细介绍了现有的 q o s 模型i 综合服务模型，差分服务模型以及多标签协议模型。并对上述模型的 优缺点进行了分析。在第三章中，分别介绍了分类器，标记器，整形机制和拥塞 控制机制。第四章结合排队论中m m 1 m 知识，详细研究了基本调度算法的q o s 参数指标。在第四章对基本调度算法研究的基础上，第五章研究了p q + w f q 调 度算法及其改进算法的参数指标，并对改进算法进行了f p g a 的实现。 第二章现有q o s 模型介绍 第二章现有o o s 模型介绍 21i n t s e r v 模型( 综合服务模型) 综合服务模型避免了阻前尽力而为服务的弊端，能够为多种业务提供有q o s 保证的服务。它的这种保证是基于资源预留机制实现的。在需要q o s 保证的应用 业务开始之前，资源预留机制先通过特殊的信令向网络申请资源。这个信令带有 该业务所需的q o s 参数，如带宽，时延抖动等。当网络能够为该业务提供q o s 服务时，它就向其发送确认信息，并在所要经历的网络节点为其预留网络资源。 应用程序在接到确认信息后，便可发送数据。该业务发送的数据必须符合其q o s 需求，当它实际使用的网络资源超出了其q o s 需求时，超出来的这部分将受到特 殊的处理( 延迟或丢弃) 。 图2 1 采用r s v p 的i n t s o r v 髓络 在网络资源允许的情况下，r s v p 会为每个要求q o s 保证的业务预留资源， 从而减少了网络的拥塞，使得各业务的服务得到保证。r s v p 是单向的，它要在 业务数据所经过的每一个网络节点上为其预留资源，是适合于点到点或点到多点 的通信业务。 r s v p 的工作过程”： 发送方向目的地址发送一个p a t h 消息，该消息包含了业务流的各种特征信 息，如带宽需求，延时和抖动等。支持r s v p 的路由器生成“路径状态”信息， 其中包含p a t h 消息的前一个源地址。 接收方在接收到p a t h 消息之后，发送r e s v 消息。该消息包括请求说明 ( r s p e c ) 和过滤说明( f s p e c ) 。其中，r s p e c 声明综合业务的类型f s p e c 进行资 6 i p 网络的q o s 技术研究 源预留的分组。 相关路由器在接受到r e s v 消息之后，对资源预留请求认证，并分配所需要 的网络资源。如果认证失败，路由器向接受方返回错误信息。成功预留资源之后， 路由器向相邻路由器发送r e s v 消息。 最后一个确认r e s v 消息的路由器向接收方发送确认信息。 发送方和接收方完成了一次r s v p 会晤之后，将拆除资源预留的全过程。 i n t s e r v 模型具有以下优点n 1 ： 1 模型简单，易于与网络策略管理集成。 2 连接接入控制能力( c a c ) ，可以指示端点其所需的带宽是否可用。 3 独立的每条q o s ，使之从体系结构上适合语音呼叫。 4 为每条数据流都留有足够的网络资源，因此能够提供较强的q o s 保证。 i n t s e r v 模型的缺点： 1 r s v p 的使用，使得链路的建立时间变长。 2 r s v p 需要在数据流所经过的每个网络节点上为该业务预留资源，这使得网络 节点变得复杂。 3 i n t s e r v 模型是基于数据流的，这使得当数据流很多时，网络的管理变得复杂。 当需要有q o s 保障的业务较多时，一些“资源碎片得不到充分的利用。同 时也使得服务“被拒 的概率增高。 4 可扩展性较差。 2 2d i f f s e r v 模型( 差分服务模型) 2 2 1d i f f s e r v 模型介绍 差分服务模型是一个多级服务模型，它采用队列，整形，流控，标记和分类 机制( 将在下一章中介绍) ，为不同的业务提供不同的服务，以此来提供q o s 保证。 差分服务模型网络中的路由器分为两种：边缘路由器和核心路由器。它们在 网络中扮演的角色不同。边缘路由器主要是为业务流的数据报文进行标记，并将 它们投递给核心路由器。而核心路由器则是根据各数据报文的标记对其进行排队， 并在适当的时候进行调度，投递给下一路由器。 第二章现有q o s 模型介绍 ；回回回国| 图2 2d i f f s c r v 网络模型图 d i f f s e r v 模型具有以下优点： 1 数据报文的转发不是基于每条流的，因此网络管理相对简单。 2 不需要发送r s v p ，因此发送端发送数据的等待时间比i n t s e r v 模型的要短。 3 网络资源不是固定分配给每条流的，因此可以充分的利用网络资源。 4 网路路由器分为边缘路由器和核心路由器，因此各种路由器的功能相对简单， 实现方便。 5 有较好的可扩展性 同时，d i f f s c r v 模型也具有以下的缺点： 1 由于网络资源不是分配给数据流的，因此不能提供严格的端到端服务质量保 证。 2 核心路由器只处理数据报文，“看不见 数据流，因此它不能为每条数据流提 供绝对的q o s 保证。 2 2 2d i f f s e r v 模型中数据报文的优先级标记 d i f f s c r v 模型中，边缘路由器对数据流的报文进行标记，这种标记采用如下两 种机制： 1 ) 基于p 优先级的标记 这种方法采用i p 报文头的t o s ( t y p eo fs e r v i c e ) 字节来标记该报文的优先 级。t o s 字节的高三b i t 用来表示报文的优先级。 7 i p 网络的q o s 技术研究 t n s 字段 囤2 , 3i p 优先级标记字段 该标记方法总共提供8 种优先级，优先级6 ，7 通常为网络控制流量预留。0 用于默认标记值。剩下的5 个优先级的用途如下： 优先级5 用于语音 优先级4 用于视频会议和流式视频 优先级3 用于呼叫信令 优先级l ，2 作为标记选项 尽管这种标记方法操作起来简单，但所提供的标记粒度有限“1 。 2 ) 基于d s c p 的标记 这种标记方法采用t o s 字节中的高6 b i t 对数据包进行标记。它所能提供的标 记粒度为6 4 个( 0 1 6 3 ) 。d s c p 可采用数字形式或指定的关键字名称表示，称为 逐跳行为( p h b ) 。p h b 有三种类型：尽力服务( d s c po ) ，确保转发( a f x y ) 和加速转发( e f ) 。 r f c2 5 9 7 定义了四个确保转发类型，采用字母( a f ) 和两位阿拉伯数字表 示。阿拉伯数字的第一位表示a f 分组，取值为1 + 4 ，对应于d s c p 的高三位。 第二位表示每个a f 分组的丢弃优先级，取值为1 3 ，分别对应与低高丢弃优先 级。 t o s 字段 卜。_ 、 l _ 、广l 一、，j 类别 丢弃优先缀 图24d s c p 的编码机制 第二章现有q o s 模型介绍 d s c p 中p h b 的十进制与二进制之问对应关系见下圈 篙护并 卫圈置 圈囝互 囝回墨 日囤囝 围2 5d s c p 中p h b 十进制与= 迸制对应关系图 在差分服务模型中，网络边缘路由器根据数据报文分类方法对报文进行分类， 并投递给核心路由器。核心路由器根据报文的d s c p 将其存储到相应的队列中， 并在队列出口处采用调度算法对不同的优先级队列进行调度，使数据报文占用相 应的网络资源。 m p l s 介绍 2 3 多标签协议( m p l s ) 模型 与使用报文中t o s 字段标记q o s 不同，在m p l s 网络中，q o s 信息是标 记在m p l s 的c o s 字段中的。m p l s 网路中，有两种路由器：标签边缘路由器 ( l e r ) 和标签交换路由器( l s r ) 。传输的数据不再是m 报文，而是在口报文 前封装了标签的数据。因此，m p l s 网络中的路由器不再根据p 报文的目的地址 为其查找下一跳路由器，而是根据报文前的标签查找其出口标签，并根据下一跳 接口将该包送出。m p l s 网络工作原理图如下： 口阿络的q o s 技术研究 图2 6m p l s 阿络工作圈 m p l s 网络的具体工作过程如下： 1 当l e r 接收到刚进入m p l s 网络的口报文后，根据目的地址和业务等级对 其进行对等转发分类( f e c ) ，以此将输入的数据流映射到一条l s r 上。当数 据报文进行完f e c 后，l e r 将根据标签信息库( l i b ) 生成一个标签，封装 到报文前。然后，将其投递给下一路由器( l s r ) 。 2 当网络中的l s r 收到报文后，先根据数据报文的标签在l i b 中进行查询，找 出其对应的出口标签。再用该标签替换入e l 标签，最后将报文从出口接口发 送出去。 3最后，数据报文将被送出网络。当到达出口l e r 时，它将报文的标签删除掉， 重新变为口报文。 l s p 链路的建立有两种方法：h o p - b y - h o p 和显示路由方式。 h o p - b y - h o p 路由；h o p b y - h o p 是从源站点到特定目的站点口树的一部分。 在网络中的每个节点，通过对等层交换标签一级一级为下一跳分配标签。 显示路由( e r - - l s p ) ：从源端到目的端直接建立一条路径，m p l s 将显示路 由嵌入到限制路由的标签分配协议信息中，从而建立这条路径，以实现端到端的 q o s 。 m p l s 流量工程( m p l st e ) m p l s t e 通过显示路由来建立l s p 。通过建立一条或多条l s p 来实现分流， 以此来平衡网络负载。在选择l s p 时，选择流量小的l s p ，通过这样有针对性的 选择使得一部分流量避开负荷较重的l s p 。也可以为同一数据流选择多条l s p ， 第二章现有q o s 模型介绍 使业务流量分摊到不同的l s p ，来合理利用网路资源。这样做，不会引起通过修 改i g p 权值而导致的解决了一条链路拥塞而可能引发其它地方拥塞的问题。 m p l st e 有以下特点口1 ： 路径选择：m p l st e 采用显示的路由选择方式。 负载均衡：m p l st e 可以配置两条或多条l s p 来承载同一用户的口业务流， 根据网路资源的利用情况，合理地将业务分摊到这些l s p 上。 路径备份：m p l st e 可以配置两条l s p ，一条处于激活状态，另一条处于备 份状态。一旦主l s p 出现故障，业务立即进行切换。 故障恢复：当一条已经建立的l s p 在某一点发生故障，故障点的m p l s 会向 上游发送n o t i f i c a t i o n 消息，通知上游l e r 重新建立一条l s p 来 替代这条出现故障的l s p 。上游l e r 就会发出r e q u e s t 消息建立 另一条l s p 来保证用户业务的连续性。 第三章q o s 机制介绍 3 1 1 标记机制 第三章0 0 s 机制介绍 3 1 标记机制和分类机制 标记足修改分组头中的某个字段，阻记录分类器得到的决定动作。通常采用 的标记方法有： 1 m p l s 实验位 m p l s 使用m p l s 标签封装m 报文。它有3 位用于c o s 标记，称为m p l s e x p 位。m p l s e x p 位在l s 标签中的位置见下图 。 隧塑溷s 图31 m p l s 标签中的m p l s e x p 位 由于m p l se x p 位和口优先级位的长度相同，因此它们之间可以通过映射 进行转换。而m p l se x p 与区分服务代码点之间却不行。 2i p 服务类型和口优先级 3 区分服务代码点 第2 ，3 中标记机制可参见22 2 节。 分类机制 分类是通过检测一个分组的特定字段，来判断该分组的类型以及属于哪条数 据流，并决定对它的处理动作。 网络基于标记字段，对数据报文的处理是有区别的。因此，对报文的标记应 在靠近源的可信任设备内。这样可以使网络在靠近数据源的地方对数据报文进行 q o s 管理。 i p 网络的q o s 技术研究 3 2 管制器 3 2 1 管制器的功能和常用算法 管制器机制是对流量违约进行即时检查，对于出现的违约显现采取相应的动 作。它对违约流量采取的动作通常为标记和丢弃。通常管制器使用令牌桶算法 进行建模。 令牌桶算法每隔单位时间( 通常是一秒) 添加令牌。一个令牌允许相应单位 的数据量通过。当桶中没有令牌时，不允许数据通过。通过这种机制对数据流量 进行管理。 在单位时间的最后。可能会有一些剩余的令牌。对这些令牌的处理是区分管 制器的关键。 目前较常见的管制器令牌桶有： 单速率双色管制嚣( 单令牌桶算法) 在单速率双色管制器机制中，流量被标记为两种状态( 颜色) 之一，符合和 违约。当流量为符合时，将被放行。否则，将被视为违约流量对其进行标记或直 接丢弃。 单速率双色管制器的算法流程图及效果图如下； 。l t 、 rt 图3 2 单速率双色管制器的算法流程图 一- 同工一 一- 第三章q o s 机制介绍 单速率三色管制器采用双令牌桶算法。在单位时间的术尾，第一个令牌桶中 i。 ；夕、 y _l a i m 图3 4 单速率三色管制嚣的算法流程曰 00+ 一- 嗣一 伊网络的q o s 技术研究 图3 5 单速率三色管制器的效果图 2 双速率三色管制器( 双令牌桶算法) 双速率三色管制器采用双令牌桶算法。它的两个令牌桶相互独立，各有一个 令牌速率。该机制允许保持一定速度的过量突发，无需通过信用量的积累以调节 临时突发，也允许对超过不同突发值的流量采取不同的动作。 双速率三色管制器的算法流程图及效果图如下： 卫= h ：；j ，_ ：_ ， i = 开 ：l l y11 图3 6 双速率三色管制器的算法流程图 - + 嗣一 第三章q o s 机制介绍 t 兰色f 螂黼曩( 取撬f 枷， 1 7 图3 7 双速率三色管制器的效果图 上述三种管制器的对比： 1 ) 单速率双色管制器在单位时间末尾将剩余的令牌丢掉，故它不支持突发流 量，任何超过速率限制的留恋都将被标记或丢弃。 2 ) 单速率三色管制器在单位时间末尾将第一个令牌桶中剩余令牌放入到第二 个令牌之中。因此，该机制可以支持一定时间的突发流量。假设令牌桶深为g ， 存放溢出令牌桶的深度为g ，每次添加令牌的时间间隔为r ，突发数据的流量 速率为y 丑，则单速率三色管制器可支持突发数据的时间为： t = z ( 五( v 。一c ：)( 式3 1 ) 3 ) 双速率三色管制器的两个令牌桶都有各自的令牌速率，任何超过限制速率且 未超过峰值速率的流量都可以放行。这无需积累未用的令牌。 3 2 2 管制器对q o s 指标的影响 一粹= 薯砌? 吞吐量：钆= 泛b w 曰w 其 i 时 i p 网络的q o s 技术研究 图4 12f c f s 机制中抖动与m ，p 的戈系图，p l 时 ( 式4 6 ) 第四章捧队和调度机制 圈4 22f c f s 机制中丢包率与m ，口的关系曲线图，p ? 丑。其中，以为组成它的队列的参数。 从b w 的公式可以看出，当b 瞅，。较大时，优先级较小的队列可能会出现“饿 死”现象。这也是p q 机制的一个很大的缺点。 豢 嘣中善n 爿占用的蕾直 i ：麓1 i ：翟。l ，一1 1 1 ； 一 。 一 l l八 f f f ；7 l k l i 图4 4 p q 机制中的流量“饿死”现象 从上图中可以看出，在p q 机制中队列 铡拥有绝对的优先权。同时在 0 3 0 的单位时间内，跏绷一直处于“饿死 状态。 w r r 机制 w r r 机制的主旨是要解决p q 机制中出现的流量“饿死 现象。它通过引 入循环调度机制，为各队列提供了带宽保证。从而很好的解决了p q 机制中的“饿 死”现象。但是这样的解决方法也使它不具有对实时数据流量的处理能力。 w r r 机制对q o s 指标的影响： 设在单位时间内，分配给第f 个队列的带宽为b 形，时间为f f ，系统总带宽为 第四章排队和调度机制 b wo 1 抖动 i - i j i t t e r o 一, = 阡二+ ( 1 一) + z t 暑l = + ( 1 一+ 善i - i 。( i i 4 - 1 8 ) 上式中瞧。为单位时间内，第f 个队列中数据包的平均经历时间，n 为在拥 塞时，该报文进入队列所排的待处理段序号( 从0 计) 。由式可知w r r 机制对 坍舭饧的贡献仅与该队列分配到的带宽比有关，且为定值。由式4 1 8 可知， 通过减小单位时间可以得到较小的抖动。 2 时延 乃蝴= 疋触f + 坍f f 劣函嘲 ( 式4 1 9 ) 3 丢包率 矿磊= 象m + l p i = l t 上式中，d 2 。 毒 4 带宽与分配给各队列的处理时间相关 譬 一，l 、 ，- 、 ， r k 、 | ， 鲁口j j | ，| | 、f 。j ? 久 、奠 i 蜮j l7 n ；气一蠢弋岁。 f ； 、?、 ￥ 1 jj j j 强 l _ _ 量产羔、鞘胁l 7 一r 矿 妒 ? j 时 i f 7 一 ； 图4 5w r r 机制中各数据流占用的带宽图 m 网络的o o s 技术研究 由上图可见，在w r r 机制中，各队列都能够占有一段带宽。从而，有效的 避免了p q 机制中的“饿死”现象。 w f q 机制 尽管w r r 机制较好的解决了p q 机制中的流量“饿死”现象，但是各条队列 的带宽分布不尽合理。w f q 机制的主旨就是要解决w r r 各队列之问带宽的公平 分配问题。w f q 中的w ( w e i g h t ) 指各队列的权重，f ( f a i r n e s s ) 指各队列分配 的带宽公平性。 与前几种机制不同，w f q 是基于数据流对报文进行动态分配的。捧队机制将 具有相同五元组( 目的口地址，源口地址，目的端口号，源端口号，协议号) 的数据报文认定为一个数据流，并将它们映射入一个队列。w r q 机制中，各队列 权重的分配是根据各数据流的优先级进行的。这样可以保证高优先级的流占用 更多的带宽，使得带宽资源得到公平合理的利用。 各数据流的权重计算方法如下：假设有4 条数据流，它们的优先级分别为0 ， 1 ，2 ，3 。各数据流占用带宽的百分比的计算公式为( 1 p 优先级+ 1 ) s u m i p 优先 级。则它们占用带宽的百分比分别为：1 1 0 ，1 5 ，3 1 0 ，2 5 。 假设有n 条数据流，权重分别为n ，n - 1 3 ，2 ，1 。队列之间消耗各自权重 所经历的时间相同，即各队列消耗一个权重能够占用相同的带宽资源。将队列的 所有权重消耗完经历单位时间。队列的权重如下( 权重上的数字为消耗它们的顺 序) ； 口口口口口口口口口口 口口口口口口四口四 口口口口口口口四 口口口口口四四 口口口口 口口口 口口 口 图4 6 w r q 机制中吾队列的权重 第四章排队和调度机制 第_ 个队列的最大权重 第个队列的当前权重 第歹个队列中数据报文的平均经历时间 1 抖动 第歹个队列对q 中数据报文的抖动影响为： w懈j-coi+1 莩，一 = i 坠生兰p j 则q 中数据报文的抖动为： 慨即呷一1 1 1 e k i ，) + 善赘+ 毫甏 吖岬一是卜w m 缸j 上w m jm 叫一旷 ( 式4 - 2 2 ) 上式中，彬撒。q 。将上式与( 式4 1 8 ) 相比可以看出，在相同的条件下，( 式 4 - 2 2 ) 和( 式4 - 1 8 ) 只有最后一项不同。两种机制中，抖动的大小就由最后一项决 定。 2 时延 ，= 疋椭+ j i t t e r 国， ( 式4 2 3 ) 3 丢包率 = 岛= 黎m + l 篇 上式中，辟= 豇言 ( 式4 - 2 4 ) 曩 0池哆 3 2 m 网络的q o s 技术研究 4 带宽 第i 个队列占用的带宽为： 即是昂 拭4 屯5 假设w f q 机制中有四条数据流，它们的优先级分另i j 为3 ，2 ，1 ，0 。则它们 占有的带宽仿真图如下： * f a k 抻鲁教掀占用盼蕾膏 l j | u ，一 f ? f j f ，一 ? l ? l r 。 l 一 f万 。一 j 旷 一r一。l 。 图4 7 w f q 机制带宽分配图 虽然w f q 机制较好的解决了w r r 机制中各队列占用带宽资源的公平性问 题。但是w f q 的这种“偏袒 高优先级队列的机制又丧失了w r r 中的最小带宽 保证的优点。当一段时间内，高优先级数据流较多时，使得低优先级数据流竞争 不到网络资源。并且，w f q 机制不能对实时性要求高的数据流作出有效的反应。 对于w f q 调度算法中各队列的权重计算，一般有两种方法。一种基于时间 块。另一种是基于数据报文。第一种方法给机制引入的判断队列权重的时间较少， 因此时间利用率高，但是数据的抖动较大。而第二种方法引入的判断时间较多， 但抖动较小。下图给出了两种判断机制的时延比较。 第四章排队和调度机制 n _ 一 匮 r 一_、 、 l 夏” “”4 | _、 f 图4 8 基于时间块和报文的w f q 调度算法时延比较 f c f s ，p q ，w r r ，w f q 四种调度机制的比较 为了直观的分析上述四种调度算法的优劣性，首先比较它们q o s 参数指标。 研究时，采用下图中的网路拓扑结构。其中，0 ，l ，2 ，3 节点分别向4 节点发送 数据，4 节点分别采用上述四种调度算法将数据发往5 节点。网络的具体参数见 附录a 。 引4 9 比较f c f s ，p q ，w r r ，w f 0 机制时采用的网路拓扑图 p 网络的q o s 技术研究 1 丢包率 i ；| 凼 o 、，u ； 】 一 一 图4 1 0 f c f s ，p q ，w r r ，w f q 机制中第一条数据流丢包率的比较 ， 们 。8 。7 。j 莹。s 。 。3 。2 。1 。 f c f s p a 慵m 喊中簟= 蓑藏毫的丢色覃 廿f c f s ip o “+ w 目舟 争w f o 1 。八 ，l 、y 、 一 ￥ 。1 f v 、x _ ；l l ； 卵 j ! n 气； i l u 一一 第四章排队和调度机制 v c f s p o w m v 怦o t t 夸f c f s l - - e - w f o l i矗 土j ，7 、：，7 ； 1 、t 、 鼍 。 j i f t 生：。b 、= ：；吐患“：，。- i 一t 人 j j f l l 7 i f 甘s 舶牌州f o 一中t 四薹托蠢的薯1 t 1 r 、 卜4 一、， 、- ，。、j 1 k 。；了 、v 、 一一 、 、。 ! ! l f 7 口网络的q o s 技术研究 队列的数据。因此，该机制的丢包率呈明显的锯齿状，不稳定。振荡的幅度则取 决于给各队列分配的时间。就这四种机制的丢包率而言，w f q 机制的则较平稳。 2 时延 图4 1 4 f c f s ，p q ，w r r ，w f q 机制中第一条数据流时延的比较 图4 1 5f c f s ，p q ，w r r ，w f q 机制中第二条数据流时延的比较 第四章排队和调度机制 暑 f c f s 户a 懈胛喊埘中蕈兰披重蠢盼时置 一 圈 i j 、 、 、 、 r ”“” 。f ，i f ，i 1 l ： 1 k k ：日女目自自日日日g g 女# 镕g m h _ 目w # b 日”h m $ _ r h 自自自a 绷 l 图4 1 6f c f s ，p q ，w r r ，w f q 机制中第三条数据流时延的比较 园-9 f c f s 少1 飞 h m 妇竭 一一 一一一 1 3 7 图4 1 7 f c f s ，p q ，w r r ，w f q 机制中第四条数据流时延的比较 从上面的仿真图可知：p qh i g h 的时延最小，适合实时性要求高的数据。而当 p q 机制中高优先级队列数据到达率较大时，低优先级队列的则时延迅速恶化， 成为最差的。f c f s 和w f q 机制的较平稳，而这两者之中，f c f s 较差。由于 3 8 p 网络的q o s 技术研究 w r r 机制的特点，其时延也呈锯齿状，不稳定。 3 抖动 l ，譬8 l l = 潲l 图4 1 8 f c f s ，p q ，w r r ，w f q 机制中第一条数据流都抖动的比较 l 口f c f s i 刨 - j l , 土k t 4 “ i 1l j ? j ? 琊 1 1 1 t t t t ” 。：l | | ：| l ? l 图4 1 9f c f s ，p q ，w r r ，w f q 机制中第二条数据流抖动的比较 第四章捧队和调度机制 7 - 。 m 蕊丽睢唧 ”m - 川h i m1j ilh h l g m i h u h 4 图4 2 0f c f s - i , q ，w r r ，w f q 机制中第三条数据流抖动的比较 图42 1 f c f s ，p q tw r r ，w f q 机制中第四条数据流抖动的比较 从上面的仿真图可知：w r r 的抖动最大，分配的时间越多，则抖动越小。w f q 机制则次之。r q 机制高优先级队列的抖动较小。该机制抖动的大小主要取决于 两个因素：队列的优先级大小和高优先队列数据的到达率。队列的优先级越低， i p 网络的q o s 技术研究 同时，高优先级队列的数据到达率越大，则抖动越大。 结合四种调度机制的实现方法及它们的o o s 参数指标可以得出以下结论t 表4 1f c f s ，p q ，w r r ，w f q 调度算法的比较 调度机制优劣 实现简单，抖动小，各数据流对数据“一视同仁 ，不能照 f c f s按照到达顺序公平使用带宽顾到数据的优先级，丢包率较 大，报文长度短的数据排队时 间较长 实现简单，抖动小，q u e u eh i g h机制过于僵硬，当高优先级队 队列的时延和丢包率最小，能列拥塞时，低优先级队列中的 p q满足实时数据要求数据延时和丢包率很大，并且 会有低优先级队列中的数据 “饿死 现象 能够照顾到各条数据流，有效抖动很大，对各数据流的带宽 愀 地避免了p q 机制中的“饿死分配不尽合理，不能处理实时 现象，时延相对较小数据 能够公平的照顾到各数据流的实现起来相对复杂，调度前需 w f q 带宽，时延，抖动，丢包率较要判断各队列的权重，引入了 小一定的时间开销，不能处理实 时数据 第五章p q + w f q ，改进的p q + w f q 算法及f p g a 实现 4 l 第五章p q + w f q ，改进的p q + w f q 算法及f p g a 实现 第四章中介绍的几种基本调度算法各有优缺点，没有一种能够对数据流的特 性作出统筹兼顾的反映。为了满足实际中各种数据对q o s 指标的要求，可将p q 和w f q 两种调度算法相结合形成新的p q + w f q 调度算法。该算法中p q 队列用 于调度对实时性要求高的数据，如语音和信令等。而w f q 算法则调度其它非实 时性数据。 5 1 p q + w f q 机制的q o s 指标 在研究p q + w f q 机制时，可将参加w f q 调度的队列合起来看成一个优先级 最低的p q 队列。 1 抖动 p q + w f q 中p q 队列的抖动可参见4 3 节。在此