网络层（七）路由算法和路由协议

1.什么是路由？
“路由是从源主机到目的主机的路径”，这个说法其实不准确。
发出IP分组的源主机，会将IP分组送到该主机的默认网关（第一跳路由器）。分组从第一个路由器到最后一个路由器（目的主机的默认网关）的路径就是路由。

2.路由算法
路由算法就是确定最佳路径的算法。

路由算法分类

网络通常抽象成一张加权图，结点就是路由器，边就是物理链路，权就是链路的耗费，链路耗费可以是这段链路的物理长度、带宽的倒数、拥塞情况等等，总之是一个权值而已，计算路由时总是希望耗费最小。

3.链路状态路由算法

• 每个路由器收集自己的链路信息（我与谁相邻，链路耗费是多少）
• 构造数据包将链路状态信息广播出去（链路层广播，mac地址全为1）
• 路由器收集到完整的信息，就知道了详细的网络拓扑信息
• 根据完整的网络拓扑信息，计算到每个结点的最短路径

链路状态路由算法里，计算最短路径采用的是Dijkstra算法。

4.距离向量路由算法
每个结点不关心整个网络拓扑，只需要知道自己到每个结点的最短路径怎么走就行。求解最短路径时算法用的Bellman-ford算法，状态转移方程非常简单：

Bellman-ford方程

5.层次化路由
上述两种路由算法，都是将网络抽象成一张图，然后计算最短路径。但在实际的Internet网络中很不实际，因结点数量过多。因此采取层次化路由这样的策略。

层次化路由

一个AS内部的路由信息由内部的路由算法确定，外部的由外部路由算法确定。

层次化路由

假设路由器1d，有个分组需要送到路由器x：

• 如果1d通过AS间路由协议学习到，只有通过AS3可以达到x，那1d的收到的分组就会通过1c送出，至于是怎么从1d到1c，这是AS内的路由算法决定的。
• 如果AS2、AS3都可以到达x，那1d就会在1c和1b两个网关中，选择离自己最近的。
  即“将分组发送给最近的网关”，这称为热土豆路由（烫手，尽早交出去）。

AS选择

6.路由协议
略