目录 第10章拥塞控制 10.1拥塞和拥塞控制概述 10.1.1拥塞现象的发生 10.12拥塞和拥塞控制的基本概念 10.1.3互联网中拥塞发生的原因 10.14拥塞控制的目标 102TCP拥塞控制机制研究 102.1互联网的网络模型 1022线性拥塞控制机制 102.3线性拥塞控制机制评价 10、3端到端拥塞控制算法硏究 10.31端到端拥塞控制算法设计的困难 10.32端到端拥塞控制算法的研究概况 10.3.3拥塞控制的源算法 10.34拥塞控制的链路算法
目 录 第 10 章 拥塞控制 10.1 拥塞和拥塞控制概述 10.1.1 拥塞现象的发生 10.1.2 拥塞和拥塞控制的基本概念 10.1.3 互联网中拥塞发生的原因 10.1.4 拥塞控制的目标 10.2 TCP 拥塞控制机制研究 10.2.1 互联网的网络模型 10.2.2 线性拥塞控制机制 10.2.3 线性拥塞控制机制评价 10.3 端到端拥塞控制算法研究 10.3.1 端到端拥塞控制算法设计的困难 10.3.2 端到端拥塞控制算法的研究概况 10.3.3 拥塞控制的源算法 10.3.4 拥塞控制的链路算法
第10章拥塞控制 10.1拥塞和拥塞控制概述 10.1.1拥塞现象的发生 1968年,生物学教授加勒特哈丁( Garrett hardin)在《科学》杂志上发表了一篇 文章《共同的悲剧》( The Tragedy of the Commons),可以说是迄今为止描述“资源两难” 问题的最有影响力的文章。文章中哈丁认为现代人过度使用资源的后果将是面临类似于 使用同一牧场的牧人所面临的悲剧:在公用牧场中放牧的牧人会尽可能多饲养牲口以使 自己的利益最大化,而这种行为导致的长期后果是牲口的总数超出了牧场所能容纳的极 限,草资源很快枯竭,进而所有的牲口也将因为没有足够的食物而面临饿死的境地。 这一思想也可以用来阐述发生网络拥塞的原因:在网络环境中,资源被所有用户所 共享;用户都尽可能多地使用共享资源来最大化自身的利益,而不考虑共享资源的整体 状况以及其它用户的使用情况,导致网络全局的负载不断增加直至发生网络拥塞。 目前互联网广泛使用的TCP协议是一种面向连接的、可靠的、基于字节流的传输 层通信协议,最早是由 Vint cerf和 Robert Kahn在1973年提出的,当时的互联网还没 有用作商业用途。1986年10月,美国 ARPANET网络第一次发生拥塞崩溃( Congestion Collapse),导致从美国的劳伦斯伯克利国家实验室(LBL)到加州大学伯克利分校(UC Berkeley)之间的数据吞吐量降低了3个数量级,从32Kb/s急剧跌落到40bs。这是因 为,在最初的TCP协议中,只有流量控制机制( Flow Contro)而没有拥塞控制机制, 接收端可以使用TCP报头的窗口值将自己的接收能力通知发送端。由于这样的控制机 制只考虑接收端的接收能力,而没有考虑网络的承受能力,不可避免地导致了网络崩溃 现象的发生。在随后的时间里,网络拥塞崩溃的情况时常发生,直到1987~1988年间, ARPANET的主机逐渐实现了由 Van jacobson设计的拥塞控制机制后,网络拥塞崩溃的 状况才得到好转。在那之后,拥塞控制引起了更多研究者的关注,也逐渐成为互联网的 个研究热点。 网络中的拥塞源于网络资源(如链路、路由器和交换机等)和网络流量分布的不均 衡性。拥塞不会随着网络资源的增加和网络处理能力的提高而自动消除。而拥塞控制算 法的分布性、网络的复杂性和对拥塞控制算法的性能要求又使拥塞控制算法的设计具有 很高的难度。虽然在拥塞控制领域巳经开展了大量的研究工作,但是拥塞问题仍然没有
351 第 10 章 拥塞控制 10.1 拥塞和拥塞控制概述 10.1.1 拥塞现象的发生 1968 年，生物学教授加勒特.哈丁（Garrett Hardin）在《科学》杂志上发表了一篇 文章《共同的悲剧》（The Tragedy of the Commons），可以说是迄今为止描述“资源两难” 问题的最有影响力的文章。文章中哈丁认为现代人过度使用资源的后果将是面临类似于 使用同一牧场的牧人所面临的悲剧：在公用牧场中放牧的牧人会尽可能多饲养牲口以使 自己的利益最大化，而这种行为导致的长期后果是牲口的总数超出了牧场所能容纳的极 限，草资源很快枯竭，进而所有的牲口也将因为没有足够的食物而面临饿死的境地。 这一思想也可以用来阐述发生网络拥塞的原因：在网络环境中，资源被所有用户所 共享；用户都尽可能多地使用共享资源来最大化自身的利益，而不考虑共享资源的整体 状况以及其它用户的使用情况，导致网络全局的负载不断增加直至发生网络拥塞。 目前互联网广泛使用的 TCP 协议是一种面向连接的、可靠的、基于字节流的传输 层通信协议，最早是由 Vint Cerf 和 Robert Kahn 在 1973 年提出的，当时的互联网还没 有用作商业用途。1986 年 10 月，美国 ARPANET 网络第一次发生拥塞崩溃（Congestion Collapse），导致从美国的劳伦斯伯克利国家实验室（LBL）到加州大学伯克利分校（UC Berkeley）之间的数据吞吐量降低了 3 个数量级，从 32Kb/s 急剧跌落到 40b/s。这是因 为，在最初的 TCP 协议中，只有流量控制机制（Flow Control）而没有拥塞控制机制， 接收端可以使用 TCP 报头的窗口值将自己的接收能力通知发送端。由于这样的控制机 制只考虑接收端的接收能力，而没有考虑网络的承受能力，不可避免地导致了网络崩溃 现象的发生。在随后的时间里，网络拥塞崩溃的情况时常发生，直到 1987～1988 年间， ARPANET 的主机逐渐实现了由 Van Jacobson 设计的拥塞控制机制后，网络拥塞崩溃的 状况才得到好转。在那之后，拥塞控制引起了更多研究者的关注，也逐渐成为互联网的 一个研究热点。 网络中的拥塞源于网络资源（如链路、路由器和交换机等）和网络流量分布的不均 衡性。拥塞不会随着网络资源的增加和网络处理能力的提高而自动消除。而拥塞控制算 法的分布性、网络的复杂性和对拥塞控制算法的性能要求又使拥塞控制算法的设计具有 很高的难度。虽然在拥塞控制领域已经开展了大量的研究工作，但是拥塞问题仍然没有
彻底解决,拥塞控制理论和算法目前还是网络研究中的一个热点问题。 10.1.2拥塞和拥塞控制的基本概念 当在网络中存在过多的分组时,网络的性能会下降,这种现象称为拥塞。Jain等使 用图10.1来描述拥塞的发生,其中有两个关键的点,分别是膝(Knee)点和崖(Clif) 点。当网络负载较轻时,吞吐量的增长和网络负载相比基本呈线性关系,网络时延增长 缓慢;在网络负载超过膝点之后,网络的吞吐量增长缓慢,而网络时延增长较快;当网 络负载超过崖点之后,网络吞吐量急剧下降,而网络时延急剧上升。 崖点 崖点 膝点 膝点 吞吐 网络时延 网络负载 网络负载 图101拥塞发生点示意图 从图10.1可以看出,网络负载在膝点附近时,网络的使用效率最高。拥塞控制就是 网络节点采取措施来避免拥塞的发生或者对拥塞的发生做出反应。使用图10.1来说明, 拥塞控制的目标就是使网络在膝点附近工作。 流量控制是一个和拥塞控制有关的概念,它们都对数据传送的速率进行控制,但是 它们的出发点不同。流量控制主要考虑了发送过程中的发送端和接收端,它的目的是保 证不使发送端的发送速率超过接收端的接收能力。而拥塞控制则主要考虑了发送端和接 收端之间的网络环境,它的目的是保证网络中的数据不超过网络的传送能力,从而避免 出现图10.1中网络性能严重下降的情况。 在拥塞控制算法中,包含拥塞避免( Congestion Avoidance)和拥塞控制( Congestion Control)这两种不同的机制。拥塞控制是“恢复”机制,它用于把网络从拥塞状态中 恢复出来,即发生在图101中的崖点左侧;拥塞避免是“预防”机制,它的目标是避 免网络进入拥塞状态,使网络运行在高吞吐量、低时延的状态下,即发生在图10.1中 的膝点。可以看出,拥塞避免应该是我们更希望实现的目标
352 彻底解决，拥塞控制理论和算法目前还是网络研究中的一个热点问题。 10.1.2 拥塞和拥塞控制的基本概念 当在网络中存在过多的分组时，网络的性能会下降，这种现象称为拥塞。Jain 等使 用图 10.1 来描述拥塞的发生，其中有两个关键的点，分别是膝（Knee）点和崖（Cliff） 点。当网络负载较轻时，吞吐量的增长和网络负载相比基本呈线性关系，网络时延增长 缓慢；在网络负载超过膝点之后，网络的吞吐量增长缓慢，而网络时延增长较快；当网 络负载超过崖点之后，网络吞吐量急剧下降，而网络时延急剧上升。 网络负载 网 络 时 延 膝点 崖点 图 10.1 拥塞发生点示意图 从图 10.1 可以看出，网络负载在膝点附近时，网络的使用效率最高。拥塞控制就是 网络节点采取措施来避免拥塞的发生或者对拥塞的发生做出反应。使用图 10.1 来说明， 拥塞控制的目标就是使网络在膝点附近工作。 流量控制是一个和拥塞控制有关的概念，它们都对数据传送的速率进行控制，但是 它们的出发点不同。流量控制主要考虑了发送过程中的发送端和接收端，它的目的是保 证不使发送端的发送速率超过接收端的接收能力。而拥塞控制则主要考虑了发送端和接 收端之间的网络环境，它的目的是保证网络中的数据不超过网络的传送能力，从而避免 出现图 10.1 中网络性能严重下降的情况。 在拥塞控制算法中，包含拥塞避免（Congestion Avoidance）和拥塞控制（Congestion Control）这两种不同的机制。拥塞控制是“恢复”机制，它用于把网络从拥塞状态中 恢复出来，即发生在图 10.1 中的崖点左侧；拥塞避免是“预防”机制，它的目标是避 免网络进入拥塞状态，使网络运行在高吞吐量、低时延的状态下，即发生在图 10.1 中 的膝点。可以看出，拥塞避免应该是我们更希望实现的目标
10.1.3互联网中拥塞发生的原因 网络中拥塞现象发生的根本原因是“需求”大于“供给”。网络中的资源(交换节 点中的缓存、链路带宽和网关处理能力等)是有限的,有限的资源要在网络用户之间共 享使用,因而用户之间对网络资源的使用存在竞争关系。由于互联网是开放的,没有使 用“准λ控制”( Admission control)算法,互联网无法根据网络资源的使用情况限制 使用网络用户的数量。由于互联网没有集中控制,所以无法控制每个用户使用网络资源 的数量。而随着互联网的发展,使用互联网用户的数量和基于互联网应用的数量都在迅 速增长。如果不使用某种机制在多个用户之间协调资源的使用,必然会岀现网络拥塞。 由于互联网流量具有强烈的突发性,流量经常向某些热点汇集,导致热点所在的区域发 生网络拥塞。 随着网络资源价格的降低,可以通过增加网络资源的手段缓解网络拥塞,比如增加 路由器的内存容量,提高路由器和交换机的处理器性能,提髙网络链路带宽等。遗憾的 是,虽然拥塞本质上是由于资源短缺引起的,但是单纯地增加网络资源并不能避免拥塞 的发生。 Raj Jain指出,即使在网络中增加资源也不能解决拥塞,甚至会加重拥塞的程 度。例如,如果路由器的缓存太大,分组通过的时延就会增大,当时延超过端系统中重 传时钟的值时,就会导致报文的重传,而这种重传反而加重了拥塞的程度。 值得指出的是,拥塞总是发生在网络中那些资源“相对”短缺的位置。互联网中的 不均衡性首先体现在资源分布的不均衡。在图102(a)中,路由器分别与Mb/s和100Kb/s 的链路相连。当分组以IMbs的速率从S发送D时,在R处会发生拥塞。互联网的不 均衡性还体现在流量分布的不均衡。在图10.2(b)中,A、B、C、D这4个节点通过 R相连,4条链路的带宽都是IMb/s,也就是说系统中资源的分布是均衡的。当A和B 都以1Mb/s的速率向C发送数据时,在R处同样会发生拥塞。在互联网中,资源分布 的不均街、流量分布的不均衡以及流量的突发性都是广泛存在的,由这些原因所导致的 拥塞不能单纯依靠增加资源的方法来解决。 IMb/s I 00K b/s (a)资源分布不均衡举例 (b)流量分布不均衡举例 图102互联网的不均衡性
353 10.1.3 互联网中拥塞发生的原因 网络中拥塞现象发生的根本原因是“需求”大于“供给”。网络中的资源（交换节 点中的缓存、链路带宽和网关处理能力等）是有限的，有限的资源要在网络用户之间共 享使用，因而用户之间对网络资源的使用存在竞争关系。由于互联网是开放的，没有使 用“准入控制”（Admission Control）算法，互联网无法根据网络资源的使用情况限制 使用网络用户的数量。由于互联网没有集中控制，所以无法控制每个用户使用网络资源 的数量。而随着互联网的发展，使用互联网用户的数量和基于互联网应用的数量都在迅 速增长。如果不使用某种机制在多个用户之间协调资源的使用，必然会出现网络拥塞。 由于互联网流量具有强烈的突发性，流量经常向某些热点汇集，导致热点所在的区域发 生网络拥塞。 随着网络资源价格的降低，可以通过增加网络资源的手段缓解网络拥塞，比如增加 路由器的内存容量，提高路由器和交换机的处理器性能，提高网络链路带宽等。遗憾的 是，虽然拥塞本质上是由于资源短缺引起的，但是单纯地增加网络资源并不能避免拥塞 的发生。Raj Jain 指出，即使在网络中增加资源也不能解决拥塞，甚至会加重拥塞的程 度。例如，如果路由器的缓存太大，分组通过的时延就会增大，当时延超过端系统中重 传时钟的值时，就会导致报文的重传，而这种重传反而加重了拥塞的程度。 值得指出的是，拥塞总是发生在网络中那些资源“相对”短缺的位置。互联网中的 不均衡性首先体现在资源分布的不均衡。在图10.2（a）中，路由器分别与1Mb/s和100Kb/s 的链路相连。当分组以 1Mb/s 的速率从 S 发送 D 时，在 R 处会发生拥塞。互联网的不 均衡性还体现在流量分布的不均衡。在图 10.2（b）中，A、B、C、D 这 4 个节点通过 R 相连，4 条链路的带宽都是 1Mb/s，也就是说系统中资源的分布是均衡的。当 A 和 B 都以 1Mb/s 的速率向 C 发送数据时，在 R 处同样会发生拥塞。在互联网中，资源分布 的不均衡、流量分布的不均衡以及流量的突发性都是广泛存在的，由这些原因所导致的 拥塞不能单纯依靠增加资源的方法来解决。 （a）资源分布不均衡举例 （b）流量分布不均衡举例 图 10.2 互联网的不均衡性
10.14拥塞控制的目标 在设计和比较拥塞控制算法时,需要一定的评价方法。从单个用户的角度出发,可 以比较端系统的吞吐速率、丢失率和时延等指标,这些是用户所关心的。由于拥塞控制 算法对整个网络系统都有影响,在评价拥塞控制算法时,更应该从整个系统的角度出发 进行考虑,既要保证网络的稳定性,又要兼顾资源分配的效率与公平性。因此,评价拥 塞控制算法的指标主要包括三项:网络的稳定性、资源分配的效率和资源分配的公平性。 1、网络的稳定性 从网络全局的角度考虑,拥塞控制不能影响网络的稳定性,这就要求拥塞控制算法 必须是收敛的。一般来说,收敛性通过网络由起始状态到达目标稳定状态的速度来衡量 然而,由于控制具有二元性,因此网络系统通常不会收敛到单一的稳定状态,而是会围 绕着最优状态抖动,称为“均衡状态”。 如图103所示,网络由起始状态到达均衡状态的时间长短以及在均衡状态下抖动的 剧烈程度决定了拥塞控制算法的收敛性,其中状态变迁的时间长短表示拥塞控制的响应 速度,抖动的剧烈程度表示拥塞控制的平滑度。因此,状态变迁时间越短,抖动程度越 轻,对应的拥塞控制响应速度越快、越平滑 平滑 标 网络总负载 图10.3响应速度与平滑性 2、资源分配的效率 资源分配的效率可以使用 Power函数来评价。 Power函数的定义为 Power=Throughput/Response Time 在上式中,一般取α=1。如果在评价时更偏重于吞吐量,则取a>1;如果在评价时 更偏重于响应时间,则取a<1。从图104可以看出,在网络负载位于膝点时, Power
354 10.1.4 拥塞控制的目标 在设计和比较拥塞控制算法时，需要一定的评价方法。从单个用户的角度出发，可 以比较端系统的吞吐速率、丢失率和时延等指标，这些是用户所关心的。由于拥塞控制 算法对整个网络系统都有影响，在评价拥塞控制算法时，更应该从整个系统的角度出发 进行考虑，既要保证网络的稳定性，又要兼顾资源分配的效率与公平性。因此，评价拥 塞控制算法的指标主要包括三项：网络的稳定性、资源分配的效率和资源分配的公平性。 1、网络的稳定性 从网络全局的角度考虑，拥塞控制不能影响网络的稳定性，这就要求拥塞控制算法 必须是收敛的。一般来说，收敛性通过网络由起始状态到达目标稳定状态的速度来衡量。 然而，由于控制具有二元性，因此网络系统通常不会收敛到单一的稳定状态，而是会围 绕着最优状态抖动，称为“均衡状态”。 如图 10.3 所示，网络由起始状态到达均衡状态的时间长短以及在均衡状态下抖动的 剧烈程度决定了拥塞控制算法的收敛性，其中状态变迁的时间长短表示拥塞控制的响应 速度，抖动的剧烈程度表示拥塞控制的平滑度。因此，状态变迁时间越短，抖动程度越 轻，对应的拥塞控制响应速度越快、越平滑。 图 10.3 响应速度与平滑性 2、资源分配的效率 资源分配的效率可以使用 Power 函数来评价。Power 函数的定义为： Power＝Throughputα／Response Time 在上式中，一般取 1。如果在评价时更偏重于吞吐量，则取 1；如果在评价时 更偏重于响应时间，则取 1。从图 10.4 可以看出，在网络负载位于膝点时，Power