路由算法如何工作

如果您已阅读十万个为什么文章路由器如何工作，那么您就知道路由器用于管理网络流量并找到发送数据包的最佳路由。但您曾否想过路由器是如何做到这一点的？路由器需要了解一些网络状态信息，以便决定如何以及向何处发送数据包。但是它们如何收集这些信息呢？

在本文中，我们将精确地找出路由器在确定数据包发送位置时使用的信息。

基础

路由器使用路由算法来找到到达目的地的最佳路由。当我们说“最佳路由”时，我们考虑的参数包括跳数（数据包从网络中的一个路由器或中间点到另一个点的行程）、时间延迟和数据包传输的通信成本。

根据路由器如何收集网络结构信息以及它们如何分析信息以指定最佳路由，我们有两种主要的路由算法：全局路由算法和分散路由算法。在分散路由算法中，每个路由器只拥有与其直接连接的路由器的信息——它不了解网络中的所有路由器。这些算法也称为DV（距离矢量）算法。在全局路由算法中，每个路由器都拥有网络中所有其他路由器的完整信息以及网络的流量状态。这些算法也称为LS（链路状态）算法。我们将在下一节讨论LS算法。

LS 算法

在LS算法中，每个路由器都必须遵循以下步骤

识别与其物理连接的路由器并获取它们的IP地址。当路由器开始工作时，它首先通过网络发送一个“HELLO”数据包。每个接收到此数据包的路由器都会回复一条包含其IP地址的消息。
测量相邻路由器的延迟时间（或网络的任何其他重要参数，例如平均流量）。为了做到这一点，路由器通过网络发送回显数据包。每个接收到这些数据包的路由器都会回复一个回显回复数据包。通过将往返时间除以2，路由器可以计算出延迟时间。（往返时间是衡量网络当前延迟的指标，通过计时从某个远程主机弹回的数据包来获得。）请注意，此时间包括传输时间和处理时间——数据包到达目的地所需的时间以及接收方处理并回复所需的时间。
在网络上广播其信息以供其他路由器使用并接收其他路由器的信息。在此步骤中，所有路由器共享其知识并相互广播其信息。通过这种方式，每个路由器都可以了解网络的结构和状态。
使用适当的算法，识别网络中两个节点之间的最佳路由。在此步骤中，路由器选择到达每个节点的最佳路由。它们通过使用一种算法来完成此操作，例如迪克斯特拉最短路径算法。在该算法中，路由器根据从其他路由器收集到的信息，构建一个网络图。该图显示了路由器在网络中的位置以及它们彼此之间的链接。每个链接都标有一个称为权重或成本的数字。这个数字是延迟时间、平均流量的函数，有时也只是节点之间的跳数。例如，如果一个节点和目的地之间有两个链接，路由器会选择权重最低的链接。

迪克斯特拉算法遵循以下步骤

路由器构建网络图，并识别源节点和目标节点，例如V1和V2。然后它构建一个矩阵，称为“邻接矩阵”。在此矩阵中，一个坐标表示权重。例如，[i, j]是Vi和Vj之间链接的权重。如果Vi和Vj之间没有直接链接，则此权重被标识为“无穷大”。
路由器为网络上的每个节点构建一个状态记录集。该记录包含三个字段：前驱字段 - 第一个字段显示前一个节点。长度字段 - 第二个字段显示从源到该节点的权重总和。标签字段 - 最后一个字段显示节点的状态。每个节点可以有一种状态模式：“永久”或“暂定”。
路由器初始化状态记录集（针对所有节点）的参数，并将其长度设置为“无穷大”，将其标签设置为“暂定”。
路由器设置一个T节点。例如，如果V1将作为源T节点，路由器将V1的标签更改为“永久”。当标签变为“永久”时，它将不再更改。T节点仅仅是一个代理。
路由器更新与源T节点直接链接的所有暂定节点的状态记录集。
路由器查看所有暂定节点，并选择到V1权重最低的节点。该节点随后成为目标T节点。
如果此节点不是V2（预期的目的地），路由器返回步骤5。
如果此节点是V2，路由器从状态记录集中提取其前一个节点，并重复此操作直到到达V1。此节点列表显示了从V1到V2的最佳路由。

我们将在下一页使用此算法作为示例。

示例：迪克斯特拉算法

在这里，我们想找到A和E之间的最佳路由（见下文）。您可以看到A和E之间有六种可能的路由（ABE、ACE、ABDE、ACDE、ABDCE、ACDBE），显而易见，ABDE是最佳路由，因为其权重最低。但生活并非总是如此简单，在某些复杂情况下，我们必须使用算法来找到最佳路由。

如您在第一张图中所示，源节点（A）已被选为T节点，因此其标签是永久的（我们用实心圆圈表示永久节点，用-->符号表示T节点）。
在下一步中，您会看到与T节点直接链接的暂定节点（B、C）的状态记录集已更改。此外，由于B的权重较小，它已被选为T节点，其标签已更改为永久（见下文）。
在步骤3中，与步骤2类似，与T节点有直接链接的暂定节点（D、E）的状态记录集已更改。此外，由于D的权重较小，它已被选为T节点，其标签已更改为永久。
在步骤4中，我们没有任何暂定节点，所以我们只需识别下一个T节点。由于E的权重最小，它已被选为T节点。

最后，E是目的地，所以我们在这里停止。

我们到了最后！现在我们必须识别路由。E的前一个节点是D，D的前一个节点是B，B的前一个节点是A。因此，最佳路由是ABDE。在这种情况下，总权重为4 (1+2+1)。

尽管该算法运行良好，但它过于复杂，可能需要路由器长时间处理，从而导致网络效率低下。此外，如果路由器向其他路由器提供错误信息，所有路由决策都将无效。为了更好地理解此算法，这里是用C语言编写的程序源代码

#define MAX_NODES 1024        /* maximum number of nodes */
#define INFINITY 1000000000      /* a number larger than every maximum path */
int n,dist[MAX_NODES][MAX_NODES];  /*dist[I][j] is the distance from i to j */
void shortest_path(int s,int t,int path[ ])
{struct state {                          /* the path being worked on */
int predecessor ;                     /*previous node */
int length                                /*length from source to this node*/
enum {permanent, tentative} label    /*label state*/
}state[MAX_NODES];
int I, k, min;
struct state *
                     p;
for (p=&state[0];p < &state[n];p++){       /*initialize state*/
p->predecessor=-1
p->length=INFINITY
p->label=tentative;
}
state[t].length=0; state[t].label=permanent ;
k=t ;                                                          
/*k is the initial working node */
do{                                                            
/* is  the better path from k? */
for I=0; I < n; I++)                                       
/*this graph has n nodes */
if (dist[k][I] !=0 && state[I].label==tentative){
            if (state[k].length+dist[k][I] < state[I].length){
		       state[I].predecessor=k;
		       state[I].length=state[k].length + dist[k][I]
		    }
}
/* Find the tentatively labeled node with the smallest label. */
k=0;min=INFINITY;
for (I=0;I < n;I++)
     if(state[I].label==tentative && state[I].length <
min)=state[I].length;
     k=I;
	}
state[k].label=permanent
}while (k!=s);
/*Copy the path into output array*/
I=0;k=0
Do{path[I++]=k;k=state[k].predecessor;} while (k > =0);
}

DV 算法

DV算法也称为贝尔曼-福特路由算法和福特-富尔克森路由算法。在这些算法中，每个路由器都有一个路由表，显示其到达任何目的地的最佳路由。页面顶部显示了路由器J的典型图和路由表。

如表所示，如果路由器J想要将数据包发送到路由器D，它应该将它们发送到路由器H。当数据包到达路由器H时，它会检查自己的表并决定如何将数据包发送到D。

在DV算法中，每个路由器都必须遵循以下步骤

它计算与其直接连接的链路的权重，并将信息保存到其表中。
在特定时间段内，它将其表发送给相邻路由器（而非所有路由器），并接收其每个邻居的路由表。
根据其邻居路由表中的信息，它更新自己的路由表。

DV算法最重要的问题之一被称为“计数到无穷大”。让我们通过一个例子来研究这个问题

想象一个如下图所示的网络图。如您在此图中所见，A与网络的其他部分之间只有一个链接。您可以在这里看到所有节点的图和路由表

现在想象一下A和B之间的链接被切断了。此时，B修正其路由表。经过一段时间后，路由器交换它们的路由表，因此B收到了C的路由表。由于C不知道A和B之间的链接发生了什么，它说它有一个到A的链接，权重为2（C到B为1，B到A为1——它不知道B没有到A的链接）。B收到此表后，认为C和A之间存在一个独立的链接，因此它修正了自己的表，并将无穷大更改为3（B到C为1，C到A为2，正如C所说）。路由器再次交换它们的路由表。当C收到B的路由表时，它看到B已将其到A的链接权重从1更改为3，因此C更新其表，并将到A的链接权重更改为4（C到B为1，B到A为3，正如B所说）。

这个过程会循环，直到所有节点发现到A的链接权重为无穷大。这种情况显示在下表中。通过这种方式，专家称DV算法具有收敛速度慢的特点。