第六章-流量和拥塞控制课件.ppt

《第六章-流量和拥塞控制课件.ppt》由会员分享，可在线阅读，更多相关《第六章-流量和拥塞控制课件.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 流量和拥塞控制流量和拥塞控制6.1 流量与拥塞控制概论流量与拥塞控制概论n问题问题当负载超过了节点的处理能力当负载超过了节点的处理能力n队列长度增加，丢弃分组队列长度增加，丢弃分组n分组时延增加，可能超时分组时延增加，可能超时超时重发超时重发网络负荷增加，网络负荷增加，分组通过量较小分组通过量较小拥塞拥塞网络负荷增加，网络负荷增加，吞吐率骤降达吞吐率骤降达0，进入死锁状态进入死锁状态6.1.1网络数据流的控制技术分类网络数据流的控制技术分类n流量控制流量控制调整网络中两个节点之间的流量，适应接收端调整网络中两个节点之间的流量，适应接收端的处理能力、通信链路的传输能力。的处理能力、

2、通信链路的传输能力。子网内的两个节点之间；用户端与网络接入点子网内的两个节点之间；用户端与网络接入点之间；网关之间等。之间；网关之间等。n拥塞控制拥塞控制限制网络内部（或网内部分区域）分组的流量，限制网络内部（或网内部分区域）分组的流量，限制节点队列的长度，避免拥塞的发生。限制节点队列的长度，避免拥塞的发生。6.1.1网络数据流的控制技术分类网络数据流的控制技术分类n死锁防止死锁防止死锁发生条件死锁发生条件:一个封闭环路上的所有节点的一个封闭环路上的所有节点的相关链路缓冲器都被积压的分组所占满，失去相关链路缓冲器都被积压的分组所占满，失去了节点所担负的存储转发能力。了节点所担负的存储转发能力。

3、网络轻负荷条件下，也可能发生网络轻负荷条件下，也可能发生合理设计网络拓扑、路由来避免合理设计网络拓扑、路由来避免n流量控制与拥塞控制之间的区别流量控制与拥塞控制之间的区别流量控制：点到点之间、流量控制：点到点之间、拥塞控制：全局性或局部网络拥塞控制：全局性或局部网络都是限制进入网络的分组的流量都是限制进入网络的分组的流量6.1.1网络数据流的控制技术分类网络数据流的控制技术分类n例：例：6.1n例：例：6.2禁止使用禁止使用n条链路的用户；全网总吞吐量为条链路的用户；全网总吞吐量为n个单位个单位公平：每个用户使用公平：每个用户使用 单位，全网总吞吐量为单位，全网总吞吐量为公平性以吞吐量为代价公

4、平性以吞吐量为代价6.1.2 拥塞控制的基本原理拥塞控制的基本原理n流量控制和拥塞控制的目标流量控制和拥塞控制的目标网络吞吐量最大化网络吞吐量最大化降低时延降低时延避免死锁避免死锁兼顾公平，在用户之间合理分配资源兼顾公平，在用户之间合理分配资源网络及其用户之间的速率匹配网络及其用户之间的速率匹配6.1.2 拥塞控制的基本原理拥塞控制的基本原理n控制方案控制方案开环控制开环控制n拥塞控制仅与预先规定的策略有关，与网络的状态拥塞控制仅与预先规定的策略有关，与网络的状态无关无关闭环控制闭环控制n从网络中的节点或目的节点获取网络状态信息，实从网络中的节点或目的节点获取网络状态信息，实时监测网络，检测拥

5、塞在何时何地发生；时监测网络，检测拥塞在何时何地发生；因缺少缓冲区而丢失分组的比例因缺少缓冲区而丢失分组的比例平均队列长度平均队列长度超时和重发的分组数超时和重发的分组数平均分组时延平均分组时延n将拥塞信息传送到可采取行动的地方（如控制中心、将拥塞信息传送到可采取行动的地方（如控制中心、源节点）源节点）n执行控制算法，纠正拥塞执行控制算法，纠正拥塞6.1.3 流控和拥塞控制所经历的层次流控和拥塞控制所经历的层次6.2.1 窗口式流量和拥塞控制窗口式流量和拥塞控制n类似于返回类似于返回n-ARQ端到端发送设定一个窗口端到端发送设定一个窗口W收端应答发端发来的每个分组收端应答发端发来的每个分组发端

6、在未收到应答之前最多可发发端在未收到应答之前最多可发W个分组个分组窗口的大小规定了网络最多可容纳的分组数窗口的大小规定了网络最多可容纳的分组数与网络的传输能力相适应与网络的传输能力相适应6.2.1 窗口式流量和拥塞控制窗口式流量和拥塞控制n窗口式流量和拥塞控制应注意的问题窗口式流量和拥塞控制应注意的问题窗口的建立窗口的建立n随着每一源随着每一源/目的节点对的建立而建立目的节点对的建立而建立窗口宽度的确定窗口宽度的确定n根据分组传输的来回时延根据分组传输的来回时延d来选择来选择n没有拥塞时，尽可能地充分利用网络的传输能力，没有拥塞时，尽可能地充分利用网络的传输能力，减少时延减少时延n拥塞时，纠正

7、拥塞拥塞时，纠正拥塞6.2.1 窗口式流量和拥塞控制窗口式流量和拥塞控制n窗口式流量和拥塞控制应注意的问题窗口式流量和拥塞控制应注意的问题报文重装报文重装n目的节点及时报告缺失分组，避免大量分组目的节点及时报告缺失分组，避免大量分组的重传。的重传。6.2.1 窗口式流量和拥塞控制窗口式流量和拥塞控制n窗口式流控技术窗口式流控技术W 窗口大小；窗口大小；d 分组传输的来回时延；分组传输的来回时延；X 单个分组的单个分组的传输时延。传输时延。dWx 发端的端的发送数率送数率为1/x，流控未激活；，流控未激活；d Wx 发端的端的发送数率送数率为W/d，流控激活，流控激活最大分最大分组传输速率速率为

8、 6.2.1 窗口式流量和拥塞控制窗口式流量和拥塞控制nd增加，拥塞增加，增加，拥塞增加，发端分组的传输速率下降，发端分组的传输速率下降，以缓解拥塞以缓解拥塞6.2.1 窗口式流量和拥塞控制窗口式流量和拥塞控制n端到端窗口流控技术的主要问题端到端窗口流控技术的主要问题需给定和调整窗口的大小。需给定和调整窗口的大小。n窗口小，网络中的数据分组少，分组时延小；窗口小，网络中的数据分组少，分组时延小；n窗口大，发送数据率高，时延大窗口大，发送数据率高，时延大n窗口的确定需综合考虑通过率、时延、信道传输能窗口的确定需综合考虑通过率、时延、信道传输能力、网络的拥塞，做到这一点，较困难。力、网络的拥塞，做

9、到这一点，较困难。公平性较差公平性较差n路径长的分组，端到端传输时延大，窗口设置较大，路径长的分组，端到端传输时延大，窗口设置较大，经过重负荷链路时，进入队列等待的分组较多；经过重负荷链路时，进入队列等待的分组较多；n路径短的分组，进入队列等待的分组较少；路径短的分组，进入队列等待的分组较少；n长路径会话中的分组获得传输（服务）的机会大，长路径会话中的分组获得传输（服务）的机会大，导致不公平导致不公平6.2.1 窗口式流量和拥塞控制窗口式流量和拥塞控制n流控窗口的动态调整流控窗口的动态调整依据获取的信息，动态调整窗口大小，避免或纠正拥依据获取的信息，动态调整窗口大小，避免或纠正拥塞塞获取信息的

10、方式获取信息的方式n感知到拥塞的节点，向源节点发一个特殊分组，源感知到拥塞的节点，向源节点发一个特殊分组，源节点减小窗口，延迟一段时间后，恢复窗口大小节点减小窗口，延迟一段时间后，恢复窗口大小n根据应答包的时延、一段时间内数据包重发的次数，根据应答包的时延、一段时间内数据包重发的次数，源节点调整窗口的大小；源节点调整窗口的大小；n目的节点根据到达的分组所收集的信息，控制应答目的节点根据到达的分组所收集的信息，控制应答分组回传的时延，迫使源节点调整窗口的大小。分组回传的时延，迫使源节点调整窗口的大小。6.2.2 漏斗式速率控制算法漏斗式速率控制算法n漏斗算法漏斗算法水流不规则的流入水桶；水流不规

11、则的流入水桶；只要水桶里有水；水以恒定的速率从孔中流出；只要水桶里有水；水以恒定的速率从孔中流出；注水流量大，漏斗满。水则溢出。注水流量大，漏斗满。水则溢出。6.2.2 漏斗式速率控制算法漏斗式速率控制算法n漏斗算法漏斗算法主机可以通过类似于漏斗的接口与网络相连；主机可以通过类似于漏斗的接口与网络相连；漏斗为容量有限的队列；漏斗为容量有限的队列；队列不空，分组以恒定速率进入网络；队列不空，分组以恒定速率进入网络；队列满，丢弃主机发来的分组，队列长度限定队列满，丢弃主机发来的分组，队列长度限定了突发性业务最大的到达量。了突发性业务最大的到达量。6.2.2 漏斗式速率控制算法漏斗式速率控制算法n令

12、牌漏斗算法令牌漏斗算法漏斗中存放的是令牌，而非数据分组；漏斗中存放的是令牌，而非数据分组；系统每隔系统每隔 时间单位，产生一个令牌；时间单位，产生一个令牌；漏斗满，新令牌将被丢弃；漏斗满，新令牌将被丢弃；分组到达时有令牌则可以发送；分组到达时有令牌则可以发送；例例6.5 P2056.2.2 漏斗式速率控制算法漏斗式速率控制算法n令牌漏斗算法令牌漏斗算法分组长度固定：每获得一个令牌，分组长度固定：每获得一个令牌，可发送一个分组；可发送一个分组；分组长度可变：一个令牌，可发分组长度可变：一个令牌，可发送送k个字节；多个令牌发送字节个字节；多个令牌发送字节数大于数大于k个字节的分组；个字节的分组；令

13、牌产生速率令牌产生速率 字节字节/秒秒令牌漏斗容量为令牌漏斗容量为C字节字节突发业务允许持续时间为突发业务允许持续时间为S秒秒漏斗的最大输出速率为漏斗的最大输出速率为M字节字节/秒秒(a)Input to a leaky bucket.(b)Output from a leaky bucket.(c)Output from a token bucket with capacities of(c)250 KB,(d)500 KB,(e)750 KB,(f)Output from a 500KB token bucket feeding a 10-MB/sec leaky bucket.令牌漏斗算

14、法的时延分析令牌漏斗算法的时延分析n该系统为时隙系统，状态在时隙结束的时刻发生该系统为时隙系统，状态在时隙结束的时刻发生变化，且在令牌到达之后发生；变化，且在令牌到达之后发生；n每个时隙每个时隙 内，内，k个分组到达的概率为个分组到达的概率为n状态转移概率状态转移概率令牌漏斗算法的时延分析令牌漏斗算法的时延分析n状态转移概率状态转移概率n全局平衡方程全局平衡方程n求出稳态概率求出稳态概率令牌漏斗算法的时延分析令牌漏斗算法的时延分析n稳态时稳态时分组到达率分组到达率令牌产生平均速率令牌产生平均速率稳态时，二者相等稳态时，二者相等分组获得令牌的平均时延分组获得令牌的平均时延令牌漏斗算法的时延分析令牌漏斗算法的时延分析