CN-链路状态路由算法

[[CN-NotesView]]

链路状态路由算法

网络抽象：图

图： G = （N，E）

链路状态路由算法

Dijstra算法

所有节点（路由器）掌握网络拓扑和链路费用

要求每一个路由器都构造一个链路状态分组，并广播出去

通过“链路状态广播”

链路状态路由算法里面利用扩散或者泛洪的方法来进行发送

任何一个路由器都会收集全了所有路由器的链路状态分组

所有节点拥有相同信息

计算从一个节点（“源”）到达所有其他节点的最短路径

获得该节点的传发表

迭代：k次迭代之后，得到到达k个目的节点的最短路径

符号

c(x,y):结点x到结点y链路费用；如果x和y不直接相连，则为无穷大

D(v): 从源到目的v的当前路径费用值

p(v): 沿从源到v的当前路径，v的前序节点

N‘ ：已经找到费用最小路径的结点集合

Dijstra 算法：

初始化
N’ = {u}
for 所有结点
	if v和u相邻
		then D(v) = c(u,v)
	else D(v) = 无穷

Loop 
	找出不再N’中的w，满足D（w）最小
	将w加入N‘
	更新w的所有不在N’中的邻居v的D（v）:
		D(v) = min(D(v),D(w) + c(w,v))
		//已知的到达w的最短路径费用加上w到v的费用
until 所有的结点都在N‘中了

u 的最终最短路径树：

u 的最终转发表：

根据上面的内容进行计算最终转发表

Dijstra 算法

算法复杂性： O($n^2$)

每一次迭代：需要检测所有不在结合N’中的结点
n(n+1)/2次的比较：O($n^2$)
更高效的实现：O(nlogn)

存在震荡的可能：
假设链路费用是该链路承载的通信量

很有可能导致数据包在DCB之间反复震荡无法传送到A，最终会因为TTL被丢弃。

所以会使用一些机制来避免这样的情况