目的：决定从源到目的地通过网络的“好的路径”（一般指最小费用的路径）。
①路由随时间缓慢变化。
②手工配置
①路由更快地变化（周期的更新，适应链路费用和网络拓扑变化）。
全局的
所有路由器具有完全的拓扑、链路费用信息。
具有全局状态信息的算法常被称作链路状态算法，因为该算法必须知道网络中每条链路的费用。
使用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算法，是因为每个结点维护到网络中所有其他结点的费用估计的向量。
使用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：对n个节点，E条链路，发送O(nE)报文。
DV：仅在邻居之间交换（收敛时间变化）
LS：O(n^2)算法要求O(nE)报文（可能具有振荡）
DV：收敛时间变化（可能有选路环路，计数到无穷问题）
若路由器异常，将发生什么现象
LS：①节点可能通告不正确的链路费用。②每个节点仅计算自己的表。
意味着其路由计算在某种程度上是分离的，提供了一定程度的健壮性。
DV：①DV节点通告不正确的路径费用。②每个节点能由其他人使用（差错通过网络传播）
因此DV算法中一个不正确的结点计算值可能扩散到整个网络。
