第四章分布式路由算法 主要内容 ●分布式路由算法导论 ·一般类型网络的最短路径路由算法 ·特殊类型网络的单播算法 。特殊类型网络中的多播算法 虚信道和虚网络 完全自适应和无死锁路由算法 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维立方表示 网络拓扑 一般类型 (不规则) 特殊类型 (规则 动态网络 (基于交换) 静态网络 (基于固定的 点到点连接)