（计算机应用技术专业论文）基于qos的公平带宽分配策略的队列管理算法研究.pdf

摹十q o s 的公1 7 带贺分配策略的队列管理算法研究 摘要 随着i n t e r n e t 的飞速发展，网络应用如：i pt e l e p h o n y 、v o d 、w w w 等多媒体应用的层出不穷，使i n t e r n e t 逐步由单一的数据传输网向数据、语 音、图像等多媒体信息的综合传输网演化。在高速网络中，按照用户请求信 息的不同，有效的分配网络带宽、提供q o s 控制是i n t e r a c t 发展的核心技术 之一，也是当前学术界计算机网络通信领域研究的热点问题。 近来，随着b t 、e d o n k e y 等p 2 p 应用软件的普及使用，q o s 的带宽公 平性问题正日益受到关注。带宽公平分配问题j 下是本文主要研究内容。为了 有效实现带宽的公平分配问题，本文主要做了以下工作： 首先对实现带宽公平分配的几种算法进行了深入的研究，分析了算法在 带宽分配公平方面所做的贡献，总结了算法的优点和缺点并对这些算法做了 详细的理论分析与定性比较。针对目自口在无状态网络体系结构下实现公平带 宽分配的c s f q 算法进行深入的研究。我们详细分析了c s f q 算法的优缺点， 发现其仍有诸多需要改进之处，比如由于它的丢包算法是针对u d p 流等非 响应流导出的，不适用于t c p 流。 本文针对t c p 流传输控制的特点提出了一种改进的c s f q 算法。对t c p 流使用了与u d p 流不同的丢包策略，较好地解决t c p 流与u d p 流的带宽分 配公平性。理论分析与实验结果证明对于改进后的算法，当t c p 流与u d p 流共享拥塞链路时，在带宽分配的公平性方面，改进算法较原算法有了很大 的性能提高。 关键字：服务质量；拥塞控制；公平性；用户数据报协议；传 输控制协议 基十o o s 的公1 7 带宽分配策略的队列管理算法研究 a b s t r a c t w i 也t h ed e v e l o p m e n to fi n t e r n e ta n d e m e r g e n c eo fn e wm u l t i m e d i a a p p l i c a t i o n ss u c ha si pt e l e p h o n y v o da n de - c o m m e r c e ，i n t e r a c th a se v o l v e d i n t o 锄i n t e g r a t e dt r a n s p o r tn e t w o r kw i t ht e x t a u d i oa n dv i d e oe r e t h ee x i s t i n g b e s t - e f f o r ts e r v i c ep r o v i d e db yc u r r e n ti n t e r a c tw o u l db en ol o n g e rs u f f i c i e n t q o sc o n t r o lo ft h em u l t i m e d i at r a f f i ca so n eo ft h ek e yt e c h n i q u e si nt h en e x t g e n e r a t i o nn e t w o r ki st h eh o t s p o to f t h ec u r r e n tc o m p u t e r n e t w o r kr e s e a r c h r e c e n t l y , t h ef a i r a l l o c a t i o no fb a n d w i d t hc o m et of r o n td u et ot h ew i d et l s e o fp 2 pa p p l i c a t i o ns u c ha sb t , e d o n k e ya n ds oo n ，t h i sp a p e ri sj u s ta b o u tt h i s i s s u e t oa c h i e v et h i s t h i sp a p e rd oal o to fr e s e a r c ha n da n a l y s i s f i r s t l y , t h i sp a p e rd o e sd e e p l yr e s e a r c ha b o u ts o m ef a i rq u e u i n ga l g o r i t h m s a n a l y s i st h ec o n t r i b u t i o no f t h e s ea l g o r i t h m sf o rt h ef a i ra l l o c a t i o no fb a n d w i d t h i nt o t a lt h ef a u l t sa n dt h ea d v a n t a g e so ft h e s ea l g o r i t h m s 驯sp a p e ri sf o c u so nc s f q ( c o r es t a t e l e s sf a i rq u e u e ) ，c s f qc a n a c h i e v e a sw e l lf a i r n e s si nb a n d w i d t ha l l o c a t i o na st h a t i m p l e m e n t e db ys t a t e n e t w o r k s b u tt h e r ea r es t i l ls e v e r a lp o s s i b i l i t i e sf o ri m p r o v i n gc s f q i t s d r o p p i n ga l g o r i t h mi sd e r i v e df r o mn o n r e s p o n s i v ef l o w ss u c ha su d pf l o w s ，a n d d o e sn o ts u i tt c pf l o w s l a s t l y , a ni m p r o v e dc s f qa l g o r i t h mw a sp r o p o s e di nc o n s i d e r a t i o no ft h e c h a r a c t e r so ft c et h e r eam a i ni m p r o v e m e n t si nt h ea l g o r i t h m ad r o p p i n g p o l i c yd i f f e r e n tf r o mt h a to fu d pi se m p l o y e dt ot c eh e n c e ，t h ef a i r n e s so f b a n d w i d t ha l l o c a t i o nb e t w e e nt c pa n du d pi sw e l la c h i e v e d 1 1 垃e x p e r i m e n t s r e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mo u t p 硼o i t l l 8t h ec o n v e n t i o n a lc s f q a l g o r i t h mb yas i g n i f i c a n tm a r g i ni nb a n d w i d t ha l l o c a t i o nf a i r n e s sw h e nt c p f l o w ss h a r et h ec o n g e s t i o nl i n kw i t hu d pf l o w s k e y w o r d s ：q o s ；c o n g e s t i o nc o n t r o l ；t r a n s f e rc o n t r o lp r o t o c o l ( t c p ) ； u s e rd a t a g r a mp r o t o c o l ( u d p ) ；f a i r n e s s 基于q o s 的公r 带宽分配策略的队列管理算法研究 1 1 研究背景及意义 第一章绪论 随着i n t e m e t 网络规模、用户数量的迅猛发展，i n t e m e t 上的业务种类也 与日俱增，诸如i p t e l e p h o n y 、视频会议、远程教学等多媒体应用层出不穷， i n t e m e t 己经逐步由单一的数据传输网向数据、语音、图像等多媒体信息的 综合传输网演化。 i n t e m e t 中现有的传输模式仍为单一的尽力而为( b e s t e f f o r t ) 服务，在这 种服务模型下，所有的业务流将被一视同仁的公平竞争网络资源，路由器对 所有的数据包都采用先来先处理的工作方式，尽最大努力将数据包传输到目 的地，但对数据包的可靠性，延迟等不能提供任何保证。这些方式适合f t p 、 w w w 、e m a i l 等业务。但对那些对带宽、延迟、延迟抖动等有特殊要求的 应用来说现有的尽力而为服务显然是不够的。尽管由于网络技术的发展，网 络带宽和网络速度都得到了极大的提高，但网络上的数据传输量也以相同的 速度增长，甚至超过了网络发展的速度。因此以提高网络资源利用率，为用 户提供更高的服务质量( q o s ，q u a l i t y o fs e r v i c e ) 成为目标的研究领域 成为目前的研究热点问题，也是当静学术界计算机网络通信领域研究的热点 问题。 公平性不仅是q o s 的重要衡量指标之一，它与网络运营商及网络用户也 有着密不可分的联系，对于网络运营商来说，公平性的提高有利于其对网络 资源实行更有效的控制，提供资源利用率，获得更大收益；对于用户来讲， 公平性的提高有利于其获得与其订约带宽相符合的服务质量。带宽的公平分 配问题正是本文的主要研究内容。 为有效实现带宽的公平分配问题，本文主要工作在于公平排队算法的研 究。 基于o o s 的公卜带宽分配策略的队列管理算法研究 1 2 i n t e m e t 的q o s 问题 q o s 保证的实现主要由网络的i s p 来完成。从i s p 的角度来看，q o s t 3 1 是用一组定量、可测量的参数来描述的。这些参数是： 1 、延迟和延迟抖动：延迟是数据包从发送到抵达目的所经历的时阃，是 描述服务质量的一个重要特性。延迟抖动是延迟的变化，即相同源目之间多 个数据包所经历延迟的差异。许多交互式的应用对延迟和延迟抖动都很敏 感，比如语音业务和视频业务；而一些非交互式的应用只对延迟抖动敏感。 延迟包括把分组送到链路的传送延迟( t r a n s m i s s i o nd e l a y ) 、分组流过链路的 传播延迟( p r o p a g a t i o n d e l a y ) 、路由器响应请求的处理延迟( p r o c e s s i n g d e l a y ) 以及分组在队列中等待的排队延迟( q u e u e d e l a y ) 。这些延迟中，只有排队延 迟是可以控制的，而其它延迟是由网络的物理特性决定的。 2 、吞吐量：服务提供者在单位时间内传输的最大字节数。与吞吐量有关 的利用率为数据在网络上发送的速率嘲，一般表示为每秒多少位( b p s ) ，每秒 多少字节( b p s ) 或每秒多少包数( p p s ) 。可以用吞吐量表示网络上总的数据传 输速率，也可用吞吐量表示网络上某一类型的数据包的传输速率。 3 、丢包率：数据包在i n t e m e t 上传输的过程中会进入路由器的队列等待 转发，如果路由器的队列满，路由器会丢弃一部分数据包，这就是一种包丢 失。丢包率等于某一时间间隔内丢失包的字节数除以某一时间间隔内传输的 字节数。 而下面我们讨论的带宽分配的公平性问题中，将会对如何减少丢包数进 行更加深入地研究。 1 3 带宽分配的公平性问题 目前互联网上的通信量主要是由传统的数据传送应用如h t i p ，s m t p ， f t p 产生。这些应用通常对单个数据包的传递时间不敏感而只关心整体数据 的传送时间。它们通常都采用能够提供可靠的端到端服务的t c p 协议，而 t c p t 3 1 协议的一项关键技术就是捌塞控制。由于每个连接的吞吐量很大程度 2 基于q o s 的公f 带_ 宽分配策略的队列管理算j 幺研究 上取决于它获得的瓶颈带宽，因此，保障连接在瓶颈处获取公平的资源分配 对于t c p 的拥塞控制来说非常必要。然而，在广泛使用t c p 协议的互联网 环境下，连接的吞吐率非常依赖于往返时间( r t t ) ，这非常不利于瓶颈连接 处的带宽公平共享。 为了解决这一问题，理想的拥塞控制机制应该能够根据共享瓶颈连接的 数据流数目来分配带宽。但是由于t c p 协议端到端控制的本质特点，它很难 得到详细的网络信息，如连接的数量、瓶颈带宽、以及共享瓶颈连接的数据 流的r t t ，因而无法依此来控制传送速率。单独的1 p 端到端的拥塞控制 机制无法防止由于非响应( n o n r e s p o n s i v e ) 流的迅猛增加带来的拥塞崩溃以 及不公平的带宽分配。随着视频、音频等多媒体应用的日益流行，这些非响 应流在网络上的比重也不断增加，于是网络层本身必需参与到控制自身资源 的使用中来。为了保障公平性在网络层加强拥塞控制是必不可少的，因此就 成为近年来学者们的一个研究热点。 1 3 1 带宽分配公平性问题产生的原因 公平性是指在网络发生拥塞时各连接能公平地共享网络资源。产生公平 性问题的根本原因在于拥塞的发生必然导致数据包丢失，而数据包丢失会导 致各数据流之间为争抢有限的网络资源发生竞争，竞争能力强的数据流将得 到更多的网络资源，从而损害了其它流的利益。所以说没有拥塞，也就没有 公平性问题。公平性问题表现在两方面：一是拥塞响应的t c p 流和非拥塞响 应的u d p 流之间资源享用的不公平：二是t c p 流之间资源享用的不公平性。 前者主要是由于发生拥塞时，不同的数据流对拥塞指示做出的不同反应造成 的。由于t c p 流具有拥塞控制机制，因此在收到拥塞指示后，发送源端会主 动降低数据发送速率。结果在网络拥塞时，拥塞响应的t c p 流得到的资源越 来越少，非拥塞响应的u d p 流得到的资源越来越多，从而导致了网络资源 分配的不公平。 网络资源分配的不公平反过来会加重拥塞情况，甚至可能导致拥塞崩 溃。对于上述的第二个不公平问题，研究表明：不同的窗口大小，r t t 值及 基于q o s 的公r 带宽分配镱略的队列管理算法研究 数据包的尺寸都会影响t c p 流对带宽的占用。窗口较大，或者r t t 较小， 或者数据包较大的业务流往往能占用更多的带宽。 1 3 2 公平带宽分配的目标及目前实现方法 目前互联网上的主要通信量都是由传送“弹性”文档( 如文件，页面等) 产生的。对于这些应用，用户能感觉到的性能主要依赖于数据流带宽分配的 方式。带宽分配的主要目标就是尽力充分利用可用带宽的同时，对于各数据 流分配的带宽维持一定的公平性。在网络中最普通的理解就是最大最小公平 性( m a x m i nf a i r n e s s ) ，就像文献”1 定义的那样：在链路容量的约束条件下， 使得速率尽可能的相等。尽管最大最小公平性是很常用的目标，但是普遍认 为大多数网络数据流控制协议都没有完美实现。1 。特别是，研究发现加法增 加乘法减小( a i m d ) 的拥塞控制准则更趋同于实现成比例而不是最大最小公 平性。 最大最小公平性：这是数据网络领域中的经典共享原则就像b e r t s e k a 论 述的那样，其简单目标就是在满足带宽约束条件下最大化集合其中的最 小元素。 7 成比例的公平性：最大最小带宽公平性作为带宽共享目标的适宜性受到 k e l l y 的质疑，他提出了一个替代概念，即成比例公平性。在满足约束 条件下最大化的速率分配就是成比例公平的。这个目标可以被看作是假 设每个路径有一个对数效用函数( 1 0 9 a r i t h m i cu t i l i t yf u n c t i o n ) ，则 将实现最大化速率分配的总体效用。 潜在的延时最小化( p o t e n t i a ld e l a ym i n i m i z a t i o n ) ：考虑到数据流是为传输 文件而存在的，一个合理的带宽共享目标就应该最小化的完成这些传输 所需要的时间延时。 加权共享：对以上三个标准都可以引入和每个路由关联的权重因子w r ， 权重的增加意味着分配的份额增加。文献“”描述了一种加权版本的成比 例标准。 为了取得以上的标准规定的带宽公平性，目前主要有两大类自适应带宽 4 基于q o s 的公平带宽分配策略的队州管理算法研究 分配方法，遵循a t m 的术语，我们称之为明确速率( e x p l i e i t - r a l e ) 算法和拥塞 指示( c o n g e s t i o n i n d i c a t i o n ) 算法。还有一类相对简单的替代方法就是对每 个路由采用固定的端到端窗口，分析这种方法可以解释队列服务规则对带宽 公平分配的冲击。明确速率算法的具体阐述由于篇幅原因将不再进行详细阐 述，可见文献“”，它在经过有限次迭代以后，收敛到一个准确的最大最小速 率分配上。鉴于明确速率法的复杂性。目前大多数网络的数据流控制协议都 是基于网络链路独立激发的二进制拥塞示。a t m 界普遍认为拥塞指示法由 于所谓的“击倒”( b e a t - d o w n ) 效应而没有明确速率法取得公平性好。 然而k e l l y 的研究发现“，b e a t - d o w n 效应以另一种简单的方式说明拥塞指 示法实现了成比例公平性而不是最大最小公平性。固定的端到端窗口控制相 对简单一些。但是只有在链路的缓存足够大以至于消除丢包可能性的情况 下，才能作为一种可行的带宽共享选择方案，具体论述见文献“”。 在路由器上进行带宽公平分配能保护响应流而不受到非响应流的影响， 并且可以简化或者增强端到端的拥塞控制。目前研究人员已经提出了许多路 由器机制来取得带宽公平分配。这些方法大致可以被分为两类：基于每个流 的数据包调度机制，如加权公平队列机制w f q ( w e i g h t e df a i rq u e u i n g ) “ 以及它的许多变体“”；基于每个流的数据包丢弃机制，如f r e d ( f l o w r a n d o me a r l yd r o p ) 。基于每个流的数据包丢弃方案也是主动队列管理机制 o ，它通过将那些获得大于公平分配带宽的数据流中丢弃数据包来达到和公 平队列相似的效果。这两种方案都需要保存每个流的状态，比起简单的f i f o 队列机制显得复杂并且可扩展性不好，因此不适合高速骨干网的路由器。为 了克服这些缺点，近年来学者们已经提出了许多框架和机制来简化实施的复 杂性并强调良好的可扩展性。 为了解决上述问题，国内外学者都做了大量研究，目前已经出现了许多 的改进算法 2 $ 1 1 2 9 1 1 3 0 。最具有代表性的就是s t o i c a 提出的核心无状态公平队列 算法c s f q j o l 3 2 1 ( c o r e s t a t e l e s sf a i rq u e u i n g ) 。c s f q 可以取得近似理想的公 平性而不需要在核心路由器保持每个流的状态。为了避免在所有路由器上维 持每个流的状态，它采用了一种只需要边界路由器维持每个流的状态而不需 要核心路由器维持的分布式算法。边界路由器估计每个流进入网络的速率并 摹- f q o s 的公卜带宽分配策略的队列管理算法研究 且将这个信息添加到每个包的包头标签中，核心路由器根据这些信息来决定 是否丢弃一个数据包。因此，和w f q 比起来，c s f q 的核心路由器非常简 单并且便于实施。然而，边界路由器的体系结构已然复杂，尽管可以很容易 地扩展c s f q 以支持具有不同权重的流，这个算法却不能支持流在不同的路 由器具有不同权重的情况。在本文的第四章中，我们将对这个算法进行详细 的介绍与分析。 1 4 本文的组织结构 本文的主要研究工作是针对现存的网络服务质量存在的问题而展开的， 具体的说主要是针对主动队列管理算法和存在的带宽分配的公平性问题而 展开的。 第一章介绍了本文相关的研究背景，阐述了本文的研究目的，接下来介 绍了q o s 的定义以及q o s 存在的阀题。分析了目前产生带宽分配不公平的 原因，并简单介绍了目前在路由器上的解决方法。 第二章主要介绍了后续研究工作中涉及到的一些基本理论和技术。由于 本文的工作是基于对网络服务质量的研究，首先研究了综合服务模型的结 构，需要进一步研究的问题以及综合服务模型的缺陷。详细介绍了区分服务 模型以及相关的理论。深入研究了造成带宽分配不公平的根本原因，即拥塞 问题，以及如何避免拥塞问题。 第三章对近似公平带宽分配的队列管理算法进行了深入的研究。首先解 释了公平带宽分配的重要意义，然后详细的分析了现有的主动队列管理算 法，如：w f q 、r e d 、f r e d 、d r r 算法。重点研究了随机早期检测r e d 算法，对其优缺点有了详细的研究并给出了目前已经存在的几种r e d 变体。 最后对这几种算法在其公平性，复杂性，是否需要维护每流状态以及对t c p 流抑制程度等方面进行了定性的比较。 第四章是本文的重点，研究了c s f q 算法在性能上的一些问题，提出了 一种改进算法，对t c p 流使用了与u d p 流不同的丢包策略，彻底解决了t c p 流与u d p 流的带宽分配公平性。最后通过实验比较分析得出t c p 流与u d p 6 基于9 0 s 的公r 齑宽分配策略的队列管理算法研究 流共享拥塞链路时在带宽分配的公平性方面，改进算法较原算法有了很大的 性能提高。 第五章给出了结论和我们需要做的进一步的研究工作。 7 基于o o s 的公卜带宽分配策略的队列管理算法研究 第二章公平带宽分配的相关理论 影响i p 网络q o s 有两个关键因素：网络资源( 如链路带宽、缓冲区) 不 足及网络中流量分布不合理，现有网络协议支持q o s 能力不足。 2 1q o s 服务模型【2 】 2 1 1 综合服务( i m s e r v ) 模型 服务质量控制研究的目标是有效提供端到端的服务质量控制或保证， 近来i e t f 的i n t s e r v 工作组已在此方面做了很多工作。综合服务的原理是对 于每个需要进行q o s 处理的数据流，通过一定的信令机制，在其经由的每一 个路由器上进行资源预留，以实现端到端的q o s 保证。首先，该模型蚴定义 了一个作用于整个网络的要求集合，整个网络中的每个元素( 子网或路由器) 都将能够实现这一要求集合。随后，通过一定的信令机制，将特定应用的服 务等级要求通知其传输路径上所有网络元素，并将应用与各个网络元素之间 进行各种资源预留与处理策略的设霞。这样，在整条路径建立起来之后，这 条路径上的所有网络元素都已经做好了为相应的数据流提供q o s 保证的准 备。 具体而言，综合服务需要所有路由器在控制路径上处理每个流的信令消 息并维护每一个流的路径状态和资源预约状态，在数据路径上执行流的分类， 调度和缓冲区管理。综合服务依靠资源预留协议。逐节点的建立或拆除每个 流的资源预留软状态：依靠接纳控制决定链路或网络节点是否有足够的资源 满足q o s 请求。依靠传输控制将i p 分组分类成传输流，并根据每个流的状 态对分组的传输实施q o s 路由、传输调度等控制。 目前，综合服务模型定义了三种业务类型，并且对这些业务类型对路由 器的要求进行了描述： 保证型服务：在r f c2 2 1 2 5 中，将延迟分为两部分：固定延迟( 触e dd e l a y ) = 蟮于9 0 s 的公r 带宽分配策略的队列管理算法研究 和排队延迟( q u e u ed e l a y ) 。固定延迟，比如传输延迟，是固定的，是路径的 特性，它不是由保证型服务决定的，而是由路径建立机制决定的。只有排队 延迟是由保证型服务决定的，排队延迟是指，报文组成的流在交换设备、路由 器等网络元素的缓冲区中排队等待的时间，它是由缓冲区的长度，即队列长 度和报文处理速度决定的。i e l f 讨论的q o s 控制主要集中在如何处理排队 延迟上。 控制负载型业务( c o n t r o l l e dl o a ds e r v i c e ) ：在r f c 2 2 l 中提到，可控负 载型服务能够在网络元素负载过商的情况下，通过容量控制，提供用户 的服务质量近似接近于网络元素无负载条件下的q o s 。它让用户无论在 网络负载很高还是很低时，感受的服务质量差不多。 尽力而为型业务( b e s te f f o r t ) ：实际就是传统的i n t e m e t 所提供的业务，该 业务不能提供任何q o s 保证。 综合服务通过在所有路由器控制路径上处理每个流的信令消息并维护 每一个流的路径状态和资源预约状态，在数据路径上执行流的分类、调度和 缓冲区管理来提供端到端的q o s 保证。其缺点是可扩展性差，因为资源预留 需要对大量的状态信息进行刷新与存储，复杂了网络核心路由器的功能。因 此当网络规模扩大时，综合服务模型将无法实现。综合服务模型通常应用于 网络规模较小，业务质量要求较高的边缘网络，如企业网、园区网等。 2 1 2i n t s e r v 的特点 目前i n t s e r v l 4 的q o s 问题在很多方面仍然有待于进一步研究，从理论上 讲i n t s e r v 模型完全可以保证为i p 网络提供q o s 保障。但随后的实验表明这 种服务模型有很明显的局限性“，这些问题不仅表现在扩展性差上，更大的 闯题是它要求核心路由器必须保持经过它的每一个单个数据流的状态，而核 心路由器是不能这么做的。另一个大问题是尽管主要的路由器生产商和主机 都支持r s v p ，它也被广泛接受，但是它始终没有成为主流，原因是i s p 们不 愿意采用它，很少有大型网络采用它。 ( 1 ) 可扩展性差：可扩展性是i n t s e r v 模型最致命的一个问题，其基于流的 9 摹于q o s 的公卜衍宽分配策略的队列管理算法研究 资源预留、调度处理以及缓冲区管理，有利于提供q o s 保证，但状态信息随 业务流数量的增长而增长，沿途的路由器要为每个数据流都维持一个“软状 态”，而路由器的存储器容量有限，可以保存的软状态信息都是有限的，在 一个运营商规模的网络中几乎不可能实现这一要求。 ( 2 ) 对路由器的要求过高，网络中所有的路由器都必须支持r s v p 信令协 议，接入控制程序，分类器以及调度器。 ( 3 ) r s v p 中引入每流状态( p e r - f l o ws t a t e ) 的概念，对于数据通信和实时应 用通信而言，m 网络同时扮演了面向无连接和面向连接网络的两个不同角 色，提供两种功能，这与其简化设计原则相抵触。 ( 4 ) 资源预留不适用于短时流，比如w e b 流等，而在因特网中w 曲流量超 过了5 0 5 。 ( 5 ) i n t s e r v r s v p 还存在着资源预留和路由协议之间的矛盾。从路由角度 来看它是一条好的路径。但从资源预留来看，由于没有足够的资源可以预留， 不能为数据流建立起一条路径，因此这一进程只能停留在这里，等待上层超 时拆除这个应用进程，再重新建立路径。 由于i n t s e r v 体系存在着诸多问题，一种新的体系结构便应运而生，这 就是区分服务体系结构( d i f t s e r v ，d i f f e r e n t i a t e ds e r v i c e s ) 。 2 1 3 区分服务( d i f l s e r v ) 模型 区分服务网络具有良好的可扩展性，这在很大程度上源于其“边界复杂， 核心简单”的设计思想。其最大的特点是区分了网络中节点的行为，使得网 络的内部节点不需要维护单个数据流的信息。这与综合业务模型有着很大的 不同，综合业务网络中的每个节点有着一致的行为，共同保证单个数据流的 服务质量。由于区分服务网络的边界节点将众多的数据流硖射到一个服务类 型，内部节点根据该服务类型为这些数据流统一提供质量保证，使得d i f f s e r v 网络不能提供细粒度的服务保证。 进一步地，目前d i f t s e r v 网络没有一个有效的全网范围内的资源管理机 制。而这个机制对于网络的服务提供是十分重要的。边界节点处理客户的服 1 0 基十q o s 的公f 带宽分配簧略的队列管理算法研究 务请求进行接纳控制时必须通过某种方式来判断当前网络是否有足够的能 力满足该请求。如果没有一个有效的资源管理机制，d i f f s e r v 网络就无法向 客户提供与其承诺一致的q o s 保证。区分服务模型使用数据流分类聚集的方 法来实现对q o s 的支持，从而克服了这些缺陷。其核心思想是上面我们所提 过的“边界复杂，内部简单”：将网络中的路由节点区分为边界节点和内部 节点，边界节点不仅要执行内部节点的逐跳转发行为( p h b ，p e rh o p b e h a v i o r ) ，还要执行其他更复杂的操作，如数据包分类、接纳控制等。关键 的地方在于：边界节点根据应用程序与网络的s l a 协商将众多的数据流聚集 到一个类( 通过标记i p 首部的d s c p 字节为同一个值) 中；内部节点不需要 维护特定流的相关信息，而保留特定类相关的信息，并且根据数据包中的 d s c p 字节来选择与特定类相关的p h b 。 1 ) d i f f s e r v 的q o s 框架结构 d i f f s e r v 的q o s 实施与网络层协议字段有关，i p v 4 协议分组头的t o s 字段和新的i p v 6 分组协议头中的一个称为业务流类别的协议字段被用于区 分服务模型框架中，这种字段在q o s 中称为区分服务码点( d s c p ) 或称为 区分服务域( d s ) 。在d i f f s e r v 的框架下，客户首先要将分组的区分服务码 点标记为特定值，然后将服务请求提交给服务提供商，后者可以根据客户提 交的服务码的值来区分每一种服务，然后相应地提供对应的网络服务。通常， 服务提供商和客户可以共同协商一个配置文件( p r o f i l e ) ，由它描述各种服务 等级通信的提交速率。如果提交的分组速率超过了配置文件中的定义范围， 则可能无法获得规定的服务等级。在d i f f s e r v 中有一个很重要的概念：每 一跳行为( p e r - h o pb e h a v i o r ，p h b ) 。p h b 是通过d s c p 来描述的，客户 和服务提供商通过协商d s c p 来预先定义p h b ，之后网络上数据的传输和 路由器转发分组的行为则由p h b 来控制。在实施核心网络的q o s 行为上， i e t f 的标准化小组主要集中于特定的每一跳排队和调度行为，这是因为当 前形式下，网络传输模型过于复杂，要完全规范d i f t s e r v 的各种指标现在 还不切合实际。目前，只有两个p h b 加速转发( e x p e d i t e df o r w a r d i n g ， e f ) 和确保转发( a s s u r e df o r w a r d i n g ，a f ) 得到认可且归入标准的范畴1 2 2 1 1 2 a 1 。 2 ) e f p h b 却a f p h b 基于q o s 的公，卜带宽分配策略的队列管理算法研究 加速转发可以用来实现d i f f s e r v 域中的低丢失率、低延迟、确定带宽 的服务，比如语音i p ( v o i p ) 和视频会议这样的应用。对于部署了d i i i s e r v 的服务网络中的那些端节点来说，这种服务类似一条点到点的连接，当建立 起发送端和接收端的链路时，采用e fp h b 的网络分组行为使得沿着该通 路上的每个路由器对一个e fp h b 的分组速率至少快于它的到达速率，这 在q o s 中也被叫做奖赏服务。确保转发没有加速转发定义的那么严格，实 际上，a f 是一个根据相对带宽可用性和多种分组丢失特性定义的路由服务 p h b 组成。e f 支持具有“硬”带宽和抖动特性的服务，而a f 则允许更为 灵活的动态共享网络资源，可视其为一种支持突发业务量的“软”带宽和适 当的损失保证。在应用中，服务提供商使用a fp h b 为来自客户d s 域的i p 分组提供不同等级的转发保证，其并没有e f 规定的加速特性，对丢失率、 延迟抖动不做很严格的保证，比较起来，a fp h b 只适合大多数基于t c p 协 议的应用程序。 3 1d i f t s e r v 评估 基于d i i t s e r v 的q o s 模型其完整度相对i n t s e r v 来说不够，但是它能解 决i n t s e r v 相对复杂的端到端特性，该模型主要好处是定义的网络q o s 特 性只需要几个简单的p h b 来表示，对业务流的分类整形控制在边缘路由器 已经被处理，部署了d i f f s e r v 的核心路由器按照d s 域提供p h b ，而对于没 有部署d i f f s e r v 的路由器则可以提供普通的尽力传递服务，因而对网络整 体来说，不至于变化过大，以后进行扩展也相对方便，所以实施起来难度比 i n t s e r v 小很多。但是d i f f s e r v 采用的是聚合类的模型，对每个业务的控制 不那么精确，如果没有明确的预留机制和业务流整形处理，任何时刻，都有 可能造成网络中某一部分比其他部分接受更多的业务量，这样会导致拥塞， 使得某一特定的服务无法正常进行。因此，它只能保证整体上的聚合业务类 的服务质量，维持不同的类别之间的相对服务等级，以达到区分服务的效果。 2 1 4 区分服务的特点 区分服务网络具有良好的可扩展性，其最大的特点是区分了网络中节点 基于q o s 的公平带宽分配策略的队列管理算法研究 的行为，使得网络的内部节点不需要维护单个数据流的信息。这与综合业务 模型有着很大的不同。综合业务网络中的每个节点有着一致的行为，共同保 证单个数据流的服务质量。由于区分服务网络的边界节点将众多的数据流映 射到一个服务类型，内部节点根据该服务类型为这些数据流统一提供质量保 证，使得d i f f s e r v 网络不能提供细粒度的服务保证。进一步地，目前d i f f s e r v 网络没有一个有效的全网范围内的资源管理机制，而这个机制对于网络的服 务提供是十分重要的。边界节点处理客户的服务请求进行接纳控制时必须通 过某种方式来判断当前网络是否由足够的能力满足该请求。如果没有一个有 效的资源管理机制，d i f f s e r v 网络就无法向客户提供与其承诺一致的服务质 量保证。 2 1 5 d i f f s e r v 与i n t s e r v 相结合的端到端q o s 提供机制 单独的i n t s e r v 和d i f f s e r v 都难以满足网络需要，因此就有了将两者结 合起来的端到端q o s 方案1 1 0 1 ，在边界网络提供i n t s e r v 机制，而在核心传输 网采用d i f f s e r v 机制，其关键是实现i n t s e r v 服务( 如确保型) 到d i f f s e r v 服务 ( 如p h b ) 的映射。i n t s e r v 主要通过r s v p 实现动态的资源管理，而d i f f s e r v 的资源管理主要包括两种方案：( 1 ) 基于业务级别规范( s l s ) 的静态资源管理方 案，在边界路由器中根据用华和网络提供商签署的s l s 进行配置，从而可以 d i f f s e r v 完成静态的资源接纳功能，但这种方式很不灵活，无法反映d i f f s e r v 域的资源可利用性。( 2 ) 动态资源管理，包括聚集r s v p 、单流r s v p 和带宽 代理。前两种要求d i f f s e r v 边界路由器机器、核心路由器支持r s v p 信令处 理，增加了d i f f s e r v 域路由器的负担并且不能真证反映全局的资源可利用性， 而带宽代理通过集中管理d i f f s e r v 区域内的网络资源以及网络拓扑，对边界 路由器相邻带宽代理的服务请求进行接纳控制，使得核心路由器的控制平面 与数据平面实现了分离，核心路由器只负责数据转发，而带宽代理完成了接 纳控制、路径选择和资源管理，从而使网络具有较好的扩展性，能够保证端 到端的q o s 。 i n t s e r v 虽然模型比较直观，但是需要骨干路由器维护大量的状态，并 基于q o s 的公3 p 带宽分配策略的队列管理算法研究 且难以适应于复播情况下用户访问链路差异很大的质量保证：而d i f t s e r v 更 多地解决业务级别而不能保证端到端的带宽保证。已经有趋势把r s v p 和 p h b 以及m p l s 技术结合起来使用，如图2 1 所示。 图2 1 r s v p 、p h b 和m p l s 结合使用示意图 目前实现i n t s e r v 和d i f t s e r v 的结合以提供端到端q o s 仍然是一个开放的 研究课题。此方面已经提出若干不同的研究方案和实现机制，典型的有面向 s c o r e ( s e a l a b l ec o r e ) 的动态分组状态( d y n a m i cp a c k e ts t a t e ，d p s ) 方案 2 0 1 ； 基于三种优先级别的带宽确保型服务机制来提供端到端q o s 。文献【l0 】提出了 另外一种在d i t t s e r v 网络云中结合r s v p 协议来提供资源预留和q o s 保证的 框架。 2 2 拥塞控制 拥塞是一种持续过载的网络状念，此时用户对网络资源( 包括链路带宽、 存储空间和处理器能力等) 的需求超过了其固有的容量。就i n t e r a c t 的体系结 构而言，拥塞发生是其固有的属性，因为在事先没有任何协商和请求许可机 制的资源共享网络中，几个i p 分组同时到达路由器，并期望经过同一个输 出端口转发的可能性是存在的，显然不是所有的分组都可以同时接受处理， 必须有一个服务顺序，中问节点上的缓存为等候服务的分组提供一定保护。 然而，如果此状况一直持续，当缓存空间被耗尽时，路由器只有丢弃分组。 表面上，增大缓存总量可以防止由于拥塞引起的分组丢弃，但随着缓存的增 加，端到端的时延也相应增加，因为分组的持续时间( 1 i f e t i m e ) 是有限的，超 时的分组同时需要重传。因此，过大的缓存空间倒有可能妨碍拥塞的恢复， 1 4 基于q o s 的公r 带宽分彭策略的队列管理算法研究 因为重传分组白白浪费了网络的可用带宽1 2 7 1 。 拥塞导致的直接结果是分组丢失率提高，端到端的时延增大，甚至有可 能使整个网络系统发生崩溃。当网络处于拥塞崩溃状态时，微小的负载增量 都将使网络的有效吞吐量( t h r o u g h p u t ) 急剧下降。1 9 8 4 年，n a g l e 报告了由于 t c p 连接中不必要的重传所引发的拥塞崩溃，1 9 8 6 1 9 8 7 年间这种现象曾出 现过多次，严重时一度使l b c 与u cb e r k e l e y 之间的吞吐量曾从3 2 k b p s 下 降到了4 0 b p s 2 s 。除此之外，还有其他一些引发拥塞崩溃的原因，例如，不 可达分组( u n d e l i v e r e dp a c k e t s ) 导致的网络崩溃。f l o y d 也报告了一种形式的拥 塞崩溃现象，即分片拥塞崩溃，网络传输大量的分组分片，但因为无法在接 收端重新组装成为有效的分组而只好将它们丢弃。网络传输大量用户不再需 要陈旧分组( s t a b l e p a c k e t s ) 也会导致另一种形式的崩溃现象。图2 1 显示了负 载与吞吐量之间的关系：当网络负载较小时，吞吐量基本上随着负载的增加而 增长，呈线性关系。到达膝点( k n e e ) 之后，随着负载的增加，吞吐量的增量 逐渐变缓、当负载越过崖点( c l i f f ) 之后，吞吐量却急剧下降。通常将k n e e 点 附近称为拥塞避免区间，k n e e 和c l i f f 之间是拥塞恢复区间，而c l i f f 之外是 拥塞崩溃区间。 图2 2 网络负载与吞吐量的关系 同络负戴 吞吐量 基于q o s 的公平带宽分配策略的队列管理算法研究 为了最大限度地利用资源，网络工作在轻度拥塞状态时应该是较为理想 的，但这也增加了滑向拥塞崩溃的可能性，因此需要一定的拥塞控制机制来 加以约束和限制。 可以从两个方面考虑如何解决拥塞问题：一是增加网络资源；二是降低用 户的需求。降低用户需求主要表现在三个方面：拒绝服务、降低服务质量和调 度。 ( 1 ) 拒绝服务：在拥塞发生时，拒绝接纳新的用户请求。此方法多用于面 向连接网络。 ( 2 ) 降低服务质量：所有用户( 包括新用户) 在拥塞时降低其发送速率。 ( 3 ) 调度：合理安排用户对网络资源的使用，保证总需求永远小于网络可 用资源。 2 2 1 基于端到端的拥塞控制 基于源端的拥塞控制策略中，使用最为广泛的是t c p 协议中的拥塞控制 策略，t c p 协议是目前互联网中使用最为广泛的传输协议，根据m c i 的统 计，互联网上总字节数的9 5 及总数据包数的9 0 使用t c