《第7讲路由选择和拥塞控制1》由会员分享，可在线阅读，更多相关《第7讲路由选择和拥塞控制1（58页珍藏版）》请在金锄头文库上搜索。
1、第六章 路由选择与拥塞控制（1）路由选择路由选择5.1网络层功能概述网络层功能概述5.2路由技术的基本概念路由技术的基本概念5.3路由选择算法路由选择算法5.4路由选择协议概述路由选择协议概述1河海大学电子信息工程系5.1 网络层的功能比特流比特流比特流比特流主机主机A主机主机Bpacketpacket通通信信子子网网资资源源子子网网2河海大学电子信息工程系网络层主要提供两种服务n n可靠的、面向连接的服务； 代表网络：ATM 对应的组织结构：虚电路n n不可靠的、无连接的服务； 代表网络：Internet 对应的组织结构：数据报3河海大学电子信息工程系1.什么是路由选择技术n n所谓路由选择
2、，指的是在分布式分组交换网中，每个节点每个节点具有自动选择传送分组到达目的地的最佳路径的能力。 （意味着每个节点都有一张路由表）n n路由选择技术是实现异种网互连的关键技术。4河海大学电子信息工程系IP数据报寻径R1R3le1le3le2R2NET1NET2NET3R0R45河海大学电子信息工程系2.路由器的两个基本任务n n路由路由=建立图表和指引方向n n交换交换=在节点之间移动分组6河海大学电子信息工程系路由选择算法1. 默认路由默认路由2. 静态路由静态路由3. 动态路由之一：距离向量法动态路由之一：距离向量法4. 动态路由之二：链路状态法动态路由之二：链路状态法7河海大学电子信息工程
3、系测量路径长度的方法n n计算站点数量或经过的链路条数计算站点数量或经过的链路条数计算站点数量或经过的链路条数计算站点数量或经过的链路条数n n以公里为单位的地理距离，路径的权重是长度。以公里为单位的地理距离，路径的权重是长度。以公里为单位的地理距离，路径的权重是长度。以公里为单位的地理距离，路径的权重是长度。n n其它的度量方法，例如用标准测试分组以每时间单位（小其它的度量方法，例如用标准测试分组以每时间单位（小其它的度量方法，例如用标准测试分组以每时间单位（小其它的度量方法，例如用标准测试分组以每时间单位（小时或天）测试运行，每条链路都以所获得的平均缓存队列时或天）测试运行，每条链路都以所
4、获得的平均缓存队列时或天）测试运行，每条链路都以所获得的平均缓存队列时或天）测试运行，每条链路都以所获得的平均缓存队列长度或传输时延来标识。长度或传输时延来标识。长度或传输时延来标识。长度或传输时延来标识。 n n链路的标注可以是距离、信道带宽、平均业务量、通信费链路的标注可以是距离、信道带宽、平均业务量、通信费链路的标注可以是距离、信道带宽、平均业务量、通信费链路的标注可以是距离、信道带宽、平均业务量、通信费用、队列平均长度、测量的时延和其它一些因素的函数而用、队列平均长度、测量的时延和其它一些因素的函数而用、队列平均长度、测量的时延和其它一些因素的函数而用、队列平均长度、测量的时延和其它一
5、些因素的函数而计算出来。计算出来。计算出来。计算出来。8河海大学电子信息工程系1. 默认路由（Default Route）n n什么是默认路由？什么是默认路由？n n对那些在路由表中未包含其路由选择信息的信对那些在路由表中未包含其路由选择信息的信对那些在路由表中未包含其路由选择信息的信对那些在路由表中未包含其路由选择信息的信宿（网络宿（网络宿（网络宿（网络/ /主机）设定的缺省路径主机）设定的缺省路径主机）设定的缺省路径主机）设定的缺省路径n n在路由表中信宿地址取值在路由表中信宿地址取值在路由表中信宿地址取值在路由表中信宿地址取值0.0.0.0(Default)0.0.0.0(Default
6、)n n默认路由的作用默认路由的作用n n对所有自治系统以外的信宿都采用默认路由对所有自治系统以外的信宿都采用默认路由对所有自治系统以外的信宿都采用默认路由对所有自治系统以外的信宿都采用默认路由n n简化路由计算，提高寻径效率，缩短表长简化路由计算，提高寻径效率，缩短表长简化路由计算，提高寻径效率，缩短表长简化路由计算，提高寻径效率，缩短表长9河海大学电子信息工程系默认路由举例网络网络A网络网络DRdb0c0f0e0Default Rd e0Default Rd f0Default Rab0Default Rac0RaRcRbRfRe10河海大学电子信息工程系2. 静态路由n n静态路由的概念
7、静态路由的概念n n静态路由工作原理静态路由工作原理n n路由配置举例路由配置举例路由配置举例路由配置举例n n故障举例故障举例故障举例故障举例（网络拓扑结构变化）（网络拓扑结构变化）（网络拓扑结构变化）（网络拓扑结构变化）n n用人工修改配置排除故障用人工修改配置排除故障用人工修改配置排除故障用人工修改配置排除故障11河海大学电子信息工程系静态路由的概念n n由网络管理员设置路由表由网络管理员设置路由表n n简单、有效，适于结构简单的网络简单、有效，适于结构简单的网络n n不适于拓扑结构和传输流量经常改变的复不适于拓扑结构和传输流量经常改变的复杂网络杂网络12河海大学电子信息工程系静态路由举
8、例网络网络A网络网络C网络网络BRa路由表路由表网络网络BRba2网络网络CRca3Rb路由表路由表网络网络ARab3网络网络CRcb2Rc路由表路由表网络网络BRbc2网络网络ARac3a1a3a2c3c2c1b2b3b1RaRbRc13河海大学电子信息工程系链路发生故障网络网络A网络网络C网络网络BRb路由表路由表网络网络ARab3网络网络CRcb2Rc路由表路由表网络网络BRbc2网络网络ARac3a1a3a2c3c2c1b2b3b1?Ra路由表路由表网络网络BRba2网络网络CRca3RaRbRc14河海大学电子信息工程系解决办法：人工修改网络网络A网络网络C网络网络BRb路由表路由表
9、网络网络ARab2网络网络CRcb2Rc路由表路由表网络网络BRbc2网络网络ARac3a1a3a2c3c2c1b2b3b1！不适于网络变化！不适于网络变化！Ra路由表路由表网络网络BRca3网络网络CRca3RaRbRc15河海大学电子信息工程系3.距离向量算法Distance-Vector1) D-V算法的基本概念算法的基本概念2) D-V算法的动态特性算法的动态特性3) D-V算法的收敛性问题及其解决办法算法的收敛性问题及其解决办法4) D-V算法小结算法小结 16河海大学电子信息工程系A路由表路由表1)距离向量算法的基本概念n n周期性地相互传递信息周期性地相互传递信息周期性地相互传递
10、信息周期性地相互传递信息n n每个路由器向与它每个路由器向与它每个路由器向与它每个路由器向与它相邻的站点相邻的站点相邻的站点相邻的站点发送一个包含它到所有其他路发送一个包含它到所有其他路发送一个包含它到所有其他路发送一个包含它到所有其他路由器的距离的向量（最短路径或最小代价）由器的距离的向量（最短路径或最小代价）由器的距离的向量（最短路径或最小代价）由器的距离的向量（最短路径或最小代价）n n维护各自的路由表维护各自的路由表维护各自的路由表维护各自的路由表n n路由器根据邻居发送的距离路由器根据邻居发送的距离路由器根据邻居发送的距离路由器根据邻居发送的距离向量的动态信息启动算法，更向量的动态信
11、息启动算法，更向量的动态信息启动算法，更向量的动态信息启动算法，更新路由表新路由表新路由表新路由表DCAB路由表路由表C路由表路由表B17河海大学电子信息工程系距离向量法的计算举例ADECB718221n n计算从计算从计算从计算从E E经相邻站点经相邻站点经相邻站点经相邻站点A A、B B和和和和DD到达信宿到达信宿到达信宿到达信宿A A、B B、C C和和和和DD的最小代价的最小代价的最小代价的最小代价DD (destination,neighbor) (destination,neighbor)n n得从得从得从得从E E到达信宿的最佳路径（最小代价）路由表到达信宿的最佳路径（最小代价）
12、路由表到达信宿的最佳路径（最小代价）路由表到达信宿的最佳路径（最小代价）路由表最小代价最小代价D (des,nei)E的路由表的路由表18河海大学电子信息工程系2)D-V算法的动态特性n n建立路由表的初始过程建立路由表的初始过程n n发现新的网络发现新的网络n n发现链路断开发现链路断开19河海大学电子信息工程系D-V建立路由表的初始过程ACB10.0.0.040.0.0.030.0.0.020.0.0.0a0 a1b0 b1 c0 c120河海大学电子信息工程系D-V网络发现过程剖析 1 1ACB到达信宿到达信宿40.0.0.0的路由变化的路由变化如果网络中的最长路径为如果网络中的最长路径
13、为N，则算法经过则算法经过N次迭代计算后收敛。即第次迭代计算后收敛。即第N步之后，网上的所有路由器都获得到达信宿步之后，网上的所有路由器都获得到达信宿40.0.0.0的路由信息。的路由信息。40.0.0.0 down40.0.0.0 up21河海大学电子信息工程系网关-网关协议GGPn nGGP概述概述n nGGP的路由发现、传播和刷新过程的路由发现、传播和刷新过程n nGGP的故障发生后的路由变化的故障发生后的路由变化n nGGP协议报文协议报文22河海大学电子信息工程系网关-网关协议GGP概述n nInternetInternet早期的路由广播协议早期的路由广播协议早期的路由广播协议早期的
14、路由广播协议n n用于核心网关路由交换用于核心网关路由交换用于核心网关路由交换用于核心网关路由交换n n对于用路由广播协议实现路由对于用路由广播协议实现路由对于用路由广播协议实现路由对于用路由广播协议实现路由广播算法具有示范意义广播算法具有示范意义广播算法具有示范意义广播算法具有示范意义n n特点特点特点特点n n以站点数（以站点数（以站点数（以站点数（HopHop）为距离为距离为距离为距离n n实现实现实现实现D-VD-V算法算法算法算法ARPANETInternet最初主干最初主干核心核心网关网关本地网点本地网点本地网点本地网点本地网点本地网点23河海大学电子信息工程系发现网络ADCBNE
15、T1NET4NET3NET2(0,3)(0,4)(0,3)(0,4)(0,1)(0,2)（Hop, Net ID)24河海大学电子信息工程系ADCBNET1NET4NET3NET2(0,4) /D向邻居传播发现信息(0,3) /D(0,3) /B(0,4) /C25河海大学电子信息工程系ADCBNET1NET4NET3NET2(0,3)(1,4)根据邻居传播的信息更新路由(0,4)(1,3)(0,1)(1,3)(0,2)(1,4)26河海大学电子信息工程系ADCBNET1NET4NET3NET2(0,1)(1,3)(0,2)(1,4)传播更新信息(1,4) /B(1,3) /C27河海大学电子
16、信息工程系ADCBNET1NET4NET3NET2(0,1) (1,3) (2,4) (0,2) (1,4) (2,3) 更新路由28河海大学电子信息工程系ADCBNET1NET4NET3NET2(0,1) ( ,3) ( ,4) (0,2) (1,4) (2,3) B发生故障29河海大学电子信息工程系GGP协议报文n n封装封装n n封装在封装在封装在封装在IPIP数据报中，用数据报中，用数据报中，用数据报中，用IPIP协议传输协议传输协议传输协议传输n n类型类型n n路由刷新路由刷新路由刷新路由刷新n n确认（收到刷新报文的回送信息）确认（收到刷新报文的回送信息）确认（收到刷新报文的回送
17、信息）确认（收到刷新报文的回送信息）n n回应请求回应请求回应请求回应请求/ /应答（主动测试）应答（主动测试）应答（主动测试）应答（主动测试）n n接口状态接口状态接口状态接口状态30河海大学电子信息工程系3)距离向量法的收敛性问题n n问题问题n n逐站传递更新信息，算法的收敛速度慢逐站传递更新信息，算法的收敛速度慢逐站传递更新信息，算法的收敛速度慢逐站传递更新信息，算法的收敛速度慢n n有可能出现各站路由信息不一致有可能出现各站路由信息不一致有可能出现各站路由信息不一致有可能出现各站路由信息不一致n n有可能有可能有可能有可能传播错误的路由信息传播错误的路由信息传播错误的路由信息传播错误
18、的路由信息n n后果后果n n在站点间构成更新路由的在站点间构成更新路由的在站点间构成更新路由的在站点间构成更新路由的路径环路径环路径环路径环（Routing Routing LoopsLoops）n n计数至无穷大计数至无穷大计数至无穷大计数至无穷大（Count to InfinityCount to Infinity）31河海大学电子信息工程系距离向量法收敛性问题的解决办法n n定义路径代价的最大值定义路径代价的最大值（Maximum）n n提高收敛速度提高收敛速度n n水平分割水平分割水平分割水平分割（Split HorizonSplit Horizon）n n毒性逆转毒性逆转毒性逆转毒
19、性逆转（Poison ReversePoison Reverse）n n保持计时保持计时保持计时保持计时（Hold-Down TimersHold-Down Timers）n n触发更新触发更新触发更新触发更新（Triggered UpdatesTriggered Updates）n n加速方法的综合应用举例加速方法的综合应用举例32河海大学电子信息工程系40.0.0.0 传播错误的路由信息 1 1ACB到达信宿到达信宿40.0.0.0的路由变化的路由变化C C与与与与B B之间的对话：之间的对话：之间的对话：之间的对话：C C我得不到信宿我得不到信宿我得不到信宿我得不到信宿40.0.0.04
20、0.0.0.0的任何路由信息，你能告诉我如何到达信的任何路由信息，你能告诉我如何到达信的任何路由信息，你能告诉我如何到达信的任何路由信息，你能告诉我如何到达信宿吗？宿吗？宿吗？宿吗？B B我可以到达信宿，距离为我可以到达信宿，距离为我可以到达信宿，距离为我可以到达信宿，距离为1 1。（传播了一条过时的错误信息）（传播了一条过时的错误信息）（传播了一条过时的错误信息）（传播了一条过时的错误信息）C C既然如此，我选择经过你到达信宿的路径，距离为既然如此，我选择经过你到达信宿的路径，距离为既然如此，我选择经过你到达信宿的路径，距离为既然如此，我选择经过你到达信宿的路径，距离为2 2。40.0.0.
21、0 down33河海大学电子信息工程系 1 1ACB到达信宿到达信宿40.0.0.0的路由变化的路由变化路径环（Routing Loop）问题这条错误的路由信息在这条错误的路由信息在C与与B之间不断复制和修改，并在网络中之间不断复制和修改，并在网络中传播（殃及传播（殃及A），），形成路径传播的环路。形成路径传播的环路。40.0.0.0 down34河海大学电子信息工程系 1 1ACB到达信宿到达信宿40.0.0.0的路由变化的路由变化严重后果：计数至无穷大40.0.0.0 down35河海大学电子信息工程系 1 1ACB到达信宿到达信宿40.0.0.0的路由变化（定义的路由变化（定义Hop最大
22、值为最大值为16）定义距离的最大值收敛！收敛！40.0.0.0 down36河海大学电子信息工程系水平分割方法的思路 1 1ACBn n分析路径环产生的原因分析路径环产生的原因分析路径环产生的原因分析路径环产生的原因n nB B向向向向C C提供了一条过时的、错误的路由信息。提供了一条过时的、错误的路由信息。提供了一条过时的、错误的路由信息。提供了一条过时的、错误的路由信息。n n能否避免事件发生？能否避免事件发生？能否避免事件发生？能否避免事件发生？n nB B必须必须必须必须经由经由经由经由C C方方方方可到达网络可到达网络可到达网络可到达网络40.0.0.040.0.0.0，B B不不不
23、不可能向可能向可能向可能向C C提供任何有价值提供任何有价值提供任何有价值提供任何有价值的路由信息。的路由信息。的路由信息。的路由信息。n n修改修改修改修改B B对对对对C C提供的路由，禁止提供的路由，禁止提供的路由，禁止提供的路由，禁止B B向向向向C C提供关于此信宿的路由信息。提供关于此信宿的路由信息。提供关于此信宿的路由信息。提供关于此信宿的路由信息。n n解决办法解决办法解决办法解决办法n nB B告诉告诉告诉告诉C C一一一一条在正常情况下不真实的消息：条在正常情况下不真实的消息：条在正常情况下不真实的消息：条在正常情况下不真实的消息：网络网络网络网络40.0.0.040.0.
24、0.0不可达不可达不可达不可达（距离为（距离为（距离为（距离为 ）。40.0.0.0 down37河海大学电子信息工程系40.0.0.0用水平分割法加速算法收敛 1 1ACB到达信宿到达信宿40.0.0.0的路由变化的路由变化链路断开时链路断开时链路断开时链路断开时C C与与与与B B之间的对话：之间的对话：之间的对话：之间的对话：C C我得不到信宿我得不到信宿我得不到信宿我得不到信宿40.0.0.040.0.0.0的任何路由信息，你能告诉我如何到达信的任何路由信息，你能告诉我如何到达信的任何路由信息，你能告诉我如何到达信的任何路由信息，你能告诉我如何到达信宿吗？宿吗？宿吗？宿吗？B B我不能
25、到达信宿，距离为我不能到达信宿，距离为我不能到达信宿，距离为我不能到达信宿，距离为 。C C既然如此，我认为信宿不可达。既然如此，我认为信宿不可达。既然如此，我认为信宿不可达。既然如此，我认为信宿不可达。收敛！收敛！40.0.0.0 down38河海大学电子信息工程系40.0.0.0毒性逆转法 1 1ACB到达信宿到达信宿40.0.0.0的路由变化的路由变化n n方法方法方法方法n n当当当当C C发现网络发现网络发现网络发现网络40.0.0.040.0.0.0发生故障时，发生故障时，发生故障时，发生故障时，主动将到达信宿的距离改为主动将到达信宿的距离改为主动将到达信宿的距离改为主动将到达信宿
26、的距离改为 。n n结果结果结果结果n n如果无其他到达信宿的路径，算法迅速收敛为信宿不可达。如果无其他到达信宿的路径，算法迅速收敛为信宿不可达。如果无其他到达信宿的路径，算法迅速收敛为信宿不可达。如果无其他到达信宿的路径，算法迅速收敛为信宿不可达。n n如果存在其他到达信宿的路径，如果存在其他到达信宿的路径，如果存在其他到达信宿的路径，如果存在其他到达信宿的路径，C C根据传播过来的信息再做修改。根据传播过来的信息再做修改。根据传播过来的信息再做修改。根据传播过来的信息再做修改。收敛！收敛！40.0.0.0 down39河海大学电子信息工程系保持计时法 1 1ACBn n当当当当C C发现网
27、络发现网络发现网络发现网络40.0.0.040.0.0.0发生故障时，发生故障时，发生故障时，发生故障时，启动保持计时器启动保持计时器启动保持计时器启动保持计时器n n在保持计时期间内，在保持计时期间内，在保持计时期间内，在保持计时期间内，C C的策略的策略的策略的策略n n如果网络状态转变，如果网络状态转变，如果网络状态转变，如果网络状态转变，down down up up，关闭计时器，保留原有路由信息；关闭计时器，保留原有路由信息；关闭计时器，保留原有路由信息；关闭计时器，保留原有路由信息；n n如果收到来自如果收到来自如果收到来自如果收到来自B B的关于信宿的路由信息，且路径比原有路径短
28、，则关闭的关于信宿的路由信息，且路径比原有路径短，则关闭的关于信宿的路由信息，且路径比原有路径短，则关闭的关于信宿的路由信息，且路径比原有路径短，则关闭计时器，更新路由信息；计时器，更新路由信息；计时器，更新路由信息；计时器，更新路由信息；n n如果无上述两种情况发生，计时器到时，更新路由为信宿不可达。如果无上述两种情况发生，计时器到时，更新路由为信宿不可达。如果无上述两种情况发生，计时器到时，更新路由为信宿不可达。如果无上述两种情况发生，计时器到时，更新路由为信宿不可达。网络网络40.0.0.0不可达不可达到时到时40.0.0.0 down40河海大学电子信息工程系 1 1ACBn n当当当
29、当C C发现网络发现网络发现网络发现网络40.0.0.040.0.0.0发生故障时，不等下一刷新周期发生故障时，不等下一刷新周期发生故障时，不等下一刷新周期发生故障时，不等下一刷新周期到来，立刻更改路由为到来，立刻更改路由为到来，立刻更改路由为到来，立刻更改路由为“ “信宿不可达信宿不可达信宿不可达信宿不可达” ”n n引起全网的连锁反映，迅速刷新引起全网的连锁反映，迅速刷新引起全网的连锁反映，迅速刷新引起全网的连锁反映，迅速刷新触发刷新法网络网络40.0.0.0不可达不可达网络网络40.0.0.0不可达不可达网络网络40.0.0.0不可达不可达40.0.0.0 down41河海大学电子信息工
30、程系D40.0.0.0 (0，直接，直接)（1）C发现信宿不可达DBAECC发现网络发现网络40.0.0.0不可达：不可达：1. 用毒性逆转法将到达网络用毒性逆转法将到达网络40.0.0.0的距离该为的距离该为 ：2. 启动保持计时器；启动保持计时器；3. 用触发刷新法立即向用触发刷新法立即向B和和D发送发送“信宿可能不可达信宿可能不可达”通知。通知。0:0:05D40.0.0.0 (1，C)D40.0.0.0 (1，C)D40.0.0.0 (2，D)40.0.0.0D40.0.0.0 (0，直接，直接)D40.0.0.0 ( ，直接，直接)D40.0.0.0 ( ，直接，直接)40.0.0.
31、0距离为距离为 42河海大学电子信息工程系（2）B和D接收到触发刷新报文DBAECB和和D接收到来自接收到来自C的的“网络网络40.0.0.0可能不可达可能不可达”报文：报文：1. 启动各自的保持计时器；启动各自的保持计时器；2. 用触发刷新法立即向用触发刷新法立即向A发送发送“信宿可能不可达信宿可能不可达”通知；通知；3. C计时器到时，更新路由表。计时器到时，更新路由表。到时到时0:0:150:0:10刷新路由刷新路由D40.0.0.0 ( ，直接，直接)D40.0.0.0 ( ，C)D40.0.0.0 ( ，C)D40.0.0.0 (2，D）40.0.0.0 downD信宿信宿(距离，下
32、站距离，下站)43河海大学电子信息工程系0:0:15时间到时间到0:0:35时间到时间到0:0:30时间到时间到（3）A接收到触发刷新报文DBAECA接收到来自接收到来自B的的“网络网络40.0.0.0可能不可达可能不可达”报文：报文：1. 启动保持计时器；启动保持计时器；2. 在路由刷新之前，仍然可以向信宿发送数据包；在路由刷新之前，仍然可以向信宿发送数据包；3. 计时器时间到时，刷新路由表。计时器时间到时，刷新路由表。D40.0.0.0 ( ，直接，直接)D40.0.0.0 (2，D)Packets for Net 40.0.0.040.0.0.0 downD40.0.0.0 ( ，D)D
33、40.0.0.0 ( ，C)D40.0.0.0 ( ，C)44河海大学电子信息工程系RIP协议Router Information Protocoln nRIPRIP协议的基本概念协议的基本概念协议的基本概念协议的基本概念n nRIPRIP协议的实现协议的实现协议的实现协议的实现n nRIPRIP路由数据封装路由数据封装路由数据封装路由数据封装n n路由请求路由请求路由请求路由请求/ /路由路由路由路由响应响应响应响应n nRIPRIP协议的工作原理协议的工作原理协议的工作原理协议的工作原理n n对路由信息的处理对路由信息的处理对路由信息的处理对路由信息的处理n n对时钟的处理对时钟的处理对时
34、钟的处理对时钟的处理45河海大学电子信息工程系RIP协议的基本概念Router Information Protocoln n最初为最初为最初为最初为XeroxXerox网络系统的通用协议而设计网络系统的通用协议而设计网络系统的通用协议而设计网络系统的通用协议而设计n n与与与与4BSD/UNIX4BSD/UNIX捆绑在一起（捆绑在一起（捆绑在一起（捆绑在一起（routedrouted进程）进程）进程）进程）n n19881988年年年年RFC1058RFC1058正式定义正式定义正式定义正式定义n n基于以站点数（基于以站点数（基于以站点数（基于以站点数（hophop）为度量的为度量的为度量
35、的为度量的D-VD-V算法算法算法算法n n定义定义定义定义hop=16hop=16为无穷大为无穷大为无穷大为无穷大n n刷新周期为刷新周期为刷新周期为刷新周期为3030秒秒秒秒n n适于小型网络的内部路由协议适于小型网络的内部路由协议适于小型网络的内部路由协议适于小型网络的内部路由协议46河海大学电子信息工程系Solaris系统的RIP实现n nroutedrouted进程的启动进程的启动进程的启动进程的启动n n主动路由主动路由主动路由主动路由（activeactive）：）：）：）：路由器广播路由器广播路由器广播路由器广播n n被动路由（被动路由（被动路由（被动路由（passivepas
36、sive）：）：）：）：主机接收主机接收主机接收主机接收n nroutedrouted进程的运行进程的运行进程的运行进程的运行n n具有相同路径长度的路由选择具有相同路径长度的路由选择具有相同路径长度的路由选择具有相同路径长度的路由选择先入为主先入为主先入为主先入为主n n定义路由条目的生存时间定义路由条目的生存时间定义路由条目的生存时间定义路由条目的生存时间180180秒秒秒秒n n对慢收敛的对策对慢收敛的对策对慢收敛的对策对慢收敛的对策n n水平分割水平分割水平分割水平分割n n毒性逆转毒性逆转毒性逆转毒性逆转n n触发更新触发更新触发更新触发更新n n保持计时保持计时保持计时保持计时47
37、河海大学电子信息工程系routed进程的启动开机开机检查所有网卡检查所有网卡有静态路由有静态路由一块网卡一块网卡启动启动routed进程进程进入被动路由工作模式进入被动路由工作模式不用不用RIP协议选择路由协议选择路由是是是是否否否否主动广播路由信息主动广播路由信息/30秒秒被动监听路由信息被动监听路由信息/30秒秒RouterHost启动启动routed进程进程进入主动路由工作模式进入主动路由工作模式128.1.2.10128.1.2.1548河海大学电子信息工程系routed进程发出路由请求RIP报文报文UDP报头报头IP报头报头Ethernet报头报头目的地址目的地址=ff:ff:ff:
38、ff:ff:ff源地址源地址=0:a0:24:ec:c6:63协议类型协议类型=0800(IP)宿宿=128.1.2.255源源=128.1.2.10协议类型协议类型=17(UDP)宿端口宿端口=520（RIP）源端口源端口=520命令类型命令类型=1(route request)寻径地址类别寻径地址类别=2(IP)寻径目的地址寻径目的地址=0.0.0.0下站下站=default端口端口=0距离距离=16（不可达）（不可达）主机主机128.1.2.10向广播地址发出路由请求（开机时自动完成）。向广播地址发出路由请求（开机时自动完成）。49河海大学电子信息工程系RIP报文报文UDP报头报头IP报
39、头报头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(route response)routed进程发出路由响应寻径地址类别寻径地址类别=2(IP)寻径目的地址寻径目的地址=128.1.1.0下站下站=128.1.1.0端口端口=0距离距离=1间隔间隔30秒，从广播地址可以接收到路由器秒，从广播地址可以接收到路由器128.1.2.1
40、5发出的路由响应。发出的路由响应。50河海大学电子信息工程系RIP协议的路由刷新n nRoutedRouted进程接收到路由广播信息，在满足以下任进程接收到路由广播信息，在满足以下任进程接收到路由广播信息，在满足以下任进程接收到路由广播信息，在满足以下任一条件下更新自己的路由表项：一条件下更新自己的路由表项：一条件下更新自己的路由表项：一条件下更新自己的路由表项：n n一条新的路由表项，且到达目的地址的距离不是无穷一条新的路由表项，且到达目的地址的距离不是无穷一条新的路由表项，且到达目的地址的距离不是无穷一条新的路由表项，且到达目的地址的距离不是无穷大；大；大；大；n n一条旧的路由表项，且此
41、条目被原信息提供者（邻接一条旧的路由表项，且此条目被原信息提供者（邻接一条旧的路由表项，且此条目被原信息提供者（邻接一条旧的路由表项，且此条目被原信息提供者（邻接路由器）更新（水平分割）；路由器）更新（水平分割）；路由器）更新（水平分割）；路由器）更新（水平分割）；n n一条旧的路由表项已经有一条旧的路由表项已经有一条旧的路由表项已经有一条旧的路由表项已经有9090秒未被刷新；有一条新的到秒未被刷新；有一条新的到秒未被刷新；有一条新的到秒未被刷新；有一条新的到达同一目的地址的路由信息到来，且距离更短。达同一目的地址的路由信息到来，且距离更短。达同一目的地址的路由信息到来，且距离更短。达同一目的
42、地址的路由信息到来，且距离更短。51河海大学电子信息工程系RIP协议的时钟n n路由刷新周期路由刷新周期路由刷新周期路由刷新周期n n每个路由器每隔每个路由器每隔每个路由器每隔每个路由器每隔3030秒刷新和广播自己的路由表。秒刷新和广播自己的路由表。秒刷新和广播自己的路由表。秒刷新和广播自己的路由表。n n路由失效计时路由失效计时路由失效计时路由失效计时n n一条路由表项未被更新的时间达一条路由表项未被更新的时间达一条路由表项未被更新的时间达一条路由表项未被更新的时间达3 3分钟（分钟（分钟（分钟（180180秒），则视秒），则视秒），则视秒），则视其为失效信息，将本路由表项的距离置为无穷大（
43、毒其为失效信息，将本路由表项的距离置为无穷大（毒其为失效信息，将本路由表项的距离置为无穷大（毒其为失效信息，将本路由表项的距离置为无穷大（毒性逆转）。性逆转）。性逆转）。性逆转）。n n路由保持计时路由保持计时路由保持计时路由保持计时n n发现一条路由失效信息后，立即启动保持计时，发现一条路由失效信息后，立即启动保持计时，发现一条路由失效信息后，立即启动保持计时，发现一条路由失效信息后，立即启动保持计时，6060秒之秒之秒之秒之后删除此条目。后删除此条目。后删除此条目。后删除此条目。52河海大学电子信息工程系4)距离向量算法小结n n采用采用采用采用最短路径最短路径最短路径最短路径准则，计算准
44、则，计算准则，计算准则，计算DD信宿信宿信宿信宿( (距离，下站距离，下站距离，下站距离，下站) )；n n每个站点只知道自己和邻居的局部信息，在自己的每个站点只知道自己和邻居的局部信息，在自己的每个站点只知道自己和邻居的局部信息，在自己的每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算刷新周期到来时，根据邻居的路由变化重新启动算刷新周期到来时，根据邻居的路由变化重新启动算刷新周期到来时，根据邻居的路由变化重新启动算法；法；法；法；n n算法的收敛速度慢（特别是对网络崩溃）造成全网算法的收敛速度慢（特别是对网络崩溃）造成全网算法的收敛速度慢（特别是对网络
45、崩溃）造成全网算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大；信息的不一致，导致产生路径环，使计数至无穷大；信息的不一致，导致产生路径环，使计数至无穷大；信息的不一致，导致产生路径环，使计数至无穷大；n n当路径环产生时，定义距离的最大值可防止算法进当路径环产生时，定义距离的最大值可防止算法进当路径环产生时，定义距离的最大值可防止算法进当路径环产生时，定义距离的最大值可防止算法进入死循环，解决计数至无穷大问题。入死循环，解决计数至无穷大问题。入死循环，解决计数至无穷大问题。入死循环，解决计数至无穷大问题。53河海大学电子信息工程系链路状态算法最短路径算
46、法定义：定义：定义：定义： 集合集合集合集合S: S: S: S: 尚未找到最短路径节点的集合尚未找到最短路径节点的集合尚未找到最短路径节点的集合尚未找到最短路径节点的集合 数组数组数组数组R: R: R: R: RiRiRiRi 为从指定源点到目的节点为从指定源点到目的节点为从指定源点到目的节点为从指定源点到目的节点i i i i的前一个的前一个的前一个的前一个节点节点节点节点 数组数组数组数组D: D: D: D: DiDiDiDi 为指定源点到节点为指定源点到节点为指定源点到节点为指定源点到节点i i i i的最短路径的最短路径的最短路径的最短路径特征：特征：特征：特征：n n每一步只能
47、选择出一个节点（每一步只能选择出一个节点（每一步只能选择出一个节点（每一步只能选择出一个节点（S S S S中每次少一个点）中每次少一个点）中每次少一个点）中每次少一个点）n n遇到距离相同的情况，选择经过节点少的点遇到距离相同的情况，选择经过节点少的点遇到距离相同的情况，选择经过节点少的点遇到距离相同的情况，选择经过节点少的点54河海大学电子信息工程系步骤步骤 R2 D2 R3 D3 R4 D4 R5 D5 R6 D(6) N1 1 2 1 5 1 1 4 2 1 2 4 4 1 1 23 1 2 4 4 1 1 4 2 54 1 2 5 3 1 1 4 2 5 4 35 1 2 5 3 1
48、 1 4 2 5 4 6132456122133521555河海大学电子信息工程系13245612213352151324561212156河海大学电子信息工程系D-VD-Vn n通过与邻居的信息交换通过与邻居的信息交换通过与邻居的信息交换通过与邻居的信息交换获得网络拓扑知识获得网络拓扑知识获得网络拓扑知识获得网络拓扑知识n n路由计算是增加路由器路由计算是增加路由器路由计算是增加路由器路由计算是增加路由器之间的站点数（之间的站点数（之间的站点数（之间的站点数（hopshops）n n定期刷新路由：收敛慢定期刷新路由：收敛慢定期刷新路由：收敛慢定期刷新路由：收敛慢n n向相邻站点传送路由表向相
49、邻站点传送路由表向相邻站点传送路由表向相邻站点传送路由表的副本的副本的副本的副本L-SL-Sn n全网获得共同的全局性全网获得共同的全局性全网获得共同的全局性全网获得共同的全局性网络拓扑知识（网络拓扑知识（网络拓扑知识（网络拓扑知识（L-SL-S图）图）图）图）n n计算到达其他站点的最计算到达其他站点的最计算到达其他站点的最计算到达其他站点的最短路径短路径短路径短路径（SPFSPF准则）准则）准则）准则）n n触发刷新：收敛快触发刷新：收敛快触发刷新：收敛快触发刷新：收敛快n n向其他站点发送链路状向其他站点发送链路状向其他站点发送链路状向其他站点发送链路状态的动态变化态的动态变化态的动态变化态的动态变化D-V和L-S算法的比较57河海大学电子信息工程系
