路由算法
1 路由与转发
2 网络抽象：图
图: G = (N, E)
- N = 路由器集合= { u, v, w, x, y, z }
- E = 链路集合 ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
- 附注: 图的抽象在网络领域应用很广泛
- E.g.:P2P，其中， N是 peers集合，而E是TCP连接集合
图抽象：费用(Costs)
- c(x, x’) = 链路(x, x’)的费用
- e.g., c(w, z) = 5
- 每段链路的费用可以总是1，或者是带宽的倒数、拥塞程度等
- 路径费用： (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
- 关键问题: 源到目的（如u到z）的最小费用路径是什么？
- 路由算法: 寻找最小费用路径的算法
3 路由算法分类
静态路由 vs 动态路由？
- 静态路由：
- 手工配置
- 路由更新慢
- 优先级高
- 动态路由：
- 路由更新快
- 定期更新
- 及时响应链路费用或网络拓扑变化
全局信息 vs 分散信息？
- 全局信息：
- 所有路由器掌握完整的网络拓扑和链路费用信息
- E.g. 链路状态(LS)路由算法
- 分散(decentralized)信息：
- 路由器只掌握物理相连的邻居以及链路费用
- 邻居间信息交换、运算的迭代过程
- E.g. 距离向量(DV)路由算法
4 链路状态路由算法
Dijkstra 算法
- 所有结点(路由器)掌握网络拓扑和链路费用
- 通过“链路状态广播”
- 所有结点拥有相同信息
- 计算从一个结点(“源” )到达所有其他结点的最
短路径- 获得该结点的转发表
- 迭代: k次迭代后，得到到达k个目的结点的最短路径
符号
- c(x,y): 结点x到结点y链路费用；如果x和y不直接相连，则=∞
- D(v): 从源到目的v的当前路径费用值
- p(v): 沿从源到v的当前路径， v的前序结点
- N’: 已经找到最小费用路径的结点集合
Dijkstra 算法
Dijkstra 算法:例1
Dijkstra 算法:例2
Dijkstra 算法:讨论
算法复杂性: n个结点
- 每次迭代: 需要检测所有不在集合N’中的结点w
- n(n+1)/2次比较: O(n2)
- 更高效的实现: O(nlogn)
存在震荡(oscillations)可能:
- e.g., 假设链路费用是该链路承载的通信量
5 距离向量(Distance Vector)路由算法
Bellman-Ford方程(动态规划)
Bellman-Ford 举例
距离向量路由算法
- 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)
-
异步迭代:
- 引发每次局部迭代的因素：局部链路费用改变、来自邻居的DV更新
-
分布式:
- 每个结点只当DV变化时才通告给邻居，邻居在必要时（其DV更新
后发生改变）再通告它们的邻居
- 每个结点只当DV变化时才通告给邻居，邻居在必要时（其DV更新
每个结点:
距离向量路由算法：举例
距离向量DV: 链路费用变化
链路费用变化:
- 结点检测本地链路费用变化
- 更新路由信息，重新计算距离向量
- 如果DV改变，通告所有邻居
t0 : y检测到链路费用改变 ，更新DV，通告其邻居。
t1 : z收到y的DV更新，更新其距离向量表，计算到达x的最新最小费用，更新其DV，并发送给其所有邻居。
t2 : y收到z的DV更新， 更新其距离向量表，重新计算y的DV，未发生改变，不再向z发送DV。
“☺好消息传播快！ ”
距离向量DV: 无穷计数问题
毒性逆转(poisoned reverse):
- 如果一个结点(e.g. Z)到达某目的(e.g.X)的最小费用路径是通过某个邻居(e.g.Y)，则：通告给该邻居结点到达该目的的距离为无穷大。
定义最大度量(maximum metric):
- 定义一个最大的有效费用值，如15跳步， 16跳步表示∞