路由原理与技术第2章IP路由基础课件

第二章IP路由基础北京邮电大学网络技术研究院下一代互联网技术研究中心第二章IP路由基础北京邮电大学本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构现有信息网络基本上都采用了分层的体系结构，即将其协议体系划分为若干个层次，每个层次完成特定的功能，这样，各个层次综合在一起，就可以完成一个完整的系统功能。现有信息网络基本上都采用了分层的体系结构，即将其协议体系划分子网层一般又称网络接口层，负责从网络层接收IP报文并向物理网络发送，或从网络上接收物理帧，取出IP数据报并提交给网络层。网络层负责处理分组在网络中的活动，提供跨越多个网络的选路功能，并对上层屏蔽底层具体子网技术的细节。传输层主要为两台主机上的应用程序提供端到端的通信。在IP网络中，有两个传输协议：TCP（TransmissionControlProtocol，传输控制协议）和UDP（UserDatagramProtocol，用户数据报协议）。应用层处理特定应用程序细节，为用户完成各种网络服务。子网层一般又称网络接口层，负责从网络层接收IP报文并向物理网本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构路由器路由器是工作在网络层上，可以连接不同类型的网络，能够选择数据传送路径并对数据进行转发的网络设备。从通信的角度看，路由器是一种中继系统。

路由器路由表路由器在接收到数据时，要对其传输路径进行选择。为了实现这一目标，路由器需要维护一个称为“路由表”的数据结构。路由表包含若干条目，供路由器选路时查询数据传输路径。路由表中的一个条目至少要包含：数据的目的地址（通常是目的主机所在网络的地址）下一跳路由器（即从本路由器出发按所给路径到给定目的地所要通过的下一个路由器）的地址相应的网络接口一般情况下还应该有标志位等内容。

路由表泛洪（Flooding）源路由泛洪（Flooding）选路策略和选路机制选路策略（RoutingPolicy）：根据数据包的目的地和网络的拓扑结构选择一条最佳路径，把对应不同目的地的最佳路径存放在路由表中；选路机制（RoutingMechanism）：搜索路由表，决定向哪个接口转发数据，并执行相应的操作；选路策略只影响路由表的内容，比如对同一个目的地址来说，由于选路策略的不同，最佳路径可能会不一样，但这并不影响选路机制的执行过程，只是会对其执行的结果产生影响。选路策略和选路机制IP网络地址结构指IP地址（包括IPv4和IPv6）的编址方式。通常把地址空间分为网络号和主机号两部分，当路由器在进行路径选择时，一般按照目的网络来查询，这样既可以降低路由表规模，也可以提高路由查询效率。早期IPv4网络把地址分为A、B、C、D、E五类，浪费了大量的地址空间，并造成路由效率低下。为解决这些问题，出现了CIDR（ClasslessInterDomainRouting，无类别域间路由）机制，即不再严格的对IP地址类别进行区分，IP地址网络号长度也不再固定。IPv6地址的编址方式与CIDR类似，也是不限定网络号空间的长度，因此有很强的灵活性。IP网络地址结构对路由选择和路由查询都有很大的影响。

IP网络地址结构自治系统和路由域由于Internet规模太大，分布范围太广，所以路由表中对应每一个目的网络都有一个条目是不可能的；同样，也不可能采用一个全局的路由算法或协议。因此，Internet将整个网络划分为若干个相对自治的局部系统，即自治系统（AS，AutonomousSystem）。自治系统可以定义为同一机构下管理的路由器和网络的集合。一个自治系统内部还可以再划分几个小的路由域，也称作区域。

自治系统和路由域内部网关协议和外部网关协议

路由协议可以分为内部网关协议（IGP，InteriorGatewayProtocol）和外部网关协议（EGP，ExteriorGatewayProtocol）两大类。内部网关协议是用于自治系统内部的动态路由协议RIP（RoutingInformationProtocol，路由信息协议）OSPF（OpenShortestPathFirst，开放最短路径优先）；外部网关协议是用于自治系统之间拓扑信息交换的路由协议BGP（BorderGatewayRoutingProtocol，边界网关路由协议）。内部网关协议和外部网关协议路由选择算法路由算法是指路由器获得对网络拓扑结构的认知，并为数据包选择正确传输路径的方法或者策略。一个理想的路由算法至少应该具备以下几点特征：①完整性和正确性；②简单性；③健壮性；④公平性；⑤最佳性。路由算法的分类。路由选择算法静态路由选择和动态路由选择按照能否自动适应网络拓扑结构的变化，可以将选路策略分为静态路由选择和动态路由选择两大类。静态路由选择并不是表示路由表一成不变，只是说明路由器不是通过彼此之间动态交换路由信息来建立和更新路由表的。动态路由选择是通过网络中路由器间的相互通信来传递路由信息，利用接收到的路由信息自动更新路由表。静态路由选择和动态路由选择距离矢量路由选择协议和链路状态路由选择协议距离矢量路由选择协议基于距离矢量路由算法。其基本思想是路由器周期地和相邻路由器交换路由表中的信息。这种信息是由若干（V，D）对组成的表项，其中，V代表矢量，指出该路由器可以达到的目的地；D表示去往目标V的距离。各个路由器根据收到的信息重新计算到各目的节点的距离，对自己的路由表进行修正。链路状态路由选择协议也被称为最短路径优先协议，它基于链路状态路由算法。采用这种协议的路由器都要维护一张可以表示整个网络拓扑结构的无向图G（V，E），在图G中，节点V表示路由器，边E表示连接路由器的链路，因此G又可以称为L-S（链路-状态）图，各路由器的路由表通过L-S图计算。距离矢量路由选择协议和链路状态路由选择协议本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构IPv6协议体系IPv6基本协议栈：IPv6、ICMPv6（InternetControlMessagesProtocolversion6，因特网控制报文协议版本6）、ND（NeighborDiscoveryProtocol，邻居发现协议）等传输层协议：TCP/UDP路由协议：RIPng、OSPFv3、BGP4+网络管理协议SNMP（SimpleNetworkManagementProtocol，简单网络管理协议）、安全协议IPSec（IPsecurity，IP安全）应用层协议IPv6协议体系IPv6基本协议栈：IPv6、ICMPv6（IPv6地址分类IPv6地址可以分为单播地址、多播地址和任播地址三类。单播地址：仅标识一个接口，相当于传统的点对点地址多播地址：用于标识一组接口，发给多播地址的报文通常要发给该组的所有成员任播地址：也用于标识一组接口，但发给任播地址的报文只发给其中的一个，通常是最近（根据路由的度量）一个IPv6地址分类IPv6地址可以分为单播地址、多播地址和任播IPv6地址的表示IPv6的128位（即16个字节）地址写成8个16位无符号整数，每个整数用4位十六进制数来表示，这些数之间用冒号(:)分开，例如：AEDC:FA20:7484:32B0:AEFC:BC91:2645:3214形如ABCD:0000:0000:0000:0008:0800:800C:417C的可以简化为ABCD::0008:0800:800C:417C简化只可以用一次。IPv6地址的表示IPv6的128位（即16个字节）地址写成IPv6地址分配IPv4映射的IPv6地址

IPv4兼容的IPv6地址

回环地址::1(即0000……0001)0000……0000FFFFIPv4地址

80位0000……00000000IPv4地址

80位

16位

16位

32位

32位

127个0IPv6地址分配IPv4映射的IPv6地址0000…IPv6地址分配（续）本地链路单播地址

本地网点单播地址

11111110100000……0000接口ID

54位11111110110000……0000子网ID接口ID

64位

10位

64位

16位

38位

10位IPv6地址分配（续）本地链路单播地址111111101IPv6地址分配（续）单播地址64位接口ID应符合IEEEEUI-64的格式。可聚集全局单播地址的格式如下：多播地址常见的多播地址：

FF02::1所有节点地址FF02::2所有路由器地址FF02::5OSPF路由器FF02::6OSPF指派路由器FF02::9RIP路由器001全球路由前缀子网ID接口ID3位

45位

16位

64位IPv6地址分配（续）单播地址001全球路由前缀子网ID接口IPv6地址的自动配置一个接口一旦被初始化，主机就可以为该接口建立一个链路局部地址，接口ID符合IEEEEUI-64标准。无状态自动配置一个IPv6节点启动时，要加入“所有节点”多播组；向“所有路由器”多播组发送请求报文，源地址是其链路局部地址；路由器收到这样一个报文后，就回应一个应答报文，通告自己的前缀。有状态自动配置利用DHCP配置主机地址。IPv6地址的自动配置一个接口一旦被初始化，主机就可以为该接从IPv4过渡到IPv6

在从IPv4过渡到IPv6的过程中，为保证IPv6节点和IPv4节点之间的互通，主要有以下几种技术：双协议栈技术隧道技术网络地址转换技术其他：SOCKS64、应用层网关、传输层中继、主动网络从IPv4过渡到IPv6在从IPv4过渡到本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构路由转发原理处理器内存接口1接口2接口n…查询路由表路由转发原理处理器内存接口1接口2接口n…本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构距离矢量路由算法

（1）各路由器对自己的路由表进行初始化，把与自己直接相连网络的距离设为0（在某些具体实现中也设为1，这只是一个初始值设定的问题），然后周期性地向外广播其路由表的内容。（2）路由器Ri收到相邻路由器Rj的距离矢量信息后，对自己的路由表进行修正。①若Rj的距离矢量信息中所包含的目的节点va在Ri的路由表中没有，则在Ri的路由表中增加一个目的节点为va的条目，令dia=dja+1，并把到节点va的下一跳路由器设为Rj。距离矢量路由算法（1）各路由器对自己的路由表进行初始化，把②若到Rj目的节点vb的路由比Ri到目的节点vb的路由短，则令dib=djb+1，并把到节点vb的下一跳路由器设为Rj。③Ri到目的节点vc最短路径上的下一跳是Rj。如果Rj的路由表中不再包含到的vc路由，则在Ri中也应该把去往vc的路由删掉；如果Rj到vc的距离发生了变化，则Ri修改路由表中到vc的距离，令dic=djc+1。②若到Rj目的节点vb的路由比Ri到目的节点vb的路由短，则距离矢量路由算法在理论上是可以正常工作的，但在实际中存在着一个严重的缺陷：尽管它可以收敛到正确的路由，但它对好消息传播的快，而对坏消息则传播的慢。总的来说，距离矢量路由选择协议的优点是易于实现，但难以适应网络拓扑的剧烈变动或者大型的网络环境。距离矢量路由算法在理论上是可以正常工作的，但在实际中存在着一链路状态路由算法

链路状态路由算法的基本步骤如下：（1）每一个路由器（节点）启动后，首先执行对相邻节点的发现工作，并获取它们的地址。（2）各路由器主动测试到每一个相邻路由器的链路时延或成本，并根据测试结果设置相关链路的状态。链路状态路由算法链路状态路由算法的基本步骤如下：（3）各路由器构造自己的L-S（Link-State，链路状态）信息包，L-S信息的内容包括本路由器的标号、本路由器的邻居路由器列表、本路由器到各邻居路由器的链路状态（时延或成本）、该L-S信息包的序号和生存时间等。（4）各路由器向所有参与链路状态交互的路由器广播其L-S信息，可以是周期性地发送，也可在链路状态发生变化时发送。（5）每个路由器在收到所有的L-S信息后，可以构造或更新表示整个网络拓扑结构的图G（V，E），顶点V表示路由器，边E表示连接路由器的链路；这时路由器就可以用Dijkstra算法从图G中计算出到所有目的路由器的最短路径，也就是构造以自己为根节点的SPF树。（3）各路由器构造自己的L-S（Link-State，链路状Dijkstra算法简介

设目的节点（就构造SPF树而言，是根节点）为k，任一条链路（i，j）的长度为dij，每个节点到k的最短路径长度估计为Dik；定义所有节点的集合为A，定义集合P∈A，并设定集合的初始值为P={k}。在算法迭代的过程中，如果Dik已经变成一个确定值，则将i标记为固定点，并将其加入集合P。在算法的每一步迭代中，在P以外的节点中，选择与目的节点k最近的节点加入到P中，算法的具体步骤如下：Dijkstra算法简介设目的节点（就构Dijkstra算法简介（1）P={k},

Dkk=0，Djk=djk（若j和k不相邻，）（2）求解使成立的i，，即寻找下一个和目的节点最近的节点；令，若P=A，算法结束。（3）对所有，置，返回步骤（2）Dijkstra算法简介（1）P={k},Dkk=0，Dj路由原理与技术第2章IP路由基础课件路由原理与技术第2章IP路由基础课件本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构集中式单（多）CPU+总线结构集中式单（多）CPU+总线结构缺陷CPU要负责整体系统的控制管理、路由计算和数据转发等各项功能，存在计算瓶颈。所有接口卡的数据都要争用总线，存在数据交换瓶颈。缺陷分布式多CPU+总线结构分布式多CPU+总线结构特点路由计算和转发分离：主控CPU负责整个系统的控制管理和路由计算（即运行路由协议，维护和更新路由表）；线卡上的CPU负责查询路由表，对数据进行转发。部分地克服了总线瓶颈，即如果数据的接收和发送都在一个线卡上，就不用争用总线；若数据的接收和发送涉及不同的线卡，还是会出现总线争用问题。特点分布式多CPU+Crossbar结构分布式多CPU+Crossbar结构特点路由计算和转发分离。采用Crossbar的交换结构（SwitchFabric），每个输入端口和输出端口之间都有一个交叉开关，只要数据流彼此不相关，就可以实现无阻塞的交换，解决了总线争用问题。基本上解决了路由器吞吐量的问题。交叉开关的设计和调度算法是研究的重点和难点。特点路由器硬件体系结构发展总结共享总线→交叉开关路由计算与转发分离路由器硬件体系结构发展总结个人观点供参考，欢迎讨论！个人观点供参考，欢迎讨论！第二章IP路由基础北京邮电大学网络技术研究院下一代互联网技术研究中心第二章IP路由基础北京邮电大学本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构现有信息网络基本上都采用了分层的体系结构，即将其协议体系划分为若干个层次，每个层次完成特定的功能，这样，各个层次综合在一起，就可以完成一个完整的系统功能。现有信息网络基本上都采用了分层的体系结构，即将其协议体系划分子网层一般又称网络接口层，负责从网络层接收IP报文并向物理网络发送，或从网络上接收物理帧，取出IP数据报并提交给网络层。网络层负责处理分组在网络中的活动，提供跨越多个网络的选路功能，并对上层屏蔽底层具体子网技术的细节。传输层主要为两台主机上的应用程序提供端到端的通信。在IP网络中，有两个传输协议：TCP（TransmissionControlProtocol，传输控制协议）和UDP（UserDatagramProtocol，用户数据报协议）。应用层处理特定应用程序细节，为用户完成各种网络服务。子网层一般又称网络接口层，负责从网络层接收IP报文并向物理网本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构路由器路由器是工作在网络层上，可以连接不同类型的网络，能够选择数据传送路径并对数据进行转发的网络设备。从通信的角度看，路由器是一种中继系统。

路由器路由表路由器在接收到数据时，要对其传输路径进行选择。为了实现这一目标，路由器需要维护一个称为“路由表”的数据结构。路由表包含若干条目，供路由器选路时查询数据传输路径。路由表中的一个条目至少要包含：数据的目的地址（通常是目的主机所在网络的地址）下一跳路由器（即从本路由器出发按所给路径到给定目的地所要通过的下一个路由器）的地址相应的网络接口一般情况下还应该有标志位等内容。

路由表泛洪（Flooding）源路由泛洪（Flooding）选路策略和选路机制选路策略（RoutingPolicy）：根据数据包的目的地和网络的拓扑结构选择一条最佳路径，把对应不同目的地的最佳路径存放在路由表中；选路机制（RoutingMechanism）：搜索路由表，决定向哪个接口转发数据，并执行相应的操作；选路策略只影响路由表的内容，比如对同一个目的地址来说，由于选路策略的不同，最佳路径可能会不一样，但这并不影响选路机制的执行过程，只是会对其执行的结果产生影响。选路策略和选路机制IP网络地址结构指IP地址（包括IPv4和IPv6）的编址方式。通常把地址空间分为网络号和主机号两部分，当路由器在进行路径选择时，一般按照目的网络来查询，这样既可以降低路由表规模，也可以提高路由查询效率。早期IPv4网络把地址分为A、B、C、D、E五类，浪费了大量的地址空间，并造成路由效率低下。为解决这些问题，出现了CIDR（ClasslessInterDomainRouting，无类别域间路由）机制，即不再严格的对IP地址类别进行区分，IP地址网络号长度也不再固定。IPv6地址的编址方式与CIDR类似，也是不限定网络号空间的长度，因此有很强的灵活性。IP网络地址结构对路由选择和路由查询都有很大的影响。

IP网络地址结构自治系统和路由域由于Internet规模太大，分布范围太广，所以路由表中对应每一个目的网络都有一个条目是不可能的；同样，也不可能采用一个全局的路由算法或协议。因此，Internet将整个网络划分为若干个相对自治的局部系统，即自治系统（AS，AutonomousSystem）。自治系统可以定义为同一机构下管理的路由器和网络的集合。一个自治系统内部还可以再划分几个小的路由域，也称作区域。

自治系统和路由域内部网关协议和外部网关协议

路由协议可以分为内部网关协议（IGP，InteriorGatewayProtocol）和外部网关协议（EGP，ExteriorGatewayProtocol）两大类。内部网关协议是用于自治系统内部的动态路由协议RIP（RoutingInformationProtocol，路由信息协议）OSPF（OpenShortestPathFirst，开放最短路径优先）；外部网关协议是用于自治系统之间拓扑信息交换的路由协议BGP（BorderGatewayRoutingProtocol，边界网关路由协议）。内部网关协议和外部网关协议路由选择算法路由算法是指路由器获得对网络拓扑结构的认知，并为数据包选择正确传输路径的方法或者策略。一个理想的路由算法至少应该具备以下几点特征：①完整性和正确性；②简单性；③健壮性；④公平性；⑤最佳性。路由算法的分类。路由选择算法静态路由选择和动态路由选择按照能否自动适应网络拓扑结构的变化，可以将选路策略分为静态路由选择和动态路由选择两大类。静态路由选择并不是表示路由表一成不变，只是说明路由器不是通过彼此之间动态交换路由信息来建立和更新路由表的。动态路由选择是通过网络中路由器间的相互通信来传递路由信息，利用接收到的路由信息自动更新路由表。静态路由选择和动态路由选择距离矢量路由选择协议和链路状态路由选择协议距离矢量路由选择协议基于距离矢量路由算法。其基本思想是路由器周期地和相邻路由器交换路由表中的信息。这种信息是由若干（V，D）对组成的表项，其中，V代表矢量，指出该路由器可以达到的目的地；D表示去往目标V的距离。各个路由器根据收到的信息重新计算到各目的节点的距离，对自己的路由表进行修正。链路状态路由选择协议也被称为最短路径优先协议，它基于链路状态路由算法。采用这种协议的路由器都要维护一张可以表示整个网络拓扑结构的无向图G（V，E），在图G中，节点V表示路由器，边E表示连接路由器的链路，因此G又可以称为L-S（链路-状态）图，各路由器的路由表通过L-S图计算。距离矢量路由选择协议和链路状态路由选择协议本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构IPv6协议体系IPv6基本协议栈：IPv6、ICMPv6（InternetControlMessagesProtocolversion6，因特网控制报文协议版本6）、ND（NeighborDiscoveryProtocol，邻居发现协议）等传输层协议：TCP/UDP路由协议：RIPng、OSPFv3、BGP4+网络管理协议SNMP（SimpleNetworkManagementProtocol，简单网络管理协议）、安全协议IPSec（IPsecurity，IP安全）应用层协议IPv6协议体系IPv6基本协议栈：IPv6、ICMPv6（IPv6地址分类IPv6地址可以分为单播地址、多播地址和任播地址三类。单播地址：仅标识一个接口，相当于传统的点对点地址多播地址：用于标识一组接口，发给多播地址的报文通常要发给该组的所有成员任播地址：也用于标识一组接口，但发给任播地址的报文只发给其中的一个，通常是最近（根据路由的度量）一个IPv6地址分类IPv6地址可以分为单播地址、多播地址和任播IPv6地址的表示IPv6的128位（即16个字节）地址写成8个16位无符号整数，每个整数用4位十六进制数来表示，这些数之间用冒号(:)分开，例如：AEDC:FA20:7484:32B0:AEFC:BC91:2645:3214形如ABCD:0000:0000:0000:0008:0800:800C:417C的可以简化为ABCD::0008:0800:800C:417C简化只可以用一次。IPv6地址的表示IPv6的128位（即16个字节）地址写成IPv6地址分配IPv4映射的IPv6地址

IPv4兼容的IPv6地址

回环地址::1(即0000……0001)0000……0000FFFFIPv4地址

80位0000……00000000IPv4地址

80位

16位

16位

32位

32位

127个0IPv6地址分配IPv4映射的IPv6地址0000…IPv6地址分配（续）本地链路单播地址

本地网点单播地址

11111110100000……0000接口ID

54位11111110110000……0000子网ID接口ID

64位

10位

64位

16位

38位

10位IPv6地址分配（续）本地链路单播地址111111101IPv6地址分配（续）单播地址64位接口ID应符合IEEEEUI-64的格式。可聚集全局单播地址的格式如下：多播地址常见的多播地址：

FF02::1所有节点地址FF02::2所有路由器地址FF02::5OSPF路由器FF02::6OSPF指派路由器FF02::9RIP路由器001全球路由前缀子网ID接口ID3位

45位

16位

64位IPv6地址分配（续）单播地址001全球路由前缀子网ID接口IPv6地址的自动配置一个接口一旦被初始化，主机就可以为该接口建立一个链路局部地址，接口ID符合IEEEEUI-64标准。无状态自动配置一个IPv6节点启动时，要加入“所有节点”多播组；向“所有路由器”多播组发送请求报文，源地址是其链路局部地址；路由器收到这样一个报文后，就回应一个应答报文，通告自己的前缀。有状态自动配置利用DHCP配置主机地址。IPv6地址的自动配置一个接口一旦被初始化，主机就可以为该接从IPv4过渡到IPv6

在从IPv4过渡到IPv6的过程中，为保证IPv6节点和IPv4节点之间的互通，主要有以下几种技术：双协议栈技术隧道技术网络地址转换技术其他：SOCKS64、应用层网关、传输层中继、主动网络从IPv4过渡到IPv6在从IPv4过渡到本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构路由转发原理处理器内存接口1接口2接口n…查询路由表路由转发原理处理器内存接口1接口2接口n…本章提纲互联网的体系结构IP路由中的基本概念IPv6协议体系及地址结构路由转发原理路由选择算法路由器硬件体系结构本章提纲互联网的体系结构距离矢量路由算法

（1）各路由器对自己的路由表进行初始化，把与自己直接相连网络的距离设为0（在某些具体实现中也设为1，这只是一个初始值设定的问题），然后周期性地向外广播其路由表的内容。（2）路由器Ri收到相邻路由器Rj的距离矢量信息后，对自己的路由表进行修正。①若Rj的距离矢量信息中所包含的目的节点va在Ri的路由表中没有，则在Ri的路由表中增加一个目的节点为va的条目，令dia=dja+1，并把到节点va的下一跳路由器设为Rj。距离矢量路由算法（1）各路由器对自己的路由表进行初始化，把②若到Rj目的节点vb的路由比Ri到目的节点vb的路由短，则令dib=djb+1，并把到节点vb的下一跳路由器设为Rj。③Ri到目的节点vc最短路径上的下一跳是Rj。如果Rj的路由表中不再包含到的vc路由，则在Ri中也应该把去往vc的路由删掉；如果Rj到vc的距离发生了变化，则Ri修改路由表中到vc的距离，令dic=djc+1。②若到Rj目的节点vb的路由比Ri到目的节点vb的路由短，则距离矢量路由算法在理论上是可以正常工作的，但在实际中存在着一个严重的缺陷：尽管它可以收敛到正确的路由，但它对好消息传播的快，而对坏消息则传播的慢。总的来说，距离矢量路由选择协议的优点是易于实现，但难以适应网络拓扑的剧烈变动或者大型的网络环境。距离矢量路由算法在理论上是可以正常工作的，但在实际中存在着一链路状态路由算法

链路状态路由算法的基本步骤如下：（1）每一个路由器（节点）启动后，首先执行对相邻节点的发现工作，并获取它们的地址。（2）各路由器主动测试到每一个相邻路由器的链路时延或成本，并根据测试结果设置相关链路的状态。链路状态路由算法链路状态路由算法的基本步骤如下：（3）各路由器构造自己的L-S（Link-State，链路状态）信息包，L-S信息的内容包括本路由器的标号、本路由器的邻居路由器列表、本路由器到各邻居路由器的链路状态（时延或成本）、该L-S信息包的序号和生存时间等。（4）各路由器向所有参与链路状态交互的路由器广播其L