ls路由算法

㈠ 配置缺省路由

缺省路由：路由算法有动静之分，静态路由是一种特殊的路由，它是由管理员手工设定的。手工配置所有的路由虽然可以使网络正常运转，但是也会带来一些局限性。网络拓扑发生变化之后，静态路由不会自动改变，必须有网络管理员的介入。
缺省路由是静态路由的一种，也是由管理员设置的。在没有找到目标网络的路由表项时，路由器将信息发送到缺省路由器。而动态的算法，顾名思义，是由路由器自动计算出的路由，常说的RIP、OSPF等都是动态算法的典型代表。
另外，还可以将路由算法分为DV和LS两种。DV（Distance Vector，距离向量）算法将当前路由器的路由信息传送给相邻路由器，相邻路由器将这些信息加入自身的路由表。而LS（Link State，链路状态）算法将链路状态信息传给域内所有的路由器，接收路由器利用这些信息构建网络拓扑图，并利用图论中的最短路径优先算法决定路由。

㈡ 广域网中路由器选择策略有两大类

广域网中路由器选择策略有两大类

一、基于静态路由的路由器选择策略：

1、最短路径优先（Shortest Path First，SPF）：按照路由表中路径的最猜迟少跳数，选择最短路径作为数据传输路径；

2、最少跳数优先（Least Hop Count，LHC）：在所有可行路径中，选择跳数最少的路径作为数据传输路径；

3、最小延迟优先（Least Delay）：通过测量每条路径的延迟，从中选择延迟最小的路径作为数据传输路径纳兆棚；

4、最小带宽优先（Least Bandwidth）：选择带宽最小的路径作为数据传输路径，以提高网络的性能。

二、基于动态路由的路由器选择策略：

1、距离向量算法（Distance Vector Algorithm，DV）：采用距离向量算法，路由器每隔一段时间，就会向相邻路由器发送一个包，该包包含路由器自身和相邻路由器的距离信息，根据这些信息洞则，路由器可以计算出到达目的地的最短路径；

2、链路状态算法（Link State Algorithm，LS）：采用链路状态算法，路由器会不断地收集周围路由器的信息，并将这些信息发送给所有路由器，根据这些信息，每台路由器都可以计算出最短路径。

㈢ 路由算法的分级路由

可以看到，在LS和DV算法中，每个路由器都需要保存其他路由器的一些信息。随着网络规模的扩大，网络中的路由器也将增加。因此，路由表的规模也将增大，从而使路由器不能有效地处理网络流量。使用分级路由可以解决这个问题。让使用DV算法来查找节点间的最佳路由。
在下述情形中，网络中的每个节点保存了一个有17个记录的路由表。在分级路由中，路由器被分成很多组，称为区域。每个路由器都只有自己所在区域路由器的信息，而没有其他区域路由器的信息。所以在其路由表中，路由器只需要存储其他每个区域的一条记录。在这个例子中，我们将网络分为5个区域。
如果A想发送分组数据包到在区域2中的一个路由器（D、E、F或G），它就将分组数据包先发送到B，依此类推。可以看到，在这种类型的路由中，可以对路由表进行概括，因此网络效率提高了。上面的例子描述了一个两级的分级路由。同样我们也可以采用三级或者四级的分级路由。
在一个三级的分级路由中，网络被分为很多簇。每个簇由很多个区域组成，每个区域包含很多个路由器。分级路由广泛应用于互联网路由中，并且使用了多种路由协议。

㈣ 路由算法的主要目的

路脊搏由器使用路由算法来找到到达目的地的最佳路由。当说“最佳路由”时，考虑的参数包括诸如跳跃数（分组数据包在网络中从一个路由器或中间节点到另外的节点的行程）、延时以及分组数据包传输通信耗时。关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法：
总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——早态而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。采用总体式路由陆野源算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。

㈤ 《计算机网络-自顶向下方法》第四章-网络层 要点

网络层的作用：实现主机到主机的通信服务，将分组从一台发送主机移动到一台接收主机。

1、转发涉及分组在单一的路由器中从一条入链路到一条出链路的传送。
2、路由选择涉及一个网络的所有路由器，它们经路由选择协议共同交互，以决定分组从源到目的地结点所采用的路径。计算这些路径的算法称为路由选择算法。

每台路由器都有一张转发表，路由器通过检查到达分组首部字段的值来转发分组，然后使用该值在该路由器的转发表中索引查找。路由选择算法决定了插入路由器转发表中的值。

路由选择算法可能是集中式的，或者是分布式的。但在这两种情况下，都是路由器接收路由选择协议报文，该信息被用于配置其转发表。

网络层也能在两台主机之间提供无连接服务或连接服务。同在运输层的面向连接服务和无连接服务类似，连接服务需要握手步骤，无连接服务不需要握手。但它们之间也有差异：
1、 在网络层中，这些服务是由网络层向运输层提供的主机到主机的服务。在运输层中，这些服务则是运输层向应用层提供的进程到进程的服务。
2、 在网络层提供无连接服务的计算机网络称为数据报网络；在网络层提供连接服务的计算机网络称为虚电路网络。
3、 在运输层实现面向连接的服务与在网络层实现连接服务是根本不同的。运输层面向连接服务是在位于网络边缘的端系统中实现的；网络层连接服务除了在端系统中，也在位于网络核心的路由器中实现。（原因很简单：端系统和路由器都有网络层）

虚电路网络和数据报网络是计算机网络的两种基本类型。在作出转发决定时，它们使用了非常不同的信息。

IP地址有32比特，如果路由器转发表采用“蛮力实现”将对每个可能的目的地址有一个表项。因为有超过40亿个可能的地址，这种选择完全不可能（即使用二分查找也十分慢）。
我们转发表的表项可以设计为几个表项，每个表项匹配一定范围的目的地址，比如有四个表项

（你可能也会考虑到，IP地址有32比特，如果每个路由器设计为只有2个表项，那么也只需要有32个路由器就可以唯一确定这40亿个地址中的一个。）

最长前缀匹配规则，是在转发表中寻找最长的匹配项，并向与最长前缀匹配相关联的链路接口转发分组。这种规则是为了与因特网的编址规则相适应。

1、输入端口
“使用转发表查找输出端口”是输入端口最重要的操作（当然还有其他一些操作）。输入端口执行完这些所需的操作后，就把该分组发送进入交换结构。如果来自其他输入端口的分组当前正在使用交换结构，一个分组可能会在进入交换结构时被暂时阻塞，在输入端口处排队，并等待稍后被及时调度以通过交换结构。
2、交换结构
交换结构的三种实现方式

3、输出端口
分组调度程序 处理在输出端口中排队的分组
4、路由选择处理器

</br>

</br>

IP协议版本4，简称为IPv4；IP协议版本6，简称为IPv6。

如上图所示，网络层有三个主要的组件
1、IP协议
2、路由选择协议
3、ICMP协议 (Internet Control Message Protocol, 因特网控制报文协议)

</br>

不是所有链路层协议都能承载相同长度的网络层分组。有的协议能承载大数据报，而有的协议只能承载小分组。例如，以太网帧能够承载不超过1500字节的数据，而某些广域网链路的帧可承载不超过576字节的数据。

一个链路层帧能承载的最大数据量叫做最大传送单元(Maximun Transmission Unit, MTU)

所以链路层协议的MTU严格限制着IP数据报的长度。这也还不是主要的问题，问题在于发送方与目的地路径上的每段链路可能使用不同的链路层协议，且每种协议可能具有不同的MTU。

举个例子：假定从某条链路收到一个IP数据报，通过检查转发表确定出链路，并且该出链路的MTU比该IP数据报的长度要小。那么如何将这个过大的IP分组压缩进链路层帧的有效载荷字段呢？

解决办法是，将IP数据报中的数据分片成两个或更多个较小的IP数据报，用单独的链路层帧封装这些较小的IP数据报；然后向输出链路上发送这些帧。每个这些较小的数据报都被称为片(fragment)。

路由器完成分片任务。同时，为了使得网络内核保持简单，IPv4设计者把数据报的重组工作放到端系统中，而非放到网络路由器中。

前提：一个4000字节的数据报(20字节IP首部加上3980字节IP有效载荷)到达一台路由器，且必须被转发到一条MTU为1500字节的链路上。假定初始数据报贴上的标识号为777。

这意味着初始数据报中3980字节数据必须被分配到3个独立的片(其中的每个片也是一个IP数据报)

IP分片：

IP地址有32比特，分为网络号和主机号。
IP地址的网络部分（即网络号）被限制为长度为8、16或24比特，这是一种称为分类编址的编址方案。具有8、16和24比特子网地址的子网分别被称为A、B和C类网络。

但是它在支持数量迅速增加的具有小规模或中等规模子网的组织方面出现了问题。一个C类(/24)子网仅能容纳多大2^8 - 2 = 254台主机(2^8 = 256, 其中的两个地址预留用于特殊用途)，这对许多组织来说太小了。然而一个B类(/16)子网可支持多达65534台主机，又太大了。这导致B类地址空间的迅速损耗以及所分配的地址空间的利用率低。

广播地址255.255.255.255。当一台主机发出一个目的地址为255.255.255.255的数据报时，该报文会交付给同一个网络中的所有主机。

某组织一旦获得了一块地址，它就可以为本组织内的主机与路由器接口逐个分配IP地址。既可手工配置IP地址，也可以使用动态主机配置协议(Dynamic Host Configuration Protocol, DHCP)自动配置。DHCP还允许一台主机得知其他信息，如它的子网掩码、它的第一跳路由器地址(常称为默认网关)与它的本地DNS服务器的地址。

由于DHCP具有能将主机连接进一个网络相关方面的自动能力，它又被称为即插即用协议。

DHCP是客户-服务器协议。客户通常是新达到的主机，它要活的包括自身使用的IP地址在内的网络配置信息。在最简单的场合下，每个子网将具有一台DHCP服务器。如果在某子网中没有服务器，则需要一个DHCP中继代理(通常是一台路由器)，这个代理知道用于该网络的DHCP服务器的地址。

DHCP协议工作的4个步骤：

网络地址转换(Network Address Translation, NAT)

ICMP通常被认为是IP的一部分，但从体系结构上将它是位于IP之上的，因为ICMP报文是承载在IP分组中的。即ICMP报文是作为IP有效载荷承载的，就像TCP与UDP报文段作为IP有效载荷被承载那样。

众所周知的ping程序发送一个ICMP类型8编码0的报文到指定主机。看到该回显请求，目的主机发回一个类型0编码0的ICMP回显回答。大多数TCP/IP实现直接在操作系统中支持ping服务器，即该服务器不是一个进程。

新型IPv6系统可做成向后兼容，即能发送、路由和接收IPv4数据报，要使得已部署的IPv4系统能够处理IPv6数据报，最直接的方式是采用一种双栈方法。

1、链路状态(Link State, LS)算法：属于全局式路由选择算法，这种算法必须知道网络中每条链路的费用。费用可理解为链路的物理长度、链路速度，或与该链路相关的金融上的费用。链路状态算法采用的是Dijkstra算法。

2、距离向量(Distance-Vector, DV)算法：属于迭代的、异步的和分布式的路由选择算法。
“迭代的”，是因为此过程一直要持续到邻居之间无更多信息要交换为止。
“异步的”，是因为它不要求所有结点相互之间步伐一致地操作。
“分布式的”，是因为每个结点都要从一个或多个直接相连邻居接收某些信息，执行计算，然后将其计算结果分发给邻居。
DV算法的方程：

其中，dx(y)表示从结点x到结点y的最低费用路径的费用，c(x, v)是结点x到结点v的费用，结点v指的是所有x的相连结点，所以x的所有相连结点都会用minv方程计算。

（N是结点（路由器）的集合，E是边（链路）的集合）

为了减少公共因特网的路由选择计算的复杂性以及方便企业管理网络，我们将路由器组织进自治系统。

在相同AS中的路由器全都运行同样的路由选择算法，且拥有彼此的信息。在一个自治系统内运行的路由选择算法叫做自治系统内部路由选择协议。

当然，将AS彼此互联是必需的，因此在一个AS内的一台或多台路由器将有另外的任务，即负责向在本AS之外的目的地转发分组。这些路由器被称为网关路由器。

分为自治系统内部的路由选择和自治系统间的路由选择

1、因特网中自治系统内部的路由选择：路由选择信息协议(Routing Information Protocol, RIP)
2、因特网中自治系统内部的路由选择：开放最短路优先(Open Shortest Path First, OSPF)
3、自治系统间的路由选择：边界网关协议(Broder Gateway Protocol, BGP)

为什么要使用不同的AS间和AS内部路由选择协议？

实现广播的方法
1、无控制洪泛。该方法要求源结点向它的所有邻居发送分组的副本。当某结点接收了一个广播分组时，它复制该分组并向它的所有邻居（除了从其接收该分组的那个邻居）转发之。
致命缺点： 广播风暴 ，如果图具有圈，那么每个广播分组的一个或多个分组副本将无休止地循环。
2、受控洪泛。用于避免广播风暴，关键在于正确选择何时洪泛分组，何时不洪泛分组。受控洪泛有两种方法：序号控制洪泛、反向路径转发(Reverse Path Forwarding, RPF)
3、生成树广播。虽然序号控制洪泛和RPF能避免广播风暴，但是它们不能完全避免冗余广播分组的传输。

多播：将分组从一个或多个发送方交付到一组接收方

每台主机有一个唯一的IP单播地址，该单播地址完全独立于它所参与的多播组的地址。

因特网网络层多播由两个互补组件组成：因特网组管理协议(Internet Group Management Protocol, IGMP)和多播路由选择协议

IGMP只有三种报文类型：membership_query报文，membership_report报文，leave_group报文。

与ICMP类似，IGMP报文也是承载在一个IP数据报中。

因特网中使用的多播路由选择
1、距离向量多播路由选择协议
2、协议无关的多播路由选择协议

㈥ 6,路由选择有哪些算法

关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法：
总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为dv（距离向量）算法。采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为ls（链路状态）算法。

㈦ 路由算法的类型有

路由算法有很多种，如果从路由表对网络拓扑和通信量变化的自适应能力的角度划分，可以分为静态路由算法和动态路由算法两大类，这两大类又可细分为几种小类型，比较典型常见的有以下几种：

一、静态路由算法

1.Dijkstra算法（最短路径算法）

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。

Dijkstra算法执行步骤如下：

步骤一：路由器建立一张网络图，并且确定源节点和目的节点，在这个例子里我们设为V1和V2。然后路由器建立一个矩阵，称为“邻接矩阵”。在这个矩阵中，各矩阵元素表示权值。例如，[i,j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连，它们的权值设为“无穷大”。

步骤二：路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段：

前序字段———表示当前节点之前的节点。

长度字段———表示从源节点到当前节点的权值之和。

标号字段———表示节点的状态。每个节点都处于一个状态模式：“永久”或“暂时”。

步骤三：路由器初始化（所有节点的）状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。

步骤四：路由器设置一个T节点。例如，如果设V1是源T节点，路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后，它将不再改变。一个T节点仅仅是一个代理而已。

步骤五：路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。

步骤六：路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。

步骤七：如果这个节点不是V2（目的节点），路由器则返回到步骤5。

步骤八：如果节点是V2，路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。

2.扩散法
事先不需要任何网络信息；路由器把收到的每一个分组，向除了该分组到来的线路外的所有输出线路发送。将来会有多个分组的副本到达目的地端，最先到达的，可能是走了“最优”的路径常见的扩散法是选择性扩散算法。

3.LS算法

采用LS算法时，每个路由器必须遵循以下步骤：

步骤一：确认在物理上与之相连的路由器并获得它们的IP地址。当一个路由器开始工作后，它首先向整个网络发送一个“HELLO”分组数据包。每个接收到数据包的路由器都将返回一条消息，其中包含它自身的IP地址。

步骤二：测量相邻路由器的延时（或者其他重要的网络参数，比如平均流量）。为做到这一点，路由器向整个网络发送响应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包。将路程往返时间除以2，路由器便可以计算出延时。（路程往返时间是网络当前延迟的量度，通过一个分组数据包从远程主机返回的时间来测量。）该时间包括了传输和处理两部分的时间——也就是将分组数据包发送到目的地的时间以及接收方处理分组数据包和应答的时间。

步骤三：向网络中的其他路由器广播自己的信息，同时也接收其他路由器的信息。

在这一步中，所有的路由器共享它们的知识并且将自身的信息广播给其他每一个路由器。这样，每一个路由器都能够知道网络的结构以及状态。

步骤四：使用一个合适的算法，确定网络中两个节点之间的最佳路由。

路由算法有哪些类型？路由算法与路由协议的区别

在这一步中，路由器选择通往每一个节点的最佳路由。它们使用一个算法来实现这一点，如Dijkstra最短路径算法。在这个算法中，一个路由器通过收集到的其他路由器的信息，建立一个网络图。这个图描述网络中的路由器的位置以及它们之间的链接关系。每个链接都有一个数字标注，称为权值或成本。这个数字是延时和平均流量的函数，有时它仅仅表示节点间的跃点数。例如，如果一个节点与目的地之间有两条链路，路由器将选择权值最低的链路。

二、动态路由算法

1.距离向量路由算法

距离向量路由算法，也叫做最大流量算法，其被距离向量协议作为一个算法，如RIP、BGP、ISO IDRP、NOVELL IPX。使用这个算法的路由器必须掌握这个距离表(它是一个一维排列-“一个向量”)，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的量和在网络中的所有的接点(除了它自己本身)是等同的。这个表中的列代表直接和它相连的邻居，行代表在网络中的所有目的地。每个数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输(我们叫这个为“成本”)。这个在那个算法中的度量公式是跳跃的次数，等待时间，流出数据包的数量，等等。在距离向量路由算法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。其优点是算法简单容易实现。缺点是慢收敛问题，路由器的路径变化需要像波浪一样从相邻路由器传播出去，过程缓慢。

每一个相邻路由器发送过来的路由表都要经过以下步骤：

步骤一：对地址为X的路由器发过来的路由表，先修改此路由表中的所有项目：把”下一跳”字段中的地址改为X，并把所有”距离”字段都加1。

步骤二：对修改后的路由表中的每一个项目，进行以下步骤：

（1）将X的路由表(修改过的)，与S的路由表的目的网络进行对比。若在X中出现，在S中没出现，则将X路由表中的这一条项目添加到S的路由表中。

（2）对于目的网络在S和X路由表中都有的项目进行下面步骤：

1）在S的路由表中，若下一跳地址是x，则直接用X路由表中这条项目替换S路由表中的项目。

2）在S的路由表中，若下一跳地址不是x，若X路由表项目中的距离d小于S路由表中的距离，则进行更新。

步骤三：若3分钟还没有收到相邻路由器的更新表，则把此相邻路由器记为不可到达路由器，即把距离设置为16。

2.链路状态最短路由优先算法SPF

1）发现邻居结点，并学习它们的网络地址；

2）测量到各邻居节点的延迟或者开销；

3）创建链路状态分组；

4）使用扩散法发布链路状态分组；

5）计算到每个其它路由器的最短路径。

㈧ 路由选择算法分为两大类

路由选择算法分为两大类如下：

静态路由选择算法和动态路由选择算法两大类。

因为路由器位于网络的连接点，当它们失效时会产生重大的问题。族银磨最好的路由算法通常是那些经过了时间考验，证实在各种网络条件下都很稳定的算法。

此外路由算兆斗法必须能快速聚合，聚合是所有路由器对最佳路径达成一致的过程。当某网络事件使路径断掉或不可用时，路由器通过网络分发路由更新信息，促使最佳路径的重新计算，最终使所有路由器达成一致。聚合很慢的路由算法可能会产生路由环或网路中断。

总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。

㈨ 路由器常见的路由算法有那些

路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状态与距离向量。
1.链接状态
2.距离向量
3.LS算法
4.Dijkstra算法

㈩ 路由算法的度量标准

路由算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法可能采用多种度量来选择路由，通过一定的加权运算，将它们合并为单个的复合度量、再填入路由表中，作为寻径的标准。
通常所使用的度量有：路径长度、可靠性、时延、带宽、负载、通信成本等。 采用LS算法时，每个路由器必须遵循以下步骤：
1、确认在物理上与之相连的路由器并获得它们的IP地址。当一个路由器开始工作后，它首先向整个网络发送一个“HELLO”分组数据包。每念拆悉个接收到数据包的路仔乎由器都将返回一条消息，其中包含它自身的IP地址。
2、测量相邻路由器的延时（或者其他重要的网络参数，比如平均流量）。为做到这一点，路由器向整个网络发送响应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包。将路程往返时间除以2，路由器便可以计算出延时。（路程往返时间是网络当前延迟的量度，通过一个分组数据包从远程主机返回的时间来测量。）该时间包括了传输和处理两部分的时间——也就是将分组数据包发送到目的地的时间以及接收方处理分组数据包和应答的时间。
3、向网络中的其他路由器广播自己的信息，同时也接收其他路由器的信息。
在这一步中，所有的路由器共享它们的知识并且将自身的信息广播给其他每一个路由器。这样，每一个路由器都能够知道网络的结构以及状态。
4、使用一个合适的算法，确定网络中两个节点之间的最佳路由。
在这一步中，路由器选择通往每一个节点的最佳路由。它们使用一个算法来实现这一点，如Dijkstra最短路径算法。在这个算法中，一个路由器通过收集到的其他路由器的信息，建立一个网络图。这个图描述网络中的路由器的位置以及它们之间的链接关系。每个链接御皮都有一个数字标注，称为权值或成本。这个数字是延时和平均流量的函数，有时它仅仅表示节点间的跃点数。例如，如果一个节点与目的地之间有两条链路，路由器将选择权值最低的链路。 Dijkstra算法执行下列步骤：1、路由器建立一张网络图，并且确定源节点和目的节点，在这个例子里我们设为V1和V2。然后路由器建立一个矩阵，称为“邻接矩阵”。在这个矩阵中，各矩阵元素表示权值。例如，[i, j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连，它们的权值设为“无穷大”。
2、路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段：
前序字段——表示当前节点之前的节点。
长度字段——表示从源节点到当前节点的权值之和。
标号字段——表示节点的状态。每个节点都处于一个状态模式：“永久”或“暂时”。
3、路由器初始化（所有节点的）状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。
4、路由器设置一个T节点。例如，如果设V1是源T节点，路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后，它将不再改变。一个T节点仅仅是一个代理而已。
5、路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。
6、路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。
7、如果这个节点不是V2（目的节点），路由器则返回到步骤5。
8、如果节点是V2，路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。 距离向量算法（也称为Bellman-Ford算法）则要求每个路由器发送其路由表全部或部分信息，但仅发送到邻近结点上。从本质上来说，链路状态算法将少量更新信息发送至网络各处，而距离向量算法发送大量更新信息至邻接路由器。 ——由于链路状态算法收敛更快，因此它在一定程度上比距离向量算法更不易产生路由循环。但另一方面，链路状态算法要求比距离向量算法有更强的CPU能力和更多的内存空间，因此链路状态算法将会在实现时显得更昂贵一些。