路由表及路由器的选择算法

标准的路由表

1、下一站选路的基本思想

路由表仅指定从该路由器到目的地路径上的下一步，而不知道到达目的地的完整路径。

2、标准的IP路由表包含许多(N,R)对序偶

N:目的网络的IP地址

R：到N路径上的下一个路由器的IP地址。

基本的下一站路由选择算法：

RouteDatagram(Datagram, RoutingTable)

{

从Datagram中提取目的IP地址D，计算netid网络号N;

if N与路由器直接连接的网络地址匹配

Then 在该网络上直接投递(封装、物理地址绑定、发送等)

ElseIf RoutingTable 中包含到N的路由

Then 将Datagram发送到RoutingTable中指定的下一站

Else 路由选择错误

}

静态路由和动态路由

静态路由是由人工建立和管理的，不会自动发生变化，必须手工更新以反映互联网拓扑结构或连接方式变化。

静态路由的特点：

优点：安全可靠、简单直观，避免了动态路由选择的开销。

劣势：不适用于复杂的互联网结构：建立和维护工作量大，容易出现路由环。

互联网出现故障，静态路由不会自动做出更改

适用环境：不太复杂的互联网结构

动态路由可以通过自身学习，自动修改和刷新路由表。动态路由要求路由器之间不断的交换路由信息。

动态路由的特点：

优点：更多的自主性和灵活性

劣势：交换路由信息需要占用网络带宽;路由表的动态修改和刷新需要占用路由器的内存和CPU处理时间，消耗路由器的资源。

适用环境：拓扑结构复杂、网络规模庞大的互联网自动排除错误路径，自动选择性能更优的路径

路径度量值metric

metric表征路径优劣的数值，metric越小，说明路径越好。

metric的计算可以基于路径的一个特征，也可以基于路径的多个特征。

跳数：IP数据报到达目的地必须经过的路由器个数。

带宽：链路的数据能力。

延迟：将数据从源送到目的地所需的时间。

负载：网络中(如路由器中或链路中)信息流的活动数量

可靠性：数据传输过程中的差错率

开销：一个变化的数值，通常可以根据带宽、建设费用、维护费用、使用费用等因素由网络管理员指定。

路由选择协议：

1、使用动态路由的基本条件

路由器运行相同的路由选择协议，执行相同的路由选择算法。

2、广泛采用的路由选择协议

路由信息协议RIP：利用向量-距离算法

开放式最短路径优先协议OSPF：利用链路-状态算法

3、路由收敛

含义：互联网中的所有路由器都运行着相同的、精确地、足以反映当前互联网拓扑结构的路由信息。

快速收敛是路由选择协议最希望具有的特征。

路由选择算法：

1、向量-距离路由选择算法

基本思想：路由器周期性地向其相邻路由器广播自己知道的路由信息，用以通知相邻路由器自己可以到达的网络以及到达该网络的距离。相邻路由器可以根据收到的路由信息修改和刷新自己的路由表。

优点：算法简单、易于实现

缺点：慢收敛问题：路由器的路径变化需要像波浪一样从相邻路由器传播出去，过程缓慢

需要交换的信息量大：与自己的路由表的大小相似

适用环境：路由变化不剧烈的中小型互联网

2、链路-状态路由选择算法

基本思想：互联网上的每个路由器周期性地向其它路由器广播自己与相邻路由器的连接关系，互联网上的每个路由器利用收到的路由信息画出一张互联网拓扑结构图。利用画出的拓扑结构图和最短路径优先算法，计算自己到达各个网络的最短路径。

OSPF路由选择协议

优点：收敛速度快;支持服务类型选择;提供负载均衡和身份认证。

缺点：要求较高的路由器处理能力;一定的带宽需求。

适用环境：规模庞大、环境复杂的互联网

两者原理性差异：

向量-距离路由选择算法：不需要路由器了解整个互联网的拓扑结构;通过相邻的路由器了解到达每个网络的可能路径。