注：本文首发于稀土掘金。该平台的作者 逐光而行 也是本人。
前置知识——有连接的服务和无连接的服务
无连接的服务
- packet(包)被称为数据报（datagram）,整个网络被称为数据报网络
- 性质：无需事先确定路径
但是包在传输中途会动态选择路径，起作用的是一系列路由算法
有连接的服务
- 整个网络被称为virtual-circuit network（虚电路网络）
- 性质：需要事先确定一条路径
用到标签交换
有无连接服务的异同比较
（非完全照搬原书，只列举了我认为最重要的几点）
| 条目 | 数据报网络 | 虚电路网络 |
|---|---|---|
| 寻址 | 每一个包都包含完整的源和目的地址（因为要自力更生的嘛，重要信息不能丢） | 每个包需包含简短的VC号 |
| 状态信息 | 无 | 对每个连接的每条虚电路，都需要用路由表保存信息 |
| 路由失效带来的影响 | 无，除非包自己丢失 | 所有会经过该路由的包都失效 |
| 服务质量 | 难 | 如果事先能保证分配足够的资源就容易 |
| 拥塞控制 | 难 | 同上 |
路由算法
评价路由算法的几大指标
- 正确性（correctness）
- 简单性 simplicity
- 健壮性 robustness
- 稳定性 stability
- 公平性 fairness
- 效率 efficiency
路由算法的两大分类
- 非适应性算法（静态路由）
- 适应性算法（动态路由）
在实际应用中是两种相结合的
（正所谓存在即合理。如果一方有压倒性优势，而另一方毫无用处可言，那后者不就早就消失了么，我们也不需要再学习了）
优化原则
在深入学习具体的路由算法之前，我们还需要知道一些理论基础及其指导。
比如：如果从I到K有条最优路径，而J在这条路上，那么J到K的最优路径也是这条。
再比如，有一个很重要的概念，叫 sink tree
（查了一下中译本，翻译为汇集树，我个人比较喜欢叫它下沉树）。
它是从所有源地到某个给定目的地的最佳路由的 集合 ，
目的地就是根结点，它没有圈，可以看做是从根向外发散出去的。
这些路由算法的目的也是为了找到这个汇集树。
最短路径算法（SPA）
这会用到Dijkstra提出的最短路径算法
以书中示例为例（考试中不需要画这么多图，只需要动态修改一个图就可以了）
假设要求从A到D的最短路径。从A出发，给每个途径的点都标注一个二元组信息。其中，数字表示从A到该点的最短路径，符号表示该点的上一跳（即，沿着目前最短的路径，是经过哪个点才来到这个点的）。
这样记录的好处就是，如果有多个入度指向当前点，每次只需要把二元组中的数值与最新的路径权重相加，一比较，就可以得知当前点的最短路径。依次这样不断推演和更新下去，直到到达目标点。
注意：如果有更小的路径，才更新，否则如果新的路径和原来的一样甚至更长，就忽略了。
弄好之后可以把这个图转化为 某个结点的 路由表 。
以A的路由表为例：
| 目标 | 下一跳 | 路径 |
|---|---|---|
| A | 无 | 0 |
| B | B | 2 |
| C | B | 9 |
| D | B | 10 |
转化方法也很简单，只需要倒过来看。由于A到其本身设为无。比如A到10，就抄表格中D的二元组里的数据10，D的上一跳是H，H的上一跳是F，就顺藤摸瓜一直往上找，直到某个点的上一跳是A，也就是说这个点是A的下一跳。
以上思路用于示例中的简单图可能有点大材小用了，但是对于复杂的图确实会很有效。
洪泛算法 Flooding
- 用途：如其名，用于分流。
一般不用于传用户数据，而是传一些系统信息，允许冗余（尤其是需要火速送达的，重复了没关系，送不到最致命，所以需要像泄洪一样一泻千里，争取覆盖）
几点注意事项：
- 每个包的头部会有一个跳计数器，初值一般赋为路径长度（如果不知道路径长度，就考虑最坏的情况：整个网络的长度），传播途中该值会递减，减至0则包被丢弃。
- 还是应尽量避免同一个包数据被多次以洪泛的形式传播。所以可以让源路由记录每个包的序列号，并且让之后的路由都维护一张列表，如果发现该序号已存在，说明它已经被传过了，就不需要再传。 不过为了防止这个列表无限大，还应该记录一个列表的项数k，表示直到k的所有项均已被观察过。因此只需要比较seq和k两个参数（而且k以前的数据也不需要记录）。
距离矢量路由（DVR）
- 别名：distributed Bellman-Ford routing algorithm
- 使用场景：是最早的阿帕网路由算法，也在RIP（routing information protocol）协议下用于互联网
- 基本思想
当前结点探测相邻结点对目标结点的到达情况，再结合自身与相邻结点的距离，来对自身到目标结点的距离进行合理推断（简单理解就是将两段距离相加）
- 特性
该算法算自己到自己的距离时会绕大圈，故路由表中的该项需手动修正。
以下以中译本电子书中提到的例子为例，介绍是如何通过该算法得出新路由表的：
将上图2的表倒过来画，更直观
J
| To | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A | 0 | 12 | 25 | 4 | 14 | 23 | 18 | 17 | 21 | 9 | 24 | 29 |
| (delay is) 8 | 8 | 20 | 33 | 48 | 22 | 31 | 26 | 25 | 29 | 17 | 32 | 37 |
| I | 24 | 36 | 18 | 27 | 7 | 20 | 31 | 20 | 0 | 11 | 22 | 33 |
| (delay is)10 | 34 | 46 | 28 | 37 | 17 | 30 | 41 | 30 | 10 | 21 | 32 | 43 |
| H | 20 | 31 | 19 | 8 | 30 | 19 | 6 | 0 | 14 | 7 | 22 | 9 |
| (delay is) 12 | 32 | 43 | 31 | 20 | 42 | 31 | 18 | 12 | 26 | 19 | 34 | 21 |
| K | 21 | 28 | 36 | 24 | 22 | 40 | 31 | 19 | 22 | 10 | 0 | 9 |
| (delay is)6 | 27 | 34 | 42 | 30 | 28 | 46 | 37 | 25 | 28 | 16 | 6 | 15 |
最后注意：从J到J的结果要进行修正，为0
将以上结果整理即可得出上图2所示的路由表。
无限计算问题
- 特点：好消息传播得非常快，对坏消息反应迟钝
- 原因：路由收敛速度慢
- 核心问题：当X告诉Y附近有一条路径时，Y不知道自己是否已在这条路径上（当网络出现故障时，不断地获取并递增更新自己告诉邻居的值，最终导致值无限增大）
（注：小蓝书中提到后继很多想解决这个问题的算法都是有名无实。不过这本书写成于10年，这十几年间也许已有了重大突破，所以我在网上找到了一篇论文，粗略看了一下，还挺有道理的）
链接如下：
An Effective Solution to Count-to-Infinity Problem for both Complex and Linear Sub-Networks
链路状态路由（LSR）(综合了前面几个）
取代了距离矢量路由算法，也是当今最广泛使用的算法
以下是算法步骤：（可以简单理解为不断和周围交换信息）
认识邻居，了解环境
在每一个端到端的线上发送一个特殊的HEELO包，如果邻居不回复，说明已挂或不存在；否则就是还活着，对方会回应自己的 名字 。这个名字是作为一个唯一标识，不能重复。
对每一个邻居设置距离或成本开销度量
成本开销可默认为网络运营商提供的值。一般都与链路带宽呈负相关。这样会使得路由倾向于选择高容量的路径。
建立链路状态包
里面携带了自己获取的关于周围环境的所有信息，便于之后和邻居交换信息。
示例如下：
接下来的内容也会细细解释一下为什么需要这几部分。
分发链路状态包
这里用了洪泛算法去分发消息。
有几个问题：
- 为了保持洪泛在可控范围内，需要一个seq。
Q：如果seq重复了怎么办呢？A: 将seq设为32位的，产生一个重复的值需要137年
- 如果某个路由坏了，seq值丢失，或者seq的值被改了，那之后的包后继路由就不认了怎么办？
A：这就是需要age的原因。
age的设置是这样的：
- 每过去一秒递减1
- 在洪泛期间每经过一个路由减1。
当该值减为0时，相关信息会被丢弃。
- 使得算法更健壮的改进方法,如图所示：  当一些包到达路由，在进行洪泛前， 两个**从同一个源头来的**相继的包会被比较。 - 如果它们的seq完全一样，就扔掉其中一个 - 如果它们的seq不一样，就扔掉旧的（先来的那个） ### 计算到其他路由的最短路径 用最短路径算法。
总的来说，链路状态路由算法被广泛应用。比如IS-IS链路状态协议和OSPF协议都有它的身影。 （注：IS-IS:intermediate system-intermediate system OSPF:open shortest path first 这两个协议几乎相同，不同点在于前者可以同时携带多个网络层协议的信息，而后者不能 ）
