目录 第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
取最大值。使用 Power函数有一定的局限性。它主要基于M/M/1队列的网络,并假设 队列的长度为无穷;另外, Power的计算一般在单资源、单用户的情况下使用。 膝 崖点 负载 图104网络负载的 Power函数值 3、资源分配的公平性 在多用户存在的情况下,需要考虑资源分配的公平性。公平性的主要评价方法包括 Max-Min公平性(Max- Min fairness)、公平性指数( Fairness Index)和比例公平性 ( Proportional Fairness)等。 Max-Min公平性被非正式地定义为:每个用户的吞吐量至少和共享相同瓶颈的其它 用户的吞吐量相同。该公平性是一种理想的状况,它是一个广泛使用的评价标准,但是 不能给出具体的公平程度。 公平性指数提供了一个计算公式,可以计算公平的程度,定义为 F(x)=22 用公平性指数计算得到的结果在0和1之间,并且结果不受衡量单位的影响。它的 个性质是:如果在n个用户中只有k个用户平均共享资源,而另外n-k个用户没有任 何资源,函数的结果为 些研究者认为,如果考虑用户的“效用函数”( Utility Function),在一些情况下 使用Max-Min公平性来评价公平程度并不是最理想的。通过使用对数效用函数,Kel!y 引入了比例公平性的概念,其定义为:向量X满足比例公平性,如果对于其它任何向量 Y都满足 ∑ Vi-x
355 取最大值。使用 Power 函数有一定的局限性。它主要基于 M / M /1队列的网络，并假设 队列的长度为无穷；另外，Power 的计算一般在单资源、单用户的情况下使用。 图 10.4 网络负载的 Power 函数值 3、资源分配的公平性 在多用户存在的情况下，需要考虑资源分配的公平性。公平性的主要评价方法包括 Max-Min 公平性（Max-Min Fairness）、公平性指数（Fairness Index）和比例公平性 （Proportional Fairness）等。 Max-Min 公平性被非正式地定义为：每个用户的吞吐量至少和共享相同瓶颈的其它 用户的吞吐量相同。该公平性是一种理想的状况，它是一个广泛使用的评价标准，但是 不能给出具体的公平程度。 公平性指数提供了一个计算公式，可以计算公平的程度，定义为： 2 2 i i n x x F x 用公平性指数计算得到的结果在 0 和 1 之间，并且结果不受衡量单位的影响。它的 一个性质是：如果在n个用户中只有k 个用户平均共享资源，而另外n k 个用户没有任 何资源，函数的结果为 n k 。 一些研究者认为，如果考虑用户的“效用函数”（Utility Function），在一些情况下 使用 Max-Min 公平性来评价公平程度并不是最理想的。通过使用对数效用函数，Kelly 引入了比例公平性的概念，其定义为：向量 X 满足比例公平性，如果对于其它任何向量 Y 都满足： i I i i i x y x 0
由于“公平性”是针对资源分配而言,所以在评价前首先要确定“资源”的含义。 目前大多数研究在评价公平性时都使用吞吐量来衡量用户得到的资源,这是从用户角度 进行考虑的,并不完全适合网络中资源的状况。网络中的资源主要包括链路带宽、网关 的缓冲和网关的处理能力,在考察公平性时应当将这些资源的分配情况综合起来考虑。 102TCP拥塞控制机制研究 10.21互联网的网络模型 拥塞现象的发生和互联网的设计机制有着密切的联系。在互联网中使用的网络模型 可以用以下几点来抽象。 ①分组交换网络 和电路交换( Circuit-Switched)相比,分组交换( Packet-Switched)的本质是网络 资源共享。共享方式提高了网络资源的利用效率,但是也带来了一些问题。在共享方式 下,如何保证用户的服务质量成为一个很棘手的问题;在分组交换的网络中有可能出现 分组的“乱序”现象,对“乱序”分组的处理增加了端系统的复杂性 在分组交换网络中,理论上可以通过路由的调整来“绕过”某个拥塞的网络节点, 负载均衡”就属于这类解决方案。但是在网络中大量的节点周围不存在多条路由,从 而不能完全使用这种方法来解决拥塞问题。另外,如果通过调整路由来解决拥塞问题, 可能会导致路由的不稳定或者振荡,对网络全局的稳定性造成巨大挑战。 ②无连接网络 互联网使用无连接( Connectionless)的模型,两个节点之间在发送数据之前不需要 建立连接。无连接简化了网络的设计,在网络的中间节点不需要保存和连接有关的状态 信息。但是无连接模型也有一定的问题。首先,在无连接模型中难以引入“准入控制” ( Admission control)算法,这样在用户需求大于网络资源的情况下难以保证服务的质 量;其次,在无连接模型中对数据发送源的追踪能力很差,这给网络的安全性带来了很 大的隐患;另外,无连接也是网络中“乱序”分组出现的一个主要原因。 ③尽力而为的服务模型 在互联网中使用的模型为尽力而为(Best- Effort),即互联网不对数据传输的服务质 量提供保证。这个选择和早期网络中的应用有关。网络上传统的主要应用包括FTP、 Telnet和SMTP等,这些应用对网络性能(如时延、分组丢失等)的变化不敏感,Best- Effort 的服务模型可以满足这些应用的需要。而且由于它们在底层都基于包含拥塞控制算法的
356 由于“公平性”是针对资源分配而言，所以在评价前首先要确定“资源”的含义。 目前大多数研究在评价公平性时都使用吞吐量来衡量用户得到的资源，这是从用户角度 进行考虑的，并不完全适合网络中资源的状况。网络中的资源主要包括链路带宽、网关 的缓冲和网关的处理能力，在考察公平性时应当将这些资源的分配情况综合起来考虑。 10.2 TCP 拥塞控制机制研究 10.2.1 互联网的网络模型 拥塞现象的发生和互联网的设计机制有着密切的联系。在互联网中使用的网络模型 可以用以下几点来抽象。 ① 分组交换网络 和电路交换（Circuit-Switched）相比，分组交换（Packet-Switched）的本质是网络 资源共享。共享方式提高了网络资源的利用效率，但是也带来了一些问题。在共享方式 下，如何保证用户的服务质量成为一个很棘手的问题；在分组交换的网络中有可能出现 分组的“乱序”现象，对“乱序”分组的处理增加了端系统的复杂性。 在分组交换网络中，理论上可以通过路由的调整来“绕过”某个拥塞的网络节点， “负载均衡”就属于这类解决方案。但是在网络中大量的节点周围不存在多条路由，从 而不能完全使用这种方法来解决拥塞问题。另外，如果通过调整路由来解决拥塞问题， 可能会导致路由的不稳定或者振荡，对网络全局的稳定性造成巨大挑战。 ② 无连接网络 互联网使用无连接（Connectionless）的模型，两个节点之间在发送数据之前不需要 建立连接。无连接简化了网络的设计，在网络的中间节点不需要保存和连接有关的状态 信息。但是无连接模型也有一定的问题。首先，在无连接模型中难以引入“准入控制” （Admission Control）算法，这样在用户需求大于网络资源的情况下难以保证服务的质 量；其次，在无连接模型中对数据发送源的追踪能力很差，这给网络的安全性带来了很 大的隐患；另外，无连接也是网络中“乱序”分组出现的一个主要原因。 ③ 尽力而为的服务模型 在互联网中使用的模型为尽力而为（Best-Effort），即互联网不对数据传输的服务质 量提供保证。这个选择和早期网络中的应用有关。网络上传统的主要应用包括 FTP、 Telnet 和 SMTP 等，这些应用对网络性能（如时延、分组丢失等）的变化不敏感，Best-Effort 的服务模型可以满足这些应用的需要。而且由于它们在底层都基于包含拥塞控制算法的
TCP协议,因此可以在一定程度上适应网络环境的变化。但是随着多媒体等应用在网络 中的引入, Best-Effort模型已经不能满足许多新的网络应用的要求。例如,很多应用的 性能对于时延的变化比较敏感,而且它们在网络发生拥塞时不能降低发送速率。 10.22线性拥塞控制机制 假设网络中有n个用户共享有限的资源,如图10.5所示。网络系统的拥塞状态由系 统中数据包的数量决定。假设时间可以分割成长度相同的时间片( Time Slot),用户在 每个时间片开始时根据前一个时间片收到的网络反馈来设定本时间片的负载水平。如果 在某个时间片t,第i个用户的负载为x(),那么瓶颈资源上的总负载则为∑x(),此 时的系统状态可以用n维向量x(t)={x1(,x2(),x2(t)}表示。 用户1 xE 用户2 用户n 图105网络资源控制机制示意图 由于网络处于或者接近膝点,所有用户的资源需求都是可以得到保证的(这一情况 在崖点并不成立)。因此,x,()表示第i个用户的资源需求,同时也是系统分配给它的 资源数。在每个时间片,网络系统根据负载情况向所有用户发送二进制反馈信号y(t)。 当y()为0时,用户会增加资源需求;反之,当yt)为1时,用户会降低资源需求。 所有用户与网络系统进行交互,改变(增加或者减少)各自的资源需求,假设改变 量为u1(t),则有下面的状态等式( State Equation) x(t+1)=xr、()+u1(t) 其中改变量u1()表示第i个用户的控制量,它是关于本用户历史需求和系统反馈的 函数,即 u1(t)=f(x,(,y;(t) 因此状态等式可以重新写为 x(t+1)=x,()+f(x、(),y,(t)
357 TCP 协议，因此可以在一定程度上适应网络环境的变化。但是随着多媒体等应用在网络 中的引入，Best-Effort 模型已经不能满足许多新的网络应用的要求。例如，很多应用的 性能对于时延的变化比较敏感，而且它们在网络发生拥塞时不能降低发送速率。 10.2.2 线性拥塞控制机制 假设网络中有n个用户共享有限的资源，如图 10.5 所示。网络系统的拥塞状态由系 统中数据包的数量决定。假设时间可以分割成长度相同的时间片（Time Slot），用户在 每个时间片开始时根据前一个时间片收到的网络反馈来设定本时间片的负载水平。如果 在某个时间片t ，第i 个用户的负载为 x t i ，那么瓶颈资源上的总负载则为 x t i ，此 时的系统状态可以用n维向量 x t x1 t, x2 t,.., x3 t表示。 1 x xi Xgoal? x2 xn 图 10.5 网络资源控制机制示意图 由于网络处于或者接近膝点，所有用户的资源需求都是可以得到保证的（这一情况 在崖点并不成立）。因此， x t i 表示第i 个用户的资源需求，同时也是系统分配给它的 资源数。在每个时间片，网络系统根据负载情况向所有用户发送二进制反馈信号 yt。 当 y t 为 0 时，用户会增加资源需求；反之，当 yt为 1 时，用户会降低资源需求。 所有用户与网络系统进行交互，改变（增加或者减少）各自的资源需求，假设改变 量为u t i ，则有下面的状态等式（State Equation）： x t x t u t i 1 i i 其中改变量u t i 表示第i 个用户的控制量，它是关于本用户历史需求和系统反馈的 函数，即 u t f x t , y t i i i 因此状态等式可以重新写为： x t x t f x t , y t i 1 i i i
需要注意的是,每个用户并不知道其它用户的资源需求,因此,当j≠时,1()不 是关于x()的函数。 通常情况下,控制函数∫可以是任意线性或者非线性函数,此处只关注线性控制函 数,则状态等式可以归约为 ;(t+) Ja,+b r, ()if y(0)=0=Increase ap+bpx, (t) if y(o)=1=Decrease 其中a1、aD、b、bb为常数 通过为上述4个参数设定不同的数值,将得到不同的拥塞控制机制 ①“乘性增加,加性减小”( Multiplicative Increase Additive Decrease,MIAD)控 制机制。当a1=0、b1>1、aD0、b1=1、aD1、aD=0、00、b=1、aD=0、0<b<1时,状态等式可表示为 (t+1) a,+x, if y(t)=0=Increase ()ify(t)=1→ Decrease 102.3线性拥塞控制机制评价 在1022节中通过设置不同参数值可以得到一组控制机制的集合,为了确定哪些控 制机制是可行的,需要观察系统状态在n维向量空间中的变迁轨迹。为了便于描述,考 虑系统中只有两个用户的情况,此时n维向量空间可以简化为二维空间 如图106所示,两个用户的资源分配{x1(t,x2(}可以用二维空间中的点(x,x2
358 需要注意的是，每个用户并不知道其它用户的资源需求，因此，当 j i 时，u t i 不 是关于 x t j 的函数。 通常情况下，控制函数 f 可以是任意线性或者非线性函数，此处只关注线性控制函 数，则状态等式可以归约为： if 1 Decrease if 0 Increase 1 D D I I a b x t y t a b x t y t x t i i i 其中 I a 、 D a 、 I b 、 D b 为常数。 通过为上述 4 个参数设定不同的数值，将得到不同的拥塞控制机制。 ① “乘性增加，加性减小”（Multiplicative lncrease Additive Decrease，MIAD）控 制机制。当 0 aI 、 1 bI 、 0 aD 、 1 bD 时，状态等式可表示为： if 1 Decrease if 0 Increase 1 D I a x t y t b x t y t x t i i i ② “加性增加，加性减小”（Additive Increase Additive Decrease，AIAD）控制机制。 当 0 aI 、 1 bI 、 0 aD 、 1 bD 时，状态等式可表示为： if 1 Decrease if 0 Increase 1 D I a x t y t a x t y t x t i i i ③ “乘性增加，乘性减小”（Multiplicative Increase Multiplieative Decrease，MIMD） 控制机制。当 0 aI 、 1 bI 、 0 aD 、0 1 bD 时，状态等式可表示为： if 1 Decrease if 0 Increase 1 D I b x t y t b x t y t x t i i i ④ “加性增加，乘性减小”（Additive Increase Multiplicative Decrease，AIMD）控 制机制。当 0 aI 、 1 bI 、 0 aD 、0 1 bD 时，状态等式可表示为： if 1 Decrease if 0 Increase 1 D I b x t y t a x t y t x t i i i 10.2.3 线性拥塞控制机制评价 在 10.2.2 节中通过设置不同参数值可以得到一组控制机制的集合，为了确定哪些控 制机制是可行的，需要观察系统状态在n维向量空间中的变迁轨迹。为了便于描述，考 虑系统中只有两个用户的情况，此时n维向量空间可以简化为二维空间。 如图 10.6 所示，两个用户的资源分配x1 t, x2 t可以用二维空间中的点（ 1 x ， 2 x ）
表示。在图106中,横坐标表示系统为用户1分配的资源数量,纵坐标表示系统为用户 2分配的资源数量。如果在某种资源分配方案下,系统分配给用户1和用户2的资源数 量之和等于目标值,即x,+x,=X,则称该分配方案是高效分配( Efficient allocation), 对应于图中的效率线。如果在某种分配方案下,系统分配给用户1和用户2的资源数量 相同,即x1=x2,则称该分配方案是公平的,对应于图中的公平线。效率线和公平线相 交于最优点( )。拥塞控制的目标是不论系统状态的起始点在哪里,都能 使系统状态逐渐变迁至最优点。 公平线 过载 最优点 数 x2 轻载 用户1分配的资源数量x1 图10.6双用户情况下的网络资源分配 所有位于效率线以下的点均表示系统“轻载”( Under load),系统可以要求用户增 加各自的需求。如图106所示,x点为起始点,加性增加策略使两个用户均将自身需 求扩大a1倍,对应于穿过x点的45°线;而乘性增加策略会使两个用户均将自身需求扩 大b1倍,对应于连接x0点与原点的直线。类似地,所有位于效率线以上的点都表示系统 过载( Overload),加性减小对应于穿过xo点的450线,而乘性减小对应于连接x0点与 原点的直线。 下面分别考虑两个用户的情况下四种拥塞控制机制的收敛情况。如图10.7、图10.8 图109和图10.10所示,在每种机制下的起始点均为(x1,x2b),即网络处于过载的 状态 (1)“乘性增加,加性减小”(MIAD)控制机制
359 表示。在图 10.6 中，横坐标表示系统为用户 1 分配的资源数量，纵坐标表示系统为用户 2 分配的资源数量。如果在某种资源分配方案下，系统分配给用户 1 和用户 2 的资源数 量之和等于目标值，即 x1 x2 Xgoal，则称该分配方案是高效分配（Efficient Allocation）， 对应于图中的效率线。如果在某种分配方案下，系统分配给用户 1 和用户 2 的资源数量 相同，即 1 2 x x ，则称该分配方案是公平的，对应于图中的公平线。效率线和公平线相 交于最优点（ 2 Xgoal ， 2 Xgoal ）。拥塞控制的目标是不论系统状态的起始点在哪里，都能 使系统状态逐渐变迁至最优点。 公平线 用户1分配的资源数量 用 户 2 分 配 的 资 源 数 量 效率线 1 x 2 x 过载 轻载 最优点 0 x 效率公平线 图 10.6 双用户情况下的网络资源分配 所有位于效率线以下的点均表示系统“轻载”（Under Load），系统可以要求用户增 加各自的需求。如图 10.6 所示， x0 点为起始点，加性增加策略使两个用户均将自身需 求扩大 I a 倍，对应于穿过 x0点的 450 线；而乘性增加策略会使两个用户均将自身需求扩 大 I b 倍，对应于连接 x0点与原点的直线。类似地，所有位于效率线以上的点都表示系统 过载（Overload），加性减小对应于穿过 x0点的 450 线，而乘性减小对应于连接 x0点与 原点的直线。 下面分别考虑两个用户的情况下四种拥塞控制机制的收敛情况。如图 10.7、图 10.8、 图 10.9 和图 10.10 所示，在每种机制下的起始点均为（ x1h， x2h ），即网络处于过载的 状态。 （1）“乘性增加，加性减小”（MIAD）控制机制
