## 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之外的目的地发送分组。