4.4 路由算法与路由协议

静态路由与动态路由，距离向量算法与链路状态算法，层次路由与自治系统，RIP、OSPF 与 BGP 三种路由协议的比较。

路由算法

路由选择协议的核心是路由算法，即需要何种算法来获得路由表中的各个项目。路由算法的目的很简单：给定一组路由器以及连接路由器的链路，路由算法要找到一条从源路由器到目的路由器的”最佳”路径（如距离最短、时延最小、费用最低）。

• 静态路由算法（非自适应路由算法）：由网络管理员手工配置路由信息。大型和复杂的网络环境通常不宜采用；
• 动态路由算法（自适应路由算法）：路由器上的路由表项是通过相互连接的路由器之间彼此交换信息，然后按照一定的算法优化出来的，而这些路由信息会在一定时间间隙里不断更新，以适应不断变化的网络，随时获得最优的寻路效果。常用的动态路由算法可分为两类：距离向量路由算法和链路状态路由算法。

距离向量路由算法

在距离向量路由算法中，所有结点都定期地将它们的整个路由选择表传送给所有与之直接相邻的结点。路由表包含：每条路径的目的地（另一结点）和路径的代价（距离）。

• 当 $x$ 收到相邻结点 $v$ 的距离向量后，按 Bellman-Ford 方程更新：$D_x(y) = \min_v \{ c(x, v) + D_v(y) \}$；
• 在距离向量路由算法中，所有结点都必须参与距离向量交换，以保证路由的有效性和一致性；
• 距离向量路由算法的实质是：迭代计算一条路由中的站段数或延迟时间，从而得到到达一个目标的最短（最小代价）通路。它要求每个结点在每次更新时都将它的全部路由表发送给所有相邻的结点。显然，更新报文的大小与通信子网的结点个数成正比，大的通信子网将导致很大的更新报文。

链路状态路由算法

链路状态路由算法要求每个参与该算法的结点都具有完全的网络拓扑信息，它们执行下述两项任务：第一，主动测试所有邻接结点的状态；第二，定期地将链路状态传播给所有其他结点（洪泛）。每个结点得到全网拓扑后，用 Dijkstra 最短路径算法（见数据结构 · 最短路径）计算出到其他各结点的最短路径。

层次路由

当网络规模扩大时，路由器的路由表成比例地增大。这不仅会消耗越来越多的路由器缓冲区空间，而且需要用更多 CPU 时间来扫描路由表，用更多的带宽来交换路由状态信息。因此路由选择必须按照层次的方式进行。因特网将整个互联网划分为许多较小的自治系统（AS），每个自治系统有权自主地决定本系统内应采用何种路由选择协议。

• 内部网关协议（IGP）：在一个自治系统内部使用的路由选择协议，与互联网中其他自治系统选用什么路由选择协议无关，如 RIP、OSPF；
• 外部网关协议（EGP）：若源站和目的站处在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中，如 BGP。

路由信息协议 RIP

RIP 是一种分布式的基于距离向量的路由选择协议，其最大优点就是简单。

• 每个路由器维护从它自己到其他每个目的网络的唯一最佳距离记录（即一组距离）；
• 距离也称跳数（Hop Count），规定从一个路由器到直接连接网络的距离为 1，每经过一个路由器，距离加 1；
• RIP 认为好的路由就是它通过的路由器的数目少，即”距离短”。RIP 允许一条路径最多只能包含 15 个路由器，因此距离为 16 时表示网络不可达——RIP 只适用于小型互联网；
• 每 30 秒和相邻路由器交换一次信息；交换的是本路由器所知道的全部信息，即自己的路由表；
• RIP 是应用层协议，它使用 UDP（端口 520）传送数据。

RIP 存在的一个问题是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有路由器（慢收敛）。可以使用水平分割（不把从某邻居学到的路由再通告回给该邻居）、毒性逆转等方法缓解。

开放最短路径优先 OSPF

OSPF 是使用分布式链路状态路由算法的典型代表，也是内部网关协议的一种。OSPF 与 RIP 相比有以下 4 点主要区别：

1. OSPF 向本自治系统中的所有路由器发送信息，这里使用的方法是洪泛法；而 RIP 仅向自己相邻的几个路由器发送信息；
2. 发送的信息是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息；而 RIP 发送的信息是本路由器所知道的全部信息；
3. 只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息，并且更新过程收敛得快，不会出现 RIP”坏消息传得慢”的问题；而在 RIP 中，不管网络拓扑是否发生变化，路由器之间都会定期交换路由表的信息；
4. OSPF 是网络层协议，它不使用 UDP 或 TCP，而直接用 IP 数据报传送（协议字段为 89）；而 RIP 是应用层协议，在传输层使用 UDP。

此外，OSPF 还允许对每条路由设置成不同的代价（多种度量），对于同一个目的网络可以有多条相同代价的路径（负载平衡）；为了使 OSPF 能够用于规模很大的网络，OSPF 将一个自治系统再划分为若干个更小的范围，称为区域（主干区域 + 其他区域），洪泛只在区域内部进行。

边界网关协议 BGP

BGP 是不同自治系统的路由器之间交换路由信息的协议，是一种外部网关协议。边界网关协议常用于互联网的网关之间。

• 因特网的规模太大，使得自治系统之间路由选择非常困难；对于自治系统之间的路由选择，要寻找最佳路由是很不现实的；自治系统之间的路由选择必须考虑有关策略。因此，BGP 只能力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非寻找一条最佳路由；
• BGP 采用的是路径向量路由选择协议：BGP 发言人交换的信息是到达某个网络所要经过的一系列 AS；
• BGP 是应用层协议，它是基于 TCP 的（端口 179）；
• 每个自治系统的管理员要选择至少一个路由器作为该自治系统的”BGP 发言人”；
• BGP 交换路由信息的结点数量级是自治系统数的量级，这要比这些自治系统中的网络数少很多。

即时练习