第四章分布式路由算法 主要内容 ●分布式路由算法导论 ·一般类型网络的最短路径路由算法 ·特殊类型网络的单播算法 。特殊类型网络中的多播算法 虚信道和虚网络 完全自适应和无死锁路由算法 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、一般型路由和特殊型路由 ⚫ 一般型路由算法 ⚫ 适合于所有类型的网络 ⚫ 但是对于某种特定网络不是很有效 ⚫ 特殊型路由算法 ⚫ 只对特定的网络类型有效,如超立方、网格等 ⚫ 这些算法由于利用了特定网络的拓扑属性,所以效 率往往较高