链路状态路由与Dijkstra算法

路由选择算法（Routing Algorithm）

路由器转发分组是通过路由表转发的，而路由表是通过各种算法得到的。路由选择算法分为静态路由算法和动态路由算法。

静态路由算法（非自适应路由算法）由网络管理员手工配置路由信息。当网络的拓扑结构或链路的状态发生变化时，需手工修改路由表中的静态路由信息。它不能及时适应网络状态的变化，因此仅用于简单的小型网络。

动态路由算法（自适应路由算法）是一种自动化的路由算法，它能根据网络的状态及路由表的变化自动适应网络状态的变化。这些路由信息会在一定时间间隔里不断更新，以随时获得最优的寻路效果。

研究路由选择算法时，通常把网络抽象成一张带权图$G = (N, E)$：结点$N$表示路由器，边$E$表示链路，每条边$(x, y)$有一个开销$c(x, y)$，它可以代表链路长度、时延或费用。一条路径的开销是路径上所有边的开销之和，路由选择的目标就是找到源与目的之间开销最低的路径。

按照每个结点掌握的信息，动态路由算法又可以分成两类：全局式算法要求每个结点都知道完整的网络拓扑和所有链路的开销；分散式算法中每个结点只知道到直接邻居的链路开销，通过与邻居交换信息逐步算出最低开销路径。下面的链路状态算法属于前者，4.9节的距离向量算法属于后者。

链路状态算法（Link-State Routing Protocol）

链路状态算法属于全局式路由选择算法，所有网络拓扑信息都是已知的，通过使用Dijkstra算法得到源点到各个结点的最短路径。

为了让每个结点都掌握完整的拓扑，每台路由器把自己所有直连链路的开销放进链路状态通告（LSA, Link-State Advertisement），向全网泛洪（flooding）：收到一个新的LSA时，路由器把它存入自己的链路状态数据库，并转发给除来源以外的所有邻居；重复收到的副本直接丢弃。LSA带有序号，序号更大的LSA会替换旧的。泛洪完成后，所有路由器都拥有相同的网络地图。

Dijkstra算法

以源结点$u$为例，算法使用以下记号：$D(v)$表示本次迭代时从$u$到$v$的当前最低开销；$p(v)$表示这条路径上$v$的前一结点；$N'$是已经确定了最低开销路径的结点集合。

初始化：
    N' = {u}
    对所有结点v：
        如果v是u的邻居，D(v) = c(u, v)
        否则 D(v) = ∞
循环：
    找出不在N'中、且D(w)最小的结点w，把w加入N'
    对w的每个不在N'中的邻居v：
        D(v) = min(D(v), D(w) + c(w, v))
直到N'包含所有结点

每次迭代都把一个结点加入$N'$，并且只可能让它的邻居的开销变小：

下表是在实验所用的网络中以$u$为源结点的计算过程（D值相同时按字母顺序选择）：

当算法终止时，每个结点都能得到从源结点沿着它的最低开销路径的前一结点。对于每个前一结点，又有它的前一结点，以此方式可以构建从源结点到所有目的结点的完整路径。

例如$z$的前一结点是$y$，$y$的前一结点是$x$，$x$的前一结点是$u$，所以$u$到$z$的最低开销路径是$u \to x \to y \to z$，开销为4。只保留每条路径的第一跳，就得到$u$的转发表：发往$v$的分组走链路$(u, v)$，发往$w$、$x$、$y$、$z$的分组都走链路$(u, x)$。

对于$n$个结点，朴素实现每次迭代都要扫描所有不在$N'$中的结点，总复杂度为$O(n^2)$；使用堆（优先队列）可以降到$O((n+m)\log n)$，其中$m$为链路数。

如果链路开销随链路上的负载变化，链路状态算法可能出现振荡：所有路由器同时把流量转到当前开销低的路径上，使它变得拥挤，下一轮又一起转走。让各路由器在随机的时刻发送LSA可以缓解这个问题。