第8讲路由选择和拥塞控制2.pptVIP

第六章 路由选择和拥塞控制（2） 拥塞控制（congestion) 一、拥塞控制的意义 1.网络拥塞产生的原因： ① 当某个结点缓冲区的容量太小时，到达该结点的分组无空间暂存而不得不被丢弃； ② 处理机处理的速率太慢，可能引起网络的拥塞。 总之：若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏，这种情况称为（拥塞）即: ∑对资源的需求＞可用资源 资源包括网络中的链路容量，交换结点中的缓冲区和处理机 等。 二、拥塞控制的一般原理 开环控制:在设计网络中事先将有关发生拥塞的因素考虑周到，力求工作时不产生拥塞。 缺点:一旦整个系统运行起来，就不再中途进行改正。 闭环控制:基于反馈环路原理，有几种措施： ① 监测网络系统以便检测到拥塞在何时、何处发生； ② 将拥塞发生的信息传送到可采取行动的地方； ③ 调整网络系统的运行以解决出现的问题。 * * 拥塞分析： 问题1：某结点缓冲区小，到达该结点的分组因无空间而被丢弃 解决：将缓冲区扩大，使所有分组可以暂存 但：链路容量和CPU速度未变 分组在很长时间内排队未发 因超时分组重发 拥塞加剧 只是转移了瓶颈 问题2：发送端在未收到确认前，保留分组副本。接收端产生的拥塞导致发送端缓冲区的拥塞。 问题在于系统各部分之间的不平衡造成的 交换结点 A A’ B B’ C=1 C=1 C=1 C=10 λA λB 初始：链路容量：C 平均速率： λA＝ λB＝0.8 整个网络吞吐量：1.6 当主机A和B到交换结点的两条链路都饱和时（ λA＝1 λB＝10），结点缓冲区有限，导致主机A或B到交换结点的分组被丢弃。 主机B到交换结点的分组到达率是主机A到交换结点的分组到达率的10倍， 因此主机B和A，其占有输入缓冲区的机会为10:1。 最终从交换结点输出到主机B’的数据率不超过1，按上述10:1关系，最终从交换结点输出到主机A’的数据率不超过0.1。 整个网络吞吐量：1.1 拥塞控制和流量控制区别： 拥塞控制：全局性 流量控制：局部的，给定的发送端和接收端之间的点对点 通信量；使发送端发送的速度不要高于接收端 接收的速度 流量控制是防止网络拥塞的一种机制 轻度拥塞 拥塞 ① 理想的流量控制 ②实际流量控制 ③无流量控制 死锁 输入负载 0 2. 拥塞与流量控制的关系 吞吐量 拥塞控制的关键： 1）关键：合理、动态分配资源 2）应具备的功能： a) 防止网络因过载而导致吞吐率下降和时延增加； b) 防止死锁； 3.“死锁”的现象 死锁：当网络负载达到某一数值时，网络的吞吐量就下降到零，网络无法工作，这就是所谓死锁。 1）直接死锁：由互相占用对方需要的资源而造成的死锁 2）重装死锁：由于路由器的缓冲区的拥塞而引起的。 假设有三个报文A、B、C经过三个路由器P、Q、R送往主机H，每个报文由4个分组组成： A3 B4 C2 C3 B1 C1 B2 B3 A1 A2 A4 H 路由器P 路由器Q 路由器R ① 每个路由器的缓冲能容纳4个分组； ② 路由器R为报文A预留了4个分组的缓冲区； ③ 由于A3还暂留在路由P中，无法转发到Q，因为Q缓冲区已满 ④ 路由器Q也无法送往R，这样，从P→Q → R的链路的任何一个分组都不能转发，形成了由于缓冲区的拥塞而引起的重装死锁。 通信量控制策略： 问题： 拥塞发生的主要原因在于通信量常常是突发性的。如果主机能以一个恒定的速率发送分组，拥塞将会少得多。对于子网而言，子网强迫分组以某种预定的速率的传送。 1、漏桶算法（leaky bucket algorithm） 思路: 用户通过一个流规范（flow specification）说明自已的通信量模式，并经过协商过程来与通信子网和接收者达成一致。 通过调整分组传输的速率，从而减少可能发生的拥塞。 漏桶算法： 主机 漏桶接口 网络 说明： ①有一小孔的桶，不管水注入桶的速率如何，水从桶中往外漏的速率是恒定的?，一旦桶空，外漏的速率为0。 ②在桶满之后，再注入桶中的水都会从桶边溢出。 ③该漏桶空实际上是一个有限的内部队列。 当队列满之后，如果有新的分组要进入队列，该分组就被丢弃。 2、令牌桶算法（token bucket） 思路： ①每隔?T秒生成一个令牌，且漏桶可以保留这些令牌。 ②如果要发送分组，必须首先抓住一个令牌，在发送分组后令牌被销毁。 ③有三个令牌，发送