文档介绍：第6章路由算法
u
y
x
w
v
z
2
2
1
3
1
1
2
5
3
5
图: 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) }
图抽象
标注:图抽象在其它网络上下文中也十分有用
例如: P2P, N是peer结点,E是TCP的连接
图抽象:边的代价
u
y
x
w
v
z
2
2
1
3
1
1
2
5
3
5
c(x,x’) = 链路的代价(x,x’)
- ., c(w,z) = 5
代价可能总为1, 或者是链路带宽的倒数, 或者是拥塞情况的倒数
Cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + …+ c(xp-1,xp)
问题: 结点u到结点z的最小代价路径是什么?
路由算法:发现最小代价路径的算法
路由:按照某种指标(传输延迟,所经过的站点数目等)找到一条从源结点到目标结点的较好路径
较好路径: 按照某种指标较小的路径
路由算法(routing algorithm):网络层软件的一部分,完成路由功能
路由的时机
虚电路:在建立虚电路时使用(会话路由选择,session routing)
数据报:每个分组独立路由
路由的概念
汇集树(sink tree)
一个结点的汇集树:所有其它结点到此结点的最优路径形成的树
路由算法就是为所有路由器找到并使用汇集树
最优化原则(optimality principle)
正确性(correctness):算法必须正确和完整,使分组一站一站接力,正确发向目的站点
简单性(simplicity):在计算机上,算法的实现应该简单。最优但复杂的算法,时间延迟很大,不实用,不应为了获取路由信息而增加很多的通信量
健壮性(robustness):算法应适应通信量和网络拓扑的变化,不向很拥挤的链路发送数据,不向中断的链路发送数据
稳定性(stability):产生的路由不应该摇摆
公平性(fairness):对每一个站点都公平
最优性(optimality):某一个指标的最优(时间、费用或综合指标)。实际上,获取最优的结果代价较高,可以选择次优的结果
路由算法的原则
路由算法的分类
自适应或者非自适应?
非自适应算法(non-adaptive algorithm):不能适应网络拓扑和通信量的变化,路由表是事先计算好的,也叫静态路由算法和非自适应路由算法
自适应算法(adaptive algorithm):能适应网络拓扑和通信量的变化,也叫动态路由算法和自适应路由算法
固定路由算法(fixed routing algorithm)
洪泛法(flooding)
随机走动法(random walk)
基于流量的路由算法(flow-based routing)
非自适应路由算法
每个网络结点存储一张表格,表格的每一项记录到达某个目的结点的下一结点或链路,而不是记录到该目的结点的所有中间结点
优点:简单,适合一个负载稳定和拓扑变化不大的网络
缺点:灵活性较差,无法对网络的拥塞和故障作出反应
固定路由算法
结点收到不是发给它的分组时,就将该分组的副本向除输入链路之外的所有与此结点相连的链路转发出去
当网络的通信量很小时,该方法使分组的时延为最小,因为在并行发送的路由中,肯定有一条为最佳
该方法的缺点是网络中的分组数目会迅速增加,导致网络出现拥塞现象,应用并不广泛
该方法可用于健壮性要求很高的地方,如军事网络
洪泛法