当前位置：首页 > wifi设置知识 > 正文内容

路由算法有哪些

秋天2023年04月30日 10:24:08wifi设置知识196

当朋友们看到这个文章时想必是想要了解路由算法有哪些相关的知识，这里同时多从个角度为大家介绍路由算法有哪些分类?相应的内容。

本文内容目录一览：

1、路由算法
2、路由选择算法分为两大类
3、6,路由选择有哪些算法？
4、路由算法的类型有
5、常见的路由选择算法有哪些
6、静态路由算法有哪些

路由算法

路由算法是网络层软件的一部分。子网提供数据报服务，每个包都要做路由选择；子网提供虚电路服务，只需在建立连接时做一次路由选择

正确性，简单性，健壮性（鲁棒性，网络出现意外情况时候的解决问题的能力。例如突然某个路由器停电了，使得周边的路由器都没法正常工宽码作，如果出现这样的问题说明路由器的健壮性不够），稳定性（常规使用是否稳定，数据量增多的时候能否正常工作），公平性（网络资源的使用是否公平，避免有些节点出现特别繁忙的状态，而有些节点总是处于很闲的状态），最优性

• 按转发方式和数据副本数量划分

1.全路路由（广播路由）算法：如洪泛算法，按照所有路径广播转发（中间转发节点以及目标节点都会送到很多重复数据。不需要路由表和路由控制功能）

2.多路路由算法：向所有接近目的节点的路径转发（中间转发节点以漏弊及目标节点都会送到很多重复数据。）

3.单路路由算法：如距离矢量算法，向目的节点沿着唯一的路径转发（中间的转发节点只转发一份数据即可）

• 按健壮性和简单性划分

1.非自适应算法（静态路由算法）：不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表。需要人为的更改和设定。特点是简单、开销小、灵活性差。典型算法为基于流量的路由算法等

2.自适应算法（动态路由算法）：可根据网络流量（网络承载的数据量）和拓扑结构的变化更新路由表。特点是开销大、健壮性和灵活性好。典型算法为距离向量路由算法、链路状态路由算法等

☆可以静态路由和动态路由结合起来使用，此时静态路由的优先级别较高

测量（获取）有关路由选择的网络度量参数（选择最优，比如是要求传播距离最短，还是要求传输时延短等）。如何测量？选取哪些网络参数？

将路由信息传送到适当的网络节点。传送给谁？如何传送？传送什么信息？

计算和更新路由表。更新路由表的算法

根据新路由表执行分组的转发

如果路由器J在路由器I到K的最优路由上，那么从J到K的最优路由一定落在同一路由上

从所有的源节点到一个给定的目的节点的最优路由的集合形成了一个以目的节点为根的树，称为汇集树；路由算法的目的是找出并使用汇集树

基本思想：构建子网的拓扑图，图中的每个节点代表一个慎搜哪路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法需要在图中找出节点间的最短路径

节点数量；地理距离；传输延迟；距离、信道带宽等参数的加权函数

网络规模增大带来的问题：路由器中的路由表增大；路由器为选择路由而占用的内存、CPU时间和网络带宽增大

分层路由：分而治之的思想；根据需要，将路由器分成区域、聚类、区和组；Fig.6-6，路由表由17项减为7项

分层路由带来的问题：路由表中的路由不一定是最优路由

☆分层路由功能大部分时候性能是比较好的，可以选择最优路径，但是有时也会选择到非最优路径。比如上图中如果想从1A到5C，应该是1A→1B→2A→2B→2D→5C是比较优的选择，但是按照1A的分层路由表显示，从区域1到区域5出口线路为1C，因此选择的路线为1A→1C→3B→4A→5A→5B→5C，这时就相对绕远了

DVR - Distance Vector Routing

动态路由算法，也称Bellman - Ford路由算法或Ford - Fulkerson算法，最初用于ARPANET（Internet的前身），被RIP协议所采用

每个路由器维护一张路由表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表；每隔一段时间，路由器向所有邻居节点发送它到每个目的节点的距离表，同时它也接收每个邻居节点发来的距离表；邻居节点X发来的表中，X到路由器I的距离为Xi，本路由器到X的距离为m，则路由器经过X到i的距离为Xi + m。根据不同邻居发来的信息，计算Xi + m，并取最小值，更新本路由器的路由表

图1：

此时路由A把它的路由表发给路由B，B会综合从A得来的路由表来更新自己的矢量表↓

根据初始A矢量表和B矢量表得知B到A为6，B到C为1，B到D没有；两个表都有到E的距离，直接从B到E为8；如果B经由A再到E就要计算A到B的距离加上A到E的距离即可，即6+1=7

图2：

B把路由表发给C之后↓

从C的初始矢量表可得知C到B为1，C到D为2，C无法直接到A，但是通过B的路由表得知B到A为6，再加上C到B的距离1，得出C到A距离为7，同理可得到E距离为7+1=8

图3：

C把路由表发给D之后↓

图4：

D把路由表发给E之后↓

J的相邻节点为4个，分别为A，I，H，K，因此可以选择的路线也为4种

现在要求J的最新路由表。以J到E为例，J到A为8，A到E为14，和为22；J到I为10，I到E为7，和为17；J到H为12，H到E为30，和为42；J到K为6，K到E为22，和为28。从而得出，经由I的时候得到的和17最小，因此在新生成的J到E的位置记录17

无限计算问题：对好消息反应迅速，对坏消息反应迟钝

比如从E到A，E刚开始连通的时候是不知道如何才能到A的，只有通过B与A交互，C与B交互这样最终E通过与D交互才知道如何能到A，这就是好消息。可能需要花些时间，但是结果都是无论目的节点是哪里总会找到路径

坏消息例子：A，B，C之间通信。B到A的距离为1（A，1），C到A的距离为2（B（经B），2）。各个节点都会有一个刷新周期，到了这个周期的时候每个节点会把自己的路由信息发给其相邻节点。例如A路由断开连接，这个时候B到A的线路断开。也就是B到A的距离为无穷大了（A，∞）。如果在B把这个信息反馈给C之前，C先把路由信息告诉B了，那么B收到的信息就为（C，3）。因为A已经不存在，而B从C处得知通过C有路径可以到达A，这时B的路由表就变成（C，3），同样的这时B再告诉C，C就会变成（B，4），就会这样无穷计算下去。如果一开始是B先把信息发给C就不会发生这样的问题

• 触发式更新：节点不等到刷新周期的到来，只要有突发情况马上就会把情况通知相邻路由

• 水平分割：因为一开始C是从B得知经过B可以到达A的，所以用了这种方法之后，C就不会再向B发送如何到A，而只等着B给C发如何到A了。这样就不会有无穷计算问题

• 定义一个最大值：坏消息例子当中，括号里后面的数会一直循环增长下去，如果把这个数字设置一个最大值，那么当循环到这个最大值的时候双方就不会再就怎么到A的信息进行交互了，就不会发生无穷计算的情况

• 挂起计数器：坏消息例子当中，B收到了C的路由最新信息（C，3）的时候这个不会马上生效刷新，（A，∞）会保留两个周期，在这两个周期里面，B肯定有机会给C发送（A，∞），

而因为C没有通往A的路径，所以当C到刷新周期的时候给B发的就为（B，∞）。B前后收到的信息不一致，但是第二次收到的信息和B发给C的信息是一致的，所以B就会认为第一次收到的（C，3）是无效的。但是如果C真的有了一条通往A的线路，这时两次发的信息一定是一致的，那么B就会相信C的信息，从而把（A，∞）刷新成C给B的信息

❉距离向量路由算法只适用于小规模网络，每个节点不清楚整个网络的拓扑结构

发现邻居节点，并学习它们的网络地址，测量到每个邻居节点的延迟或开销，将所有学习到的内容封装成一个链路状态包（包以发送方的标识符开头，后面是序号、年龄和一个邻居节点列表；链路状态包定期创建或发生重大事件时创建）。将链路状态包广播发送给所有其他路由器【洪泛方式：状态包包含一个序号，每次发送新包时加1。路由器记录信息对（源路由器，序号），当一个链路状态包到达时，若是新的则分发，若是重复的则丢弃，若序号比路由记录中的最大序号小则认为过时而丢弃】。计算到每个其他路由器的最短路径

☆链路状态路由算法适用于大规模网络。每个节点都会了解其他节点的局部拓扑，因此就会了解整个网络的拓扑结构，这时当前节点就能找到到目的节点的最优路由

• 使用32位序号。

因为序号是循环使用的，如果位数很少，比如只是1~7，那么7不一定比1大，1有可能是下一轮的第一个数。而32位的时候因为数字特别庞大，不会出现这样问题

• 增加年龄域，每秒钟年龄减1，为零则丢弃

比如A发给B （C，4），由于差错，本来是（C，5）的下一个包，变成了（C，1000）。这之后来的（C，6），（C，7）。。。都没有（C，1000）大，因此包会被丢弃。但其实后面到的包都是新的。为了避免这样的问题发生，（C，1000）里的1000就会在每一秒减1，直到年龄比新到的包小，接下来就可以正常接包了。不过这之前到的包都会被丢弃，这也是没有办法的事

• 链路状态包到达后，延迟一段时间，并与其它已到达的来自同一路由器的链路状态包比较序号，丢弃重复包，保留新包

• 链路状态包需要应答

为了保证数据传输的可靠性

路由选择算法分为两大类

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

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

关于路由选择算法的介绍如下：

路由算法是提高路由协议功能，尽量减少路由时所带来开销的算法。当实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。路由算法必须健壮，即在出现不正常或不可预见事件的情况下必须仍能正常处理，例如硬件故障、高负载和不正确的实现。

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

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

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

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

路由算法分为:静态路由算带橡毕法和动态路由算法(又称为

自适应路由选择算法)1.静态算法分为:a.泛射路由算法(扩散法)

b.固定路由算法

c.随机走动法（Random

Walk）d.最短路径法（Shortest

Path，SP）2.动态路由算法分为:

（1）分布式路由选择。基本算蠢芹法有距离向量算法和链路如仿状态算法；

2）集中式路由选择。(3）混合式动态路由选择

(4).链路状态路由算法

路由算法的类型有

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

一、静态路由算法

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）计算到每个其它路由器的最短路径。

常见的路由选择算法有哪些

链路状态算法（也称最短路径算法）发送路由信息到互联网上所有的结点，姿轿明然而对于每个路由器，仅发送它的路由表中描述了其自身链路状态的那一部分。距离向量算法（也称为Bellman-Ford算法）则要求每个路由器发送其路由表全部或部分信息，但仅发送到邻近结点上。从本质上来说，链路状态算法将少量更新信息发迹告送至网络各处，而距离向量算法发送大量更新信息至邻接路由器。 ——由于链路状态算法收敛更快，因此它在一定程度上比距离向量算法更不易产生路由循环。但另一方面，链路状态算法要求比距离向量算法有更强帆手的CPU能力和更多的内存空间，因此链路状态算法将会在实现时显得更昂贵一些。除了这些区别，两种算法在大多数环境下都能很好地运行。