（计算机软件与理论专业论文）fast+tcp拥塞控制机制公平性的改进研究.pdf

摘要 随着计算机技术的发展，i n t e r n e t 在过去十几年中迅速发展，其规模的迅速膨 胀和用户数量的急剧增长不仅对网络设备提出了更高的要求，也对网络拥塞问题的 研究提出了新的挑战。现有的网络拥塞控制算法远远无法满足未来网络的需求。近 年来针对高速网络进行研究的源端拥塞控制算法成为拥塞控制算法的研究热点之 一 实现拥塞控制的算法可以根据实现的位置不同分为两大类：在端系统上使用的 源算法( s o u r c ea l g o r i t h m ) 以及在网络设备上使用的链路算法( 1 i n ka l g o r i t h m ) 。 衡量拥塞控制算法的标准有效率、公平性、稳定性，收敛性等，其中公平性是最重 要的标准之一。 本文分析了现今应用最为广泛的实现源端拥塞控制算法的t c p 协议，重点研究 了由加州理工学院提出的针对高速远距离网络的t c p 拥塞控制算法一f a s t t c p 的 拥塞控制机制及其公平性问题。通过理论分析和仿真实验对f a s tt c p 协议的公平 性问题进行了研究，并比较分析了f a s t 和r e n o 之间的公平性问题。 针对f a s tt c p 在重路由和持续拥塞情况下存在的缺陷，本文提出了相关的改 进算法，并通过仿真实验对改进后的f a s t 协议的公平性进行了分析研究。 关键字：f a s tt c p 、拥塞控制、公平性 硕士学住论文 m a s t e r st h e s i s a b s t r a c t i nr e c e n ty e a r s ，r a p i di n f l a t i o no f i n t e r a c ts c a l ei sn o to n l yb r o u g h tf o r w a r da l l i g h e r r e q u e s tt on e t w o r ke q u i p m e n t ，a l s oi m p e l l e de m b e d d e dr e s e a r c hi nc o n g e s t i o nc o n t r 0 1 t h e r ea r et w op r i m a r yc o m p o n e n t si ne n d t o - e n dc o n g e s t i o nc o n t r o l ：o n ei st h el i n k a l g o r i t h me x e c u t e db yn e t w o r kd e v i c e s ，s u c ha sr o u t e r so rs w i t c h e s ；t h eo t h e ri st h e s o u r c ea l g o r i t h me x e c u t e db yh o s tc o m p u t e r so re d g ed e v i c e s a n df a i r n e s si so n eo f m o s ti m p o r t a n tc r i t e r i o nt om e a s u g ec o n g e s t i o nc o n t r o lm e c h a n i s m f a s tt c pi st h en e wv a r i a n to f t c pp r o p o s e db yn e t l a b w ea n a l y s i st h e c o n g e s t i o nc o n t r o lm e c h a n i s ma n df a i m e s so f f a s tt c p t h em a j o rw o r ko f t h i sp a p e r i si m p r o v i n gf a s tt c pt oa v o i du n f a i r n e s si nr e r o u t i n ga n da v o i dp e r s i s t e n tc o n g e s t i o n k e yw o r d ：f a s tt c p , c o n g e s t i o nc o n t r o l ，f a i m e s s i i 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：日期： 年月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名：至动 日期：钾年岁月刀日 导师签名：影杯军 日期：沙四年，月枷 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。圆重迨塞握窑厘澄蜃! 旦兰生；旦= 生；旦三生筮查。 作者签名：互动 日期：御年歹月趱日 导师签名：己辫手 日期：哆年厂月列日 硕士学位论文 m a s t e r st h e s i $ 第一章绪论 当一个子网或者子网的一部分中出现太多分组的时候，网络的性能开始下降。 这种情况称为拥塞。实现拥塞控制的算法由两部分组成：在端系统上使用的源算 法以及在网络设备上使用的链路算法。源算法中使用最广泛的是t c p 协议中的拥塞 控制算法。t c p 协议是目前i n t e r n e t 上使用最广泛的传输协议，它所实现的拥塞控 制算法对解决网络上的拥塞问题有着举足轻重的作用。 1 1 研究背景及意义 随着互联网规模的不断增长，现今的i n t e r n e t 在规模、速度、负载和连接性 上已经远远超出了过去的网络环境。随着网络技术的发展，出现了快速长距离( f a s t l o n g d i s t a n c e ) 网络、高带宽延迟乘积( h i g hb a n d w i d t h d e l a yp r o d u c t ) 网络等各 种高速网络。 这些高速网络主要用于教育科研等项目，支持端到端的大数据量的传输，一些 需要传输大量实时数据、图像和媒体文件的应用经常通过这些高速网络进行数据传 输，此外高速网络还可用于语音、媒体通讯和各种远程高速虚拟环境。由于高速网 络具有广泛的应用前景，也因为现有的t c p 拥塞控制算法仅适用于普通网络，并且 其本身固有的不足也使t c p 的拥塞控制逐渐成为了网络稳定高效运行的瓶颈，因此 适用于高速网络的拥塞控制算法成为当前的研究热点。 在t c p 协议实现的拥塞控制算法中，每个源主机通过调整拥塞窗口的大小来改 变源端的传输速率，从而对网络中出现的拥塞做出响应。关键问题之一在于，t c p 使用的是一种分布式的方法来实现拥塞控制，源端只能通过获得网络状态信息来确 定拥塞窗口的大小。 在各种拥塞控制算法中，主要的两个目标是：一、避免网络拥塞的产生以及在 拥塞发生后解除拥塞；二、为每个连接提供公平的服务。在异构或同构的网络连接 中保证公平的带宽分配是网络能够被广泛应用的一个重要特性。公平的服务包括探 测流对网络拥塞的错误反应以及不公平的占用网络资源( 网络资源包括路由器缓冲 区以及链路带宽等) 。 公平性是拥塞控制算法中最重要的特性之一。由于t c p 协议的拥塞算法能够很 好的分布在网络中，因此获得了广泛的应用，但同时也带来了一些问题。首先，源 端只能获得有限的网络状态信息，而根据这些信息，源端可能会对网络拥塞做出错 硕士学位论文 m a s t e r st h e s i s 误的判断和反应。其次，用户可能有意或无意的修改t c p 协议的实现代码，而我们 无法确定这些修改过的t c p 协议能够正确的处理网络拥塞。当网络发生拥塞时，以 上两种情况可能导致源端无法正确的控制窗口大小，结果造成持续不断的发包。这 种情况可能导致网络拥塞状况无法减轻，也可能使其它正确执行t c p 拥塞控制算法 的流无法获得公平的带宽分配。 t c p 协议中另一个主要问题是t c p 的拥塞控制算法倾向于具有较小r t t 的流。 由于t c p 协议使用的窗口控制算法的缺陷，使得具备较长r t t 的流无法同相同链路 中具有较小r t t 的流获得相同的带宽，这也导致了t c p 协议拥塞控制算法不公平性 的产生。 现有的一些研究指出，网络在拥塞控制问题上占主动地位，网络的参与对提高 连接之间的公平性有着重要作用。因此，对现今应用最广泛的源端拥塞控制算法t c p 协议以及各种不同的t c p 协议版本进行公平性研究有着重要意义。 1 2 国内外研究现状分析 最初的t c p 协议仅有流控制，而没有拥塞控制。报文接收方通过t c p 首部将自己 的接收能力通报给发送方，这种做法忽略了网络的传输能力，最终导致网络崩溃的 发生。1 9 8 6 年1 0 月，在大规模网络崩溃发生后，人们开始对拥塞控制领域进行大量 研究。 现有的i n t e r n e t 中各种版本的t c p 协议使用的拥塞控制策略一般包括慢启动、 拥塞避免、快速重传和快速恢复这4 个核心算法。在经历了从p a h o e 到r e n o 再至 n e w r e n o 等多个版本的演化后，t c p 协议中实现的拥塞控制算法r e n o 得到了广泛的 应用并获得了良好的效果。但随着t c p 带宽迟延的持续增加，r e n o 自身最终会成 为影响其性能的瓶颈。 近年来，在拥塞算法方面的研究热点主要有“慢启动”方面的改进，基于速率 的控制策略，t c p f r i e n d l y 的拥塞控制，e c n ( e x p t i c i tc o n g e s t i o nn o t i f i c a t i o n ) 的使用，快速重传和快速恢复的改进，网络容量探测机制的改进等。 由于公平性是拥塞控制算法的重要特性之一，因此，针对t c p 拥塞控制机制的 公平性研究也成为拥塞控制机制的研究热点之一 t c pv e g a s 是于1 9 9 4 年由l a w r e n c eb r a k m o 和l a r r yp e t e r s o n 提出，用来作 为r e n o 的替代版本。它使用队列延迟代替r e n o 中的丢包机制来衡量拥塞。v e g a s 能够在没有路由器帮助的情况下改善t c p 连接间的公平性。v e g a s 通过观察已发送 数据包的r t t 来控制拥塞窗口的大小，当r t t 增大时，v e g a s 便认为网络出现拥塞， 2 硕士学位论文 m a s t e r st h e s i s 相应的调整拥塞窗口的大小：当r t t 减小，v e g a s 则认为网络拥塞状况减轻或消除， 会相应的增加拥塞窗口的大小。 v e g a s 显著改善了r e n o 中的不公平现象，它不会惩罚具有大的传播时延的数据 流。1 。v e g a s 在平衡状态下的目标是在链路中保持相同数量的数据包，而r e n o 则会 不停的发送数据包以获得丢包率信息，因此当v e g a s 和r e n o 竞争同一条链路带宽 时，协议问的不公平性便体现出来。 仅依靠源端机制，无法完全保证连接之间资源分配的公平性。由于t c p 协议将 网络看作一个黑盒，t c p 源端在有其它连接共享瓶颈链路时无法准确地获得网络资 源利用状况，因此路由器支持的队列缓存以及资源分配机制能够帮助源端改善连接 间的公平性问题。 本文所研究的f a s tt c p 协议是t c p 协议演化的最额版本之一，它是在t c pv e g a s 的基础上发展而来的，是一个更为稳定的协议版本。其中实现的拥塞控制算法能够 稳定的获得高利用率以及高吞吐量。由于f a s tt c p 协议在稳定性、效率、公平性 等方面比r e n a 有显著提高。因此对在针对高速网络拥塞控制方面，对f a s tt c p 协 议公平性的研究也是当前的研究热点之一。 通过给每个流最先发送的数据包头添加优先级信息，减少传播时延的测量误 差，可以在持续拥塞状况下改进f a s tt c p 协议的公平性啪1 。修改窗口控制机制， 镗够将f a s tt c p 扩展成为符合( 瑾，| ) 比例公平性的协议，从而提高f a s tt c p 协议 的公平性。由于f a s tt c p 同v e g a s 一样，将队列延迟作为拥塞信号，因此对r t t 测量的准确性会直接影响f a s tt c p 协议的性能。利用测量技术周期性检测网络主 于链路，根据链路性能为竞争连接设定适当的期望冗余参数包，鹾够在不依赖路由 的条件下使瓶颈排队趋向于一个固定长度，使f a s tt c p 不会随着连接的增多降低 其公平性。 由于f a s tt c p 在设计时没有考虑重路由和持续拥塞闯题，因此在这两种情况 下，f a s tt c p 协议的公平性仍然是一个开放性问题。如何在f a s tt c p 协议和其它 基于丢包率的协议共享链路带宽的情况下，保证不同连接之间的公平性也是当前的 研究热点之一。 1 3f a s $ t c p 协议介绍 f a s tt c p 协议是加州理工的n e t l a b 实验小组在2 0 0 4 年研究实现的一种新型 t c p 拥塞控制协议。它针对当前高性能网络的高速、长延迟、大容量的特点，对传统 t c p 拥塞控制机制进行了全面、根本的改进。 f a s tt c p 的拥塞控制机制与传统的基于丢包率的拥塞控制机制不同，该机制是 一个基于平衡的算法，通过该算法调整f a s tt c p 的窗口机制，使得使用f a s tt c p 协议的流能够逐步到达平衡状态，从而消除了数据包级的震荡问题。f a s t 继承了 v e g a s 的做法，使用队列延迟作为衡量网络拥塞的主要方法，由于在高速长距离的 网络中，队列延迟比丢包率提供了更准确地信息，使源端能够更准确的判断拥塞的 发生。 f a s tt c p 在平衡状态下，目标是在瓶颈路由的队列中维持一定数量的数据包， 从而避免拥塞的产生并持续获得高的链路利用率。f a s tt c p 通过测量已发送数据包 的r t t 来控制拥塞窗口大小。 1 4 主要工作及论文结构 本文针对t c p 协议的最新变种之f a s tt i 协议进行分析研究，通过理 论分析及模拟实验相结合的方式，对f a s t t c p 的平衡状态、稳定性、吞吐量、公 平性等方面进行了分析，对f a s tt c p 协议和现有的r e n o 的协议间的公平性、协 议内的公平性进行了比较，研究表明，在以上各方面，f a s tt c p 协议都具有更好 的性能表现。但由于使用队列延迟作为主要拥塞信号，使得f a s t 在和r e n o 等基 于丢包的拥塞控制协议竞争网络资源的情况下，无法公平的获得资源分配。 由于使用队列延迟作为主要拥塞信号，也使f a s t t c p 协议在重路由或持续拥 塞的情况下，性能受到较大影响。本文针对f a s t t c p 协议在重路由和持续拥塞情 况下存在的问题，对f a s t 的r t t 测量模块及窗口更新机制进行了改进研究，并通 过n s 2 进行模拟，验证了所提出算法的正确性以及对公平性方面改进的效果。 本文的内容结构安排如下： 第一章介绍了本文的研究背景和意义，对国内外的研究现状进行了分析，简 述了f a s tt c p 与传统的t c p 协议在拥塞控制机制上的不同，并列出了论文结构。 第二章介绍了拥塞控制的基础知识，分析了源端拥塞机制的重难点，详细分 析了现在广泛应用的t c p 协议r e n o 的拥塞控制机制及其存在的问题，对本文重点 研究的协议f a s tt c p 进行了理论分析。 第三章介绍了网络公平性研究需要的具备的一些基本概念，详细分析了f a s t t c p 协议在公平性上的优缺点，并同r e n o 的公平性进行了比较分析，对f a s tt c p 协议在重路由和持续拥塞情况下存在的问题进行了分析，并提出了改进算法，并定 性的分析了算法的正确性以及对公平性改进的效果。 4 硕士学位论文 m a s t e r 。st h e s l s 第四章分析了改进后的f a s t a 协议在参数选择上可能出现的各种问题，对 f a s t a 协议在重路由和持续拥塞情况下的性能进行了分析研究，验证了该算法在公 平性上的改进效果。 第五章对全文进行了总结，并对现有工作中仍存在的问题进行了分析，提出 了下一步研究工作的设想。 第二章t c p 拥塞控制算法研究 2 1 拥塞控制算法概况 2 2 1 拥塞和拥塞控制 当一个子网或者子网的一部分中出现太多分组的时候，网络的性能开始下降。 这种情况称为拥塞( c o n g e s t i o n ) 。”。当主机发送到网络上的数据量低于网络的传输容 量时，除了在传输过程中因传输错误无法正确到达目的主机的数据包外，大部分数 据将被正确发送至目的主机。然而随着通信量的增加，当用户发送的数据量超出网 络的传输容量时，网络就会产生拥塞。 图1 给出了数据吞吐量与给定负载之间的关系，显示出了最佳操作点k n e e 和 拥塞崩溃区。开始时网络负载较轻，网络带宽未被完全利用，吞吐量与负载量呈正 比。当吞吐量继续上升，最终会保持在一个稳定的值，该稳定值和链路带宽的最大 限制值相等，此时，数据包开始在链路中排队。当负载进一步加重，吞吐量会出现 “悬崖”效应在很短的时间内迅速下降最终接近于0 。 0 ，t i m d 1 0 d ( b i t s s ) 图1 数据吞吐量与给定负载的关系 拥塞控制机制试图减少和消除这种“悬崖”效应一网络崩溃。一个好的拥塞 控制算法的目标是通过调整资源，从而提供最佳负载，使网络始终处于图中曲线的 左转折处。 拥塞控制机制可分为拥塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控带d j ( c o n g e s t i o n c o n t r 0 1 ) 两种类型。拥塞避免算法是一种“预防”机制，用于k n e e 点之前，目标是 为了使网络维持在高吞吐量、低延迟状态，避免网络拥塞的发生。拥塞控制算法是 6 一hro#彳薯cbiti，o 硕士学位论文 m a s t e r st h e s i s 一种“恢复”机制，用于k n e e 点之后，用于拥塞产生后将网络从拥塞状态中快速 恢复过来并重新进入拥塞避免阶段。 2 2 2 拥塞产生的原因 拥塞产生的原因是对网络的需求大于网络的实际承载能力。当网络中有限的资 源被多用户共享时，如果没有相关的机制控制流入网络中的数据量，则必然会导致 网络拥塞甚至网络崩溃的发生。 拥塞一般发生在网络资源相对短缺的位置。拥塞发生点的不均衡性反映了 i n t e m e t 的不均衡性。网络的不均衡性表现在两个方面，一是网络带宽的不均衡性， 由于网络设施的不同，在不同的路径中具有不同的带宽，当数据从高带宽的链路进 入低带宽的链路时，可能会发生拥塞；二是流量分布的不均衡，不同的数据流以不 同的速率进入网络，当主机发送数据包至网络的速率过高，超过网络的承载能力时， 会产生拥塞。在互联网中，资源和流量分布的不均衡都是广泛存在的，因此，仅靠 增加网络资源的方式，远不足以解决网络拥塞的问题。 2 2 3i n t e r n e t 网络模型 拥塞的发生和互联网的设计机制有着密切关系，互联网的网络模型可以用以下 几点进行抽象： 1 分组交换网络 分组交换也称包交换，它将用户传送的数据划分成一定长度，每个部分成为一 个分组。在每个分组前加上一个头部，用来标示该分组的目的地址，然后交换机通 过每个分组的地址标志，将其转发至目的地。这一过程称为分组交换。进行分组交 换的通信网称为分组交换网。 分组交换网络是在“存储转发”的基础上发展起来的，这种网络结构同时 具有电路交换和报文交换的优点。和电路交换网络相比，分组交换网络提高了资源 的利用率。和报文交换网络相比，分组交换网络具有较小的传输时延河更好的交互 性。 2 无连接( c o n n e c t i o n l e s s ) 网络 无连接的网络指网络中的节点在传输数据前不需要建立连接。这种连接模式简 化了网络的设计，在网络的中间节点上不需要保存和连接有关的状态信息。但该模 型在用户需求大于网络资源时很难保证服务质量；由于该模型对发送源的追踪能力 较差，也给网络安全带来了隐患；无连接的网络模型也是造成乱序报文出现的主要 原因之一。 7 硕士学位论文 m a s t e r st h e s i s 3 尽力交付( b e s t - e f f o r t ) 的服务模型 尽力而为网络不对数据传输的服务质量提供保证。尽管最近几年提出了很多的 方案，如集成服务删、区分服务1 等服务模型用于提供网络服务质量的保证，但是 尽力而为网络的服务模型简单实用，在当前和未来的网络中，该模型仍占有重要的 比重。 2 2 4 拥塞控制的理论方法 从控制理论的角度，拥塞控制算法可分为开环控制和闭还控制两大类嘲1 。当系 统流量特征可以准确规定、性能要求能够事先获得的情况下，使用开环控制算法更 合适；当流量特征无法准确描述或者当系统不提供资源预留时，可以使用闭环系统。 在i n t e r n e t 中采用的是闭环控制方式。 闭环的拥塞控制分为以下三个阶段：监测网络中拥塞的发生；将拥塞信息反馈 给拥塞控制点；拥塞控制点根据拥塞信息进行调整从而消除拥塞。闭环的拥塞控制 可以动态的适应网络的变化，但其算法性能受到反馈延迟的严重影响。当拥塞发生 点和控制点之间的延迟很大时，算法的性能会受到严重影响。 实现拥塞控制的算法可以根据实现位置的不同分为两大类：在端系统上使用的 源算法( s o u r c ea l g o r i t h m ) 以及在网络设备上使用的链路算法( 1 i n ka l g o r i t h m ) 。 源端算法在主机和网络边缘设备中执行，根据链路的反馈信息调整源端的发送速 率。链路算法在网络设备中执行，其作用是检测网络拥塞的发生，并将网络状况反 馈给源端，并采取一些预防拥塞的措施。 源算法中使用最广泛的是t c p 协议中的拥塞控制算法。t c p 协议是目前在互联 网中使用的最广泛的传输协议。其中使用的拥塞控制算法已经成为保证互联网稳定 性的重要因素。 链路算法的研究目前主要集中在“主动队列管理”( a c t i v eq u e u em a n a g e m e n t ， a q m ) 算法方面。和传统的尾部丢弃算法相比，a q m 在网络设备的缓冲溢出之前就丢 弃或标记报文。 a q m 能够公平的处理各种t c p 流，避免多个t c p 连接由于队列溢出而同时进入 “慢启动”状态，并能维持较小的队列长度，在高吞吐量和低时延之间做出合理的 平衡。 硕士学位论文 m a s t e r st h e s i s 2 2t c p 拥塞控制研究 2 2 1i c p 协议的拥塞控制算法介绍 在各种源端的拥塞控制算法中，t c p 的拥塞控制算法是使用的最为普遍和成功 的拥塞控制算法。它使用了序列号、校验和、确认以及超时重传等机制，为用户提 供了可靠的数据传输。t c p 的拥塞控制由慢启动、拥塞避免、快速重传和快速恢复 四个核心部分组成，下面分别介绍这四种算法： 1 慢启动 早期开发的t c p 应用在启动一个连接时会向网络中发送大量的数据包，这样容 易导致路由器缓存空间耗尽，使网络产生拥塞，从而导致t c p 连接吞吐量的急剧下 降船1 。由于t c p 源端无法得知网络资源当前的利用状况，因此新建立的t c p 连接不 能一次发送大量数据，而只能采用逐步增加发送数据量的方法，从而避免拥塞的发 生。 当建立新的t c p 连接时，拥塞窗口( c o n g e s t i o nw i n d o w ，c w n d ) 初始化为一个 数据包大小。源端按照拥塞窗口的大小发送数据报，当每次收到一个a c k 确认时， 拥塞窗口的大小增加一，这时c w n d 随着回路响应时间( r o u n d t r i p t i m e ，r r r ) 呈指 数增长。使用慢启动方法，要达到每个r t t 发送w 个数据包的量仅需时 r t t x l o g w 。 2 拥塞避免 由于传输引起数据包丢失的概率很小( 1 ) ，因此如果t c p 源端发现超时或收 到3 个相同的a c k 副本时，便认为网络发生了拥塞，随后便进入了拥塞避免阶段。 此时慢启动的阈值( s s t h r c s h ) 被设置为当前拥塞窗口大小的一半，如果收到的是超时 信息，则将拥塞窗口设置为1 。当c w n d s s t h r e s h 时，t c p 协议启动拥塞避免算法。 在拥塞避免阶段。c w n d 每次收到一个a c k 时只增加一个1 c w n d 个数据报，在一个 r t t 内，c w n d 仅增加1 。因此在拥塞避免阶段，c w n d 不是呈指数增长，而是线性增 长。 3 快速重传 j a c o b s o n 提出了对拥塞避免算法的改进，实现了当收到一个乱序包时，接收端 可以发送一个复制a c k 。这个a c k 的目的是告诉发送端有乱序包并且通告该包的 序号。 t c p 并不知道复制a c k 是由于包的丢失引起的，还是由于包乱序引起的。但 9 硕士学位论文 m a s t e r st h e s i s 如果认为是乱序包引起的，在乱序包处理前应当只有1 个或者2 个a c k 。如果有3 个或者超过3 个复制a c k 收到，则认为是由于丢包引起的，因此重传包而不等重 传计时器超时。这种机制就是快速重传机制。 4 快速恢复 重传了丢失的数据包后，执行拥塞避免算法而不是慢启动算法，这就是快速恢 复算法，这样可以在中等程度拥塞的情况下支持高输出。快速恢复是基于“管道” 模型( p i p em o d e ) 的“数据包守恒”原则( c o n s e r v a t i o no fp a c k e t sp r i n c i p l e ) 嘲， 即同一时亥在网络中传输的数据包数量是恒定的，只有当“旧”的数据包离开网络 后，才能发送“新”的数据包进入网络。 快速重传和快速恢复算法通常结合在一起实施。 a ) 当收到第三个复制a c k 时。s s t h r e s h 设为当前窗口拥塞的一半，但不小于2 。 重传丢失的数据段。设置c w n d 为s s t h r e s h + 3 x s e g m e n t 。这就实现了根据离开网 络的数据段和接收端缓存的数据段来扩大c w n d 。 b ) 每次当另外一个复制a c k 到达时，将c w n d 增加l 。这就为已经离开网络的数 据段扩大了拥塞窗口。 c ) 当下一个对新数据认可的a c k 到达时，将c w n d 设为s s t h r e s h ，这个a c k 是 对第一步中重传的数据段的认可。 2 2 2t o p 拥塞控制的改进和优化 虽然t c p 协议已被广泛的应用，但在实际应用中仍然存在很多不足之处，因此 对t c p 协议拥塞控制机制的改进研究一直都是业界研究的热点问题。目前针对t c p 拥塞控制机制的改进主要集中在以下几个方面： 1 “慢启动”的改进 t c p 的延迟响应算法一直被证明有损于t c p 的性能，而慢速启动算法又经常是 以大量报文段的丢失而终止的。这些显然都损害了t c p 的性能。通过改进慢启动算 法，能够缩减到达接收方报告的窗口尺寸所需要的时间，从而避免大量报文段丢失。 “慢启动”阶段对短数据的传输更为重要，而“拥塞避免”阶段对长数据的 传输更为重要。在慢启动方面的研究主要包括：增大拥塞窗口的初始值：通过将“慢 启动”过程分段，逐步减小窗口增加的速度，使“馒启动”阶段能够平滑的过渡到 “拥塞避免”阶段1 ；或通过多个流共享网络状况信息，从而根据网络的实际情况 决定初始的阈值”。 2 基于速率( r a t e - b a s e d ) 的控制策略 i o 硕士学位论文 m a s t e r s 下h e s i s t c p 使用的窗口控制策略有一些缺陷：容易导致报文的突发：发送速率受到窗 口大小的限制；一个窗口内多个报文的丢失不容易恢复等“。 为了解决这些问题，一些研究者提出r b p ( r a t e b a s e dp a c i n g ) ，将窗口控制和速 率控制结合起来。但在拥塞发生时，r b p 会导致多个连接同时丢失报文，从而出现 “全局同步”( g l o b a ls y n c h r o n i z a t i o n ) 的现象，严重降低网络的吞吐量。而且实现r b p 需要大量高精度的时钟，会消耗大量资源。1 。 3 a c k 过滤 a c k 过滤的主要目标是保持t c p 协议的“自时钟”( s e l f d o c k i n g ) 机制。该机 制可以减轻突发报文对网络的冲击。有研究指出可以通过在网络中增加 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 报文之间的间隔1 。 4 快速重传和快速恢复的改进 当在单个窗口中有多个报文丢失，快速重传会将每个丢失的报文当作独立的网 络拥塞信息，因此t c p 会多次将拥塞窗口大小减半，从而引起网络性能的严重降低。 对快速重传的改进包括n e w r e n o ，s a c k ，f a c k 等。 5 e c n ( e x p l i c i tc o n g e s t i o nn o t i f i c a t i o n ) 的使用 源端通过报文中网关设定的标志位来检测拥塞的发生，而不完全依赖报文丢失 来判断拥塞的发生。e c n 的使用有利于将由于传输错误导致丢失的报文和拥塞导致 丢失的报文区分开来。 6 t c p f r i e n d l y 的拥塞控制 对多媒体数据的传输，很多情况下要求其速率不能发生剧烈变化，但要能对网 络拥塞作出正确响应，并保持和t c p 协议间的公平性。t c p - f r i e n d l y 的定义为：长 时间的吞吐量不超过相同条件下t c p 连接的吞吐量。在保证公平性方面还存在对非 t c p - f r i e n d l y 协议的惩罚措施o ”等方法。 7 特殊网络环境下的拥塞控制 特殊网络环境包括无线链路，卫星链路和非对称链路。这些链路延迟高，丢失 率高，双向传输性能不同。在这些网络环境中的拥塞控制算法需要增加特殊的机制。 2 2 3t o p 拥塞控制算法的主要问题 拥塞控制算法的问题主要集中在效率和公平性上。现有的t c p 协议在如何获得 商效以及良好的公平性上仍存在许多未解决的问题。 1 高效 如何获得高效是t c p 拥塞控制算法的重点问题之一。高效指所使用的解决方案 硕士学位论文 m a s t e r st h e s i s 能够带来高的网络利用率。高的网络利用率指相互竞争的数据流都具有高的、端到 端的吞吐量和较低的延迟。如果发送端要求的总资源和网络所能提供的资源相等或 接近，则可以认为拥塞控制算法的效率较高：如果出现网络负载不足或超载，则可 认为算法效率不高。因此，效率与总资源的利用率有关，而与各个端系统的资源利 用率无关。 2 公平性 t c p 拥塞控制算法的公平性主要表现在两个方面：一、在使用相同协议的数据 流之间如何保证公平性；二、在使用不同传输协议的数据流间如何保证公平性。 当网络出现拥塞时，必然会发生资源竞争，竞争能力强的数据流将得到更多的 网络资源，而竞争能力较差的流则会明显效率低下。网络拥塞会导致不公平性的产 生，丽网络资源分配的不公平会加重网络拥塞的状况，甚至会造成网络崩溃的发生。 研究表明，不同的窗口大小、r 1 u r 的值以及数据包的长度都会影响t c p 流对带宽的 占用。较大的窗口，较小的r t t 值以及较大的数据包都会导致t c p 流占用更多的带 宽。 3 效率和公平性 公平性和高效是两个相互制约的因素。效率和公平性通常存在一些矛盾。最大 化带宽的分配有时会导致部分流分配到的带宽为零，从而造成不公平性。效率和公 平性之间存在某种平衡。当效率最大时，网络资源分配可能出现极端的不公平现象。 相反，公平的资源分配方案可能导致较低的网络利用率。 2 2 4t o p 协议的公平性 一个合理的i n t e r a c t 资源分配方案是实现服务质量分级和保证。为了实现这一 目标，集成服务( i n t e g r a t e ds e r v i c e s ) 。”和区分服务( d i f f e r e n t i a t e ds e r v i c e s ) 1 等多种 i n t e m e t 体系模型相继被提出。 集成服务提供端到端的质量保证服务或可控负载服务。但由于其实现方案是完 全分布式的，因此这种控制方式的实现极其复杂。区分服务模型的基本思想是在网 络的边界部分根据用户和i s p 事先约定的服务等级协议以及数据流量的实际情况对 分组进行分类，并进行相应的标记，写入i p 数据报的头部。在网络内部通过该标 记选择转发方式。虽然这种实现方式简便，适用于大型网络，但对服务质量难以实 现严格的保证。 尽力交付服务模型虽然是当前网络中存在的最普遍的服务方式，但依靠链路端 进行拥塞控制的方法仍离大规模的应用还有一段相当长的时间，因此在这种服务模 j 2 式里，源端的t c p 拥塞控依仍将长期发挥其作用。在目前的网络模型和将来的 i n t e r n e t 体系中，t c p 拥塞控制算法在资源分配时的公平性是一个极为重要问题。 虽然研究者们提出了一些对现有t c p 拥塞控制算法的改进方案+ ，但这些方 法都没有考虑到r t t 对带宽的公平分配带来的影响。 r e n o 在两个阶段增加拥塞窗口的大小：“馒启动”阶段和“拥塞避免”阶段。 当t c p 发送方在时刻f + 收到一个a c k ，则窗口c w n d ( t + f 。) 由删h d ( ，) 更新为： 1 “慢启动”阶段 c w n d ( t ) + 拼，如果c w n d q ) “f ) ， 在下一个窗口，将每m a x f 刚) 一以f ) 】，w o ) ，1 个a c k 后将w ( i ) 大小增加一；如果 戳f ) 1 ；如果偏重 于反应时间，则取口 o 。 ， 其中g 扛，r n 。 硕士学位论文 m a s t e r l st h e s i s 当f a s tt c p 流到达平衡状态时，其吞吐量可表示为： 蕾= 竺( 1 4 ) q i 其中口是f a s t t c p 在到达平衡状态时源端i 在链路缓存里的数据包数量。 在r e n o 中，每个r t t 内将拥塞窗口大小加l ，因此具有较小r t t 的连接，窗 口增加的速率比具有较大i m 的连接快，从而占用更多的带宽，造成带宽分配不公。 f a s tt c p 和r e n o 不同，它不惩罚具有较大传播时延的数据流。根据公式1 4 可以看 出，当一个连接具有较大的传播时延时，源端i 为了在平衡点维持固定数量的数据 包在链路中，f a s tt c p 会给该连接一个较大的拥塞窗口。 f a s tt c p 的协议内公平性仅在链路能力下降时才会受到其它协议的影响。而 f a s tt c p 的协议间公平性能够通过计算f a s tt c p 的参数矩阵口获得，但如何仅 依靠本地信息正确的计算该矩阵仍然没有确定的解决方法“。 f a s tt c p 和r e n o 、h s t c p ( h i g h s p e e dt c p ) 、s t c p ( s e a l a b l et c p ) 相比，具 有最好的公平性索引因子“。由于在f a s tt c p 中，每个连接都试图在平衡状态下 维持相同数量的数据包在队列中，因此相互竞争的源端会获得相等的瓶颈带宽资 源。 3 。2 2f a s tt o p 协议在公平性方面仍存在的问题 虽然f a s tt c p 从实验分析和在l i n l l ) ( 系统下的实现情况来看，在公平性上同 其他t c p 协议的变种相比具有较好的性能，但仍存在一些尚未解决的问题0 1 。 首先，根据f a s t t c p 的窗口更新公式可以看出，当砌r r 测量结果比实际r t t 更大时，会使f a s t t c p 的窗口的增长速率更为温和，从而占用较少的带宽，不利 于f a s tt c p 与其它l o s s b a s e d 机制的t c p 协议竞争带宽。 第二，f a s tt c p 中，具有较长r t t 的连接与较短r t t 的连接相比具有较高 的队列延迟，这使得具有较长r t t 的连接在平衡状态下在队列中保持较少的数据 包，因而占用了较少的带宽。 第三，网络环境通常是变化的，当发生重路由以及持续拥塞现象时，由于f a s t t c p 使用的是基于队列延迟的拥塞控制方法，因此当对b a s e r t t 的测量不准确时， 会对f a s tt c p 的性能造成极大影响，从而影响f a s tt c p 连接的公平性以及效率。 硕士学位论文 m a s t e r st h e s i s 3 3f a s tt c p 中的重路由问题 3 3 1f a s tt c p 中重路由问题介绍 由于使用队列延迟作为拥塞的衡量标准，在某些情况下，可能会对f a s tt c p 协议的性能造成很大影响。其中之一便是重路由问题。f a s tt c p 在提出时没有任 何机制来处理连接的重路由问题。本节讨论f a s t t c p 中存在的重路由问题和该问 题对f a s tt c p 连接可能产生的影响。 当f a s tt c p 根据传播时延b 弱e r t t 来调整其窗口大小时，传播时延测量的准 确性对f a s tt c p 的连接显得非常重要。而重路由路径的改变可能导致连接的传输 延迟的变化，当新的传播时延大于重路由前的传播时延时，连接的吞吐量会剧烈下 降，从而使f a s tt c p 的连接无法获得公平的带宽分配。 在f a s tt c p 中，使用b 硒e r t t 作为最小r t t ，其中b a s e r t t 的值是测量出 的连接链路中的传播时延。当一个f a s tt c p 连接的路由改变时，路由器并没有任 何信息能够通知源端这一变化。当新的路由中的传播时延比之前的传播时延短，由 于f a s t 会将较短的传播时延更新为b a s o r t t ，因此这种改变不会对f a s tt c p 的 连接造成任何严重的影响。 但当新的路由中的传播时延比之前的传播时延长，f a s tt c p 连接无法分辨这 种增长是由于网络拥塞还是重路由引起的。由于缺乏确定的信息，源端会将这种现 象解释为网络拥塞，并减小其拥塞窗口。然而在这种情况中，从理论上分析，源端 应该增加窗口大小而不是将窗口减小。具体分析如下： 假设连接i 的传播时延为d l ，窗口大小为，发包率为鼍，则连接保持在链路 中的数据包数量为w 一吐。由于f a s tt c p 在到达平衡后，其目标是在链路中保 持数量为口的数据包，当传播时延增加时，连接应该增加拥塞窗口的大小从而维持 链路中数据包的数量。 由于f a s tt c p 对时延测量的依赖，r t t 测量结果的不准确或改变会对f a s t t c p 连接的性能和公平性造成较大的影响。本文模拟了一个简单的网络环境来分析 f a s tt c p 如何处理传播时廷的改变。 图6 重路由模拟网络拓扑 在我们的仿真实验中，采用图6 显示的哑铃形的拓扑结构，链路中共有两个连 接，链路带宽为1 5 m p b s ，传播时延为1 0 r e s ，连接2 的传播时延固定为1 3 4 m s ，我 们通过修改r 2 到s 3 的链路延迟来改变连接1 的传播时延。在t = 1 5 s e c 时，连接l 的传播时延从1 3 4 m s 变为8 8 m s ，在t = 3 6 s e c 时，传播时延从8 8 m s 变为4 8 4 m s ，在 f = 6 0 s e c 时，传播时延从4 8 4 m s 变厨8 8 m s 。数据包大小为1 0 0 0 b y t e s 。 图7f a s tt c p 重路由模拟中的平均队列长度 图8f a s tt c f 重路由模拟中的窗口大小 通过图8 可以看出，当连接1 的传播时延由8 8 m s 变为4 8 4 m s 后，f a s tt c p 窗口持续减小，虽然6 0 s e e 时传播时延重新变为8 8 m s ，但是其窗口大小却因连接2 占用了过多的带宽而无法恢复到之前的大小，从而造成了f a s t t c p 连接问的资源 分配不公。 3 3 2 对f s tt o p 重路由的改进研究 由于网络中的交换机不会通知源端关于路由的改变状况，因此需要源端能够探 测到路由相应的改变。本文对f a s tt c p 的b a s e r t t 测量以及窗口更新机制进行了 改进研究，通过最近时刻的r t t 的增加来判断重路由的发生，从而解决f a s tt c p 协议中由于重路由引起的性