计算机网络——网络层学习笔记（中）：路由算法
路由选择算法
1、路由算法概述
路由算法（协议）确定去往目的网络的最佳路径
转发表确定在本路由器如何转发分组。
网络抽象：图
图：G=(N,E)
N=路由器集合，E=链路集合
关键问题：源到目的的最小费用路径是什么？
路由算法：寻找最小费用路径的算法。
2、路由算法分类
分类方式一：
静态路由：手工配置、路由更新慢、优先级高
动态路由：路由更新快（定期更新、及时响应链路费用或网络拓扑变化）
分类方式二：
全局式路由选择算法：所有路由器掌握完整的网络拓扑和链路费用信息。例如链路状态算法（LS，Link State）。
分散式路由选择算法：路由器值掌握物理相连的邻居以及链路费用，邻居间信息交换、运算的迭代过程。例如距离向量算法（DV,Distance-Vector）。
3、链路状态路由算法
Dijkstra算法
所有结点（路由器）掌握网络拓扑和链路费用。
通过链路状态广播。
所有结点拥有相同信息。
计算从一个结点（源）到达所有其他结点的最短路径。
获得该结点的转发表
迭代：K次迭代后得到到达K个目的结点的最短路径。
符号：
c(x,y) 结点x到y的链路费用，不直接相连为记为无穷大
D(v) 从源到目的v的当前路径费用值
p(v) 沿从源到v的当前路径，v的前序结点
N' 已经找到最小费用路径的结点集合
★算法描述：
1 Initialization:
2 N' = {u}
3 for all nodes v
4 if v adjacent to u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 find w not in N' such that D(w) is a minimum
10 add w to N'
11 update D(v) for all v adjacent to w and not in N' :
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N'
★算法复杂性：n个结点
每次迭代需要检测所有不再集合N'中的结点w
n(n+1)/2次比较：O(n2)
更高效的实现：O（nlogn）
★存在问题：震荡（oscillations）
数据报可能总是路由不到A，随着TTL减少最终被丢包。通常会使用其他机制也避免震荡现象，比如引入随机延时。
4、距离向量算法
Bellman-Ford方程（动态规划）
Define
dx(y) := cost of least-cost path from x to y
Then
dx(y) = min {c(x,v) + dv(y) }
where min is taken over all neighbors v of x
重点：结点获得最短路径的下一跳，该信息用于转发表中！
Dx(y)=从结点x到结点y的最小费用估计
x维护距离向量（DV）：Dx=[Dx(y): y∈N]
结点x：
已知到达每个邻居的费用：c(x,v)
维护其所有邻居的距离向量：Dv=[Dv(y): y∈N]
核心思想：
每个结点不定时地将其自身的DV估计发送给其邻居。
当x接收到邻居的新的DV估计时，即一句B-F更新其自身的距离向量估计
Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N
Dx(y)最终会收敛于实际的最小费用dx(y)
特点：
1、异步迭代：
引发每次局部迭代的因素
1）局部链路费用改变
2）来自邻居的DV变化
2、分布式
每个结点只有当DV变化时才通告给邻居，邻居在必要时（其DV更新后发生变化）再通告它们的邻居。
每个结点的状态变化：
等待（本地局部链路费用变化或收到邻居的DV更新）
↓
重新计算DV估计
↓
如果DV中到达任一目的距离发生改变，通告所有邻居
（回到等待……）
存在问题：无穷计数
坏消息传播得慢，当网络中存在环路时，可能会出现无穷计数问题。
解决方法：
1、毒性逆转
如果一个结点Z到达某目的X的最短路径是经过某个邻居Y，则通告给该邻居结点到达该目的的距离为无穷大。
注：涉及3个或更多结点的环路将无法用毒性逆转技术检测到。
2、定义最大度量
定义一个最大的有效费用值，如15跳步，16跳步代表无穷大。
--------------------------------------------------------------
简单总结一下，路由算法很重要！！！要好好看书哇(#^.^#)