2.1分布式路由算法导论： 冗余型路由和非冗余路由 。冗余型路由算法 用几个边分离（或节点分离）的路径向同一个目标 发送多个拷贝。 只要这些路径中的一个是好的，那么就会至少有一 个消息拷贝到达目标。 。必须保证有且只有一个拷贝被接收 ·非冗余型路由算法 。对每个日标只需转发消息的一个拷贝
2.1分布式路由算法导论： 冗余型路由和非冗余路由 ⚫ 冗余型路由算法 ⚫ 用几个边分离（或节点分离）的路径向同一个目标 发送多个拷贝。 ⚫ 只要这些路径中的一个是好的，那么就会至少有一 个消息拷贝到达目标。 ⚫ 必须保证有且只有一个拷贝被接收 ⚫ 非冗余型路由算法 ⚫ 对每个目标只需转发消息的一个拷贝
死锁避免型路由和 非死锁避免型路由 ●死锁避免型路由算法 。通过仔细设计的路由算法，保证不发生死锁。 ·非死锁避免型路由算法 。没有特别的设施来预防或避免死锁。 。可能发生死锁，也可能不发生死锁
死锁避免型路由和 非死锁避免型路由 ⚫ 死锁避免型路由算法 ⚫ 通过仔细设计的路由算法，保证不发生死锁。 ⚫ 非死锁避免型路由算法 ⚫ 没有特别的设施来预防或避免死锁。 ⚫ 可能发生死锁，也可能不发生死锁
2.1分布式路由算法导论： 路由函数 ·路由函数 ·定义一个消息如何从源节点路由到目标节点。 ● 每个PE在收到一个消息以后，都将决定： 1)把这条消息传送到本地存储器，还是 2)转发到一个邻接的PE 。有许多不同的路由函数的定义，例如 依赖于目标的、依赖于输入的、依赖于源的、依赖 于路径的等等 ·本章仅使用依赖于目标的路由函数
2.1分布式路由算法导论： 路由函数 ⚫ 路由函数 ⚫ 定义一个消息如何从源节点路由到目标节点。 ⚫ 每个PE在收到一个消息以后，都将决定： 1）把这条消息传送到本地存储器，还是 2）转发到一个邻接的PE ⚫ 有许多不同的路由函数的定义，例如 ⚫ 依赖于目标的、依赖于输入的、依赖于源的、依赖 于路径的等等 ⚫ 本章仅使用依赖于目标的路由函数
2.2一般类型网络的最短路径路由 算法 。许多分组交换网，如法国的Transpac或美国的 ARPAneti都使用最短路径路由 本节介绍三个一般类型网络的 最短路径路由算法： 。Dijkstra集中式算法 。Ford分布式算法 ●ARPAnet路由算法
2.2 一般类型网络的最短路径路由 算法 ⚫ 许多分组交换网，如法国的Transpac或美国的 ARPAnet都使用最短路径路由 ⚫ 本节介绍三个一般类型网络的 最短路径路由算法： ⚫ Dijkstra集中式算法 ⚫ Ford分布式算法 ⚫ ARPAnet路由算法
2.2一般类型网络的最短路径路由算法： 分布式系统图示 一般地，一个分布式系统可以用图来表示： 节点代表PE(处理单元)； 边代表通信链接； 每个链接的数字代表链接代价。 P2 右图显示了一个分布式系 4 统的例子 P1 3 P4 2 P5 20 P3
2.2 一般类型网络的最短路径路由算法： 分布式系统图示 ⚫ 一般地，一个分布式系统可以用图来表示： 节点代表PE（处理单元）； 边代表通信链接； 每个链接的数字代表链接代价。 ⚫ 右图显示了一个分布式系 统的例子 P1 P2 P3 P4 P5 4 5 3 1 2 2 20