什么是路由权,路由算法

2016-11-12

路由权和路由算法可能很多人都不太了解,小编收集的本文为大家揭开神秘面纱,欢迎大家阅读借鉴,希望对您有所帮助!

路由权

B

Network N1

Network N2

A

C

D带宽

时延

负载

可靠性

跳数

开销

路由权:用于选择最佳路由的信息。

路由算法修改路由表的基本目的是将最好路由信息添加到路由表中,路由的好坏是由路由算法根据自己获得的路由信息计算出来的。对于每一条路由,路由算法产生一种权值来表示路由的好坏。通常情况下,这种权值越小,该路径越好。

路由权的计算可能基于路径某单一特性计算,也可能基于路径多种属性进行计算。有几种路径特性经常被用于权值计算,如下:

1) 带宽 -- 链路的数据容量。例如,通常情况下10M 以太网链路比 64K 出租线路要更好。

2) 时延 -- 报文从到达目标网络所需要的时间。

3) 负载 -- 处于活跃状态的网络资源数量。

4) 可靠性 -- 每条数据链路的出错率。

5) 跳数 -- 报文到目的地需要经过的网络数。

6) 开销 -- 一种人为设定的值,通常由网络管理员根据带宽、线路价格或其他一些因素综合得出。

路由算法

路由算法,又名选路算法,可以根据多个特性来加以区分。算法的目的是找到一条从源路由器到目的路由器的“好”路径(即具有最低费用的路径)。算法设计者的特定目标影响了该路由协议的操作;具体来说存在着多种路由算法,每种算法对网络和路由器资源的影响都不同;由于路由算法使用多种度量标准(metric),从而影响到最佳路径的计算。

路由算法是提高路由协议功能,尽量减少路由时所带来开销的算法。当实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。路由算法必须健壮,即在出现不正常或不可预见事件的情况下必须仍能正常处理,例如硬件故障、高负载和不正确的实现。因为路由器位于网络的连接点,当它们失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验,证实在各种网络条件下都很稳定的算法。此外路由算法必须能快速聚合,聚合是所有路由器对最佳路径达成一致的过程。当某网络事件使路径断掉或不可用时,路由器通过网络分发路由更新信息,促使最佳路径的重新计算,最终使所有路由器达成一致。聚合很慢的路由算法可能会产生路由环或网路中断。

路由算法是提高路由协议功能,尽量减少路由时所带来开销的算法。当实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。路由算法必须健壮,即在出现不正常或不可预见事件的情况下必须仍能正常处理,例如硬件故障、高负载和不正确的实现。因为路由器位于网络的连接点,当它们失效时会产生重大的问题。

最好的路由算法通常是那些经过了时间考验,证实在各种网络条件下都很稳定的算法。此外路由算法必须能快速聚合,聚合是所有路由器对最佳路径达成一致的过程。当某网络事件使路径断掉或不可用时,路由器通过网络分发路由更新信息,促使最佳路径的重新计算,最终使所有路由器达成一致。聚合很慢的路由算法可能会产生路由环或网路中断。

LS算法

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

ls算法的步骤流程

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

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

3、向网络中的其他路由器广播自己的信息,同时也接收其他路由器的信息。

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

4、使用一个合适的算法,确定网络中两个节点之间的最佳路由。

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

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能力和更多的内存空间,因此链路状态算法将会在实现时显得更昂贵一些。

路由知识的相关文章:

1.路由器知识点大全

2.路由器知识全解

3.路由器的类型以及作用的知识介绍

4.详细的介绍路由器是什么

5.路由器简介知识大全

6.路由器基本知识常用术语

7.路由器的配置基础知识

8.路由器有什么组成

9.路由器应用限制

10.教你配置简单的静态路由

更多相关阅读

最新发布的文章