路线选择和路线选择算法发挥着重要作用。

• 默认路由器 : 主机通常直接链接到一个名为主机默认路由器的路由器, 也称为主机初始路由器 。
• 源代码路由器:源主机的默认路由器 。
• 目标路由器是主机的默认路由器 。

• 选择路由器用于确定从源主机到目的地主机的路径,该路径可归属于从源路由器到目的地路由器的路径。
• 路由选择算法通过运行、交换和计算信息,在网络路由器中发挥作用,然后用于设置路由器再版。

路由选择算法的分类

中央全球选择路线的算法

• 中央全球选择路线的算法：通过让每个结点向网络中所有其他结点广播链路状态分组（每个链路状态分组包含它所连接的链路的特征和费用），这样每个节点都可以获得该网络的等同的、完整的视图。每个节点都可以利用这些完整的网络信息来执行路由选择算法。LS（链路状态）算法便是一种中央全球选择路线的算法。
  我们用爪哇模拟LS算法:在图中描述的网络中,路由器0是源路由器,它计算出从源路由器到网络中所有其他路由器的最短路径。
  

测试结果

分散式路由选择算法

• 分布式路线选择算法:无节点拥有关于所有网络连接费用的全面信息,每个节点只有在知道与它直接连接的费用的情况下才能开始工作。
• DV(远距离矢量)方法是一种分散的路线选择系统。
• DV算法的特点
  1个分布点:每个节点从一个或多个直接相连的邻居那里获得信息,进行计算,并将结果分发给邻居。
  第二轮:在邻居之间无法传递更多信息之前,该程序会重复。
  3种差异:不需要所有节点以一致的方式相互沟通。

DV算法的原理

• Dx(y) = minc(x,v)+Dv(y) 路由器 x 和路由器 y 之间最短连接点的成本
  路由器 x 至邻居路由器的路线成本为 c (x,v)。
  Min 指所有路由器 x 的邻居路由器(即所有与路由器 x 直接相连的路由器)。
• Dx(远距离矢量)表示从路由器x到所有其他路由器y(N)的估计矢量。
  Dx(y) 表示路由器x和路由器y之间最短路线的费用。
  表示在特定网络中收集路由器。
• 在DV算法中,每个路由器x必须保存下列信息:
  ①c(x,v)
  Dx [Dx(y) : yN] = 2路由器 x 远距离矢量 Dx
  每个路由器邻居的远程矢量 v x Dv [Dv(y) : yN]
• 算法流程
  
• 让我们从一个例子的镜头来看算法过程。
  
  
  如算法流程图所示,在初始化阶段,对于路由器xx,如果y直接与x直接相连,Dx(y)首先转换为c(x,y)或Dx(y)或Dx(y),最初变成无限,这样路由器x的距离矢量可以从 Dx(y) 中导出,然后将x的距离矢量传递给路由器x的每个相邻路由器,允许访问图表的第一个列和进程1
  如算法流程图所示,当路由器x与其邻居之一之间的费用变化或从邻居的路由器收到远程矢量信息时,路由器x将更新其远程矢量,如果更新后x变化的距离矢量,x将他的新远程矢量传送给邻居的所有路由器。
  抵达第3栏后重新计算,路由器x、y和z没有变化,算法已经稳定。
• 当从邻居路由器获得远程矢量信息时,路由器和邻居路由器之间的成本变化或更新邻居路由器的矢量列表非常值得注意。上述图表中的第二个过程是邻居路由器的远程矢量信息的结果。当路由器的成本与邻居路由器的成本不同时会发生什么情况?
• 路由器与其邻居之一之间的时数成本不尽相同(在此,只考虑y至z至目的地x之间的距离表中适当的表格项目)。
  
• T. 0,路由注意到连接成本的变化(从4到1),更新了远程矢量,并通知了邻居。
• T1,z从y得到更新,并更新了距离表,计算新的最低成本为x(从成本5到成本2),并将其新的远程矢量送至邻国。
• y 因为最低成本没有改变, y不向 z 发送任何信息 。
• 当路由器和其邻居之一之间的成本增加时(目前只有y至z至目的地x的距离表的适当表格项目)
  
  Dy(x)=4 在成本变化之前, Dy(z)=1, Dz(y)=1, Dz(x)=5;
  费用变化之后，y检测到费用的变化，开始更新自己的距离向量Dy(x)=min{c(y,x)+Dx(x),c(y,z)+Dz(x)}=min{60+0,1+5}=6，并且向z通知这个变化。如果y需要向x发送一条消息，y会选择通过z路由到x（因为在y看来，y->x的费用是60，而y->z->x的费用是6），当消息到达z时，z又会选择通过y路由到x（因为此时在z看来，z->x的费用是50，而z->y->x的费用是c(z,y)+Dy(x)=1+6=7）,如此往复，经过44次迭代（z发现z->y->x的费用大于50）后，z会直接将这个消息发送到x。
  连带费增长的坏消息是增长缓慢!
• 处理无穷无尽数字的方法:日益严重的有害逆转
  这个概念是直截了当的:如果z决定把y-route带到目的地x,z-通知y,z-x的距离是无限的,也就是说,既然你相信z-x没有通往x的路径,y 只要z继续选择y-route到x,从而撒谎,y 就不会试图选择xx。
  使用有害的反向程序,有三个或三个以上节点(而不仅仅是两个直接相连的邻居)的电路是无法探测到的。

中央全球选择路线的算法和分散式路由选择算法的对比

• 信件的复杂性。 LS 方法要求网络中的每个节点知道网络中每个链接的成本。 这意味着发送 O (N) 信息( N 表示路由器和 E 表示链接), 如果链接的成本发生变化, 就需要向所有节点发送新的链接 。 当连接成本发生变化时, DV 算法只有在新链接成本导致与链接最低成本路径连接的节点发生变化时才传播更新的链接成本 。
• 趋同率(算法稳定速度):LS算法的时间复杂性是O(N2)(N代表路由器的数量),但DV方法难以恢复,可能会遇到无限的计算问题。
• 强力:由于一次总付方法在某种程度上是孤立地计算出来的,因此它提供了一定程度的弹性。 在DV算法中,一个节点可以将其不准确的最低成本路径通知任何或所有目的地节点。

层次路由选择

• 为什么你要添加路线选择层?
  1 如果网络中的所有路由器都相等,随着路由器数量的增加,与分配费用的变化相对应,路由器之间的费用将非常高,因此没有剩余能力交付数据组。
  应允许2家公司酌情管理和维护其网络,并与其他外部网络连接。
• 这两个问题可以通过将路由器纳入自治系统来解决。
  自主系统内部路线选择协议:同一系统的所有路由器都使用相同的路线选择方法(如LS或DV算法),并互相了解对方的存在,在自主系统中运行的路线选择算法被称为自主系统内部路线选择程序。
  网关路由器负责向Ben AS以外的目的地转运集群。
  自主系统路由选择协议:从邻近的AS获取无障碍信息,并在AS中向所有路由者传播,这是自主系统路由选择协议将处理的两个目标。

本文由 在线网速测试 整理编辑，转载请注明出处，原文链接：https://www.wangsu123.cn/news/14223.html。