计算机网络 拥塞控制与避免 ppt

1、 o路由选择 固定路由选择 随机路由选择 基于流量的路由选择o拥塞控制与避免 在每个节点上保持一张路由表,表上标明对每一个目的地址应走哪条链路进行转发.路由表是在整个系统进行配置时生成的.配置时根据事先计算好的“网络中任意两个节点之间最短路径”,将这些最短通路制成路由表,存放在各个节点中.每一个分组都可在所到达的节点中查找下一步应转发到哪一个节点(下一站节点或后继节点). 经典的求最短路径算法是Dijkstra算法.它的条件是已知网络的拓扑和各链路长度, 主要是通过计算任意两节点间的最小链路长度,求得从源节点到目的节点间最短通路. oDijkstra算法 对于一个无向图G=(V，E),其中V表

2、示网络中所有节点的集合,E表示网络中所有链路的集合,D(v)为源节点到节点v的距离,l(i, j)为节点i至节点j之间的距离.(1)初始化 任选一个节点作为源节点,不妨不妨令 V=1,对所有不在V中的节点v,写出:1456232221113355不直接相连与节点若节点直接相连与节点若节点1 1 ), 1 ( )(vvvlvD图图 求最短路径算法的网络拓扑求最短路径算法的网络拓扑实际编程时一般取D(v)=1000代替.源节点源节点(2)寻找一个不在V中的节点w,其D(w)值为最小.把w加入到V中.然后对所有不在V中的节点,用D(v),D(w)+l(w, v)中较小的值去更新原有的D(v)值,即:

3、 D(v) MinD(v),D(w)+l(w, v)(3)重复步骤(2),直到所有的网络节点都在V中为止. 由Dijkstra算法可知,若将已知的各链路长度改为链路时延,跳数,带宽或费用,就相当于求任意两节点之间具有最小时延,最少跳数,最大带宽或最小费用的通路.所以, 求最短路径算法具有普遍的应用价值.基于左图的网络拓扑结构基于左图的网络拓扑结构,采采用用Dijkstra算法算法,计算以节点计算以节点1为源节点的最短通路的过程为源节点的最短通路的过程.表中带圆圈的数字表示表中带圆圈的数字表示的是的是: 在每一次执行步在每一次执行步骤骤(2)时时, 所寻找到的具所寻找到的具有最小值的有最小值的D

4、(w)值值.步骤步骤 V D(2) D(3) D(4) D(5) D(6)初始化初始化 1 2 5 1 1 1,4 2 4 2 2 1,4,5 2 3 1 4 3 1,2,4,5 3 1 2 4 4 1,2,3,4,5 2 1 2 4 5 1,2,3,4,5,6 2 3 1 2 1456232221113355o 上述路由表仅是以节点1为源节点,由Dijkstra算法计算得到节点1为根的通路树,然后生成节点1内存中的路由表这样的路由表每个节点都有一个,只需分别以这些节点为源点,重新执行算法即可0)(1)(2)(3)(4)(5)图图 基于基于Dijkstra算法生成的最

5、短通路树算法生成的最短通路树图图 依据最短通路树生成节点依据最短通路树生成节点1的路由表的路由表目的节点目的节点 下一站下一站123456-24444目的节点目的节点 下一站下一站12*-24 当分组到达某个节点时就随机地选择一条链路作为转发的路由.当网络中的节点或链路发生故障时,采用随机走动法是最有效的,它使得路由算法具有较好的稳健性.AKLPEMNDCB信源信源信宿信宿0.50.50.20.20.30.30.30.3图图 随机走动算法示意图随机走动算法示意图0.20.20.20.30.30.30.30.30.30.30.3o基本思想n既考虑拓扑结构，又兼顾网络负荷；n前提：每对结点间平均数

6、据流是相对稳定和可预测的；n根据网络带宽和平均流量，可得出平均包延迟，因此路由选择问题归结为找产生网络最小延迟的路由选择算法。n提前离线（off-line）计算o需要预知的信息n网络拓扑结构；n通信量矩阵Fij；n线路带宽矩阵Cij；n路由算法（可能是临时的）0网络拥塞的原因网络拥塞的原因:(1)网络中某个节点缓存的容量太小网络中某个节点缓存的容量太小,造成到达造成到达该节点的分组因无空间暂存而不得不丢弃该节点的分组因无空间暂存而不得不丢弃. 若将站点的容量扩展容量扩展到很大, 所有到达的分组均可在此节点缓存, 而由于链路的容量和处理机的速度并未提高,因此分组在队列中的排队时延将会很长排队时延

7、将会很长, 结果上层软件只好将它们进行重传(超时重发).所以简单地扩大缓存的存储空间同样会造成网络资源的严重浪费. 图图 当通信量太大时当通信量太大时,会发生拥塞会发生拥塞,性能显著降低性能显著降低.发送的分组发送的分组提交的分组提交的分组子网的最大子网的最大传输容量传输容量完美的完美的理想的理想的拥塞的拥塞的(2)处理机的处理速度太慢处理机的处理速度太慢 如果路由器的CPU处理速度太慢,以至于不能执行要求它们做的日常工作(缓冲区排队,更新路由表等),使得缓存中的队列变得很长,即使线路的容量还很富裕.(3)低带宽的链路低带宽的链路 由于带宽太低,造成链路上需要传输的分组太多,子网的性能降低.若

8、升级带宽而不提高处理机性能都不会有多大的作用.只升级系统的一部分,而不是整体,往往只会把瓶颈转移到系统其它地方. o拥塞控制的一般原理拥塞控制的一般原理 拥塞控制算法大致可分成开环控制和闭环控制两大类.(1)开环控制算法原理开环控制算法原理 通过良好的来避免拥塞问题的发生,在网络运行过程中,何时接受新分组,何时丢弃分组以及丢弃哪些分组都是事先规划好的,并不考虑当前的网络流量状况.(2)闭环控制算法原理闭环控制算法原理 通过,使网络流量与网络可用资源相协调,从而使网络拥塞问题得到解决.检索技术: 检索机制能够随时发现拥塞问题,判断的依据和参数主要有:因缺少缓冲区空间而等.如果基准参数超过临界值,

9、则意味着可能发生了网络拥塞.反馈技术:反馈机制将发生拥塞的信息从检查点传送到控制点.反馈方式主要有两种:.显式反馈采用由检查点向控制点反馈一个警告分组的方式来通告网络已发生了拥塞.隐式反馈采用由控制点(源端)通过观察应答分组返回所用时间进行推断的方式来判断网络是否发生了拥塞.调整技术:调整机制是通过检查点和控制点相互协作来共同努力解决拥塞问题.控制点通过降低载荷,即;检查点通过载荷脱落,即,或者通过(如增加附加链路或提高链路带宽),对于后者,要求系统能够提供后备的资源.o拥塞控制算法拥塞控制算法 根据数据交换方式(虚电路或数据报)的不同,拥塞控制算法采用不同的策略.1. 1. 面向虚电路的拥塞

10、控制算法面向虚电路的拥塞控制算法源主机源主机目的主机目的主机连接请求连接请求转发转发转发转发转发转发连接请求连接请求连接请求分组中包括连接请求分组中包括:(1)最大分组长度最大分组长度(2)最大传输速率最大传输速率(3)分组序号分组序号(4)传输模式等传输模式等应答分组应答分组转发转发转发转发转发转发应答分组应答分组应答分组对连接分组中应答分组对连接分组中的根据流量说明信息进的根据流量说明信息进行确定它能接受的流量行确定它能接受的流量传输模式传输模式.应答分组经过各路由器应答分组经过各路由器时时,对各路由器所记录对各路由器所记录的发送者流量说明信息的发送者流量说明信息进行确认进行确认.连接请求

11、分组经过各路连接请求分组经过各路由器时由器时,各路由器记录各路由器记录流量说明信息流量说明信息.确认确认 转发转发转发转发转发转发确认确认 图图 虚电路交换的建立虚电路交换的建立 在数据传输过程中,路由器将根据协商好的传输模式对该链路上的交通进行整形.是调整数据传输的平均速率,使数据按照传输模式规定的速率进行传输,尽量避免突发性增大通信量,导致产生拥塞问题.交通整形是对传输速率进行调整,而不是调整流量控制中一次可传送的数据量.2. 2.面向数据报的拥塞控制算法面向数据报的拥塞控制算法 数据报服务是一种无连接传输方式。路由器一旦检测到系统可用资源(如链路利用率或队列长度)超过临界值,就会向源主机

12、发送一个抑制分组,警告网络可能发生拥塞.源端主机定期地侦听抑制分组,如果在侦听期内收到抑制分组,则会减少发送给目的主机的数据量. 当减至在侦听期不再收到抑制分组后,可以逐渐增加通信量.主机可以通过调整其发送操作的相关参数(发送窗口或漏桶输出率)来减少通信量,路由器通常采用加权公平队列算法来处理分组排队,检测是否超过临界值,以及何时发送抑制分组. 图图 基于数据报服务的拥塞控制策略基于数据报服务的拥塞控制策略源主机源主机目的主机目的主机抑制分组抑制分组抑制分组抑制分组抑制分组抑制分组抑制分组抑制分组主机收到主机收到抑制抑制分组分组后，逐步后，逐步减少发送给目减少发送给目的主机的分组的主机的分组数量，一般改数量，一般改变发送窗口或变发送窗口或采用漏桶输出采用漏桶输出率等。率等。 ,因为距离远,反应慢.一种改进的方法是抑制分组途径的各个路由器都要抑制通信量,使通信量得