链路状态(Link State,LS)路由选择算法
- 全局式的路由选择算法；
链路状态广播算法
- 为获取全局网络信息，实践中要求每个节点向网络中所有其它节点广播链路状态分组；
- 节点广播的结果是，所有节点都具有了该网络等同的完整的视图；
链路状态路由选择算法
- 具体的链路状态路由选择算法可选用Dijkstra算法等单源最短路径算法；
- 每个节点都在其上运行单源最短路径算法，以获取到达每个目的地的下一跳路由节点，从而构造转发表；
Dijkstra算法
c(x,y): 结点x到结点y链路费用；如果x和y不直接相连，则=∞
D(v): 从源到目的v的当前路径费用值
p(v): 沿从源到v的当前路径，v的前序结点
每轮迭代，从最短路径未确定的节点集合中，选取一个路径最短的节点，到该节点的当前最短路径就是到该节点的最短路径，将之加入最短路径已确定节点集合，并更新到该节点邻接节点的当前最短路径；
k次迭代后，得到到达k个目的结点的最短路径
算法复杂性
对n个节点
时间复杂度
更高效的实现
链路状态路由算法的问题
存在震荡(oscillations)可能
在状态a下，算法判定转换到状态b费用更底，
在状态b下，算法判定转换到状态a费用更底；
这是由于由于算法选择的路由会影响链路拥塞程度，链路拥塞程度会影响链路权重，链路权重又会影响算法选择的路由；
