路径选择问题
复习
- 路由表与最长前缀匹配：路由器按最长前缀决定下一跳
- 路由器与逐跳转发：路由器只决定下一跳
- ICMP：网络用它报告转发过程中的问题
TL;DR
- 把网络抽象成带权图，节点是网络，边是链路
- 路径选择就是在图上找一条合适的路
- “合适”可以是跳数少、代价低或时延小
- 各种路由算法，都是在这张图上做选择
正文
我们知道路由器要“选择更接近目标的下一跳”。可它凭什么知道哪个方向更接近？总得先有一张“地图”吧。
这一章，我们来看看这张地图长什么样。
把网络画成一张图
听起来复杂，抽象起来却很干净：把网络看作一张带权的图。
- 节点：一个个网络或路由器
- 边：连接它们的链路
- 权重：这条链路的“代价”
有了这张图，“找一条好路”就变成了图论里的最短路径问题——只不过这里的“最短”，不一定指距离。
“代价”可以是很多东西
边上的权重，可以根据需要定义成不同的东西：
- 跳数：经过多少台路由器，越少越好
- 带宽：链路越宽，代价越低
- 时延：延迟越小越优先
- 甚至可以是费用、政策、拥塞程度
所以路由问题并不是简单的“地理最短”，而是“按某种标准最优”。选择什么做权重，就直接决定了路由器会挑出什么样的路径。
谁来算这张图
接下来就是关键问题了：这张图，路由器是各自算，还是一起共享？答案是“都有”，而且是两种风格：
- 有的算法，每台路由器只和邻居唠叨，逐步逼近答案
- 有的算法，每台路由器先拿到全网地图，再自己算最优路径
它们就是下一章要讲的距离向量路由和链路状态路由。先记住这个大方向：同一个“在图上选路”的问题，可以有不同的信息共享方式。
另外别忘了，网络是不断变化的：链路会断、会通、会变慢。所以路由算法不仅要能算出好路，还得能在变化中快速恢复。这也是后面两章评价它们的重点。
思考题 1
为什么可以把网络抽象成带权图？这里的权重可以表示哪些含义？
思考题 2
“最优路径”一定唯一吗？它取决于什么？
小结
知识点
- 网络可抽象成带权图
- 路径选择即图上的最短路问题
- 权重可表示跳数、带宽、时延等
- 路由算法还要能应对网络变化
参考资料
- Wikipedia(zh)：图论：以节点和边研究关系的数学分支
- Wikipedia(zh)：最短路径问题：在带权图中寻找最优路径
思考题答案（仅供参考）
思考题 1
因为路由关心的正是“哪些点相连、连接代价多大”，这与图的节点、边、权重一一对应。权重可以表示跳数、带宽、时延、费用或政策偏好等，具体用什么，取决于你想要哪种“最优”。
思考题 2
不一定唯一。是否唯一取决于权重定义和网络结构：如果有两条路径总代价相同，它们都是最优的。所以“最优”是相对于某套权重标准而言的，换个标准，答案可能不同。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪