网络层-路由协议.ppt

第五章 路由算法(1)路由算法是网络层软件的一部分子网采用数据报方式,每个包都要做路由选择;子网采用虚电路方式,只需在建立连接时做一次路由选择。路由算法应具有的特性正确性(correctness)简单性(simplicity)健壮性(robustness)稳定性(stability)公平性(fairness)最优性(optimality)路由算法分类非自适应算法,静态路由算法自适应算法, 路由算法(2) 最优化原则最优化原则(optimalityprinciple)如果路由器J在路由器I到K的最优路由上,那么从J到K的最优路由会落在同一路由上。 路由算法(3) 最短路径路由算法(ShortestPathRouting)属于静态路由算法基本思想构建子网的拓扑图,图中的每个结点代表一个路由器,每条弧代表一条通信线路。为了选择两个路由器间的路由,算法在图中找出最短路径。测量路径长度的方法结点数量地理距离传输延迟距离、 路由算法(4)Dijkstra算法每个结点用从源结点沿已知最佳路径到本结点的距离来标注,标注分为临时性标注和永久性标注;初始时,所有结点都为临时性标注,标注为无穷大;将源结点标注为0,且为永久性标注,并令其为工作结点;检查与工作结点相邻的临时性结点,若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注,则用新计算得到的和重新标注该结点;在整个图中查找具有最小值的临时性标注结点,将其变为永久性结点,并成为下一轮检查的工作结点;重复第四、五步,直到目的结点成为工作结点;例,- 路由算法(5) 洪泛算法(Flooding)属于静态路由算法基本思想把收到的每一个包,向除了该包到来的线路外的所有输出线路发送。主要问题洪泛要产生大量重复包。解决措施每个包头包含站点计数器,每经过一站计数器减1,为0时则丢弃该包; 路由算法(6)选择性洪泛算法(selectiveflooding)洪泛法的一种改进。将进来的每个包仅发送到与正确方向接近的线路上。应用情况路由器和线路的资源过于浪费,实际很少直接采用;具有极好的健壮性,可用于军事应用;作为衡量标准评价其它路由算法。 路由算法(5) 基于流量的路由算法(Flow-BasedRouting)属于静态路由算法基本思想既考虑拓扑结构,又兼顾网络负荷;前提:每对结点间平均数据流是相对稳定和可预测的;根据网络带宽和平均流量,可得出平均包延迟,因此路由选择问题归结为找产生网络最小延迟的路由选择算法。提前离线(off-line)计算需要预知的信息网络拓扑结构;通信量矩阵Fij;线路带宽矩阵Cij;路由算法(可能是临时的)。