路由协议与路由选择算法优化

2023-06-26 理论教育版权反馈

【摘要】：选路策略包括静态路由选择以及各种动态路由协议。本小节介绍路由器中完成选路机制功能的路由选择算法及完成选路策略功能的路由协议。各个路由器根据收到的信息，重新计算到各目的节点的距离，并对自己的路由表进行修正。图6.20RIP算法更新路由表示例OSPF的提出主要是为了克服RIP的缺陷。

路由器要实现数据转发的功能，至少需要完成以下两个工作。

①选路策略。选路策略指根据数据包的目的地和网络的拓扑结构选择一条最佳路径，把对应不同目的地的最佳路径存放在路由表中，及建立并维护路由表。选路策略包括静态路由选择以及各种动态路由协议。

②选路机制。选路机制指查询路由表从而决定向哪个接口转发数据，并执行相应的操作。即如何根据路由表内容转发数据包。

选路策略只影响路由表的内容，如对同一个目的IP 地址来说，由于选路策略的不同，最佳路径可能会不一样，但这并不影响选路机制的执行过程，只是会对其执行的结果产生影响。

本小节介绍路由器中完成选路机制功能的路由选择算法及完成选路策略功能的路由协议。

1.路由选择算法

路由器在收到数据包之后要根据查询路由表的结果对其进行转发。根据该数据包的目的主机与本路由器节点是否处于同一个物理网络，分组转发可以分为直接转发和间接转发。在直接转发中，目的主机与本路由器处于同一个物理网络，此时可以将分组封装在物理帧中，直接发送到目的主机。在间接转发中，由于目的主机与本路由器不在同一个物理网络中，需要按照路由表查询得到下一跳路由器，并对应转发分组。

在路由表中，还有两类特殊的路由，即默认路由（Default Routing）和特定主机路由（Hostspecific Routing）。选路时，如果没有在路由表中搜索到与目的地址匹配的表项，那么可以将该分组转发到一个默认的下一跳路由器上。这就是默认路由，由此可以减小路由表的规模，提高查表效率。此外，一般而言路由表的表项是基于网络号的，但有时为了某些特殊目的（如管理维护等），也允许在路由表中使用主机地址作为表项，为特定主机指定特定的路由通路，这就是特定主机路由。

在路由器中的选路算法可以总结如图6.19所示。

pagenumber_ebook=144,pagenumber_book=131

图6.19　选路算法

2.路由协议

互联网中的路由协议是指路由器获得对网络拓扑结构的认知，并为数据包选择正确传输路径的方法或者策略。一个理想的路由协议至少应该具备以下特征。

①完整性和正确性，即每个路由器中的路由表都必须给出到所有可能目的节点的下一跳应怎样走，且给出的走法是正确的。

②简单性，即路由选择的计算不应使网络通信量增加太多的额外开销。

③健壮性，主要指当某些节点、链路出现故障不能工作，或故障恢复后投入运行，算法能及时改变路由。

④公平性，即算法对所有用户都是平等的。

⑤最佳性，即以最低的成本来实现路由算法。

由于互联网规模太大、分布范围太广，路由表中对应每一个目的网络都有一个条目是不可能的，同样，也不可能采用一个全局的路由算法或协议。因此，Internet将整个网络划分为若干个相对自治的局部系统，即自治系统（AS，Autonomous System）。自治系统可以定义为同一机构下管理的路由器和网络的集合。

对应的路由协议可以分为内部网关协议（IGP，Interior Gateway Protocol）和外部网关协议（EGP，Exterior Gateway Protocol）两大类。内部网关协议是用于自治系统内部的动态路由协议，包括路由信息协议（RIP）、开放最短路径优先（OSPF）、OSI的IS-IS和Cisco路由器系统中的增强型内部网关路由选择协议（EIGRP，Enhanced Interior Gateway Routing Protocol）等；而外部网关协议则是用于自治系统之间拓扑信息交换的路由协议，包含边界网关协议（BGP）等。

为了降低数据包在网络中的传输开销和时延，要求为数据选择的路径是最短的。这里的“最短”在不同的场合具有不同的含义，它可以是跳数的多少、物理距离的长短或者时延的大小等。互联网中使用的各种路由协议或者路由算法，其根本目的就是寻找源节点和目的节点之间最短的一条路径，即最短路由。互联网的复杂性使得当前使用的路由协议主要是动态的、分布式的。目前互联网上的动态路由协议主要基于两种动态分布式路由选择算法：距离矢量路由算法和链路状态路由算法。RIP和BGP使用距离矢量路由算法，OSPF使用链路状态路由算法。

下面对代表性的RIP和OSPF路由协议进行简要介绍。

在各种内部网关协议中，RIP是出现最早，也是使用时间最长的协议之一，它使用距离矢量算法来计算路由。具体来说，各个路由器都维持一个距离矢量表，对每个目的节点都有一个对应的表项，包括到该目的节点最短路径上的下一个路由器和到该目的节点的最短路径长度两项内容。路由器周期地和相邻路由器交换路由表中的信息，即向邻居路由器发送路由表的全部或部分。各个路由器根据收到的信息，重新计算到各目的节点的距离，并对自己的路由表进行修正。这样使得每一个路由器都可以知道其他路由器的情况，并形成关于网络“距离”的累积透视图，并据此更新路由表。RIP的优点是易于实现，但难以适应网络拓扑的剧烈变动或者大型的网络环境。图6.20给出了一个RIP算法更新路由表的例子。在图6.20（a）中，路由器R1直接连接网络N1，可以实现直接转发，对应发出的距离向量消息中记为{目的网络：N1，开销：0}。此处使用转发次数代表对应的最短路径长度，即开销。而此时，路由器R2的路由数据库中记录，到达N1的路由是下一跳经过R6转发，对应开销为5。当R2接收到R1发出的距离向量更新消息之后，发现由本节点到达N1，可以经过R1，由于R1和R2相邻，因此对应开销为1，小于原有记录的开销值5。由此，路由器R2更新本地路由数据库，如图6.20（b）所示，并向邻居发送更新的距离向量消息，其中表项写明{目的网络：N1，开销：1}。

pagenumber_ebook=146,pagenumber_book=133

图6.20　RIP算法更新路由表示例

OSPF的提出主要是为了克服RIP的缺陷。在网络中，每个OSPF 路由器都维护一个用于跟踪网络状态的链路状态数据库，内容是反映路由器状态的各种链路状态通告，包括路由器可用接口、已知可达路由和链路状态信息。各OSPF路由器都会主动测试所有与之相邻的路由器的状态，并根据测试结果设置相关链路的状态。在发送路由更新消息时，路由器将向全网发布链路状态分组（LSP），即{源路由器标识符，相邻路由器标识符，二者之间链路费用}。这样，网络中每个路由器就得到了一张整个网络拓扑结构的图，再利用最短路由选择算法（详见5.2.2节）计算所有路由，并写到路由表中。OSPF 能够及时反映网络拓扑结构的变化，收敛速度很快，对应开销较小，适用于规模较大及拓扑变化比较快的网络，但对处理器性能要求比较高，占用的网络带宽比较多。在实际应用中，考虑到网络规模和算法效率，可以将网络分成不同的区域，如图6.21所示。每个区域都有边界路由器（ABR），各个ABR 彼此相连构成骨干区域，实现跨区域的通信。每个区域内部的路由器之间互相发布LSP，不同区域之间只需要传输概括性的路由消息即可。

pagenumber_ebook=146,pagenumber_book=133

图6.21　OSPF算法示例

路由协议与路由选择算法优化

相关推荐