动态路由算法与拥塞控制.ppt
主要内容（2）,7.1网络层概述7.2路由算法7.2.1 最优化原则7.2.2 最短路径路由算法7.2.3 洪泛算法7.2.4 基于流量的路由算法7.2.5 距离向量路由算法7.2.6 链路状态路由算法7.2.7 分层路由7.2.8 移动主机的路由,7.2路由算法（28）,7.2.5距离向量路由算法（DV：Distance Vector Routing）属于动态路由算法,也称Bellman-Ford路由算法和Ford-Fulkerson算法，最初用于ARPANET，被RIP(Routing Information Protocol)协议采用。基本思想每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表；以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离；,7.2路由算法（29）,每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表；邻居结点X向路由器Y发来的表中，X到路由器Zi的距离为Li，路由器Y到X的距离为m，则路由器Y经过X到Zi的距离为Li+m。根据不同邻居发来的信息，计算Li+m，并取最小值，更新Y路由器的路由表；注意：Y路由器中的老路由表在计算中不被使用,路由器,J从它的四个邻居路由器上收到的向量,J的新路由表,A,8,20,A,28,I,20,H,17,I,30,I,18,H,12,H,10,I,0,6,K,15,K,7.2路由算法（30）,无限计算问题算法的缺陷：对好消息反应迅速(好消息：网络上加入一个路由器）对坏消息反应迟钝（坏消息：网络上减少一个路由器）,对好消息反应迅速,对坏消息反应迟钝：引起无穷计算问题,7.2路由算法（31）,为什么会出现无穷计算问题：因为路由器A通过路由器B才能到达路由器C，虽然路由器A已经下线，C仍然向B报告了以前C到A的距离。解决无穷计算问题的方法：水平分裂算法工作过程与距离向量算法相同，区别在于到X的距离不向真正通向X的邻居结点报告，使得坏消息传播的也快。,7.2路由算法（32）,7.2路由算法（33）,虽然广泛使用，但有时候会失败。,主要内容（2）,7.1网络层概述7.2路由算法7.2.1 最优化原则7.2.2 最短路径路由算法7.2.3 洪泛算法7.2.4 基于流量的路由算法7.2.5 距离向量路由算法7.2.6 链路状态路由算法7.2.7 分层路由7.2.8 移动主机的路由,7.2路由算法（34）,7.2.6链路状态路由算法（LS：Link State Routing）距离向量路由算法的主要问题选择路由时，没有考虑线路带宽；路由收敛速度慢(无穷计算)。,7.2路由算法（35）,链路状态路由算法发现邻居结点，并学习它们的网络地址；测量到每个邻居结点的延迟或开销；将所有学习到的内容封装成一个包；将这个包发送给所有其它路由器；每个路由器独立计算到其它路由器的最短路径。,返回,7.2路由算法（36）,发现邻居结点，并学习它们的网络地址；路由器启动后，通过发送HELLO包发现邻居结点；两个或多个路由器连在一个LAN时,引入人工结点；,7.2路由算法（37）,7.2路由算法（38）,测量到每个邻居结点的延迟或开销；一种直接的方法是：发送一个要对方立即响应的ECHO包，来回时间除以2即为延迟。,7.2路由算法（39）,将所有学习到的内容封装成一个包；包以发送方的标识符开头，后面是序号、年龄和一个邻居结点列表；列表中对应每个邻居结点，都有发送方到它们的延迟或开销；链路状态包定期创建或发生重大事件时创建。,7.2路由算法（40）,7.2路由算法（41）,将这个包发送给所有其它路由器；基本思想：洪泛链路状态包，为控制洪泛，每个包包含一个序号，每次发送新包时加1。路由器记录信息对(源路由器，序号)，当一个链路状态包到达时，若是新的，则分发；若是重复的，则丢弃；若序号比路由器记录中的最大序号小，则认为过时而丢弃；,7.2路由算法（42）,第4步中存在的问题序号循环使用会混淆路由器崩溃；序号出错；,7.2路由算法（43）,解决这些问题的办法序号循环使用会混淆，解决办法：使用32位序号；路由器崩溃后，序号重置；增加年龄（age）域，每秒钟年龄减1，为零则丢弃。链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包；序号出错链路状态包需要应答；,7.2路由算法（44）,计算到每个其它路由器的最短路径。根据Dijkstra算法计算最短路径；实用协议Internet网络协议：内部网关路由协议开放最短路径优先OSPF（Open Shortest Path First）IS-IS,7.2路由算法（45）,距离向量算法（DV）和链路状态算法（LS）的比较路由信息的复杂性DV仅在邻居节点之间交换LS路由信息向全网发送N节点，E个连接的情况下，每个节点发送O(nE)的报文,7.2路由算法（46）,收敛（Convergence）速度DV收敛时间不定：可能会出现路由循环LS使用最短路径优先算法，算法复杂度为O(n2)（n个结点（不包括源结点），需要n*(n+1)/2 次比较），如果使用更有效的实现方法，算法复杂度可以达到O(nlogn)可能存在路由振荡（oscillations）,7.2路由算法（47）,健壮性:如果路由器不能正常工作会发生什么?DV结点会广播错误的路径开销每个结点的路由表被别的结点使用，错误会传播到全网LS结点会广播错误的链路开销每个结点只计算自己的路由表,主要内容（2）,7.1网络层概述7.2路由算法7.2.1 最优化原则7.2.2 最短路径路由算法7.2.3 洪泛算法7.2.4 基于流量的路由算法7.2.5 距离向量路由算法7.2.6 链路状态路由算法7.2.7 分层路由7.2.8 移动主机的路由,7.2路由算法（48）,7.2.7分层路由（Hierarchical Routing）网络规模增长带来的问题路由器中的路由表增大；路由器为选择路由而占用的内存、CPU时间和网络带宽增大。,7.2路由算法（49）,分层路由分而治之的思想；根据需要，将路由器分成区域（regions）、聚类（clusters）、区（zones）和组（groups）Fig.5-17，路由表由17项减为7项。分层路由带来的问题路由表中的路由不一定是最优路由。,7.2路由算法（50）,主要内容（2）,7.1网络层概述7.2路由算法7.2.1 最优化原则7.2.2 最短路径路由算法7.2.3 洪泛算法7.2.4 基于流量的路由算法7.2.5 距离向量路由算法7.2.6 链路状态路由算法7.2.7 分层路由7.2.8 移动主机的路由,7.2路由算法（51）,7.2.8移动主机的路由需要解决的问题为了能够将数据包转发给移动主机，网络必须首先要找到移动的主机。网络结构示意图,7.2路由算法（52）,一些基本概念,移动用户（mobile users）：包括位置发生变化，通过固定方式或移动方式与网络连接的两类用户,家乡位置（home location）：所有用户都有一个永久的家乡位置，用一个地址来标识；,外部代理（foreign agent）：每个区域（一个LAN或一个wireless cell）有一个或多个外部代理，它们记录正在访问该区域的移动用户；,家乡代理（home agent）：每个区域有一个家乡代理，负责记录家乡在该区域，但是目前正在访问其它区域的用户。,7.2路由算法（53）,外部代理定期广播声明自己的存在和地址的包，新到达的移动主机接收该信息；若移动用户未能收到该信息，则移动主机广播包，询问外部代理的地址,移动主机向外部代理注册，告知其家乡地址、目前的数据链路层地址和一些安全信息；,外部代理与移动主机的家乡代理联系，告知移动主机的目前位置、自己的网络地址和一些安全信息；,家乡代理检查安全信息，通过，则给外部代理确认;,外部代理收到确认后，在登记表中加入一项，并通知移动主机注册成功。,移动用户进入一个新区域时，必须首先向外部代理注册,7.2路由算法（54）,移动用户的路由转发过程,当一个包发给移动用户时，首先被转发到用户的家乡局域网；,该包到达用户的家乡局域网后，被家乡代理接收，家乡代理查询移动用户的新位置和与其对应的外部代理的地址；,家乡代理采用隧道技术，将收到的包作为净荷封装到一个新包中，发给外部代理；,家乡代理告诉发送方，发给移动用户的后续包作为净荷封装成包直接发给外部代理；,外部代理收到包后，将净荷封装成数据链路帧发给移动用户。,主要内容（2）小结（1）,7.1网络层概述7.2路由算法7.2.1 最优化原则7.2.2 最短路径路由算法7.2.3 洪泛算法7.2.4 基于流量的路由算法7.2.5 距离向量路由算法7.2.6 链路状态路由算法7.2.7 分层路由7.2.8 移动主机的路由,主要内容（2）小结（2）,最优化原则路由算法的目的是找出并使用汇集树。静态路由算法最短路径路由算法洪泛算法基于流量的路由算法,主要内容（2）小结（3）,动态路由算法距离向量路由算法将自己（路由结点）对全网拓扑结构的认识告诉给邻居无穷计算问题，水平分裂算法链路状态路由算法将自己（路由结点）对邻居的认识洪泛给全网分层路由移动主机的路由,主要内容（3）,7.3拥塞控制算法7.3.1 拥塞控制的基本原理7.3.2 拥塞控制算法7.4网络互连 7.4.1 级联虚电路 7.4.2 无连接网络互连 7.4.3 隧道技术 7.4.4 互联网路由 7.4.5 分段 7.4.6 防火墙,主要内容（3）,7.3拥塞控制算法7.3.1 拥塞控制的基本原理7.3.2 拥塞控制算法,7.3拥塞控制算法（1）,拥塞（congestion）网络上有太多的包时，性能会下降，这种情况称为拥塞。拥塞产生的原因多个输入对应一个输出；慢速处理器；低带宽线路。,7.3拥塞控制算法（2）,解决办法针对某个因素的解决方案，只能对提高网络性能起到一点点好处，甚至可能仅仅是转移了影响性能的瓶颈；需要全面考虑各个因素。,7.3拥塞控制算法（3）,拥塞控制与流量控制的差别拥塞控制（congestion control）需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，涉及主机、路由器等很多因素；流量控制（flow control）与点到点的通信量有关，主要解决快速发送方与慢速接收方的问题，是局部问题，一般都是基于反馈进行控制的。,发送的分组,转发的分组,子网的最大传输容量,7.3拥塞控制算法（4）,7.3.1拥塞控制的基本原理根据控制论，拥塞控制方法分为两类开环控制通过好的设计来解决问题，避免拥塞发生；拥塞控制时，不考虑网络当前状态。闭环控制基于反馈机制；工作过程监控系统，发现何时何地发生拥塞；把发生拥塞的消息传给能采取动作的站点调整系统操作，解决问题。,7.3拥塞控制算法（5）,衡量网络是否拥塞的参数缺乏缓冲区造成的丢包率；平均队列长度；超时重传的包的数目；平均包延迟；包延迟变化（Jitter）。,7.3拥塞控制算法（6）,反馈方法向负载发生源发送一个告警包；包结构中保留一个位或域用来表示发生拥塞，一旦发生拥塞，路由器将所有的输出包置位，向邻居告警；主机或路由器主动地、周期性地发送探报（probe），查询是否发生拥塞。,主要内容（3）,7.3拥塞控制算法7.3.1 拥塞控制的基本原理7.3.2 拥塞控制算法,7.3拥塞控制算法（7）,7.3.2拥塞控制算法拥塞预防策略流量整形（Traffic Shaping）流说明（Flow Specification）虚电路子网中的拥塞控制抑制包（Choke Packets）加权公平队列（Weighted Fair Queueing）逐跳抑制包（Hop-by-Hop Choke Packets）负载丢弃（Load Shedding）,7.3拥塞控制算法（8）,拥塞预防策略开环控制影响拥塞的网络设计策略,7.3拥塞控制算法（9）,7.3拥塞控制算法,7.3拥塞控制算法（7）,7.3.2拥塞控制算法拥塞预防策略流量整形（Traffic Shaping）流说明（Flow Specification）虚电路子网中的拥塞控制抑制包（Choke Packets）加权公平队列（Weighted Fair Queueing）逐跳抑制包（Hop-by-Hop Choke Packets）负载丢弃（Load Shedding）,7.3拥塞控制算法（10）,流量整形（Traffic Shaping）开环控制基本思想造成拥塞的主要原因是网络流量通常是突发性的；强迫包以一种可预测的速率发送；在ATM网中广泛使用。,7.3拥塞控制算法（11）,漏桶算法（The Leaky Bucket Algorithm）将用户发出的不平滑的数据包流转变成网络中平滑的数据包流；可用于固定包长的协议，如ATM；也可用于可变包长的协议，如IP，使用字节计数；无论负载突发性如何，漏桶算法强迫输出按平均速率进行，不灵活。,7.3拥塞控制算法（12）,令牌桶算法（The Token Bucket Algorithm）漏桶算法不够灵活，因此加入令牌机制；基本思想：漏桶存放令牌，每T秒产生一个令牌，令牌累积到超过漏桶上界时就不再增加。包传输之前必须获得一个令牌，传输之后删除该令牌；,7.3拥塞控制算法（13）,漏桶算法与令牌桶算法的区别流量整形策略不同：漏桶算法不允许空闲主机积累发送权，以便以后发送大的突发数据；令牌桶算法允许，最大为桶的大小。漏桶中存放的是数据包，桶满了丢弃数据包；令牌桶中存放的是令牌，桶满了丢弃令牌，不丢弃数据包。,漏桶算法/令牌桶算法比较,时间t,流量,漏桶输入的流量,25MB/s 持续40ms,漏桶输出的流量,25,漏桶算法,25MB/s 持续40ms,令牌桶输出的流量,容量为250KB的令牌桶算法,25MB/s 持续40ms,令牌桶输出的流量,容量为500KB的令牌桶算法,25MB/s 持续40ms,令牌桶输出的流量,容量为750KB的令牌桶算法,7.3拥塞控制算法（14）,漏桶/令牌桶组合方法：,一般设定为漏桶的速率比令牌桶的最低速率大，比网络的最大速率小。,25MB/s 持续40ms,容量为500KB的令牌桶+10MB/s的漏桶,7.3拥塞控制算法（15）,令牌桶输出的流量,7.3拥塞控制算法（16）,流说明（Flow Specification）当发送者、接收者和子网都达到一致性后，通信量整形才能发挥最佳效果。要达成一致，必须以一种精确的方式来通知各方，说明通信量模式，即采用流说明的方式。,7.3拥塞控制算法（17）,一个数据流的发送方、接收方和通信子网三方认可的、描述发送数据流的模式和希望得到的服务质量的数据结构，称为流说明。对发送方的流说明，子网和接收方可以做出三种答复：同意、拒绝、其它建议。,7.3拥塞控制算法（18）,一个流说明的例子,7.3拥塞控制算法（19）,虚电路子网中的拥塞控制许可控制（admission control），基本思想：一旦发生拥塞，在问题解决之前，不允许建立新的虚电路；另一种方法是发生拥塞后可以建立新的虚电路，但要绕开发生拥塞的地区；资源预留：建立虚电路时，主机与子网达成协议，子网根据协议在虚电路上为此连接预留资源。,7.3拥塞控制算法（20）,7.3拥塞控制算法（21）,抑制包（Choke Packets）基本思想路由器监控输出线路及其它资源的利用情况，超过某个阈值，则此资源进入警戒状态；每个新包到来，检查它的输出线路是否处于警戒状态；若是，则向源主机发送抑制包，包中指出发生拥塞的目的地址。同时将原包打上标记（为了以后不再产生抑制包），正常转发；,7.3拥塞控制算法（22）,源主机收到抑制包后，按一定比例减少发向特定目的地的流量，并在固定时间间隔内忽略指示同一目的地的抑制包。然后开始监听，若此线路仍然拥塞，则主机在固定时间内减轻负载、忽略抑制包；若在监听周期内没有收到抑制包，则增加负载；通常采用的流量增减策略是：减少时，按一定比例减少，保证快速解除拥塞；增加时，以常量增加，防止很快导致拥塞。,7.3拥塞控制算法（23）,使用抑制包的方法的问题：源端主机是否采取行动是自愿的，假设一个路由器由于被多个主机超量发送的流量而形成拥塞；路由器会向所有的源端主机都发送抑制包；有些主机可能会减慢发送速度，但有些主机不一定会减慢发送速度；结果是遵守规则的主机反而得到了比以前少的带宽。解决这种问题的办法是采用加权公平队列,7.3拥塞控制算法（24）,加权公平队列（Weighted Fair Queueing）公平队列（Fair Queueing）算法路由器的每个输出线路有多个队列；路由器循环扫描各个队列，发送队头的包；所有队列具有相同优先级；一些ATM交换机、路由器使用这种算法；一种改进：对于变长包，由逐包轮循改为逐字节轮循,O,A,B,C,D,E,19,16,8,17,18,7.3拥塞控制算法（25）,7.3拥塞控制算法（26）,加权公平队列算法给不同主机以不同的优先级；优先级高的主机在一个轮循周期内获得更多的时间片。,7.3拥塞控制算法（27）,逐跳抑制包（Hop-by-Hop Choke Packets）在高速、长距离的网络中，由于源主机响应太慢，抑制包算法对拥塞控制的效果并不好，可采用逐跳抑制包算法。基本思想抑制包对它经过的每个路由器都起作用；能够迅速缓解发生拥塞处的拥塞；上游路由器要求有更多的缓冲区；,抑制包算法的过程,抑制包算法的过程,逐跳抑制包算法的过程,逐跳抑制包算法的过程,7.3拥塞控制算法（28）,负载丢弃（Load Shedding）上述算法都不能消除拥塞时，路由器只得将包丢弃；针对不同服务，可采取不同丢弃策略文件传输，优先丢弃新包，wine策略；多媒体服务，优先丢弃旧包，milk策略；早期丢弃包，会减少拥塞发生的概率，提高网络性能。,7.3拥塞控制算法（29）小结,7.3.1 拥塞控制的基本原理7.3.2拥塞控制算法拥塞预防策略流量整形（Traffic Shaping）流说明（Flow Specification）虚电路子网中的拥塞控制抑制包（Choke Packets）加权公平队列（Weighted Fair Queueing）逐跳抑制包（Hop-by-Hop Choke Packets）负载丢弃（Load Shedding）,
