最新-路由算法补充知识-课件.ppt

1、网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14路由技术路由技术 确定路由算法确定路由算法 设计目标设计目标 选择类型选择类型 定义最佳路径的度量准则定义最佳路径的度量准则 实现路由协议实现路由协议 路由传输协议（路由传输协议（Routed Protocol）网间经路由被传输的协议：网间经路由被传输的协议：IP，OSI，Netware 路由选择协议（路由选择协议（Routing Protocol）实现路由选择算法的协议：实现路由选择算法的协议：RIP，OSPF，BGP网络与分布式系统研究室网络与分布式系统研究室(DisNet

2、 Lab of NWU)2023-2-142023-2-141.路由算法需要考虑的基本因素路由算法需要考虑的基本因素1）路由算法的设计目标）路由算法的设计目标2）选择最佳路由的度量参数）选择最佳路由的度量参数网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-141）路由算法的设计目标）路由算法的设计目标 优化：根据一定的优化准则选择最佳路径的能力优化：根据一定的优化准则选择最佳路径的能力 简单：利用最少的物理资源、提供最有效的功能简单：利用最少的物理资源、提供最有效的功能 稳定：经受得住各种恶劣环境的考验，故障率低稳定：经受得住各

3、种恶劣环境的考验，故障率低 收敛：跟随路由更新信息变化重新计算，快速取收敛：跟随路由更新信息变化重新计算，快速取 得全网一致的最佳路由得全网一致的最佳路由 灵活：快速、准确地适应各种网络环境和变化灵活：快速、准确地适应各种网络环境和变化网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-142）选择最佳路由的度量参数）选择最佳路由的度量参数 路径长度路径长度 由网络管理员定义每条网络链路的代价（由网络管理员定义每条网络链路的代价（cost），从源到宿的），从源到宿的代价总和为路径长度。代价总和为路径长度。以路径中的站点（以路径中的站

4、点（hop）为单位，从源到宿的站点数之和为路）为单位，从源到宿的站点数之和为路径长度。径长度。可靠性可靠性链路数据传输的可靠性（误码率）链路数据传输的可靠性（误码率）延迟延迟数据包从源到宿需要花费的传输时间数据包从源到宿需要花费的传输时间 带宽带宽链路的最大传输能力以及网络流量链路的最大传输能力以及网络流量 负载负载网络资源（例如路由器的网络资源（例如路由器的CPU）的使用率）的使用率 通信代价通信代价占用通信线路的费用占用通信线路的费用网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-142.路由选择算法路由选择算法1）缺省路径

5、）缺省路径2）静态路由）静态路由3）动态路由）动态路由距离向量法距离向量法4）动态路由）动态路由链路状态法链路状态法网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-141）缺省路径（）缺省路径（Default Route）什么是缺省路径？什么是缺省路径？对那些在路由表中未包含其路由选择信息的对那些在路由表中未包含其路由选择信息的信宿（网络信宿（网络/主机）设定的缺省路径主机）设定的缺省路径 在路由表中信宿地址取值在路由表中信宿地址取值0.0.0.0(Default)缺省路径的作用缺省路径的作用 对所有自治系统以外的信宿都采用缺省

6、路径对所有自治系统以外的信宿都采用缺省路径 简化路由计算，提高寻径效率，缩短表长简化路由计算，提高寻径效率，缩短表长网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14缺省路径举例网络网络A网络网络DRdb0c0f0e0Default Rd e0Default Rd f0Default Rab0Default Rac0RaRcRbRfRe网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-142）静态路由）静态路由 静态路由的概念静态路由的概念 静态路由工作原理静态路

7、由工作原理 路由配置举例路由配置举例 故障举例（网络拓扑结构变化）故障举例（网络拓扑结构变化）用人工修改配置排除故障用人工修改配置排除故障网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14静态路由的概念静态路由的概念 由网络管理员设置路由表由网络管理员设置路由表 简单、有效，适于结构简单的网络简单、有效，适于结构简单的网络 不适于拓扑结构和传输流量经常改变的不适于拓扑结构和传输流量经常改变的复杂网络复杂网络网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14静态

8、路由举例静态路由举例网络网络A网络网络C网络网络BRa路由表路由表网络网络BRba2网络网络CRca3Rb路由表路由表网络网络ARab3网络网络CRcb2Rc路由表路由表网络网络BRbc2网络网络ARac3a1a3a2c3c2c1b2b3b1RaRbRc网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14链路发生故障链路发生故障网络网络A网络网络C网络网络BRb路由表路由表网络网络ARab3网络网络CRcb2Rc路由表路由表网络网络BRbc2网络网络ARac3a1a3a2c3c2c1b2b3b1?Ra路由表路由表网络网络BRba

9、2网络网络CRca3RaRbRc网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14解决办法：人工修改解决办法：人工修改网络网络A网络网络C网络网络BRb路由表路由表网络网络ARcb2网络网络CRcb2Rc路由表路由表网络网络BRbc2网络网络ARac3a1a3a2c3c2c1b2b3b1！不适于网络变化！不适于网络变化！Ra路由表路由表网络网络BRca3网络网络CRca3RaRbRc网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14静态路由算法静态路由算法洪泛

10、（洪泛（flooding）算法）算法：向着除了进入链路：向着除了进入链路以外的其他链路转发；以外的其他链路转发；随机算法随机算法：随机选择下一跳；：随机选择下一跳；（概率）分流算法（概率）分流算法：按照链路（静态）带宽：按照链路（静态）带宽（速率）选择下一跳（速率）选择下一跳网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-143）距离向量算法）距离向量算法Distance-Vector D-V算法的基本概念算法的基本概念 D-V算法的动态特性算法的动态特性 D-V算法的收敛性问题及其解决办法算法的收敛性问题及其解决办法 D-V算

11、法小结算法小结网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14A路由表路由表距离向量算法的基本概念距离向量算法的基本概念 周期性地相互传递信息周期性地相互传递信息 每个路由器向与它每个路由器向与它相邻的站点相邻的站点发送一个包含它到所有其他路发送一个包含它到所有其他路由器的距离的向量（最短路径或最小代价）由器的距离的向量（最短路径或最小代价）维护各自的路由表维护各自的路由表 路由器根据邻居发送的距离路由器根据邻居发送的距离向量的动态信息启动算法，更向量的动态信息启动算法，更新路由表新路由表DCAB路由表路由表C路由表路由表B

12、网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14D-V路由选择算法举例网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14距离向量法的计算举例距离向量法的计算举例ADECB718221信宿信宿（D,V）到到 A1,A到到 B5,D到到 C4,D到到 D2,D 从从 A 从从 B 从从 D 到到 A 0 7 3 到到 B 7 0 3 到到 C 5 1 2 到到 D 3 3 0 计算从计算从E经相邻站点经相邻站点A、B和和D到达信宿到达信宿A、B、C和和D的最小代

13、价的最小代价D(destination,neighbor)得从得从E到达信宿的最佳路径（最小代价）路由表到达信宿的最佳路径（最小代价）路由表最小代价最小代价D(des,nei)E的路由表的路由表网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14原路由不经过原路由不经过N但距离大但距离大新路由不一定最优，但新路由不一定最优，但，原路由可能故障，原路由可能故障原路为无穷大，则取代为经原路为无穷大，则取代为经N、长度为、长度为C的路由的路由网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2

14、-142023-2-14D-V网络发现过程剖析网络发现过程剖析 1 1ACB40.0.0.0 up时时间间ABC刷刷新新初初始始 信信宿宿不不可可达达40.0.0.0开开启启 0C 发发现现新新网网络络第第 1 步步 10CB,0+1=1第第 2 步步210BA,1+1=2到达信宿到达信宿40.0.0.0的路由变化的路由变化如果网络中的最长路径为如果网络中的最长路径为N，则算法经过，则算法经过N次迭代计算后次迭代计算后收敛。即第收敛。即第N步之后，网上的所有路由器都获得到达信宿步之后，网上的所有路由器都获得到达信宿40.0.0.0的路由信息。的路由信息。网络与分布式系统研究室网络与分布式系统研

15、究室(DisNet Lab of NWU)2023-2-142023-2-14D-V发现链路断开发现链路断开 1 1ACB40.0.0.0 down时时间间ABC刷刷新新初初始始210信信宿宿可可达达40.0.0.0断断开开212BC，1+1=2到达信宿到达信宿40.0.0.0的路由变化的路由变化C与与B之间的对话：之间的对话：C 我得不到信宿我得不到信宿40.0.0.0的任何路由信息，你能告诉我如何到达信宿吗？的任何路由信息，你能告诉我如何到达信宿吗？B 我可以到达信宿，距离为我可以到达信宿，距离为1。（传播了一条过时的错误信息）（传播了一条过时的错误信息）C 既然如此，我选择经过你到达信宿

16、的路径，距离为既然如此，我选择经过你到达信宿的路径，距离为2。网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14距离向量法的收敛性问题及解决办法距离向量法的收敛性问题及解决办法 问题问题 逐站传递更新信息，算法的收敛速度慢逐站传递更新信息，算法的收敛速度慢 有可能出现各站路由信息不一致有可能出现各站路由信息不一致 后果后果 在站点间构成更新路由的路径环（在站点间构成更新路由的路径环（Routing Loops）计数至无穷大（计数至无穷大（Count to Infinity）解决办法解决办法 定义路径代价的最大值（定义路径代价的

17、最大值（Maximum）提高收敛速度提高收敛速度网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14 1 1ACB40.0.0.0 down时时间间ABC刷刷新新初初始始210信信宿宿可可达达40.0.0.0断断开开212BC，1+1=2第第 1 步步232CB，2+1=3第第 2 步步434BC，3+1=4BA，3+1=4到达信宿到达信宿40.0.0.0的路由变化的路由变化路径环（路径环（Routing Loop）问题）问题这条错误的路由信息在这条错误的路由信息在C与与B之间不断复制和修改，之间不断复制和修改，并在网络中传播（

18、殃及并在网络中传播（殃及A），形成路径传播的环路。），形成路径传播的环路。网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14 1 1ACB40.0.0.0 down时时间间ABC刷刷新新初初始始210信信宿宿可可达达40.0.0.0断断开开212BC，1+1=2第第 1 步步232CB，2+1=3第第 2 步步434BA，BC，3+1=4第第 3 步步454CB，4+1=5第第 13 步步141514CB，14+1=15第第 14 步步161516BA，BC，15+1=16 Count to Infinity到达信宿到达信宿4

19、0.0.0.0的路由变化的路由变化严重后果：计数至无穷大严重后果：计数至无穷大网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14 1 1ACB40.0.0.0 down时时间间ABC刷刷新新初初始始210信信宿宿可可达达40.0.0.0断断开开212BC，1+1=2第第 1 步步232CB，2+1=3第第 2 步步434BA，BC，3+1=4第第 3 步步454CB，4+1=5第第 13 步步141514CB，14+1=15第第 14 步步161516BA，BC，15+1=16第第 15 步步不不可可达达16不不可可达达CB，

20、15+1=16第第 16 步步不不可可达达扔扔弃弃到达信宿到达信宿40.0.0.0的路由变化（定义的路由变化（定义Hop最大值为最大值为16）解决办法：定义距离的最大值解决办法：定义距离的最大值收敛！收敛！网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14加速收敛的方法加速收敛的方法 水平分割（水平分割（Split Horizon）毒性逆转（毒性逆转（Poison Reverse）保持计时（保持计时（Hold-Down Timers）触发更新（触发更新（Triggered Updates）加速方法的综合应用举例加速方法的综合应

21、用举例网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14距离向量算法小结距离向量算法小结 路径选择采用最短路径准则，计算路径选择采用最短路径准则，计算D信宿信宿(距离，下站距离，下站)；每个站点只知道自己和邻居的局部信息，在自己的刷新每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算法；周期到来时，根据邻居的路由变化重新启动算法；算法的收敛速度慢（特别是对网络崩溃）造成全网信息算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大；的不一致，导致产生路径环

22、，使计数至无穷大；当路径环产生时，定义距离的最大值可防止算法进入死当路径环产生时，定义距离的最大值可防止算法进入死循环，解决计数至无穷大问题；循环，解决计数至无穷大问题；各种加速收敛方法的目的在于避免路径环的形成，但不各种加速收敛方法的目的在于避免路径环的形成，但不能从根本上杜绝这一现象的发生；能从根本上杜绝这一现象的发生；在具体的路由协议中，各种加速收敛方法往往综合使用。在具体的路由协议中，各种加速收敛方法往往综合使用。网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-144）链路状态（）链路状态（Link-State）算法）算

23、法 L-S算法的基本概念算法的基本概念 L-S算法的动态特性算法的动态特性 L-S算法的性能分析算法的性能分析 L-S算法与算法与 D-V算法的比较算法的比较 OSPF协议协议网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14链路状态算法的基本概念链路状态算法的基本概念 链路状态算法的基本概念链路状态算法的基本概念 链路状态法的计算举例链路状态法的计算举例 Dijkatra算法计算结果算法计算结果网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14 每个路由器周

24、期性地收集和发送信息每个路由器周期性地收集和发送信息 主动测试其到所有邻居的链接状态（度量值）主动测试其到所有邻居的链接状态（度量值）向所有的路由器发送（广播）自己拥有的状态信息向所有的路由器发送（广播）自己拥有的状态信息 得到一个全网的、动态的逻辑链路状态（得到一个全网的、动态的逻辑链路状态（L-S）图）图 每个路由器刷新自己的路由表每个路由器刷新自己的路由表 当当L-S变化时，用最短路径优先变化时，用最短路径优先(SPF)算法重新计算本地路由算法重新计算本地路由DCAB链路状态算法的基本概念链路状态算法的基本概念_路路由由表表SPF算法算法拓扑数据库拓扑数据库（L-S图）图）SPF树树L-

25、S包包网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14AEDCB212113Dijkatra最短路径算法最短路径算法 计算加权无向图（即计算加权无向图（即L-S图）中两个结点之间的最短路径图）中两个结点之间的最短路径 对每结点赋以标注对每结点赋以标注D(v),NP(v)链路状态法的计算举例链路状态法的计算举例F3552其中其中自变量自变量v：无向图中的结点无向图中的结点函数函数D(v)：到目前为止，从源点到目前为止，从源点到结点到结点v的最短路径（边长之和）的最短路径（边长之和）函数函数NP(v)：沿源点到结点：沿源点到结点

26、v的的最短路径中与最短路径中与V相邻的前一结相邻的前一结点点网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14Dijkatra算法计算结果算法计算结果AEDCB212113计计算算BCDEF02,A5,A1,A,-,-12,A4,D2,D,-22,A4,D4,E33,E4,E44,E源点源点A到所有结点的最短路径到所有结点的最短路径F3552DFEABC11212L-S图图SPF树树网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14L-S算法的动态特性算法的动

27、态特性 建立路由表的初始过程建立路由表的初始过程 发现新的网络发现新的网络 路由表的维护路由表的维护 发现拓扑变化发现拓扑变化 修改拓扑数据库修改拓扑数据库 计算计算SPF树树 修改路由表修改路由表网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14ACB10.0.0.040.0.0.030.0.0.020.0.0.0a0 a1b0 b1 c0 c1A 的的路路由由表表10.0.0.0a0020.0.0.0a10L-S建立路由表的初始过程建立路由表的初始过程C 的的路路由由表表30.0.0.0c0040.0.0.0c10B 的的

28、路路由由表表20.0.0.0b0030.0.0.0b10网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14ACB40.0.0.0L-S网络发现过程剖析网络发现过程剖析C发现直连网络发现直连网络30.0.0.0和和40.0.0.0 构造包含发现信息的构造包含发现信息的L-S报文报文(LSP)向全网广播向全网广播 接收全网的其他路由器发来的接收全网的其他路由器发来的L-S报文报文 根据收集的信息建立拓扑数据库根据收集的信息建立拓扑数据库 启动启动SPF算法以算法以C为源点计算为源点计算SPF树树 建立到达所有信宿的路由表（端口和代

29、价）建立到达所有信宿的路由表（端口和代价）c1信信 宿宿端端 口口代代 价价3 0.0.0.0c004 0.0.0.0c10LSP30.0.0.0c0网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14（1）发现拓扑变化）发现拓扑变化AEDCBFNet XNet X DownNet X DownLSPLSP发现网络发现网络X不可达不可达构造构造LSP向全网广播向全网广播发现网络发现网络X不可达不可达构造构造LSP向全网广播向全网广播网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-1

30、42023-2-14（2）修改拓扑数据库）修改拓扑数据库AEDCBFNet X全网具有相同全网具有相同的的L-S逻辑图。逻辑图。网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14AEDCBFNet X（3）各自重新计算）各自重新计算SPF树树2233115ECBFAD52212A的的SPF树树（新）（新）ECBFAD12211A的的SPF树树（旧）（旧）ECFAD32212B的的SPF树树（旧（旧=新）新）BECFAD35211C的的SPF树树BECFAD2211F的的SPF树树B2ECFAD2211E的的SPF树树B2ECF

31、AD22211D的的SPF树树B251网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14AEDCBFNet X根据各自计算的根据各自计算的SPF树刷新路由表树刷新路由表（4）修改各自的路由表）修改各自的路由表a0a1a2Net YA 的的路路由由表表 Net Y a2 1 Net Y a1 4 路路由由表表路路由由表表路路由由表表路路由由表表路路由由表表221网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14L-S算法的性能分析算法的性能分析 优点优点 代价代

32、价 路由刷新问题路由刷新问题 线路传输速率不同线路传输速率不同 网络运行状态不同网络运行状态不同 解决办法解决办法网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14L-S算法的优点算法的优点 所有路由器具有相同的网络拓扑知识（所有路由器具有相同的网络拓扑知识（L-S图）图）一次性、无修改地向全网广播一次性、无修改地向全网广播LSP 路由器根据全局信息维护各自的路由表路由器根据全局信息维护各自的路由表 保证链路状态信息的单向传播保证链路状态信息的单向传播 保证算法的收敛性保证算法的收敛性网络与分布式系统研究室网络与分布式系统研究

33、室(DisNet Lab of NWU)2023-2-142023-2-14AEDCBFL-S算法的代价算法的代价 SPF算法计算和拓扑数算法计算和拓扑数据库需要更多的据库需要更多的CPU和和内存资源内存资源 网络启动时的扩散路由网络启动时的扩散路由信息（信息（flood）需要占用）需要占用很多带宽资源很多带宽资源网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14AEDCBFNet X DownNet X upNet X upNet X Down慢慢快快慢慢线路传输速率不同产生的影响线路传输速率不同产生的影响E应该选择哪棵应该

34、选择哪棵SPF树？树？Net X DownNet X upNet X Down来自来自D来自来自A慢慢Net XE收到的收到的LSPECFAD2211E的的SPF树树NetX downB2ECFAD1211E的的SPF树树NetX upB2开始开始 Net X down后来后来 Net Xup网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14AEDCBF网络已经启动部分网络已经启动部分网络尚未启动部分网络尚未启动部分 网络的一部分已经网络的一部分已经启动，而另一部分启动，而另一部分正待启动正待启动 网络的一部分刷新网络的一部分

35、刷新速度快，而另一部速度快，而另一部分刷新速度慢分刷新速度慢 造成网络的不同部造成网络的不同部分拥有不同的分拥有不同的L-S图图网络运行状态不同产生的影响网络运行状态不同产生的影响网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14L-S对问题的解决办法对问题的解决办法 减少对资源的需求减少对资源的需求 尽可能降低路由刷新频度尽可能降低路由刷新频度 用用Multicast取代取代Broadcast(flood)将网络拓扑结构划分为不同层次和区域将网络拓扑结构划分为不同层次和区域 在层次间和区域交接处交换路由信息在层次间和区域交接

36、处交换路由信息 协调协调L-S刷新刷新 对对LSP加时间戳标识加时间戳标识 对对LSP加序列号标识加序列号标识 用分级路由管理网络的逻辑分组用分级路由管理网络的逻辑分组网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14D-V和和L-S算法的比较算法的比较D-V 通过与邻居的信息交换通过与邻居的信息交换获得网络拓扑知识获得网络拓扑知识 路由计算是增加路由器路由计算是增加路由器之间的站点数（之间的站点数（hops）定期刷新路由：收敛慢定期刷新路由：收敛慢 向相邻站点传送路由表向相邻站点传送路由表的副本的副本L-S 全网获得共同的全

37、局性全网获得共同的全局性网络拓扑知识（网络拓扑知识（L-S图）图）计算到达其他站点的最计算到达其他站点的最短路径（短路径（SPF准则）准则）触发刷新：收敛快触发刷新：收敛快 向其他站点发送链路状向其他站点发送链路状态的动态变化态的动态变化网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14思考题思考题 如果路由表包含全部到达信宿的路径信如果路由表包含全部到达信宿的路径信息显然有助于作出最优选择，是否可行？息显然有助于作出最优选择，是否可行？会带来什么问题？会带来什么问题？如果路由表只包含相邻站点的路由信息，如果路由表只包含相邻站

38、点的路由信息，有何优缺点，能否保证得到全局最优解？有何优缺点，能否保证得到全局最优解？指出默认路由的作用。指出默认路由的作用。指出静态路由与动态路由的区别。指出静态路由与动态路由的区别。如何解决如何解决D-V算法和算法和L-S算法的问题？算法的问题？网络与分布式系统研究室网络与分布式系统研究室(DisNet Lab of NWU)2023-2-142023-2-14 对如图所示的网络采用对如图所示的网络采用D-V水平分割法计算路水平分割法计算路由，能否避免产生路径环？由，能否避免产生路径环？从以下几方面描述从以下几方面描述D-V的工作原理的工作原理 如何传播路由更新信息如何传播路由更新信息 什么样的知识需要被传播什么样的知识需要被传播 什么时候传播这样的知识什么时候传播这样的知识 怎样存放路由更新信息怎样存放路由更新信息思考题（续）思考题（续）DBCA断开断开