网页设计制作网站图片,3322怎么做网站,wordpress接单修改任务,沈阳网站的优化基础知识路由器使用
路由算法来找到到达目的地的最佳路由。当我们说“最佳路由”时#xff0c;我们考虑的参数包括诸如跳跃数#xff08;分组数据包在网络中从一个路由器或中间节点到另外的节点的行程#xff09;、延时以及分组数据包传输通信耗时。 关于路由器如何收集网…基础知识路由器使用
路由算法来找到到达目的地的最佳路由。当我们说“最佳路由”时我们考虑的参数包括诸如跳跃数分组数据包在网络中从一个路由器或中间节点到另外的节点的行程、延时以及分组数据包传输通信耗时。 关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由我们有两种主要的路由算法总体式路由算法和分散式路由算法。采用分散式路由算法时每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV距离向量算法。采用总体式路由算法时每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS链路状态算法。我们将在下一节讨论LS算法。 LS算法 采用LS算法时每个路由器必须遵循以下步骤 确认在物理上与之相连的路由器并获得它们的IP地址。 当一个路由器开始工作后它首先向整个网络发送一个“HELLO”分组数据包。每个接收到数据包的路由器都将返回一条消息其中包含它自身的IP地址。 测量相邻路由器的延时或者其他重要的网络参数比如平均流量。 为做到这一点路由器向整个网络发送响应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包。将路程往返时间除以2路由器便可以计算出延时。路程往返时间是网络当前延迟的量度通过一个分组数据包从远程主机返回的时间来测量。请注意该时间包括了传输和处理两部分的时间——也就是将分组数据包发送到目的地的时间以及接收方处理分组数据包和应答的时间。 向网络中的其他路由器广播自己的信息同时也接收其他路由器的信息。 在这一步中所有的路由器共享它们的知识并且将自身的信息广播给其他每一个路由器。这样每一个路由器都能够知道网络的结构以及状态。 使用一个合适的算法确定网络中两个节点之间的最佳路由。 在这一步中路由器选择通往每一个节点的最佳路由。它们使用一个算法来实现这一点如Dijkstra最短路径算法。在这个算法中一个路由器通过收集到的其他路由器的信息建立一个网络图。这个图描述网络中的路由器的位置以及它们之间的链接关系。每个链接都有一个数字标注称为权值或成本。这个数字是延时和平均流量的函数有时它仅仅表示节点间的跃点数。例如如果一个节点与目的地之间有两条链路路由器将选择权值最低的链路。 Dijkstra算法执行下列步骤 路由器建立一张网络图并且确定源节点和目的节点在这个例子里我们设为V1和V2。然后路由器建立一个矩阵称为“邻接矩阵”。在这个矩阵中各矩阵元素表示权值。例如[i, j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连它们的权值设为“无穷大”。 路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段 前序字段——表示当前节点之前的节点。 长度字段——表示从源节点到当前节点的权值之和。 标号字段——表示节点的状态。每个节点都处于一个状态模式“永久”或“暂时”。 路由器初始化所有节点的状态记录集参数将它们的长度设为“无穷大”标号设为“暂时”。 路由器设置一个T节点。例如如果设V1是源T节点路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后它将不再改变。一个T节点仅仅是一个代理而已。 路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。 路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。 如果这个节点不是V2目的节点路由器则返回到步骤5。 如果节点是V2路由器则向前回溯将它的前序节点从状态记录集中提取出来如此循环直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。 这些步骤的流程图如下 routing-algorithm1.gif (40.56 KB) 2008-10-19 19:34 示例Dijkstra算法我们想找到A与E下图之间的最佳路由。可以看到A与E之间有六条可能路径ABE、ACE、ABDE、ACDE、ABDCE、ACDBE很明显ABDE是最佳路由因为它的权值最小。但是实际情况并非总是如此简单有很多复杂的情形需要使用算法来找到最佳路由。 1、如下图所示源节点(A)被选为T节点所以它的标号是永久我们将永久性节点以实圈标注T节点以--符号标注。 routing-algorithm3.gif (2.52 KB) 2008-10-19 19:45 2、在这一步中直接链接到T节点的暂时性节点(B, C)的状态记录集已经被修改。同时由于B有更小的权值所以它被选作T节点其标号被改为永久如下图所示。 routing-algorithm4.gif (2.97 KB) 2008-10-19 19:45 3、与步骤2类似在这一步中直接链接到T节点的暂时性节点(D, E)的状态记录集已经被修改。同时由于D有更小的权值所以它被选作T节点其标号被改为永久如下图所示。 routing-algorithm5.gif (3.08 KB) 2008-10-19 19:47 4、在这一步中已经没有任何暂时性节点所以我们仅仅需要确认下一个T节点。因为E有最小权值所以它被选作T节点。 routing-algorithm6.gif (3.11 KB) 2008-10-19 19:49 5、E是目的节点所以我们在这里停止。 我们已经到达了终点现在我们需要确定路由。E的前序节点是DD的前序节点是BB的前序节点是A。所以最佳路由是ABDE。在这个案例中权值和为4(121)。 虽然这个算法工作良好但是它非常复杂以致于路由器需要花费大量时间进行处理网络的性能因此下降了。同样如果一个路由器将错误的信息发送给其他路由器那么所有的路由决定都将是无效的。为了更好的理解这个算法下面给出由C语言编写的源代码 引用: #define MAX_NODES 1024 /*最大节点数 */ #define INFINITY 1000000000 /*比所有最大路径都大的数 */ int n,dist[MAX_NODES][MAX_NODES]; /*dist[I][j] 是从 i 到 j 的距离*/ void shortest_path(int s,int t,int path[ ]) {struct state { /*当前计算的路径 */ int predecessor ; /*前序节点 */ int length /*从源节点到当前节点的长度*/ enum {permanent, tentative} label /*标号状态*/ }state[MAX_NODES]; int I, k, min; struct state * p; for (pandstate[0];p predecessor-1 p-lengthINFINITY p-labeltentative; } state[t].length0; state[t].labelpermanent ; kt ; /* k 是初始工作节点 */ do{ /*是从 k 开始的一条更好路径么*/ for I0; I /*图有 n 个节点 */ if (dist[k][I] !0 andand state[I].labeltentative){ if (state[k].lengthdist[k][I] state[I].length){ state[I].predecessork; state[I].lengthstate[k].length dist[k][I] } } /*找到具有最小权值的暂时性节点。*/ k0;minINFINITY; for (I0;I 0;I )
