（计算机应用技术专业论文）面向网络qos的拥塞控制研究.pdf

摘要 【随着i n t e r n e t 的飞速发展，涌现了许多新型网络应用，例如视频点播、网 络会议等。这些新型网络应用的一个共同特征就是对网络提出服务质量( q o s ) 要求。但是，基于“尽力而为”服务模型的i n t e m e t 无法提供有效的q o s 保证。 为解决上述矛盾，人们提出了各种各样网络q o s 技术，如综合服务、区分服务、 多协议标记交换等。由于这些技术通常需要改变现有网络的下层框架，离真正 实现和运用还有很长路要走。 影响网络q o s 的因素有很多，其中一个重要的因素就是网络拥塞。拥塞控 制作为避免和控制网络拥塞的重要手段，不仅对提高网络的性能和效率有重大 影n 向，也是提高网络q o s 能力的前提和基础。卜_ ，一一 本文从拥塞控制的角度出发，研究高效、公平的拥塞控制机制，使之能辅 助网络提供非确定性的q o s 保证。本文在对i n t e r n e t 网络拥塞控制领域最新研 究成果进行了系统、全面总结的基础上，就目前该领域三个主要的研究方向展 开了系统深入的研究，阐明了作者在这方面的见解和观点，取得了若干创新和 突破。本文研究的主要创新点包括： 1 ) 提出了一种新的高速网络分组调度算法e w f q 陔算法重新定义了 虚拟时间计算函数，并采用s e f f 作为调度规则。仿真实验证明该算法具有计 算复杂度低、分配带宽公平、w f i 低等优点乒卜 2 ) 提出了一种基于方程的实时媒体流拥塞控制机制e b c c 。( 叠b c c 采用 稳定状态下的t c p 速率响应函数作为控制方程，并对控制参数往返时延r t t 与丢失率p 的估算作了特殊的平滑处理，能较好地完成实时媒体流的拥塞控制 任务少厂一 3 ) 提出了一种基于速率的发送方和接收方混合驱动组播拥塞控制机制 r b m c c 。呻m c c 把对拥塞的响应任务分配给接收者、中间节点和发送方三方 共同完成，实现对网络拥塞的快速、准确响应。仿真实验证明r b m c c 具有良 好的可伸缩性和满意的公平性。卜，一一 j l l # i 、，本文还做出了如下贡献： 1 )系统全面深入地研究了拥塞控制领域最新研究成果，总结出目前拥 塞控制的研究主要集中在三个方向：( i ) 改进现有的t c p 拥塞控制算法： ( i i ) 研究在中间网络设备( 主要指路由器或交换机) 中采取一定的策略来避 免和控制网络拥塞；( i i i ) 研究新的端到端拥塞控制协议。 2 )系统全面深入地综述了组播模式下的拥塞控制研究进展，并分析了 可靠组播拥塞控制存在的主要问题，以及各种解决方案的优缺点。 3 )系统分析了t c p 拥塞控制原理、实现及其改进。本文主要研究了 两种比较流行的t c p 实现：t c pt a h o e 与t c pr e n o ，详细介绍两种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 a c t ，m a n ya p p l i c a t i o n sh a v ec o m ef o r t h ，s u c h a sv o d ，n e t w o r kc o n f e r e n c e a l lo f t h e s e a p p l i c a t i o n sh a v e ac o m m o nf e a t u r e ，i e t h e yr e q u i r en e t w o n t o p r o v i d eq o s h o w e v e r , i n t e r n e tw i t c hi sb a s e do n “b e s t e f f o r t ”c m m o t g u a r a n t e eq o s t o s o l v et h i s p r o b l e m ，v a r i o u s n e t w o r kq o s t e c h n o l o g i e sw e r ep r e s e n t e d ，s u c ha si n t e g r a t e ds e r v i c e ，d i f f e r e n t i a t e ds e r v i c e ， a n dm u l t i p l ep r o t o c o ll a b e ls w i t c h b e c a u s et h e s et e c h n o l o g i e sn e e dt om o d i f y t h ei n f r a s t r u c t u r eo fc u n e n tn e t w o r k ，t h e r ei sal o n gw a yt og ob e f o r et h e yb e c o m e a p p l i c a b l e t h e r ea r em a n yf a c t o r st oi n f l u e n c en e t w o r kq o s a ni m p o r t a n to n ei s n e t w o r k c o n g e s t i o n a sa c r u c i a lm e t h o dt oa v o i da n dc o n t r o ln e t w o r kc o n g e s t i o n ， c o n g e s t i o nc o n t r o l i sn o to n l yt h ec r i t i c a lf a c t o ro fn e t w o r kp e r f o r m a n c ea n d e f f i c i e n c yi m p r o v e m e n t ，b u ta l s ot h ep r e m i s eo fi m p r o v i n g n e t w o r k q o s t h i sd i s s e r t a t i o ne x p l o r e sm e t h o d so fh o w t oa d m i n i s t e ra n dc o n t r o ld i v e r s e n e t w o r kt r a f f i c s e f f i c i e n t l y a n d i m p a r t i a l l y t oe n a b l en e t w o r kt o p r o v i d e u n d e t e n n i n e dq o sg u a r a n t y o nt h eb a s i so fs y s t e m a t i cs u m m a r i z a t i o no fu pt o d a t en e t w o r kc o n g e s t i o nc o n t r o lw o r k ，t h i sd i s s e r t a t i o nr e s e a r c h e st h r e ep r i m a r y f i e l d so fc o n g e s t i o nc o n t r o li nd e p t h ；d e s c r i b e st h ea u t h o r sc r e a t i v ev i e w p o i n t s a u do b t a i n ss e v e r a lb r e a k t l n o u g h s t h ep r i m a r yi n n o v a t i o n so f t h i sd i s s e r t a t i o na r e a sf o l l o w s ： 1 ) p r e s e n t i n g an e w a l g o r i t h m o f h i g h s p e e d n e t w o r k p a c k e t s c h e d u l e - e w f q ，w h i c hr e d e f i n e st h ev i r t u a lt i m ec a l c u l a t i o nf u n c t i o n ，a n du s e s s e f fa st h es c h e d u l er u l e s s i m u l a t e de x p e r i m e n t ss h o wt h a te w f qh a sm a w a d v a n t a g e s ，s u c ha sl o w e rc o m p u t a t i o n a lc o m p l e x i t y , f a i r e rb a n d w i d t ha s s i g n m e n t ， a n di o w e rw f i ， 2 ) p r e s e n t i n ga ne q u a t i o n b a s e dr e a lt i m em e d i as t r e a mc o n g e s t i o nc o n t r o l m e c h a n i s l n e b c c ，w h i c hu s e st c p r a t er e s p o n s ef u n c t i o nu n d e rs t a b l es t a t u sa s t h ec o n t r o l e q u a t i o n ，a n dp r o c e s s e s t h ec o n t r o l p a r a m e t e r 月玎a n dpw i t h 1 1 1 一 d i s t i n c t i v es m o o t hm e t h o d e b c cc a na c c o m p l i s hc o n g e s t i o nc o n t r o lt a s kf o rr e a l t i m em e d i as t e a m sp r e f e r a b l y 3 ) p r e s e n t i n g ar a t e b a s e d m u l t i c a s t c o n g e s t i o n c o n t r o l l a a e c h a n i s m r b m c ci n i t i a t e du n i t e d l yb ys e n d e ra n dr e c e i v e r , w h i c ha s s i g n st h e r e s p o n s ed u t i e st or e c e i v e l ，i n t e r m e d i a t en o d ea n ds e n d e ri n o r d e rt oa c c o m p l i s h f a s ta n da c c u r a t er e s p o n s e sf o rd y n a m i cn e t w o r kc o n d i t i o n s i m u l a t e de x p e r i m e n t s s h o wt h a tr b m c ci ss c a l a b l ea n df a i r i na d d i t i o n ，t h ec o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r e ： 1 ) g i v i n gas y s t e m a t i c m a di n - d e p t hs u r v e yo fc u r r e n tr e s e a r c ho fc o n g e s t i o n c o n t r o l ，w h i c hh a st h r e ef o c u s e s ：( i ) i m p r o v i n gt h ec u r r e n tt c pc o n g e s t i o n c o n t r o l a l g o r i t h m ；( i i ) s t u d y i n g s o m e p o l i c i e s w h i c hw e r e a p p l i e d i nt h e n e t w o r kd e v i c e ，s u c ha sr o u t e ro rs w i t c h ，t oa v o i da n dc o n t r 0 1 n e t w o r k c o n g e s t i o n ；( i i i ) s t u d y i n gn e w e n d q o e n d c o n g e s t i o n c o n t r o l p r o t o c 0 1 2 、g i v i n g as y s t e m a t i ca n di n d e p t hs u m m a r yo ft h ep r o g r e s so fm u l t i c a s t c o n g e s t i o nc o n t r 0 1 a n a l y z i n g t h e m a j o rd i f f i c u l t i e s o fr e l i a b l em u l t i c a s t c o n g e s t i o nc o n t r o l ，r e l a t e dp r o p o s a l sa n d t h e i ra d v a n t a g e sa n d d i s a d v a n t a g e s 3 ) s y s t e m a t i c a l l ya n a l y z i n g t h et c p s p r i n c i p l e ，i m p l e m e n t a t i o n a n d i m p r o v e m e n t t h i sd i s s e r t a t i o nr e s e a r c h e st w op o p u l a ri m p l e m e n t a t i o n s o f t c p ：t c pt a h o ea n dt c pr e n o ，a n di n t r o d u c e st w ot c p r a t er e s p o n s em o d e l s s i m p l em o l l a n d c o m p l e x m o d e l c o n g e s t i o nc o n t r o li sas o p h i s t i c a t e dt a s kt h a tc a n n o tb ea b s o l u t e l yr e s o l v e d b y m o n o l i t h i cp r o t o c o lo ra l g o r i t h m t h eo n l y w a y t og u a r a n t e et h es t e a d i n e s sa n d e f f i c i e n c yo f n e t w o r ki st ou s ev a r i o u sm e c h a n i s m st oc o n t r o lt h ec o n g e s t i o nf r o m m u l t i p l ea s p e c t so f t h e w h o l en e t w o r k k e yw o r d s ：q o s ，c o n g e s t i o nc o n t r o l ，f a i r i n gq u e u i n g ，r e a l t i m e m e d i as t e a m ，r e l i a b l em u l t i c a s t 1 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。据我所知，除了文中特别加以标注和 致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得电子科技大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均己在论文中作了明确的说明并表示致谢。 躲土与址嘿冽2 年f 脚日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位 论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：且啦 导师签名：拯 日期：渺免月1 8 日 电子科技大学博士学位论文 1 1i n t e r n e t 网现状 第一章绪言 i n t e m e t 的历史可追溯到上个世纪7 0 年代，其最初的形式和主要功能是用 于美国军方传送一些机密或非机密的军用信息。随着应用需求的增加及t c p i p 技术研究的发展，i n t e r n e t 的主要服务对象逐渐从军用向民用方向转移，其规模 也越来越大。尤其是w w w 出现以来，i n t e r n e t 的网络规模、用户数量及业务 量呈现出爆炸式的增长。应该说，到目前为止i n t e r n e t 的发展与运行是非常成 功的，这主要应归功于支撑i n t e r n e t 运行的t c p i p 协议在设计上的灵活性与合 理性。但是，随着技术的发展与应用需求的更新，今天的i n t e m e t 呈现出了许 多新的特点，主要有以下几点： ( 1 ) 不同的应用要求有不同的服务质量( q o s ) ，如吞吐量、传输时延、 时延抖动等。目前的i n t e r n e t 不提供服务质量保证，只许诺以点对点的“尽力 而为”( b e s t e f f o r t ) 服务。如何在i n t e r n e t 中实现服务质量保证是当前通信研 究领域十分关注的问题，i p v 6 、i n t e g r a t e ds e r v i c e s r s v p 和d i f f e r e n t i a t e ds e r v i c e s 等多种q o s 服务模型和技术被相继提出。一个合理的i n t e m e t 的资源分配方案 是实现服务质量保证的关键技术。目前i n t e r n e t 的资源分配主要在用户端和中 继网络设备中进行。 ( 2 )网络多媒体应用的推广对i n t e r n e t 的正常运行带来了严峻的挑战。 实时音频视频等多媒体业务在i n t e r n e t 网上传输时，均要求网络能提供大量的 网络带宽，而且对报文的时延也有很高的要求。为满足这些要求，许多多媒体 应用采用u d p 作为传输层协议，对报文的丢失和网络的拥塞不作任何响应。当 网络拥塞发生时，有拥塞控制反应机制的协议( 如t c p ) 数据流会主动减小注 入网络的数据量，而上述多媒体u d p 流由于没有端到端的拥塞控制机制，即使 网络发出了拥塞指示( c o n g e s t i o ni n d i c a t i o n ) ，u d p 也不会降低速率，结果导 致t c p 流得到的网络资源越来越少，并最终饿死。 ( 3 ) 组播( m u l t i c a s t ) 技术的应用在节省网络资源的同时，也给网络的 正常运行提出了严峻的挑战。近年来，i n t e r n e t 中涌现出大量新的应用，如软件 第一章绪言 分发、视频会议、远程教学、信息发布等。这些应用都有一个共同的特点：使 用一对多( o n e t o m a n y ) 或多对多( m a j l y t o m a n y ) 的数据通信方式。组播技术 的提出和研究正是为满足上述应用的需求。组播通信能把数据从一个发送者高 效地传送给一个通信组的所有接收者。 通信能显著降低网络与端系统的开销。 与多路单播( u n i c a s t ) 方式相比，组播 但是组播通信技术还存在许多潜在的、 亟需解决的问题，如组播路由问题、组播安全问题、组播拥塞控制问题、组播 数据恢复问题等。这些问题中任何一个得不到解决，推广组播应用都将遇到巨 大困难。而组播拥塞控制又是所有问题中最重要的、最难解决的和最令人关注 的问题之一。如果可靠组播应用不能对网络拥塞做出正确响应，其对i n t e r n e t 所产生的影响将比单播( u n i c a s t ) 拥塞所产生的影响更为严重。 i n t e m e t 的新特点要求研究新的技术和开发新的协议对网络施加更合理、更 有效的管理和控制。特别随着i n t e r n e t 迅速发展，其规模越来越大、结构也日 趋复杂、应用越来越繁多，拥塞控制的作用显得更为突出。 1 2网络服务质量( n e t w o r kq o s ) 与拥塞控制 近年来，服务质量( q o s ) ，尤其是i pq o s 一词频频出现于科技文献中。 随着网络多媒体应用及其它实时业务的大量出现，给原本不提供q o s 的i n t e r n e t 提出了新的研究课题。于是，各种各样新的网络服务模型和q o s 技术应运而生。 其中比较突出的有综合服务模型( i n t - s e r v ) ，区分服务模型( d i f f - s e r v ) ，多协议标 记交换( m p l s ) ，流量工程和约束路由等。下面主要介绍前面三种技术。 1 2 1 综合服务模型( i n t s e r v ：i n t e g r a t e ds e r v i 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 ) 的基本思想是“所有流的相 关状态信息应该是在端系统上”。它基于每个流( 单个的或是汇聚的) 提供端到 端的保证或是受控负载的服务( c o n t r o l l e d - l o a ds e r v i c e ) ，其核心技术是资源预 留协议( r s v p ) ，即实时应用在传输数据之前必须首先建立通道和预留资源。 为了保证o o s ，：i n t s e r v 定义了4 个功能部件。为支持i n t - s e r v ，网络中 的每个路由器皆需要实现这4 个部件： q ) r s v p ( r f c 2 2 0 5 ) ：r s v p 即资源预留协议，它是i n t e r n e t 上的信令协议。 电子科技大学博士学位论文 通过r s v p ，用户可以给每个业务流( 或连接) 申请资源预留。这些要预留的资源 包括缓冲区及带宽的大小。这种预留需要在路径上的每一跳的路由器都要进行， 这样才能提供端到端的q o s 保证。r s v p 可以适用于点到点以及点到多点的通信 环境。 许可控制( a d m i s s i o nc o n t r 0 1 ) 对用户的访问进行一定的监视和控制， 它基于用户和网络达成的服务协议 有利于保证通信双方的共同利益。 ( d 分类器( c l a s s i f i e r ) ：根据预置的一些规则，它对进入路由器的每一个 分组进行分类。这可能需要查看i p 分组里的某些域，例如：i p 源地址、i p 目 的地址、上层协议类型、源端口号、目的端口号：分组经过分类以后被放到不 同的队列中等待接收服务。分组分类技术还不很成熟，是一个有待研究的领域。 ( 9 分组调度器( s c h e d u l e r ) ：它主要是基于一定的调度算法对分类后的分 组队列进行调度服务。 i n t s e r v 的优点是能提供绝对的q o s 保证，能工作在u n i c a s t 与m u l t i c a s t 模式下。但i n t s e r v 的致命缺陷是其可伸缩性差，主要有两方面的原因：1 ) 由 于i n t s e r v 的工作方式是基于每个流( p e r - f l o w ) ，这就需要保存大量的与分组 队列数成正比的状态信息( “软状态”信息) ，并且需要周期性的更新。2 ) 由于 需要进行端到端的资源预留，必须要求从发送者到接收者之间的所有路由器都 支持i n t s e r v 服务。这就要求发送者到接收者之间的所有路由器必须实现 r s v p 、许可控制、m f ( m u l t i - - f i e l d ) 分类和分组调度。另外，在i n t s e r v 中 一个流的预留资源不能与其它流复用，这将导致资源的浪费。 1 2 2区分服务模型( d i f f - s e r v ：d i f f e r e n t i a t e ds e r v i c e ) 针对综合服务模型的缺陷，i e t f 组织制定了新的i p 网络q o s 标准：区分 服务( d i f f s e r v ：d i f f e r e n t i a t e d s e r v i c e ) 。区分服务是由综合服务( i n t s e r v ) 发展 而来的，它采用了i e t f 基于r s v p 的服务分类标准，避免了综合服务中分组 流在沿路节点上的资源预留。如图1 - 1 所示为区分服务体系结构。提供区分服 务的i n t e r n e t 区域应主要包括：核心路由器、边缘路由器、资源控制器( b b ， b a n d w i d t hb r o k e r ) 。在区分服务区域中，网络的边缘设备对每个分组进行分类、 标记d s 域。t p 分组用d s 域来携带对服务的需求信息。在网络的核心节点上， 路由器根据分组头上的d s 码点( c o d e p o i n t ) 选择码点所对应的转发处理方式。 第一章绪言 资源控制器b b 配置了管理规则，为客户分配资源。b b 可以通过服务级别协定 ( s l a 。s e r v i c e l e v e l a g r e e m e n t ) 与客户进行相互协调以分享有限的带宽。 图卜1区分服务体系结构示意图 区分服务使得i s p s 和企业网能支持不同的服务类( s e r v i c ec l a s s e s ) 。每种 服务类通过网络提供的不同服务级别进行区分。区分服务承诺为大规模网络提 供可扩展的粗粒度优先级服务。可以肯定，比面向细粒度分组流的r s v p 集成 服务有更好的可扩展性。d i f f - s e r v 为i pq o s 提供了良好的基础，但还是还不能 完全依靠自己提供端到端的q o s 保证。d i f f - s e r v 需要大量网络单元的协同工作 才能向用户提供端到端的服务质量。由于这些组件高度分散的特点和对它们进 行集中管理的需要，必须有一个全局的带宽管理对全局资源进行动态管理。 1 2 3多协议标签交换( m p l s ：m u l t ip r o t o c o ll a b e ls w i t c h ) 从现有的网络技术来看，a t m 技术提供了最为成熟的q o s 解决方案。但 纯粹的a t m 网络实现过于复杂，a t m 信元到桌面的业务发展十分缓慢。相反 i p 网络实现灵活，却很难提供q o s 服务。因此，两种技术的结合就成了必然。 多协议标签交换( m p l s ) 技术就是综合利用网络核心的交换技术和网络边缘 的i p 路由技术各自的优点而产生的。i e t f 在1 9 9 7 年初成立了m p l s 工作组， 利用集成模型中现有技术的主要思想与优势，制定出一个统一的、完善的第3 层交换技术标准。m p l s 明确规定了一整套协议和操作过程，最终在i p 网内通 过a t m 和帧中继实现快速交换。m p l s 中的关键概念是用标签来识别和标记 电子科技大学博士学位论文 i p 报文，并把标签封装后的报文转发到支持m p l s 的交换机或路由器，由它们 在网络内部继续交换标签，转发报文。 如图1 - 2 所示，m p l s 网络由标签边缘路由器( l e r ) 和标签交换路由器 ( l s r ) 组成。在l s r 内，m p l s 控制模块以i p 功能为中心，转发模块基于标 签交换算法，并通过标签分配协议( l d p ) 在节点间完成标签信息以及相关信 令的发送。值得注意的是，l d p 信令以及标签绑定信息只在m p l s 相邻节点问 传递。l s r 之间或l s r 与l e r 之间依然需要运行标准的路由协议，并由此来 获得拓扑信息。通过这些信息l s r 可以明确选取报文的下- - n g 并可最终建立特 定的标签交换路径( l s p ) 。m p l s 使用控制驱动模型，即基于拓扑驱动方式对 用于建立l s p 的标签绑定信息的分配及转发进行初始化。l s p 属于单向传输路 径，因而全双工业务需要两条l s p ，每条l s p 负责一个方向上的业务。 m p l s 的出现在很大程度上解决了i p 网络与a t m 相互衔接的问题。与此 同时，以m p l s 核心技术的i po v e ra t m 网络解决方案承诺提供真正的端到端 的q o s 保证，为q o s 的研究提供了崭新的研究方向。 1 2 4 面向网络q o s 的拥塞控制 上述三节分别介绍了三种不同的q o s 技术。这三种技术有一定的继承和发 展关系，并且都承诺提供网络q o s 保证，因此成为近年q o s 领域的研究热点。 但是它们都存在一定缺陷与不足，例如三种技术大都需要增加新的通信信令， 甚至需要改变下层基础结构。这些缺陷与不足都给实现、推广和应用这些技术 第一章绪言 带来了很大的困难。本文在研究这些技术的基本原理及实现方法的基础上，希 望从另外一个角度去研究使现有网络提供或增强q o s 的方法。本文的主要目的 就是研究更为稳定、高效的拥塞控制策略，使之能辅助网络提供非确定性的q o s 保证，即面向网络q o s 的拥塞控制。 如图1 3 所示为数据包延迟、吞吐量与网络拥塞的关系示意图。可以看出， 延迟 吞吐量 最大吞吐量 上 蕊二 负载负载 a ) 延迟一负载曲线b ) 输出一负载曲线 图1 3 延迟、吞吐量与拥塞关系示意图 当网络拥塞发生时，网络提供的q o s 严重下降，甚至导致网络死锁。因此，如 何更有效避免拥塞的发生以及拥塞发生后的恢复是网络提供q o s 的有效手段 之一。 1 3拥塞的定义与拥塞控制属性 1 3 1 拥塞的定义 因为存在许多不同的度量来描述拥塞现象，如传输延时、数据吞吐、队列 长度和网络效率等，人们对拥塞控制并无严格定义，甚至对拥塞的定义都无法 完全统。普遍上认为当用户( 或叫端系统) 给网络带来的负载( l o a d ) 大于 网络资源容量和处理能力时，网络提供的服务质量将降低，表现为数据包时延 增加、丢弃概率增加，网络效率降低等( 如图1 - 4 为网络拥塞状况) 。实际上， 拥塞不仅与网络负载相关，而且与用户对服务质量( q o s ) 的满意度相关。这 电子科技大学博士学位论文 儿给出两个比较类似并且相对被普遍认可的拥塞的定义。 定义1 1 如果因为网络负载增加而导致用户，的满意度降低，用户j 则认 为网络发生拥塞( 爿n e t w o r k i ss a i d t ob ec o n g e s t i o n f r o m t h e p e r s p e c t i v eo f u s e r t i f t h es d t i a f a c t i o no f l d e c r e a s e sd u et oa ni n c r e a s ei nn e t w o r k l o a d ) 1 l o l 耧 姆 匿 图1 - 4 网络拥塞情况 送数据包数量 上述定义并不是很完整，因为网络负载的减少在某种情况下并不一定能让 用户的满意度增加。如图l - 5 ，假设：所有链路带宽为1 ，接收者满意度即为所 占用带宽。路由器队列调度规则为w f q ，流一( 从发送者s l 到r 1 ) 权值为1 ， 流毋( 从发送者s 2 到r 2 ) 权值为2 ，流f 3 ( 从发送者s 3 到r 3 ) 权值为l 。刚 开始，三个数据源均发送数据，此时r l 满意度为l 3 ，r 2 与r 3 满意度为2 3 。 当s 2 停止发送数据后，r l 的满意度变为1 2 ，而r 3 的满意度则变为1 2 ( 网络 负载降低，用户r 3 满意度反而降低) 。 第一章绪言 定义1 2 如果由于用户i 的网络连接性能( 带宽、延迟、延迟抖动等) 的 变化而导致其满意度降低，用户f 则认为网络发生拥塞( 彳n e t w o m i ss a i d t ob e c o n g e s t e df i r mt h ep e r s p e c t i v eo f u s e rti f t h es a t i s f a c t i o no f ld e c r e a s e sd u et oa m o d i f i c a t i o no ft h ep e r f o r m a n c e ( b a n d w i d t h ，d e l a y , j i t t e r , e t c jo f 向西n e t w o r k c d n e c t i 口”) 2 】。 关于网络拥塞的原因，也有许多解释，如认为低速链路、较慢的处理器和 较小的缓存是造成网络拥塞的原因，但大部分都不是很准确( 本文稍后会详细 分析造成网络拥塞的原因) 。事实上随着网络及其相关技术的发展，高速链路、 高性能处理器和大容量缓存( 相对而言) 已相当普遍，但网络拥塞现象并没有 得到消除或缓解，反而在当今拓扑结构、传输链路和应用需求异构化的场合更 容易产生更严重的网络拥塞1 3 】。 1 3 2拥塞控制及其属性 形象地说，搠塞控制就是通过一定的控制机制决定注入网络数据的数量和 速度，但严格定义拥塞控制却很困难。尽管如此，我们仍能给出理想拥塞控制 应具有的属性。在此之前，首先给出另外一个相关的术语的定义。 定义1 3 假设每个用户在抢占网络资源方面均是自私的( s e i r i s h ) ，当网络 处于某种状态，如果每个用户都不能继续增加其满意度，此时称网络处于n a s h 平衡点( n a s h e q u i l i b r i u m ) 。 理想的拥塞控制的属性应包括以下几点： 电子科技大学博士学位论文 1 1 稳定性( s t a b i l i t y ) 。即存在且仅一个n a s h 平衡点，拥塞控制应能收敛于 该n a s h 平衡点。 2 、 高效性( e f f i c i e n c y ) 。拥塞控制的效率包含两方面含义：一方面是拥塞控制 算法必须保证网络效率，使网络既不会欠载也不会过载；另方面是拥塞 控制应快速收敛于n a s h 平衡点。 3 ) 公平性( f a i r n e s s ) 。关于公平的定义有很多，其中最大最小公平( m a x m i n 向i r n e s s ) 被普遍接受。另外对t c p ( 网络中主流传输协议) 拥塞控制而言， 主要考虑不同连接间的公平性( 即协议内公平，i n t r a - p r o t o c o lf a i r n e s s ) ，对 非t c p 拥塞控制而言，则要考虑两种公平性，一是协议内公平；一是协议 间公平，即t c p 友好( t c pf r i e n d l y ) 。 4 ) 鲁棒性( r o b u s t n e s s l 。拥塞控制应能抵御恶意用户( 即不遵守拥塞控制) 的 行为，即能隔离恶意用户，防止降低其他用户的满意度。 5 ) 可扩展性( s c a l a b i l i t y ) 。对单播( u n i c a s t ) 而言，拥塞控制的可扩展性体 现在对不同规模网络、不同链路状况、不同端用户能力等均有效。对组播 ( m u l t i c a s t ) l 而言，拥塞控制的可扩展性除上述外，还应能处理大量异构接收 者的情况。 需要指出的是，上述5 种属性是拥塞控制的理想境界，大多数拥塞控制只 能达到其中几种要求。如当具有不同传输时延的t c p 连接竞争网络资源时，t c p 拥塞控制对具有较大传输时延的连接具有不公平性。尽管研究证明当竞争带宽 的各连接的传输时延按比例减小时，小传输时延的连接对大传输时延连接的抑 制性相对减弱，这种不公平性也减弱0 1 ，但t c p 拥塞控制的不公平性属性依然 存在。 1 4 i n t e r n e t 拥塞控制研究进展 正如1 1 节所述，今天的i n t e m e t 是一个规模庞大，业务种类繁多，通讯量 剧增的网络，其拥塞程度越来越剧烈。尽管t c p 拥塞控制在i n t e r n e t 的发展中 对保证i n t e r n e t 的稳定性和鲁棒性起着至关重要的作用，但随着互联网技术的 发展和网络情况的变化，仅靠单一的t c p 拥塞控制来管理网络业务已经显得越 来越力不从心了，设计和采用新的拥塞控制机制已迫在眉睫。 第一章绪言 网络拥塞控制一般可以分为两种：开环控制和闭环控制。开环控制是在网 络业务运行前，事先设计一个“好”的网络，确保它不会发生拥塞，而网络一 旦运行起来，就不再采取调节措施。开环控制比较典型的例子就是资源预留( 如 r s v p 协议) 。这种方法虽然是一种很直接的控制拥塞的方法，但由于事先精确 确疋业务特性儿乎小u j 再岜，凼此为保让服务麒量、避免删基，往往嵛费预留多 余的网络资源( o v e r a l l o c a t er e s o u r c e s ) ，很容易造成网络资源利用率低下。另 外，资源预留的复杂性和可扩展性差也是该方法不能被广泛采用的重要原因。 对于互联网这种网络业务不断变化的复杂系统，一般采用闭环控制。依据控制 论的观点，闭环控制中发送方接收反馈信息，并从反馈信息中推断( d e d u c e ) 网络状况，确定控制参数，并依据一定的控制算法调整发送速率，完成对网络 捌塞的响应。本论文除非特别指出，所有拥塞控制都是指闭环控制。 1 4 1 i n t e r n e t 网络拥塞的原因 网络产生拥塞的根本原因在于用户提供给网络的负载( b a d ) 大于网络资 源容量和处理能力。拥塞具体表现为报文时延增加、丢失、服务质量降低等。 搁塞一旦发生，如果不采取正确控制，拥塞会继续加重最终导致网络崩溃。文 献 5 分析了拥塞产生的直接原因，主要表现在三点： ( 1 ) 路由器存储空间不足；几个输入数据流共同需要同一个输出端口， 如果入口速率之和大于出口速率，在这个端口就会建立队列。如果没有足够的 存储空间，数据包就会被丢弃，对突发数据流更是如此。增加存储空间在表面 上似乎能解决这个矛盾，但如果路由器有无限存储量时，拥塞只会变得更坏， 因为数据包经过长时间的排队完成转发时，它们早已超时，源端认为它们已经 被丢弃( 实际上它们仍在网络中传输) ，因此重传这些数据包，从而浪费网络资 源，加重网络拥塞。 ( 2 ) 带宽容量相对不足；根据香农信息理论，任何信道带宽最大值即信 道容量c = b l 0 9 2 ( i + s n ) ( 为信道白噪声的平均功率，s 为信源的平均功率， 曰为信道带宽) 。所有信源发送速率之和胄必须小于或等于信道容量c ，如果 r c ，则在理论上无差错传输是不可能的，所以在网络低速链路( 相对而言) 处就会形成带宽瓶颈，网络就会发生拥塞。 ( 3 ) 处理器处理能力弱、速度慢。如果路由器的c p u 在执行排队缓存、 电子科技大学博士学位论文 更新路由表等操作时，处理速度跟不上高速链路，也会产生拥塞。同时低速链 路对高速c p u 也会产生拥塞。 上述是早期i n t e r n e t 网络发生拥塞的三个主要原因，t c p 拥塞控制较好地 解决了由这三种原因造成网络拥塞。可以想象，如果所有的端用户均遵守或兼 容t c p 控制，网络的拥塞则会得到很好的控制【6 。但令人遗憾的是，许多新的 网络应用采用了与t c p 不同的拥塞控制策略，甚至根本不采用任何拥塞控制， 它们给网络的稳定运行带来了巨大的威胁。造成i n t e r n e t 网络拥塞的原因已经 发生了变化，主要有以下两类： 1 、多媒体实时应用和部分用户自己编写的网络程序。这类应用为追求高的 服务质量，采用恒定的发送速率，称为非响应流或恶意流。当拥塞发生时，有 拥塞控制反应机制的t c p 数据流会按拥塞控制步骤进入拥塞避免阶段，从而主 动减小注入网络的数据量。但上述这类应用由于没有端到端的拥塞控制机制， 即使网络发出了拥塞指示( 如报文丢失，往返时延增加等) ，也并不降低发送速 率，结果导致遵守拥塞控制的t c p 流得到的网络资源越来越少，而没有拥塞控 制的数据流会得到越来越多的网络资源，这就导致了网络资源分配的严重不公 平。这种不公平最终会导致t c p 流饿死，直至网络崩溃。 2 ) 组播应用的推广一方面节省了网络资源，降低了网络管理费用，但与此 同时，如果组播应用不能对网络拥塞做出正确响应，将会给i n t e m e t 带