文档介绍：拥塞控制算法
1
一、拥塞控制
拥塞现象
拥塞现象是指到达通信子网中某一部分的分组数量过多, 使得该部分网络来不及处理,以致引起这部分乃至整个网络性能下降的现象,严重时甚至会导致网络通信业务陷入停顿。
网络吞吐量
吞吐量是指在没有帧丢失的情况下，设备能够接受的最大速率。网络的吞吐量与通信子网负荷(即通信子网中正在传输的分组数)有着密切的关系。
2
拥塞现象的产生
当通信子网负荷比较小时,网络的吞吐量随网络负荷的增加而线性增加。当网络负荷增加到某一值后,若网络吞吐量反而下降,则表征网络中出现了拥塞现象。在一个出现拥塞现象的网络中,到达某个节点的分组将会遇到无缓冲区可用的情况,从而使这些分组不得不由前一节点重传,或者需要由源节点或源端系统重传。当拥塞比较严重时,通信子网中相当多的传输能力和节点缓冲器都用于这种无谓的重传,从而使通信子网的有效吞吐量下降。
3
拥塞与死锁
提供的负载
吞吐量
理想的拥塞控制
拥塞
死锁（吞吐量 = 0）
无拥塞控制
实际的拥塞控制
轻度
拥塞
0
(单位时间内输入给
网络的分组数目)
(单位时间内从网络
输出的分组数目)
4
区别
流量控制只在一对给定的发送方和接收方之间，控制发送方不以超过接收方处理能力的速率发送数据。
拥塞控制是一个全局性的过程，涉及到网络中所有的主机、所有的路由器，以及与降低网络传输性能有关的所有因素。
联系
流量控制限制了进入网络中的信息总量，可以在一定程度上减缓拥塞的作用。
拥塞控制与流量控制区别联系
5
拥塞控制策略
策略一：开环控制方法。
重在预防，希望通过完美的设计来避免拥塞的发生
需精心设计网络的各个环节，尽可能减少不必要的数据重传和避免数据过分集中在某个局部，同时还要严格控制进入子网的数据量以及数据流入的速度。
策略二：闭环控制方法。
重在解决，在拥塞发生后设法控制和缓解拥塞。
需监视拥塞的发生，网络中要定期收集一些性能参数，一旦参数值超过一定的门限，检测到拥塞的结点立即通知有关结点，以便采取措施。
6
通信量整形
目标：迫使分组按照预定的速率进入网中
漏桶算法
基本思想：
在主机和网络之间接入一个“漏桶”。
无论主机以多大的速率发送分组，“漏桶”中的分组总是以恒定的速率注入网中。
如果主机发送过快，当“漏桶”满了之后，多余的分组即被丢弃。
优点：无论数据量有多大，数据总是以平均速率发送。
缺点：漏桶满后数据会丢失。
7
漏桶模型
说明
绿色-未整形的流量
紫色-整形后的流量
红色-丢失的分组
8
漏桶的本质
就是一个固定长度的分组队列，主机发送的每一个分组都加入到队列中排队，如果队列满则分组被丢弃，同时队列按照约定的速率向网络发送分组。
两种情况：
分组长度固定
让队列每隔一个固定的时间发送一个分组。
分组长度可变
规定队列每次可以发送的最大字节数。
9
令牌桶算法
漏桶算法的缺点：数据总以平均速率发送，突发数据到来时不能较快给予响应，有时还会丢失数据。希望能改进
于是有令牌桶算法，特点：
令牌桶中装的不是分组而是令牌。
桶中每隔Δt时间产生出一个令牌，当桶装满后，随后产生的令牌就被丢弃。
分组在桶外的缓冲区中等待发送，桶中有多少个令牌就允许发送多少个分组。(也可以规定：一个令牌表示允许发送 k 个字节)
每个令牌用后即销毁，当桶中没有令牌时必须停止发送。
10