（通信与信息系统专业论文）无线网络拥塞控制及分组调度策略的研究.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律责任由本人承担。 论文作者签名：囱盘缸 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校 保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保 存论文和汇编本学位论文。 f 保密论文在解密后应遵守此规定、 论文作者签名：白查鱼导师签名：兰隧日期：丝! 兰：兰：) z 山东大学硕士学位论文 摘要 未来的无线通信具有支持从话音到多媒体( 特别是i n t e r n e t ) 业务的能力。用户可以通过无线 局域网( w l a n ) ，也可以通过3 g 等无线网络接入到有线i n t e m e t 中并且可以在任何时间和地点 访问i n t e m e t 服务。无线网络有自身的特点：( 1 ) 无线链路存在衰落效应，分组的差错率将比有线 网络高，( 2 ) 某段时间某个地点无线信道不可用，这就是位置相关错误( l d e ) 。这两个特点对t c p 拥塞控制和网络的队列调度有重要的影响。这就要求新技术来保证无线用户在访问i n t e m e t 时的服 务质量( q o s ) 。本论文的主要研究无线网络的两个特点对t c p 拥塞控制和队列调度的影响及改进 措施。 本论文主要包括三个方面：( 1 ) 无线网络中，主机上t c p 端到端的拥塞控制性能：( 2 ) 无线 网络中接入点( 或基站) 的队列调度算法：( 3 ) 开发一个实际应用系统。在无线同域网( w l a n ) 环境f ，采用s o c k e tr t p r t c p 协议，m p e g 4 视频压缩编码，j p 多播技术来完成实时的多媒体通 信。 本文的创新性工作体现在以下几个方面： 首先，对i n t e m e t 的最重要协议之一传输控制协议t c p 的拥塞控制性能进行较深入研究： 对不同版本的t c p 进行仿真，并比较其各自性能。后又结合无线网络高错误率的特点针对目前 广1 泛使用的r e n ot c p 性能的不足，给出我们的解决方案v e g a st c p ( 一个尚未被广泛应用的 t c p 版本) 。对v e g a s 进行了改进使其能更适合无线环境，为检验所傲改进用n s - 2 进行了仿真， 实验结果证明这些改进是正确和有效的。用数学分析和仿真相结合的方法，给出了v e g a s 虽然性能 远远优于r e n o ，却没有被广泛应用的原因：与r e n o 相对激进的行为相比。v e g a s 是保守的；进两 导致二者共存时得不到公平的带宽分配。我们对v e g a s 做了改进，使其能够与r e n o 竞争带宽，以 便将来得到广泛应用。 其次，分析并比较现有的各种调度算法的延迟性能，公平性和复杂性得出w f 2 q + 在所有逼 近g p s 的分组算法中具有最好的性能，复杂性也相对较低。我们发现w f 2 q + 本身的一种潜在的对 滞后会话的补偿能力。在已有的各种无线调度算法，如c i f q i w f q 等都引入了某些补偿措施( 有 的文献中称为时隙交换本质是相同的) 。研究证明w f 2 q + 本身的补偿措施对无线多媒体应用来 说是不够的。针对无线信道l d e 错误论文利用w f 2 q + 的g b t 性质定量分析了无线分组网络 中经历了信道错误的会话领先和滞后的状况( 包括是领先还是滞后，领先，滞后服务量为多少) 。通 过设置领先和滞后门限。丢弃过度滞后的会话分组。这对多媒体传输来说是合理的。注意到先前 经历信道错误的会话，在信道恢复后会垄断调度器。造成其他非滞后会话的延迟和延迟抖动的增 大，论文采用让滞后会话适当为非滞后会话让出部分服务量的方法在滞后会话的补偿与菲滞后 会话延迟性能之间达到平衡。 最后，实现了一个无线局域网多媒体传输系统。采用m p e g 4 压缩编码和i p 多插技术传输实 时的多媒体信息，接收端加入多播组接收视频。整个系统使用v c + + 实现。 关键字；无线网络，t c p 拥塞控制队列调度，服务质量 3 a b s t r a c t i nt i l ef u t u r e ，t h ew i r e l e s st e l e c o m m u n i c a t i o ns y s t e m sw i l lp r o v i d es e r v i c et h a te v o l v e sf r o mv o i c et o d i g i t a lm u l t i m e d i a ( e s p e c i a l l yi n t e m e t ) u s e rc a nv i s i tt h e i n t e r n e tt h r o u g hw i r e l e s sl a n ( w l a n ) o r 3 g m o b i l es y s t e m b u tb e c a u s eo f t h ec h a r a c t e ro fw i r e l e s sn e t w o r k ，w i r e l e s sl i n kw a sa f f e c t e db yf a d i n g ，t h e e r r o rr a t eo fp a c k e t sw i l lb e h i g h e rt h a n w i r e dn e t w o r k t r a d i t i o n a li n t e m e tp r o t o c o la n dc o n t r o l a l g o r i t h mc a nn o tb eu s e dd i r e c t l yt ow i r e l e s sn e t w o r k i tw i l ln e e dm o r ea n dm o r en e w e rt e c h n i q u e st o e n s u r et h a tw i r e l e s su s e r sh a v et h es a m eq u a l i t yo fs e r v i c el i k ew i r eu s e t s t h em a i nr e s e a r c ho b j e c ti n t h i sd i s s e r t a t i o ni st op r o v i d ew i r e l e s sm u l t i m e d i aq u a l i t yo fs e r v i c ei nw i r e l e s sa c c e s si n t e r n e t t h em a i n r e s e a r c ha s p e c to ft h i sd i s s e r t a t i o ni s c o n g e s t i o nc o n t r o ls c h e m ea n dq u e u i n gs c h e d u l i n ga l g o r i t h m i n w i r e l e s sn e t w o r k t h et h e s i si so n ep a r to ft h er e s e a r c hr e s u l t so ft h es h a n d o n gp r o v i n c ee x c e l l e n ty o u n gs c i e n t i s t a w a r df u n d s ( n o 0 1 b s 0 4 ) i ti n c l u d e s3p a r t s ( 1 ) t h et c pe n d - t o - e n dc o n g e s t i o nc o n t r o ls c h e m ei nt h e h o s l ：( 2 ) q u e u es c h e d u l i n ga l g o r i t h mi nt h er o u t e ro rt h ea c c e s sp o i n t ；( 3 ) a ni pm u l t i c a s ts y s t e mu s i n g m p e g 4i nw l a n t h es o l v e dk e yi s s u e sa n dt h em a i nc o n t r i b u t i o n si nt h i sp a p e ra r eg i v e na sb e l o w ： f i r s t ，w ea n a l y z et h ep e r f o r m a n c eo f t c po v e rw i r e l e s sl i n k b a s e do ns t u d yo f t h ec o n g e s t i o nc o n t r o l o ft h e p o p u l a rr e n ot c p ( b e r k e l e yd i s t r i b u t i o n ) ，t h ec h a r a c t e ro fw i r e l e s sn e t w o r ka n dt h ep r e v i o u s a c h i e v e m e n t si nw i r e l e s sc o n g e s t i o nc o n t r o l ，w ei n t r o d u c ear e s o l u t i o n - v e g a s - ag o o db u tn o n p o p u l a r t c p w em o d i f yt h ev e g a ss ot h a ti tc a l lb ea d a p t e dt ot h ew i r e l e s sn e t w o r k b y f o c u s i n go n t h es i t u a t i o n w h e r e 丁c pr e n oa n dv e g a sc o n n e c t i o n ss h a r et h eb o t t l e n e c kl i n k w ei n v e s t i g a t et h ef a i r n e s sb e t w e e n t h e s et w ov e r s i o n s f r o mt h ea n a l y s i sa n dt h es i m u l a t i o nr e s u l t s ，w ef i n dt h a tt h ep e r f o r m a n c eo ft c p v e g a si sm u c h s m a l l e rt h a nt h a to fr e n o w ea d j u s tt h ev e g a s sr o b u s t n e s st oc o m p e t ew i t hr e n o t h e r e s u l t so f a n a l y t i ca n ds i m u l a t i o nv a l i d a t et h em e c h a n i s m sa n d a l g o r i t h m sp r o p o s e di nt h i sp a p e r s e c o n d ，a so n eo fn e t w o r kr e s o u r c ea l l o c a t i o nk e yt e c h n o l o g i e s ，q u e u es c h e d u l i n gi so f t e nu s e dt o a l l o c a t et h el i n kb a n d w i d t h b u tt h ec o n v e n t i o n a ls c h e d u l i n ga l g o r i t h m sd e v e l o p e df o rw i r e dn e t w o r k s c a n n o tb ed i r e c t l ya p p l i e dt ow i r e l e s sn e t w o r k , b e c a u s eo fb u r s ta n d l o c a t i o n d e p e n d e n te r r o r si nw i r e l e s s c h a n n e l s t h ec o m p a r i s o no fs o m ep a c k e t a p p r o x i m a t i o na l g o r i t h m so fg p si nd e l a y , f a i r n e s sa n d c o m p l e x i t ys h o w s t h a tw f 2 q + h a st h et i g h t e s tp e rs e s s i o nd e l a yb o u n d sa n dr e l a t i v e l yl o w c o m p l e x i t y t h ei n h e r e c o m p e n s a t i o nt e c h n i q u eo fw f 2 q + i si m p o r t a n tf o rw i r e l e s sn e t w o r k w eu s et h et i g h t g l o b a l l yb o u n d e dt i m e s t a m p ( g b t ) t od e t e c tl e a d i n ga n dl a g g i n gs t a t u so f e a c hs e s s i o n w er e f l e c tt w o w i r e l e s ss c h e d u l i n gi s s u e st oo u r s c h e d u l n gf r a m e w o r k ：d e g r a d a t i o na n dr e a d j u s t i n g ， f i n a l l y , w ed e v e l o pam u l t i c a s ts y s t e mi nw l a n i tc o d e d e c o d et h em u l t i m e d i am e s s a g eu s i n gt h e m p e g 4j nt h ee n dh o s t ， k e y w o r d s ：w i r e l e s sn e t w o r k ，t c p c o n g e s t i o nc o n t r o l ，q u e u es c h e d u l i n g , q o s 4 山东大学硕士学位论文 符号说明 w l a n - w i r e l e s sl o c a la r e an e t w o r k 无线局域网 q o s q u a l i t yo fs e r v i c e 服务质量 r e d - r a n d o m e a r l yd e t e c t i o n 随机早期检测 c w n d - c o n g e s t i o nw i n d o w 拥塞窗口 a c k a c k n o w l e d g e m e n t 确认 t c p t r a n s m i s s i o nc o n t r o lp r o t o c o l 传输控制协议 r t t - r o u n d t r i pt i m e 往返时间 a r q - a u t o m a t i cr e p e a tr e q u e s t 自动请求重传 s s t h r e s h s l o ws t a r tt h r e s h o l d 慢启动门限 s f i s e r v i c ef a i r n e s si n d e x 服务公平指数 w f i w o r s t c a s ef a i m e s si n d e x 晟坏公平指数 s f f s m a l l e s tv i r t u a lf i n i s h e dt i m ef i r s t 最小虚完成时间优先 s s f s m a l l e s tv i s u a ls t a r t e dt i m ef i r s t 最小虚开始时间优先 s e f f s m a l l e s te l i g i b l ev i r t u a lf i n i s h e dt i m ef i r s t 最小合法虚完成时间优先 g p s g e n e r a lp r o c e s s o rs h a r i n g 通用处理机共享 w f q - w e i g h t e d f a i rq u e u i n g 加权公平队列 w f 2 q w o r s t - c a s e - f a i rw e i g h t e df a i rq u e u i n g 晟坏状况加权公平队列 w f 2 q + w o r s t - c a s e f a i rw e i g h t e d f a i rq u e u i n gp l u s 改进的最坏状况加权公平队列 s c f o s e l f - c l o c k e df a i rq u e u i n g 自时钟公平队列 s t f q ( s f q ) 一s t a r tt i m ef a i rq u e u i n g 开始时间公平队列 m d s c f q - m i n i m u m d e l a ys c f q 最小延迟s c f q l f v c l e a pf o r w a r d v i r t u a lc l o c k 前跳虚时钟 f c f s f i r s tc o m ef i r s ts e r v i c e 先到先服务 1 p ，i n t e m e tp r o t o c o l 互连网协议 n s n e t w o r ks i m u l a t o r 网络仿真器 i e t f i n t e r n e te n g i n e e r i n gt a s kf o r c e 互连网工程任务组 i n t s e r v i n t e g r a t e ds e r v i c e 集成服务 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 区分服务 l d e l o c a t i o nd e p e n d e de r r o r 位置相关的错误 b e r - b i te r r o rr a t e 误码率 r t p r t c p r e a l - t i m e t r a n s p o r t ( c o n t r o l l p r o t o c o l 实时传输( 控制) 协议 r s v p r e s o u r c er e s e r v a t i o np r o t o c o l 资源预约协议 s 山东大学硕士学位论文 第一章绪论 1 1 无线通信网络及网络业务的发展趋势 二十世纪九十年代以来。无线通信囡不受空间、时间限制等特点而飞速发展。无线通信系统 所提供的业务从纯语音业务发展到低速数字业务再发展到多媒体业务。无线通信方式也从模拟发 展到数字传输方式。今天各种无线通信系统包括寻呼，g s m ，g p r s ，u m t s ，w l a n 等已经 开始得到广泛应用。它们基本上可以分为电信网( g s m ，g p r s 等) 和计算机网络( w l a n ) 。w l a n 是一绅计算机局域网，而屯信网主要是由电信运行商管理，在可预期的将来，它 | 、 也将融合所谓 的b 3 g 并提供l p 数字化多媒体业务。所有这些变化都使得无线通信相关技术的研究成为热点。 无线通信经历了儿个重要的发展阶段：第一代无线通信系统使用模拟蜂窝技术，主要支持模 拟电话业务，为此国际上制定了几种无线标准：美国的a m p s 、英国的t a c s 、日本n t t 等。9 0 年代我国 l 入了利用数字方式进行传输的第二代无线通信系统，它具有更高的频谱利蹦率，能 提供语音和低比特速率的数据业务。g s m 、p d c 、i s 1 3 6 、i s 9 5 都属于第一二代系统。随着多媒体 业务在有线网络中广泛应用，无线网络也将提供多媒体业务。第三代以及超三代( 3 g ，b 3 g ) 无 线通信系统将超出第二代的范围( g s m ，i s 9 5 ) ，为用户提供更高比特率、更灵活的多媒体业务( 语 音、数据和视频) 。 作为第三代无线网络的最重要的应用，无线用户将可以在任何时候、任何地点访问i n t e m e t 。 无线i n t e r n e t 业务主要包括w e b 浏览器、e - m a i l 、文件传输、v o i c eo v e ri p ，v i d e oo v e ri p 等高速多 媒体业务。今后，还可能出现面向家庭的，并能提供消息、视频点播和网络家电等可能的业务。 1 2 无线网络的特点 无线网络的主要的优点在于其高度的灵活性：由于在无线设备问无需连线，一方面能火量降 低建设成本。快速组网：另一方面非常适合大型会议，古建筑，室外网上直播。码头等不宜实施 有线网络的地方。无线网络在结构及传输模式上和有线网络存在很大的不同，无线网络面临着公 共交换网和分组数据网中所没有涉及的技术挑战。无线网络具有以下特点： 一 信道误码率( b e r ) 高 - 端到端延迟( l o n ge n d - t o e n dd e l a y ) 及延迟抖动大 带宽比较低。 - 不确定性：无线信号在传输时存在干扰。经历长距离传输时会出现信号衰减信号在经历不 同的物理障碍时引起多径衰落。虽然目前采用了通道纠错编码、分集、功率控制等技术，无 线网络仍然有比有线网络高得多的差错率( 1 0 - 3 ) 并且无线网络的衰减是随时间、空间改变 6 山东大学硕士学位论文 的( 即无线信道的位置相关错误：l d e ) 。 1 3 无线网络的o o s 服务质量( q o s ) 将是未来无线网络的关键技术之一。目前的有线网络尚不能提供很好的q o s ， 各种机制还处于研究阶段。由于无线网络的不确定性、移动性和低带宽特性在无线网络上提供 q o s 将更加困难。无线网络q o s 主要构件分为以下几个部分：服务类别、流描述、拥塞控制和分 组调度。以下几节做简单的介绍【1 】。 1 3 1 服务类别和流描述 无线网络中不同的多媒体业务( 包括数据、语音和视频) 有特定的q o s 需求( 例如分组丢 失率、延迟、抖动) 。从服务提供的观点来看，多媒体业务需求可以通过流特征来描述。流特征被 定义为在服务初始期间向用户提供的一系列服务质量( q o s ) 参数。一般包括平均比特率、峰值比 特率、流突发度、平均突发尺寸。延迟及延迟抖动边界、最大和最小带宽需求、分组丢失率。延 迟主要包括接入延迟、传播延迟和拥塞排队延迟。接入延迟主要是由媒介接入协议产生，传播延 迟主要是由物理信道的属性来决定，拥塞排队延迟主要由服务队列中的时间决定。延迟抖动主要 是由于缓冲区大小、拥塞和丢失引起。最大和最小带宽需求将通过吞吐量来表示分组差错率需 求意味着业务可以容忍的最大可能的差错等级。 服务类别说明和流描述是在应用层实现的并且可以有不同的描述方式如下所述： 一 按带宽来分，陡能参数主要包括：峰值速率( b i t s c c ) ；最小可按受的速率( b i t s e c ) ；平均速 率( b i t s e c ) 。 - 按连接的确定性来分：误码率 b e r ) ：误帧率( f e r ) ：最大分组丢失率： - 按延迟来分：最大可容忍的延迟；最大可容忍的延迟抖动： 一 按公平性来分：为不同的业务提供不同的权值，使得各种用户能公平地占用网络带宽。评价 标准为不同的公平性指数。 针对这些q o s 参数，一般将业务分为实时业务和非实时业务两类。对于实时业务，延迟性能 是关键差错性能被限制在可接受的等级。非实时业务将能够容忍延迟但需要无差错传输。多 媒体流的q o s 特征如表l - 1 实时业务 非实时业务 应用语音图象数字音频远程登录 e - m a i l 延迟 b o u n d e db o u n d e db o u n d e d 敏感不敏感 比特率 2 4 - 3 2 c b r ：6 4 3 8 4c b r ：1 2 8 5 1 2 8 1 2 88 1 2 8 ( k b p s ) v b r ：v b r ： 平均：2 3 9 4平均；2 1 3 2 峰值：8 2 2峰值；“ b e rl m 3 c b r ：l o 5c b r ：1 0 - 4 l o 71 0 7 v b r ：1 0 - 6v b r ：1 0 5 表l - i 多媒体流的q o s 特征 7 山东大学硕士学位论文 在i m t 2 0 0 0 中，定义了四种主要的业务流类型：对话类( c o n v e r s a t i o n a lc l a s s ) 流类( s t r e a m i n g c l a s s ) ，交互类( i n t e r a c t i v ec l a s s ) 和背景类( b a c k g r o u n dc l a s s ) 2 。对话类主要承载实时业务流， 包括一些延迟敏感的应用例如：语音和电视会议。流类业务的延迟要求相对丁对话类业务来说 较低，但仍需要考虑延迟特性，其应用例子为实时的语音和图象。交互和背景类主要提供非实时 服务，例如突发的分组传输，交互类包括w e b 测览器，应考虑一定的时间限制。背景类将不考虑 时间的限制，例如，e m a i l 和文件。这些业务无需严格的延迟要求，但是对分组差错率要求很高。 目前的无线网络主要是接入骨干的i p 和a t m 网络中，由于不同类型的网络有不同的业务类 型描述因此我们需要对各种业务类型进行对比和映射。在a t m 网络中业务流被分为以下几类： ( 1 ) c b r ( c o n s t a n t b i t r a t e ) 和v b r ( v a r i a b l e b i t r a t e ) 支持实时应用，可映射为无线网络的对 话类和流类：( 2 ) a b r ( a v a i l a b l eb i tr a t e ) 和u b r ( u n s p e c i f i e db i tr a t e ) 将支持非实时应用， 可映射为交互类和背景类。在宽带i p 网络的区分服务结构( d i 惑e r v ) 中，业务类型分为p r e m i u m s e r v i c e ，a s s u r e ds e r v i c e 和b e s te f f o r t 。这些服务类之间的关系如表1 - 2 a t ml p 无线例子 c b r p r e m i u ms e r v i c e 对话和流类语音 v b ra s s u r e ds e r v i c e 对话和流类视频 a b ra s s u r e ds e r v i c e 交互 w w w u b rb e s l e f r o r l 背景 e m a i l 表卜2 服务类映射 1 3 2 无线网络的o o s 结构框架 为了支持无线网络的o l o s 需求无线网络的q o s 提供需要在各个层面上来考虑。表1 3 给出 了无线网络中，各层所提供的服务质量( q o s ) 的控制功能。 层 活动 应用层语音视频压缩技术 传输层拥塞控制，无线t c p 网络层 无线队列调度，基于路由的q o s 链路层 a r q ，多址接入技术 物理层扩频，编码，成帧 表1 3 协议栈各个层次上所提供的q o s 功能 将来的i n t e r a c t 不仅要提供尽力而为的服务，而且还要提供多媒体服务。i e t f 先后提出了集成 服务( i n t s e r v ) 【4 】和区分服务( d i f f s e r v ) 【5 】两种网络结构。集成服务模型主要包括资源预约协议 ( r s v p ) 和一组服务类型的定义，其目标是为每个连接提供端到端的确定的服务质量保证。集成 服务可以提供类似于电路交换网络中虚链路具有的比较确定的、定量的服务质量。其服务包括确 保服务。负载受控服务。为实现集成服务结构，中间路由器内部要完成接入控制、分组分类、r s v p 、 分组调度算法，这些算法需求主要是通过信令来完成的。i n t s e r v 的主要问题是路由器要为每个会 话维护相应的状态信息当存在大量会话时，内部节点为维护各连接状态所需开销迅速增大，造 8 山东大学硕士学位论文 成集成服务的可扩展性差。 为了解决可扩展性，i e t f 又提出另一种能提供粗粒度服务质量的区分服务( d i f l s e r v ) 。它由 一些边缘路由器和核心路由器组成，边缘路由器执行较为复杂的业务流分类、业务量调节及队列 管理和调度的功能而核心路由器则执行较为简单的队列管理和调度的功能。d i f f s e r v 按汇聚的连 接分配网络资源，核心路由器不采用复杂的信令协议，具有很好的可扩展性。区分服务利用l p 分 组的d s c p 子域标记分组转发优先级。d i f f s e r v 边缘路由器包括分组分类器( t r a f f i cc l a s s i f i c a t i o n ) 和调节器( c o n d i t i o n i n g ) 和调度器( s c h e d u l i n g ) ，核心路由器按不同的p h b 来调度分组。 拥塞控制和分组调度与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 i s e r v 是两种q o s 的体系结 构是应用在于整个网络的宏观概念。拥塞控制和分组调度是两个实现q o s 时非常重要的微观机 制无论在i n t s e r v 还是d i f f s e r v ，拥塞控制和分组调度都扮演着重要的角色是实现q o s 的基础。 如图13 1 。 线网络一般是作为接入网连入i n t e r n e t 的，l m e r n e t 的骨干网( 由电信运行商管理) 基本是有 线网络，目前的i n t e r n e t 协议和控制策略也都是针对有线网络设计的。 t c 9 韶塞控队列调度 制 图1 3 1 互连网t c p 拥塞控制和分组调度 1 4 拥塞控制 传送数据包数量 酗1 3 2 当负载过大时，发生拥 塞，网络性能急剧下降 况 况 随着计算机网络快速增长而来的是越来越严重的拥塞问题。例如由于本地缓存溢出。i n t e m e t 网关会丢弃约1 0 的数据包【6 】。据统计，i n t e r a c t 上9 5 的数据流使用的是t c 朋p 协i 发 7 l 。i n t e m e t 主要互连协议的t c p i p 的拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 机制对控制拥塞具有特别重要的意义。拥 塞控制是确保i m e m o 鲁棒性( r o b u s t n e s s ) 的关键因素，也是各种管理控制机制和应用( 如多媒体通 信中q o s 控制【8 】区分服务【9 】【1 0 】) 的基础，因此成为当前网络研究的一个热点问题。 网络产生拥塞的根本原因在于用户( 或叫端系统) 提供给网络的负载( 1 0 a d ) 大于网络资源容 量和处理能力( o v e r l o a d ) 。表现为数据包时延增加、丢弃概率增大、上层应用系统性能下降等。 图1 3 2 显示了拥塞发生的情况。 拥塞产生的直接原因有以下3 点： ( 一) 存储空间不足 9 山东大学硕士学位论文 几个输入数据流共同需要同一个输出端口，在这个端口就会排队。如果没有足够的存储空间， 数据包就会丢弃。对突发数据流更是如此。增加存储空间在某种程度上可以缓解这一矛盾，但如 果路由器有无限存储量时，拥塞只会变得更坏，而不是更好，因为在网络里数据包经过长时间摊 队完成转发时，它们早已超时，源端认为它们已经被丢弃，而这些数据包还会继续向下一路由器 转发，从而浪费网络资源，加重网络拥塞。 ( 二) 带宽容量不足 低速链路对高速数据流的输入也会产生拥塞。根据香农信息理论，任何信道带宽最大值即信 道容量c = b i o ( 1 + s n ) ( n 为信道白噪声的平均功率s 为信源的平均功率，b 为信道带宽) 。所 有信源发送的速率r 必须小于或等于信道容量c 。如果r c 则在理论上无差错传输就是不可能 的，所以在网络低速链路处就会形成带宽瓶颈，当其满足不了通过它的所有源端带宽要求时网 络就会发生拥塞。 ( 三) 处理器处理能力弱、速度慢也能引起拥塞 如果路由器的c p u 在执行排队缓存，更新路由表等功能时，处理速度跟不上高速链路，也会 产生拥塞。 拥塞一旦发生往往会形成一个不断加重过程。如果路由器没有空余的缓存，它就必须丢弃新 剑的数据包。当数据包丢弃时，源端会超时、重传该包。由于没有得到确认，源端只能保留数据 包，结果缓存会进一步消耗，加重拥塞。 t c p i p 的拥塞控制与网络服务质量q o s 是密切相关的。q o s 实际上是通过对带宽、缓存等网 络资源的管理与调度实现所传输数据流要求的一系列服务请求，例如保证传输时延、抖动、丢失 率和吞吐量等指标。拥塞控制的目的正是要采用合理的算法与机制确保网络不因传入数据流过大 耗尽网络资源而导致崩溃( c o n g e s t i o nc o l l a p s e ) 。与传统的尽力而为服务( b e s t e f f o r t ) 遇到网络资 源不足就简单地丢弃数据包相比，q o s 对网络拥塞控制提出了更高的要求。从i n t s e r v 发展来的对 不同数据流实现区分服务的d i f f s e r v 更是离不开拥塞控制，以确保各服务类型得到应有的服务。 可以这样说，没有拥塞控制就不可能有今天i n t e r a c t 的飞速发展，也就不可能有上层的各种应用。 在无线网络中无线链路由于衰落和多径效应的影响信道的差错率很高。这样势必将引起 数据在网络中频繁地重传，降低整个网络的吞吐量。目前在i n t e r a c t 实际使用的t c pr e n o 版本都 认为分组丢失是网络发生拥塞控制的指示，并调用相应的拥塞控制策略通过降低发送速率，来避 免拥塞。然而在无线环境中，分组的丢失很可能是由于信道错误引起，这时应该立即进行重传， 而不是降低发送速率，引起网络吞吐量的波动和降低。因此，有必要对1 p 进行改进，使其能够 判断分组丢失的真正原因：拥塞还是无线信道错误。论文将在第二章阐明改进方法。 1 5 分组调度 队列调度算法运行在网络节点中发生冲突需排队等待调度之处，它按照一定的服务规则对交 换节点的不同输入业务流分别进行调度和服务使所有的输入业务流能按预定的方式共享交换节 点的输出链路带宽。输入业务到达交换节点后分别暂存到相应的队列中。如何把输入业务流对 t o 山东大学硕士学位论文 应到不同的队列中，不同的调度算法在不同的网络环境里有不同的方法，先到先服务( f c f s ) 只根 据分组的到达时间对之进行服务，这时队列数为1 ，这种调度算法的实现简单，力度较大，但无法 实现为不同的业务流提供相应q o s 。较复杂的调度算法则会根据一定的规则把输入业务流对应到不 同的队列里，从而对输入业务进行有区别的服务。目前因特网业务流分类算法还是有待进一步研 究的课题 i i 。本文不讨论队列调度算法所涉及的业务流分类，只讨论对不同业务流所属队列的 调度。 根据不同的服务规则队列调度算法可分为基于时延的和基于速率的两类。根据调度算法的 工作状态又可以分为工作保持和非工作保持 1 2 。根据通信网络环境，又可分为无线环境下的 队列调度和有线环境下的队列调度。实际上，对于某一特定的调度算法，根据不同的分类标准， 又可属于多个不同的类，所以并没有一种统一的分类标准。根据调度算法的服务规则、调度目标 及其发展趋势，同时为了能更清晰地说明各类算法之间的区别，本文把目前己出现的队列调度算 法大致分为如下五类：基于轮循的调度算法、基于通用处理机共享( g p s ：g e n e r a l i z e dp r o c e s s o r s h a r i n g ) 的算法、基于时延的调度算法、基于服务曲线( s e r v i c ec u r v e ) 的算法及核心无状态 公平队列。 ( 一) 基于轮循的调度算法 传统的轮循( r r ：r o u n dr o b i n ) 算法对不同队列( 业务流) 进行无区别的循环调度服务。这 样就使分组长度不同的队列之间产生不公平的现象；而且这种算法不能对业务提供时延保证。为 了改进r r 算法的时延特性及其在变长分组环境下的不公平性，出现了些改进型的算法，如加权 轮循( w r r ：w e i g h t e dr o u n dr o b i n ) 1 3 ，差额轮循( d r r ：d e f i c i tr o u n dr o b i n ) 1 4 紧急 轮循( u r r ：u r g e n c y b a s e dr o u n dr o b i n ) 1 5 。这些算法力图在尽量保持r r 算法实现简单性的 同时，从不同的方面改进r r 算法的时延特性和其在可变长分组环境下的不公平性。 ( 二) 基于g p s 模型的p f q 调度算法 g p s 是一个理想化的流模型 1 6 它根据各队列的共享比例对所有的活动队列同时服务。所以 能使各业务流真正公平地共享链路带宽。对每个队列业务流保证明确的端到端的时延上限，而且 与其他队列业务流无关。g p s 模型是流系统，但是实际的系统都是分组系统：在任何给定的时刻只 能有一个分组可以得到服务，分组的传输是不能被抢占的。因此出现了一类用来逼近基于流的g p s 模型的分组算法：分组公平排队( p f q ：p a c k e tl a i r q u e u i n g ) 算法。目前，p f q 主要有：1 f q 1 7 ， w f 2 q 1 7 ，w f 2 q + t 8 。s c f q 1 9 ，e ) - s c f q z 0 ，s f q 2 1 ，f f q 2 2 ，s p f q 2 2 ，l f v c 2 3 算法 等 ( 三) 基于时延的调度算法 基于轮循和g p s 模型的调度算法可以看成是基于速率的调度算法这种算法通常为每个队列提 供一定的速率保证来达到提供时延保证的目的。而基于时延的调度算法则是以( 为各队列) 直接 提供时延保证为目的。这类算法的代表是最早期限优先( e d f 2 4 ：e a r l l e s td e a d l i n ef i r s t ) 。 在e d f 算法中，给每个队列赋予了一个时延参数d i ，表示系统对此队列提供的时延上界：e d f 为每 个到达的分组计算一个时签( 等于分组到达时间与其所属队列d i 值之和，时签最小的晟先得到服 务) 。e d f 算法中由于涉及到对时签的排序，其复杂度为0 ( 1 0 9 n ) 。由于要求输八业务必须满足 山东大学硕士学位论文 一定构属性要求，使得在实际中e d f 无法提供端到端的时延保证。h z h a n g 等人在文 2 5 j 中提出r c s 惆度算法。r c s 在e d f 的基础上，引入了整形机制，在每个节点处都能得到时延保证。憝形机制使 r c s 为非工作保持，其链路利用率有所下降。 ( 四) 基于服务曲线的算法 为了解决使用单个参数( 如速率) 引起的时延与带宽的分配互相辎合的问题，c r u z 2 0 首先 提出了服务曲线的q o s 模型。每一种业务种类被赋予一条服务曲线，这条服务曲线指定了它不同时 刻应该收到的最小的服务量，对于相同的到达曲线，不同服务曲线所提供的时延是不同的，用非 线性的服务曲线实现时延和带宽的解耦。但是一个根本的矛盾就是由于有了非线性的服务曲线和 有优先级的业务，就有可能对所有的业务种类不能同时提供保证的服务曲线，也有可能不能同时 保证实时性和公平性。基于服务曲线的算法有：基于服务曲线的晟早期限优先( s c e d 2 7 2 8 ： s e r v i c ec u r v e b a s e de a r l i e s zd e a d i n e ) 和分级的公平服务曲线( h f