一些基本概念：
默认路由器：与主机直接相连的路由器，又叫第一跳路由器。每当主机发送一个分组时，都先传送给它的默认路由器。
源路由器：源主机的默认路由器。
目的路由器：目的主机的默认路由器。
路由算法——全局路由算法：所有路由器拥有完整的网络拓扑信息和链路费用信息。——>链路状态路由算法LS：必须知道网络中每条链路的费用。
路由算法——分布式路由算法：以迭代的、分布式的方式计算最低费用路径。节点只有与其直接相连链路的费用信息，不需拥有所有网络链路费用的完整信息。——>距离向量路由算法DV：每个节点维护到网络中所有其他节点的费用（距离）的估计向量。
路由算法——静态路由算法：路由确定后基本不再变化。只有人工干预调整时，可能有一些变化。
路由算法——动态路由算法：当网络的流量负载或拓扑发生变化时，路径可能发生改变。 可以周期性地或直接地响应拓扑或链路费用的变化。
链路状态选路算法LS
- 所有节点知道网络拓扑，以及每条链路的费用信息。通过链路状态广播来实现（“泛洪”），所有节点拥有相同的信息 。拥有这些信息后，运用Dijkstra算法选路，获得路由表。
- 基本思想：以源节点为起点，每次找出一个到源节点的费用最低的节点，直到把所有的目的节点都找到为止。
- 术语：
c(x,y) ：表示从节点x到y的链路费用;
D(v)：表示从源节点到目的节点v的当前路径的费用；
p(v)：表示从源节点到目的节点v的路径上的前驱节点(例如w是v的前驱节点)；
每个节点都用（D(v），p（v））表示
N’：表示已经找到最低费用路径的节点集合。
4. 例子：
5.复杂度：O（n2）
距离向量路由算法DV
1.Bellman-Ford方程:
dx(y) = minv{c(x,v)+ dv(y)}
其中：
dx(y)：节点x到节点y的最低费用路径的费用。
v: 节点x的邻居节点。
c(x,v)+ dv(y)：x与某个邻居v之间的直接链路费用c(x,v)，加上邻居v到y的最小费用。即x经v到节点y的最小的路径费用。
minv ：从所有经直接相连邻居节点v到节点y的费用中选取的最小路径费用。
2.节点距离向量表
（初始路由选择表中，因为还未从邻居节点收到通告，所以被初始化为无穷大）
节点x的距离向量Dx ，即节点x到每个目的节点y的估计费用； Dx = [Dx(y)：y在N中]
节点x每个邻居的距离向量Dv ，即x的邻居v到每个目的节点y的估计费用，Dv = [Dv(y)：y在N中]
3.距离向量的更新
当节点x收到一个邻居v的新距离向量，先保存，并用B-F公式更新自己的距离向量： Dx(y) = minv{c(x,v)+ Dv(y)}
若距离向量未发生变化，则不向邻居节点发送更新。
当距离向量不再变化，算法终止，此时Dx(y)收敛到dx(y)，即得到节点x到节点y的最低费用路径。
4.“好消息”传播快，即节点之间链路费用减少后能迅速静止
5.“坏消息”传播很慢，即链路费用增加后迭代到静止的次数很多，会出现“计数到无穷”问题。——>毒性逆转
LS算法与DV算法比较
1.消息复杂度：
LS算法：知道网络每条链路的费用，需发送O(nE)个报文；当一条链路的费用变化时，必须通知所有节点
DV算法：迭代时，仅在两个直接相连邻居之间交换报文；当链路费用改变时，只有该链路相连的节点的最低费用路径发生改变时，才传播已改变的链路费用。
2.收敛速度：
LS算法：收敛快，一次性算出。需要O(nE)个报文和O(n2)的搜寻，可能会振荡；
DV算法：收敛较慢。可能会遇到选路回环，或计数到无穷的问题。
3.健壮性：当一台路由器发生故障、操作错误或受到破坏时，会发生什么情况?
LS算法：路由器向其连接的一条链路广播不正确费用，路由计算基本独立（仅计算自己的转发表），有一定健壮性。
DV算法：一个节点可向任意或所有目的节点发布其不正确的最低费用路径，一个节点的计算值会传递给它的邻居，并间接地传递给邻居的邻居。一个不正确的计算值会扩散到整个网络。
