（电工理论与新技术专业论文）internet中关于模糊拥塞控制算法的研究.pdf

a b s t r a c t w i t ht h er a p i dp r o g r e s so fi n t e m e t ，t h ea m o u n to fi n f o r m a t i o nh a si n c r e a s e d r a p i d l ya n dt h ec o n g e s t i o no fi n t e m e th a sb e c o m em o r ea n d m o r es e r i o u s - t r a d i t i o n a l b e s t e f f o r tm o d e la s s u m e st h a ta l la p p l i c a t i o n sa r ec o l l a b o r a t i v e ，a n da p p l yw i t h e n d - t o e n dc o n g e s t i o nc o n t r o lm e c h a n i s m u s u a l l yr o u t e rd e a l sw i t hc o n g e s t i o nb y t h em e t h o d ss u c ha sf i r s t i n f i r s t - o u ta l g o r i t h ma n dt a i l d r o pa l g o r i t h m h o w e v e r , w i t ht h er a p i di n c r e a s eo fi n f o r m a t i o n ，t h o s et r a d i t i o n a lc o n g e s t i o nc o n t r o lm o d e l sa l e u s e f u ln ol o n g e r s o ，s o m ee x c e l l e n tc o n g e s t i o nc o n t r o lm e t h o d ss h o u l db es t u d i e d f u r t h e r u s u a l l yi nt h ep r o c e s so fc o n g e s t i o nc o n t r o lt h e r ea r es e v e r a lp h a s e si n c l u d i n g n o r m a l ，c o n g e s t i o na v o i d a n c ea n dc o n g e s t i o n b e c a u s eo ft h eu n c e r t a i n t y i n d i s t i n g u i s h i n gt h et h r e ep h a s e sf r o me a c ho t h e r , s o m et r a d i t i o n a lm e t h o d sa l en o ta b l e t oo b t a i ns a t i s f a c t o r ye f f e c t h o w e v e gf u z z yc o n g e s t i o nc o n t r o la l g o r i t h mb a s e do n f u z z yt h e o r yu t i l i z e sf u l l yt h ep r e d o m i n a n c eo ff u z z yt h e o r yi nd e a l i n gw i t ht h e u n c e r t a i ne v e n t s ，t h e no b t a i n sf a i rt h r o u g h p u tb yc o m b i n i n gt h ew h o l ec o n t r o lw i t h t h el o c a lc o n t r 0 1 o nt h eb a s i so fs t u d ya n dd e v i c e ，f u z z yc o n g e s t i o nc o n t r o la l g o r i t h mi s i m p l e m e n t e di ncp r o g r a m m i n gl a n g u a g ea n dm u l t i t h r e a d i n gt e c h n o l o g y t h e e x p e r i m e n t r e s u l t sr e v e a lt h a tf u z z yc o n g e s t i o nc o n t r o la l g o r i t h mi sb e t t e rt h a n t r a d i t i o n a lc o n g e s t i o nc o n t r o la l g o r i t h m ，a n di m p r o v e so nc o n g e s t i o nc o n t r o l p e r f o r m a n c eo f r o u t e r k e yw o r d s ：c o n g e s t i o nc o n t r o l ，r o u t e r ，f u z z yt h e o r y ，c u tm a t r i x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨洼盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：热目月羊 签字日期： 2 哪年f 月乡日 学位论文版权使用授权书 本学位论文作者完全了解苤洼盘堂有关保留、使用学位论文的规定。 特授权苤盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：菇幸曰目莩 导师签名 家学军 签字日期：2 口哆年f 月多1 9签字日期：pp p ；年 月占目 第一章绪论 第一章绪论 近年来，i n t e m e t 正经历着惊人的发展，网络信息量在极短的时间内成倍地 增长，网络拥塞问题日益突出，这对网络拥塞控制的研究提出了更高的要求。本 章主要介绍了论文的相关研究背景和论文的主要内容。 1 1 引言 进入2 0 世纪8 0 年代末期以来，在计算机网络领域最引人注目的就是起源于 美国的i n t e m e t 的飞速发展。i n t e m e t 的本来意思是互联网，我国自然科学名词审 定委员会推荐的译名是“英特网”。现在，i n t e m e t 已发展成为世界上最大的国际 性计算机互联网。i n t e m e t 对世界的冲击非常大，影响到人们生活的各个方面， 这就使得2 0 世纪9 0 年代成为i n t e m e t 时代，或者网络时代。 i n t e m e t 的迅速发展始于2 0 世纪9 0 年代。由欧洲原子核研究所组织c e r n 开发的万维网w w w ( w o r l d w i d e w e b ) 被广泛应用在i n t e m e t 上，大大方便 了广大非网络专业人员对网络的使用，成为i n t e m e t 的指数级增长的主要 驱动力【1 ”。 由于i n t e m e t 存在着技术上和功能上的不足，加上用户数量激增，使得现有 的i n t e m e t 不堪重负。网络流量的整体失衡与拥塞( c o n g e s t i o n ) 成为当前i n t e r n e t 中的主要问题，严重时更是极大地影响了网络性能。 在网络中，绝大多数的客户服务器应用程序都是使用传输层的t c p 或者 u d p ，这两个协议转而使用网络层的i p ( i p v 4 或i p v 6 ) 。尽管可以绕过传输层而 直接使用i p v 4 或i p v 6 ，但这种技术( 称为原始套接口) 较少使用1 3 1 。其中，u d p 是一种简单的、不可靠的数据报协议，而t c p 则是一种精致的、可靠的字节流 协议j 。在基于t c p 的端到端的连接中都是采用相同的端到端的拥塞控制方法， 它通过在限定时间内是否收到目端的应答来判断分组是否到达，于是就会出现传 输分组的超时现象。然而在网络中造成分组超时的原因很多，但大多数分组的 传输超时是由拥塞造成的，因此，i n t e m e t 上几乎所有的t c p 算法都假设分组的 传输超时是由拥塞引起的1 5 1 。当源端检测到传输超时，数据包就要重发，不断重 发带来的是资源的浪费和拥塞的进一步恶化。此外，一些基于q o s ( q u a l i t yo f 第一章绪论 s e r v i c e ) 的高质量服务1 6 7 8 i ，如i p 电话、视频会议等，根本就不容许任何 超时或者重发。因此，作为网络中的核心转发设备路由器( r o u t e r ) 必须要加强自 身的拥塞处理能力。 通常情况下，拥塞会发生在不问的时间段、不同的网段。为了提高网络的服 务性能，必须要从源端、目的端、通信子网、路由器等许多方面来进行拥塞处理 和拥塞避免。本文在第三章中将对网络中的拥塞控制策略进行了较为详细的论 述。其中，搠塞避免和传统的闭环控制方法应当归为宏观的流量控制，它关系到 大的网络区域中网络流量的规划；而那些传统的开环控制如漏桶算法，以及那些 基于分类队列的调度算法如加权公平队列w f q ( w e i 曲t e d f a i rq u e u i n g ) 算 法、尾部丢弃t d f i f o ( t a i ld r o pf i r s ti nf i r s to u t ) 算法等【 ”1 ，它们更多的是 从微观的角度束实现对流量的控制。从总体的控制性能来看，宏观的流量控制与 微观的流量控制同等重要。 一般来说，在对网络的载荷情况进行评价时，都是以正常、拥塞避免、拥塞 三个概念来描述的 “。而在上述的那些拥塞控制算法当中，几乎所有的触发各 种算法运行的参数都是确定的值，如带宽利用率、队列长度等。然而，拥塞这一 概念本身是模糊的，用确定的值来控制模糊变量，肯定不能取得更好的效果。 目前在拥塞控制方面，开环拥塞控制和闭环拥塞控制的研究都不少，本文将 在第三章进行较为详细的论述。 1 2 论文的选题意义、创新点和论文的组织 1 2 1 论文的选题意义 传统的b e s t - e f f o r t 模型是网络中最为典型的服务模型，它假定所有的应用都 是协作的，并采用相同的端到端的拥塞控制机制，其中路由器采用先来先服务调 度算法和尾部丢弃策略来处理网络拥塞，然而，随着网络信息量的急剧增长，所 有应用的协作性问题成为矛盾，传统模型不再有效。s f - l o y d 和u j a c o b s o n 提出 的随机提前检测r e d ( r a n d o me a r l yd e t e c t i o n ) 算法【1 2 】，对路由器缓冲区队列 长度采取加权平均的办法，有效地减少了路由器的拥塞次数，它是目前绝大多数 路由器中所运行的一种较好的队列调度算法，但该算法中公平性的实现具有一定 的局限性，它的进一步应用受到限制。当前，能够适应网络信息量激增的更为优 秀的拥塞控制模型有待于进一步的研究和探索。文中所提出的基于模糊理论 第一章绪论 ( f u z z yt h e o r y ) 的拥塞控制算法，对于网络拥塞控制性能的提高，具有重大的理 论和现实意义。 1 2 、2 论文的创新点 本文在研究各种开、闭环拥塞控制算法的基础上，提出了基于模糊理论的拥 塞控制算法，并设计了两组仿真实验，验证了算法的有效性和较优性。 本文主要的三个创新点： 提出了一种新的基于优先级队列的拥塞控制数学模型。 将模糊理论引入到中所提出数学模型中，提出了基于模糊理论的拥塞 控制算法。该算法充分利用模糊推理的类人思维方式，采用整体和局部相结合的 方法，智能地处理网络拥塞，有力地保证了各t c p 、u d p 吞吐量的公平性，从 而更好地改进了路由器的拥塞控制性能。 对模糊拥塞控制算法进行设计、实现，并进行仿真实验。实验仿真结果 验证了算法的有效性、合理性和较优性。 1 2 3 论文的组织 本章为论文的绪论部分。介绍了论文的相关研究工作背景，选题意义，以及 论文的主要创新点。 第二章概括性地论述了i n t c m e t 中拥塞问题的分类和一些解决办法，并解释 了拥塞控制所存在的困难。 第三章对传统的开、闭环拥塞控制算法和各种队列调度算法进行研究，并在 此基础上提出了一种新的基于优先级队列的拥塞控制数学模型。 第四章首先讨论了与拥塞控制算法有关的模糊数学基础；并充分利用该理论 在解决不确定性问题上的优势，对本文第三章中所提出的新的拥塞控制模型进行 研究，并实现了拥塞的模糊控制。 第五章首先提出了用于仿真的网络模型和评价指标，然后再从两个角度对模 糊算法进行性能评价。 最后对本文的算法进行总结，并提出了一些相关的、有价值的研究方向。 第二章 n t e r n e t 中的拥塞问题 第二章 in t e r n e t 中的拥塞问题 网络中的拥塞问题随着网络的快速发展而变得日益严重，并逐渐成为阻碍网 络服务性能进一步提高的焦点，因此，恰当地处理好拥塞，己成为网络设各供应 商们提高网络没备服务质量、增强产品竞争力的重要方面。 拥塞控制是关于网络中资源的再分配。也就是当网络中的服务请求太多，或 者是网络载荷接近于网络的容量时，就必须对网络资源的占用情况做出调整，来 达到网络的均衡。这些网络资源包括链路带宽以及网络转发设备的缓冲区大小、 处理器速度等。尽管在网络载荷较低时，已经进行了资源的分配，但随着网络载 荷的逐渐增大，网络资源占用的公平性将成为问题。如果没有恰当的拥塞控制方 法，在网络载荷繁重的时候，网络的吞吐量将会极大地减少。 本章首先介绍了几个关于拥塞控制的错误理解。然后再系统地论述拥塞问题 的分类和一些解决办法，并解释了拥塞控制所存在的困难。最后，介绍了流量工 程与拥塞控制的关系f l 卜“l 。 2 1 关于拥塞控制的几个误解 当网络不能满足用户所要求的网络资源使用量时，就会发生拥塞。因此，人 们认为当网络设备的价格降低后，网络的拥塞问题将自动被解决，于是就产生了 如下的几个错误的理解： 1 、认为拥塞是因为缓冲区空间太小的原故，那么，当存储器的价格降低到 能够提供任意要求大小的存储器空间时，拥塞问题将得到解决。 2 、认为拥塞是因为低速链路的原故，那么，当更高速率的链路能够提供时， 拥塞问题将得到解决。 3 、认为拥塞是因为低速处理器的原故，那么，当处理器的速度大幅度提高 时，拥塞问题将得到解决。 4 、认为上述的几个方面都得到解决时，拥塞问题将得到解决。 事实上并非如此，如果没有适当的拥塞控制协议，即使上述各个方面都能够 得到满足，也会发生拥塞邮】。 第二章i n t e r n e t 中的拥塞问题 太大的缓冲区空间无益于拥塞 首先，足够大的缓冲区空间是不能够解决拥塞的，廉价的存储器对拥塞问题 没有多大的帮助。对于网络中的核心转发设备来说很大的数据缓冲区空削同很 小的数据缓冲区空间一样，都无益于拥塞。如图2 1 ( a ) 所示，由于太小的缓冲 区空闻，一些数据包要被丢弃。而太大的缓冲区空阎，如图2 一】( b ) 所示，则会 由于数据包在缓冲区中等待太长的时间而纷纷超时，而对于源端来说，所有超时 的数据包都需要重发。 一 ( a ) 太小的缓冲区 一坷) 超时 ( b ) 太大的援冲区 图2 一l 事实上，太大的缓冲区更加不利于拥塞控制，大量的因为超时而被丢弃的数 据包在到达该路由器以前所占用的网络资源将全部浪费，而重传的数据将会使拥 塞更加进一步恶化。 高速的数据链路无益于拥塞 同样，高速的数据链路也不能够解决拥塞。最初，连结计算机的电话线的传 输速度仅为3 0 0 b p s ，随着技术的进步，传输速度提高到1 5 m b p s 。再后来，出现 了更快速度的局域网( l a n s ) ，如以态网( e t l l e r n e t ) 的传输速度达到了1 0 m b p s 。于 是，人们开始关注拥塞控制技术，因为这些高速的l a n s 是通过低速的链路连 结起来的，在它们的连结接口处的拥塞成为新的瓶颈。 如果没有适当的拥塞控制策略，高速的数据链路反而会降低网络的服务性 能。如图2 - 2 所示，四个节点由三条1 9 2 k b p s 的链路相连，假设传输某一文件 用了5 分钟。现在。用一条i m b p s 的链路替换掉s 与r 之间的低速链路，则传输 同一文件的时间达到了几个小时。这是因为高速链路的存在，使得第一个路由器 的数据输入速度远大于数据离开的速度，从而建立起很长的队列，缓冲区溢出， 数据包大量丢弃，以至于传输完整个文件的时间大大增加。 第二章 n t e r n e t 中的拥塞问题 ( a ) 传输某一文件用时5 分钟( b ) 传输同一文件用时好几个小时 图2 2 造成这釉现象的关键在于高速链路不能够孤立存在，它的加入只是增加数据 包丢弃的数量。 高速的处理器无益于拥塞 此外，高速的处理器也不能够解决拥塞。与高速的数据链路一样，在网络中 只是增加处理器的速度，同样会增加网络中各处速度的不匹配程度，从而产生拥 塞。 前面的分析似乎让人认为，如果所有的链路、处理器的速度都提高到相同的 水平，拥塞将不会发生。这也是不正确的。即使这样，拥塞还是会发生。如图 2 3 所示，所有的处理器、链路的速度都是i g b p s 。如果路由器r 同时将来自a 和b 的数据向c 发送，则在同一时间内，会有2 g b p s 的输入，而输出只有1 g b p s ， 同样会发生拥塞。 图2 - 3 数据由 、b 经路由器r 发往d 拥塞的本身是一个动态的问题，采用静态的方法是不能够解决的。如上述的 一些方法，都只是静态地增大缓冲空间、提高数据链路的传输速度，或者是加快 处理器的处理速度，它们不但没有解决拥塞问题，反而加剧了网络载荷的不平衡 性，更加不利于拥塞。因此，必须要采用适当的拥塞控制方法才能处理好拥塞。 第二章 n t e r n e t 中的拥塞问题 2 2 拥塞控制的基本原理 当一部分通信子网中有太多的分组时其性能降低。这种情况叫做搠塞1 4 l 。 图2 - 4 描述了这一过程。当主机转发到通信子网中的分组数量在其传输容量之内 时，它们将全部到达目的地( 除了因传输错误而不能正确到达的少数分组外) 。且 到达目端的数量与发送的数量成正比。然而，当通信量增加太快时，路由器不再 能够应付，开始丢失分组，并会导致情况恶化，在通信量非常高的情况下，网络 将完全瘫痪，几乎没有分组到达。 轷 求 蛊 制 裂 孟魅 完美的 大传输容量 “5 ” 粼 发送的分组 图2 4 当通信量太大时，会发生拥塞，性能显著降低 拥塞控制问题主要是控制问题。绝大多数的拥塞控制都是由反馈机制和控制 机制的组合来共同完成的。根据控制论原理，控制的频率应该与反馈的频率大致 相当。如图2 5 所示，如果控制的速度比反馈的速度更快，系统将发生震荡，变 得不稳定。另一方面，如果控制的速度赶不上反馈的速度，系统将对网络的变化 反映缓慢。因此，在设计拥塞控制策略时，应用这一原理去选择适当的控制频率 是比较重要的。然而，有许多的控制方法忽略了这一原理，从而使得它们的控制 效果不太理想。 图2 5 控制速度与反馈延迟的联系 第二章i n t e r n e t 中的拥塞问题 通常情况下，拥塞持续的时间长短是不一样的。对于持续较短时间的拥塞， 如数据链路层、网络层中的优先队列、缓冲区管理策略等，能够取得较好的控制 效果。而对于持续时间较长的拥塞，则可以采用动态地增加网络资源和动态地减 少网络服务请求的方法来进行拥塞控制( 将在2 3 节中详细讨论) 。 2 3 拥塞控制的基本概况 2 3 1 拥塞控制的种类与控制方法 概括地说，在任何给定的时间窗口内，如果网络资源的总的需求量超过了可 供使用的网络资源的总量，则表明在这段时间内，已经发生了拥塞。其数学表达 式为： 需求可供使用阚络资源。 整个的计算机网络系统包括有许多种网络资源，如缓冲区、链路带宽、处理 器、服务器等1 1 6 1 。在目的端，如果缓冲区的大小不足以容纳所到达的数据量， 就会发生丢包。同样，如果共享同一数据链路的流量的总和大于链路的带宽，则 该链路就会发生拥塞。 图2 6 拥塞问题的类型 前面的关于拥塞的描述尽管简单，却有利于拥塞问题及其控制方法的分类。 如图2 - 6 所示，根据拥塞问题所涉及到的网络资源的数量，可将其分为单资源拥 塞问题和分布式资源拥塞问题。其中，单资源包括非智能化资源，如l a n s ，它 们必须由用户自己进行配置，以实现对拥塞的智能化控制。在局域网中，一些方 法，如c s m a c d ( c a r r i e rs e n s em u l t i p l ea c c e s sw i t hc o l l i s i o nd e t e c t i o n ) ，令牌 环( t o k e n r i n g ) ，以态网( e t h e r n e t ) 等”，就是单资源拥塞问题的处理策 第二章i n t e r n e t 中的拥塞问题 略。对于本身具有智能特性的单个资源，如域名服务器其本身就能够进行适当的 拥塞处理。因此对于整个网络而言，拥塞控制的难度在于对分布式资源的控制。 如链路的带宽，则要求用户的带宽使用率必须受到限制，其总和不能超过它的最 大容量。下面将主要讨沦分布式资源的拥塞控制策略。 关于分布式资源的拥塞控制策略主要有两种类型：即动态地增加网络资源和 动态地减少网络服务请求。 1 、动态地增加网络资源的控制方法：它是通过动态地增加网络资源的容量 来增大网络的载荷能力。 备用链路在网络载荷较大时，自动投入运行： 加大卫星链路的发射功率，可以增加带宽m 】； 将额外的流量分散到低载荷条件下的非最佳路由。 在上述的这些方法中，用户甚至不会知道网络中是否发生了拥塞，网络完全 是通过自身的响应来解决问题。 2 、动态她减少网络服务请求的控制方法：它是通过减少服务请求来降低网 络载荷。它们通过某种形式告知用户关于网络拥塞的现状，以便用户调整它们的 发送流量。下面是三种较为典型的控制方法。 中断服务请求。 当网络发生拥塞时，就不再接受新的服务请求。如电话正忙的声音则表示 电话网络过载的信息。同样，网络在发生拥塞时会拒绝开始任何新的服务。 降低服务级别。 这种策略要求所有的用户动态地发送数据，并随着网络的载荷情况，调节 数据发送速率，来控制拥塞。 资源预留。 用户在进入网络之前，首先进行资源预定，如果网络不能满足要求，就终 止这次呼叫“。如t c p 连结的建立过程，队列的轮询与优先级别等。 所有上述的拥塞控制策略，都要求网络能够对其当前的状态进行测量，然后 再采取相应的措施。一般来说，在这些控制策略的实现过程中，网络信息的反馈 是非常重要的。 目前，已经提出了许多种反馈机制。 第二章i n t e r n e t 中的拥塞问题 反馈信息包。 它将拥塞处的信息以数据包的形式传送到控制端。这些数据包被称为阻塞 包。而控制端再根据阻塞包所传回的信息，调节发送端的数据发送速率。当网络 出现轻微的捌塞时，这种方法比较有效。而在拥塞程度较大时，这些额终的阻塞 包将会进一步加重网络的拥塞程度。 在数据包的定义域中增加反馈字段。 这种方法将反馈信息字段直接定义在发送的数据包中，当它的相应字段被修 改后，则表示该数据包在其传输途中发生了拥塞。在源端与目的端之间进行全双 工通信时，此时的目的端通过检查拥塞字段来了解拥塞情况，并将拥塞信息捆绑 在由目的端发往源端的数据包中，告知源端，网络已经发生了拥塞。 2 3 2 拥塞控制的困难 尽管已经提出了很多的拥塞控制策略，但是有许多人还在探索新的方法。关 于这一领域的研究工作至少持续了2 0 多年脚，2 ”。主要原因有两个：一是拥塞 控制的要求使得很难找到一种满意的解决方案；二是不同的网络影响了拥塞控制 策略的设计。因此，某种网络中的控制方法在具有不同体系结构的异类网络中是 没有作用的。 首先，拥塞的控制开销要小。特别是在拥塞时，不应该增加网络的流量。这 就是一些依赖于反馈信息的控制方法应用不多的原因之一。一些研究人员建议反 馈只能在网络载荷较低的情况下使用，因此，在网络载荷比较高的情况下，通常 不宜采用反馈拥塞控制方法。 其次，拥塞控制要具有公平性。在网络载荷不高的情况下，公平性是不重要 的。然而，在网络发生拥塞时，可供使用的网络资源小于用户需求，这时，资源 分配的公平性是重要的。有关公平性的定义很多，但没有一种能够被广泛接受。 例如，一些人认为某几个用户的资源缺乏是不公平的那么，如果所有的用户都 拥有共享资源的一部分，则认为是公平的。而另外一些人则认为，即使所有的用 户都拥有一部分资源也可能会出现不公平的现象，因为资源的分配可能是不均匀 的，问题的关键在于。网络资源均匀分配的依据存在主观因素。这将给拥塞控制 的公平性带来困难。 第三，拥塞控制要具有适应性。网络的容量是不断地发生变化的。随着网络 第二章i n t e r n e t 中的拥塞问题 资源如节点和链路的上载与下载，网络的容量会增加或者减少；随着网络用户的 加入或者退出，网络资源的需求量也随之增减。因此，拥塞控制策略要与网络的 容量和需求相匹配，具有实时适应性。 第四，拥塞控制要能工作在恶劣的情况下。在网络发生拥塞时，数据包的传 输错误率和丢弃率不断增大。这时，拥塞控制还要能够正常工作。 最后，拥塞控制策略要具有整体较优性。也就是说，拥塞控制要使整个网络 工作在较优状态。有时尽管单个的用户具有较优性，但是总体的性能却不好。例 如，如果每一个用户都想得到最大的吞吐率，则可能会导致网络性能变坏，更加 严重时会使网络发生拥塞，甚至崩溃。 2 3 3 网络体系中影响拥塞控制的策略 在网络体系结构中，各种通信协议将会影响拥塞控制方法的设计，下面列举 了网络协议栈中影响拥塞的一些策略1 4 1 。 传输层 超时算法 重传策略 乱序缓存策略 确认策略 流量控制策略 往返延迟估算策略 网络层 连接机制 分组排队、服务策略 分组丢弃策略 路由选择算法 分组生命期管理策略 数据链路层 重发策略 排队服务策略 第二章】n t e r n e t 中的拥塞问题 ，流量控制策略 确认策略 分组丢弃策略 接下来从数据链路层开始，逐级向上进行讨论。重传策略处理发送者的速度 多快会超时，以及超时后传送什么。太快的发送者如果使用退后的帧来重传所有 分组，那么这对网络造成的载荷比一个使用重发方法的慢速发送者大得多。与此 紧密相连的是缓存策略。如果只是机械地丢弃乱序的分组，这些分组将不得不重 传，造成额外的载荷。确认策略也会影响拥塞。如果每个分组都要立即确认，确 认分组也将会造成额外的开销。 在网络层，虚电路和数据报之间的选择会对拥塞产生影响。因为很多拥塞控 制算法只用于虚电路子网。分组排队和服务策略关系到是否为路由器的每条输入 线路建立一个队列。每条输出线路一个队列，或者两者都有。它还关系到分组的 处理顺序( 如循环排序，或基于优先级) 。丢弃策略说明当没有剩余空间时，哪些 分组被丢弃。 路由选择算法能通过将通信量分散到所有线路上来避免拥塞，而坏的路由算 法会将过多的通信量发送到本来已经拥塞的线路上。最后，生命周期策略管理决 定一个分组在丢弃前能存活多长时间。生命期太长或太短都会影响网络的性能。 在传输层，与数据链路层类似，只是决定超时间隔更困难。因为在网络上的 传输时间比在两个路由器间的传输时间更难预测。如果时间间隔太短，会产生一 些不必要的额外分组；如果间隔太长，拥塞会减少，但是一旦分组丢失，反应时 间则会太长。 2 4 流量工程与拥塞控制 i n t e m e t 流量工程是以合理的代价克服网络拥塞，使之最小化。同样，拥塞 控制也是为了处理好拥塞，这是二者的共同目的。然而，它们是有区别的。 流量工程的宏观特性 i n t e m e t 中的流量工程定义为处理i p 网络的运行性能评价和性能优化等方面 的问题，属于i n t e m e t 网络工程的范畴m ，“，州。它包含了i n t e m e t 业务量的测 量、描述、建模和控制等技术和原理的应用。 i n t e m e t 流量工程的主要目标是同时在流量水平和资源水平上增强运行中 第二章i n t e r n e t 中的拥塞问题 的网络性能。通过解决流量导向的性能要求，同时有效、可靠、经济地使用网络 资源来达到优化的目标。流量导向的性能测量包括延迟、延迟变化、包丢失率、 和吞吐量等【”“2 ”。 1 p 网络中最重要的功能是从源节点把数据包路由到目的节点。因此，i n t e r n e t 流量工程的最重要的功能是控制和优化路由功能，以便以最有效的方式操纵通过 网络的数据包。当数据包通过网络时，它们会争用网络资源。如果数据包的到达 率超过了网络资源的吞吐能力，并且持续一定的时间，网络资源就会拥塞，结果 一部分数据包就要被丢弃。同时，拥塞也增加了传输延迟，延迟变化，限制了网 络服务的可预言性。因此，拥塞是非常不希望发生的现象。以合理的代价克服拥 塞是i n t e r n e t 流量工程的一个主要目标。 由此可以看出，流量工程是从宏观的角度来对整体的网络流量进行规划，使 拥塞最小化。 拥塞控制的微观特性 i n t e m e t 网络提供实时服务，其运行环境是非常动态的。即使是最好的、最 先进的路由算法，也不能杜绝拥寨发生的可能性。特别是一些突发性的拥塞，那 些属于网络流量控制的算法根本来不及反应，等到整体的流量重新均衡后，一些 局部的网络资源可能已经变得非常拥挤。而绝大多数的拥塞控制算法，却能够处 理好这种情况。 造成整体流量控制与拥塞控制之间的差别，主要是由于它们的一些控制参数 具有不同的性质。如在流量控制中，与流量导向有关的性能指标，是关于延迟、 延迟变化、包丢失率、吞吐量等参变量。这些参数是对网络宏观特性的度量，其 值盼获得是通过对定时间窗口内数据流特性进行测量的结果，这往往忽略某一 具体数据流当前的实时状态。雨拥塞控制策略中的许多参数如发送速率、队列长 度等则是对网络数据流的微观特性的度量。 显然，流量工程与拥塞控制各具优势，具有互补性，它们的协同工作将会使 网络运行于更加优化的状态。 第三章拥塞控制算法的研究 第三章拥塞控制算法的研究 从控制论的角度来看，网络拥塞的所有解决方案被分为两类：一类是丌环， 类是闭环2 ”。做开环控制的工具的功能包括何时接受新的信息，何时丢弃 分组，以及丢弃哪些分组，还包括在网络的不同点作计划表。所有这些的共同之 处在于，它们在做出决定的时候并不考虑当前网络的状况。 与之相比较，闭环的解决方案是建立在反馈的概念之上的。当用于拥塞控制 时，这样的方法有三个部分： 1 、 监视系统，监测何时何地发生了拥塞。 2 、 将此信息传送至可能采取行动的地方。 3 、调整系统操作以更正问题。 无论是开环还是闭环控制，拥塞控制都必须确保通信子网能运送待传输的数 据，这是全局的问题，涉及所有的主机，所有的路由器，路由器中的存储一转发 处理行为，以及所有将导致削弱通信子网负荷能力的其他因素。在只关系到某发 送者和某接收者之间的端到端的通信量时，则称之为端到端拥塞控制，本章在对 拥塞控制算法进行讨论的基础上，提出了一种新的基于分类队列的控制模型，关 于该算法的具体分析和优势将在第四章进行研究。 3 1 拥塞避免 一个当前工作正常的网络，从全局来看，是无法预料它在何时何地将会发生 拥塞，而一旦发生拥塞，其恢复过程则是缓慢的。一些在呼叫阶段所预定的网络 资源，也会由于网络在重荷的情况下而不能提供预定的服务。因而对于网络中绝 大多数的客户端，都要具有控制自身流量的能力，随时调整数据的发送速率，尽 量避免拥塞的发生。从这个角度来看，拥塞避免( a v o i d a n c ec o n g e s t i o n ) 与发生了 拥塞时所采取的控制策略同样重要。 通常源端使用基于窗口的协议来控制它的发送流量。这项任务大部分是由 t c p 来完成的，因为对于拥塞最切实的办法是降低数据传输速率。 对于网络中的绝大多数路经，由于传输两造成的数据包丢弃率是很少购 ( p ，则当数据分组到达时，总会有令牌剩余，故盯值可以与最大 分组相同。如果p 在区间，p 】上不断增大。则盯值最小也要满足分组丢弃的限 制。图示的曲线能够反映这一变化过程。 对于不确定的数据源，要选择合适的( 盯，p ) 对是不容易的，但对于大多数的 数据源，可以在如图的( 盯，p ) 曲线上找到一k n e e 点来达到均衡。 3 3 传统的闭环拥塞控制算法 莳述的些拥塞控制算法，基本上都是开环的，它们都试图在一开始就防止 拥塞的出现，而不是出现的时候再进行处理。早期在i n t e m e t 中使用的闭环拥 塞控制算法主要有：抑制分组法、虚电路子网中的拥塞控制算法和载荷脱落法 等。 3 3 。1 抑制分组法 该算法可用于虚电路和数据报子网l 。每个路由器都很容易监视其输出线 路和其它资源的利用率。例如每条线路都有一个实变量“，其值在0 0 到o 。l 之 间，它反映了该条线路最近的利用率。为保持“的预测值较准，可以周期地测取 线路瞬间利用率的离散值，( 为0 或1 ) ，于是“按下列公式进行更新： u 新= “旧+ ( 1 一c t ) f 其中常数口用于决定路由器忘记近期历史的速度。 当“值超过临界值时，输出线路就进入“警告”状态。每个新来的分组都要 查看它的输出线路是否处于警告状态。如果是，则路由器发送一个抑制分组 ( c h o k ep a c k e t ) 至1 源端主机，并在抑制分组中指明原分组的目的端，同时设置好 阻塞标记位。 当源端主机得到这个分组时，要求它按比率减少发送到特定目端的通信 量。由于其它到达同一目的端的分组或许已在途中，并还将产生更多的抑制分组， 故主机在一定固定时间间隔内不再理会与该目的端有关的抑制分组。此时间间隔 一过，主机再次监听另一时间间隔的抑制分组。如果个抑制分组到来时，线路 仍拥塞，那么主机将再次减少更多的通信量，并开始忽略后继的抑制分组。如果 第三章拥塞控制算法的研究 在监听期内没有抑制分组到来，主机则可以增加发送流量。 3 3 2 虚电路子网中的拥塞控制算法 这是一种广泛应用的防止已出现的子网情况恶化的技术，称之为许可控制 ( a d m i s s i o nc o n t r 0 1 ) 。其思路是一旦出现拥塞的信号，就不再创建任何虚电路， 直到拥塞解除。因此建立新的传输层连接的努力都将失败。 另一种方法是，允许建立新的虚电路，但要仔细选择路由，以便所有新的虚 电路绕过问题区域。如图3 - 4 ( 幻所示的子网，其中有两个路由器拥塞。假设与路 由器爿相连的主机想与路由器口所连的主机建立连接。通常，这一连接会通过图 示的拥塞点。为了避免这一情况发生，重画子网如图3 - 4 ( b ) 所示，删除拥塞路由 器及其线路。虚线表示一条绕过拥塞路由器的可能虚电路。 拥窘 掘塞 ( a ) 图3 - 4 ( a ) 一个拥塞子网 3 3 3 载荷脱落 bb ( b ) 删除拥塞之后的子网和从a 和 的条虚电路 当许多办法都不能够消除拥塞时，路由器只好使用载荷脱落。载荷脱落 l s ( l o a ds h e d d i n g ) 是一种极端的方法i j 2 ”】，即当路由器被它所不能够控制的 分组所淹没时，它只好将这些分组都丢弃。 一个路由器可以随意挑选要丢弃的分组，具体丢弃哪个分组，可能取决于所 运行的应用程序。对于文件传输，旧文件比新文件更有价值，如果丢弃7 而保留 第三章拥塞控制算法的研究 分组8 1 0 ，会在接收方产生一段空隙，而不得不重传7 l o ( 如接收者是乱序分组) ， 若丢弃分组1 0 ，却只需重传1 0 。与之相反，对于多媒体，新分组比旧分组重要 得多。 种较好的丢弃策略，是应用程序必须在其分组上标上优先级来说明它们有 多重要。当分组不得不丢弃时，路幽器将首先丢弃最低优先级的分组，然后是次 优先级的，依此类推。 给分组分级要采用一个或多个头部位以存放优先级。a t m 信元在其头部中 保留了一位作此用途，因此每个a t m 信元要么标为低优先级，要么标为高优先 级。a t m 交换机实际在决定丢弃时，要用到这一位信息。 在有些网络中，许多分组被组织为一个大单元以用于重传。如在a t m 网络 中，信息单位都是定长的信元。这些信元只是消息的一部分。当一个信元被丢弃， 最终整个消息都要重传，而不只是丢弃的信元。在这种情况下，一个丢弃了个 信元的路由器，最好也将那个消息中的其它信元一并丢弃。因为磊传输它们，只 会占用带宽。 当一个路由器感觉问题耍出现时，它最好尽早开始丢弃分组，而不是等到它 拥塞后再采取行动。 3 4 基于分类队列的拥塞控制算法 前述的些传统的开、闭环拥塞控制算法，都具有一定的拥塞控制能力。然 而，随着i n t e m e t 的迸一步发展，人们对网络的性能要求日益提高，因而必须要 开发出基于网络不同性能要求的控制策略，特别是在发生拥塞、或者感觉耍出现 问题时，要对具有不同性能要求的连接采取不同的控制策略，而不能够对谁都采 取同样的方法。 对于网络中的核心存储转发设备路由器，它必须能够区分不同的网络连接。 如一些普通的f t p 文件传输、h t t p 网页浏览文件等。在通常情况下，用户对它 们的传输性能要求不高。而其它的基于q o s 的高质量服务，如i p 电话、视频会 议、多媒体传输等，根本就不允许超时、或者重发。在网络正常时，任何连接 的服务质量都是能够得到保证的。而当网络性能变坏，或者由于某一连接发生了 拥塞，路由器就必须采取办法。特别是在共享链路带宽、处理丢报时，必须要考 虑到公平性的原则，处理好真正处于拥塞状态的数据报，有效地隔离和保护好未 发生拥塞的连接。 第三章拥塞控制算法的研究 对于这些要求较高的拥塞控制，则要按照不同的消费者和流量提供不同的控 制策略。下面接着讨论与分类队列有关的网络技术，这将为实现分类各种流量、 公平性拥塞控制提供技术支持。 3 4 1 区分服务( d if f s e r v ) 路由器在支持分类队列拥塞控制上的结 构特点 什么是区分服务( 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 是一个多服务模型【3 3 ，”i ，它可以满足不同的q o s 需 求。图3 5 说明了d i f f e r e n t i a t e ds e r v i c e 模型的基本构成元素。 1 t i 舢路由器 h 3 图3 5 区分服务( d s ) 模型 在d s ( d i f f e r e n t i a t e ds e r v i c e ) 框架中，主要包括边界功能、核心功能两个部分。 边界功能部分：实现数据流的分类。当数据报到达网络边界( 也就是具有区 分服务功能的主机所产生的数据流或者是数据流路由中的第一个具有区分服务 功能的路由器) 。如图3 - 5 所示，从主机h l 发往主机h 3 的数据包首先在路由器 r 1 中被标i 己，而从主机h 2 发往主机h 4 的数据包则首先在路由器r 2 中被标记。 其中标记是在数据包的头部设置一定的值，指明它的数据流类型。从而在d s 核 心域中收到不同类型的服务。这些服务包括立即转发、延时或者丢弃等。 核心功能部分：实现数据包的转发。当某一具有d s 标记的数据包到达 笙三童塑壅笙型蔓婆塑业壅 d i f f s e r v 路由器时，就按照该数据包的服务类型向前转发。路由器的这种转发行 为称之为p h b ( p e rh o pb e h a v i o r ) 行) b1 3 ”3 6 1 ，它会影响路由器的缓冲区和链路的 带宽。在图3 5 中，如果从h l 发往h 3 的数据包与从h 2 发往h 4 的数据包标有 相同服务类型的标记，那么，路由器在转发时会同等对待它们。否则，它们的 p h b 行为是不一样的。 区分服务( d i f f s e r v ) 路由器模型 d i f f s e r v 路由器模型定义了数据通路元素，它主要包括分类、测量、队列调 度与算法丢弃三个模块。并描述了这些元素可能的配置参数以及它们之间的连接 方式，以实现流量调节、决策数据包转发的p h b 行为。图3 - 6 描述了d i f f s e r v 路由器的框架结构1 3 7 1 。 图3 - 6d i f f s c r y 路由器的框架结构 数据输入输出：它由入口、路由器核心、出口组成。在实际应用中，路由器 可以连接任意数目的入口和出口。入口、出口部分是功能上的数据通路元素，包 括分类器、队列调度器等，支持d i f f s e r v 流量调节和数据包转发的p h b 特性。 是组成d i f f s e r v 路由器的基本部分。 配置和管理接口：d i f f s e r v 操作的参数通过接口监控和提供。监控的参数包括 不同的d i f f s e r v 服务水平的流量统计。提供的参数包括分类规则、t c ( t i m ec o n t r 0 1 ) 和p h b 配置参数。网管可通过一个或者多个管理工具如s n m p ( s i m p l en e t w o r k m a n a g e m e n tp r o t o c 0 1 ) 等，同d i f f s e r v 配置和管理接口交互。也可通过其它的路由 器配置工具如串行终端、t e l n e t 控制台等来完成配制。 可选的q o s 代理：d i f f s e r v 可以使用r s v p ( r e s o u r c er