目的：决定从源到目的地通过网络的“好的路径”（一般指最小费用的路径）。

根据算法是静态的还是动态的进行分类：

静态：

①路由随时间缓慢变化。

②手工配置

动态：

①路由更快地变化（周期的更新，适应链路费用和网络拓扑变化）。

根据算法是全局式的还是分散式的来加以区分：

LS（Link State，链路状态算法）

全局的

所有路由器具有完全的拓扑、链路费用信息。

具有全局状态信息的算法常被称作链路状态算法，因为该算法必须知道网络中每条链路的费用。

使用Dijkstra算法。

所有节点知道网络拓扑、链路费用

1）经“链路状态广播”完成

2）所有节点具有相同信息

从一个节点到所有其他节点计算最低费用路径

1）给出对这些节点的转发表

k次迭代后，得到k个目的地的最低费用路径。

算法：

①维护一个集合N',初始时将起点u放入其中，维护一个数组D，其中D(v)代表u到v的距离，初始时，所以与u相邻的节点的数组D赋为u到其的距离，非相邻结点赋为∞。

②找出不在集合N'中的w且使得D(w)最小，将w加入集合N’。

③对于w的所有不在N’中的邻居v，更新D(v),即D(v)=min(D(v), D(w)+c(w,v))。知道所有节点都在N’中

具体例子1

ps：p(v)从源到v沿着当前最低费用路径的前一节点

解题步骤：

步骤	N'	D(v)，p(v)	D(w)，p(w)	D(x)，p(x)	D(y)，p(y)	D(z)，p(z)
0	u	2，u	5，u	1，u	∞	∞
1	ux	2，u	4，x		2，x	∞
2	uxy	2，u	3，y			4，y
3	uxyv		3，y			4，y
4	uxyvw					4，y
5	uxyvwz

具体例子2

计算从x到所有网络结点的最短路径。

解题步骤：

步骤	N’	D(t)，p(t)	D(u)，p(u)	D(v)，p(v)	D(w)，p(w)	D(y)，p(y)	D(z)，p(z)
0	x	∞	∞	3，x	6，x	6，x	8，x
1	xv	7，v	6，v		6，x	6，x	8，x
2	xvu	7，v			6，x	6，x	8，x
3	xvuw	7，v				6，x	8，x
4	xvuwy	7，v					8，x
5	xvuwyt						8，x
6	xvuwytz

算法复杂性：n个节点

1）每次迭代：需要检查不在N’中的所有节点w

2）n(n+1)/2对比：O(n^2)

3)更有效的实现是可能的：O(nlogn)

可能震荡（由于链路流量变化，导致链路费用变化，所以需要重计算）

DV(Distance-Vector，距离矢量算法)

分散的

一开始，路由仅有与其直接相连链路的费用信息。

计算的迭代过程，与邻居交换信息。

之所以叫做DV算法，是因为每个结点维护到网络中所有其他结点的费用估计的向量。

使用Bellman-Ford方程(动态规划)

定义：dx(y)代表从x到y最低费用路径的费用；c(x,v)是x到直接邻居v的费用；minv对x的所有直接邻居取最小值。

dx(y)=minv{c(x,v)+dv(y)}

简单例子：

已知dv(z)=5,dx(z)=3,dw(z)=3

基本思想：

1）每个节点周期性的发送它自己的距离矢量DV给邻居。

2）当节点x接受到来自邻居的新DV估计，它使用B-F方程更新其自己的DV：

Dx(y) ← minv{c(x,v) + Dv(y)}    for each node y ∊ N

在规模较小、正常的条件下，估计值Dx(y)收敛在实际最小费用dx(y)。

异步迭代：

每次本地迭代由下列引起：

1)本地链路费用改变c(x,v)

2)DV从邻居更新报文d(v,y)

分布式：

1)每个节点仅当其DV改变时通知邻居。

2）如果必要，邻居则通知它们的邻居

每个节点的流程如下：

具体例子

假设每个结点初始时知道到它的每个邻居的费用。考虑距离向量算法，并显示在结点z中的距离表表项。

无穷计算问题

例子阐述现象

只关注y与z到目的地x的距离表中的有关表项。

在链路变化之前Dy(x)=4,Dy(z)=1,Dz(y)=1,Dz(x)=5。

若t0时刻，y检测到费用从4变为60，则Dy(x)=min{60+0,1+5}=6。（其实明显不存在1+5这条路，但是结点x仅有的信息是，它到x的直接费用是60，且z上次告诉它，z能以5费用到达x）。

这样出现了一个问题，即选择环路。y到达x，y通过路由z，z又通过路由y。这样就像一个黑洞，目的地为x的分组会在y和z结点间反复。

t1时刻，Dy(x)更新，所以又通知给z，则Dz(x)=min{50+0,1+6}=7。此时又会通知y，就这样类似进行下去。直到z最终算出它经过y的路径费用>50为止。这样才知道z直接到x是最低费用，y经过z再到x是最低费用。所以坏消息传播得很慢。

毒性逆转

思想：如果z通过y路由选择到目的地x，则z将通告y，z到x的距离是无穷大。即z将通告y Dz(x)=∞（即使实际上Dz(x)不是∞）。这样的话就可以保证只要z继续经y路由到x，则y就永远不会试图经由z到x(因为在其认知里，Dz(x)=∞)

例子阐述现象：

继续上图中的例子进行阐述。

由于使用毒性逆转，则对于y来说，Dz(x)=∞，所以t0时刻，Dy(x)=min{60+0,1+∞}=60。

通知给z，Dz(x)=min{50+0,1+60}=50，通知给y，则Dy(x)=min{60+0,1+50}=51。此时y又通知z Dy(x)=∞。以此来毒化了从z到x的逆向路径（比如z直接到y，y再经由z到x）。

然而当涉及到3个或更多结点的环路将无法用毒性逆转技术检测到。

那么可以定义最大度量来解决无穷计数的问题。

比如定义一个最大的有效费用值，如15跳步，16跳步表示∞。

LS与DV算法的比较

报文复杂性

LS：对n个节点，E条链路，发送O(nE)报文。

DV：仅在邻居之间交换（收敛时间变化）

收敛速度

LS：O(n^2)算法要求O(nE)报文（可能具有振荡）

DV：收敛时间变化（可能有选路环路，计数到无穷问题）

健壮性

若路由器异常，将发生什么现象

LS：①节点可能通告不正确的链路费用。②每个节点仅计算自己的表。

意味着其路由计算在某种程度上是分离的，提供了一定程度的健壮性。

DV：①DV节点通告不正确的路径费用。②每个节点能由其他人使用（差错通过网络传播）

因此DV算法中一个不正确的结点计算值可能扩散到整个网络。