4.1分布式路由算法导论： 2、最短路由算法和非最短路由算法 。最短路径算法 ·对给定的源-目标对给出一个代价最小的路径 。路径的代价 ·所有跳步（连接）代价的线性和。 缺点：可能会导致网络某一部分的拥塞 非最短路由算法 可以将消息路由到一个更长的路径从而避免拥塞。 在某些情况下，随机路由可能是有效的。 2008.3.28 Advanced Operating System 12/91
2008.3.28 Advanced Operating System 12/91 4.1分布式路由算法导论： 2、最短路由算法和非最短路由算法 ⚫ 最短路径算法 ⚫ 对给定的源-目标对给出一个代价最小的路径 ⚫ 路径的代价 ⚫ 所有跳步（连接）代价的线性和。 ⚫ 缺点：可能会导致网络某一部分的拥塞 ⚫ 非最短路由算法 ⚫ 可以将消息路由到一个更长的路径从而避免拥塞。 ⚫ 在某些情况下，随机路由可能是有效的
4.1分布式路由算法导论： 3、确定型路由和适应型路由 确定型路径算法（静态） ·路由路径只在网络的拓扑发生改变时才发生变化， ·而且它不使用任何有关网络状态的消息。 适应型路由算法（动态） 。路径根据网络流量而改变。 2008.3.28 Advanced Operating System 13/91
2008.3.28 Advanced Operating System 13/91 4.1分布式路由算法导论： 3、确定型路由和适应型路由 ⚫ 确定型路径算法（静态） ⚫ 路由路径只在网络的拓扑发生改变时才发生变化， ⚫ 而且它不使用任何有关网络状态的消息。 ⚫ 适应型路由算法（动态） ⚫ 路径根据网络流量而改变
4.1分布式路由算法导论： 5、容错型路由和非容错型路由 ●容错型路由算法 ·即使出现错误，被路由消息也能保证送到。 ·非容错型路由算法 。假定路由不会出错 。路由算法不必动态调整自己的活动。 2008.3.28 Advanced Operating System 14/91
2008.3.28 Advanced Operating System 14/91 4.1分布式路由算法导论： 5、容错型路由和非容错型路由 ⚫ 容错型路由算法 ⚫ 即使出现错误，被路由消息也能保证送到。 ⚫ 非容错型路由算法 ⚫ 假定路由不会出错 ⚫ 路由算法不必动态调整自己的活动
4.1分布式路由算法导论： 6、冗余型路由和非冗余路由 。冗余型路由算法 用几个边分离（或节点分离）的路径向同一个目标 发送多个拷贝。 ● 只要这些路径中的一个是好的，那么就会至少有一 个消息拷贝到达目标。 必须保证有且只有一个拷贝被接收 。非冗余型路由算法 。对每个目标只需转发消息的一个拷贝。 2008.3.28 Advanced Operating System 15/91
2008.3.28 Advanced Operating System 15/91 4.1分布式路由算法导论： 6、冗余型路由和非冗余路由 ⚫ 冗余型路由算法 ⚫ 用几个边分离（或节点分离）的路径向同一个目标 发送多个拷贝。 ⚫ 只要这些路径中的一个是好的，那么就会至少有一 个消息拷贝到达目标。 ⚫ 必须保证有且只有一个拷贝被接收 ⚫ 非冗余型路由算法 ⚫ 对每个目标只需转发消息的一个拷贝
4.1分布式路由算法导论： 7、死锁避免型路由和非死锁避免型路由 死锁避免型路由算法 ·通过仔细设计的路由算法，保证不发生死锁。 ·非死锁避免型路由算法 ·没有特别的设施来预防或避免死锁。 。可能发生死锁，也可能不发生死锁。 2008.3.28 Advanced Operating System 16/91
2008.3.28 Advanced Operating System 16/91 4.1分布式路由算法导论： 7、死锁避免型路由和非死锁避免型路由 ⚫ 死锁避免型路由算法 ⚫ 通过仔细设计的路由算法，保证不发生死锁。 ⚫ 非死锁避免型路由算法 ⚫ 没有特别的设施来预防或避免死锁。 ⚫ 可能发生死锁，也可能不发生死锁