中国科学技术大学：《高级操作系统 Advanced Operating System》课程教学资源（PPT课件讲稿）第二章 分布式路由算法主要内容（1/2，主讲：陈香兰）

第二章分布式路由算法 主要内容 ·分布式路由算法导论 ·一般类型网络的最短路径路由算法 。特殊类型网络的单播算法 。特殊类型网络中的多播算法 ·虚信道和虚网络 ·完全自适应和无死锁路由算法

第二章 分布式路由算法 主要内容 ⚫ 分布式路由算法导论 ⚫ 一般类型网络的最短路径路由算法 ⚫ 特殊类型网络的单播算法 ⚫ 特殊类型网络中的多播算法 ⚫ 虚信道和虚网络 ⚫ 完全自适应和无死锁路由算法

第二章分布式路由算法 主要内容(cont'd) ·几个自适应和无死锁路由算法 ·容错单播的一般方法 ·网格和圆环中的容错单播算法 ● 超立方中的容错单播算法 ·容错组播算法

第二章 分布式路由算法 主要内容（ cont'd ） ⚫ 几个自适应和无死锁路由算法 ⚫ 容错单播的一般方法 ⚫ 网格和圆环中的容错单播算法 ⚫ 超立方中的容错单播算法 ⚫ 容错组播算法

2.1分布式路由算法导论 进程间通信类型 ●有效的进程间通信对分布式系统的性能很重要 ·根据目标个数的不同，进程间通信的类型有： 。一对一（单播 一对多（组播) 一对所有（广播》

2.1分布式路由算法导论 进程间通信类型 ⚫ 有效的进程间通信对分布式系统的性能很重要 ⚫ 根据目标个数的不同，进程间通信的类型有： ⚫ 一对一（单播） ⚫ 一对多（组播） ⚫ 一对所有（广播）

2.1分布式路由算法导论： 通信延迟及其原因 在基于消息传递的分布式系统中，消息一般在 到达目标节点之前可能要通过一个或多个中间 节点，故存在通信延迟 c ·分布式系统中的通信延迟依赖于如下四个因素： 。网络拓扑： 。通常用图表示 ·定义处理单元(PE)之间是如何连接的 路由 决定如何选择路径以便将消息传递到日的地

2.1分布式路由算法导论： 通信延迟及其原因 ⚫ 在基于消息传递的分布式系统中，消息一般在 到达目标节点之前可能要通过一个或多个中间 节点，故存在通信延迟。 ⚫ 分布式系统中的通信延迟依赖于如下四个因素： ⚫ 网络拓扑： ⚫ 通常用图表示 ⚫ 定义处理单元（PE）之间是如何连接的 ⚫ 路由 ⚫ 决定如何选择路径以便将消息传递到目的地

2.1分布式路由算法导论： 通信延迟及其原因(cont'd) 。流量控制 ·流量控制决定在消息沿路径传递时如何分配网络资源， 包括： ·信道 ·缓冲区 交换 。这是一个实际的机制，它决定消息如何从一个输入信道 转到一个输出信道

2.1分布式路由算法导论： 通信延迟及其原因（cont'd） ⚫ 流量控制 ⚫ 流量控制决定在消息沿路径传递时如何分配网络资源， 包括： ▪ 信道 ▪ 缓冲区 ⚫ 交换 ⚫ 这是一个实际的机制，它决定消息如何从一个输入信道 转到一个输出信道

2.1分布式路由算法导论： 路由算法类型 。路由算法类型包括： 。特殊VS.一般 。最短VS.非最短 确定型VS.适应型 源路由VS.目标路由 容错型VS.非容错型 。冗余型VS.非冗余型 死锁避免型VS.非死锁避免型

2.1分布式路由算法导论： 路由算法类型 ⚫ 路由算法类型包括： ⚫ 特殊 vs. 一般 ⚫ 最短 vs. 非最短 ⚫ 确定型 vs. 适应型 ⚫ 源路由 vs. 目标路由 ⚫ 容错型 vs. 非容错型 ⚫ 冗余型 vs. 非冗余型 ⚫ 死锁避免型 vs. 非死锁避免型

2.1分布式路由算法导论： 一般型路由和特殊型路由 一般型路由算法 。适合于所有类型的网络 。但是对于某种特定网络不是很有效 特殊型路由算法 只对特定的网络类型有效，如超立方、网格等 这些算法由于利用了特定网络的拓扑属性，所以效 率往往较高

2.1分布式路由算法导论： 一般型路由和特殊型路由 ⚫ 一般型路由算法 ⚫ 适合于所有类型的网络 ⚫ 但是对于某种特定网络不是很有效 ⚫ 特殊型路由算法 ⚫ 只对特定的网络类型有效，如超立方、网格等 ⚫ 这些算法由于利用了特定网络的拓扑属性，所以效 率往往较高

2.1分布式路由算法导论： 最短路由算法和非最短路由算法 。最短路径算法 。对给定的源-目标对给出一个代价最小的路径 路径的代价 ·所有跳步（连接）代价的线性和。 缺点：可能会导致网络某一部分的拥塞 非最短路由算法 可以将消息路由到一个更长的路径从而避免拥塞。 在某些情况下，随机路由可能是有效的

2.1分布式路由算法导论： 最短路由算法和非最短路由算法 ⚫ 最短路径算法 ⚫ 对给定的源-目标对给出一个代价最小的路径 ⚫ 路径的代价 ⚫ 所有跳步（连接）代价的线性和。 ⚫ 缺点：可能会导致网络某一部分的拥塞 ⚫ 非最短路由算法 ⚫ 可以将消息路由到一个更长的路径从而避免拥塞。 ⚫ 在某些情况下，随机路由可能是有效的

2.1分布式路由算法导论： 确定型路由和适应型路由 确定型路径算法 。路由路径只在网络的拓扑发生改变时才发生变化， ·而且它不使用任何有关网络状态的消息。 适应型路由算法 。路径根据网络流量而改变

2.1分布式路由算法导论： 确定型路由和适应型路由 ⚫ 确定型路径算法 ⚫ 路由路径只在网络的拓扑发生改变时才发生变化， ⚫ 而且它不使用任何有关网络状态的消息。 ⚫ 适应型路由算法 ⚫ 路径根据网络流量而改变

2.1分布式路由算法导论： 容错型路由和非容错型路由 ●容错型路由算法 。即使出现错误，被路由消息也能保证送到。 ·非容错型路由算法 。假定路由不会出错 。路由算法不必动态调整自己的活动

2.1分布式路由算法导论： 容错型路由和非容错型路由 ⚫ 容错型路由算法 ⚫ 即使出现错误，被路由消息也能保证送到。 ⚫ 非容错型路由算法 ⚫ 假定路由不会出错 ⚫ 路由算法不必动态调整自己的活动