拥塞控制

一、 拥塞产生的原因
出现资源拥塞的条件：
∑对资源的需求＞可用资源
解决网络拥塞的办法是采用流量控制。
拥塞控制的主要功能：
(1)防止网络因过载而引起吞吐量下降和时延增加；
(2)避免死锁；
(3)在互相竞争的各用户之间公平地分配资源。

二、 拥塞控制方法

1．缓冲区预分配法——适用于虚电路通信子网
建立虚电路时

传送分组时

2．抑制分组法——可用虚电路或数据报通信子网
策略：在出现拥塞前兆时，对分组进行截流。
算法实现：
每个节点(路由器)都监视其输出线路利用率
μ可用下列公式更新：
f反映线路瞬时利用率，取值为0-1之间的常数；α反映了更新速度。
各节点为每一条线路定义阀值，当μ大于此值时，则该线路进入“告警”状态。
每新收到分组时路由器要查看其输出线是否处于“告警”状态，若是则发送一个抑制分组到源主机，并在抑制分组中指明分组的目的地，并在原分组上加一个标志，表示以后不用再产生抑制分组；发送端主机收到该抑制分组后，将发送速率降低一档，若继续发送抑制分组，则发送端继续降低速率。
3．分组丢弃法
策略：当缓冲区满时，将到来的分组丢弃，丢弃分组后，发送端因得不到确认而超时重发。
缓冲器分配规则：
为每个输入线分配一个能容纳一个分组的缓冲器先把到达的分组接收下来，检查该分组内有无对前面发送的信息报的应答，如果应答表明前一次发送的信息包已经妥收，那么把此分组丢弃，准备接收下一个分组。
限制输出线队列长度N+1个节点缓冲区除了分给输入线(1个)以外，剩余的全分给输出线(N个)。
分配给输出缓冲区的方法有平分法 最大分配法最小分配法 最大最小分配法
4．许可证法
策略：限制通信子网内的分组数目，使之不超过某一个固定值从而避免拥塞。
实现方法：在通信子网中有固定数目的许可证在网中随机巡航流动，任何一个分组想进入网络必须先获得一个许可证；当分组到达终点时就释放许可证。
许可证的分布原则：尽量减少分组等待许可证的时间。
平均分布；——忙、闲不公平
所有许可证在网内四处流动； ——付出等待时延
每个节点上保存少量许可证，其它许可证在网内流动。
存在问题：
能防止全局性拥塞，但仍不能完全消除局部拥塞；
需要防止许可证丢失。
三、流量控制
流量控制和拥塞控制的区别拥塞控制:必须保证通信子网能正常传输数据，包括流量控制，使全局性问题。
流量控制:根据接收端能承受的数据速率来调节发送端传输数据的速率，防止到达接收端的数据速率超过接收端的处理速率，只与发送者与接收者之间的点到点通信量有关。
流量控制是按级进行的，大致可以划分为四种不同级别。

1.网段级流量控制——需要解决“存储——转发”问题
目的：在相邻两节点之间维持一个均匀的流量，以避免出现局部缓冲区拥塞和死锁。
根据是对两节点间的流量还是对其中每条虚电路的流量进行控制可再划分为：
数据链路网段级流量控制——适用于虚电路、数据报两种业务采用信道队列限制法(即分组丢弃法)进行控制：监视每一个队列的缓冲区的占用情况并对其定义一个极限(固定的或动态可调的)，当某一队列中待转发的分组数超过此极限时即丢弃该分组。
特点：能有效的避免吞吐量的降低，但无法解决间接死锁的问题。
虚电路网段级流量控制——适用于虚电路

信道队列限制法有以下四种变形：
平均分配设N为节点中输出队列的总数,N_i为第i个队列中的分组数,而B为缓冲区的大小(除分配给输入线的之外），则约束条件为： 0≤N_i≤B/N 这种固定分配方法，效率低，性能较差。 最长队列共享设bmax为所允许的最长队列(此处bmax＞B/N)，则约束条件为： 0≤N_i≤b_max 以及 ∑N_i≤B 最小分配共享设b_min为保证分配给每一队列的缓冲区大小(当然bin ≤B/N)，则约束条件为： ∑Max(0, N_i -b_min)≤B-Nb_min 最小分配最长队列共享合并了前两种方式，即每—队列保证有一个最小的缓冲区b_min供使用，同时其最大长度受b_max的限制。
死锁：两个节点之间互相僵持，整个网络不能传输分组，吞吐量为零的情况。
1.存储——转发死锁
直接存储——转发死锁：互相占用了对方需要的资源而造成的死锁。
间接存储——转发死锁：每个节点都试图向相临节点发送分组，但没有一个节点有空闲缓冲区来接收分组导致产生死锁。
2.重装死锁：发生在目的节点，因缓冲区不足无法排序组装造成。

信道队列限制法无法解决间接死锁的问题！
解决间接存储——转发死锁
采用结构化缓冲池策略或称为缓冲区的有向图分配法给每个节点开辟M十1个缓冲区(每个缓冲区存放一个分组)，并从0到M编上号码。仅当与主机相连的源节点的缓冲区0空闲时分组才能发往源节点的缓冲区0。
接着，仅当某个相邻节点中的缓冲区1空闲时分组才能发往缓冲区1，以后每转发一次，所到达的缓冲区的编号就增大一个号，0->1->2->……->M
最终，分组的最坏结局一定是以下两种情况之一：
· 传到所要到达的目的节点，然后交付给主机；
· 传到编号为M的缓冲区，然后被丢弃，因而不再消耗网络的资源。
2．源节点到目的节点级的流量控制——需要解决“重装死锁”问题目的：防止在输出节点出现由于目的节点到主机的连接线路过载或是由于主机接收数的速率太低而导致缓冲区拥塞。
当需要在目的节点把到达的分组重新装配成报文时有可能出现重装死锁！
在ARPANET中使用的源节点到目的节点级的流量控制的方法是：
①源节点发送报文时必须先发送一个“请求缓冲空间”的分组；
②目的节点收到该分组后，即为此报文保留8个缓冲区并回答一个“分配”分组。
③当整个报文的8个分组都收齐并送交主机后，目的节点就发回一个“准备下一报文”的确认分组。
④当源节点无报文要发送但仍收到“分配”分组时，须发回“归还”分组以释放目的节点缓冲空间。

3．进网级流量控制
目的：控制网络外部的通信量进入网络从而防止整个网内的缓冲区产生拥塞。
拥塞的测量：
①局部测量：测量入口节点缓冲区的情况；
②全局测量：测量全网所有缓冲区的占用程度；
③选择测量：测量某个目的节点的整条通路的拥塞情况。
将测量结果报告进网节点，以控制从外部进入网内的通信量。
最出名的进网级流量控制方案为许可证法。

4．传输级流量控制
目的：在两个远程进程之间的虚电路连接中提供分组的可靠传送，即在进程级防止用户缓冲区出现拥塞。
各层采取的流量控制：
数据链路层：进网级、网段级（数据链路网段级）
网络层：入口到出口级、网段级（虚电路网段级）
传输层：传输级