（计算机应用技术专业论文）网络带宽分配实现机制的公平性研究.pdf

摘要 随着互联网规模的增长，互联网上的应用和用户都在快速的增 长，各种不同的应用和不同的用户共享着网络带宽，这样它们之间的 带宽分配的公平性问题就显得十分的重要了。人们在带宽分配的实现 机制上做了很多的研究，本文就是在前人研究的基础上对带宽分配机 制的公平性进行了进一步的研究。 本文首先对已有的一些主要的主动队列管理算法进行了总结和 分析，研究了主动队列管理算法的公平性问题。在这个基础上，本文 重点研究了一种核心无状态公平队列管理算法( c s f q 算法) 的公平 性，发现它在保证适应性的流与非适应性的流之间的公平性方面存在 缺陷。我们提出了一种改进的核心无状态公平队列管理算法( i c s f q 算法) ，并通过模拟实验验证了其公平性。而后，我们将对公平性的 研究深入到区分服务网络中。区分服务网络中的分组标记算法能在带 宽分配的公平性方面提供保障，我们总结了目前分组标记算法的研究 现状，其中重点分析了一种基于时间滑动窗口的三色分组标记算法以 及它的一个改进版本，在对它们的优缺点进行研究分析的基础上我们 提出了一种更加公平的三色分组标记算法，通过模拟实验可以发现这 种分组标记算法与主动队列管理算法相结合能够较好的实现低预定 率和高预定率情况下的公平带宽分配。 关键字：带宽分配，公平性，主动队列管理，区分服务网络，分组标 记算法 a b s t r a c t w i t ht l l ed e v e l o p m e mo ft 1 1 ei n t e m e t ，m e 印p l i c a t i o na i l dm eu s e ro f i ta r e m c r e a s i n gr a p i d l y b e c a u s ed i f l e r e ma p p l i c a t i o n s 锄du s e r ss h a r e t h en e t 、) l ，o r kb a l l d w i d t h ，n l ef a i m e s so f b 柚d 埘d t i la 1 1 0 c a t i o ni sb e c o m i n g m o r ea n dm o r ei m p o n a m p e 叩l em a k em a n yr e s e a r c h e s o nt l l e m e c h a i l i s mo fb a i l d w i d ma 1 1 0 c a t i o n ，a n dt h i sp 印e rh a sm a d e 如n h e r r e s e a r c ho nm em e c h a n i s mo fb 粕d w i d t ha u o c a t i o nb a s e do nm ee a r l i e r r e s e a i h e s t h i sp 印e ra d d r e s s e st ot h ef a i m e s so fa q m a l g o r i t h m sa r e rt h e s w 吼撕z a t i o n 锄da n a l y s i so fs o m em 勾o ra q ma l g o r i t h m s w b 矗u so n t i l ef a i m e s so f 吐l ec o r e - s t a t e i e s sf a i rq u e u ea l g o r i l l l l w ep r o p o s ea n i m p m v e dc s f qa l g o r i t l l l n 锄dv e r i 匆i t sf a i m e s sb yt i l es i m u l a t i o n w b e x t e n do l l rr e s e a r c ht om ed i f f s e r vn 神w o r l 【s m c et l l ep a c k dm a r k a l g o r i t c a i lg u a r a n t e e t i l e f a i m e s s ，w es t u d yt l ep a c k e tm 酞 a l g o 矾l l n s ，f o c u s i n go n 锄p a c l r e tm a r ka l g o r i t l l i n 一1 s 、v t c ma l g o r i l i i l 锄di t sa d v a l l c e dv e r s i o ni t s w t c ma l g o r i t i l m t h e n 、wp r o p o s eaf a i r e r m a r ka l g o r i t h m f t s w t c ma l g o r i t l l i i l ，a n db yt l l es i m u l a t i o nw ec a nf m d t i l a tm i sp a c k e tm a r ka l g o r i t h mc o m b m i n gw i t l la q m c a i la c h i e v e sf a i r 盯 b a i l d w i d t ha l l o c a t i o ni nh i 曲p r o v i s i o nl e v e la n di i ll o wp r o v i s i o nl e v e l k e yw o r d s ：b a l l d w i d t t la l l o c a t i o i l f a i m e s s ，a c t eq u e u em a n a g e m e n t ， d i 胚e n ，n e t 、o r kp a c 妇m 破a l g o r i t i l l n i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：血近日日期：2 塑年卫月丑日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：- 二嘲 导师签名j 翌型陛日期：皿年卫月丛日 硕十学伊论文第一章绪论 第一章绪论 随着互联网规模的增长，互联网上的应用和用户都在快速的增长，各种不同 的应用和不同的用户共享着网络带宽，这样它们之间的带宽分配的公平性问题就 显得十分的重要了。人们在带宽分配的实现机制上做了很多的研究。其中主动队 列管理机制在实现网络拥塞控制的同时，其对带宽分配的公平性也是值得关注和 研究的一个方面。当i e t f 提出了区分服务体系结构的一系列概念和标准之后，如 何在区分服务网络中为处于各种不同级别的不同的数据流分配分别对应于其级 别的公平合理的带宽，是一个值得研究的问题。 1 1 主动队列管理机制 1 1 1 研究背景 t c p 协议是目前在i n t e m e t 中使用最广泛的传输协议，根据m c i 的统计，总 字节数的9 5 和总报文数的9 0 使用t c p 传输。近年来，t c p 中采用了很多新 的拥塞控制算法，包括慢启动、拥塞避免、快速重传、快速恢复和选择性应答等， 这明显提高了网络传输的性能。t c p 中所提供的基于窗口的端到端拥塞控制算法 已经成为保证h 他m e t 稳定性的重要因素。然而随着i n t e m n 本身的迅速发展， 网络规模越来越大，仅仅依靠源端来实现端到端的拥塞控制是不够的。事实上在 i r n e m e t 这样复杂的异构系统中，不能指望所有的用户在i n t 锄c t 应用中兼容这种 端到端的拥塞控制，所以网关或路由器现在必须参与资源的控制工作。在t c p 的端到端控制系统中，数据发送方和接收方对网络的拥塞程度一无所知，网络传 输中的大部分分组丢失事件是由于路由器节点的缓冲区溢出造成的，因而只有路 由器才对网络的拥塞程度有最直接的了解。而现在的口路由器的主要功能是进 行分组转发，不具备对网络的拥塞进行检测和控制功能。为此，i e t f 提出了在 路由器中提供主动队列管理技术，采用排队算法和分组丢弃策略监控路由器缓冲 区队列，提前检测拥塞的出现并通知数据发送方。这样发送方可以在路由器溢出 之前调整数据的发送速率，避免更严重的拥塞发生，并降低分组丢弃率。 另外，在传统的队列管理算法中，只有当缓冲队列满的时候才对到达的分组 进行丢弃，这就是我们常说的“尾丢弃”和“头丢弃”机制。虽然这些方法在当 前h l 钯m e t 上得到了广泛的使用，但其存在几个重大缺陷： ( 1 ) 死锁( 1 0 c k _ o i i t ) 问题：在某些情况下，“去尾”算法会让某个流或者 少数几个流独占队列空间，阻止其他流的分组进入队列。这种“死锁”现象通常 硕七学伊论文 第一章绪论 是由于同步( s y n c h r o m z a t i o n ) 或其他定时作用的结果。 ( 2 ) 满队列( 如l lq u e l l e s ) 问题：由于“去尾”算法只有在队列满时才会发 出拥塞信号，因此会使得队列在相当长时间内处于充满( 或几乎充满) 的状态。 而队列管理最重要的目标之一就足降低稳定状态下队列的长度，因为端到端的延 迟主要就是由于在队列中排队等待造成的。 ( 3 ) 全局同步( g l o b a ls y n c h r o n i z a t i o n ) 问题：由于i i l t e n l e t 上数据的突发 本质，到达路由器的分组也往往是突发的。如果队列足满的或者几乎是满的，就 会导致在短时间内连续大量地丢弃分组。而t c p 流具有自适应特性，源端发现 分组丢失就急剧地减小发送窗口，分组到达速率就迅速下降，于是网络拥塞得以 解除，但源端得知网络不再拥塞后又开始增加发送速度，最终又造成网络拥塞， 而且这种现象常常会周而复始地进行下去，从而在一段时间内网络处于链路利用 率很低的用状态，降低了整体吞吐量，这就是所谓地“t c p 全局同步”现象。 除了”去尾”机制，另外两种在队列满时进行队列管理的机制是“随机丢弃” ( r a n d o m d m p ) 和“前丢弃”( d r o p 自r o 眦) 机制。当队列满时，前者从队列中随 机找出一个分组丢弃以让新来的分组进入队列；后者从队列头部丢弃分组，以便 让新分组进入队列。这两种方法虽然都解决了“死锁”问题，但仍然没有解决“满 队列”问题。由于这几种方法部是在队列满了被迫丢弃分组，因此称为被动式队 列管理。 而采用主动队列管理机制则能很好地解决上述被动队列管理机制所带来的 一些问题。随着s a l l yf l o y d 等人提出了r e d ( 鼬n d o me a r l yd e t e c t i o n ) 算法之 后，人们开始对主动队列管理算法进行了一系列的研究，并提出了许多r e d 算 法的改进版本比如f r e d 【1 l ( f l o wr e d ) 、s f e d 【2 】( s e l e c t i v ef a i r n e s se a r l v d e t e c t i o n ) 、s r e d 【3 j ( s t a b i l i z e dr e d ) 、a r e d 【4 l ( a d a p t i v er e d ) 等，以及其他 的些主动队列管理算法例如c h o k e 、c s f q 、b l u e ，a v q 等及其变种。 1 1 2 主动队列管理机制的特点 主动队列管理机制是一种基于f i f o 调度策略的队列管理机制，使得路由器 能够控制在什么时候丢多少分组，以支持端到端的拥塞控制。它具有以下优势： ( 1 ) 减少了路由器中丢弃的分组的数量：i n t e m e t 中分组的突发本质是不可 避免的，主动队列管理机制通过保持较小的平均队列长度( a v e m g eq u e l | es i z e ) ， 能提供更大的容量吸收突发分组，从而大大减少了分组丢失数。进一步说，如果 没育a q m ，会有更多的分组被丢弃，这主要是因为以下三个原因：a 由于使用 共享的队列和p q m ，会不可避免地产生全局同步，导致很低的平均带宽利用率， 即吞吐量很低b t c p 从突发分组的丢弃中恢复要比从单个分组丢弃中恢复更复 2 硕十学付论文 第一章绪论 杂：c 如果一个分组在到达目的端之前被丢弃，则其在传输过程中所消耗的资源 都被浪费，降低了网络带宽的利用率。因此，不必要的分组丢弃也就意味着带宽 的浪费。 ( 2 ) 对交互式服务提供了更低的延迟：主动队列管理机制通过保持较小的 平均队列长度，队列管理能够减少分组的排队延迟( q u e u i n gd e l a y ) ，而排队延 迟是造成端到端延迟( e n d t o e n d d e l a y ) 的主要原因。这对交互式应用比如w 曲 浏览、t e l n e t 业务和视频会议等非常重要。 ( 3 ) 避免了。死锁”现象：主动队列管理机制能够通过确保到来的分组几 乎总是有可用的队列空间，从而阻止“死锁”行为的发生。也因为这个原因， 主动队列管理机制能防止路由器对低带宽高突发的流的偏见。 1 1 3 主动队列管理机制公平性的研究 目前评价公平性的标准主要有三种：“最大一最小公平”原则、“公平指数” 原则以及“比例公平”原则。 。最大一最小公平”原则的一个非正式的定义就是：每个用户的吞吐量至少 和其他共享相同瓶颈链路的用户的吞吐量相同。这是一种理想的状态，但是它不 能给出公平的程度。 “公平指数”原则提供了一个计算公式，可以计算公平的程度。它定义为： 坼，= 瓣 一t7x jj 公式( 1 一1 ) 它的计算结果位于0 和1 之间，并且结果不受衡量单位的影响。它的一个性质就 是：如果厅个用户只有七个用户平均共享资源，而另外疗七个用户没有任何资 源的话，那么计算结果就为七佃。 还有一些研究者认为，如果考虑用户的“效用函数”( 毗i l 酊缸l c t i o n ) 的话， 在一些情况下使用“最大一最小公平”原则来评价并不是最理想的。针对对数的 效用函数，人们引入了“比例公平”的概念。它的定义就是：向量x 满足“比例 公平”，如果对于其他任何向量j ，都满足以下公式 。孕od4 j 公式( 1 2 ) 最初s a l l yf l o y d 教授提出r e d 算法时，并没有考虑公平性这个问题。但是， 随着对主动队列管理机制的研究的进一步深入，人们发现公平性是主动队列管理 机制需要解决的一个重要问题。如何使路由器不增加过多的额外负担，又能够提 高公平性，一直是困扰广大研究人员的一个难题。 人们在考虑到各种主动队列管理机制的公平性问题的基础上，提出了一些在 硕士学付论文 第一章绪论 公平性方面有更好表现的主动队列管理算法例如b l u e 算法的一种改进算法 s f b 算法，c h o k e 算法还有c s f q 算法等一系列算法。 s f b 算法在公平性方面育比较严格的保证。虽然它能较好地解决了区分适应 流和非适应流地问题，但过于复杂，会大大增加路由器的额外开销。而我们希望 在公平性方面做出一些研究的前提就是不能使得路由器的额外开销过大，而s f b 的做法显然与我们的初衷相违背了。但是s f b 作为一种在理论上进行研究的对 象来说还是具有其积极的意义的。 另外一种主动队列算法就是c h o k e 算法。虽然从直观上看，c h o k e 具有 一定的合理性，但是这个算法难以进行严格的理论分析，对其效果和性能的评价 更多地依赖于实验验证。虽然对于占用带宽较多的流，其分组被标记的概率要大， 但难以得到一个理论上的界限。因此，它的公平性难以衡量。 与c h o k e 不同，从理论上说，c s f q 较前面的算法更精确，对于分组丢弃 撅率的计算更合理，近似实现了。最大一最小公平”原则。其中所采取的d p s 技术通过让分组携带流状态信息，从而避免了在核心路由器维持每流状态信息， 简化了核心路由器的操作。但是在边缘路由器，还是需要对分组按流分类，估计 每流的到达速率，维持每流的状态信息，因此，边缘路由器的负担还是较重。另 外，分组头部信息的读取和更新操作，一方面与现有路由器普遍具有的功能有所 差距；另一方面，依赖分组头部信息计算丢弃概率( 并且头部信息还需在沿途节 点动态更新) 需要网络中所有的路由器实现严格的协同。一旦网络中其中一个路 由器出现问题( 如对分组头部信息更新出错) ，则可能会影响到网络中所有的路 由器和流。因此，这种方案由于需要网络中的路由器进行较为严格的协同，给网 络的健壮性造成一定的损害。 1 2 区分服务网络体系结构下的分组标记算法 区分服务体系结构1 4 3 】为了以一种可扩展的方式为不同的服务请求柬提供不 同等级的服务而提出来的。在区分服务网络体系结构中，m 流被分类并聚合成 不同的转发类，在边缘节点标记上不同的优先级别，在中心节点通过不同的丢弃 机制对分组进行丢弃。因此，区分服务网络能够提供一定程度的o o s 保证，而 不是现在的b e s k 仃o n 服务。在区分服务网络体系结构中，一个客户同一个服务 提供商签订服务合同，称为s l a 。它规定了服务的参数的最低限度( 通常称为 c i r 或者t a r g e tm t e ) ，即时是在网络拥塞的情况下。为了确保s l a ，在边缘节点 进行标记，然后在核心节点用a q m 进行丢弃。分组标记机制在边缘节点根据流 量值对分组进行监控和标记。如果进入网络的流的流量遵从其约定的值，则属于 该流的分组被标记成高的优先级，否则，超出约定流量值的那部分流量的分组被 4 硕十学位论文 第一章绪论 标记为低的优先级；而在核心节点部署的主动队列管理机制则根据分组被标记的 优先级的高低来处理分组，优先级高的分组可以优先于优先级低的分组转发，而 优先级低的分组则有可能被丢弃。 由于分组在核心节点会得到怎么样的处理与其在边缘节点怎么样被标记有 着直接的关系，所以分组标记算法就显得尤为重要了。目前，根据对流的测量方 法的不同，我们可以将分组标记算法分为两类：( 1 ) 基于令牌桶的分组标记算法； ( 2 ) 基于平均速率测量器的分组标记算法。 1 3 论文的组织 论文全文共分六章： 第一章绪论。这一章主要介绍主动队列算法以及分组标记算法的相关背景及其 概念。阐述了对它们的公平性研究的必要性及其重要意义。 第二章主要对几种主要的主动队列管理算法进行了研究，通过定性的方式和模 拟实验定量的方式对这些主动队列管理算法进行了分析，总结了几类不同的主动 队列管理算法的各自的特点。 第三章主要重点研究了核心无状态队列管理算法即c s f q 算法在公平性方面的 表现，并在此基础上提出了一种改进的核心无状态队列管理算法，通过模拟实验 表明其在其他性能( 例如算法复杂度、带宽利用率等) 不受到影响的情况下，公 平性得到了较大的改进。 第四章主要研究了区分服务体系结构下分组标记算法的历史以及发展现状，重 点分析了基于时间滑动窗口的三色标记算法及其改进版本在公平性方面的表现。 第五章提出了一种更加公平的基于时问滑动窗口的三色标记算法。首先对其实 现机制进行详细的介绍，然后通过在n s 一2 上的模拟实验分析其公平性，并与 之前的基于时间滑动窗口的三色标记算法进行比较，分析其优劣之处。 第六章结束语。对所做的研究与设计工作进行了总结，并阐述了将来进一步的 工作计划。 硕十学何论文 第二章主动队列管理算法研究 第二章主动队列管理算法研究 在对主动队列管理算法进行研究之前，我们先将主动队列算法进行了分类。 与之前一些主动队列管理算法的分类方式不同，我们按照主动队列算法的基本思 想的不同，将目f i 的主要的主动队列管理算法分为四类： ( 1 ) 基于l 迮d 基本思想的主动队列算法； ( 2 ) 基于b l u e 基本思想的主动队列算法； ( 3 ) 基于c h o k e 基本思想的主动队列算法； ( 4 ) 基于c s f q 基本思想的主动队列算法。 2 1 各种算法的基本思想描述 2 1 1 基于r 印基本思想的主动队列算法 r e d i ，j ( r a n d o me a d yd e t e c t i o n ) 的基本思想就是在拥塞发生的早期，通过 对到达分组按某个概率进行丢弃，以避免拥塞的发生。其关键就是如何检测拥塞， 以及如何计算分组的丢弃概率。在r e d 中，引入了两个重要的参数聊加曲和m 饿肪 分别表示队列门限值的最大值与最小值，用于检测拥塞。若当前平均队列长度小 于小舰h ，则到达的分组以概率o 被丢弃；若当前平均队列长度口唱介于肌加腩和 眦d 之b j ，则到达的分组以概率m 被丢弃，若当前的平均队列长度大于小咖， 则到达的分组以概率l 被丢弃。丢弃概率m 的计算也主要依赖于当前平均队列 长度，而与每流( p e r n o w ) 信息无关。即在某一段时间内，所有到达分组的丢 弃概率胁是基本相等的，而不管它们所属的流占用带宽的多少。 后来人们在r e d 的基础之上对r e d 进行了局部的改良，衍生出一些r e d 的改进算法，这样的算法中具有代表性的有f r e d 【u ( f l o wr e d ) 、s f e d 【2 1 ( s e l e c t i v ef a i m e s se a r l yd e t e c t i o n ) 、s r e d 嘲( s 协b i l i z e dr e d ) 、a r e d 州( a d a p t i v e r e d ) 。这样的算法具有一个共同的特点，即他们对当前网络是否拥塞是基于对 缓冲队列长度( 平均长度或者瞬时长度) 是否超过某一个门限值而做出判断的， 并且在此基础之上决定丢弃概率。 2 1 2 基于b l u e 基本思想的主动队列算法 b l u e 删与r e d 以及f r e d 的一个很大的区别在于它用分组的丢失率以及链 路带宽利用率来衡量链路的状况而不是用队列长度。在b l u e 中有三个重要的参 数：，k ，奶和以；其中p 埘足分组被打上e c n 标记的概率或者丢弃的概率，西是当 6 硕士学伊论文 第一二章主动队列管理算法研究 发现有分组丢失的时候p 肼应该上升的数量，而西是当发现链路空闲的时候厶应该 下降的数量。它的主要思想就是：每过一定的时间间隔，对链路的状态进行观测： 当链路空闲的时候：，= ，_ 击，当发现有分组丢失的时候：厶= p 棚+ 西。每个 分组到达时，都以概率厶打入e c n 标记或者丢弃。 b l u e 克服了r e d 以及f r e d 算法用队列长度判断网络拥塞的程度这一做法 所带来的缺陷，它主要通过链路的带宽利用率以及是否有分组丢失来判断拥塞的 程度，从而进一步决定厶的取值，有其合理性。但是它在公平性方面却没有做太 多考虑，对于所有的流的分组都按照同一概率进行丢弃，使得它的公平性不是很 好。 当前基于b l u e 的后继研究中有s f b 【1 ( s t o c h a s t i cf a i rb l u e ) 。它主要是针 对b l u e 在公平性方面的不足而提出的，保护了像t c p 流这样的响应性的流的正 常占用带宽不被非响应性的流占用。 2 1 3 基于c h o k e 基本思想的主动队列算法 c h o k e 【8 】中也用了两个参数检测拥塞：肌伽睹和眦d 铂。它的基本思想是当一 个分组到达路由器时，测量队列的平均长度口v g ，若嘴嘲加曲则接纳分组；若 仉苫 埘锻f j l 则以丢弃该分组；若此时册加t i l c 时认为链路拥塞，当4 c 即链路 阻塞的情况下，我们分下面几种情况更新n ： ( 1 ) 当前的队列长度大于门限值( g 跏c n 兰q s 切刀胖妇) ，且队列长度是 增加了的时候( g s z z p c 打 q 弛肌v ) ，我们降低a ( 口= c 组) ； ( 2 ) 当前的队列长度大于门限值，且队列长度是减少了的时候( 祁加c 打 口熨z p p m ，) ，维持d 不变； ( 3 ) 当前的队列长度小于这个值( 吁跏c 打 q s 切7 研啪) ，且队列长度是 减少了的时候( q 韶c h 口鼢尸_ r 卵) ，也维持n 不变。 算法伪码图如图3 3 。 硕十学位论文第= 章一种改进的核心无状态队列管理算法 e s l i m a t c 对口进行估计 ，j o 是用于记录在时间窗口疋内拗“的最大值 计算入口链路聚合到达速率彳和入口链路聚合接纳速率f - i f 口兰o ， 目前链路拥塞 i f ( 馏 耐= = 尉岱日 ，之前网络并没有拥塞 将计时器置零，并且改变拥塞标志位，口保持不变； ) e l s e 硅研j i m e s t t j 抽l e + k a m ! t l j n l ： e l s e， 以下为对原算法重点改动部分 i f ( q s 担p c 芝庐船胁 ) ，用a c ，a 减小n 珏沁s i z e c n q s i z e p r e nt a = 口c 啊： s 删j i m e2c n j i m e ： e l f o l 珊叶髓晰p = c r f 酊m p j ，保持n 不变 r e n m ： e k e ，当前队列长度小于门限值 硅沁s i z e c r t q s i z e p th 甩n c 惩增大n n = 口o 霞 s t 硎i m e2c n j i m e ： ) e l ，保持。不变 s t 帆j i m e2c r l j i m e ： 埋【t i l m ： ，改动到此结束 e l s c ， 目前链路没有产生拥塞 i f ( k 时闻内网络一直不拥塞)a = m “伽6 吐j o ； e i s e 将计时器置零；并且改变捆塞标怎位；口保持不变； r 咖m a ： 图3 - 3i c s f q 算法中e s t i m a i 伪码图 前面提到了，i c s f o 的主要思想就是当拥塞发生的时候，在带宽利用率保持 比较高的情况之下，尽可能的降低d 。而在我们的算法中衡量带宽利用率是看缓 冲队列的长度，以往的研究表明，当网络发生拥塞的时候，如果缓冲队列的长度 能够在一段时间内持续保持在一定范围内波动的话，那么这段时间内带宽的利用 率是比较高的。那么根据我们算法的主要思想，我们只要在链路拥塞的时候，当 队列长度大于门限值且还在继续增加的时候降低a ；而在队列长度小于门限值且 还在继续减小的时候增加n 就可以了。 1 6 硕十学竹论文 第= 章一种改进的核心无状态队列管理算法 3 3 模拟实验 在这一节，我们将在公平性方面对c s f q 算法和我们提出的i c s f q 算法进 行比较。我们将这两种算法布署在模拟的网络上面，然后通过观察超速的流的实 际占用的带宽来对两种算法的公平性进行评价。 前面说了，我们在对公平性进行评价的时候，主要是通过观察超速的非适应 性流( 比如说c b r 流) 的实际占用的带宽来进行判断的。这是因为适应性的流 ( 比如说t c p 流) 能够根据网络的状况来自动调节流本身的发送速率，而非适 应性的流则不具备这样的速率调节能力。这样，如果网络本身没有很好地对公平 性进行保证的话，那么非适应性的流就有可能通过某种方法侵占适应性流所应当 占用的理想带宽。那么如果能使这些非适应性的流的实际占用带宽越理想的话， 我们就可以认为这个网络所具备的公平性就越好。 除非有特别的声名，否则在模拟中所用到的参数都按照下面的规定来设置： 每个数据源点和数据目标节点到网络边缘节点的带宽均为l o m ( 为了保证其始 终大于流的发送速率r 1 ) ，延时均为l m s ；其余网络节点日j 链路带宽均为1 m ，延 时为l m s ，同时缓冲队列最大长度为6 4 k b ，c s f q 和i c s f q 中队列长度门限值 均为其一半即3 2 k b 。在用指数平滑法中测量流的速率的时间日j 隔常数k = l o o m s ，而在估计a 时的时间问隔也为l o o m s 。 3 3 1 单瓶颈链路 如图3 4 ，q 1 为所要观察的瓶颈链路。图中有l o 个数据源点s e i l d e 巧( 编号 从o 到9 ) 分别向对应的目的结点蒯v e r s ( 编号o 到9 ) 发送分组。 图3 4 单瓶颈链路网络拓扑 在我们的第一个实验中，1 0 数据源点( 编号0 到9 ) 全部发送c b r 流。其 中9 个c b r 流( 流d 号从o 到8 ) 发送速率恒定为o 1 m ，另外一个c b r 流( 流 d 号为9 ) 为超速c b r 流，发送速率从o 1 m 增加到l o m 。 在我们第二个实验中，1 0 个数据源点中9 个( 编号0 到8 ) 发送t c p 流( 流 i d 号从o 到9 ) ，另外一个数据源点( 编号9 ) 发送c b r 流。在我们的模拟实验 中，c b r 流的发送速率从o 1 m 增加到l o m 。 1 7 硕十学位论文 第二章一种改进的核心无状态队列管理算法 u z 2，o 墩c 嗍舸拍嚣毫搴越c 哺畔燃擎 ( a ) 1 0 个流全为c 腿流( b ) 一个超速c 腓流与9 个t c p 流 图3 5 单瓶颈链路下c s f q 算法与i c s f q 算法公平性比较 图3 5 ( a ) 为单瓶颈链路情况下所有流均为c b r 流时超速c b r 流的实际占用 带宽；图3 5 ( b ) 为单瓶颈链路情况下c b r 流与t c p 流并存时超速c b r 流的实 际占用带宽。 通过观察图3 5 ，我们发现： ( 1 ) 当链路中只存在c b r 流的时候，即使有超速流存在，瓶颈链路上的公 平性依然保持的比较好，理想的共享带宽为o 1 m b p s ，而c s f q 算法和我们提出 的i c s f q 算法均能使得超速流的占用带宽保持在o 1 m b p s 附近； ( 2 ) 当网络中有t c p 流和超速c b r 流共存的时候，t c p 流应当享有的理 想带宽会被c b r 流“侵占”；此时c s f q 实际的公平性并不是很好。瓶颈链路总 的带宽是l m ，总共有1 0 个数据流，这样当链路拥塞的时候，每个流的公平占 用带宽应当在0 1 m 左右，而我们注意到，当超速c b r 流的发送速率增加到l m 之后，其实际占用的带宽基本上维持在o 3 5 到o 4 5 之间，大大超出了其所应该 享有的带宽资源；而在我们所提出的i c s f q 算法中，当超速c b r 流的发送速率 增加到l m 之后，其实际占用的带宽基本上维持在o 2 5 左右。与原有的c s f q 算法相比有了比较大的改善。 3 3 2 多瓶颈链路 如图3 6 ，q 2 和q 4 是我们要观察的瓶颈链路。图中s e n d e r s l 、s e n d e r s 2 、 s e n d e r s 3 分别代表三个不同的数据源点集合，其中s e n d e r s l 中有l o 个数据源点 ( 编号从o 到9 ) ，而s e n d e r s 2 和s e n d e r s 3 中则均有5 个数据源点( 编号分别从 1 0 到1 4 和1 5 到1 9 ) ；r e c e i v e r s l 、r e c e i v e 硌2 、r e c e i v e r s 3 则分别代表三个不同 的数据目标节点集合，其中r e c e i v e r s l 中有1 0 个节点( 编号从2 0 到2 9 ) 接收 从s e n d e r s l 集合中数据源点发送过来的分组，而r e c e i v c r s 2 和r c c e i v e r s 3 中分别 瑚 哺 伸 缁 惜 咖 啡 啪 _蠢鼙地蓝体嚣埘露田釜 旧 懈 蟮 蛐 哺 蛐 哪 埘霹衄蕾h-霞釜 硕士学付论文 第二章一种改进的核心无状态队列管理锋法 k e c a v d zk c c 廿v a s j 图3 6 多瓶颈链路网络拓扑 有5 个节点( 编号从3 0 到3 4 和从3 5 到3 9 ) 分别接受从s e n d e r s 2 和s e n d e r s 3 集合中数据源点发送过来的分组。其中从s e i l d e r s l 到黜i v e 巧l 的l o 个流中， 有9 个t c p 流和1 个c b r 流( 流i d 为9 ) ，这个c b r 流发送速率从0 1 m 增加 到1 0 m ；而从s e i l d e r s 2 到r e c e i v c r s 2 、s e n d e r s 3 到e i v e 体3 的各5 个流中，均 分别有4 个t c p 流和1 个c b r 流，这2 个c b r 流发送速率从0 1 m 增加到1 0 m ( 流分别为1 4 和1 9 ) 。 图3 7 ( a ) 为f l o w i d = 9 的c b r 流在q 2 上的实际占用带宽图，图3 7 ( ” ( a ) f i d ；9 的c 腿流在q 2 上所占带宽 2 ，o 髓c 日f 濉的赞羞述事 ( b ) f i d 一9 的c 肌流在q 4 上所占带宽 ( c ) f i d - 1 4 的c b r 流在0 2 上所占带宽 ( d ) f i d 1 9 的c 肌流在q 4 上所占带宽 图3 - 7 多瓶颈链路下c s f q 算法与i c s f q 算法公平性的比较 ，。，。，。，l 孵 尊 * 抽 点 ” 舯髟龟矿轼掣瓢旷和。 憎 喵 憎 蜡 哺 柚l_摹t电肇翟譬-霉釜 、；j1，dj1，1，l，jl ” 越擎t柚堑毓譬萋銎 篝 等 惜 押。-i器一m蕾墨蓼 硕十学伊论文 笔= 章一种进的核心无状态队列管理锋法 为f l o w i d = 9 的c b r 流在q 4 上的实际占用带图，图3 7 ( c ) 为f l o w i d = 1 4 的 c b r 流在q 2 上的实际占用带宽图，图3 7 ( d ) 为f l o w i d = 1 9 的c b r 流在q 4 上的实际占用带宽图。我们可以看到，在多瓶颈链路网络拓扑下，我们可以看到 原有的c s f q 算法对c b r 流的实际占用带宽控制不是很好，c b r 流占用的带宽 大大地超出了其所应该占用的理想带宽。由于q 2 和q 4 上面活动流的数目均为 1 5 ，所