路由算法分类_35913.doc

路由算法及分类 路由算法及分类： 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算法，最初用于ARPANET，被RIP协议采用。 1）基本思想 每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表； 以子网中其它路由器为表的索引，表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离； 每隔一段时间，路由器向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表； 邻居结点X发来的表中，X到路由器i的距离为Xi，本路由器到X的距离为m，则路由器经过X到i的距离为Xi + m。根据不同邻居发来的信息，计算Xi + m，并取最小值，更新本路由器的路由表； 注意：本路由器中的老路由表在计算中不被使用 2）无限计算问题 算法的缺陷：对好消息反应迅速，对坏消息反应迟钝； 3）水平分裂算法 工作过程与距离向量算法相同，区别在于到X的距离不向真正通向X的邻居结点报告，使得坏消息传播的也快。 虽然广泛使用，但有时候会失败。 5、链路状态路由算法 （Link State Routing） 1）距离向量路由算法的主要问题 选择路由时，没有考虑线路带宽； 路由收敛速度慢。 2）链路状态路由算法 发现邻居结点，并学习它们的网络地址； 路由器启动后，通过发送HELLO包发现邻居结点； 两个或多个路由器连在一个LAN时，引入人工结点； 测量到每个邻居结点的延迟或开销； 一种直接的方法是：发送一个要对方立即响应的