第7讲路由选择和拥塞控制1.ppt

《第7讲路由选择和拥塞控制1.ppt》由会员分享，可在线阅读，更多相关《第7讲路由选择和拥塞控制1.ppt（58页珍藏版）》请在三一文库上搜索。

1、第六章 路由选择与拥塞控制（1）,路由选择,1,河海大学电子信息工程系,5.1 网络层功能概述 5.2 路由技术的基本概念 5.3 路由选择算法 5.4 路由选择协议概述,2,河海大学电子信息工程系,5.1 网络层的功能,比特流,物理层,数据链路层,网络层,传输层,应用层,比特流,物理层,数据链路层,网络层,物理层,数据链路层,网络层,传输层,应用层,主机A,主机B,packet,packet,通信子网,资源子网,3,河海大学电子信息工程系,网络层主要提供两种服务,可靠的、面向连接的服务； 代表网络：ATM 对应的组织结构：虚电路 不可靠的、无连接的服务； 代表网络：Internet 对应的组

2、织结构：数据报,4,河海大学电子信息工程系,1.什么是路由选择技术,所谓路由选择，指的是在分布式分组交换网中，每个节点具有自动选择传送分组到达目的地的最佳路径的能力。 （意味着每个节点都有一张路由表） 路由选择技术是实现异种网互连的关键技术。,5,河海大学电子信息工程系,IP数据报寻径,R1,R3,le1,le3,le2,R2,NET1,NET2,NET3,R0,R4,6,河海大学电子信息工程系,2.路由器的两个基本任务,路由=建立图表和指引方向 交换=在节点之间移动分组,7,河海大学电子信息工程系,路由选择算法,1. 默认路由 2. 静态路由 3. 动态路由之一：距离向量法 4. 动态路由之

3、二：链路状态法,8,河海大学电子信息工程系,测量路径长度的方法,计算站点数量或经过的链路条数 以公里为单位的地理距离，路径的权重是长度。 其它的度量方法，例如用标准测试分组以每时间单位（小时或天）测试运行，每条链路都以所获得的平均缓存队列长度或传输时延来标识。 链路的标注可以是距离、信道带宽、平均业务量、通信费用、队列平均长度、测量的时延和其它一些因素的函数而计算出来。,9,河海大学电子信息工程系,1. 默认路由（Default Route）,什么是默认路由？ 对那些在路由表中未包含其路由选择信息的信宿（网络/主机）设定的缺省路径 在路由表中信宿地址取值0.0.0.0(Default) 默认路

4、由的作用 对所有自治系统以外的信宿都采用默认路由 简化路由计算，提高寻径效率，缩短表长,10,河海大学电子信息工程系,默认路由举例,网络A,网络D,Rd,b0,c0,f0,e0,Default Rd e0,Default Rd f0,Default Ra b0,Default Ra c0,Ra,Rc,Rb,Rf,Re,11,河海大学电子信息工程系,2. 静态路由,静态路由的概念 静态路由工作原理 路由配置举例 故障举例（网络拓扑结构变化） 用人工修改配置排除故障,12,河海大学电子信息工程系,静态路由的概念,由网络管理员设置路由表 简单、有效，适于结构简单的网络 不适于拓扑结构和传输流量经常改

5、变的复杂网络,13,河海大学电子信息工程系,静态路由举例,网络A,网络C,网络B,Ra路由表 网络B Rb a2 网络C Rc a3,Rb路由表 网络A Ra b3 网络C Rc b2,Rc路由表 网络B Rb c2 网络A Ra c3,a1,a3,a2,c3,c2,c1,b2,b3,b1,Ra,Rb,Rc,14,河海大学电子信息工程系,链路发生故障,网络A,网络C,网络B,Rb路由表 网络A Ra b3 网络C Rc b2,Rc路由表 网络B Rb c2 网络A Ra c3,a1,a3,a2,c3,c2,c1,b2,b3,b1,?,?,Ra路由表 网络B Rb a2 网络C Rc a3,Ra

6、,Rb,Rc,15,河海大学电子信息工程系,解决办法：人工修改,网络A,网络C,网络B,Rb路由表 网络A Ra b2 网络C Rc b2,Rc路由表 网络B Rb c2 网络A Ra c3,a1,a3,a2,c3,c2,c1,b2,b3,b1,！,！,不适于网络变化！,Ra路由表 网络B Rc a3 网络C Rc a3,Ra,Rb,Rc,16,河海大学电子信息工程系,3. 距离向量算法,Distance-Vector 1) D-V算法的基本概念 2) D-V算法的动态特性 3) D-V算法的收敛性问题及其解决办法 4) D-V算法小结,17,河海大学电子信息工程系,A 路由表,1) 距离向量

7、算法的基本概念,周期性地相互传递信息 每个路由器向与它相邻的站点发送一个包含它到所有其他路由器的距离的向量（最短路径或最小代价） 维护各自的路由表 路由器根据邻居发送的距离向量的动态信息启动算法，更新路由表,D,C,A,B 路由表,C 路由表,B,18,河海大学电子信息工程系,距离向量法的计算举例,A,D,E,C,B,7,1,8,2,2,1,计算从E经相邻站点A、B和D到达信宿A、B、C和D的最小代价D (destination,neighbor) 得从E到达信宿的最佳路径（最小代价）路由表,最小代价D (des,nei),E的路由表,19,河海大学电子信息工程系,2) D-V算法的动态特性,

8、建立路由表的初始过程 发现新的网络 发现链路断开,20,河海大学电子信息工程系,D-V建立路由表的初始过程,A,C,B,10.0.0.0,40.0.0.0,30.0.0.0,20.0.0.0,a0 a1 b0 b1 c0 c1,21,河海大学电子信息工程系,D-V网络发现过程剖析,1 1,A,C,B,到达信宿40.0.0.0的路由变化,如果网络中的最长路径为N，则算法经过N次迭代计算后收敛。即第N步之后，网上的所有路由器都获得到达信宿40.0.0.0的路由信息。,40.0.0.0 down,40.0.0.0 up,22,河海大学电子信息工程系,网关-网关协议GGP,GGP概述 GGP的路由发现

9、、传播和刷新过程 GGP的故障发生后的路由变化 GGP协议报文,23,河海大学电子信息工程系,网关-网关协议GGP概述,Internet早期的路由广播协议 用于核心网关路由交换 对于用路由广播协议实现路由广播算法具有示范意义 特点 以站点数（Hop）为距离 实现D-V算法,ARPANET,Internet 最初主干,核心网关,本地网点,本地网点,本地网点,24,河海大学电子信息工程系,发现网络,A,D,C,B,NET1,NET4,NET3,NET2,(0,3),(0,4),(0,3),(0,4),(0,1),(0,2),（Hop, Net ID),25,河海大学电子信息工程系,A,D,C,B,

10、NET1,NET4,NET3,NET2,(0,4) /D,向邻居传播发现信息,(0,3) /D,(0,3) /B,(0,4) /C,26,河海大学电子信息工程系,A,D,C,B,NET1,NET4,NET3,NET2,(0,3) (1,4),根据邻居传播的信息更新路由,(0,4) (1,3),(0,1) (1,3),(0,2) (1,4),27,河海大学电子信息工程系,A,D,C,B,NET1,NET4,NET3,NET2,(0,1) (1,3),(0,2) (1,4),传播更新信息,(1,4) /B,(1,3) /C,28,河海大学电子信息工程系,A,D,C,B,NET1,NET4,NET3

11、,NET2,(0,1) (1,3) (2,4),(0,2) (1,4) (2,3) ,更新路由,29,河海大学电子信息工程系,A,D,C,B,NET1,NET4,NET3,NET2,(0,1) (,3) (,4) ,(0,2) (1,4) (2,3) ,B发生故障,30,河海大学电子信息工程系,GGP协议报文,封装 封装在IP数据报中，用IP协议传输 类型 路由刷新 确认（收到刷新报文的回送信息） 回应请求/应答（主动测试） 接口状态,31,河海大学电子信息工程系,3) 距离向量法的收敛性问题,问题 逐站传递更新信息，算法的收敛速度慢 有可能出现各站路由信息不一致 有可能传播错误的路由信息 后

12、果 在站点间构成更新路由的路径环（Routing Loops） 计数至无穷大（Count to Infinity）,32,河海大学电子信息工程系,距离向量法收敛性问题的解决办法,定义路径代价的最大值（Maximum） 提高收敛速度 水平分割（Split Horizon） 毒性逆转（Poison Reverse） 保持计时（Hold-Down Timers） 触发更新（Triggered Updates） 加速方法的综合应用举例,33,河海大学电子信息工程系,传播错误的路由信息,1 1,A,C,B,到达信宿40.0.0.0的路由变化,C与B之间的对话： 我得不到信宿40.0.0.0的任何路由信息

13、，你能告诉我如何到达信宿吗？ 我可以到达信宿，距离为1。（传播了一条过时的错误信息） 既然如此，我选择经过你到达信宿的路径，距离为2。,34,河海大学电子信息工程系,1 1,A,C,B,到达信宿40.0.0.0的路由变化,路径环（Routing Loop）问题,这条错误的路由信息在C与B之间不断复制和修改，并在网络中传播（殃及A），形成路径传播的环路。,35,河海大学电子信息工程系,1 1,A,C,B,到达信宿40.0.0.0的路由变化,严重后果：计数至无穷大,36,河海大学电子信息工程系,1 1,A,C,B,到达信宿40.0.0.0的路由变化（定义Hop最大值为16）,定义距离的最大值,收敛

14、！,37,河海大学电子信息工程系,水平分割方法的思路,1 1,A,C,B,分析路径环产生的原因 B向C提供了一条过时的、错误的路由信息。 能否避免事件发生？ B必须经由C方可到达网络40.0.0.0，B不可能向C提供任何有价值的路由信息。 修改B对C提供的路由，禁止B向C提供关于此信宿的路由信息。 解决办法 B告诉C一条在正常情况下不真实的消息：网络40.0.0.0不可达（距离为）。,38,河海大学电子信息工程系,40.0.0.0,用水平分割法加速算法收敛,1 1,A,C,B,到达信宿40.0.0.0的路由变化,链路断开时C与B之间的对话： 我得不到信宿40.0.0.0的任何路由信息，你能告诉

15、我如何到达信宿吗？ 我不能到达信宿，距离为。 既然如此，我认为信宿不可达。,收敛！,40.0.0.0 down,39,河海大学电子信息工程系,40.0.0.0,毒性逆转法,1 1,A,C,B,到达信宿40.0.0.0的路由变化,方法 当C发现网络40.0.0.0发生故障时，主动将到达信宿的距离改为。 结果 如果无其他到达信宿的路径，算法迅速收敛为信宿不可达。 如果存在其他到达信宿的路径，C根据传播过来的信息再做修改。,收敛！,40.0.0.0 down,40,河海大学电子信息工程系,保持计时法,1 1,A,C,B,当C发现网络40.0.0.0发生故障时，启动保持计时器 在保持计时期间内，C的策

16、略 如果网络状态转变，down up，关闭计时器，保留原有路由信息； 如果收到来自B的关于信宿的路由信息，且路径比原有路径短，则关闭计时器，更新路由信息； 如果无上述两种情况发生，计时器到时，更新路由为信宿不可达。,网络40.0.0.0不可达,到时,41,河海大学电子信息工程系,1 1,A,C,B,当C发现网络40.0.0.0发生故障时，不等下一刷新周期到来，立刻更改路由为“信宿不可达” 引起全网的连锁反映，迅速刷新,触发刷新法,网络40.0.0.0不可达,网络40.0.0.0不可达,网络40.0.0.0不可达,42,河海大学电子信息工程系,D40.0.0.0 (0，直接),（1）C发现信宿不

17、可达,D,B,A,E,C,C发现网络40.0.0.0不可达： 1. 用毒性逆转法将到达网络40.0.0.0的距离该为： 2. 启动保持计时器； 3. 用触发刷新法立即向B和D发送“信宿可能不可达”通知。,0:0:05,D40.0.0.0 (1，C),D40.0.0.0 (1，C),D40.0.0.0 (2，D),40.0.0.0,D40.0.0.0 (0，直接),D40.0.0.0 (，直接),D40.0.0.0 (，直接),40.0.0.0距离为,43,河海大学电子信息工程系,（2）B和D接收到触发刷新报文,D,B,A,E,C,B和D接收到来自C的“网络40.0.0.0可能不可达”报文： 1

18、. 启动各自的保持计时器； 2. 用触发刷新法立即向A发送“信宿可能不可达”通知； 3. C计时器到时，更新路由表。,到时,0:0:15,0:0:10,刷新路由 D40.0.0.0 (，直接),D40.0.0.0 (，C),D40.0.0.0 (，C),D40.0.0.0 (2，D）,D信宿(距离，下站),44,河海大学电子信息工程系,0:0:15,时间到,0:0:35,时间到,0:0:30,时间到,（3）A接收到触发刷新报文,D,B,A,E,C,A接收到来自B的“网络40.0.0.0可能不可达”报文： 1. 启动保持计时器； 2. 在路由刷新之前，仍然可以向信宿发送数据包； 3. 计时器时间

19、到时，刷新路由表。,D40.0.0.0 (，直接),D40.0.0.0 (2，D),Packets for Net 40.0.0.0,D40.0.0.0 ( ，D),D40.0.0.0 ( ，C),D40.0.0.0 ( ，C),45,河海大学电子信息工程系,RIP协议 Router Information Protocol,RIP协议的基本概念 RIP协议的实现 RIP路由数据封装 路由请求/路由响应 RIP协议的工作原理 对路由信息的处理 对时钟的处理,46,河海大学电子信息工程系,RIP协议的基本概念,Router Information Protocol 最初为Xerox网络系统的通用

20、协议而设计 与4BSD/UNIX捆绑在一起（routed进程） 1988年RFC1058正式定义 基于以站点数（hop）为度量的D-V算法 定义hop=16为无穷大 刷新周期为30秒 适于小型网络的内部路由协议,47,河海大学电子信息工程系,Solaris系统的RIP实现,routed进程的启动 主动路由（active）： 路由器广播 被动路由（passive）： 主机接收 routed进程的运行 具有相同路径长度的路由选择先入为主 定义路由条目的生存时间180秒 对慢收敛的对策 水平分割 毒性逆转 触发更新 保持计时,48,河海大学电子信息工程系,routed进程的启动,开机,检查所有网卡,

21、有静态路由,一块网卡,启动routed进程 进入被动路由工作模式,不用RIP协议选择路由,是,是,否,否,主动广播路由信息/30秒,被动监听路由信息/30秒,Router,Host,启动routed进程 进入主动路由工作模式,128.1.2.10,128.1.2.15,49,河海大学电子信息工程系,routed进程发出路由请求,RIP报文,UDP报头,IP报头,Ethernet 报头,目的地址=ff:ff:ff:ff:ff:ff 源地址=0:a0:24:ec:c6:63 协议类型=0800(IP),宿=128.1.2.255 源=128.1.2.10 协议类型=17(UDP),宿端口=520（

22、RIP） 源端口=520 命令类型=1 (route request),寻径地址类别=2(IP) 寻径目的地址=0.0.0.0 下站=default 端口=0 距离=16（不可达）,主机128.1.2.10向广播地址发出路由请求（开机时自动完成）。,50,河海大学电子信息工程系,RIP报文,UDP报头,IP报头,Ethernet 报头,目的地址=ff:ff:ff:ff:ff:ff 源地址=0:a0:24:ea:b3:57 协议类型 =0800(IP),宿=128.1.2.255 源=128.1.2.15 协议类型=17(UDP),宿端口=520（RIP） 源端口=520 命令类型=2 (rou

23、te response),routed进程发出路由响应,寻径地址类别=2(IP) 寻径目的地址=128.1.1.0 下站=128.1.1.0 端口=0 距离=1,间隔30秒，从广播地址可以接收到路由器128.1.2.15发出的路由响应。,51,河海大学电子信息工程系,RIP协议的路由刷新,Routed进程接收到路由广播信息，在满足以下任一条件下更新自己的路由表项： 一条新的路由表项，且到达目的地址的距离不是无穷大； 一条旧的路由表项，且此条目被原信息提供者（邻接路由器）更新（水平分割）； 一条旧的路由表项已经有90秒未被刷新；有一条新的到达同一目的地址的路由信息到来，且距离更短。,52,河海大

24、学电子信息工程系,RIP协议的时钟,路由刷新周期 每个路由器每隔30秒刷新和广播自己的路由表。 路由失效计时 一条路由表项未被更新的时间达3分钟（180秒），则视其为失效信息，将本路由表项的距离置为无穷大（毒性逆转）。 路由保持计时 发现一条路由失效信息后，立即启动保持计时，60秒之后删除此条目。,53,河海大学电子信息工程系,4) 距离向量算法小结,采用最短路径准则，计算D信宿(距离，下站)； 每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算法； 算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大； 当路径环产生时

25、，定义距离的最大值可防止算法进入死循环，解决计数至无穷大问题。,54,河海大学电子信息工程系,链路状态算法最短路径算法,定义： 集合S: 尚未找到最短路径节点的集合 数组R: Ri为从指定源点到目的节点i的前一个节点 数组D: Di为指定源点到节点i的最短路径 特征： 每一步只能选择出一个节点（S中每次少一个点） 遇到距离相同的情况，选择经过节点少的点,55,河海大学电子信息工程系,步骤 R2 D2 R3 D3 R4 D4 R5 D5 R6 D(6) N 1 1 2 1 5 1 1 4 2 1 2 4 4 1 1 2 3 1 2 4 4 1 1 4 2 5 4 1 2 5 3 1 1 4 2 5 4 3 5 1 2 5 3 1 1 4 2 5 4 6,56,河海大学电子信息工程系,1,3,2,4,5,6,1,2,2,1,3,3,5,2,1,5,1,3,2,4,5,6,1,2,1,2,1,57,河海大学电子信息工程系,D-V 通过与邻居的信息交换获得网络拓扑知识 路由计算是增加路由器之间的站点数（hops） 定期刷新路由：收敛慢 向相邻站点传送路由表的副本,L-S 全网获得共同的全局性网络拓扑知识（L-S图） 计算到达其他站点的最短路径（SPF准则） 触发刷新：收敛快 向其他站点发送链路状态的动态变化,D-V和L-S算法的比较,