（通信与信息系统专业论文）公平队列算法在无线网络中的应用.pdf

摘要 摘要 在不久的将来，宽带城域无线接入系统( b w a ) 将成为全球通信架构中的一 个重要的组成部分。人们对b w a 系统提出对不同层次的业务提供不同的q o s 服 务的要求。在所有的需要被解决的技术专题中，分组调度是最重要的，调度算法 提供了带宽控制、拥塞控制的机制。i e e e8 0 2 1 6 标准本身只制定了介质访问接入 ( m a c ) 层的框架，但具体的调度算法却留给厂家来选择。本文正是在这种情况下 分别针对p m p 和m e s h 两种网络形式开展对无线资源调度算法的应用展开研究 的。 本文一方面对p m p 网络中宽带无线接入网络m a c 接入关键技术中的调度和 资源分配进行研究。通过对有线网络中保证服务质量( q o s ) 发挥了重要作用的加权 公平队列( w f q ) 、改进的加权公平队列( 胛2 q ) 等算法的研究，进一步研究了如何 将这些算法应用到i e e e8 0 2 1 6 的调度体系中去。然后通过m g f q 算法对系统的 性能进行分析，获得平均时延的上下界。为了验证理论分析，我们在o p n e t 中对 新的调度体系进行建模对其性能进行了仿真验证，并对仿真结果进行分析。 另一方面，与i e e e8 0 2 1 6 d 的网格( m e s h ) 结构相对应，本文迸一步研究了公 平排队算法在分布式a d h o c 网络中的应用，我们研究了一种全分布式的自协调 逼近的a d h o c 公平队列算法，进而讨论了算法中采用的三种机制的原理和作用， 最后对算法的性能进行了分析。 关键词：公平队列服务质量调度宽带无线接入无线城域网 a b s t r a c t a b s t r a c t i nt h ef u t u r e ，a r e ab a n d w i d t ha c c e s sn e t w o r kw i l lp l a ya ni m p o r t a n tr o l ei ng l o b a l c o m m u n i c a t i o ns t r u c t u r e s ob w aa r er e q u i r e dt op r o v i d eq o sg u a r a n t e ef o rd i f f e r e n t s e r v i c e i na l lt e c h n o l o g yp r o b l e m s ，t h em o s ti m p o r t a n ti sp a c k e ts c h e d u l i n g ，b e c a u s e p a c k e ts c h e d u l i n gc a nb e u s e dt oc o n t r o lb a n d w i d t ha n dc o n g e s t i o n i e e e8 0 2 1 6 p r o t o c o lo n l yd e f i n eaf r a m eo fb a n d w i d t ha c c e s sn e t w o r k ，a n dl e a v es c h e d u l i n g a l g o r i t h mt ov e n d e gt h i sp a p e rd os o m er e s e a r c hj u s ti nt h i ss t a t u st ow i r e l e s sr e s o u r c e s c h e d u l i n ga l g o r i t h ma p p l i e di np 【pa n dm e s hn e t w o r k i no n eh a n d ，t h i sp a p e r soner e s e a r c hp u r p o s ei st h es c h e d u l i n gs t r u c t u r ea n d r e s o u r c ea s s i g n m e n ta l g o r i t h mi np m pn e t w o r k a f t e rd os o m er e s e a r c ho fw f qa n d w f 2 qw h i c hp l a ya ni m p o r t a n tr o l ei nw i r e dn e t w o r k ，w ed om o r ed e e p l yr e s e a r c hi n h o wi n t e g r a t et h e s ea l g o r i t h mi n t oi e e e8 0 2 1 6 t h e nw eg e tt h em e a nd e l a y s b o r d e r l i n e b ym i g f q f o rv a l i d a t et h et h e o r y , w eb u i l dam o d e lf o ro u rn e w s c h e d u l i n gs t r u c t u r e ，a n dt h e ns i m u l a t ea n da n a l y s i st h i sm o d e l sp e r f o r m a n c e o nt h eo t h e rh a n d ，c o r r e s p o n d i n gw i t hi e e e8 0 2 1 6m e s hs t r u c t u r e ，t h i sp a p e rd o f u r t h e rr e s e a r c ht ot h ea p p l i c a t i o no ff a i rq u e u ea l g o r i t h mi n t od i s t r i b u t i n gn e t w o r ko r a d h o cn e t w o r k b a s e do na s e l f - c o o r d i n a t i n ga p p r o a c ht od i s t r i b u t e df a i rq u e u i n g i 1 2a dh o cw i r e l e s sn e t w o r k s ，w er e s e a r c ht h et h e o r ya n df u n c t i o no f t h r e em e c h a n i s m i nt h i sa l g o r i t h m f i n a l l yw ea n a l y s i st h ep e r f o r m a n c eo f t h i sa l g o r i t h m k e y w o r d ：f qq o ss c h e d u l i n gb w aw m a n 创新性声明 、7 6 9 5 4 2 0 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一局工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：丛之琏：日期2 1 1 羔：2 皇 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 本人签名： 导师签名： 拯缝： 妒 日期互! ! 皇：f ：2 1 日期坦盟3 。 第1 章绪论 第1 章绪论 1 1 引言 随着近年无线技术的飞速发展，无线技术能够为人们提供越来越宽的带宽、 越来越高的速率。从最初的单载波到扩频技术到先进的调制技术的出现，无线通 信抗干扰和多径的能力也越来越强。多天线技术和智能天线技术的应用，也使无 线传输也变得越来越可靠，越来越高效。随着新技术的实用化和产品化，人们对 无线的应用也提出了更高的要求，无线网络不仅要承载单纯的数据或语音的，而 且还有多媒体等多种业务。这些业务对带宽的需求和时延的要求都不尽相同。另 一方面因为人们对移动性的需求日益增加，因此网络的拓扑也从传统的点到多点 发展到m e s h 网络、a d h o c 网络等。这些新的挑战都对无线m a c ( m e d i u m a c c e s s c o n t r 0 1 ) 层的设计提出新的要求，其中最大的最关键的是对无线资源管理策略的挑 战。 原有的无线m a c 层协议或者保证了业务传输的灵活性或者保证了业务传输 的可靠性。如无线局域网8 0 2 1 1 协议中的m a c 协议采用的是c s m a c a 机制， 但这种机制只能保证业务传输的灵活性，当有多个不同类型的业务同时传输时， 则不能提供较好的业务之间的隔离，虽然可以通过不同的竞争退避时间来区分不 同的优先级的业务，但是依然无法确保业务时延的上界和下界。传统的t d m a 协 议则因为对资源采用时隙方式来分配，因此可以保证实时业务的时延边界，但是 却丧失了数据业务的突发性和灵活性。因此当需要有多种类型的业务同时传输的 时候，m a c 协议往往采用c s m c a + t d m a 的方式来保证协议的在灵活性和可 靠性之间取得平衡，但这种方式实现起来比较复杂实用化较为困难。 因此本文结合有线网络中的保证q o s 的传统的公平排队算法，结合现有的协 议分析了如何在需要传输多种类型的业务的情况下如何保证各种业务的 q o s ( q u a l i t yo fs e r v i c e ) ，并对公平排队算法应用到一些协议中的性能进行分析仿 真。 1 2 资源调度算法的研究现状 通过对如何保证在i n t e r a c t 中传输毒爨楚等业务的q o s 的研究，i e t f ( i n t e m e t e n g i n e e r i n g t a s kf o r c e ) 提出了两种主要的q o s 模型t h e i n t e g r a t e ds e r v i e e s ( i n t s e r v ) 模型和t h ed 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 ) 模型”。 公平队列算法在无线网络中的应用 i n t s e r v 模型在很多方面类似于a t m 网络中的q o s 架构。它的主要的思想是： 对于每一个实时业务流的资源可以被精确预约，以给业务提供指定的q o s 保证。 r s v p 协议就是用来在i n t e r n e t 网上用于给业务在每一个路由器上精确的预约 资源的协议【3 j 。 呼叫接入控制c a c ( c a l la c c e s sc o n t r 0 1 ) 过程决定了一个业务的资源请求是否 应该被接受，当流建立起来以后这个过程就不用再考虑整个网络的资源情况。不 幸的是i n t s e r v 模型不能大规模应用，只能用于小型网络或者企业的虚拟专用网络 中运行。 另一个q o s 模型是d i f f s e r v 模型，d i f f s e r v 体系模型的核心思想是：在网络边 界将数据流按q o s 要求进行简单分类，不同的类在内部节点的每次转发中实现不 同的转发特性。d i f f s e r v 体系使得i s p 能够提供给每个用户不同等级和质量的服务。 用户( 或网络边界节点) 通过设置每个数据包的d s 字段( i p v 4 首标中的服务类型 ( t o s t y p eo fs e r v i c e ) 字段或i p v 6 首标中的通信类( t r a f f i cc l a s s ) 字段) 的值要求特定 的服务等级。其中，被设置的d s 字段被称为区分服务码点( d s c p ) 。在每个支持 d i f f s e r v 的网络节点中，这个d s 值将数据报映射到类转发行为p h b ( p e r - h o p b e h a v i o r ) 中去，从而在转发中区别对待。用户和i s p 之间有一个协定，此协定规 定了该用户在每个服务等级上所能发送的最大速率。超过此最大速率的数据包或 被丢弃，或无法享受到它所要求的服务。d i f f s e r v 网络最大的特征是其可扩容性。 此体系将许多复杂的控制移到了网络边界，使内部节点能对叠加之后的数据流进 行处理，而不必对每个数据流分别处理，从而大大减小了网络内部应该记录的状 态，简化了网络内部节点的操作。这样d i f f s e r v 体系就可以布置到一个大规模的网 络中去。 我们吸取有线网络q o s 架构的优点，结合近年来公平队列算法的最新发展， 研究了在两种无线环境下的q o s 调度架构，并对其性能进行分析和仿真。 在分组交换网络中的q o s 可以以一个指定的参数集来表示：时延( d e l a y ) 、时 延抖动( d e l a yj i t t e r ) 、带宽( b a n d w i d t h ) 、丢包错包率( l o s so re r r o rr a t e ) 。在这样的 有线网络中维持q o s 需要一套成熟的监督和控制机制来保证达到我们想要的q o s 。 在q o s 管理体系中的一个至关重要的元素是业务所经过的各个路由器中的分组调 度机制。调度器决定了每一个路由器中的分组被服务的先后顺序，也决定了队列 中分组的排队时延。 同有线网络一样，无线网络也需要对资源进行管理和控制，在无线网络中调 度器对系统的性能也起到了至关重要的作用，它也是保证系统q o s 的关键因素。 一个好韵调度算法将在保证各个服务流之间的公平性的同时也必须保证各个服务 流之间的有效隔离。公平性是指每一个依据其权重在系统中获得相应的带宽。有 效的隔离则是指系统要有对恶意流的控制和屏蔽能力。猛一看，好像有线环境下 第1 章绪论 的调度模型可以用来在无线信道中调度，并且将在无线信道中工作正常。然而， 共享无线信道有两个特征将使有线网络中的调度模型不适应于无线信道】。( 1 ) 突 发信道错误。( 2 ) 依赖于位置的信道容量和错误。由于无线传输中的干扰是与节点 所处的位置有关的，因此不同的点到点的链路因为位置和无线环境不同，相应的 信道容量也不同。除此之外，由于干扰，衰落和多径的影响，信道错误也是节点 所处的位置有关的。这就暗示在任何时刻，都有可能有这样的情况，一些流可以 传输而一些流不能传输。因此同一时刻，仅仅信道中的一个子集可以被调度，而 这个子集则是随着时间动态的改变。而在有线环境下，信道中所有的流至少在同 一时刻都可以参与调度。基于这几点，就清楚的可以看到，、因为无线环境于有线 环境的不同，而导致应用到无线信道中的调度模型与有线环境中的不同。 1 3 研究内容 我们研究的动机是由于近年来关于公平队列算法的发展推动了对无线环境中 的q o s 架构的研究，因此我们相信将公平队列算法的最新成果应用到实际的无线 环境中去将会大大改善多媒体业务在无线传输中的质量。 我们选择了两种无线的拓扑结构作为我们研究的环境：一是点到多点的宽带 无线接入环境，我们首先对i e e e8 0 2 1 6 的协议进行深刻研究，发现协议对调度部 分是留给设备制造厂家设计的，它的调度部分只是停留在一个简单的模型上；然 后我们将公平队列算法应用到其中，比较了有公平队列算法后的系统性能与其简 单调度模型的系统性能。我们研究的第二个环境是在a d h o c 的自组织网络中， 我们对采用了新的分布式协调算法的a d h o g 风络进行了性能的分析与仿真。 我们的研究目的是通过仿真证明了无线公平队列算法应用到无线网络中去所 带来的性能的改善是很大的，并通过仿真为两种环境下的调度模型进行验证。 4 公平队列算法在无线网络中的应用 第2 章公平队列算法( f a i rq u e u ea l g o r i t h m ) 2 1 引言 人们在有线网络时期就在广泛研究公平排队系统，它主要的作用是用于分组 调度，路由器中的调度器起到了拥塞控制和给不同类型的分组保证不同的业务质 量。 图2 1 是一个简单的路由器模型，其中的各个部件如下所述： 图2 1 一种简单路由器模型 包分类器：基于分类策略的包的分类器。 路由表+ 交换网络：在路由转发策略控制下决定输入到输出的正确映射。 调度器：决定下面该服务哪一个业务流。 在整个网络中有很多进程来负责确保网络有效运行，它们分别运行在不同的 时间级上： 1 ) 调度和缓冲管理( u s ) 2 ) 反馈控制( m s ) 3 ) 重协商( s e c ) 4 ) 呼叫控制路由( m i n ) 5 ) 容量规划网络设计( d a y ) 由此可见调度器在网络中充当着最小粒度的协调翎，它作用于每一个包， 并有效的控制着网络。调度算法要完成如下功能： 箜! 重垒坠型簦鲨! ! ! ! ! g ! ! 堡垒! g ! ! ! 坐翌! 一5 1 ) 保证不同类型业务的不同的q o s ； 2 ) 给不同的业务分配带宽、保证时延、丢包率、限制时延抖动； 3 ) 决定网络是否公平。 公平队列算法是调度器中常用的算法，这类算法统称为f q ( f a i r q u e u i n g ) 算法。 w f q 算法是f q 算法中最重要的一种。 w f q ( w e i g h t e df a i rq u e u i n g ) 算法的思想在参考文献 4 中第一次被提出，但是 术语w f q 本身并未在该文献中出现。文献【4 中提出并详细地分析和仿真了f q 算 法。在f q 算法中各个会话( 有人用“流”这个术语，在面向连接的网络中也称为“连 接”。这些术语在本文中含义相同) 的权重是相同的。只是在最后的讨论部分文献 4 】 才指出这种情况可以推广到各个会话的权重不同的情况。在参考文献 5 中，作者 提出了g p s ( 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 g p s ( p a c k e t - b y - p a c k e tg p s ) 算法，并 且指出p g p s 和文献 4 q h 的w f q 算法是同一个算法。值得注意的是，w f q 这个 术语除了指一种特定的算法( 这时它就是p g p s ) 之外还有其他含义。有时w r q 是 指一般的加权公平调度策略，那么它所涵盖的算法就包括s c f q 。w f 2 q 等等的很 多算法。 近年来，基于g p s 模型的分组公平排队( p f q ：p a c k e tf a i rq u e u i n g ) 调度算法 得到了较为广泛的研究。所有的p f q 算法皆基于： 1 ) 系统维持一个全局函数p ( t ) ，称为系统虚时间函数( 或s y s t e mp o t e n t i a l f u n c t i o n ) ，用以记录调度器已提供的服务量，调度器利用系统虚时间函数为每个分 组计算其相应的开始时间标签和完成时间标签，见式( 2 1 ) ； 2 ) 执行一定的分组选择策略，有最小完成时间标签优先( s f f1 ”1 ) 、最小合格 完成时间标签优先( s e f f t3 】1 4 1 ) 、最小开始时间标签优先( s s f 肛1 ) 。 霹= m a x 把，y ) ) ， ，+ ，1 、 f j = s ：+ 琏| r i k ；r - q 。 式中：p ? 表示连接( 或会话) i 的第k 个分组，a ? 表示p ? 的到达时间，钟表示 p 的服务开始时间标签；彤表示p ? 的结束服务时间标签，辟表示p ? 的分组长度， 表示连接i 的预约速率，矿o ) 表示系统t 时刻虚时间函数值。 w f q 的提出先于g p s ，其分组选择策略属于s f f ，而w f 2 q 的分组选择策略 属于s e f f ，w f q 等系列算法的时间标签都是按式( 1 ) 计算，其系统虚时间都按下式 计算： r ( o ) = 0 矿k 一) 2 掣+ 蚩 j e 最 f r j 一，j i ，- ，= 2 , 3 ， ( 式2 2 ) 公平队列算法在无线网络中的应用 这里假定在时间段( f 。，t j ) 系统内阻塞的连接没有变化，且这些阻塞的连接 的集合用b ，来表示。我们在这里可以简单的认为阻塞就是该业务队列中仍然有排 队的分组。关于阻塞集的概念是人们在研究公平排队算法是最容易混淆的概念。 在w f q 算法中的阻塞集不是指利用该算法后的实际系统中的被阻塞的集合，而是 一个在参考的g p s 系统中的被阻塞的集合，具体的概念将在下面阐述。 2 2 公平队列算法的描述 2 2 1r o u n d r o b i n 算法 在调度模型中最早提出的调度模型是r o u n d r o b i n 模型，该模型的原理如 图2 ，2 所示： 1 t j 皿 2 ( 皿 n 叫( 圆 输入流 圈2 2 公平队列模型一 调度器为每一个业务流保持一个队列，r o u n d r o b i n 算法在该调度架构中 轮流从每一个业务流中取出一个包发送出去，当一个业务流为空的时候，调度器 马上转移到下一个业务流。该算法有效的分别服务每一个业务流，但是在业务流 中包的尺寸可变的情况下，该算法却不能提供带宽的公平分配，包尺寸大的业务 流显然获得比包尺寸小的业务流更多的带宽。 2 2 2b i t - b y - b i tr o u n dr o b i n 算法 为了解决上述算法中的不公平性，人们提出了b i t - b y - b i tr o u n dr o b i n 算 法。该算法假设业务流中的包可以分成一个一个b i t 来传输，调度器依然轮流服 务每一个业务流。该模型如图2 3 所示： 蔓! 童垒! 坠型篁鲨! 里坐垫竺! 垒! g 堕尘里! 一7 图2 3 b i t - b y b i tr o u n dr o b i n 模型 在该模型中我们假设r ( t ) 表示该算法的轮询次数，r ( t ) 是一个连续函数。我们 用二o ) 表示活动的业务数，活动的业务指在队列中有b i t 要传输的业务。假设是 调度器的出口速率，则存在以下等式。 a r“ 一o t5 瓦丽 对该式两边积分为： 耻l 惫t ( 式2 3 ) ( 式2 4 ) 也就是说活动的业务越多，轮次数增长的越慢。 假设有一个业务中的个包大小为p ，在r 。的时候这个包的第一个b i t 被传输 在时间t 的时候这个包被传输完毕，则存在 r ( t ) = r ( t 。) + 尸 ( 式2 5 ) 我们设业务a 中的一个包为i ，则这个包的大小表示为只。；设这个包到达系统 的时间为，? ，设掣和e 4 为包只4 开始被服务和结束服务时的系统保留的轮次数 r o ) ，则存在以下等式： 一 f ? = s ：斗p ? s 7 = m a x ( f , ：l ，r 够j j ( 式2 6 ) 该式中，r ( t ) 是一个线性分段函数，是整个系统所保留的轮次数。 但是这个模型显然是不现实的，这种方法不能用于分组服务系统中。而且这 种模型只能在各个业务中公平的分配带宽，不能按照业务的需求成比例的给业务 分配不同的带宽。 2 2 3g p s 算法 人们又提出了一种更加理想的公平队列模型，这种模型可以按照用户预约的 速率来对不同的业务进行服务，业务之间预约的带宽可以不相等。邀种理想的调 度模型是g p s 模型”i 。 公平队列算法在无线网络中的应用 这种调度模型如图2 4 所示 图2 4g p s 模型 在图2 , 4 中每一个流被分配一个权重中。，中：西。，假设总服务器的出口速率 为r ，则业务流i 被分配到的带宽为( 假设该流处于活动状态) ： ( 式2 7 ) 上式中b 为处于阻塞状态的业务流。这种服务模型假设业务流被连续服务， 服务器可以同时并行服务每个流，每一个流所获得带宽与权重成比例，当一个 流处于非空状态的时候我们就称这个流被阻塞，或者说这个流处于活动状态 ( h c t i v e ) 或者说这个流有订货( b a c k l o g g e d ) 。关于该服务模型的公平性我i i 女n t 定义： 定义2 1 一个g p s 调度器是工作保持的( w o r kc o n s e r v i n g ) ，对n 个队列进行 n g - ，并且可以用n 个正实数- ，r 2 ，来表示，且r = 。设彬( r ，f ) 为连 接i 在0 ，) 期间所接受的服务。若某个连接在时间t 排队的流量为正数，则称这个 连接在时间t 阻塞a 那么g p s 可定义为对在时间段0 ，t ) 内持续阻塞的任一连接i ， 都有下式成立： 揣考驴墟，- 埘 。式2 m 上式要求，其中业务i 必须是在时间段r ，) 内被阻塞。则我们就说该系统是公 平的。g p s 中业务i 被保证的速率为晶，则毋 垒一r 。 西j 。 图2 5 是一个g p s 系统工作的例子。图2 5 中红颜色代表业务1 ，绿颜色代表 业务2 ，蓝颜色代表业务3 。其中o 。= o 2 5 ，m 2 = o 2 5 ，0 3 = 0 5 。因此在时间【0 ， 蔓! 童坌兰坠型篁鎏! ! ! 堑q ! ! 坚垒! g 塑! 墅! 一9 2 z f a q ，业务2 、3 被阻塞，则业务2 分配到的带宽为面三每= ；，业务2 分配的 带宽为去= ；。确2 ，3 勰 带宽为0 2 5 ，业务2 分到的带宽为o 2 5 ， 业务1 、2 、3 被阻塞，则业务1 分到的 业务3 分到的带宽为o 5 。 图2 5g p s 系统一：作过程 我们用数学公式去描述包在g p s 系统中的调度情况为： 掰= m a x k ，矿) ) f = s ? + 霉几 ( 式2 9 ) 其中p ? 表示连接( 或会话) i 的第k 个分组，口? 表示p ? 的到达时间，彰表示p ? 的服务开始时间标签，劈表示钟的结束服务时间标签，口表示p j 的分组长度， 表示连接i 的预约速率，y o ) 表示系统虚时间，它是一个分段线性增长函数，且服 从下式： v ( o ) = 0 矿( t j _ t + 7 y ) = 叱) + 瓦t x r e b j f f 一，一i ，j = 2 , 3 ， 2 2 4p g p s 算法 ( 式2 1 0 ) 因为g p s 算法是一种实际上不可能实现的算法，因此它只能作为现实算法逼 近的且标一呋们为了模拟g p s 算法提出予嗍- 謦法。p g p s 算法的内容如下： 定义2 2 假定在时间t 以后系统无分组到达。调度器选择在相应的g p s 系统 1 0 公平队列算法在无线网络中的应用 里最先完成服务的分组进行服务，则该调度器为p g p s ( p a c k e t - b y - p a c k e t ，g p s ) 。 p a r e k h 等人提出g p s ，并证明了g p s 与p g p s 之间的关系。根据参考文献【5 】，g p s 与其对应的p o p s 间存在下列性质，我们用定义2 来说明这个性质。 定义2 3g p s 系统的分组服务完成的顺序与将来的分组到达无关，g p s 与 其对应的p g p s 间存在下列性质： d 一d 争 v f 一 ( 式2 1 1 ) 彤，a e s ( 0 ，f ) 一彬，。( o ，r ) - p ( t ) ) 。 定义2 6 分组系统的阻塞更新事件为下列事件的任一事件： t 时刻某个空闲的连接有分组到达，并且满足p ( 钟) e 。，设f = o ， 将连接i 加入虚阻塞集； t 时刻某个队列的e 。- p ( t ) ，将连接i 从虚阻塞集中删除。 定义2 7 若某分组调度系统按式( 2 1 ) 为分组加标签，按定义3 的阻塞更新毒 件来更新系统的虚阻塞集合，分组选择策略为s f f ，即选择最小完成时间标签的分 组服务，按下式计算系统虚时间： 尸( f ：) 一盹) = ，( t 2 一t 1 ) l z r , v i 哪：) ( 式2 1 3 ) 若( ，l ，屯) 内虚阻塞集不变，则称该系统为加权公平排队系统，简称w f q 。 引理2 2 ：w f q 的系统虚时间和与它对应的g p s 的系统虚时间相等。 证明：因为w f q 按s f f 选择分组，是工作保持的，其对应的g p s 也是工作 保持的，根据引理1 ，二者的系统忙期相同。因此，只需证明一个系统忙期内二者 的虚时间相同。如果系统虚时间在每个阻塞更新事件发生时都和对应的g p s 的虚 时间相等，则w f q 的虚阻塞集合与g p s 的阻塞集合相同，则该系统能保证虚时 间始终相等。下面用数学归纳法证明这一假设。设以表示第k 个阻塞更新事件发 生的时间。当第一个分组到达时，“系统从空闲变为忙，设该时间为0 ，则p ( o ) = o 。 而t = o 也正是第一个阻塞更新事件发生的时间，因此虚时间相等对第一个阻塞更新 1 2 公平队列算法在无线网络中的应用 事件的时间成立，并且此时g p s 的阻塞集合与w f q 的虚阻塞集合相同。假设虚 时间相等对第k 个阻塞更新事件的时刻成立，即r 。0 ，f ) = ( f ，f ) ，到下一次阻 塞更新事件发生之前，g p s 系统的阻塞集合没有变化，根据虚阻塞集合以及阻塞 更新事件的定义，w f q 的虚阻塞集合也不变，即二者保持相同，因此第k + 1 个阻 塞更新事件的系统虚时间相等也成立，证毕。 从上面的分析我们可以看出w f q 系统的虚时间实际上就是g p s 系统的虚时 间，也就是说在计算2 1 3 式的时候，其考虑的虚拟阻塞集合应是对应的g p s 系统 的阻塞集合，而不是实际的采用了w v q 的系统的阻塞集合。 ( 2 ) w f 2 q 算法 w f q 算法因为虚时间逼近于g p s 算法，因此w f q 算法有着于g p s 算法相差 不多的时延特性，w f q 算法与g p s 算法有以下关系： d ，k ，。- d 争v 城 彬，g 。( 0 ，f ) 一彬，。( o ，r ) 三。v f ，f w f q 算法保持了g p s 算法有时延边界的特性，但它的时延只能保证最多滞后 于g p s 系统三。，不能保证超前多少，也不能保证各个队列公平分配系统的时 延，可能会造成系统的不公平，图2 8 是一个w f q 系统的安排分组的过程。 设业务1 每单位时间发送一个分组，共发送n + 1 个分组，业务1 的权重为0 5 。 设业务2 到业务n + l 仅在时间0 发送一个分组，各队的权重为1 2 * n 。所有分组长 度相等都为上。，。则系统分组到达时序如下： s 1 s 2 s 3 s 4 图2 8 分组到达顺序图 g p s 分组服务时序和w f q 分组服务时序分别如图2 9 和2 1 0 所示。 鼢 一一 笙! 童坌垩坠型墨垄! 墅! 塑! 些垒堑竺塑里! 旦 s ，乓斗二二i 瓣 s 2 s 3 s 4 缈1 卜墨卜 s 1 图2 9g p s 服务顺序图 3 2 卜菩* 茜一 s 3 l ：。j i ! ! ! i l 。一 0n + l n + 22 n 8 4 卜未鲁3 2 l n 一0n + 2 n + 。 d 1 鼢1 卜1 蔷警一 图2 1 0w f q 服务顺序图 由此可见w f q 存在两个问题：( 1 ) 对流超前g p s 的时间多少没有一种有效 的保证。( 2 ) 带来时延的不稳定，如业务t 。因此为了解决以上问题，出现了w f 2 q 算法。该算法内容如下： w f 2 q 是种几乎完全近似于g p s 算法的调度算法，它与对应的g p s 算法之 间的差不大于一个分组的长度。w f 2 q 算法是在w f q 算法的基础上修改而成的， 因此它与w f q 算法之间有一些差别：在w f q 算法中服务器选择所有的在t 时刻 有分组的流中在对应的g p s 系统中最先完成服务的分组。而w f 2 q 算法中服务器 在选择在t 时刻在对应的g p s 系统中已经开始对这个包进行服务( 也有可能已经完 成) 的流中的最先完成服务的分组。因此w f 2 q 算法缩小了分组选择的范围，但是 却保证了时延。 图2 1 1 是一个w f 2 q 算法的示意图，从中我们可以看到与w f q 算法相比， s l 被以分散的方式被服务的；而在w f q 算法中，s l 被服务的过程中有较大的中 断，因此时延的抖动会比较大。而w f 2 q 算法能有效的控制时延，迫使算法的性 能最接近于理想的g p s 系统。在w f 2 q 算法中，可以保证式2 1 5 的成立。 公平队列算法在无线网络中的应用 s ，i 生i ! l l 茎。l 墨! 匕：二二一璺：。型 012 3 45 6 7 2 n 22 n 12 l l2 n + i s 2 卜产卜茜一 0122 n 。 卜业3l 4 2 上n 一0 钳卜也5l 6 2 卜0n 鼢1 卜_ 矗警一 d - 图2 1 1w f 2 q 服务顺序圈 d ，k 嘲一d 导 彬，。( o ，f ) 一彤，。：j ( o ，f ) 。 ( 式2 1 5 ) w t , w f 2 0 ( 0 ，r ) 一彬。( 。，r ) ( 一手 上，。 上式中d 表示时延，w ( 0 ，f ) 表示在时间( o ，r ) 内服务器所服务的b i t 数。 2 3f q 算法的有界公平准则 研究了上面的一些f q 算法，它们各自有自己的公平性的准则，但我们可以总 结它们的公平性准则f 9 l ，并研究其所蕴含的性能指标。我们记( ，t ：) 为流k 在时 间( f 】，屯) 内所被服务的量的总和。吼( f ，t ，) r k 表示流k 在这个时间段的归一化服务 量。在时间t 一个流可能是有订货的( 队列中有分组在等待) 这样的流的集合记为 b ，f ，) ( 对于w f q 则是对应在参考系统g p s 系统中的忙与闲) ，也可能是空闲的 这样的流的集合记为4 ( ，t ，) 。我们不可能苛刻的要求一个分组调度算法绝对公平， 而只能将其公平度控制在一个可以允许的范围内，也就是有界公平： l w k ( 吒t l , t 2 ) 一掣鲫m b ( t t , t 2 ) 吒 0 在这里不同的f q 算法妒的取值是不同的，例如s c f q ( 自时钟公平队列算法) 和s f q ( 开始时间公平队列算法) 中取妒= 三：i a x + 上? “7 0 ，这里上：“和三? “分别为 流k 和j 的最大分组长度。为了便于分析我们又为f q 系统定义了两种虚时间，一 种为系统虚时间谁) ( s y s t e mp o t e n t i a l ) ，一种为连接虚时间咋o ) ( c o n n e c t i o n p o t e n t i a l ) ，连接虚时间保挣跟踪流的归一化服务量，即 整! 童坌垩坠型簦鲨! 塑堡垒些堕垒! 罂j 些婴! 坚 我们将一个流的服务滞后量记为瓯( ，) = v 一耽e ) ， 以是对服务滞后量的一种限制： 0 坑0 ) 吼o ) 因此服务量的公平边界可 ( 式2 1 8 ) 吼o ) 是与每个流相关的一个服务滞后量的边界参数，它与每个流的预约速率 有关，例如s c f q 算法中吼o ) = 厶0 ) ，o ，在时间上对瓯e ) 和敛o ) 做统计平均后 也存在： 0 s 硼s 翮 ( 式2 1 9 ) 但是有一点我们需要注意，当业务流k 处于状态时瓯o ) 吼o ) ，而当业务流 处于空闲状态的时候瓯o ) = 0 ，因此我们需要将这种情况考虑进去，设业务流k 处 于订货状态的概率为p r 瞳b 】，则有下式成立： 0 羽羽p r 陆b 】 ( 式2 2 0 ) 对于p r k b l 也就是队列k 中有分组在等待的概率实际上也就是服务器忙的 概率，而服务器忙的概率p ：工- 2 ：z z c ，而分散到每一个流上则 p r 陆b 】 上。_ ，在这里厶是队列k 的分组平均长度，咯是流k 的分组预约速 率。因此流k 的平均服务滞后量的范围为： 7 _ 一 0 瓯o ) 兰生妒。 ( 式2 2 1 ) 另外在两个不同的流之间我们用来衡量它们的相对滞后的一个量为 毛o ) = 心o ) 一_ ( f ) = ( v ( ，) 一v ( f ) ) 一( v ( ，) 一v 。( r ) ) = 口o ) 一坑o ) ( 式2 2 2 ) 如( ，) 也是一个随机变量，它的均值是有界的一吼凡( f ) 竹，七，ek ，因 为o 夏d 五生瓦，所以： 。羽观等万五等瓦 这样我们就求出了否丽和否厕两个随机变量均值的范围，从而为我们在以后 分析f q 算法的时延边界时提供重要的理论依据。 儿0屯 ”、：一 0 d帆胜 砸也 v v ，j、【 i i 也 公平队列算法在无线网络中的应用 第3 章i e e e8 0 2 1 6 中f q 算法的研究 3 1i e e e8 0 2 1 6 与d o c s i s 下的q o s 服务流 i e e e8 0 2 1 6 协议是在d o c s i s 协议的基础上发展起来的，因此很多地方跟 d o c s i s 协议是一样的。d o c s i s 协议是一种h f c 有线光网络中的m a c 层接入控 制协议，i t f c 有线光网络主要被用在广播t v 信号给用户。这种系统被大量应用 给终端用户提供多种业务的服务，它不仅能广播电视信号和其他下行数据业务( 如 f t p 等) ，而且可以提供上行的多种数据接入服务。因为两种协议的想近性，因此 我们的研究不仅对于i e e e8 0 2 1 6 ( w i m a ) ( ) 宽带接入网络，而且对于h f c 有线宽 带接入网络都是适用的。 我们在研究i e e e8 0 2 1 6 与d o c s i s 协议前，先看一下这两种协议的帧结构， 和它们对于不同类型业务的处理。 d o c s i s 的帧结构如图3 1 所示： d o c s i s 的网络拓扑中由c m t s ( c a b l e m o d e m t e r m i n a t i o ns y s t e m ) 来负责给一 片小区的用户提供服务，每个用户需要c m ( c a b l em o d e m ) 来通过总线与c m t s 相 接。因此c m t s 相当于i e e e8 0 2 1 6 中的b s ，而c m 相当于i e e e8 0 2 1 6 中的s s 。 d o c s i s 是频分双工的，上行信道和下行信道分别使用不同的载频，其传输速率和 带宽是不对称的，通过d c d ( d o w l lc h a n n e ld e s c r i p t i o n ) 和u c d ( u pc h a n n e l d e s c r i p t i o n ) 来描述上下行链路的调制方式和传输速率。 厂 n心刘 飞孓、。 卜、n、h 。暮r d 。一。阳删鼬酬 图3 1d o c s i s 帧结构 每一个上行信道都被分为固定大小的微时隙流，d o c s i s 的m a c 层机制利用 请求授予( r e q u e s t g r a n t ) 机制来协调多个c m 之间的传输。如果一个c m 需要 在上行信道上发送数据它必须先请求，然后c m t s 才磐分配一个能够传输一定数 量数据的传输机会给c m 。c m t s 在下行信道上周期性的发送m a p 信息来给c m 指出上行信道上的资源分配情况，c m 根据接收到的m a p 就可以判断出上行信道 中哪些时隙时划分给自己的。因此这相当于一种竞争预约的机制，c m 在预约到带 宽内是无冲突传输的。在m a p 中c m t s 除了要给c m 指出资源分配情况，而且 还要指出一段竞争期用于c m 通过竞争的方式向c m t s 发送带宽请求。在竞争期 内d o c s i s 采用最简单的二进制退避算法来解决c m 之间竞争发送带宽请求而引 起的碰撞。当一个c m 通过竞争获得一次传输数据的机会，那么它就可以通过 p i g g y b a c k 来捎带其它的上行信道带宽请求。 d o c s i s 还支持分段( f r a g m e n t a t i o n ) 和串联( c o n c a t e n a t i o n ) 机制。当c m t s 分 配给c m 的传输机会的大小小于c m 实际请求的大小时，c m 应该用可能填充到这 个传输机会中的最大数据量来填充到这个传输机会中，而剩下的数据要等到下一 次分配传输机会的时候发送。c m t s 则能够把分段后的数据重组。同理当c m t s 分配给c m 的传输机会的大小大于c m 实际请求的大小时，c m 应该将自己缓存中 的下一个包与当前包串联起来来填充满这个传输机会，同样c m t s 也可以将串联 后