距离向量路由

复习

路径选择问题：把网络抽象成带权图
路由器与逐跳转发：每台路由器只决定下一跳
路由表与最长前缀匹配：路由表记录目的与下一跳

TL;DR

距离向量路由：每台路由器只知道“到各目标的距离”和“该走哪个邻居”
它通过和邻居交换距离信息，逐步逼近全网最优
好消息传得快，坏消息传得慢
实现简单，但收敛可能很慢，甚至出现环路

正文

　　路由算法要解决的第一个问题是：如果每台路由器都不知道全网地图，能不能算出好路？

　　距离向量路由的回答是：能，只要邻居之间多聊天。

一条朴素的等式

　　它的核心，是一句简单得可爱的话：

我到目标 X 的距离，等于“我到某个邻居的距离”加上“那个邻居到 X 的距离”，在所有邻居里取最小的那个。

　　用式子写出来就是：dist(我, X) = min over 邻居 n (dist(我, n) + dist(n, X))。

　　这意味着，一台路由器不需要知道整条路径，只要知道“到每个邻居多远”，再听邻居说“我到 X 多远”，就能算出自己到 X 的距离，以及该走哪个邻居。

聊天聊出答案

　　于是距离向量算法就这么运行：

每台路由器维护一张表：到各目标的距离，以及对应的下一跳
定期把自己的距离表发给所有邻居
收到邻居的表后，按上面的等式更新自己的表

　　一开始，大家只知道直接相连的邻居；随着消息一轮轮扩散，远处的距离也慢慢传了过来。最终，网络变化停下来，各表趋于稳定，这个过程叫收敛。

坏消息为什么走得慢

　　这套方法有个有趣又麻烦的毛病：好消息传得快，坏消息传得慢。

　　如果某条链路变好、变近，邻居很快就能利用上，迅速更新。可如果一条链路断了，问题就来了：路由器 A 原本经 B 能到 X，B 断了。可这时 C 可能还告诉 A“我到 X 只要一点点，而且我经过你”，A 一听就误以为“那我经 C 也不错”，于是把包发给 C；C 又发给 A……两个路由器互相以为对方能到，距离越加越大，慢慢往上爬，这就是“计数到无穷”。

　　缓解的办法有：水平分割（不把从某个邻居学来的路又告诉它）、毒性逆转（干脆告诉它“到我这儿是无穷远”）。这些手段能减轻，但根治不易。

　　正因为这种慢收敛和环路隐患，另一条路被提了出来：让每台路由器都拿到完整的地图。这就是下一章的链路状态路由。

思考题 1