4.5 路由选择算法

• 默认路由器（Default Router）：又称第一跳路由器（First-hop Router），与主机直接相连的路由器。

• 源路由器（Source Router）：源主机的默认路由器。

• 目的路由器（Destination Router）：目的主机的默认路由器。

因特网是一个图（Graph），G=（N，E）N个节点，E条边，路由的过程为求两个节点之间的最低费用路径（Least-cost Path）。

分类：

• 第一种：

  • 全局式路由选择算法（Global Routing Algorithm）：链路状态（Link State，LS）算法。

  • 分散式路由选择算法（Decentralized Routing Algorithm）：距离向量（Distance-Vector，DV）算法。

• 第二种：

  • 静态路由选择算法（Static Routing Algorithm）

  • 动态路由选择算法（Dynamic Routing Algorithm）

• 第三种：

  • 负载敏感算法（Load-sensitive Algorithm）

  • 负载迟钝算法（Load-insensitive Algorithm）

4.5.1 链路状态路由选择算法

Dijkstra算法，在一个路由器上计算全局路由状态。

4.5.2 距离向量路由选择算法

距离向量路由选择算法（Distance-Vector，DV）：每个路由器要从相邻的节点获得信息，计算并发送给相邻节点。

Bellman-Ford算法：

链路费用改变与链路故障

由直接相邻的路由检测，并反馈给网络。

增加毒性逆转

LS与DV路由算法的比较

• 报文复杂性：

  • LS需要每个节点都知道整个网络的链路费用。

  • DV两个相邻路由间直接交换报文。

• 收敛速度：LS快于DV

• 健壮性：

  • LS节点只算自己的转发表，相互之间不影响。

  • DV节点计算出的结果需要传递给相邻节点，相互依赖大。

其他路由选择算法

电路交换路由选择算法（Cireuit-switched Routing Algorithm）：链路资源需要留给每条经过的链路。

4.5.3 层次路由选择

问题：

• 互联网规模不断增大。

• 不同ISP之间需要自治管理，自治系统（Automous System，AS）

自治系统内部路由选择协议（Intra-autonomous System Routing Protocol）：同一个AS中的路由器运行同一种路由选择算法。

自治系统间路由选择协议（Inter-autonomous System Routing Protocol）：不同AS间运行的路由选择算法。

网关路由器（Gateway Router）：负责向AS之外的目的地发送分组。