文档介绍：第8章分布式系统中的路由算法
由NordriDesign提供
确定型路由和适应型路由
确定型路径算法
路由路径只在网络的拓扑发生改变时才发生变化，
而且它不使用任何有关网络状态的消息。
适3)=min{D(3),D(2)+l(2,3)} =min{4, 3+3}=4。
Dijkstra集中式算法： 算法举例（cont‘d）
取D(1),D(3)中具最小值的对应节点P3加入到集合N中, N= { P5,P4,P2,P3} 对不在N中的其它节点P1更新 D(1)=min{D(1),D(3)+l(3,1)} =min{7,4+5}=7
Dijkstra集中式算法： 算法举例（cont'd）
取D(1)中具有最小值的对应节点P1加入到集合N中, N= { P5,P4,P2,P3,P1}, 此时，节点都在N中，算法结束。
Dijkstra集中式算法： 连续的步骤，如下表：
Ford分布式算法
第二种类型的路由算法采用分散式的方法进行路由
分布式算法
每个节点在交互式的基础上和其邻节点交换代价和路由信息，直到这些节点的路由表到达最短路径的要求为止
Ford分布式算法（cont'd）
Ford分布式算法也包括两个部分：
一个初始步骤
一个最短距离计算的步骤
这里，最短距离指一个给定节点和目标节点之间的距离
当所有节点都带有 1）一个表示它们到目标节点距离的标记以及 2）沿着最短路径到达目标节点要经过的下一个节 点的标记时，算法结束。
Ford分布式算法： 算法描述
每个节点v，都有(n,D(v))的标记。
D(v)代表该节点到目标节点的最短距离的当前值；
n是截至目前得到的最短路径的下一个节点。
初始步骤：
设d是目标节点。
令D(d)=0，将所有其它节点标记为(.,∞)
Ford分布式算法： 算法描述（cont'd）
最短距离计算步骤：
对所有节点的最短路径做标记： 对每个节点v≠d： 使用v的每个邻节点w的当前D(w) 计算D(w)+l(w, v)，使得 D(v):=min{D(v),D(w)+l(w,v)} 更新v的标记：用使上述表达式取值最小的邻接节点代替n，并用新值代替D(v)。 对每个节点重复上述操作，直到不再有改变
Ford分布式算法： 举例
上述算法作用于如图所示的网络： 以P5为目标节点
初始： 令D(5) = 0，将其他节点P1,P2,P3,P4都标记为(.,∞)
Ford分布式算法： 举例：第一轮
对于P1，
邻节点为P2,P3，由当前标记可知P2,P3距离P5都为∞，则P1不能通过任何节点到达P5，P1仍标记为(.,∞)
同理，P2仍标记为(.,∞)
对于P3，
邻节点为P1,P2,P4,P5，其中 D(1)= D(2)=D(4)=∞,D(5)=0
由于P3到P5的距离20+D(5)为20 小于当前D(3)= ∞, 表明P3经P5有最短路径可达P5
故P3标记为(P5, 20)
同理，P4标记为(P5, 2)。
Ford分布式算法： 举例：第二轮
对于P1，
邻节点为P2,P3，由当前标记可知P5距离P2为∞，距离P3为20，则P1通过P3有最短路径到达P5，D(1)为P1到P3的距离与P3到P5的距离之和为5+20=25，故P1标记为(P3,25)；
对于P2，
邻节点为P1,P3,P4，计算P2到 Pi (i = 1,3,4)的距离与当前D(i)之 和，并取最小值，可见计算P2到 P4的距离与当前D(4)之和最小为 3，说明P2经P4有最短路径到达 P5，故P2标记更新为(P4,3)；
同理，更新P3和P4的标记为 (P4,4)，(P5,2)
Ford分布式算法： 举例：第三轮
按同样方法更新P1,P2,P3,P4的标记为： (P2,7),(P4,3),(P4,4),(P5,2)；
由于此后再重复以上算法试图更新 每一个节点的标记都不会改变其 标记，算法结束。
Ford分布式算法： 举例小结
Ford分布式算法（cont’d）
上例中，所有节点的行为在经过几轮之后都被同步了
上述同步方法仅仅是为了便于演示
同步方法是指所有节点在每一轮中都更新一次标记
Ford算法也适用于异步系统，
其中每个节点以随机的速率更新其D(v)值。
ARPAnet路由算法