“网络工程师培训”基础教程：路由的基本概念及算法

什么是路由

在基于 TCP/IP 的网络中，所有数据的流向都是由IP地址来指定的，网络协议根据报文的目的地址将报文从适当的接口发送出去。而路由就是指导报文发送的路径信息。

就像实际上生活中交叉路口的路标一样，路由信息在网络路径的交叉点（路由器）上标明去往目标网络的正确途径，网络层协议可以根据报文的目的地查找到对应的路由信息，把报文按正确的途径发送出去。

一般一条路由信息至少包含以下几方面内容：目标网络，用以配置报文的目的地址，进行路由选择；下一跳，指明路由的发送路径；Metric、路由权，标示路径的好环，是进行路由选择的标准。

例如，在上图中路由器上有一条去往目标网络 N 的路由，下一跳是R1。所有经过此路由器的去往目标网络 N 的报文都被转发到路由器R1 上去，再重复这种路由过程，直到到达正确的目的地。

路由的分类

通常情况下，指导 IP 转发的路由信息可以通过如下三种不同的途径来获得：

静态路由 —— 由系统管理员手动配置的到目标网络的唯一路径，当网络结构发生变化时也必须由系统管理员手动的修改配置。但合理的使用静态路由可以改进网络的性能，为重要的应用保存带宽。

缺省路由 —— 由系统管理员手动配置的一种特殊路由，可以将所有找不到匹配路由的报文转发到指定的缺省网关。

动态路由 —— 由动态路由协议从其他路由器学到的到达目标网络的发送路径，可以根据网络结构的变化动态地更新路由信息。

对网络拓扑变化的适应性

网络的配置不同决定了其对网络拓扑结构变化的适应能力，这取决于网络中是否使用动态路由协议。

静态路由信息可以指导报文的正常转发。再如图所示的网络中，为到达目标网络 N2 ，在路由器A上配置静态路由指向路由器 D ，在路由器 D 上配置静态路由指向路由器 C ，这样，从网络 N1 发往 N2 的报文就可以经过路由器A、D、C 最后到达目标网络 N2。

但假如从路由器 A 到 D 的通路出现了问题，那么路由器 A 就不能根据静态路由的指示将报文发送到路由器 D 上去。如果想要保证网络的畅通，就必须由网管员手动配置一条经由路由器B的静态路由，这样，报文就可以经由路由器 A、B、C ，最后到达目标网络。

如果网络中运行了某种动态路由协议（如 RIP 协议）情况就会有所不同。当经由路由器 D 的路由失效之后，路由器之间会通过动态路由协议的路由信息传递，自动的发现另外一条到达目标网络经由路由器 B 的路由，并修改路由表，指导报文进行正确的转发。

路由权

路由算法修改路由表的基本目的是将最好路由信息添加到路由表中，路由的好坏是由路由算法根据自己获得的路由信息计算出来的。对于每一条路由，路由算法产生一种权值来表示路由的好坏。通常情况下，这种权值越小，该路径越好。

路由权的计算可能基于路径某单一特性计算，也可能基于路径多种属性进行计算。有几种路径特性经常被用于权值计算，如下：

带宽—— 链路的数据容量。例如，通常情况下10M 以太网链路比64K 出租线路要更好。

时延—— 报文从到达目标网络所需要的时间。

负载—— 处于活跃状态的网络资源数量。

可靠性—— 每条数据链路的出错率。

跳数—— 报文到目的地需要经过的网络数。

开销—— 一种人为设定的值，通常由网络管理员根据带宽、线路价格或其他一些因素综合得出。

路由优先级

前面讲过，各个路由协议都有自己的标准来衡量路由的好坏（有的采用下一跳次数、有的采用带宽、有的采用时延，一般在路由数据中用度量 Metric 来量化），并且每个路由协议都试图将自己认为是最好的路由送到路由表中，这样我们就有可能从不同的协议得到到达同一目标网络的不同路由。尽管每个路由协议都给出了度量值，但是由于各个协议所采用度量值的含意不同，它们之间没有可比性。这就需要有种策略来决定使用哪一条路由。按照策略，判断最优的路由，我们才将它加入路由表，利用它来进行包的转发。

通常，我们使用路由优先级来判断不同路由协议所获得路由的好坏。每一种路由协议都由自己的优先级，当不同路由协议之间的路由发生冲突时，选择其中优先级最高的路由协议获得的路由。路由优先级是根据路由算法的优劣等因素得出的经验数值，也可以由网管员手动修改。

在上图中，三种路由协议 RIP 、OSPF 、IGRP 各自得到了一条到达目标网络10.0.0.0 的路由。我们假定三种协议之间的路由优先级的次序是OSPF > IGRP > RIP ，则最终选定 OSPF 路由作为最优路由。

自治系统

为了便于网络的管理，人为地将互联网划分成若干自治系统。每一个自治系统由一组在统一的机构管理下的路由器组成，整个系统对外呈现统一的路由机制，并被看成独立的网络组成单元。

自治系统由一个16bit 的整数标示，这个整数被称作自治系统号。自治系统号是由 NIC（Network Information Center）统一分配和管理的。

IGP和EGP

从上一节所定义的自治系统我们可以把网络化分成若干区域，从而可以标示路由协议的作用范围。根据路由协议的不同作用范围，我们可以将路由协议划分成域内路由协议（IGP）和域间路由协议（EGP）。

顾名思义，域内路由协议的作用范围被限制在自治系统内部，而域间路由协议适用于不同自治系统间的路由交换。

IGP 包括 RIP、IGRP、OSPF、IS-IS 等，而 EGP 目前只有 BGP 协议。

按寻径算法划分路由协议

根据寻径算法，单播路由协议可分成距离矢量协议（Distance-Vector）和链接状态协议（Link-State）。距离矢量协议包括 RIP、IGRP、EIGRP、BGP，链接状态协议包括 OSPF、IS-IS。

距离矢量算法

距离矢量算法是动态路由协议常用的一种路由算法，其基本原理就是运用矢量叠加的方式获取和计算路由信息。

所谓距离矢量即是将一条路由信息考虑成一个由目标和距离（用 Metric 来度量）组称的矢量，每一台路由器从其邻居处获得路由信息，并在每一条路由信息上叠加从自己到这个邻居的距离矢量，从而形成自己的路由信息。

在上图所示的例子中，路由器 I 从路由器 J 获得到达目标网络 N 的路由信息（N，M2），其中 N 标示目标网络，M2 标示距离长短的 Metric 值。并且在这条矢量数据上叠加从 I 到 J 的距离矢量（J，M1），形成从I 到目标网络 N 的路由信息（N，M），其中M = M1+M2 。

这种过程发生在路由器的各个邻接方向上，通过这种方法路由器可以获得到达网络中目标网络的途径和距离，并从中选择最佳路径形成和维护自己的路由表。

距离矢量协议

距离矢量协议直接传送各自的路由表信息。网络中的路由器从自己的邻居路由器得到路由信息，并将这些路由信息连同自己的本地路由信息发送给其他邻居，这样一级级的传递下去以达到全网同步。每个路由器都不了解整个网络拓扑，它们只知道与自己直接相连的网络情况，并根据从邻居得到的路由信息更新自己的路由表。

距离矢量协议无论是实现还是管理都比较简单，但是它的收敛速度慢，报文量大，占用较多网络开销，并且为避免路由环路得做各种特殊处理。

目前基于距离矢量算法的协议包括 RIP、IGRP、EIGRP、BGP。其中 BGP 是距离矢量协议变种，它是一种路径矢量协议。

链路状态协议

链接状态协议传送路由器之间的连接状态，每个路由器将自己所知道的链路状态通知其他路由器。这样网络中的路由器都知道整个网络拓扑结构，路由根据 SPF（Shortest Path First）算法得出。基于链路状态算法的协议结构复杂，难于管理。但由于每一台路由器都了解全网的拓扑结构，所以不用担心路由环路的影响，同时它的收敛速度快，需要传递的信息量少，可以节省网络带宽。

典型的基于链路状态算法的协议有 OSPF 和 IS-IS。

路由环路问题

路由环路问题是当网络拓扑结构发生变化，由于网络中存在的环状结构所引发的。上图是一个简单的例子。

如图所示，路由器 D 与目标网络 N 直接相连，而路由器 A、B、C 之间组成了一个环形网络，连接路由器的路径旁边的数字显示了路径对应的权值。这样在路由器 A 上就有一条经过路由器 D 的去往目标网络的路由，权值为 1，而路由器 B、C 上分别有一条经过路由器 A 的去往目标网络的路由，权值为2。假设，路由器 A 与 D 之间的通信出现了问题，这时候就有可能产生路由环路问题，并导致慢收敛。为了简单起见，我们假设所有的路由器都同时发送路由更新报文，下表显示了路由器 A、B、C 上到达目标网络的路由随时间的变化。

虽然算法最终收敛，但在漫长的收敛过程中在各个路由器上的路由并不能反映网络的真实结构，A、B、C 三台路由器之间相互欺骗，把错误的路由信息在网络中相互传递。

计算到无穷

仍然考虑如前面的网络结构，这里我们假设路由器 C 与 D 之间没有直接的通路相连，这时再断掉路由器A与D之间的连接，循环路由就会持续进行下去，错误的路由在路由环中一直传播下去。在前面所述的例子中，这种循环最终会停下来是因为路由器 C 得到了一条更好的路由（D，10），从而中止了路由循环的继续传播。现在这个中止条件没有了，路由信息的循环累加就会不停的继续下去，直到路由权值累加到无穷大。这就被称为计算到无穷问题。

解决路由环问题的几种方法

为解决路由环问题首先要设定一个最大值作为路由权的无穷大值，这个数值通常要根据协议的路由权值的计算方法而定。比如在 RIP 中以跳数来作为路由权的度量，它的最大值就是 16，也就是说如果某条路由的 Metric 值为 16 就表示这条路由不可达。

最大值的设定只能解决无限循环的问题，而并不能解决慢收敛问题。路由环路产生的一个重要原因就是不正确的路由信息通过获得这条信息的接口再发送回去，替代了新的正确的路由，这也就导致了错误路由信息的循环往复。如在我们前面提到的例子中，正是因为路由器 C 将从路由器A上得到的路由信息有发送回路由器 A，才会导致路由的循环依赖。由此我们得到一个解决路由环路的方法：水平分割。水平分割就是从某个接口接收到的路由信息不再从这个接口发送回去，从而避免错误的路由信息被使用。

另一个方法就是路由保持法，也就是将路由的不可达状态保持一段时间，在这段时间内不对这条路由作任何修改，直到这条路由的不可达状态被尽可能的扩散出去。这样也可以防止错误路由的传播。