最优化原则( optimality principle) 最短路径路由算法( Shortest Path Routing) 从所有的源结点到一个给定的目的结点的最优路由 的集合形成了一个以目的结点为根的树,称为汇集 属于静态路由算法 基本思想 路由算法的目的是找出并使用汇集树 构建子网的拓扑图,图中的每个结点代表一个路 由器,每条弧代表一条通信线路。为了选择两个 器间的路由,算法在图中找出最短路径 測量路径长度的方法 结点数量 距离、信道带宽等参数的加权函数 路由器B的汇集树 Dijkstra算法 采用标注的方式求出某一结点的汇集树和路由表 D(- ①每个结点用从源结点沿已知最佳路径到本结点的距离 来标注,标注分为临时性标注和永久性标注 ②初始时,所有结点都为临时性标注,标注为无穷 ③将源结点标注为0,且为永久性标注,并令其为工作 >0=+☆ (A. E) pD( ④检查与工作结点相邻的临时性结点,若该结点到工作 结点的距离与工作结点的标注之和小于该结点的标 注,则用新计算得到的和重新标注该结点 橙B ⑤在整个图中查找具有最小值的临时性标注结点,将其 变为永久性结点,并成为下一轮检查的工作结点 (B)pm)“(点m 重复第④、③步,直到所有鲒点成为工作结点 求结点A的汇集树 结点A的汇集树 距离矢量路由算法( Distance vector routing) 属于动态路由算 最初应用于 ARPANET,后来应用于因特网的RP协 议(路由信息协议) 同理,以结点E为源结点,采用m某法,日B 基本思想 求出结点E的汇集树和路由表 的路由表 每个结点通过测取与相邻结点的距离,再依据与其 相邻结点交换的距离信息,间接地求出路由表; 结点E的汇集树 各结点周期性地测取相邻结点的距离 向相邻结点发送它到每个目的结点的距离表 同时,它也接收每个邻居结点发来的距离表; 结点中的老路由表在计算中不被使用3