7.2路由算法(2) 72.1最优化原则 最优化原则( optimality principle) 如果路由器J在路由器丨到K的最优路由上,那么从J 到K的最优路由会落在同一路由上。 汇集树( sink tree) 从所有的源结点到一个给定的目的结点的最优路由的集 合形成了一个以目的结点为根的树,称为汇集树 路由算法的目的是找出并使用汇集树 Fig. 5-5.(a)A subnet (b)A sink tree for router B
7.2 路由算法（2） 7.2.1 最优化原则 ▪ 最优化原则（optimality principle） - 如果路由器 J 在路由器 I 到 K 的最优路由上，那么从 J 到 K 的最优路由会落在同一路由上。 ▪ 汇集树（sink tree） - 从所有的源结点到一个给定的目的结点的最优路由的集 合形成了一个以目的结点为根的树，称为汇集树； - 路由算法的目的是找出并使用汇集树
7.2路由算法(3) 7.22最短路径路由算法( Shortest Path Routing) ■属于静态路由算法 基本思想 构建子网的拓扑图,图中的每个结点代表一个路由器, 每条弧代表一条通信线路。为了选择两个路由器间的路 由,算法在图中找出最短路径。 测量路径长度的方法 结点数量 地理距离 传输延迟 距离、信道带宽等参数的加权函数
7.2 路由算法（3） 7.2.2 最短路径路由算法（Shortest Path Routing） ▪ 属于静态路由算法 ▪ 基本思想 - 构建子网的拓扑图，图中的每个结点代表一个路由器， 每条弧代表一条通信线路。为了选择两个路由器间的路 由，算法在图中找出最短路径。 ▪ 测量路径长度的方法 - 结点数量 - 地理距离 - 传输延迟 - 距离、信道带宽等参数的加权函数
算法一( Dijkstra算法): 设源节点为1,计算源节点到所有节点的最短路径 令D(为源节点到节点v的距离,是沿某一通路的所有链路的 长度之和。再令L(为相邻节点的距离,不相邻节点到j 的L(,)为无穷大。算法如下: (1)初始化:令N表示网络节点的子集,初始时N={1}。对 于所有不在N中的节点有: D(∽)=L(,j),若节点v与节点1直接相连 D(V)=无穷大,若节点v与节点1不相连 (2)寻找一个不在N中的节点w,其D(w)最小。把W加入到N 中,然后对所有不在N中的节点,用[D,D(w)+LW,]中较 的值更新所有的D(∽)值。 (3)重复步骤(2),直到网络中所有的节点都在N中为
▪ 算法一（ Dijkstra算法）： 设源节点为1，计算源节点到所有节点的最短路径。 令D(v)为源节点到节点v的距离，是沿某一通路的所有链路的 长度之和。再令L(i,j)为相邻节点 i到j的距离，不相邻节点 i到j 的L(i,j) 为无穷大。算法如下： （1）初始化：令N表示网络节点的子集，初始时N={1}。对 于所有不在N中的节点有： D(v)=L(I,j)，若节点v与节点1直接相连 D(v)=无穷大，若节点v与节点1不相连 （2）寻找一个不在N中的节点w，其D(w)最小。把w加入到N 中，然后对所有不在N中的节点，用[D(v),D(w)+L(w,v)]中较 小的值更新所有的D(v)值。 （３）重复步骤（２），直到网络中所有的节点都在Ｎ中为 止
算法二 对每个节点赋予标记(nD0),其中D(代表从节点V到目 的节点的最段距离的当前值,而n则为沿着当前已算出的最 短通路的后继节点的编号。 12初试化:设节1为目的草点,将基他所有节点 够大的数值表示。 2)对所有除目的节点以外的节点标上最短距离,即对任何v 不等于1的节点做如下运算:对所有的与节点相邻的节点 用节点W 值D)计算DW)+Lw,其中W包括 找出其最 用此 更新原来的D 同时更新n的 可以从所得到的当前最小D()的通路中找到节点V的 继节点,此后继节点的标号就是n的当前值。 当对所有Ⅴ不等于1的节点全部都进行完上述计算,重复(2) 。若计算结果与前次一致,计算结束
▪ 算法二 对每个节点赋予标记（n,D(v)），其中D(v) 代表从节点v到目 的节点的最段距离的当前值，而n则为沿着当前已算出的最 短通路的后继节点的编号。 （１）初试化：设节点１为目的节点，将其他所有节点标上 （.,无穷大），符号.表示暂时空缺，而无穷大可以用任何足 够大的数值表示。 （2）对所有除目的节点以外的节点标上最短距离，即对任何v 不等于1的节点做如下运算：对所有的与节点v相邻的节点w ，用节点w的当前值D(w)计算D(w)+L(w,v)，其中w包括1， 找出其最小值，用此最小值更新原来的D(v)。同时更新n的 值。可以从所得到的当前最小D(v)的通路中找到节点v的后 继节点，此后继节点的标号就是n的当前值。 当对所有v不等于1的节点全部都进行完上述计算，重复（2） 。若计算结果与前次一致，计算结束
B(2,A) C(∞,-) 3)F(a-)D→ H G(6,A) H(∞。 B(2,A) C(9,B) B(2,A) C(9,B E(4,B) E(4,B) F(∞,-)>D( A口 F(6,E)D(∞,1 H(∞o,-) B(2,A) B(2,A) C(9,B) E(4,B F6.E)DD(∞2)A F(6E)>D( G(5,E) H(9,G) G(5,E) H(8,F) Fig. 5-6. The first five steps used in computing the shortest path from a to D. The arrows indicate the working node