18新利最新登入路由算法如何工作| HowStuffWorks吗 - 新利luck18官网-官方网站,18新利最新登入

如果你读过HowStuffWorks的文章18新利最新登入18新利最新登入路由器的工作原理,那么你知道路由器是用来管理网络流量和找到最好的路线发送数据包。但是你有没有想过如何路由器呢?18新利最新登入路由器需要一些关于网络状态信息,以做出决定关于如何以18luck手机登录及在哪里发送数据包。18新利最新登入但是他们18新利最新登入如何收集这些信息?18luck手机登录

恰恰在这篇文章中,我们会发现信息在确定使用路由器发送一个数据包。18luck手机登录

最基本的

路由器使用路由算法找到目的地的最佳路线。当我们说“最佳路线,“我们考虑参数的数量啤酒花(旅行一个数据包从一个路由器或中间点到另一个网络中的),包传输的延时和通信成本。

基于路由器收集网络18新利最新登入的结构信息和分析信息指定的最佳途径,我18luck手机登录们有两个主要的路由算法:全球路由算法和分散式路由算法。在分散式路由算法,每个路由器的信息路由器直接连接到——它不知道网络中的每一台路由器。18luck手机登录这些算法也被称为DV距离向量路由选择算法。在全球路由算法,每个路由器都有完整的信息对所有其他路由器在网络和交通网络的状态。18luck手机登录这些算法也被称为LS(链接状态)算法。在下一节中我们将讨论LS算法。

LS算法

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

确定身体的路由器连接到他们,让他们的IP地址当路由器开始工作时,它首先发送一个“你好”数据包在网络。每个路由器接收这包回复消息,其中包含它IP地址。
测量延迟时间(或任何其他网络的重要参数,如平均流量)的邻居路由器为了做到这一点,路由器发送echo数据包在网络上。每个路由器接收这些包回答回应应答包。往返时间除以2,路由器可以计算延迟时间。(往返时间是衡量当前的网络延迟,发现的时间包反弹一些远程主机。)注意,这一次包括传输和处理时间——时间数据包到达目的地和时间需要接收者处理并答复。
广播的信息在网络上其他路由器18luck手机登录和接收其他路由器的信息在这个步骤中,所有路由器分享他们的知识和广播他们的信息。通过这种方式,每个路由器都可以知道网络的结构和状态。
使用一个适当的算法,确定网络的两个节点之间的最佳路径在这一步中,路由器选择每个节点的最佳途径。他们使用一种算法,如迪杰斯特拉最短路径算法。在这个算法中,一个路由器,根据收集到的信息从其他路由器,构建一个网络图。18luck手机登录这个图表显示了网络中的路18新利最新登入由器的位置及其相互联系。每一个环节与许多称为标记重量或成本。这个数字是延迟时间的函数,平均流量,有时简单的节点之间的跳数。例如,如果有两个节点之间的联系和目的地,路由器选择最低的链接权重。

的迪杰斯特拉算法经过这些步骤:

网络的路由器建立一个图形和标识源和目的节点,例如V1和V2。然后构建一个矩阵,称为“邻接矩阵”。In this matrix, a coordinate indicates weight. For example, [i, j] is the weight of a link between Vi and Vj. If there is no direct link between Vi and Vj, this weight is identified as "infinity."
路由器构建状态记录网络上的每个节点。记录包含三个字段:前任领域——第一个字段显示前面的节点。18新利最新登入长度字段——第二个字段显示重量之和从源节点。18新利最新登入标签字段-最后一个字段显示节点的状态。18新利最新登入每个节点可以有一个状态模式:“永久”或“临时”。
路由器初始化状态记录的参数设置(用于所有节点)和它们的长度设置为“∞”及其标签“试探性”。
路由器设置T-node。例如,如果V1源T-node,路由器更改V1的标签,“永久”。When a label changes to "permanent," it never changes again. A T-node is an agent and nothing more.
路由器更新状态记录设置为所有临时节点与源T-node直接相关。
路由器看着所有的试探性的节点并选择重量V1是最低的一个。然后目的地T-node该节点。
如果这个节点不是V2(目的地),路由器回到步骤5。
如果V2这个节点,路由器提取其前一节点的状态记录集和这直到它到达V1。这个列表显示的节点的最佳路线从V1 V218新利最新登入。

我们将使用这个算法为例在下一页。

例子:迪杰斯特拉算法

这里我们想找到之间的最佳路径和E(见下文)。你可以看到有六个之间可能的途径和E(安倍王牌,ABDE ACDE, ABDCE, ACDBE),很明显,ABDE是最好的路线,因为它的重量是最低的。但生活并不总是那么容易,还有一些复杂的情况下,我们必须使用算法来找到最好的路线。

正如你所看到的第一形象,源节点(A)被选为T-node,所以其标签是永久性的(我们展示永久节点与圈和T-nodes - - >符号)。18新利最新登入
在下一步,你会看到临时节点的状态记录集直接联系T-node (B, C)已经被改变了。也,因为B更少的重量,它被选为T-node及其标签改变了永久的(见下文)。
在步骤3中,在步骤2中,临时节点的状态记录集,直接链接到T-node (D, E),已经改变了。也,因为D少重量,它被选为T-node及其标签已经变成永久性的。
在步骤4中,我们没有任何的节点,所以我们只下T-node识别。E以来最少的重量,它已被选为T-node。

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

我们在结束!现在我们必须确定路线。前面的节点的E D,和之前的节点D是B, a和B之前的节点是ABDE所以最好的途径。在这种情况下,总重量是多少4(1 + 2 + 1)。

尽管这个算法是有效的,它是如此复杂,可能需要很长时间的路由器来处理它,和效率的网络失败。另外,如果其他路由器路由器给了错误的信息,所有的路由决策将是无效的。18luck手机登录更好地理解这个算法,这是源程序由C:

#定义MAX_NODES 1024 / *最大数量的节点* / #定义无穷1000000000 / *数量大于每一个最大路径* /整数n, dist [MAX_NODES] [MAX_NODES];/ * dist[我][j]是距离我* /空白shortest_path (int, int, int[]道路){结构状态{/ * * / int前任工作的路径;/ *前一节点* / int长度/ *长度从源到这个节点* / enum{永久性的,试探性的}标签/ *标签状态* /}[MAX_NODES];int I、k、最小值;结构状态* p;(p =状态[0];p <国家[n]; p + +){/ *初始化状态* / p - >前任= 1 p - >长度=无穷大p - >标签=初步;}状态[t] . length = 0;国家[t]。标签=永久;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算法也被称为bellman路由算法和Ford-Fulkerson路由算法。在这些算法中,每个路由器的路由表显示了它任何目的地的最佳路线。18新利最新登入路由器J的典型图形和路由表显示在页面的顶部。18新利最新登入

如表所示,如果路由器J想要包18新利最新登入路由器D,它应该寄给路由器H .当数据包到达路由器H,它检查自己的表,并决定如何将数据包发送到D。

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

它重要的链接直接连接到它的重量和保存信息表。18luck手机登录
在特定的时间内,其表发送给它的邻居路由器(不是所有路由器)和接收每个邻国的路由表。
基于信息的邻居的路由表,更18luck手机登录新自己。

最重要的一个问题,DV算法被称为“数到无穷大”。让我们来看看这个问题用一个例子:

想象一个网络图如下所示。18新利最新登入当你看到这张图,只有一个一个和网络的其他部分之间的联系。在这里你可以看到所有节点的图和路由表:

网络图和路由表”width= — 网络图和路由表
18新利最新登入HowStuffWorks.com

现在想象一下,A和B之间的联系被切断。在这个时候,纠正其表。具体的时间后,路由器交换他们的表,所以B接收C的路由表。自C不知道发生了什么事A和B之间的联系,它说它有一个链接到一个2的重量(1 C B,和1 B——它不知道B没有链接),B接收这个表并认为有一个单独的C和之间的联系,所以它纠正了表和变化无穷3 (1 B, C,和2 C, C说)。再次,路由器交换他们的桌子。当C收到B的路由表,它看到B改变了链接的重量从1到3,所以C更新表和链接的重量变化4 (1 C B和3 B, B表示)。

这个过程循环直到所有节点发现链接的权重是无穷。这种情况如下表所示。18新利最新登入通过这种方式,专家说DV算法有一个收敛速度慢。