链路状态路由算法

⑴ 链路状态路由算法的算法工作原理

链路状态选路算法的工作原理如下
（1）在参与链路状态选路的路由器集合中，每个路由器都需要通过某种机制来了解自己所连接的链路及其状态。
（2）各路由器都能够将其所连接的链路的状态信息通知给网络中的所有其他路由器，这些链路信息包括链路状态、费用以及链路两端的路由器等。
（3）链路状态信息的通过链路状态分组（LSP）来向整个网络发布。一个LSP通常包含源路由器的标识符、相邻路由器的标识符，以及而知之间链路的费用。每一个LSP都将被网络中的所有的路由器接收，并用于建立网络整体的统一拓扑数据库。由于网络中所有的路由器都发送LSP，经过一段时间以后，每一个路由器都保持了一张完整的网络拓扑图，再在这个拓扑图上，利用最短通路算法（例如Dijkstra算法等），路由器就可以计算出从任何源点到任何目的地的最佳通路。
这样，每一个路由器都能够利用通路最短的原则建立一个以本路由器为根、分支到所有其他路由器的生成树，依据这个生成树就可以很容易地计算出本路由器的路由表。

⑵ 链路状态路由协议运行什么算法来计算到达目的网络的最短路径

一、RIP协议RIP(RoutinginformationProtocol)是应用较早、使用较普遍的内部网关协议(InteriorGatewayProtocol,简称IGP)，适用于小型同类网络，是典型的距离向量(distance-vector)协议。文档见RFC1058、RFC1723。RIP通过广播UDP报文来交换路由信息，每30秒发送一次路由信息更新。RIP提供跳跃计数(hopcount)作为尺度来衡量路由距离，跳跃计数是一个包到达目标所必须经过的路由器的数目。如果到相同目标有二个不等速或不同带宽的路由器，但跳跃计数相同，则RIP认为两个路由是等距离的。RIP最多支持的跳数为15，即在源和目的网间所要经过的最多路由器的数目为15，跳数16表示不可达。1.有关命令任务命令指定使用RIP协议routerrip指定RIP版本version{1|2}1指定与该路由器相连的网络networknetwork注：1.Cisco的RIP版本2支持验证、密钥管理、路由汇总、无类域间路由(CIDR)和变长子网掩码(VLSMs)二、IGRP协议IGRP()是一种动态距离向量路由协议，它由Cisco公司八十年代中期设计。使用组合用户配置尺度，包括延迟、带宽、可靠性和负载。缺省情况下，IGRP每90秒发送一次路由更新广播，在3个更新周期内(即270秒)，没有从路由中的第一个路由器接收到更新，则宣布路由不可访问。在7个更新周期即630秒后，CiscoIOS软件从路由表中清除路由。1.有关命令任务命令指定使用RIP协议routerigrpautonomous-system1指定与该路由器相连的网络networknetwork指定与该路由器相邻的节点地址neighborip-address注：1、autonomous-system可以随意建立，并非实际意义上的autonomous-system,但运行IGRP的路由器要想交换路由更新信息其autonomous-system需相同。三、OSPF协议OSPF(OpenShortestPathFirst)是一个内部网关协议(InteriorGatewayProtocol,简称IGP)，用于在单一自治系统(autonomoussystem,AS)内决策路由。与RIP相对，OSPF是链路状态路有协议，而RIP是距离向量路由协议。链路是路由器接口的另一种说法，因此OSPF也称为接口状态路由协议。OSPF通过路由器之间通告网络接口的状态来建立链路状态数据库，生成最短路径树，每个OSPF路由器使用这些最短路径构造路由表。文档见RFC2178。1．有关命令全局设置任务命令指定使用OSPF协议routerospfprocess-id1指定与该路由器相连的网络networkaddresswildcard-maskareaarea-id2指定与该路由器相邻的节点地址neighborip-address注：1、OSPF路由进程process-id必须指定范围在1-65535，多个OSPF进程可以在同一个路由器上配置，但最好不这样做。多个OSPF进程需要多个OSPF数据库的副本，必须运行多个最短路径算法的副本。process-id只在路由器内部起作用，不同路由器的process-id可以不同。2、wildcard-mask是子网掩码的反码,网络区域IDarea-id在0-4294967295内的十进制数，也可以是带有IP地址格式的x.x.x.x。当网络区域ID为0或0.0.0.0时为主干域。不同网络区域的路由器通过主干域学习路由信息。

⑶ 链路状态路由算法的算法思想

链路状态算法的思想是要求网络中所有参与链路状态路由协议的路由器都掌握网络的全部拓扑结构信息，并记录在路由数据库中。链路状态算法中路由数据库实质上是一个网络结构的拓扑图，该拓扑图由一个节点的集合和一个边的集合构成。在网络拓扑图中，结点代表网络中路由器，边代表路由器之间的物理链路。在网络拓扑结构图中，每一条链路上可以附加不同的属性，例如链路的状态、距离或费用等。如果没一个路由器所保存的网络拓扑结构图都是一致的，那么个路由器生成的路由表也是最佳的，不存在错误路由或循环路由。

⑷ 路由算法主要有哪几种

静态路由算法主要有：
洪泛法（Flooding）
随机走动法（Random Walk）
最短路径法（Shortest Path，SP）
基于流量的路由算法(Flow-based Routing，FR)</ol>动态路由算法主要有：
距离矢量算法（RIP）
链路状态算法（OSPF）
平衡混合算法（EIGRP）</ol>

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

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

⑹ 两种路由选择算法是什么

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

⑺ 路由协议中的链路状态法的工作过程是什么

链路状态法工作过程：

1、了解直连网络。

2、向邻居发送Hello数据包。

3、建立链路状态数据包。

4、将链路状态数据包泛洪给邻居。

5、构建链路状态数据库。

运行链路状态路由协议的路由器，只将它所直连的链路状态与邻居共享，这个邻居是指一个域内（domain），或一个区域内（area）的所有路由器。

(7)链路状态路由算法扩展阅读：

链路状态路由协议，更新的是“拓扑”。每台路由器上都有完全相同的拓扑，他们各自分别进行SPF算法，计算出路由条目。

一条重要链路的变化，不必再发送所有被波及的路由条目，只需发送一条链路通告，告知其它路由器本链路发生故障即可。其它路由器会根据链路状态，改变自已的拓扑数据库，重新计算路由条目。

⑻ 链路状态路由采用的算法是：

b和c 例如ospf 区域内是最短路径优先算法，那么区域间呢？区域间为距离矢量算法。

⑼ 路由算法的类型有

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

一、静态路由算法

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算法

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