（信号与信息处理专业论文）ip+qos中拥塞控制技术的研究与应用.pdf

i pq o s 中拥塞控制技术的研究和应用 摘要 po o s 中拥塞控制技术研究和应用 摘要 当今不断进步的网络技术刺激着网络应用不断发展，而网络应用 的不断发展对网络质量提出了更高地要求。最初的d 网络采用尽力 而为模式，主要针对非实时的数据业务。如今在传统的i p 网络上需 要承载各种数据业务、电信业务以及多媒体业务。但传统t c p i p 协 议体系结构不能保证网络的服务质量。人们寻求各种的i pq o s 解决 方案。 q o s 是网络在传输数据流时要求满足的一系列服务请求，具体可 以量化为带宽、延时、延时抖动、丢失率、吞吐量等性能指标。q o s 反应了网络元素( 应用程序、主机和路由器等) 在保证信息传输和满 足服务要求方面的能力。作为q o s 技术中最为核心的拥塞控制技术， 成为了当今网络技术中的热点。 本文首先描述了当今i p 网络的现状，分析了在i p 网络中实现 q o s 的必要性。之后本文对i pq o s 技术进行了介绍。本文介绍了两 种q o s 模型，综合服务模型和差分服务模型，并分析了两种q o s 模 型各自的优缺点。 之后本文对q o s 体系结构中的拥塞控制组件进行了详尽的介绍。 在没有任何协商和请求许可机制的资源共享网络中，拥塞状况是不可 避免的。拥塞的发生是传统i p 网络的固有属性。本文分析现有的各 种拥塞控制机制，剖析了当前较为流行的流量整形、队列管理和队列 调度算法，对它们的优劣特点进行了全面的比较。 最后本文介绍了拥塞控制技术在网络产品中的应用。分析了 c i s c o 和华为3 c o m 的两款交换机所采用的拥塞控制策略。之后还结 合笔者在实验室期间参与的研发项目，介绍了如何选择拥塞控制算 法，以及如何在f p g a 芯片上实现拥塞控制。 关键词服务质量综合服务差分服务拥塞控制队列管理 队列调度流量整形 第i 页 i pq o s 中拥塞控制技术的研究和应用 摘要 r e s e a r c ha n di m p l e m e n to f c o n g e s t l o nc o n t r o li ni pq o s a b s t r a c t t r a d i t i o n a li p 。b a s e dn e t w o r kw i t hb e s t _ e f f o r tf e a t u r ei sn o t d e s i g n e d f o rr e a l - t i m es e r v i c e sd e l i v e r y n o w ，i p b a s e dn e t w o r kn e e d st oc a r r ya l l k i n d so fs e r v i c e si n c l u d i n gt r a d i t i o n a ld a t as e r v i c e s ，m e d i as e r v i c e sa n d t e l e c o m m u n i c a t i o ns e r v i c e s q o sg u a r a n t e ei sa b i gp r o b l e mf o ri p - b a s e d n e t w o r kt h a tn e e d st ob es o l v e d e f f i c i e n t l y t h ep r i m a r yg o a lo fq o si st op r o v i d ep r i o r i t yi n c l u d i n gd e d i c a t e d b a n d w i d t h ，c o n t r o l l e dj i t t e ra n dl a t e n c y ，a n di m p r o v e dl o s sc h a r a c t e r i s t i c s r e c e n t l y ，t h er e s e a r c ho fq o s i ni p - b a s e dn e t w o r ki sa t t r a c t i n gm o r ea n d m o r e a t t e n t i o n t h e r e f o r e ，a s t h ec o r eo fq o s ，t h e t e c h n o l o g y o f c o n g e s t i o nc o n t r o li sb e c o m i n g t h eh o t s p o ti nt h i sf i e l d f i r s t l y ，t h ep a p e ra n a l y z e s t h en e c e s s i t yo f i m p l e m e n t i n gq o s i nt h e c u r r e n ti p - b a s e dn e t w o r k ，a n di n t r o d u c e sb o t ht h ec o n c e p t i o no fi pq o s a n dt w ok i n d so fs e r v i c e m o d e l i n t e g r a t e d s e r v i c e sm o d e l ( i n t s e r v m o d e l ) a n d d i f f e r e n t i a t e ds e r v i c em o d e l ( d i f f s e r vm o d e l ) m o r e o v e r ，i t d i s c u s s e se a c hm o d e l sp r o sa n dc o n s t h e n ，t h ep a p e ri n t r o d u c e st h ec o n g e s t i o nc o n t r o lm e c h a n i s m si n g r e a t d e t a i l s t r a f f i c c o n g e s t i o n i si p b a s e dn e t w o r kn a t u r a l c h a r a c t e r i s t i c sb e c a u s ei ti sar e s o u r c e - s h a r i n gn e t w o r kw i t h o u tr e s o u r c e n e g o t i a t i o n a n da d m i n i s t r a t i o nm e c h a n i s m t h ep a p e r a n a l y z e s s o m e p o p u l a rt r a f f i c c o n t r o l a l g o r i t h m s ，q u e u em a n a g e m e n ta l g o r i t h m s a n d q u e u es c h e d u l i n ga l g o r i t h m s ，a n dc o m p a r e s t h e m f i n a l l y ，t h ep a p e rd e s c r i b e sh o w t h ec o n g e s t i o nc o n t r o lm e c h a n i s m i s i m p l e m e n t e di n n e t w o r kp r o d u c t i o n s o m es o l u t i o n si nt h es w i t c h d e s i g n e db y t h ec i s c oa n dh u a w e i 一3 c o ma r ea l s o p r e s e n t e di nt h ep a p e r a d d i t i o n a l l y ，t h ep a p e ri n t r o d u c e s h o wt oc h o o s eb e t t e r c o n g e s t i o n c o n t r o la l g o r i t h ma n dh o wt oi m p l e m e n tt h ea l g o r i t h mi nf p g aw i t ht h e 第i i 页 1 pq o s 中拥塞控制技术的研究和应用摘要 e x a m p l e o fa u t h o r sw o r ki nt h el a b o r a t o r y k e yw o r d sq o s ，i n t s e r v ，d i f f s e r v ，c o n g e s t i o n c o n t r o l ，q u e u e m a n a g e m e n t ，q u e u es c h e d u l i n g ，t r a f f i cs h a p i n g 第m 页 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论 本人签名： 处，本人承担一切相关责任。 日期：盘咝：i ：翊 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅：学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名：歇泐 1 l 1 适用本授权书。 e t 期：曼竺：兰当 日期： = ：；堡 i pq o s 中拥塞控制技术的研究和应用 1 1开题背景 第一章绪论 当今i p 网络的普及性决定了球网络在当今传输领域的不可替代性。以太网 技术已经垄断了l a n 领域，随着1 0 g 标准的正式通过，光纤以太网技术的出现 及r p r 技术的逐渐成熟，推动了以太网技术进入城域网领域。尽管以太网的价 格便宜、配置灵活、维护简单、应用广泛，但是正是因为其协议的简单性、开放 性，采用尽最大努力( b e s t - e f f o r t ) 模式，它对m 网络之上的业务不能提供足够 的服务质量保证、安全保密需求的保证。 当前提出的电信级以太网对传统的以太网技术提出了新的要求，包括网络可 靠性、网络模型、q o s 保证机制、流量工程机制、故障保护机制、业务提供能力、 网络和用户安全机制以及维护管理等各个方面。目前的m 网络离电信级的m 网 络还有很大的差距，在许多方面需要进行深入的研究，对现有的i p 网络进行改 进。 本论文针对当前球网络的热点问题一口q o s ( q u a l i t yo f s e r v i c e ) 作为研究方 向，对现有的各种解决方案和技术进行了分析，对q o s 中各种组件进行了介绍， 并对拥塞控制技术进行重点研究。 1 2论文结构 本文后续章节安排如下： 第二章对i pq o s 的体系结构进行了分析。分别介绍了综合服务模式和差分 服务模式的q o s 体系结构。 第三章介绍了i pq o s 中拥塞控制技术，介绍各种不同的拥塞控制机制。剖析 了各种流量整形、队列管理和队列调度算法，对它们的特点进行了比较。 第四章介绍了拥塞控制技术在实际的网络产品中的应用。 第1 页 i pq o s 中拥塞控制技术的研究和应用i p q o s 体系结构 第二章 i pq o s 体系结构 2 1i pq o s 概述 q o s ，即服务质量。q o s 在r f c 2 3 8 6 中定义为：q o s 是网络在传输数据流时 要求满足的一系列服务请求，具体可以量化为带宽、延时、延时抖动、丢失率、 吞吐量等性能指标。q o s 反应了网络元素( 应用程序、主机和路由器等) 在保证 信息传输和满足服务要求方面的能力。 最初的i p 网络主要针对非实时的数据业务，i p v 4 对实时业务支持不够。尽 管在i p 协议中有服务类型t o s 字段，但是t c p i p 协议体系不能保证网络的服务 质量q o s 。随着网络的发展，各种基于i p 网络的新的应用服务也越来越多。当 前火热的三网融合正是在以i p 为基础的公共网络上承载各种数据业务、电信业 务以及视频媒体业务。各种业务特性决定了其在i p 网络上传输所要求的不同传 输质量指标，这种现实服务质量与服务质量需求的冲突日益加剧。i p 网络的尽 力服务不可能识别和区分出网络中的各种通信类别，传统网络的尽力服务模式 ( b e s t e f f o r t ) 已不能完全满足当今各种应用的需要。例如v o i p 技术，作为一种 实时的业务，对数据包在网络上的延时非常敏感，但对丢包率并无特别严格要求。 又如传统的e - m a l t 业务，对于网络延时特性就没有特别要求，但是对于数据包 传输的正确与否十分敏感。 采用不断的提高网络容量的方法支持q o s 是不现实的。q o s 的实现是一个全 网的概念，片面的提高网络体系中其中一个部分的容量可能造成更严重的拥塞直 至网络崩溃。保证网络质量首先是使网络有较合理的设计和配置，尽量避免网络 瓶颈的存在。其次可以使用呼叫抑止，为每个用户建立端到端的资源预留，当资 源不够时，禁止一些用户向网络发送数据报；也可以通过设定优先级，在网络拥 塞时，使某些用户的i p 包有更好的机会穿越网络。 i e t f ( 互连网工程任务组) 等标准化组织成立了研究组专门研究不同的结构 及其实现，开展多项研究项目，如：i n t e m e t 2p r o j e c tq b o r t es t a r t e d ( 1 9 9 8 ) 。1 7 0 多个大学，4 0 多个著名企业，3 0 多个组织加入了该研究计划。 为解决i p 网络q o s 问题，i e t f 组织提出了两种服务模型：综合服务模型 ( i n t e g r a t e ds e r v i c e sm o d u l e ，i n t s e r vm o d u l e ) u 1 和差分服务模型( d i f f e r e n t i a t e d s e r v i c e sm o d u l e ，d i f f s e r vm o d u l e ) 2 1 第2 页 i pq o s 中拥寒控制技术的研究和应用 i p q o s 体系结构 2 2 综合服务模型( i n t s e r vm o d u l e ) 2 2 1模型简介 i n t s e r vm o d u l e 由i e t f 的i n t s e r v 工作组于1 9 9 4 年在r f c1 6 3 3 中提出。 i n t s e r vm o d u l e 是一种综合服务模型，可以满足多种的端到端的q o s 服务。l n t s e r v 定义了三种服务类型。 质量保证型服务( g u a r a n t e e ds e r v i c e s ) 2 1 ：对带宽、时延、分组丢失率 提供了定量的质量保证，常用于需要严格保证无丢失、准确到达的实时 传输应用上。 可控负载型服务( c o n t r o l l e d - l o a ds e r v i c e s ) t 4 _ l ：在轻负载下和b e s t ，e f f o r t 类似：在网络负载加重时给用户提供一种类似在网络轻负载情况下的服 务。 尽力而为型服务( b e s t - e f f o r ts e r v i c e s ) ：类似于目前i n t e m e t 网上提供的 服务，是一种尽力而为的工作方式，基本无任何质量保证。 i m s e r v 依靠资源预留协议( r e s o l l r c er e s e r v a t i o np r o t o c o l ，r s v p ) d 逐节点 地建立或者拆除每个流的资源预留状态( s o t ts t a t e ) ；依靠接纳控制( a d m i s s i o n c o n t r 0 1 ) 决定链路或网络节点是否有足够的资源满足q o s 请求；依靠分类器 ( c l a s s i f i e r ) 将收到的i p 分组进行分类，根据分类的结果把把分组放到相应的队 列中，最后由分组调度器( p a c k e ts c h e d u l e r ) 将分组转发出去。i m s e r v r s v p 模 块结构如图。 预留设置消息 甲一田由：= ：= _ 囡 厂1j 笙型| - - j 骓 喊 卤1 主机 路由器 图2 - 1i n t s e r v r s v p 模块功能结构图 i n t s e r v 体系的核心是r s v p 。在传送数据之f i 口r s v p 要在发送者、接收者及沿 途的路由器间协商q o s ，通知网络它自己的流量参数和需要的特定服务请求，保 留带宽、时延等，进行资源预留，以保证在传送时的用) 5 q o s 要求。r s v p 是单 第3 页 i fq o s 中拥塞控制技术的研究和应用i p q o s 体系结构 向的预约方式，由接收者开始向发送者要求资源预约。r s v p 本身不是一个路由 选择协议，而是用来沿着所选定的路由预留资源的信令协议。其预留建立在流的 基础上，流由坤v 4 的地址字段或i v 6 的流标识来指定，路由器根据为该流分配的 资源来调度分组的转发。发送方主机一般在收到网络的确认消息，即确认网络已 经为这个应用程序的报文预留了资源后，才开始发送报文。同时主机发出的报文 应该控制在流参数的范围之内。 接纳控制( a d m i s s i o nc o n t r 0 1 ) ：它基于用户和网络达成的服务协议，对用户 的访问进行一定的监视和控制，有利于保证双方的共同利益。 分类器( c l a s s i f i e r ) ：根据预置的一些规则，对进入路由器的每一个分组进 行分类。分类的依据通常是分组中的某些域：p 源地址、i p 目的地址、上层 协议类型、源端口号、目的端口号；分组经过分类后被放到不同的队列中等待接 受服务。 队列调度( s c h e d u l e r ) ：基于一定的调度算法对分类后的分组队列进行调度 服务。 2 2 2模型特点 i m s e r v 是基于流的( 单独的或聚集的) 、状态相关的体系结构，依赖于每个 流的状态和针对每个流的管理。这种实现机制使i n t s e r v 能够提供较状态无关的体 系结构，具有更高的灵活性和更好的服务级别保证，但同时也导致了i n t s e r v 的可 扩展陛问题和鲁棒性问题，后果是实现较复杂，难于应用。 在i n t s e r v 体系结构中，网络中每个节点都要维护多类数据库( 例如，对于使用 链路状态协议的q o s 路由，路由器必须同时维护链路状态数据库和q o s 路由表； 网络中的资源管理器必须维护资源数据库等) ，并实现较复杂的功能模块( 如资 源预留、接纳控制、包分类、包调度等) r s v p 信令协议提供q o s 协商机制：各 网络节点建立和维护预留信息，并根据自身资源状况对用户的预留请求进行接纳 控制，数据传输时各网络节点监控传输流，并提供相应服务。这种完全分布式的 控制造成了极大的复杂性，导致路由器要维护的信息量大，实现较复杂。 总而言之，q o s 和i n t s e r v 在整个i n t e m e t n 络应用时，尽管基于流的q o s 资源 预留、调度处理以及缓冲区管理，有利于提供q o s 保证，但是系统开销过高，对 于大型网络存在可扩展性问题。因而，单纯的i n t s e r v 结构无法大范围使用，以其 现在的形式将不会在i n t e m e t 中得到广泛应用。 第4 页 i pq o s 中拥塞控制技术的研究和应用 i p q o s 体系结构 2 3 差分服务模型( d i f f s e r vm o d u l e ) 23 1模型简介 在i n t s e r v 体系的发展遭到巨大障碍时候，d f f s e r v 应运而生。i e t f 在r f c 2 4 7 5 中提出d i f f s e r vm o d u l e ，旨在定义一种实施i pq o s 且更容易扩展的方式， 以解决i n t s e r v 扩展性差的缺点。d i f f s e r v 简化了信令，对业务流的分类颗粒更 加粗。它通过汇聚( a g g r e g a t e ) 和p h b ( p e rh o pb e h a v i o r ) 的方式来提供一定程 度上的q o s 保证。 d i f f s e r v 模型中提供了三种不同的服务类型，以满足不同业务的服务要求。 确保服务( a s s u r e ds e r v i c e ) ：确保服务对应的p h b 是确保转发( a s s u r e d f o r w a r d i n g ，a f ) 。确保服务是根据用户和i s p 签定的服务层协议( s e r v i c e l e v e la g r e e m e n t ，s l a ) 提供给用户可靠的服务，保证在网络拥塞时仍能保 证用户拥有一定量的预约带宽，使用户摆脱在“b e s t - e f f o r t ”传输时无法 把握自己实际占用带宽量的无奈窘态。确保服务只考虑带宽和丢失率， 不涉及延迟和抖动。 奖赏服务( p r e m i u ms e r v i c e ) 。奖赏服务所对应的p h b 是加速转发 ( e x p e d i t e df o r w a r d i n g ，e f ) 。奖赏服务是为用户提供低延时、低抖动、 低丢失率和保证带宽的服务。它是目前所定义的服务级别最高的差分服 务种类，用户可以享受类似专线的服务质量，因而奖赏服务也称为“虚 拟专线”服务。 尽力而为型服务( b e s t - e f f o r ts e r v i c e s ) ：是目前i m e m e t 网上提供的服务， 是一种尽力而为的工作方式，基本无任何质量保证。 d i f f s e r v 的核心思想是“边缘分类，内部转发”。d i f f s e r v 体系是层次结构 化，被划分为d s 区域( d i f f e r e n t i a t e ds e r v i c e sd o m a i n ) 和d s 区( d i 恐r e n t i a t e d s e r v i c e s r e g i o n ) 两级。d s 区域是由一些相连的d s 节点构成的集合，它们遵循 统一的服务提供策略并实现一致的p h b 组。多个d s 区域组成d s 区，d s 区内 的各个d s 区域可以支持不同的p h b 、有不同的服务提供策略，它们之间通过服 务层协议( s l a ) 和传输协议( t r a f f i cc o n d i t i o n i n ga g r e e m e n t ，t c a ) 协调以提供 跨区域服务。 第5 页 i pq o s 中拥塞控制技术的研究和应用 i p q o s 体系结构 图2 2 差分服务的边缘路由器和核心路由器的功能 在串连d s 区域和非d s 区域的网络边界点，边缘路由器将数据流按预先制 定的t c a 要求进行简单分类( c l a s s i 母i n g ) 、标记( m a r k i n g ) 、整形( s h a p i n g ) 和丢弃( d r o p p i n g ) ，聚合为不同的流组，这种聚集的流组信息存储在每个i p v 4 包头的t o s 字段中或i p v 6 的业务流量类型字段，称为差分服务标记域。 内部节点在调度转发i p 包时根据包头的d s c p ( d i f f e r e n t i a t e ds e r v i c e sc o d e p o i n t ，d s c p ) 选择提供特定质量的调度转发业务，其外特性称为逐点行为( p h _ b ) 。 网络边界对单流做分类聚合与网络内部对聚集流提供特定质量的调度转发服务， 这两个过程通过i p 包头的d s c p 协同工作。 如图2 3 ，差分服务标记域分为两部分，6 位d s 标记( d s c p ) 和2 位保留 字段( c u r r e n tu n u s e d ，c u ) 。目前c u 字段也被用于拥塞指示( e x p l i c i t c o n g e s t i o n n o t i f i c a t i o n 。e c n ) 。 图2 - 3i p 包头的差分服务标记域 采取边缘分类，核心转发的模式的d i f f s e r v 体系具有以下特点： - 简化网络内部节点的服务机制：在内部节点只进行简单的调度转发，而 流状态信息的保存与流监控机制的实现等只在边界节点进行，内部节点 是状态无关的。 简化内部节点的服务对象：采用汇聚传输控制，服务对象是流聚集而非 单流，单流信息只在网络边界保存和处理。 d i f f s e r v 模型分成了两个组成部分，数据转发部分和管理部分。d i f f s e r v 把 数据转发部分和属于管理部分的接纳控制和资源分配独立开来，这种分离与 第6 页 i pq o s 中拥塞控制技术的研究和应用i p q o s 体系结构 i n t e m e t 中将数据转发模块与路由模块独立的思想吻合。相比之下，a t m 和 i n t s e r v 都是在连接建立的阶段，将数据转发与接纳控制、资源分配结合在一起， 保证数据流的服务质量。 2 3 2模型特点 d i f f s c r v 是基于i n t s c r v 构架中遇到的问题而提出的模型，其优点正是i n t s e r v 模型的缺点，而其缺点也真是i n t s e r v 的优点所在。 d i f f s e 的优点有： 1 扩展性好。d s 字段只是规定了有限数量的业务级别，状态信息的数 量正比于业务级别，而不是流的数量。d i f f s e r v 将复杂的服务质量保 证通过d s 字段转换为先进的单跳行为，从而大大减少了信令的工作。 2 便于实现。只在网络的边界上才需要复杂的分类、标记、管理和整形 操作。i s p 核心路由器只需要实现行为聚集( b a ) 的分类，因此实现 和部署区别型业务都比较容易。 d i f f s e r v 的缺点是： 1 d i t t s c r v 为i pq o s 奠定了宝贵的基础，但还是没有办法完全依靠自己 来提供端到端的q o s 结构。d i f f s e r v 需要大量网络单元的协同动作， 才能向用户提供端到端的服务质量。鉴于这些组件高度分散的特点和 对它们进行集中管理的需要，必须有一个全局的带宽管理对全局资源 进行动态管理。 2 d i f f s c r y 已有的框架都是基于单播构架的，处理组播会出现一系列的 问题。比如“被忽略的预留子树问题( n e g l e c t e dr e s e r v a t i o ns u b t r e e ， n r s ) ”，“异构组播问题”和“发送方任意动态改变”问题。 3 对于被分类到同一组流当中的微流的公平性无法得到保证。例如在同 一a f 组，终端带有拥塞控制机制的流和终端没有拥塞控制机制的流 具有不同的带宽竞争能力，就存在不公平性。 第7 页 i pq o s 中拥塞控制技术的研究和应用拥塞控制 第三章拥塞控制 3 1 拥塞控制概述 拥塞是一种持续过载的网络状态，此时用户对网络资源( 包括链路带宽、存 储空间和处理器处理能力等) 的需求超过了其固有的容量。 就i n t e m c t 的体系结构而言，拥塞的发生是其固有的属性，因为在事先没有 任何协商和请求许可机制的资源共享网络中，几个i p 分组同时达到路由器，并 期望经过同一个输出端口转发的可能性是存在的。显然，不是所有的分组可以同 时接受处理，必须有一个服务顺序。中间节点上的缓存为等候服务的分组提供一 定的保护。如果此状况具有一定的持续性，当缓存空间耗尽时，节点只能丢弃分 组。表面上，增大缓存总可以防止由于拥塞引起的分组丢弃，但n a g l e ( 1 9 8 7 ) 发现如果缓存空间无限大，拥塞情况不会变好，反而会更糟。随着缓存的增加， 端到端的时延也相应增大，而超时的分组同样需要重传。因此，过大的缓存空间 反而使得已经拥塞的网络状况迸一步恶化，因为不断重传的分组进一步浪费了网 络的可用带宽。 拥塞导致的赢接结果是网络的吞吐量大幅度下降，端到端时延急剧增加，甚 至有可能使整个系统发生崩溃。当网络处于拥塞崩溃状态时，微小的负载增量都 将使网络的有效吞吐量( t h r o u g h p u t ) 急剧下降。 网 络 吞 吐 量 无拥墓 轻度佣毫 严重拥喜 1-。 羲壶器 数据a 默 妒磐丢弗t、 a 8 负载 图3 - 1 网络性能和网络负我的关系 图3 1 刻画了网络吞吐量和负载之间的关系。当网络的负载较小时，吞吐量 和负载曾线性关系；当负载达到a 点( 膝点k n e ep o i n t ) 之后，随着负载的继续 增加，吞吐量的增量变化的很小；当负载超过了b 点( 崖点c l i f fp o i n t ) 之后， 吞吐量却急剧下降。通常将膝点附近称为拥塞避免区，膝点和崖点间的区域成为 拥塞恢复区，而崖点之后的区域称之为拥塞崩溃区。 第8 页 i pq o s 中拥塞控制技术的研究和应用 拥寒控制 为了最大限度地利用资源，网络工作在轻度拥塞状态时是最理想的工作状 态，但是这也增加了滑向拥塞崩溃的可能性，需要通过一定的方法来加以约束和 限制，即所谓的拥塞控制机制，也是d i f f s e r vm o d e l 中的重要组件。 像计算机网络这样的复杂系统中的问题，都能从控制论的角度进行解释。这 种方法导致所有解决方案被分为两类：一类是开环，一类是闭环。 开环的关键在于，它致力于通过良好的设计来避免问题的出现，确保问题一 开始时就不会发生。一旦系统安装并运行起来，就不再做任何中间阶段的更正。 做开环控制的工具的功能包括决定何时接受新的通信，何时丢弃分组，以及丢弃 哪些分组，还包括在网络的不同点作计划表。所有这些的共同之处在于，它们在 做出决定时并不考虑当前网络的状况。 与之相比较，闭环的解决方案是建立在反馈环路的概念之上的。当用于拥塞 控制时，这种方法有3 个部分：( 1 ) 监视系统，检测何时何地发生了拥塞。( 2 ) 将此信息传送到可能采取行动的地方。( 3 ) 调整系统操作以更正问题。 有多种度量可用来监视子网的拥塞状况。其中主要的有：因缺少缓冲区空间 而丢失分组的比例，平均队列长度，超时和重发分组的数量，平均分组延迟，以 及标准方差分组延迟。对于以上所有因素，数值的增加就表示发生拥塞可能性的 增加 反馈环路的第二步是将拥塞信息从检测点传达到可对此采取行动的地方。最 显而易见的方法就是检测到拥塞的路由器向信源发送一个分组。当然，这些额外 的分组恰好在子网拥塞时又增加了子网的负荷。还可以采用另外的方法。例如， 可以在每个分组中保留一位或一个字段，当路由器发现拥塞状态超过监测临界值 时，就在所有发送分组中填允这一个位或字段，以警告它的邻居要发生拥塞了。 还有另一种方法，就是让主机或路由器定期发送证实分组来显式地询问拥塞状 况。这一信息可用来使通信量绕过有问题的区域。 在所有的反馈方案中。都希望主机能够根据拥塞的信息采取适当行动以减少 拥塞。要正确工作，必须认真调整时间幅度，如果每次有两个分组相继到达时， 路由器就产生一个s t o p 消息，路由器每空闲2 0 m s 又生成一个g o 消息，那么 系统将会摇晃不定。另一方面，如果它在产生任何消息之前都先等待3 0 m i n ，以 确保准确无误。那么拥塞控制机制就会因为反应太慢而毫无用处。要想工作正常， 就得取某一平均值，但取一个正确的时间常量也不是件简单的事。 现在已经出现了很多拥塞控制方法： 1 流量整形。 突发的流量往往是造成网络拥塞的罪魁祸首。通过在网络边缘对入网的业务 流进行流量整形，保持网络流量的平滑，那网络状态将变得可预测，网络拥塞的 第9 页 i pq o s 中拥塞控制技术的研究和应用 拥塞控制 情况将容易被避免。所以说流量整形是网络拥塞的避免方法。 2 t c p 流量控制技术。 据统计，i n t e m e t 上9 5 的数据流使用的是t c p 协议，而非弹性的u d p 业 务只占据很小的份额。由此可见t c p 流量控制是i n t e m e t 正常运行的基础。在 i n t e m e t 设计的初期，接收端驱动的t c p 流量控制是唯一可行的拥塞控制方法。 t c p 流量控制遵循两个主要原理：实现流控自同步( s e l f - c l o c k i n g ) 的分组 守恒定理；o 加性增加倍乘减小( a d d i t i v ei n c r e a s ea n dm u l t i p l i c a t i v ed e c r e a s e ， a i m d ) 的窗口管理算法。a i m d 依赖简洁的实现机制，在多个相互冲突的目标 之间实现了较为理想的平衡与协调。虽然无法保证具有不同属性的终端系统( 比 如不同r t t 时间、不同分组大小、经历不同跳数的拥塞链路等) 能够分配到等 量的带宽，但却能确保大致相似的用户得到基本相同的网络资源。 t c p 流量控制技术的关键是窗口管理。t c p 流量控制多个改进和增强版本的 焦点都集中在窗口管理上。在1 9 8 8 年，v a nj a c o b s o n 在他的论文【复1 中指出了t c p 在控制网络拥塞方面的不足，提出了“慢启动”( s l o ws t a r t ) 和“拥塞避免” ( c o n g e s t i o n a v o i d a n c e ) 算法。之后研究者为了完善性能，又不断增加了快速重 传和快速恢复机制，形成了称为t c pt a h o e ，t c pr e n o 和t c ps a c k 等多种版 本。围绕这t c p 流量控制方法的拥塞控制机制一直是i n t e m e t 网络研究的热点。 3 端到端的拥塞控制机制。 t c p 流量控制算法在探索空闲带宽和响应拥塞的过程中，造成了信源速率的 大幅变化。虽然“尽力而为型”( b e s t e f f o r t ) 的i m e m e t 业务能够很好的适应这 种变化，但是有些应用则显得极不适应，比如流媒体业务更希望拥塞控制机制对 于拥塞的响应能够缓慢一些，从而有一个较为平滑的带宽占用以更好的匹配实时 生成的业务码流。在组播业务中t c p 流量控制更显得不适合，因为它需要组内 的所有接收者都对接收的分组给予确认，从而产生了许多难以克服的技术问题。 一方面，需要一致的t c p 流量控制来达到公平的带宽分配；另一方面，为了适 应业务的特点又期望放弃t c p 流量控制机制。针对于这种矛盾的存在，提出了 “t c p 兼容性”( t c p c o m p a t i b i l i t y ) 概念。这种新机制的基础是一个重要的研 究结论：t c p 流占用的带宽正比于分组丢失率平方根的倒数【7 1 。以及以此理念 为出发的各种新的拥塞控制算法，其中包括t c p f r i e n d l y 的速率控制( t f r c ) 和其他基于方程的拥塞控制、二项式拥塞控制、具有不同a i m d 参数的拥塞控 制算法以及接收端t c p 仿真机制( t c pe m u l a t i o na tr e c e i v e r ，t e a r ) 等。 4 中间节点上的增强机制。 在h a t e m e t 技术的发展初期，设计者遵循一个技术理念：所有与流相关的状 态都应该尽量在终端系统上实现和维护。这一原则使得早期的拥塞控制都是在终 第1 0 贞 i pq o s 中拥塞控制技术的研究和应用拥塞控制 端系统上实现和维护，对于网络中间节点所能发挥的作用考虑较少。勿庸置疑， 这一原则提供的可扩展性在i n t e r a c t 的发展初期极大的促进了i n t e m e t 网络的快 速发展。但是随着应用要求的日益丰富和技术的不断发展，想要完全依赖终端系 统上的算法和策略是很难满足诸如q o s 这样复杂的应用需求。况且i n t e m e t 有许 多异构的自治域通过松耦合方式组成，具有与生据来的分散特性，网络中间节点 能更及时，更准确的了解网络中的拥塞状态。在网络的中间节点设备上增加拥塞 控制算法和策略，能使网络更有效地避免拥塞，或者更早从严重的网络拥塞状态 中恢复过来。对路由器的扩展要受继承性和延续性的限制，否则将影响技术的实 用性。现有在中间节点路由器上实施的增强机制和功能扩展主要是队列管理和队 列调度策略。队列管理通过控制队列的占用率避免拥塞的发生，以及从拥塞中恢 复，并且间接影响带宽的分配。队列调度直接管理输出链路的带宽资源。 本章以下部分将对流量整形，队列管理和队列调度技术进行进一步的介绍。 3 2 流量整形 流量整形是调整数据传输的平均速率( 以及突发性) 。与之相比，t c p 滑动 窗口协议只是限制一次能传送数据的数量，而不是传送的速率。最基本的流量整 形算法有漏桶算法( 1 e a k e db u c k e ta l g o r i t h m ) 和令牌桶算法( t o k e nb u c k e t a l g o r i t h m ) 。 3 2 1漏桶算法 假设有一个底部有- - j t l 的桶，如图3 2 中所示。不管桶进水的速率是多大， 只要桶中有水，水从桶中往外漏的速率是恒定的p ，一旦桶空了，速率便为零。 而且，只要桶一满，再往里流的水都一律从桶边溢出去，流失了( 也就是说，不 再在桶底小孔的水流中出现) 。 图3 - 2 漏桶算法模型 第1 1 员 i pq o s 中拥塞控制技术的研究和应用拥塞控制 同样的思想也可以应用到分组的处理中。该算法首先由t u r n e r ，( 1 9 8 6 ) 提 出，被称作漏桶算法。漏桶算法有三个基本参数： - 参数c ：桶内不断变化的数据量 - 参数b c ：许诺的数据流量，即限定的数据输出速率 - 参数b e ：允许的突发数据流量。桶内的数据量不能超过b c + b e ，若超过 就将溢出丢弃。 漏桶算法的实现是很容易的，漏桶本质上是一个有恒定服务时间的单服务器 排队系统，具有限定的输出速率b c ，同时允许一定的突发数据量b e 。主机发送 的每一个分组都送到队列中排队，如果队列满则分组被丢弃，同时队列以速率 m i n b c ，c 】向网络中发送分组。如果分组的长度是固定的，那么让队列每隔一个 固定的时间发送一个分组即可实现恒定速率。如果分组的长度是可变的，则应规 定队列每次可以发送的最大字节数，比如每次最多可以发送1 3 个字节，则可以使 用一个字节计数器，每次发送前将字节计数器初始化为n ；如果连续m 个分组都 比较短，分组长度总和小于n ，则可以一次性发送m 个分组，并且每发送一个分 组，就从字节计数器中减去该分组的字节数；当剩余的字节数不够发送下一个分 组时就停止发送，等待下一次机会，同时字节计数器中的值变为无效，在下一次 发送时重新初始化为n 。 漏桶机制将主机中用户进程的不均匀分组流转换为输入网络的均匀分组流， 使突发的数据流变得平滑，大大减少系统拥塞的概率。 3 2 ，2令牌桶算法 令牌桶的算法的模型如下图： 晰中装 若令牌 网络 ( a )( b ) ( a ) 育五十丹组等待发送( b ) 育兰个分组通过 图3 - 3 令牌桶算法模型 网络 第1 2 页 i pq o s 中拥塞控制技术的研究和应用拥寒控制 基本的漏桶算法强迫输出数据流保持一个固定的平均速率，而不管突发通信 量的大小。既是说，漏桶把业务流的突发特性完全滤除，这可能对一些应用带来 负面影响。对很多应用而言，希望当大的突发通信量到来时，输出速率也相应增 加一点，在一定程度上保持业务流的突发特性。令牌桶算法就是这样的一种算法。 在这个算法中，令牌以一定的速率注入令牌桶令牌桶有一定的容量，在业务流 速率较低时可以缓存令牌，在业务流突发数据时可以使用以前缓存的令牌，保持 一定的突发度。当令牌桶没有缓存的令牌时，业务流就只能以令牌注入的速率通 过。 令牌桶的一个问题是，它允许在一定的时间内以业务流突发速率来传输速 率，但当令牌桶为空时报文的通过速率迅速降至令牌的注入速率。这种整形后的 速率曲线与业务流的统计速率曲线也有较大的差异。常用的一种办法是在令牌桶 之后再加一个漏桶，以平滑令牌捅产生的高速突发流量，尽量使平滑后的速率曲 线符合业务流的统计特性，减少对业务流的损伤。 3 2 3流量整j i ；算法比较 表3 - t 流量整形算法比较 漏桶算法令牌桶算法 区别一漏桶算法不允许空闲主机保留发送权，以备以后有大的 突发通信量出现时使用。令牌桶算法却允许，最大到桶 的大小n 。这一特性意味着多达n 个分组的突发通信量可 以马上传送，允许一些输出流中的突发性，以及对输入 的突然增长提供更快的反应。 区) j a j -漏桶不允许突发流量以突发速率进入网络，只能以恒定 的速率进入。令牌桶算法允许突发流量以突发速率进入 网络