路由选择原理与路由算法分析

2017-06-27 16:29 阅读 982 次 评论 0 条

"路由""交换"Route的两大基本功能,通过查找路由表以获取最佳路径信息的过程被称为"路由",而将从接收端口进来的数据在输出端口重新转发出去的功能称之为"交换"。本文主要针对路由器的"路由"功能展开。

路由选择的基本原理

通信子网为网络中源节点到目的节点之间IP信息包的传递提供了多条传输路径,当我们在网络中收到一个分组后,就要确定其下一个结点的传输路径,这就是IP路由选择(网络层)

我们模拟一个场景:处于LAN中的Host_A要向处于Internet中的Host_B发送数据包,中间可能有多个路由器工作,形成了多条线路。

在上图中,Route1-2-4与Route1-3-4分别是两条不同的路由路径,而路由选择没有谁好谁坏,只有哪种更适合。

路由器是互联网中的中转站,网络中的数据包通过路由器转发到目的网络,在路由器的内部会有一份路由表。路由表中包含了该路由器掌握的目的网络地址以及通过此路由器到达这些网络的最佳路径,如某个接口或下一跳地址。

下图就是基本的路由选择原理,从源主机到目标主机的路由过程:

当路由器从某个接口收到一个数据包时,路由器会首先查看路由器中是否包含目的网络地址,找到数据包的目的网络所对应的接口,从该接口转发出去,最终打到目标主机。

Linux与Windows下的路由表

在Linux(CentOS)中,我们可以使用route命令来查看路由表:

在Windows下,我们使用route print查看路由表:

鉴于安全原因,这里不再贴图,感兴趣可以自行尝试,参数与Linux基本相同,不再阐述。

常见路由表生成算法

路由算法在计算最佳路径时所考虑的因素被称为评价因子(Metric)。常见的评价因子如:带宽、可靠性、延时、负载、跳数和费用等。

距离向量算法(DV)

距离矢量路由协议的典型例子包括消息协议(RIP)和内部网关路由协议(IGRP)等。

链路向量选路算法

链路状态路由协议的典型例子有开放最短路径优先协议(OSPF)等。

☛ Dijkstra算法

① 路由器建立一张网络图,并且确定源节点V1和目的节点V2,然后路由器建立一个矩阵,称为"邻接矩阵"。在这个矩阵中,各矩阵元素表示权值。例如:[i,j]是节点Vi与Vj之间的链路权值,若两个节点之间没有链路直接相连,它的权值设为无穷大。

② 路由器为网络中的每一个节点建立一组状态记录,此记录包括三个字段:

③ 路由器初始化(所有结点)状态记录集参数,将它们的长度设定为"无穷大",标号设定为"暂时"。

④ 路由器设置一个T节点。例如:如果设V1是源节点,路由器将V1的标号更改为"永久"。当一个标号更改为"永久"后,将不再改变,一个T节点仅仅是一个代理。

⑤ 路由器更新与源T节点直接相连的所有暂时节点的状态记录集。

⑥ 路由器在所有的暂时性节点中选择距离V1的权值最低的结点,称为新的T结点。

⑦ 如果这个节点不是V2(目的节点),路由器返回步骤⑤。

⑧ 如果节点时V2,路由器则向前回溯,将它的前序节点从状态记录集中提取出来,直到提取到V1为止,这个节点列表便是V1到V2的最佳路径。

LS路由算法

① 确认在物理上与之相连的路由器并获取它们的IP地址。当一个路由器开始工作后,它首先向整个网络发送一个"HELLO"分组数据包。每个接收到数据包的路由器都返回一条消息,其中包含它自身的IP地址。

② 测量相邻路由器的延时(或其他重要的参数)。为做到这一点,路由器向整个网络发送相应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包,将路程往返时间除以2,路由器便可以计算出延时。该时间包括了传输和处理两部分的时间,也就是将分组数据包发送到目的地的时间以及接收方处理分组数据包和应答的时间。

③ 向网络中的其他路由器广播自己的信息,同时也接收其他路由器的信息。

④ 使用一个合适的算法,确定网络中两个节点之间的最佳路由。

在这一步中,路由器选择通往每一个节点的最佳路由。它们使用一个算法来实现这一点,如Dijkstra最短路径算法。在这个算法中,一个路由器通过收集到的其他路由器的信息,建立一个网络图。这个图描述网络中的路由器的位置以及它们之间的链接关系。每个链接都有一个数字标注,称为权值或成本。这个数字是延时和平均流量的函数,有时它仅仅表示节点间的跃点数。例如,如果一个节点与目的地之间有两条链路,路由器将选择权值最低的链路。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:路由选择原理与路由算法分析 | 术与道的分享
1024do.com导航_术与道导航平台

发表评论


表情