文档介绍：路由算法及分类
路由算法及分类:
1、非自适应算法,静态路由算法
不能根据网络流量和拓扑结构的变化更新路由表,使用静态路由表,也称为固定式路由选择算法。
特点:简单,开销少;灵活性差。
2、自适应算法,动态路由算法
可根据网络流量和拓扑结构的变化更新路由表。
特点:开销大;健壮性和灵活性好。
3、最优化原则(optimality principle)
如果路由器 J 在路由器 I 到 K 的最优路由上,那么从 J 到 K 的最优路由会落在同一路由上。
4、汇集树(sink tree)
从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树,称为汇集树;
路由算法的目的是找出并使用汇集树。
几种典型的路由选择算法:
1、最短路径路由算法(Shortest Path Routing)
1)基本思想
构建子网的拓扑图,图中的每个结点代表一个路由器,每条弧代表一条通信线路。为了选择两个路由器间的路由,算法在图中找出最短路径。
2)测量路径长度的方法
结点数量
地理距离
传输延迟
距离、信道带宽等参数的加权函数
3)Dijkstra算法
每个结点用从源结点沿已知最佳路径到本结点的距离来标注,标注分为临时性标注和永久性标注;
初始时,所有结点都为临时性标注,标注为无穷大;
将源结点标注为0,且为永久性标注,并令其为工作结点;
检查与工作结点相邻的临时性结点,若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注,则用新计算得到的和重新标注该结点;
在整个图中查找具有最小值的临时性标注结点,将其变为永久性结点,并成为下一轮检查的工作结点;
重复第四、五步,直到目的结点成为工作结点;
2、洪泛及选择洪泛算法
1) 洪泛算法(Flooding)
属于静态路由算法
a)基本思想
把收到的每一个包,向除了该包到来的线路外的所有输出线路发送。
b)主要问题
洪泛要产生大量重复包。
c)解决措施
每个包头包含站点计数器,每经过一站计数器减1,为0时则丢弃该包;
记录包经过的路径
2)选择性洪泛算法(selective flooding)
洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。
3)应用情况
路由器和线路的资源过于浪费,实际很少直接采用;
具有极好的健壮性,可用于军事应用;
作为衡量标准评价其它路由算法。
3、基于流量的路由算法(Flow-Based Routing)
属于静态路由算法
1)基本思想
既考虑拓扑结构,又兼顾网络负荷;
前提:每对结点间平均数据流是相对稳定和可预测的;
根据网络带宽和平均流量,可得出平均包延迟,因此路由选择问题归结为找产生网络最小延迟的路由选择算法。
提前离线(off-line)计算
2)需要预知的信息
网络拓扑结构;
通信量矩阵Fij;
线路带宽矩阵Cij;
3)路由算法(可能是临时的)
1/m = 800 bits
根据排队论,平均延迟 T = 1/ (mC - l)
4、距离向量路由算法(Distance Vector Routing)
属于动态路由算法,也称Bellman-Ford路由算法和Ford-Fulkerson算