（通信与信息系统专业论文）互联网中服务质量控制机制与算法的研究.pdf

北隶邮f u 人学博l ? 论义 中史摘嘤 中文摘要 近年来，随着互联网的日益普及和无线通信技术的飞速发展，i p 网络丌始承 载更加丰富的网络服务，尽力而为的服务方式已经不能满足许多实时应用的工作 要求，对互联网服务质量保证机制和算法的研究逐渐成为热点。传输层在互联网 的协议栈处于中问位置，因此研究网络层与链路层对传输层性能的影响意义重大。 本论文围绕着下一代互联网的服务质量体系及其相关的控制机制和算法进行了研 究，研究的侧重点选择在区分服务网络的公平性，无线分组网( w l a n ，a dh o c 网) 中的m a c 层协议性能及改进等几个方面，主要考察了传输层，网络层以及 m a c 层的相关算法以及相互影响。论文中的工作主要包括以下几个方面： ( 1 ) 针对区分服务网络中响应流与非响应流共存时获取带宽的不公平现象，提 出了一种直接捐j 塞反馈机f 目j ( d c c s ) ，配合网络边缘的动态流量调节( d t c ) 算法， 能够为区分服务网络提供较好的公平性。该机制不仅能改善响应流与非向应流之 间的公平性，而且能减小响应流( 如t c p ) 之间由于分组长度，微流数目及环回时延 ( r t t ) 等因素面产生的差异。 ( 2 ) 对无线局域网( w l a n ) 的接入，提出了w l f v c 算法以提高各个流在较 短时间尺度上的公平性。该算法是基于前跳虚时钟( l f v c ) 算法的全分布式的无线 调度算法，可以为不同的流在较短时间尺度上按权值分配带宽，因而有更好的时 延和抖动性能，也可以保证不同特性流间的公平性。 ( 3 ) n 提高传输控制协议( t c p ) 在w l a n 上的性能，提出了d c f + 机制。引入了 基于m a r k o v 链的分析模型以计算w l a n 的饱和吞吐量性能，并对d c f 及d c f + 进行分析和比较。建模及仿真结果表明d c f + 可以提高t c p 在w l a n 上的性能。 ( 4 ) 在多跳的a dh o c 网络中，提出了b b d c f ( b l a c kb u r s td c f ) 机制，对多跳环 境下接入算法的公平性和性能都有很大的改进，仿堇、表明b b d c f 对t c p 经历多 跳情况下的性能有较大的提高。 【关键词】互联网，服务质量控制，调度，t c p 友好，区分服务，无线局域网 韭塞堕! ! 查兰坚! 丝苎篓：! ! 竺竺一 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e ta n dw i r e l e s st e c h n o l o g y , m a n yn e wn e t w o r k s e r v i c e sb e c o m ea v a i l a b l ei nr e c e n ty e a r s t h eb e s te f f o r t ( b e ) i n t e m e ts e r v i c ec a n n o t s a t i s f y t h e r e q u i r e m e n t s f o rn e wr e a l t i m e a p p l i c a t i o n s ，a n dt h er e s e a r c h o fc o n t r o l m e c h a n i s m sa n da l g o r i t h m sf o rq u a l i t yo fs e r v i c e ( q o s ) a r et h ef o c u s t h ep e r f o r m a n c e o f t r a n s p o r tl a y e rp r o t o c o li st h ek e y i s s u e sb e c a u s eo fi t sm i d d l es t a t u si n 口p r o t o c o l s t a c k s t h e t o p i c s r e l a t e dt o q o sc o n t r o la l g o r i t h m s i nn e x t g e n e r a t i o n i n t e m e t a r c h i t e c t u r ea r ed i s c u s s e di n t h i st h e s i s f a i r n e s si s s u c si nd i f f e r e n t i a t e d s e r v i c e s n e t w o r k ，t h ep e r f o r m a n c ee n h a n c e m e n ts c h e m e si nw i r e l e s sp a c k e tn e t w o r k s ( w l a n ， a dh o cn e t w o r k s ) ，t h ea l g o r i t h m so f t r a n s p o r tl a y e r , n e t w o r kl a y e ra n dm a cl a y e r , a s w e l la st h e i ri n t e r a c t i o n s ，a r ee x a m i n e di nt h i st h e s i s t h em a i nc o n t r i b u t i o n sa r ea s f o l l o w i n g ： ( 1 ) d i r e c tc o n g e s t i o nc o n t r o ls c h e m e ( d c c s ) a n dd y n a m i c t r a f f i cc o n d i t i o n i n g ( d t c ) a r ep r o p o s e d t oa c h i e v et h ef a i m e s sb e t w e e nr e s p o n s i v ea n du n r e s p o n s i v e a g g r e g a t e s i nd i f f - s e r vn e t w o r k m o r e o v e r , b e t t e ra l l o c a t i o n sf o r r e s p o n s i v e f l o w s ( t c p ) w i t hd i f f e r e n tp a c k e tl e n g t h ，m i c r o f l o wn u m b e r ，r o u n dt r i pt i m e ( r t t ) ，c a n b e a c h i e v e db yd c c s ( 2 ) w l f v c ，w h i c hi s af u l l yd i s t r i b u t e dw i r e l e s s s c h e d u l i n gs c h e m eb a s e do n l f v c ( l e a pf o r w a r dv i r t u a lc l o c k ) ，i sp r o p o s e dt op r o v i d es t r e a m sw i t hf a i m e s s ， e s p e c i a l l yi nt h es h o r tt i m es c a l e t h i ss c h e m e i sa b l et oa l l o c a t eb a n d w i d t ht os t r e a m s p r o p o r t i o n a l t ot h e i rw e i g h t si ns h o r tt i m es c a l e t h e r e f o r e ，b e t t e r d e l a ya n dj i t t e r p e r f o r m a n c ec a l l b ea c h i e v e d m e a n w h i l e ，f a i m e s sb e t w e e ns t r e a m sw i t hd i f f e r e n t c h a r a c t e r i s t i c sc a r lb ea c h i e v e d ( 3 ) d c f + i sp r o p o s e dt oi m p r o v et h ep e r f o r m a n c eo ft c p ( t r a n s p o r tc o n t r o l p r o t o c 0 1 ) o v e rw l a n t oa n a l y z et h ep e r f o r m a n c eo fd c fa n dd c f + ，a na n a l y t i c a l m o d e li si n t r o d u c e dt oc o m p u t et h es a t u r a t e dt h r o u g h p u to fw l a n d c f + i ss h o w nt o b ea b l et o i m p r o v et h ep e r f o r m a n c eo ft c po v e rw l a n b o t hb ym o d e l i n ga n d s i m u l a t i o n s ( 4 ) b b d c f ( b l a c kb u r s td c f ) i sp r o p o s e d t o i m p r o v e t h ef a i r n e s sa n d p e r f o r r n a n c eo f i e e e8 0 2 11d c fi nw i r e l e s sm u l t i h o pn e t w o r k s i m u l a t i o nr e s u l t s s h o wt h a tt c pb e n e f i t sf r o mb b d c f g r e a t l y i nm u l t i h o pa dh o cn e t w o r k k e yw o r d s ：i n t e r n e t ，q o sc o n t r o l ，s c h e d u l i n g ，t c pf r i e n d l y , d i f f - s e r v , w l a n i i 北京邮电大学博士论文 第1 章绪论 第一章绪论 本章首先对本论文选题的原因和背景进行了总结和归纳，然后对目前国内外 在相关领域的研究动态进行了描述，主要包括服务质量体系，服务质量机制和移 动分组网的服务质量三个方面。最后介绍了本论文的研究内容和结构安排。 1 1 引言 近年来i n t e m e t 飞速发展，新的应用层出不穷。而传统的d 网络只提供尽力 而为( b e s te f f o r t ) 的业务，伴随着传输和处理能力的增强，以及多媒体业务的引入， 人们越来越期望网络能提供某种程度的服务质量( ( q u a l i t yo fs e r v i c e ) 保证。这样， i n t e m e t 中q o s 的研究成为成为国际上的热点，进而大量的文章对q o s 及其相关问 题进行了研究，包括服务质量体系，服务质量机制和算法，共享资源管理( 如带 宽分配) ，业务量调节，队列调度，以及传输控制机制等。 对服务质量的保证有很多不同的理解。对应用而言，服务质量的保证是一个 端到端的概念，涉及到整个网络的方方面面：1 ) 从工作协议的层次上来看，可以在 链路层、网络层、传输层、应用层等不同的层次来进行保证；2 ) 从实施主体上来看， 可以在终端和( 或) 网络节点上进行：3 ) 从保证的粒度上来看，可以是基于用户的、 基于汇聚流的、基于单个流的服务质量保证，也可以是定量的或者定性的服务质 量保证；4 ) 从技术的角度来看，包括框架性的服务质量保证体系结构和具体的服务 质量保证机制和算法。虽然对服务质量的保证有很多的视角，但归纳来说用户的 满意度是体现有服务质量保证的重要标准，为此，国内外的学者们在各个方面进 行了大量的研究和探索。许多专门的工作组也应运而生，也有很多的标准和草案 问世。 美国在这方面的投入较大，为了解决在i n t e m e t 上多种业务的q o s 保障，美国 在1 9 9 6 年成立了以提高互联网服务质量为核心的i n t e m e ti i 以及n g i 研究机构， 意在提供高速宽带，满足多种业务需求的下一代i n t e m e t 解决方案。i e t f ( i n t e m e t 北京邮电大学博士论文 销i 章绪论 e n g i n e e r i n g t a s kf o r c e ) t g 成立y # f 的工作小组，以提供互联网的服务质量定义 及相关标准。 目前，t c p i p 协议是i n t e m e t 的通信基础。在i n t e m e t 上提供真正的q o s ，须 在完善的q o s 策略基础上，建立完整的服务质量体系结构，研发具有q o s 保证的 通信协议，提供流量控制、路由选择、差错控制以及安全机制等关键技术。区分 服务( 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 ) 的网络体系是i e t f 在综合服务 ( i n t e g r a t e ds e r v i c e s ，简称i n t e s e r v ) 之后又成立的工作组，该体系主要的切入点 是针对i n t e 一$ e r v 里的扩展性不好的问题，采用了服务质量等级的方案。由于区分 服务体系尚不完善，存在很多问题，其中流或汇聚流之间的公平性问题，尤其是 响应流( 如t c p ) 和非响应流之间( 比如缺少流控的u d p ) 的公平性问题，是研 究的热点之一。 对于响应流和非响应流的公平性问题的解决方案很多，一个最简单的想法就 是区分流的性质并采用不同的控制机制。实际上，对不同需求的业务采用不同的 控制机制是提高服务质量的一类保障技术。相关的机制可以包括对网络节点的资 源管理机制如队列调度、缓冲区管理、资源预留协议，以及各种流量控制技术如 接入控制、发送速率控制、反馈信息控制、业务量整形等等。而其中的缓存管理 和队列调度机制，对q o s 保证具有重要意义，对这方面的研究是一直以来难点和 重点。 互联网本身是从有线连接方式的计算机网发展壮大而来的，但是随着互联网 应用的日益丰富，移动互联网的发展也逐渐成为下一代互联网的发展方向。随着 无线及移动通信技术和互联网的日益成熟，人们希望移动终端能以更高的速率接 入有线的骨干网络。同有线以太网相比，无线局域网w l a n 为用户提供了更加方 便快捷的接入方式，而且随着技术的成熟和标准的完善，w l a n 所能提供的接入 速率从1 m b p s 提高到几十兆。i e e e 为w l a n 制订了相应的国际标准8 0 2 1 1 ，该 标准主要定义了w l a n 的物理层和m a c 的协议内容，包括物理层的编码和解码， 调制和解调方式，占用的频带，以及m a c 层的工作方式，等等。与有线环境下的 媒体相比，在w l a n 中的无线物理媒体有很大的不同，因为此时信道是被有限距 离下的站点所共享。由于无线环境下特有的隐藏终端、捕获效应等因素的影响， ! 堕塑皇查兰丝主丝兰 一 墨上要! ! 兰l w l a n 中的m a c 协议设计需要考虑的因素更多，因此无线局域网中m a c 层协议 的设计比有线环境下更为复杂。 随着w l a n 的广泛使用，在w l a n 中研究q o s 成为整个q o s 体系中网络接 入侧的一个重要组成部分。在w l a n 这种特殊的环境下，m a c 层的协议性能对 服务质量的提供有举足轻重的影响。研究m a c 层协议对上层，包括口层和t c p 层的性能的提高有现实的应用意义。并且，从底层为高层提供性能改进的方案更 符合从分层的角度解决问题的思想，因为这个时候引起性能劣化的原因是无线信 道的特殊情况造成的，而协议的工作方式对获得的性能有很大的影响。另外， w l a n 中真正量化的q o s 保证机制仍然依赖于m a c 层协议的工作方式与队列调 度算法的结合，雨其性能仍然有待分析。个适合于w l a n 的分布式调度算法是 一直以来的研究热点。 除此之外，作为对w l a n 的扩展，无线自组织网( a dh o cn e t w o r k ) 方面的研 究也越来越受到重视。用a dh o e 网接入骨干网是对w l a n 这种类似于小区式的接 入方式的一个自然扩展，因此研究a dh o e 网络的性能将有助于未来提供全网端到 端的q o s 保证体系的实现。一个多跳豹移动无线自组织网络( m a n e t ) 中的节点 通过多跳的无线链路同其他节点互联，这种形式的网络在军事、医疗，救援等方 面的实际应用有重大意义。i e t f 也为m a n e t 成立了专门的工作组。而考察t c p 在m a n e t 上的性能，对其分析与提高，这对于m a n e t 的实际应用，将起到至 关重要的影响。 综上，本论文认为未来的q o s 保证机制和算法的研究将涉及到i n t e r n e i 各个层 面，并且在网络接入，网络核心等位置将用到不同的机制和算法。对核心网络的 q o s 问题的研究。本文选取了区分服务的网络体系，并主要考察了公平性以及网 络效率的问题；对网络接入侧的q o s 问题，本文考察了近年来研究较热的无线局 域网w l a n ，并主要考察了w l a n 中的分布式调度算法的改进，w l a n 中传输 协议的性能提高几个方面：最后本文将研究的领域扩展到多跳a dh o c 网络，主要 分析了在a dh o e 网络中有待解决的问题以及性能提高的机制。下面，本文将就目 前国内外在相关领域的发展进行简要的综述，并对本文所涉及到的一些基本框架 和概念进行简要的介绍。 北京邮屯大学博士论文 第1 章绪论 1 2 国内外发展动态 1 2 1 服务质量保证体系 对服务质量的研究是在对b i s d n 网络的异步传输模式( a t m ) 的研究中成 为热点的。b i s d n 的目标是要用一个网络实现现有以及未来可能出现的各种电信 业务，包括从几k b p s 的数据业务，几十k b p s 的话音业务到上百兆的图像和高速数 据业务。按照a t m 论坛的建议，a t m 可提供5 种业务类型：恒定比特速率( c b r ) 、 非实时可变比特速率( r a t v b r ) 、实时可交比特速率( r t v b r ) 、可用比特速率 ( a b r ) 、未确定比特速率( u b r ) ，每一种业务类型都对应着一系列具有相同需 求和特性的典型应用。在a t m 的服务质量保障模型中首先为每种业务类型定义了 描述其连接特性的流量参数和q o s 参数，并通过连接接纳控制( c a c ) 、用户参数 控制( u p c ) 、优先级控制( p c ) 、业务量整形( t s ) 和明确的前向拥塞指示( e f c i ) 等一系列流量管理机制，来为用户提供所需要的服务质量等级。 与a t m 相比，传统的i n t e m e t 只能提供尽力而为的服务质量，也就是说只能 按照网络的能力来为用户提供业务，实际上是没有保障的q o s 。随着互联网的发 展，各种实时业务和高质量业务不断增加，如视频会议、视频点播、网络检索等， 网络资源短缺情况已经越来越明显，网络应用的质量也不够理想，互联网用户不 约而同的把眼光投向了a t m 技术所能提供的服务质量保障机制。但由于传统互联 网的t c p i p 技术已经深入桌面的各项应用，研究人员开始对基于t c p i p 的互联 网提出了q o s 的要求，希望通过相应的机制改进来合理利用网络系统的有限资源， 满足不同应用对质量的不同需求，由此，众多研究机构和标准化组织为基于t c p i p 的互联网提出了多种保障服务质量的体系结构，包括综合服务( i n t e 。s e r v ) ，区分服 务( d i f f - s e r v ) 等。 综合服务体系模型 综合服务体系是i e t f 支持的第一个保障每个流q o s 的业务模型，它的部分动 机来源于m b o n e 的分布式会议实验和在9 0 年代初期的i e t f 会议的广播实验。根 据砸t f 的建议，综合服务网络提供三种q o s 类型：质量确保( g u a r a n t e e dq u a l i t y ) 北京邮电大学博士论文 第1 章绪论 服务，受控负载( c o n t r o l l e d l o a d ) 服务和尽力而为( b e s t - e f f o r t ) 服务。 综合服务体系与传统互联网结构的最大区别在于提供了建立“会话”的信令 过程一资源预留协议( r s v p ) ，信令的交互可以在网络路由中为每个“会话”建 立并动态维护资源预留状态，通过这种资源的预留，保障不同类型服务的质量。 与a t m 机制类似的是，综合服务体系也对不同服务所需资源、会话类型、数据分 组的格式和流量特性等参数进行了描述，并通过网络节点中的分类器、分组调度 器和接纳控制等一系列流量管理机制来保障不同的服务质量要求的。目前，综合 服务体系已经在几个国家的网络中进行了实验，尤其是它的资源预留协议r s v p 已经在多种厂商的路由器和交换机设备中获得实现。 区分服务体系模型 由于综合服务体系需要r s v p 这样复杂的信令系统，给网络增加了巨大的开 销，实现的复杂度也比较大，扩展性差，因此，i e t f 又提出了区分服务体系的模 型。区分服务体系模型与综合服务体系模型相比，具有简单、易于实现、与其它 服务质量保障技术相互兼容等众多优势。它将具有相同或相近质量需求的服务划 分到同一服务类中，用同样的区分服务编码点( d s c p ) 值来标识，并对每种服务 类采用相同的p i - - i b ( p e r h o p b e h a v i o r ) 。根据i e t f 的建议，区分服务体系模型提 供三种标准的p h b 组：快速转发方式组( e f ) ，确保转发方式组( a f ) 和缺省转 发方式组。 在区分服务体系结构中，多个相互连接并基于相同网络策略和p h b 类型的路 由器组成的子网称为d i f f s e r v 子网区域。这些路由器可分为边缘路由器和内部路由 器两种，同时边缘路由器又可根据业务流的流向分为流入路由器和流出路由器。 区分服务网络的主要控制和管理功能都在流入路由器中实现，包括d s c p 值的标 识和重标识、p h b 转发的映射、流量调节等。在各种服务质量体系的方案中，有 关服务质量的控制机制和算法是研究的热点，下面将讨论相关的机制和算法。 1 2 2 服务质量控制机制和算法 在上面提到的各种服务质量体系中，流量管理或流量控制机制是实现q o s 保 北京邮电大学博士论文 第1 章绪论 障必不可少的功能模块，并在不同的体系模型中起到了不同的控制作用。从实现 的协议的层次来看，这些功能一部分由网络层的服务质量控制机制来提供，另一 部分由传输层的控制机制来提供。下面我们就从这两方面简要的介绍一下目前的 研究成果。 网络层的控制机制 最初在a t m 模型中，拥塞控制机制的主要作用是保护网络和用户以实现预先 规定的网络性能。概括的说，拥塞控制是指网络为了避免拥塞，同时优化网络资 源的使用以取得较好的网络效率所采取的一系列操作。a t m 的拥塞控制功能包括 连接接纳控制，用户网络参数控制，优先级控制、业务量整形等机制。连接接纳 控制是在呼叫建立阶段网络所执行的一组操作，用于接受或拒绝一个a t m 连接； 用户网络参数控制在信元流量大小和信元选路的有效性等方面监视和控制a t m 连接的流量：优先级控制在a t m 网络中产生不同优先级的业务流量，当网络资源 不够时，一些低优先级的信元会先被丢弃；业务量整形能改变信元流的业务量特 性，以使得业务流穿过用户网络接口( u n i ) 时与用户要求的流量特性保持一致。 在i p q o s 体系中，综合服务与区分服务对q o s 的控制有不同的体系和机制， 但在思想上与a t m 中的q o s 控制有很多相似之处。例如在i e t f 的r f c l 6 3 3 建议 中，综合服务体系模型的参考实现机制主要包括四个组成部分：分组调度器、分 类器、接纳控制和预留建立协议。 在区分服务体系结构中，流量控制功能作用于d i f f s e r v 子网边缘，对流入或流 出的应用流进行调整，它可以看作是边缘路由器中的一个流量调节器。流量调节 器又包含计量器( m e t e r ) 、标记器( m a r k e r ) 、整形器( s h a p e r ) 和丢包器( d r o p p e r ) 等功能部件。流量调节器的结构如图l 一1 所示： j ! 室些皇查堂苎主兰苎 一蔓l 兰! i 兰l 图1 1 边缘路由器功能的逻辑结构图 在边缘路由器中，数据包先经过分类器判断服务的类型，以确定流量调节器 采用哪种类型的流量规范进行调节。计量器根据这种流量规范计量应用流的流量 特性，并判断数据包是满足还是超出了规范。根据判断结果，标记器、整形器和 丢包器i ；采用相应的策略处理这个数据包。按照计量器的判断结果，标记器可以 为数据包设置相应于其服务类型的d s c p 值，并将标识后的数据包归到特定的一 种p h b 转发集合中。整形器通过延时一个或多个数据包来调整流，使之与流量规 范致。整形器中的缓冲区通常为有限容量，如果延时的流量超过了缓冲区容量， 丢包器将按照一定策略丢弃一些数据包。 不论是在综合服务还是区分服务体系中，网络层q o s 的控制都必须依靠相应 的缓存管理机制和队列调度算法。不同的地方在于，在综合服务的网络中调度是 针对不同的微留进行的，而由于区分服务网络中引入了d h c p 来表示分组的类别， 调度时是针对不同的分组类别两不是分组所属的微流。低复杂度高性能的队列调 度算法是一直以来的国际上研究的热点和难点。 根据不同的服务规则，队列调度算法可以分为以下几种：先到先服务、循环 调度、处理机共享、优先级服务、随机服务等。根据调度算法的调度目标，也可 一 分为基于时延的和基于速率的这两类。根据通信网络环境，又可分为无线环境下 的队列调度和有线环境下的队列调度。根据调度算法的工作状态，又可以分为工 作保持( w 硼d i l g c o n s e r v i n 曲和非工作保持( n o n w o r k i n g c o n s e r v i n g ) 。其中工作保持 算法表示只要系统中有等待分组，调度算法就一定会工作；雨非工作保持算法则 意味着即使系统中有等待分组，调度算法也可能暂时不对其进行调度，这类调度 算法一般要求在输入业务流被调度之前需经过一个整形器进行整形处理。工作保 ! ! 室坚皇奎堂竖主堕兰壁上童! i ! l 持算法具有更高的链路利用率，而非工作保持算法能对端到端时延及时延抖动进 行很好的控制。 实际上，对于某一特定的调度算法，根据不同的分类标准，它可能属于多个 不同的类，所以并没有一种统一的分类标准。根据调度算法的服务规则、调度目 标及其发展趋势，同时为了能更清晰地说明各类算法之间的区别，我们把目前已 出现的队列调度算法大致分为如下五类：基于轮循的调度算法、基于优先级的调 度、基于通用处理机共享( g p s ) 的算法、基于时延的调度算法、基于服务曲线( s e r v i c e c u r v e ) 的算法等。 评价队列调度算法性能的好坏主要涉及到时延性能、公平性、复杂性这三个 方面。队列调度算法可能在不同环境下有不同的应用。例如，队列调度算法可能 被用于隔离恶意业务流来为正常业务流提供服务质量保证；队列调度算法还可能 用来让用户平等的分享链路的可用带宽；或者用来实现分级的链路共享等。实际 上，有效的队列调度算法应该拥有诸多好的特性，即下面要讨论的队列调度算法 应达到的主要性能指标。 时延性能：队列调度算法应为不同的业务流提供端到端的时延保证，而且只 与此业务流的某些参数( 如带宽需求等) 有关，丽与其他的业务流无关。s f i l i a d i s 和v a r m a 首先提出了一种分析网络中不同队列调度算法带来的端到端时延的模型： 时延速率调度器( l r s ：l a t e n c y - r a t es e r v e r ) 。c h i u s s i 随后又提出了另种分析端 到端时延的模型：速率分隔时签调度器( r s t ：r a t e s p a c e d t i m e s t a m ps c h e d u l e r ) ， 此模型的限制条件比l r s 要少且在定长分组环境下应用时更加有效。在本论文中 主要通过仿真考察算法的性能。 公平性：可用的链路带宽必须以公平的方式分配给共享此链路的各业务流； 此外队列调度算法必须能够隔离不同的业务流，让不同的流只能获取自己应该享 用的带宽，这样即使存在恶意或高突发性业务，它也不致影响到其他的正常业务 流。一个不公平的调度算法可能会在一较短的时间间隔里给预约了相同带宽的两 个业务分配不同的服务速率。关于算法公平性的定义有：服务公平指数( s f i ：s e r v i c e f a i m e s si n d e x ) 和最坏公平指数( w f hw o r s t c a s ef a i r n e s si n d e x ) 两种。s f i 表示任意 两个活动队列在任意时间间隔内受到的归一化服务量( 等于服务量与其分配的服务 北京邮电大学博士论文 第1 章绪论 速率的比值) 的最大差值；w f i 用来表示一个队列在分组级系统和相应流系统上接 受到的服务量的最大差值，较大的w f i 意味着该调度算法输出业务量有较大的突 发性。 复杂性和可扩展性：调度算法实现起来必须比较简单。在高速网络中，传输 一个分组的时间很小，所以调度算法必须在短时间里完成对分组的调度，这就要 求调度算法尽量简单，易于实现。另外当业务流数量增加和链路速率变化范围较 大时，调度算法仍应有效工作；这要求调度算法应该具有良好的可扩展性。 传输层控制功能 在传统的互联网中通常采用t c p i p 四层结构的协议栈，从上往下分别为： 应用层、传输层、网间网层、网络接口层。其中，应用层向用户提供常用的应用 程序，比如文件传输，远程登录，e m a i l 等；传输层也就是t c p 层，提供端到端 的可靠的信息流传输功能，这些流通过格式化的带有源端、目的端地址、序号等 信息的数据包来进行传输，并由目的端返回的确认完成完整的传输过程；网间网 层也就是口层，提供非连接的数据包传送功能，具有寻路和转发的能力：网络接 口层是t c p i p 协议栈的最底层，负责从网络上接收物理帧，解封其中的d 数据包 发到口层，或者从p 层取到数据包，通过封装后发送到网络上。 由于p 层以下的网络部分是基于无连接和不可靠的传送方式，那么互联网中 的服务质量保障与传输层有着密切的联系。从概念上说，传输层在网络分层结构 中起着承上启下的作用，无论下层网络提供什么样的服务，传输层都可以对其加 以屏蔽，将下层网络采用的技术、设计和各种不尽人意的地方与应用层隔离开来， 提供尽可能多的保障。因此，t c p 协议在设计的过程中就增加了许多复杂的流量 控制和拥塞控制机制。如果使用u d p 这样的非可靠传输协议，流控和拥塞控制的 功能就要由应用来完成。 网络性能和服务质量的降低在很大程度上是因为网络的拥塞，尤其是越来越 严重的拥塞崩溃现象。针对这些问题，t c p 协议从t a h o e 版本开始就具有最经典 的拥塞控制机制一慢启动机制，这种控制机制采用的是窗口滑动的拥塞控制原理， 使得t c p 可以限制源端向网络中发送的数据包的速率，减轻给网络增加的负载， 韭塞坚皇奎堂堡主堡兰 塑堕! ! ! l 降低拥塞程度。 在最早的面向连接的传输过程中，通常采用简单停等协议。简单停等协议就 是源端每发送一个数据包都需要得到目的端的确认，只有收到上一个包的确认， 才会发下一个包，但这种拚议的最大问题是效率太低，网络资源没有被充分利用。 滑动窗口技术是在简单停等协议基础上的一个变形，它允许源端在等待一个确认 信息之前可以发送多个包。对滑动窗口操作的最简单设想就是一个传输包的序号 的序列，然后在序列上放置一个可以滑动的窗口，窗口内序号对应的数据包是允 许发送的。 当然，以上的情况是在网络资源充分，没有拥塞的条件下窗口的正常变化过 程，如果网络发生拥塞使t c p 的数据包延时较长时间或丢失，t c p 的源端就会根 据不同的情况采取不同的方式来调整流量，达到缓解拥塞的目的。 传输层协议的性能对应用的性能有极大的影响，而目前在i n t e r n c t 中使用最 广的传输协议是可靠传输协议t ( p 和非可靠传输协议u d p ，考察t c p 和u d p 之 间的相互影响，以及t c p 协议在各种环境尤其是无线或移动网络中的性能，是近 来的研究热点。另外，由于无线分组网络较有线网络有其特有的问题，其中m a c 层和网络层以及传输层的相互作用对整体性能有很大的影响，而本论文将考察在 w l a n 和a dh o c 网络这样的环境中m a c 的协议对服务质量，包括性能和公平性 等方面改进的机制和算法。 1 2 3 无线局域网( w l a n ) 与多跳的移动无线自组织网 i n t e r a c t 和移动通信，作为迈向信息社会的两个重要标志，分别对应着对大 量信息资源的有效访问和随处漫游的个人通信。目前，随着移动手机和智能化移 动终端的实现，已使得越来越多的用户习惯于移动通信的方式，同时也期望能够 更加灵活地、不受任何限制地进行通信和接入到i n t e r a c t 网。各运营商、制造商和 内容提供商都非常积极地工作，先后推出了无线应用协议( w a p ) 、移动d 、蓝 牙( b l u e t o o t h ) 以及无线局域网( w l a n ) 等解决方案及相关的产品【4 2 】。 w a p 技术【4 3 】是在数字移动电话、因特网或其他个人数字助理机( p d a ) 、 北京邮电大学博士论文 第1 章绪论 计算机应用之间进行通讯的开放全球标准。它是由一系列协议组成，用来标准化 无线通信设备，可用于i n t e m e t 访问，包括收发电子邮件，访问w a p 网站上的页 面等等：移动口技术 4 4 4 6 通过在网络层改变i p 协议，从而实现移动计算机在 i n t e r n e t 中的无缝漫游；b l u e t o o t h 4 7 4 8 是由爱立信、i b m 、诺基亚、英特尔和东 芝共同推出的一项短程无线电技术标准，旨在取消有线连接，实现数字设备间的 无线互联，以便确保包括蜂窝电话、掌上电脑、笔记本电脑、相关外设和家庭h u b 等众多设备之间进行信息交换；无线局域g 目 4 9 5 0 采用i e e e8 0 2 1 l 系列协议，以 无线信道作传输媒介组建的计算机局域网络，是在有线网的基础上发展起来的， 使网上的计算机具有可移动性，能快速、方便地解决有线方式不易实现的网络信 道的连通问题。 在无线分组网络中，由于分组在媒体接入控制层( m a c ) 的传送受到无线误 码，站点移动，以及多址接入时分组间的碰撞等多方面的影响。无线网络中m a c 层所能提供的服务质量较有线网络有很大的劣化。但随着w l a n 等接入方式的广 泛使用，研究如何提高无线信道链路层的服务质量控制，这对于网络层乃至传输 层所提供的服务质量有极大的影响，对于全网端到端q o s 的提供有重要的意义。 图l - 2 隐藏终端与暴露终端 在w l a n 中，尤其是在多跳a dh o c 网络中，隐藏终端与暴露终端对整个网 络的性能有很大的劣化。隐藏终端与暴露终端可以用图1 2 来解释，其中a 为分 组发送站点，b 为分组接受节点，图中的实线和虚线所表示的圆分别为发送节点a 和接受节点b 的发射范围，即能正确的接受到a 和b 所发送的分组的范围。本论 文中假定各个站点均按相同的功率工作，并且站点能正确接收分组的范围和进行 载波监听的范围相同。 隐藏终端是指在接收节点的范围内，但是在发送节点的范围之外的节点。如 - l l - 北京邮电大学博士论文 第1 章绪论 图1 2 中所示，节点h 不能听到节点a 发往节点b 的分组，因此在a 向b 的发送 过程中，节点h 会认为信道空闲。如果此时节点h 发送了分组，则对节点b 的接 受产生了干扰，此时，称节点h 为节点a 的隐藏终端。显然隐藏终端的存在会导 致分组的碰撞，使得性能劣化。 暴露终端与隐藏终端相反，是指在发送节点范围之内，但是在接受节点范围 之外的站点。如图1 2 中节点e 可以听到节点a 发往节点b 的分组，但此时节点 e 的发送并不会对a 对b 的分组发送产生干扰，此时节点e 为节点a 的暴露终端。 暴露终端的存在会使得网络的利用率下降。 8 0 2 1 1 中r t s c t s 握手机制的引入可以解决部分隐藏终端的问题，但在多跳 环境下，仍然存在信道接入时不公平的问题。并且，最近的研究表明，即使在不 考虑站点移动性的情况下，由于分组接入时的碰撞也会对整体性能带来很大的劣 化，使得像t c p 这样的协议在经历多跳的无线链路时会有较大的劣化，即使只有 一个连接，该连接发送的多个分组之间在信道接入时也会互相干扰，导致该连接 性能劣化。 1 3 本文的主要贡献 对服务质量控制机制和算法的研究涉及的内容是网络中的方方面面，本论文 研究的侧重点放在传输层，网络层和m a c 层的相关协议和算法。由于各个层间性 能的相关性，实际研究的算法也是涉及到两个或两个以上的层次及其相互影响。 本文从i e t f 已有多个r f c 的区分服务网络体系入手研究传输层和网络层的服务 质量算法，然后针对w l a n 环境中的m a c 协议考察了服务质量以及t c p 的性能， 最后研究了多跳无线网络中m a c 协议对传输协议性能的提高机制。因此，本文的 贡献可以归纳为以下几个方面： 夺针对综合服务( i n t e s e r v ) 体系在实现中的可扩展问题，i e t f 为实现i n t e m e t 服务质量而定义了区分服务的体系结构。然而，该体系为减小开销，不使 用资源预留及微流状态记录，在响应流与非响应流之间以及不同参数的响 应流之间，都存在严重的不公平问题。本文提出了一种直接拥塞反馈机制 ( d c c s ) ，配合网络边缘的动态流量调节( d t c ) 算法，能够为该体系提供很 1 2 北京邮电大学博士论文 第1 章绪论 好的公平性。该机制不仅能保证响应流与非响应流之间的公平性，而且能 解决响应流( 如t c p ) 自身由于分组长度，微流数目及环回时延( i 玎t ) 等因 素而产生的差异 夺i e e e8 0 2 1 l m a c 被用于支持无线局域网( w l a n ) 中的分组传输。分布 式协调功能( d c f ) 是i e e e8 0 2 1 1 的m a c 协议的基本方式，但该方式 在较短时间尺度的公平性不好。本文提出了w l f v c 以提供流之间的短期 公平性，该机制是基于前跳虚时钟( l f v c ) 算法的全分布式的无线调度机 制，可以为流在较短时间尺度上按权值分配带宽。因此，可以取得更好的 时延和抖动性能，也可以保证不同特性流间的公平性。由于无线分组间的 碰撞和无线链路误码劣化了m a c 协议在w l a n 中的性能，w l f v c 在设 计时也将其补偿策略考虑在内。 夺可靠传输协议t c p 是目前i n t e m e t 中应用最广泛的协议，而无线局域网是 近来的高速无线接入方式。为提高传输控制协议( t c p ) 在w l a n 上的性 能，本文提出了d c f + 。为对d c f 及d c f + 进行分析，本文引入了分析模 型以计算w l a n 的吞吐量性能。建模及仿真结果表明本文提出的d c f + 可以提高t c p 在w l a n 上的性能。 夺作为无线局域网的协议标准，i e e e8 0 2 1 1 的m a c 协议d c f 在多跳的无 线a dh o c 试验网以及仿真中被广泛的试用。在d c f 中针对隐藏终端设计 的r t s c t s 工作方式尚不能完全的解决无线局域网中的隐藏终端问题， 而这一问题在多跳的a dh o c 网络中将变得更为复杂，将引发公平性和性能 方面的一系列问题。本章提出的b b d c f ( b l a c k b u r s td c f ) 机制对多跳环境 下的d c f 的公平性和性能都有很大的改进，仿真表明b b d c f 对t c p 经 历多跳情况下的性能将有很大程度的提高。 1 4 本文的结构和安排 本文的剩余部分内容安排如下： 第二章主要探讨了区分服务网络中的公平性问题及其解决方案。首先简要描 北京邮电大学博士论文 第1 章绪论 述区分服务网络中a f 的性能问题与公平性问题，并分析了目前的算法为什么不能 很好的解决该问题；然后提出一种直接拥塞反馈机制和动态流量调节的算法相互 配合。最后用仿真的方法验证了该机制在提高公平性的同时，优化了网络资源的 利用率。 第三章主要的研究内容是无线局域网中的分布式调度算法。首先简要介绍了 i e e e8 0 2