为什么DV逐渐让位于LS？
DV
站的不高，看得不远
完全相信邻居
LS
想办法站得高，看更远
多高、多远？
怎么做？
链路状态路由（Link State）
主要思想
发现 它的邻居节点们，了解它们的网络地址
设置 到它的每个邻居的成本度量
构造 一个分组，包含它所了解到的所有信息
发送 这个分组给所有其他的路由器
计算 到每个路由器的最短路径
发现邻居节点
当一个路由器启动的时候，在每个点到点的线路发送一个特
别的HELLO分组
设置链路成本
为了决定线路的开销，路由器发送一个特别的 ECHO 分组，
另一端立刻回送一个应答
通过测量往返时间（round-trip time） ，发送路由器可以获得
一个合理的延迟估计值
为了得到更好的结果，可多次测量，取均值
一种常用的选择
与链路带宽成反比
构造链路状态分组
链路状态分组构造后被发送给其他的路由器，分组中包含这些信息：
1 发送方的标识（ID of the sender）
2 序列号（sequence number ）
3 年龄（age ）
4 邻居列表（list of neighbors ）
5 到邻居的成本/量度（delay to each neighbor ）
应该什么时候构造分组?
周期性地构造和发送，或者有特别的事件发生时
构造，比如某条线路或邻居down掉了
发布链路状态分组
基本算法：
每个分组都包含一个序列号，序列号随着新分组产生而递增
路由器记录下他看见的所有 (源路由器，序列号)对
当一个的新的分组到达时，路由器根据它的记录：
如果该分组是新的，就被从除了来线路外的所有其他线路转
发出去 ( flooding，泛洪)
如果是重复分组，即被丢弃(喜新厌旧)
如果该分组的序列号比对应的源路由器发送的到过此地的分
组的最大序列号还小，则该分组被当作过时的信息而被拒绝
基本算法遇到的问题：
序列号回转，引起新老分组识别混淆
解决办法：使用 32-bit 的序列号，即使每秒产生一个分组，也
需要137年才发生号码回转
如果一台路由器崩溃，那么他将丢失自己的序列号记录，如果他
再从0开始，新分组将被当作旧分组被拒绝
解决上述的路由器崩溃和序列号损坏的方法是：每个分组的
序列号之后是年龄(age) ，并且每秒钟年龄减1
当年龄为零 ( zero )时，来自该路由器的信息被丢弃
通常地，每隔一段时间，如10秒钟，一个新分组就会到来，
所以，只有路由器down机才可能导致超时（ 或者，连续6个
间隔因为丢失，没有收到新的分组）
一些改进让基本算法更加健壮：
当一个链路状态分组到达某个路由器时，它首先被放到一个保留
区中等待一段时间
如果来自相同路由器的另一个分组到达了，这两个分组的序列号
会被比较：
如果相等，是重复分组，丢弃
如果不相等，旧的那个被丢弃
为了防止路由器到路由器的线路发生错误，所有的链路状态分组
都要被确认
当一条线路空闲的时候，路由器扫描保留区，以便选择一个分组
或确认，并将其发送出去
计算新的路由路径
一旦一个路由器获得了全部的链路状态分组就可以构造出全
网络图来了（Graph）
现在，可以使用最短路径算法来计算路由器之间的最短路径
计算结果是一棵树，会形成相应的路由，安装在路由表中，
引导数据分组的转发
链路状态路由选择的基本原理
发现邻居
设置成本
构造LSA
分发LSA
计算