（控制科学与工程专业论文）ip网络中拥塞控制和可扩展组播路由研究.pdf

p 网络巾拥塞控制和可扩展组播路由研究浙江大学博士学位论文 p 网络中拥塞控制和可扩展组播路由研究 博士研究生：陈尚兵指导教师：钱积新教授 捅要 l i n t e m e t 已成为一个重要的和无处不在的基础设施，人们对网络性能、服务 内容和安全性的期望不断提高。但是“尽力而为”服务仍是目前i n t e m e t 中主 要的一种服务类别，所有分组在网络中被同等对待，缺少有效的管理，局部的 拥塞经常发生，导致网络性能下降、应用的分组丢失和数据抖动，不能保证服 务质量( q o s ) 。随着分布式多媒体应用需求的不断增长，以及i n t e m e t 上商业 化应用的飞速发展，对网络性能和服务质量提出了更高的要求。而拥塞控制是 实现服务质量的基础，路由技术是实现服务质量的重要手段。厂5 无论网络如何发展，拥塞控制是不可缺少的。以往的拥塞控制研究主要着 重于网络端系统的控制功能增强，依赖于经验和仿真研究，缺少一定的理论支 持。我们的研究描述了一个端到端的系统模型，强调路由器队列管理在系统控 制中的地位，并从闭环控制的角度出发，设计和仿真队列管理算法。支持服务 质量的组播路由的一个主要问题是算法复杂，结点加入时延大，路由的控制信 令负担高，可扩展性差，难以适应有动态成员的大型群组。算法对网络拓扑的 依赖和不恰当的路径搜索方法是这些问题的原因所在，针对这些问题，我们提 出了改进的方案。 我们的工作以高速计算机网络的网络层协议为目标，分析、研究和扩展与 服务质量体系相关的队列管理和组播路由策略。队列管理是从网络结点出发研 究端到端的传输控制问题；路由是从网络资源管理出发研究资源分配问题。二 者共同成为网络服务质量控制的重要方面。 f 主要研究内容和创新点包括： ( 1 ) 研究了i p 网络中提供q o s 保证的协议和体制； ( 2 ) 描述拥塞控制的结构，研究主动队列管理的控制系统模型，给出一 种窗1 2 1 受限情况下r e d 算法的最大丢包率的调节方法，设计了一 种用于主动队列管理的模糊控制器，仿真证明了这些队列管理算法 的有效性： ( 3 ) 研究组播q o s 路由的网络模型和q o s 约束条件；分析组播路由问 题和算法；分析i n t e m e t 中现有主流的组播路由协议的不足之处及 其对q o s 的支持。 i p 刚络中拥塞控制和可护展组播路由研究 浙江大学博士学位论文 ( 4 ) 提出一种支持q o s 的拓扑自适应动态组播路由算法t a d m r ，进行 了理论分析和仿真，结果表明：该算法与同类算法相比能显著降低 的控制信令开销和结点加入时延，适用于各种网络规模和群组规 模，具有很好的可扩展性； ( 5 ) 分析i n t e m e t 中q o s 路由问题以及与资源预留的交互，初步探讨了 利用r s v p 机制实现t a d m r 协议的可能性，给出实现方案。) _ 彩 关键词：拥塞控制、主动队列管理、组播、q o s 路由、可扩展性 i i i p 网络中拥塞控制和可扩展组播路由研究浙江大学博士学位论文 a b s t r a c t i n t e m e th a sb e e n d e v e l o p e d i n t ot h eb a s i co ft o d a y ss o c i a l 1 i f e p e o p l e a r e e x p e c t i n gm o r ea n d m o r e c a p a b i l i t i e ss u c ha sp e r f o r m a n c e ，c o n t e n ta n ds a f e t yf r o m n e t w o r k h o w e v e r , t h em a i nk i n do f s e r v i c ei ss t i l l b e s te f f o r t i nt h ei n t e r a c t a l l p a c k e t sa r et r e a t e de q u a l l y t h e r el a c k so f e f f i c i e n tq u e u em a n a g e m e n t c o n g e s t i o n h a p p e n sh e r ea n d t h e r eb e t w e e nw h i l e s ，w h i c hc a u s e st h ed r o p p i n go f p a c k e t so rt h e j i t t e r i n e s s o ft r a n s p o r t ，a n de v e np e r v a d e st o c o l l a p s e t h en e t w o r k w i t ht h e d e v e l o p m e n to f i n t e r a c tb a s e db u s i n e s sa n da p p l i c a t i o n s ，q u a l i t yo fs e r v i c e ( q o s ) i sr e q u i r e da n di n t e m e ti se x p e c t e dt o s u p p o r tt h eq o s c o n g e s t i o nc o n t r o li st h e b a s eo f q o sa n dr o u t i n gt e c h n o l o g yc a r lg i v eg o o ds u p p o r t t ot h eq o s s y s t e m n om a t t e rh o wt h en e t w o r ki s ，i ti sn e c e s s a r yt oc a r r yo u tt h ec o n g e s t i o nc o n t r 0 1 t h ep r e v a i lm o d e lo f c o n g e s t i o nc o n t r o lr e s e a r c hi st h a tf i r s t l yp r o p o s eas c h e m e b a s e do n e x p e r i e n c e a n di n t u i t i o n ，a n dt h e n v e r i f y a n d i m p r o v e i t t h r o u g h s i m u l a t i o n sa n d e x p e r i m e n t s ，a n dm a i na t t e n t i o ni sp a i do n t h ef u n c t i o n so ft h ee n d s y s t e m s w ea n a l y s i st h ec o n g e s t i o nc o n t r o ls y s t e m a sac l o s e1 0 0 ps y s t e ma n dt a k e t h er o u t e ra st h ef e e d b a c kc o n t r o l l e r s ot h er o l eo f q u e u em a n a g e m e n t i s e m p h a s i z e d a n dn e wa c t i v eq u e u e m a n a g e m e n ta l g o r i t h m sa r ed e s i g n e d c o m m o n q o s a w a r ed y n a m i c m u l t i c a s tr o u t i n ga l g o r i t h m sh a v et h es a l n ep r o b l e m s s u c ha sc o m p l e x i t y , l o n g j o i n i n gl a t e n c yf o rn e wm e m b e r s ，h e a v yc o n t r o lm e s s a g e o v e r h e a d w h i c hc a u s et h ep o o rs c a l a b i l i t y i ti sh a r dt od e s i g na na l g o r i t h i nt h a ti s s u i tf o rl a r g em u l t i c a s tg r o u ps i z e 皿ek e y sa r eh o wt oa v o i dt h e a l g o r i t h m s d e p e n d e n c yo f t h en e t w o r k s t o p o l o g i e sa n dh o w t oc a l c u l a t et h ec o n n e c t i n g r o u t i n g f o rt h en e wm e m b e r s e f f i c i e n t l y w eg i v eo u t o u rs o l u t i o n si no u rr e s e a r c h w et a k eb o t ht h ea c t i v eq u e u em a n a g e m e n t a l g o r i t h ma n dt h eq o s - a w a r ed y n a m i c m u l t i c a s tr o u t i n ga l g o r i t h ma so u rt o p i c s n e ya r eb o t hr e l a t e dt ot h et a s ko f q o s g u a r a n t e ei nt h en e t w o r k a c t i v eq u e u em a n a g e m e n ti st h et r a n s p o r tc o n t r o lp r o b l e m i nt h ee n d t o e n ds y s t e m ，r o u t i n gi sa b o u tr e s o u r c ea l l o c a t i o na n d a s s i g n m e n tw h i c h c a nd e c i d ed i r e c t l yt h eq o so f c e r t a i n a p p l i c a t i o n s 1 1 1 i p 网络中拥塞控制和可扩展组播路由研究浙江大学博士学位论文 t h em a i nc o n t e n t sa n dc o n t r i b u t i o n sa r el i s t e db e l o w ： ( 1 ) a n a l y s i s o ft h eq o sg u a r a n t e es y s t e mi nt h ei pn e t w o r k w h i c hi n c l u d e st h e p r o t o c o l s ，s t a n d a r d sa n dp o l i c e s ( 2 ) d i s c u s st h es t r u c t u r eo ft h ee n d t o e n d c o n g e s t i o nc o n t r o l s c h e m e sw i t h a c t i v eq u e u em a n a g e m e n t ( a q m ) i ni pn e t w o r kf r o mt h ec o n t r o l t h e o r e t i c p o i n to fv i e w g i v eo u t am e t h o dt oe s t i m a t et h em a x i m u m d r o pp r o b a b i l i t y o fr e d ( p m a x ) i nv i e wo ft c ps o u r c e s m a x i m u mw i n d o wl i m i t a n d p r o p o s eaf u z z yl o g i cb a s e da q m w h i c hc a ni m p r o v et h er o b u s t n e s so ft h e c o n t r o la l g o r i t h m s g i v eo u tt h ed e t a i l e ds i m u l a t i o n s ( 3 ) s t u d y o f t h en e t w o r km o d e la n dt h eq o sr e s t r i c t i o n so f q o s a w a r em u l t i c a s t r o u t i n gp r o b l e m s u m m a r i z et h er o u t i n ga l g o r i t h m sa n dp r o t o c o l s a n a l y s i s t h es h o r t c o m i n g sa n dt h eq o s s u p p o r ta b i l i t i e so fc u r r e n t l yu s e dm u l t i c a s t p r o t o c o l s ( 4 ) p r o p o s e aq o s a w a r ed y n a m i cm u l t i c a s tm u t i n ga l g o r i t h mn a m e dt a d m r m o s to fa i m l e s s s e a r c h i n g i ns o m es i m i l a r a l g o r i t h m s c a nb ea v o i d e d t a d m rc a nb eu s e dt oc o n s t r u c tl o wc o s tt r e es i m i l a rt oo p t i m a lg r e e d y s t r a t e g yw i t ha d a p t a t i o nt ot h et o p o l o g yo fn e t w o r k c o n t r o lo v e r h e a da n d a c c e s sl a t e n c yc a na l s ob er e d u c e dg r e a t l y , s oi ts c a l e sw e l l s i m u l a t i o n s r e s u l t sp r o v e dt h e s e ( 5 ) s t u d y t h er o u t i n gc o n t r o lc a p a b i l i t yo fr s v p p r o t o c o la n di t sm l a t i o nw i t l l t h eq o s p r o b l e m p r o p o s eas c h e m et h a tu s er s v p a st h em u t i n gm e s s a g e p r o t o c o lo f 咖m r k e y w o r d s ：c o n g e s t i o nc o n t r o l ，a c t i v eq u e u em a n a g e m e n t ，m u l t i c a s t ， q o s - a w a r er o u t i n g ，s c a l a b i l i t y i v i p 网络中拥塞控制和可扩展组播路由研究浙江大学博士学位论文 第一章绪论 本章从网络环境和网络应用中提供服务质量( q u a l i t yo fs e r v i c e ，q o s ) 的要 求出发，分析了网络拥塞控制和q o s 路由研究背景，介绍研究现状，阐述论文 的研究内容和总体结构。 1 1l p 网络q o s 概述 世界上有许多不同的网络，而且常常使用不同的硬件和软件。在一个网络 上的用户经常需要和另一个网络上的用户通信。这就需要连接不同的、而且往 往是不兼容的网络。互连的网络就称为互连网( i n t e r n e t w o r k 或i n t e r n e t ) 。而 因特网i n t e m e t ( 大写的i ) 是指特定的世界范围内的互连网，它被广泛地用于 连接大学、政府机关、公司和个人用户 1 】。 i p 网络即采用i p ( i n t e m e tp r o t o c 0 1 ) 协议的网络。现在，因特i 网( i n t e m e t ) 上大部分的网络采用该协议。i n t e r a c t 是在, m 王p a n e t ( 美国国防高级研究计划 局网络) 和n s f n e t 网络互联的基础上发展起来的。a r p a n e t 是在6 0 年代 末期发展的，它是第一个电子的存储一转发分组交换网。1 9 6 9 年试验性网络取 得成功后，逐渐发现当时的a r p a n e t 协议不适合在多个网络上运行。这导致 了对协议更深入的研究，最后产生了t c p 】 p 模型和协议。 在1 9 8 3 年当t c p ，】田成为a r p a n e t 上唯一正式的协议之后，a r p a n e t 上连接的网络、机器、用户迅速增长，当n s f n e t 和a r p a n e t 互联之后， 更是以指数级增长，i n t e m e t 就是在此网络互联的基础上逐渐形成的。 上世纪九十年代中期以前，i n t e m e t 上的网络包括骨干网都是由路由器构成 的，它们都采用i p 协议。后来，随着用户数的剧增和对带宽要求较高的w w w 应用的普及，网上的信息流量持续增加，网络的带宽资源变得十分紧张，以致 网络经常发生拥塞，而a t m 技术的出现则为解决i n t e m e t 所面临的问题提供了 希望。由于a t m 网络可以传送包括语音、图像等实时数据在内的各种数据， 同时它沿用了电信网的中央控制和面向连接的基本原理，因此更适合于有服务 质量保证和安全性的商业骨干网；而i p 网的无连接性带来了网络的简便可操作 性和坚固性，因而更适合于用户端的多业务接入。目前已存在a t m 为骨干网 i p 网为接入网的混合网络( i p - o v e r - a t m ) 。这种网络的实质就是如何在a t m 网络上支持t c p i p 协议的问题。 1 p 网络中拥塞控制和可扩展组播路由研究浙江大学博士学位论文 上世纪九十年代后期，由于路由技术的发展已经使得骨干网上的路由器可 以提供以前只有a t m 才有的高速链路和可以预见的性能，随着高速光纤的提 供，网络服务提供商( i s p ) 需要考虑是继续使用昂贵的结构复杂的设备，还 是移植到简单的完全由路由器组成的核心网络上。构造完全由路由器组成的网 络需要解决的一个问题是如何对网络的流量进行精确的控制，以便充分使用网 络资源的同时，能够提供与i p o v e r - a t m 【2 】一致的支持服务质量保证等的功能。 在网络容量方面，网络千线的数据吞吐率每5 到l o 年都有跨数量级的增 加，如今以光通信为基础的干线通信速率已从g b p s 向t b p s 数量级迈进；高性 能交换机路由器不断出现。宽带网络技术的出现大大增加了分组交换计算机网 络的容量，从几兆( m ) 比特秒到成百上千兆( g ) 秒，使得网络可以支持新 的应用，如视频会议、科学计算可视化、i n t e m e t 电话、多媒体邮件、医学成像、 视频点播和远程教学等。同时，随着w e b 应用、数字图书馆、i o 集中的科学 应用的增长，传统“尽力而为”( b e s t e f f o r t ) 服务类别的数据流量也在持续增 长。在这种环境下，数据负载可从几兆到几个吉比特【3 】【4 1 。 i n t e m e t 已成为一个重要的和无处不在的商业基础设施，这大大改变了消费 者对网络性能、安全性和服务的期望。但是“尽力而为”服务仍是目前i n t e m e t 中主要的一种服务类别，所有分组在网络中被同等对待，任何拥塞链路都会增 加分组传输时间，从而导致性能下降、数据抖动、或者分组丢失，不能保证服 务质量。随着分布式多媒体应用需求的不断增长，以及i n t e r a c t 上商业化应用 的飞速发展，对服务质量( q u a i l i t yo f s e r v i c e ，q o s ) 提出了更高的要求 4 1 1 5 1 “， 高效的q o s 支持显得越来越重要。 简单地说，q o s 能够对数据包进行合理的排队，对含有内容标识的数据包 进行优化，并对其中特定的数据包赋以较高的优先级，从而加速传输的进程。 q o s 直接表现为坤数据流通过网络时的性能，它有一套度量指标，包括业务可 用性、延迟、可变延迟、吞吐量和丢包率： 业务可用性：用户到i p 业务之间连接的可靠性； 延迟：也称为时延( l a t e n c y ) ，指两个参照点之间发送和接收数据包的时 间间隔： 延迟抖动( j i t t e r ) ，指在同一条路径上发送的一组数据流中数据包之间的 时间差异； 吞吐量：网络中发送数据包的速率，可用平均速率或峰值速率表示； 丢包率：在网络中传输数据包时丢弃数据包的最高比率。 不同的应用要求不同的q o s 某些应用要求严格的端端延时，某些应用要 求传输速率保证，而有些应用没有严格的延时和或带宽需求，只要求较高的吞 吐量。 i p 网络中拥塞控制和可扩展组播路由研究浙江大学搏士学位论文 1 2q o s 研究体系 支持q o s 的研究一方面主要着眼于分组调度、拥塞控制。网络拥塞是导致 网络性能下降的主要原因。控制网络的拥塞，一方面要设计高效稳定的拥塞控 制算法：源端根据网络拥塞状况调整数据发送速率，缓解网络拥塞。t c p 拥塞 控制在这方面发挥着重要作用。在t c f 拥塞控制成功的影响下，其它数据流传 输控制协议也多少进行了类t c p 的拥塞控制，不如s c t p 1 ”、d c c f 8 1 。但是 t c f 拥塞控制算法的一个重要特点是假定下面的网络层和低层在指示拥塞和 控制拥塞方面不提供任何支持。无论t c f 数据流的始端和终端之间经历什么样 的网络层以及网络层的协议如何，它提供的只是端到端的控制。 由于带宽、缓存等资源相对日益缺乏，i n t e m e t 继续变得拥挤。这种情况下， 人们一方面继续改进已有的端到端的拥塞控制方法，另一方面，意识到仅仅靠 端到端的拥塞控制是不够的。在i n t e m e t 这样的复杂异构系统中，不能指望所 有的i n t e m e t 应用兼容这种端到端的拥塞控制，网络本身应该参与到资源的管 理和控制中。这就是要在路由器中采用积极的队列管理( a c t i v eq u e u e m a n a g e m e n t ，a q m ) 技术，包括分组排队算法和分组丢弃策略，也就是说t c p 下层的i p 要参与处理拥塞控制。分组调度算法决定哪些包可以传输从而分配带 宽，分组丢弃策略决定哪些包被丢弃从而分配缓存。 t c f 是基于窗口的端到端拥塞控制，它在感知到拥塞至采取行动之间有明 显的时延，在这个时延中，如果信息序列很短，也许在反馈信息到达源端后信 源已经传输完毕。而且它又依靠网络层的i p 协议来传输反馈，反馈信息本身也 会给网络造成额外的负担。t c f 拥塞控制不能对所有类型的数据流起作用，从 而可能造成不公平性。基于主动队列管理的拥塞控制则可以做到公平性，因为 它不依赖信源。但是它增加了路由器的复杂性。而基于t c f 的拥塞控制度复杂 性可以随信源的负荷而不同，产生高负荷的信源需要更复杂的控制。基于主动 队列管理的拥寨控制能克服段时间的局部拥塞，但是没有办法根本解决拥塞， 最终要通过源端的流量减少来缓解长时间的网络拥塞。 支持q o s 的研究主要另一方面的主要内容是资源预留和q o s 路由f m ”】。 值得一提的是，不管网络设计的多么优化，路由都是对拓扑结构和网络状态变 化作出响应的一个重要的网络功能。网络设计通常依赖于对用户流量和负载的 长期测量，其目标是产生最小设备代价的网络拓扑结构，与路由相结合，容纳 特定网络条件下预期的用户流量。约束路由在寻径路由时会受到一定的约束， 如带宽或时延的要求。传统的i n t e m e t 中的路由算法主要是保证基本的连通性， 路由协议是基于单一度量( m e t r i c ) 优化，如跳数( h o p ) ，其算法有b e l l m a n f o r d i p 网络中拥塞控制和可扩展组播路由研究浙江大学博士学位论文 和d i j k s t r a ，难以满足多样的q o s 需求。所以，有必要用多个路由度量表征网 络，如带宽、跳数、延时、丢失率、抖动等，但是找到满足多个约束的路由是 非常困难，甚至是不可行的。 如图1 1 ，拥塞控制和q o s 路由资源预留，构成了q o s 研究体系的基础部 分【1 4 l 。 图1 - 1 网络中支持k s 的研究体系 1 3 支持q o s 的网络业务 1 3 1 网络业务模型 最初设计的i n t e m e t 是面向非连接的分组交换网络，所有的业务分组被不 加区分的在网络中传输，网络能给出的唯一承诺就是尽自己最大的努力传输进 入网络中的每一个分组，但它无法给出一个定量的性能指标，相应地，用户也 无需进行业务许可请求。很显然，这种网络体系结构一方面缺乏一定的隔离和 保护机制，另一方面，需要对网络所传输的业务类型有一个较为具体和明确的 定义，即所谓的网络业务模型。 i e t f 提出了其它一些著名的服务模型和机制来满足q o s 需求，其中比较 典型的有：集成服务( i n t e g r a t e ds e r v i c e s ，i n t s e r v ) 资源预留协议( 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 ) 1 5 1 【1 6 1 、m il s ( m u l t i p r o t o c o ll a b e l s w i t c h i n g ) 、流量工程( t r a f f i ce n g i n e e r i n g ) 【1 7 】 1 8 1 ，子网带宽管理( s u b n e t b a n d w i d t h m a n a g e m e n t ，s b m ) ”，其目的都是为了满足应用的q o s 需求，同时 有效地利用网络资源。 4 i p 网络中拥塞控制和可扩展组播路由研究浙江大学博士学位论文 i n t e r n e t 的i n t s e r v 体系能使应用在多种具有不同q o s 的服务中选择一种自 己需要的服务，它完成了如下的两件功能：( 1 ) 一个应用的数据通路中的网络 元素( 如i p 路由器) 具有控制q o s 的机制；( 2 ) 提供一种能将应用的q o s 要 求传送给网络元素并能在应用和网络元素之间交互q o s 管理信息的机制。第一 个功能由负载受控的网络业务和质量保证业务来完成。第二个功能可以采用多 种机制来完成，通常采用资源预留协议如r s v p 来实现。但由于r s v p 基于每 个数据流状态，每次连接都有自己相应的状态，网络内部节点对数据流状态的 更新和维护会占用大量资源，这使其可扩展性很差，因此i n t s e r v ，r s v p 很难得 到大规模使用。 由于i n t s e r v r s v p 可扩展性不好，很难得到大规模使用，i e t f 在1 9 9 8 年 公布d i f f e r e n t i a t e ds e r v i c e s 体系模型。这是目前被普遍认可的体系，并仍在不 断完善中。 d i f 飓e r v 体系模型的核心思想是：在网络边界将数据流按q o s 要求进行简 单分类，不同的类在内部结点的每次转发中实现不同的转发特性。d i f l s e r v 体 系使得i s p 能够提供给每个用户不同等级和质量的服务。用户( 或网络边界结 点) 通过设置每个数据包的d s 字段( n , v 4 首标中的服务类型字段或i p v 6 首标 中的流量标记字段) 的值要求特定的服务等级。在每个支持d i f f s e r v 的网络结点 中，这个d s 值将数据包映射到一类转发行为p h b ( p e r - h o pb e h a v i o r ) 中去， 以在转发中区别对待。用户和i s p 之间有一个协定，此协定规定了该用户在每 个服务等级上所能发送的最大数据率。超过此最大速率的数据包或被丢弃，或 无法享受到它所要求的服务。 d i t l s e r v 网络最大的特征是其可扩展性。此体系将许多复杂的控制移到了 网络的边界，使内部结点能对叠加之后的数据流进行处理，而不必对每个数据 流分别处理，从而大大减少了网络内部应该记录的状态，简化了网络内部结点 的操作。 【一 用户子网，集成服务区域 1，一 主干网，区分服务区域 1一 用户子网，集成服务区域 图1 - 2 集成服务和区分服务盹互补服务横型 集成服务使用资源预留协议为数据流提供量化的q o s 保证，但其扩展性有 限。区分服务结构的网中结点只对有限个p h b 按确定的优先级进行资源分配 i p 网络中拥塞控制和可扩展组播路由研究浙江大学博士学位论文 与调度，因此具有很好的扩展性。集成服务和区分服务的互补，将量化的q o s 保证特性和可扩展性优点相融合，为i n t e r n e t 上的应用提供更好端到端的q o s 保证。实施的基本策略如图1 2 ：在用户子网中，采用集成服务体系，在主干 网采用区分服务体系。数据流在子网的边缘路由器中被映射到不同的服务质量 级别，在主干网中以不同的p h b 穿越主干网【柏】。 1 3 2 多协议标签交换( m p l s ) 与流量工程 多协议标签交换技术是i p 技术和a t m 技术互相影响的产物，是为了综合 利用网络核心的交换技术和网络边缘的i p 路由技术各自的优点而产生的。 m p l s 明确规定了一整套协议和操作过程，最终在i p 网内通过a t m 和帧中继 实现快速交换。m p l s 中的关键概念是用标签来识别和标记i p 报文，并把标签 封装后的报文转发到已升级改善过的交换机或路由器，由它们在网络内部继续 交换标签，转发报文。它在i p 数据包前加入固定长度的包头( 标签) ，不对i p 数据包的内容做任何的处理。采用固定长度的标签，加快了m p l s 交换机查 找路由表的速度，减轻了交换机的负担。利用m p l s 实现端到端的q o s ，实际 上是将第三层的q o s 通过与m p l s 的有机结合转换成第二层的q o s ，以实现 端到端的q o s 。 实施流量工程来提供q o s 的一种原因是：由于网络在设计时的构想与现实 的业务流量分布不一致，导致网络的某些链路数据流量远大于当初的设想，造 成局部拥塞，而某些链路却造成局部空闲。而传统的口路由算法会导致网络资 源使用的不均衡，无论是最短路径优先算法( o s p f ) 还是距离向量算法( r i p ) ， 在选路时都是使用最短的路径转发i p 分组。由于i g p 在计算路由时并未将链 路带宽和流量特点考虑进去，丽单纯计算出最短路径，这必然使得短的路径容 易拥塞，而较长的路径容易空闲。这种由于网络资源使用不均衡造成的网络拥 塞必然致使网络性能降低，服务质量无法保证。流量工程的主要目的是将业务 流量合理分配在现有的网络拓扑结构上，以优化网络资源的合理使用。另一方 面，随着近来出现的要求网络提供多等级q o s 的呼声日甚，网络要能够提供区 分业务、集成业务资源预留等网络功能也需要网络具有一定的流量工程能力。 流量工程的主要目的可以分为两类：面向流量的和面向资源的。面向流量 的流量工程的主要目标是提高业务流的服务质量，其主要目标是：降低分组丢 失率，降低时延，增大吞吐量和实施业务级协定( s e r v i c el e v e l a g r e e m e n t 。s l a ) 。 面向资源的流量工程的主要目标是有关资源使用的优化方面。网络资源的有效 管理是面向资源的目标实现的基础。通常。需要保证网络资源不会在某些子网 过分使用和拥塞，而在别的候选路径上的予网使用却十分空闲。带宽是现有网 6 i p 网络中拥塞控制和可扩展组播路由研究浙江大学博士学位论文 络的主要和缺乏的资源。所以，流量工程的主要功能是有效管理带宽资源。尽 可能地减小拥塞是面向流量和面向资源的流量工程的主要目标，并且主要不是 为了解决暂时拥塞而是解决更长时的拥塞。多协议标签交换则可提供对业务流 量的很强控制能力，使流量工程的实施十分便利。在一个m p l s 网络中，标签 ( l s p ) e 2 0 】【2 1 1 可被用来实施流量工程。网络运营者或网络管理应用软件 可以通过建立明确路由标签交换路径( e r l s p ) 来控制业务流量的流向，从 而实现流量工程。e r - l s p 可以完全不受坤层的路由协议影响，达到对业务流 量的完全控制。 明确l s p 的建立可以分为两个步骤：首先是计算或配置得到明确路由 ( e x p l i c i tr o u t e ) 。其次是利用信令协议建立l s p 。其中明确路由的建立方法又 可采用几种方式：一种是依靠基于约束的选路的在线计算，一种是依靠基于约束 的选路的离线计算。还有一种是根据网络运营的需要直接配置。利用信令协议 建立l s p 也可分为两种，一种是c r - l d p “，利用标签传播协议( l a b e l d i s t r i b u t i o np r o t o c 0 1 l d p ) 来建立l s p ；还有一种是r s v p t 2 ”，通过对已经有的 r s v p 协议扩展来适应建立l s p 的要求。这两种方法各有利弊，孰好孰坏众说 纷纭。 主机a主机b j 端到端的q o s j 圈1 - 3 各支持q o s 的协议之间在网络层次上的协同关系 1 3 3 支持q o s 的协议栈 从协议栈的角度看，各支持q o s 的模型和协议组成了一个“自顶而下，端 到端”的q o s 体系结构，图1 3 表示这种协同关系的一个典型结构【2 2 1 。s b m 旧噘! 呈吓m ，品薹一 i p 网络中拥塞控制和可扩展组播路由研究浙江大学博士学位论文 协议提供信令，在共享及交换的 e e e 8 0 2 网络的第二层实现分类和优先级控制， 使得8 0 2 局域网映射到q o s 协议成为可能。r s v p 为网络分配带宽，d i f f s e r v 则为网络流量指定优先级。r s v p 相对来说毕d i f f s e r v 复杂得多，对路由器的 要求也高的多。所以在主干网上r s v p 是使用受限的，而d i f f s e r v 在主干网上 容易存在，成为r s v p 的一个很好的补充。主机进行资源预留请求，主干网人 口路由器把它映射成d s 字节，主干网出口路由器又把它恢复成r s v p 并送至 目的地。这样网络的结构是以r s v p 为边缘，以d i f f s e r v 为核心。 1 4 流量控制与拥塞控制研究的意义 1 4 1 拥塞与拥塞控制 一些q o s 的研究认为在具有充足资源的尽力而为的网络中，拥塞问题会不 复存在，简单的尽力而为能满足大部分要求。但是网络资源的代价是昂贵的， 而且没有什么网络的资源会永远满足需求。大多数的研究者们认为：更多更合 理的控制机制对己有网络的稳定运行无疑将是至关重要的。其中一个最基本和 最重要的要求就是防止网络出现拥塞崩溃，使网络运行在轻度拥塞的最佳有效 状态，同时保证一定的公平性。 上- d , 节介绍的i n t s e r v 、d i f f s e r v 等业务模型，都是结合应用的需要和技 术的发展提出来的。无论哪一种业务体系结构，其技术的核心都需要在恰当的 层次和粒度上对流量进行必要的管理，其中包括接纳控制，流量成形，队列管 理，调度和拥塞控制等诸多方面，但最基本和最核心的应该依旧是拥塞控制， 因为很难想象一个时常有可能出现严重拥塞，无法及时加以恢复的网络能够实 现良好的q o s 保证。实施拥塞控制应该是其它q o s 机制正常工作的必要前提。 拥塞是一种持续过载的网络状态，此时用户对网络资源( 包括链路带宽， 存贮空间和处理器处理能力的需求超过了其固有的容量。就i n t e m e t 的体系结构 而言，拥塞的发生是其固有的属性，因为在事先没有任何协商和接纳控制机制 的资源共享网络中，几个i p 分组同时到达路由器，并期望经同一个输出端口转 发的可能性肯定是存在的，显然，不是所有分组可以同时接受处理，必须有一 个服务顺序，中间节点上的缓存为等候服务的分组提供一定保护，然而，如果 此状况具有一定的持续性，当缓存空间被耗尽时，路由器只有丢弃分组。 就一般而言，路由器通常采用f c f s ( f i r s tc o m e f i r s ts e r v e d ) 的服务顺序， 用f i f o ( f i r s ti nf i r s to u t ) 的队列即可实现，当缓存溢出时从尾部丢弃分组。 表面上，增大缓存总可以防止由于拥塞引起的分组丢弃，但随着缓存的增加， 端到端的时延也相应增大，因为分组的持续时间( l i f e t i m e ) 是有限的，超时 i p 网络中拥塞控制和可扩展组播路由研究 浙江大学博士学位论文 的分组同样需要重传。因此，过大的缓存空间倒有可能妨碍拥塞的恢复，因为 有些分组白白浪费了网络的可用带宽。 拥塞导致的直接结果是分组丢失率提高，端到端时延加大，甚至有可能使 整个系统发生崩溃。最早报告的拥塞崩溃发生在1 9 8 4 年【2 3 1 。当网络处于拥塞崩 溃状态时，微小的负载增量都将使网络的有效吞吐量( g o o d p u t ) 急剧下降。当负 载减小时，拥塞可以自动恢复。除此之外，还有其他一些诱发拥塞崩溃的原因。 例如，不可达分组( u n d e l i v e r dp a c k e t s ) 导致的网络崩溃：它与前一种有所不同， 不是一种稳定状态；分片拥塞崩溃【2 5 】：网络传输了大量的分组分片，但因为无 法在接收端重装成有效的分组而只好将它们丢弃，因此网络传输大量用户不再 需要的陈旧分组( s t a b l ep a c k e t s ) ，导致这种形式的拥塞崩溃现象。 图1 - 4 亥l j 画了网络负载与吞吐量之间的关系。当负载较小时，吞吐量与负载 之间呈线性关系；到达膝点( k n e e ) 之后，随负载的增加，吞吐量的增量逐渐 吞吐量 图l 一4 吞吐量和负载的关系简圈 负载 变小；当负载越过崖点( c l i f f ) 之后，吞吐量却急剧下降。通常将k n e e 点附 近称为拥塞避免区间：k n e e 到c h 跎问是拥塞恢复区间：c l i f f - ) - 夕f 是拥塞崩溃 区间。为最大限度地利用资源，网络工作在轻度拥塞状态时应该是较为理想的， 但这也增加了滑向拥塞崩溃的可能性，因此需要一定的拥塞控制机制来加以约 束和限制，这是研究拥塞控制最本质的意义。 总之：拥塞是不可避免的。这是因为：( 1 ) 为了提高链路的利用效率， 网络传输采用分组交换，这样路由器的缓存经常被占；( 2 ) 如果路由器缓存 总是空的，虽然传输延迟低，但是网络的利用效率也低；( 3 ) 如果路由器缓 存总是被占用，传输延迟高，但是网络利用效率也高。因此，拥塞控制的研究 的目的不是要完全避免拥塞，而是研究怎样的拥塞程度是合适的。一种形象的 指标是： 赫盎一网络负载 一。 传输延迟 j p 网络中拥塞控制和可扩展组播路由研究浙江大学博士学位论文 如图1 - 5 ，a 点的拥塞程度是最恰当的，它对应于膝点和崖点之间。 效率 l 图1 - 5 网络曩佳的拥塞状态 虽然拥塞控制的研究并非由q o s 保证而起，它从分组交换网络的诞生时就 一直倍受关注，但是在强调业务模型的新网络体系结构中，研究如何通过增强 的拥塞控制来帮助实现q o s ，也是拥塞控制研究的意义所在。 1 4 2 拥塞控制的研究内容 按照实施拥塞控制的物理位置的不同，端到端的拥塞控制方案可分为基于 源端的速率控制与基于网络中间结点的路由器缓存队列管理。源端的速率控制 的典型是t c p 的拥塞控制【2 4 1 ，其它的流媒体传输协议也有类似的流量控制。路 由器缓存的队列管理主要有传统的“尾部丢弃法”，r e d 、r e m 、p i 等主动队 列管理技术是近年来研究的热点，也是本文工作重点的一部分。 按照源端采用的流量控制策略，拥塞控制分为基于窗口的和基于速率的( 又 称基于方程的) 。基于窗口流量控制在源端或者接收端维持一个类似于t c p 拥 寨窗口的漏斗机制，来控制一次性发送到网络中的数据量【z ”。基于速率的拥塞 控制算法又可称为基于方程的拥塞控制算法、基于模型的拥塞控制算法