（控制科学与工程专业论文）基于internet的通信网络拥塞控制若干问题研究.pdf

摘要 摘要 本文致力于对i n t e r n e t 中的拥塞控制问题进行研究。论文首先介绍了拥塞 的现象和拥塞控制的基本知识。接下去介绍了一种新的面向多媒体通信的流控 制传输协议s c t p ，将其和t c p 协议进行比较，分析了s c t p 的长处和弱点，并设 计了仿真实验来测试s c t p 的性能，发现在避免t l o l 现象上，s c t p 并没有期待的 那么好。 根据捌塞控制实现的位置，将拥塞控制划分为t c p 捌塞控制和i p 拥塞控制。 本文对不同版本的t c p 拥塞控制算法进行了探讨。分析了t c p 拥塞控制的四个 阶段( 慢启动、拥塞避免、快速重传、快速恢复) ，以及各个阶段的作用。 本文对一些具有代表性的i p 拥塞控制算法进行了介绍与分析。其中重点介 绍了随机早期检测r e d 算法，根据r e d 存在的一些缺陷，并结合动态部分缓存 共享( d p b s ) 策略，对标准r e d 算法进行了改进，并通过仿真证明改进后的r e d 算法能够克服标准r e d 算法的两个缺陷：无优先级，不能满足q o s 的要求：对 窄带t c p 不公平。最后，对将来的研究方向提出了些建议。 关键词：流控制传输协议，动态部分缓存共享，拥塞控制，t c p 拥塞控制，l p 拥塞控制 a b s t r a c t a b s t r a c t t h ep a p e ra i m st os t u d yi n t e r n e tc o n g e s t i o nc o n t r 0 1 i nt h ef i r s tp a r t ，t h i sp a p e r i n t r o d u c e ss o m eb a s i ck n o w l e d g eo fc o n g e s t i o nc o n t r 0 1 a n dt h e ni n t r o d u c ean e w l y d e v e l o p e dt r a n s p o r tp r o t o c o l - - s c t p - - t a i l o r e df o rs i g n a l i n gt r a n s p o r t t h i sp a p e r a n a l y z e s s c t p s s t r e n g t h s a n dw e a k n e s s e sa n dp r o v i d e ss i m u l a t i o nr e s u l t s t h e s i m u l a t i o n ss h o wt h a tt h es u p p o s e d l yl a r g e s ta d v a n t a g eo fs c t p o v e rt c p h o l b l o c k i n g a v o i d a n c e - - - - d o e sn o tp r o v i d eas u b s t a n t i a lp e r f o r m a n c ei n c r e a s eu n d e r n o r m a lc i r c u m s t a n c e a c c o r d i n gt ot h ep o s i t i o nt h a tc o n t r o li sa p p l i e d ，c o n g e s t i o nc o n t r o li s d i v i d e d i n t ot w oc l a s s e s ：t c pc o n g e s t i o nc o n t r o la n di pc o n g e s t i o nc o n t r 0 1 t h i sp a p e r i n t r o d u c e ss e v e r a l a l g o r i t h m s o ft c pc o n g e s t i o nc o n t r o lw h o s ea d v a n t a g e sa n d s h o r t a g e s a i ed i s c u s s e d a n dt h e na n a l y s et h e f o u r p h a s e o ft c pc o n g e s t i o n ( s l o w 。s t a r t ，c o n g e s t i o na v o i d a n c e ，f a s tr e t r a n s m i t ，f a s tr e c o v e r ) a n d t h e i re f f e c t a f t e rt h e d i s c u s s i n g o ft c pc o n g e s t i o nc o n t r o l ，t h i sp a p e r f o c u so ni p c o n g e s t i o nc o n t r o l ，e s p e c i a l l y o nr a n d o me a r l yd e t e c t i o n ( r e d ) a l g o r i t h m t h e w e a k n e s so fr e di sn op r i o r i t ya n du n f a i rt ot h el o ws p e e dt c p f l o w c o m b i n et h e d p b s i f d y n a m i cp a r t i a l b u f f e rs h a r i n g ) s c h e m e ，a ni m p r o v e dr e dm e c h a n i s m b a s e do nd p b si s p u t f o r w a r d t h es i m u l a t i o ns h o w st h a tt h ei m p r o v e dr e d a l g o r i t h m c a n c o n q u e r t w ow e a k n e s so fr e d i nt h ef i n a l i t y ，p r o v i d es o m es u g g e s t i o n f o rf u 【t u r er e s e a r c h k e yw o r d s ：s c t p , d p b s ，c o n g e s t i o n c o n t r o l ，t c pc o n g e s t i o nc o n t r o l ，i pc o n g e s t i o n c o n t r o l 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提f ，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：壹c 屯沁 芦r 年3 月i i _ ：】 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月口 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位沦义，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位沦文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对木论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：董屯渡 妒上年；月f 日 第一章，j i 高 第一章引言 随着互联网规模的增长，互连网上的用户和应用都在快速的增长，拥塞已经 成为一个十分重要的问题。近年来，在拥塞控制领域开展了大量的研究工作。在 最初的t c p 协议【l 】中只有流控帚o ( f l o wc o n t r 0 1 ) 而没有拥塞控制，接收端利用t c p 报头将接收能力通知发送端。这样的控制机制只考虑了接收端的接收能力，而没 有考虑网络的传输能力，导致了网络崩溃( c o n g e s t i o nc o l l a p s e ) 的发生。1 9 8 6 年 1 0 月，由于拥塞崩溃的发生，美国l b l 到u c b e r k e l e y 的数据吞吐量从3 2 k b p s 跌落到4 0b p s ”1 。在那之后，在拥塞控制领域开展了大量的研究工作。拥塞控制 算法对保证i n t e r n e t 的稳定具有十分重要的作用。 1 1 为什么需要拥塞控制 1 1 。1 拥塞出现的条件 在计算机网络中的链路容量、交换结点中的缓冲区和处理机等，都是网络的 资源。在某些时间，若对网络中的某一资源的需求超过了该资源所能提供的可用 部分，网络的性能就要变坏，这种情况就叫做拥塞( c o n g e s t i o n ) 。可以将出现 拥塞的条件写成如下的公式： x 对资源的需求，可用资源 ( 1 1 ) 一 捌塞发生的原因是“需求”大于“供给”。网络中有限的资源由多个用户共 享使用。由于没有“接纳控制”算法，网络无法根据资源的情况限制用户的数量： 缺乏中央控制，网络也无法控制用户使用资源的数量。目前i n t e r n e t 上用户和应 用的数量都在迅速增长。如果不使用某种机制协调资源的使用，必然会导致网络 拥塞。虽然拥塞源于资源短缺，但增加资源并不能避免拥塞的发生，有时甚至会 加重拥塞程度【3 】。例如：增加网关缓冲会增大报文通过刚关的延迟，如果总延迟 超过端系统重传时钟的值，就会导致报文重传，反而加重了拥塞。 幽11 带宽不均衡 第章0 i 吉 拥塞总是发生在网络中资源“相对”短缺的位置。拥塞发生位置的不均衡反 映了i n t e r n e t 的不均衡性。首先是资源分布的不均衡。图1 1 中带宽的分布是不 均衡的，当以l m b s 的速率从s 向d 发送数据时，在删关r 会发生棚塞。其 次是流量分前i 的不均衡。图1 ，2 中带宽的分布是均衡的，当a 和b 都以1 m b s 的 速率向c 发送数据时，在网关r 也会发生拥塞。i n t e m e t 中资源和流量分稚的 不均衡都是广泛存在的，由此导致的拥塞不能使用增加资源的方法来解决。 图1 2 带宽均衡流量不均衡 1 1 2 拥塞出现的三个直接原因 上面提到了拥塞出现的根本原因就是了对资源的需求，可用资源。接下来 将列举网络发生拥塞的直接原因1 4 】，主要有三点： 1 链路带宽不足导致拥塞，高速链路和低速链路的不匹配或者多条输入带宽 总和大于输出带宽容量，都会使路由器中数据到达率远远大于离去率，从 而导致长队列缓冲区用完进而导致拥塞。如图1 1 中的例子就是高速链路 和低速链路的不匹配造成拥塞。 2 处理器能力弱、速度慢。如果路由器的c p u 在执行排队缓存、更新潞由 表等功能时，处理速度跟不上高速链路，也会产生拥塞。同样，低速链路 对高速c p u 也会产生拥塞。 3 路由器缓存不足导致拥塞。当多个分组突然从不同输入线路涌入路由器 时，这些分组就要在路由器进行排队，如路由器没有足够的缓存存储分组， 就会使些分组被丢弃。虽然增加缓存对这一问题会有所帮助，但过大的 缓存反而会导致拥塞的恶化。简单地扩大缓冲区的存储窄间4 i 但会造成刚 络资源的严重浪费，而且解决不了网络拥塞的闻题。这一点将在第1 i 3 节中做具体的说明。 1 1 3 拥塞控制的作用 若网络中有许多资源同时产生捌塞，网络的性能就明显变差，整个网络的吞 吐量将随输入负荷的增大而f 降。只要任意增d i l “些资源，例如，将结点缓冲区 的存储空州扩大，或将链路更换为更高速率的链路，或将结点处删机的运算速度 第章0 l 言 提高，就可以解决网络j 爿j 塞的问题? 其实彳i 然。这是因为拥塞控制是一个非常复 杂的问题。简单地采用上述做法，在许多情况下，不但不能解决拥塞问题，而且 还可能使网络的性能更坏。网络拥塞往往是由许多因素引起的。例如，当某个结 点缓冲区的容量太小时，到达该结点的分组因无空间暂存而不得不被丢弃。现在 设想将该结点缓冲区的容量扩大到非常大。于是儿到达该结点分组均可在这缓冲 区的队列中排队，不受任何限制。由于输出链路的容量和处理机的速度并未提高， 因此在这队列中的绝大多数分组的排队等待时间将会很长很长，结果卜层软件只 好将它们进行重传( 因为早就超时了) 。由此可见，简单地扩大缓冲区的存储空 f 司不但会造成网络资源的严重浪费，而且解决不了网络拥塞的问题。又如，处理 枫的速率太慢可能引起网络的拥塞。如某个路由器的c p u 运行太慢，使得缓冲 区中得队列变得很长，即使线路得容量还很宽裕。简单地将处理机得速率提高， 可能会会使上述情况缓解些，但往往又会将瓶颈转移到其它的地方。问题的实 质往往是系统的各个部分不匹配。只用所有的部分都平衡了，问题才会得到解决。 拥塞常常使问题趋于恶化。如果一个路由器没有足够的缓冲区，它就会丢弃一些 新到的分组。但当分组被丢弃时，发送这一分组的相邻的路由器就会重发这一分 组，可能还要重发多次。发送端在未收到确认之前必须保留所发分组的副本以便 重发。可见在接收端产生的拥塞反过来会引起发送端缓冲区的拥塞。 图1 3 的横坐标是网络负载( o f f e r e dl o a d ) ，代表单位时间内输入给网络的 分组数目。因此网络负载也称为输入负载。纵坐标是吞吐量( t h r o u g h p u t ) ，代 表单位时间内从网络输出的分组数目。具有理想拥塞控制的网络，在吞吐量饱和 之前，网络吞吐量应等于网络负载，故吞吐量曲线是4 5 。的斜线。但当网络负载 超过某一限度时，由于网络资源受限，吞吐量不再增长而保持为水平线，即吞吐 量达到饱和。这就表明网络负载中有一部分损失掉了( 例如，输入到网络的某些 分组被某个结点丢弃了) 。虽然如此，在这种理想的诮塞控制作用下，网络的吞 吐量仍然维持在其所能到达的最大值。 但是实际网络的情况就很不相同了。从图1 3 可以看出，随着网络负载的增 大，网络吞j 吐量的增长速度逐渐减小了。也就是说，在网络吞吐量还未达到饱和 时，就已经有一部分的输入分组被丢弃了。当网络吞吐量明显地小r 理想的吞吐 量利，网络就进入了轻度拥塞了的状态。更值得注意的是，当网络负载达到某一 数值时，刚络的吞吐量反而随网络负载的增大而下降这时网络就进入了捌塞状 态。当网络负载继续增大剑某一数值时，网络的吞吐量卜- 降到零，嘲络已无法工 作。这就是的死锁( d e a d l o c k ) 。加e 合适的拥塞控制以后，网络就不易出现拥 塞现象和死锁，但是如图1 ，3 所示，需要付出的代价是：当网络负载较小时，有 捌摧控制的吞吐量反面比无拥塞控制时要小。 第一辛引苦 吞吐量 曲_ 图1 3 拥塞控制的作用示意图 1 1 4 拥塞控制与流量控制的区别和联系 拥塞控制与流量控制的关系密切，他们之间也存在一些差别。拥塞所要做的 都有一个前提，就是网络能够承受现有的网络负荷。拥塞控制是一个全局性的过 程，涉及到所有的主机，所有的路由，以及与降低网络传输性能有关的所有因素。 相反，流量控制往往指在给定的发送端和接收端之间的点对点通信量。流量 控制所要做的就是使发送端发送数据的速率不能使接收端来不及接收。流量控制 几乎总是存在着从接收端到发送端的某种直接反馈，使发送端知道接收端是处_ 丁 怎样的状况。 可以用一个简单的例子说明这种区别。设有一个光纤网络，其链路传输速率 为1 0 0 0 g b s 。用一个巨型计算机向一个p c 机以1 0 g b s 的速率传送一个文件。 显然，网络本身不存在拥塞的问题。但是流量控制是必须的。巨型机必须经常停 下来，以便使p c 来得及接收。 但是如果另有一个网络，其链路传输速度为1 m b s ，而有1 0 0 0 台计算机连 接在这个网络。假定有5 0 0 台计算机分别向其余的5 0 0 台计算机以1 0 0 k b s 速率 发送文件。那么现在的问题已不是接收端是否来得及接收，而是整个网络的输入 负载是否超过网络所能承受的。 拥塞控制和流量控制之所以常常被弄混，是凼为某些搠塞控制算法是向发送 端发送控制报文，并告诉发送端网络已出现麻烦，必须放慢发送速率。这点又和 流量控制是很干h 似的。 1 2 拥塞控制算法的概况 1 2 1 拥塞控制算法设计的要求和难点 拥塞控制算法设计的要求和难点主要体现在以下方面【5 】【6 】： 1 ，算法必须具有很好的适应性。i n t e r n e t 中各处的网络性能有很大的差异，算 法必须具有很好的适应性；另外由于i n t e m e t 对报文的j f 确传输不提供保证， 算法必须处理报文丢失、乱序到达等情况。 2 ，公平性、效率、稳定性和收敛性。拥塞控制算法对性能有很高的要求，包括 算法的公平性、效率、稳定性和收敛性等。某些性能目标之问存在矛盾，在 算法设计时需要进行权衡。 3 算法的分布性。拥塞控制算法的实现分布在多个网络节点中，必须使用不完 整的信息完成控制，并使各节点协调工作，还必须考虑某些节点工作不正常 的情况。 4 算法的代价。拥塞控制算法必须尽量减少附加的网络流量，特别是在拥塞发 生时。在使用反馈式的控制机制时，这个要求增加了算法设计的困难。算法 还必须尽量降低在网络节点( 特别是网关) 上的计算复杂性。目前的策略是将 大部分计算放在端节点完成，在网关上只进行少量的操作，这符合i n t e r n e t 的 基本设计思想【7 1 。 1 2 2 拥塞控制算法的分类 根据控制方式，控制位置，传输模式和设计结构，拥塞控制有多种不同的分 类方法。从图1 4 可以看出这些分类。 幽14 扪塞控制分类 第一章，；i 焉 1 由于计算机网络是一个很复杂的系统，因此可以从控制理论的角度来看拥塞 控制这个问题。从控制理论的角度出发，拥塞控制算法可以分为，：环控制和 闭环控制两大类心j 。7 f 环控制就是在设计网络肘，事先将有关发生拥塞的剧 素都考虑周全，力求网络在 ：作时不产生拥塞。例如，当流量特征可以准确， 性能要求可以事先获得时，可以使用开环控制。但是，当流量特征不能准确 描述或者当系统不提供资源预留时，适于使用闭环控制。1 玎t e m e t 中主要采 用闭环控制方式。 闭环的拥塞控制分为以下三个阶段： 检测网络系统以便检测到拥塞在何时、何地发生； 将拥塞发生的信息传送到可以采取措施的地方； 拥塞控制点根据拥塞信息进行调整以消除j 爿! | 塞。 有很多方法可以用来检测网络的拥塞。主要的一些指标是：由于缺乏缓 冲空间而丢弃的分组的百分数；平均队列长度：起时重传的分组数；平均分 组时延：分组时延的标准差等。上述这些指标的增长都标志若捌塞的增长。 2 根据算法的实现位置，可以将拥塞控制算法分为两大类：链路算法( 1 i n k a l g o r i t h m ) 和源算法( s o r c ea l g o r i t h m ) i 。其中链路算法对应为i p 拥塞控制， 源算法对应为t c p 摺塞控制。链路算法在网络设备( 如路由嚣裙交换祝) 率执 行，作用是检测网络拥塞的发生，产生拥塞反馈信息；源算法在主机和网络 边缘设备中执行，作用是根据反馈信息调整发送速率。拥塞控制算法设计的 一个关键问题就是如何生成反馈信息和如何对反馈信息进行响应。 3 ，根据参与通信的用户1 数量的不同，网络传输又可以分为单播“n i c a s t ) 和组播 ( m u l t i c a s t ) 4 1 】两种。相应地，拥塞控制也可以分为单播拥塞控制和组播拥寒 控制两种。所谓单播是指通常所说的点对点( p o i n t t op o i n t ) l 墅j 传输，而组播是 指一对多的传输方式，即一个放送端，多个接收端， 以上从不同角度对拥寒控制进行了分类，但实际列络中采用的拥塞控制往往 不能归一到某一类，它们通常是几种控制方式的结合。 1 2 3 拥塞控制算法的研究热点 目前拥塞控制算法的研究热点包括【1 0 u 4 0 】： 1 ，“慢启动”过程的改进i n i i “】。众所周知，目前 d l e i j l e t 上的一个主要应用一 h 订p 的流量主要是短数据。另一方面，网络结构利状态变得复杂，己经不 容易很快得到一个t c p 连接的最佳参数设置。因此，传统的慢启动有两个问 题：其一，由于它从发送一个数据包丌始，所以要经过多个r t t ( r o u n d t r i p t i m e ) 才能到达一个最优的流量点，这对小流量但是链路时延又比较大的t c p 流f 常不利；其二，由于发送端并不了解可利用的刚络资源，采用指数方式的增 长经常错误地引导发送端过快过多地发送突发性的数据包，从而引发瓶颈链 路的拥塞。这方面的研究包括：增大摺塞窗口的初始值，文献3 】推荐将初始 拥塞窗口的值由1m s s ( m a x i m u ms e g m e n ts i z e ) 增加到4 m s s ；将“慢启动” 过程分为多段，逐步减小窗口增长的速度，平滑从“陧启动”到“拥塞避免” 的过渡4 t 。 2 快速恢复的改进。快速恢复的改进方案有很多，比较著名的包括 n e w r e n o t c p ，s a c k ，f a c k ( f o r w a r da c k n o w l e d g m e n t ) 。 s a c k 允许接 收端向发送端通告所有的正确接收到的数据，从而使发送端只需重传真j 下丢 失的数据包。n e w r e n o - t c p 不需要s a c k ，f a c k 是基于s a c k 的。s a c k 和f a c k 能有效地从多个数据包丢失中恢复，但是它们大大增加了t c p 的 复杂性，需要接收端对发送端的配合，不易大规模地应用。文献【1 5 】建议t c p 同时实现n e w r e n o 和s a c k ，在应用中根据接收端是否支持s a c k 来选择 最好的快速恢复策略。 3 a c k 过滤( a c kf i l t e r ) 。它的目的是保持t c p 的“自时钟”( s e l fc l o c k i n g ) 机 制吼“自时钟”机制可减轻突发报文对网络的冲击，而“a c k 压缩”( a c k c o m p r e s s i o n ) l 1 q 破坏了“自时钟”机制。文献旧建议在网络中增加 p e p ( p e r f o r m a n c ee n h a n c ep r o x y ) 来确保a c k 报文之间的间隔。 4 减少不必要的“超时重传”和“快速重传”。当重传发生时，t c p 为了降低 传输速率都会、撼小搠塞窗口。然而r t t ( r o u n dt r i pt i m e ) 测量的准确性和乱序 报文都会影响t c p 做出正确的判断。e i f e l 算法1 1 8 l 通过在应答报文中增加特 殊信息来解决这个问题。 5 ，e c n ( e x p l i c i t c o n g e s t i o nn o “f i c a t j o n ) 的使用 1 9 】【加1 。端系统通过报文中网关没定 的标志位检测拥塞，而不完全依赖报文丢失来判断拥塞的发生。在无线恻络 环境中，e c n 的使用有利于将报文损坏( p a c k e tc o r r u p t i o n ) j 1 拥塞导致的报文 丢失区分开。 6 t c p f r i e n d l y 的拥塞控制【2 l 】 2 2 】。随着各种视频通讯需求的出现，多媒体的传 输要求速率不能剧烈变化，并和t c p 的传输保持公平。t c p f r i e n d l y 定义 2 3 1 为：长时间的吞吐量不超过相同条件下t c p 连接的吞叶量。针对这个需求 提出了t c p f r i e n d l y 的捌塞控制。它使用基于速率的控制，速率的训。算建曲： 存t c p 吞吐量模型1 2 4 l 的基础上。 7 t c p 在无线链路闭、卫星链路【2 6 】和非对称”链路( a s y m m e t r i cl i n k ) t 2 7 】上的 拥塞控制。这些链路的特点为高延迟、高丢失率、两个方m 传输链路的性能 不村f 刚，这砦环境中的捌塞控制算法需要增加特殊的考虑。 8 随着网络中“流”( f l o w ，指一个t c p 连接) 数日的增加，刚关的平均队列眭 度会逐渐增加。一些研究者使用真实实现对r e d 进行试验【”1 1 2 8 i ，也反映出 相同的问题。因而需要根据网络中负载的情况对标记丢失概率进行动态调 整。 1 3 本文的工作 本文的工作包括以下几个方面： 介绍拥塞控制的基本概念，包括拥塞和拥塞控制的概念、i n t e m e t 的网络模 型、i n t e m e t 中拥塞发生的原因；介绍了拥塞控制算法的概况，包括、拥塞控制 算法设计的困难和拥塞控制算法的研究概况。 对当前流行的多个网络仿真平台进行了比较，尤其对n s 一2 网络仿真平台进 行了介绍。 介绍了一种新的面向多媒体通信的流控制传输协议s c t p ，将其和t c p 协议 进行比较，分析了s c t p 的长处和弱点，并设计了仿真实验来测试s c t p 的性能， 发现在避免h o l 现象上，s c t p 并没有期待的那么好。 根据拥塞控制实现的位置，将拥塞控制划分为t c p 拥塞控制和i p 拥塞控制。 对不用版本的t c p 拥塞控制算法进行了探讨。分析了t c p 拥塞控制的四个阶段 f 慢启动、拥塞避免、快速重传、快速恢复) ，以及各个阶段的作用。 i p 拥塞控制是整个拥塞控制体系中不可缺少的一部分，本文对一些具有代 表性的i p 拥塞控制算法进行了介绍与分析。其中重点介绍了随机早期检测r e d 算法，并结合动态部分缓存共享( d p b s ) 策略，对标准r e d 算法进行了改进，并 通过仿真证明改进后的r e d 算法能够克服标准r e d 算法的两个缺陷：无优先级， 不能满足o o s 的要求；对窄带t c p 不公平。 1 4 本文结构 本文按以下方式展开： 在第一章中，说明了拥塞控制的意义，并总结了当前拥塞控制的研究概况， 包括 j 塞控制当前的研究热点，捌塞控制算法设计的困难，拥塞控制算法的分类 等。接下来介绍了本文的贡献。 在第二章巾，介绍了i n t e r n e t 的发展历程、体系结构、拥塞和拥塞控制的概 念、拥塞控制算法的评价方法。 在第三章中，对当前流行的多个网络仿真平台进行了比较，尤其对n s 一2 网 络仿真平台进行了介绍。 在第四章中，介绍了一利新的面向多媒体通信的流控制传输协议s c y p ，并 将其和t c p 功议进行比较，分析了s c t p 的长处和弱点，并设计了仿真实验来 测试s c t p 的性能，发现在避免h o l 现象上，s c t p 并没有期待的那么好。 在第五章中，对t c p 拥塞控制和i p 拥塞控制进行了深入全面的探讨，对已 有的一些标准算法进行了研究和比较，分析了它们各自的长处和弱点，并将动态 裔l ；分缓存共享d p b s 策略引入到r e d 算法中，对标准的r e d 算法进行了改进。 并进行了仿真，仿真结果表明改进后的r e d 算法能够克服标准r e d 算法的两个 缺陷：无优先级，不能满足q o s 的要求；对窄带t c p 不公平。 最后一章对本文的工作进行了总结，并对未来的研究思路和方向进行了展 望。 第章i n t e r n e t 平i i 拥塞控制 第二章i n t e r n e t 和拥塞控制 2 1i n t e r n e t 的发展历程 i n t e r n e t 是当前全球最大的、最开放的、以t c p i p 协议族为核心的、由众 多网络互连而成的计算机网络。它的发展可追溯到7 0 年代中期a r p a ( a d v a n c e d r e s e a r c hp r o j e c t a g e n c y ，美国国防部远景规划局) 为实现异种网络之间的互连 ( i n t e r c o n n e c t i o n ) 与互通( i n t e r c o m m u n i c a t i o n ) 建立的a r p a n e t 试验网。当时 a r p a n e t 仅是一个用5 0k b p s 线路连接着几十台计算机，并使用网络控制协议 n c p ( n e t w o r k c o n t r o lp r o t o c 0 1 ) 传输数据的小型网络。 2 0 世纪7 0 年代末，随着大规模集成电路( l s 0 技术的发展，大量小型和微 型计算机开始涌现，局域网( l a n ) 技术也发展起来，这样就产生了小型和微型机 与远程主机相互通信的需求。为此，a r p a 开始了一个称为i n t e m e t 的研究计划， 主要研究如何将各种l a n 和广域网( w a n ) 互连起来。1 9 7 3 年a r p a n e t 扩展 成国际互联网，第一批接入的有英国和挪威计算机。1 9 7 4 年r p a 的鲍勃凯恩 和斯坦福的温登泽夫全合作提出了称为网际协议i p 和传输控制协议t c p 的 两个协议，使不同的计算机及网络可以相互通信。以这两个协议为核心，以 a r p a n e t 为主干许多不同的网络开始相互互连，构成了i n t e r n e t 的原型。 a r p a n e t 的主要特点是实现了资源共享、分散控制、分组交换和分层网络协议， 这些特点被认为是现代计算机网络的般特征，被其后的网络设计广泛采用。 进入8 0 年代，随着a r p a 将a r p a n e t 各站点的通讯协议全部转为 t c p i p ，标志着全球i n t e r n c t 的j f 式诞生，t c p h p 也随之广为流传开来。之后， i n t e r n e t 规模呈指数增长，到1 9 9 6 年已有1 7 5 个国家，2 4 万个网络，10 0 0 万 台计算机接入i n t e r n e t ，网上用户达到7 千多万人。而且还以每年一倍的速度增 长。 我国i n t e m e t 的发展较晚，但却- 卜分迅速。9 0 年代，我国先后建立了中固 公用计算机互联网( c h i n a n e t ) ，中国教育科研计算机陋 ( c e r n e t ) ，中国科学技 术计算机 x x ( c s t n e t ) ，中国金桥互联嗣j ( c h i n a g b n 3 四大骨干网，为n t e r n e t 在 我幽的使用、发展奠定了良好的基础。据中因互联网信息巾心统计，截止到2 0 0 4 年1 2 月3 1h ，我罔的一卜网计算机总数达到了4 1 6 0 万台，是1 9 9 7 年1 0 月第一 次调查结果2 9 9 万台的1 3 9 1 倍。 互联网的成功主要归因于分组交换、无连接的删络层和t c p 的椭塞控制。 首先，i n t e r a e t 丌创了分组交换的先河，与传统的电路交换4 目比，分组交换很好 第二章i n t e n a e t 和拥塞控制 的适应了突发数据传输的要求，提高了带宽利用率，为i n t e m e t 提供了高效的传 输技术。其次，采用i p 作为互联网的网络层，一方面为异种网之间的互联、互 通提供了平台，另一方面，由于i p 的无连接机制，网络资源分配相对简单，从 而降低了网络设备的复杂度。最后，由于互联网采用t c p 拥塞控制机制，避免 了端到端流量控制的拥塞崩溃问题，为i n t e m e t 的不断扩展提供了基础。 2 2 开放系统互联参考模型( i s o o s i ) 2 2 1l s o o s i 层次结构 国际标准化组织i s o ( i n t e r n a t i o n a ls t a n d a r d so r g a n i z a t i o n ) 及下属的计算机与 信息处理标准化技术委员会于1 9 8 4 年正式颁布了一个称为开放系统互连基本 参考模型o s i ( o p e ns y s t e mi n t e r c o n n e c t i o nb a s i cr e f e r e n c em o d e d 的国际标准 i s o o s l 7 4 9 8 。自此计算机网络开始了走向国际标准化网络的时代，困际标准化 网络具有统一的网络体系结构，遵循国际标准化的协议，能支持各厂商生产的计 算机网络设备的互连。 但是，i s o o s i 模型仅仅规定了每层应该作什么，并没有对每一层的协议进 行确切的描述，因而并没有被真正实现，它只代表一个理想化的网络，主要用于 教学和网络协议设计的参考。其结构如下图2 1 所示。 7 应用层 6 表示层 5 会蹯层 4 传输层 3 网络层 2 数据链路层 l 物理层 圈2 1i s o o s l 参考模型 各层功能简要介绍： ( 1 ) 物理层定义了为建立、维护和拆除物理链路所需的机械的、电气的、 功能的和规程的特性，其作用是使原始的数据比特流能在物理媒体l ：传输。具体 涉及接插件的规格、0 、“1 ”信号的电平表示、收发双方的协调等内容。 ( 2 ) 数据链路层一- 比特流被组织成数据链路协议数据印元( 通常称为帧) t 并 第一? 章i n t e r n e t 和拥塞控制 以其为单位进行传输，帧中包含地址、控制、数据及校验码等信息。数据链路层 的主要作用是通过校验、确认和反馈重发等手段，将1 i 可靠的物理链路改造成对 网络层来说无差错的数据链路。数据链路层还要协调收发双方的数据传输速率， 即进行流量控制，以防止接收方因来不及处理发送方发来的高速数据而导致缓冲 器溢出及线路阻塞。 ( 3 ) 网络层一数据以网络协议数据单元( 分组) 为单位进行传输。网络层关心 的是通信子网的运行控制，主要解决如何使数据分组跨越通信子嘲从源传送到目 的地的问题，这就需要在通信子嘲中进行路由选择。另外，为避免通信子网中出 现过多的分组而造成网络阻塞，需要对流入的分组数量进行控制。当分组要跨越 多个通信子网才能到达目的地时，还要解决网际互连的问题。 ( 4 ) 运输层一是第一个端到端，也即主机到主机的层次。运输层提供的端到 端的透明数据运输服务，使高层用户不必关心通信子网的存在，由此用统一的运 输原语书写的高层软件便可运行于任何通信子刚上。运输层还要处理端到端的差 错控制和流量控制问题。 ( 5 ) 会话层一是进程到进程的层次，其主要功能是组织和同步不同的主机上 各种进程间的通信( 也称为对话) 。会话层负责在两个会话层实体之间进行对话连 接的建立和拆除。在半双工情况下，会话层提供一种数据权标来控制某方何时 有权发送数据。会话层还提供在数据流中插入同步点的机制，使壬导数据传输因网 络故障而中断后，可以不必从头开始而仅重传最近个同步点以后的数据。 f 6 ) 表示层一为上层用户提供共同的数据或信息的语法表示交换。为了让采 用不同编码方法的计算机在通信中能相互理解数据的内容，可以采用抽象的标准 方法来定义数据结构，并采用标准的编码表示形式。表示层管理这些抽象的数据 结构，并将计算机内部的表示形式转换成网络通信中采用的标准表示形式。数据 压缩和加密也是表示层可提供的表示变换功能。 ( 7 ) 应用层是开放系统互连环境的最高层。不周的应用层为特定类型的网络 应用提供访问o s i 环境的手段。网络环境下不同主机间的文件传送访问和管理 ( f r a m ) 、传送标准电子邮件的文电处理系统( m h s ) 、使，小同类型的终端和主机 通过阀络交互访问的虚拟终端( v n 防议等都属于应用层的范畴。 2 2 。2 服务接口和协议 山于错误的时问、错误的技术、错洪的实现和错误的政策，使得i s o o s i 模型没有被实际的网络设计所采用。但1 s o o s i 提供了3 个有益的概念服务、 接口和协议。下面给出它们的定义： ( 1 ) n 务每一层都为其直接相邻上层提供相应的服务，每层的服务定义该层 第章i n t e r n e l 和拥塞控制 能作什么，而不管上层如何访问它，该层如何 作和怎样实现。服务是通过些 服务原语向上层提供的。 ( 2 ) 接口接1 2 1 是相邻层之问相互通信的一个服务访问点。每一层的接口告诉 上层的进程如何访问它。它定义了调用的参数以及预期的返回结果。同样，它也 和该层如何工作无关。 ( 3 ) 协议为进行计算机网络中的数据交换而建立的规则、标准或约定的集 合。协议总是指某一层协议，准确地说，它是对同等实体之怕j 的通信制定的有关 通信规则约定的集合。 2 3i n t e r n e t 体系结构 2 。3 。1i n t e r n e t 参考模型 i n t e m e t 参考模型又称为t c p i p 参考模型，该模型也是一个层次模型，它 主要从使用性的角度考虑，因而相对于i s o o s i 参考模型来说更为简单。由于 t c p i p 是先于o s 模型开发的，因而并不符合o s i 标准。大致来说t c p 对应 o s l 模型的传输层，i p 对应网络层，i n t e r n e t 参考模型与i s o o s i 模型对比如 图2 2 所示。 7 应用层 6 表示层 5 会话层 4 传输层 3 网络层 2 数据链路层 1 物理层 应用层( t e l n e t f t p s m t p 等) 传输层t c p ， 1 0 p ，s c r p 网际层i p 网络接门层 图2 2t c p i p 模型与i s 0 0 s i i n t e r n e t 参考模型与i s o o s i 模型的区别在于，o s i 模型层次清晰，每一层 都有确确的功能，而t c p i p 的层次划分不够清楚，例如：t c p i p 早期就没有区 分服务、接u 和协议的概念。i n t e m e t 模型是先有实现后有模型，实际上i n t e m e t 模型是为了描述t c p i p 协议栈而提出来的。t c p i p 协议族是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 r n e t 列拥塞控制 2 4 拥塞和拥塞控制 2 4 1 什么是拥塞 当网络中存在过多的报文时导致网络的性能急剧下降，这种现象称为捌塞。 拥塞和i n t e m e t 的设计机制有着密切的联系。可以使用下图2 3 来描述拥塞的发 生。 吞吐量 。厂 c l i r f 一 负载 延迟 i c i i f f 负载 图2 3 拥塞的发生 当负载较小时，吞吐量的增长和负载相比基本呈线性关系，延迟增长缓慢； 在负载超过k n e e 之后，吞吐量增长缓慢，延迟增长较快；当负载超过c l i f f 之 后，吞吐量急剧下降，延迟急剧上升。可以看出，负载在k n e e 附近时，网络的 使用效率最高。拥塞控制就是网络节点采取措施避免拥塞的发生或者对拥塞的发 生做出反应，在图2 3 中就是使负载保持在k n e e 附近。拥塞控制的目的是使负 载不超过网络的传输能力，使网络运行在高吞吐量、低延迟的状态下。拥塞控制 算法包含拥塞避免( c o n g e s t i o na v o i d a n c e ) 平d 拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 两种不同 的机制。捌塞控制用来保证网络刁i 进入c l i f f 右边的区域；拥塞避免工作在k n e e 处，它鼓励用户增加负载只要不使延迟迅速增加就可以，这样保持负载在k n e e i 奄、 2 4 。2 拥塞的危害 如果对网络摺塞不加以控制，就会使得包丢失率增加、延迟增大、系统吞吐 量降低，严重的还会导致拥塞崩溃的发生。拥塞的危害具体表现为以下几个方而： 1 ) 延迟增加。拥蹇发乍时，路山器缓冲队列长度增加，分组等待排队输 n 的时 间变长，进而导致延迟的增加。糟糕的是，随着延迟的增加还会引起超时亟 1 4 第一二章i n t e m e t 和拥塞控制 传，更多的分组进入网络，进一步加重拥塞程度。 2 ) 包丢失率增大。由于搁塞，路由器不得不丢弃些分组，在路由器缓存溢出 的情况下，随后到达路由器【e | 勺分组都会被丢弃。路由器采用的丢弃策略，直 接影响着系统的性能。 3 ) 资源利用率降低。拥塞会导致资源利用率的降低，例如路由器缓存被输出到 某一链路的分组占满，此后通往其它链路的分组都会被丢弃，造成这些链路 得不到充分利用，资源无效利用率增加。在拥塞节点处被丢弃的分组，此前 消耗的网络资源都成为无用消耗，降低了资源的有效利用率。 4 ) 导致拥塞崩溃。拥塞的持续恶化，会导致拥塞崩溃的发生。这是最为严重的 后果。此时，几乎无任何有效的数据传输，网络进入死锁状态。f l o y r d 在文 献【6 】中总结了j 封塞崩溃的几种形式分别为负载崩溃、未达分组导致的拥塞崩 溃、分段重装导致的拥塞崩溃、过时分组导致的崩溃以及控制分组流量增加 导致的拥塞崩溃。 2 4 3 拥塞控制算法的评价方法 在设计和比较拥塞控制算法时，需要一定的评价方法。从用户r 的角度出发， 可以比较端系统的吞吐率、丢失率和延迟等指标，这些是用户所关心的。由于拥 塞控制算法对整个网络系统都有影响，在评价算法时更应该从整个系统的角度出 发进行考虑。两个重要的评价指标是资源分配的效率和资源分配的公平性。 资源分配的效率