路由算法详解

文章摘要：路由算法详解引言如果您已经阅读过博闻网中的路由器工作原理一文，您会了解到路由器的作用是管理网络流量和找到发送分组数据包的最佳路由。但是您是否想过路由器是怎么做到这一点的？路由器需要一些网络状态的信息来决定如何发送分组数据包以及发往哪里。但是它是怎样收集这些信息的？ 在本篇博闻网文章中，我们将带您详细了解路由器需要哪些信息来决定往哪发送分组数据包。路由器基础知识路由器使用路由算法来找到到达目的地的最佳路由。当我们说“最佳路由”时，我们考虑的参数包括诸如跳跃数（分组数据包在网络中从一个路由器或中间节点到另外的节点的行程）、延时以及分组数据包传输通信耗时。 关于路由器如何收集网络的结构信息以及对之进

路由算法详解,标签：电子电路基础,模拟电路基础,http://www.88dzw.com

路由算法详解

引言

如果您已经阅读过博闻网中的路由器工作原理一文，您会了解到路由器的作用是管理网络流量和找到发送分组数据包的最佳路由。但是您是否想过路由器是怎么做到这一点的？路由器需要一些网络状态的信息来决定如何发送分组数据包以及发往哪里。但是它是怎样收集这些信息的？

在本篇博闻网文章中，我们将带您详细了解路由器需要哪些信息来决定往哪发送分组数据包。

路由器基础知识

路由器使用路由算法来找到到达目的地的最佳路由。当我们说“最佳路由”时，我们考虑的参数包括诸如跳跃数（分组数据包在网络中从一个路由器或中间节点到另外的节点的行程）、延时以及分组数据包传输通信耗时。

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

LS算法

采用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的最佳路由。

[1] [2] [3] [4] [5]  下一页