Internet 网络层的核心功能为路由选择（routing）和转发（forwarding），转发通过路由器索引其转发表决定某分组被指向的链路接口；路由选择算法在路由器中运行、交换和计算信息，这些信息被用于配置转发表。无论网络层提供的是数据报服务（在给定源和目的地址之间的所有分组可能采用不同的路由），还是虚电路服务（在给定源和目的地址之间的所有分组将采用相同路径），网络层都必须为发送方到接收方的分组确定所采用的路径，这就是路由选择的工作。

主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器（default router），或称为第一跳路由器（first-hop router）。每当主机发送一个分组时，该分组被传送给它的默认路由器。我们将源主机的默认路由器称作源路由器（source router），把目的主机的默认路由器称为目的路由器（destination router）。一个分组从源主机到目的主机的路由选择问题可归结为从源路由器到目的路由器的路由选择问题。

因此，路由选择算法的目的是：给定一组路由器以及连接路由器的链路，路由选择算法要找到一条从源路由器到目的路由器的“好路径”。通常，一条好路径指具有最低代价的路径（实践中还需关心一些其他问题，这也使得概念简单、性能优秀的算法变得复杂），且通常使用图来形式化路由选择问题。

路由选择算法可以根据算法是静态的还是动态的进行分类：

还可以根据算法是全局式的还是分散式的来加以区分：

在链路状态路由算法中，网络拓扑和所有链路费用都是已知的，实际中这是通过让每个节点向网络中所有其他节点广播链路状态分组来完成的，即链路状态广播。

可以采用 Dijkstra 算法作为链路状态路由算法，该算法可以计算从某节点（源节点，记为 u u u）到网络中所有其他节点的最低费用路径。Dijkstra 算法是迭代算法，其性质是经过 k k k 次迭代之后，可找到 k k k 个目的节点的最低路径费用。用计算得到的最短路径信息来配置转发表，到达某个目的节点要走与当前节点相连的那条链路。

距离向量（DV）算法是一种迭代的、异步的、分布式的算法，可以采用 Bellman-Ford 算法的思想。同 Dijkstra 算法，这也是一个单源最短路径算法，采用了动态规划的计算方式，令 d x ( y ) d_x(y) dx​(y) 表示从 x x x 到 y y y 最短路径的费用， c ( x , v ) c(x,v) c(x,v) 表示 x x x 到邻居 v v v 直接链路的费用，则递归方程为： d x ( y ) = m i n v { c ( x , v ) + d v ( y ) } d_x(y) = min_v\{c(x,v)+d_v(y)\} dx​(y)=minv​{c(x,v)+dv​(y)} 该方程也称为 Bellman-Ford 方程，使用该方程可以获得最短路径的下一跳，该信息用于配置转发表；另一个重要实际贡献是它提出了在 DV 算法中发生的邻居到邻居通信的形式。

用 D x ( y ) D_x(y) Dx​(y) 表示每个节点 x x x 对在 N N N 中的所有节点 y y y 最短路径的费用的估计；令 D x = [ D x ( y ) , y ∈ N ] \textbf{D}_x=[D_x(y),y\in N] Dx​=[Dx​(y),y∈N] 表示节点 x x x 的距离向量（DV），该向量是从 x x x 到网络中所有其他节点 y y y 的最低费用估计的向量。每个节点 x x x 维护下列路由选择信息：

① 对于每个直接相连邻居 v v v，从 x x x 到 v v v 的链路费用 c ( x , v ) c(x,v) c(x,v)。 ② 节点 x x x 自身的距离向量，即 D x = [ D x ( y ) , y ∈ N ] \textbf{D}_x=[D_x(y),y\in N] Dx​=[Dx​(y),y∈N]，包含了 x x x 到 N N N 中所有目的地 y y y 的费用的估计值。 ③ 它的每个邻居的距离向量，即对 x x x 的每个邻居 v v v，有 D v = [ D v ( y ) , y ∈ N ] \textbf{D}_v=[D_v(y),y\in N] Dv​=[Dv​(y),y∈N]。

由于局部链路费用改变或收到来自邻居的 DV 更新，某节点的 DV 估计可能会发生变化，将新的 DV 估计发送给其邻居；当 x x x 接收到邻居的新的 DV 估计时，即依据 B-F 方程更新其自身的距离向量估计： D x ( y ) ← m i n v { c ( x , v ) + D v ( y ) } ,   f o r   e a c h   n o d e   y ∈ N D_x(y)\leftarrow min_v\{c(x,v) + D_v(y)\},\ for\ each\ node\ y\in N Dx​(y)←minv​{c(x,v)+Dv​(y)}, for each node y∈N如果节点 x x x 的距离向量因这个更新步骤而改变，节点 x x x 接下来将向它的每个邻居发送其更新后的距离向量。只要所有的节点继续以异步方式交换它们的距离向量，每个费用估计 D x ( y ) D_x(y) Dx​(y) 将最终收敛于实际的最小费用 d x ( y ) d_x(y) dx​(y)。

上面的算法基本思想体现出该算法是一个异步迭代、分布式的算法，每个节点所要执行的动作可总结如下：

当一个运行 DV 算法的节点检测到从它自己到邻居的链路费用发生变化时，它就更新其距离向量，并且如果某最低费用路径的费用发生了变化，向邻居通知其新的距离向量。当链路费用减小时，DV 算法只需要少数轮迭代就可以达到静止状态。即“好消息传播快”。

现在考虑一下当某链路费用增加时发生的情况。如上图所示， x x x 与 y y y 之间的链路费用从 4 增加到 60：

消除无穷计数问题的方法有很多，其中包括一种称为毒性逆转（poisoned reverse）的技术，其思想较为简单：如果 z z z 通过 y y y 路由选择到目的地 x x x，那么 z z z 将通告 y y y： D z ( x ) = ∞ D_z(x)=\infty Dz​(x)=∞，我们现在看一下毒性逆转如何解决无穷计数问题。

但是更复杂的网络将无法用毒性逆转技术检测到，还需要一些其他的技术，如定义最大跳步数等。

DV 和 LS 采用互补的方法来解决路由选择计算问题。在 DV 算法中，每个节点仅与它的直接相连的邻居交谈，但它为其邻居提供了从它自己到网络中（它所知道的）所有其他节点的最低费用估计；在 LS 算法中，每个节点（经广播）与所有其他节点交谈，但它仅告诉它们与它直接相连链路的费用。记 N N N 是节点（路由器）的集合， E E E 是边（链路）的集合：

在前面介绍的 LS 和 DV 算法的研究中，都将网络抽象为一张图。但是将任意规模的网络抽象为一个图来计算路由过于理想化，因为至少有以下两个重要原因：

这些问题都可以通过将路由器聚合为自治系统（Autonomous System, AS）来解决，每个 AS 由一组通常处在相同管理控制下的路由器组成（例如，由相同的 ISP 运营或属于相同的公司网络）。在相同的 AS 中的路由器全都运行同样的路由选择算法（如一种 LS 或 DV 算法），称为自治系统内部路由协议（intra-autonomous system routing protocol），不同自治系统内的路由器可以运行不同的 AS 内部路由协议。当然，将 AS 彼此互联是必须的，因此在一个 AS 内的一台或多台路由器负责向在本 AS 外的目的地转发分组，这些路由器被称为网关路由器（gateway router），它们通过链路连接其他 AS 的网关路由器。

可以仅通过 AS 内部路由协议为在 AS 内部的源和目的对决定路由选择路径，但是如何将数据分组路由选择到位于其 AS 外部的目的地呢？

因为自治系统间路由协议涉及两个 AS 之间的通信，这两个通信的 AS 必须运行相同的自治系统间路由选择协议。事实上，因特网中的所有 AS 中都运行相同的 AS 间路由选择协议，该协议称为 BGP4。如下图中，假设 AS1 内的某路由器收到一个目的地址在 AS1 之外的数据报，那么 AS1 必须知道哪些目的网络可以通过 AS2 到达，哪些可以通过 AS3 到达，且需要向 AS1 中的所有路由器传播这些可达性信息，以配置它们的转发表来处理外部 AS 目的地。

以路由器 1d 为例，看一下它的转发表如何配置。假设 AS1 通过 AS 间路由协议学习到：子网 x x x 可以通过 AS3（网关 1c）到达，但不能通过 AS2 到达，AS1 则向它的所有路由器传播这个信息。当路由器 1d 知道从 AS3 并因此从网关 1c 可达子网 x x x 时，根据 AS1 内部路由选择协议提供的信息，确定其到达 1c 的最小费用路径接口 I I I，并将表项 ( x , I ) (x,I) (x,I) 放入其转发表中。

接着上面的例子，假设 AS1 通过 AS 间路由协议学习到：子网 x x x 通过 AS3 和 AS2 均可到达，AS1 将向它的所有路由器传播该信息。为了配置转发表，路由器 1d 必须确定通过哪个网关路由器来转发目的地址为 x x x 的数据分组，这个任务也是由 AS 间路由选择协议来完成。在实践中经常使用的一种方法是热土豆路由：将分组发送给最近的网关路由器。下图总结了路由器 1d 对转发表增加用于 x x x 的表项所采取的动作。