中国科学技术大学：《高级操作系统 Advanced Operating System》课程PPT教学课件（分布式系统设计）分布式路由算法（1/3）

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

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

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

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

4.1分布式路由算法导论 一、进程间通信类型 有效的进程间通信对分布式系统的性能很重要 根据日标个数的不同，进程间通信的类型有： 。一对一（单播 ● 一对多（组播） 一对所有（广播） 2008.3.28 Advanced Operating System 4/91

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

4.1分布式路由算法导论： 二、通信延迟及其原因 在基于消息传递的分布式系统中，消息一般在 到达目标节点之前可能要通过一个或多个中间 节点，故存在通信延迟 ·分布式系统中的通信延迟依赖于如下四个因素： 。网络拓扑、路由、流量控制、交换 2008.3.28 Advanced Operating System 5/91

2008.3.28 Advanced Operating System 5/91 4.1分布式路由算法导论： 二、通信延迟及其原因 ⚫ 在基于消息传递的分布式系统中，消息一般在 到达目标节点之前可能要通过一个或多个中间 节点，故存在通信延迟。 ⚫ 分布式系统中的通信延迟依赖于如下四个因素： ⚫ 网络拓扑、路由、流量控制、交换

4.1分布式路由算法导论： 二、通信延迟及其原因(cont'd) 1、网络拓扑，也叫互连网络 网络拓扑 通常用图表示，定义处理单 元(PE)之间是如何连接的 一般类型 特殊类型 。分类 (不规则) (规则 ● 特殊类型的网络使用 k元n维立方表示 动态网络 静态网络 (基于交换) (基于固定的 点到点连接) 2008.3.28 Advanced Operating System 6/91

2008.3.28 Advanced Operating System 6/91 4.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 1、网络拓扑，也叫互连网络 ⚫ 通常用图表示，定义处理单 元（PE）之间是如何连接的 ⚫ 分类 ⚫ 特殊类型的网络使用 k元n维立方表示 网络拓扑 一般类型 (不规则) 特殊类型 (规则 动态网络 (基于交换) 静态网络 (基于固定的 点到点连接)

4.1分布式路由算法导论： 二、通信延迟及其原因(cont'd) 2、路由 ·决定如何选择路径以便将消息传递到目的地。 ●本章主要考虑路由 2008.3.28 Advanced Operating System 7/91

2008.3.28 Advanced Operating System 7/91 4.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 2、路由 ⚫ 决定如何选择路径以便将消息传递到目的地。 ⚫ 本章主要考虑路由

4.1分布式路由算法导论： 二、通信延迟及其原因(cont'd) 3、流量控制 。流量控制决定在消息沿路径传递时如何分配网络资 源， ·网络资源包括： 。信道 。缓冲区 2008.3.28 Advanced Operating System 8/91

2008.3.28 Advanced Operating System 8/91 4.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 3、流量控制 ⚫ 流量控制决定在消息沿路径传递时如何分配网络资 源， ⚫ 网络资源包括： ⚫ 信道 ⚫ 缓冲区

4.1分布式路由算法导论： 二、通信延迟及其原因(cont'd) 4、交换技术 这是一个实际的机制，它决定消息如何从一个输入信 道转到一个输出信道。 交换技术 存储转发 分割-通过 分组交换 电路交换 虚拟分割通过 虫孔路由 2008.3.28 Advanced Operating System 9/91

2008.3.28 Advanced Operating System 9/91 4.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 4、交换技术 ⚫ 这是一个实际的机制，它决定消息如何从一个输入信 道转到一个输出信道。 交换技术 存储-转发 分割-通过 分组交换 电路交换 虚拟分割-通过 虫孔路由

4.1分布式路由算法导论： 三、路由算法类型 路由算法类型包括： 1. 特殊VS.一般 2. 最短VS.非最短 3. 确定型VS.适应型 4. 源路由Vs.目标路由 5. 容错型VS.非容错型 6. 冗余型VS.非冗余型 7.死锁避免型VS.非死锁避免型 2008.3.28 Advanced Operating System 10/91

2008.3.28 Advanced Operating System 10/91 4.1分布式路由算法导论： 三、路由算法类型 ⚫ 路由算法类型包括： 1. 特殊 vs. 一般 2. 最短 vs. 非最短 3. 确定型 vs. 适应型 4. 源路由 vs. 目标路由 5. 容错型 vs. 非容错型 6. 冗余型 vs. 非冗余型 7. 死锁避免型 vs. 非死锁避免型

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

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