文档介绍：分布式路由算法主要内容（ cont'd ）
一般类型网络的分布式路由算法
自适应和无死锁路由算法
网格和圆环中的容错单播算法
超立方中的容错单播算法
容错组播算法
1
可编辑ppt
进程间通信类型
有效的进程间通信对分布式系统的性能很重要
根据目标个数的不同，进程间通信的类型有：
一对一（单播）
一对多（组播）
一对所有（广播）
2
可编辑ppt
通信延迟及其原因
在基于消息传递的分布式系统中，消息一般在到达目标节点之前可能要通过一个或多个中间节点，故存在通信延迟。
分布式系统中的通信延迟依赖于如下四个因素：
网络拓扑：
通常用图表示
定义处理单元（PE）之间是如何连接的
路由
决定如何选择路径以便将消息传递到目的地。
3
可编辑ppt
通信延迟及其原因（cont'd）
流量控制
流量控制决定在消息沿路径传递时如何分配网络资源，包括：
信道
缓冲区
交换
这是一个实际的机制，它决定消息如何从一个输入信道转到一个输出信道。
4
可编辑ppt
路由算法类型
路由算法类型包括：
特殊 vs. 一般
最短 vs. 非最短
确定型 vs. 适应型
源路由 vs. 目标路由
容错型 vs. 非容错型
冗余型 vs. 非冗余型
死锁避免型 vs. 非死锁避免型
5
可编辑ppt
一般型路由和特殊型路由
一般型路由算法
适合于所有类型的网络
但是对于某种特定网络不是很有效
特殊型路由算法
只对特定的网络类型有效，如超立方、网格等
这些算法由于利用了特定网络的拓扑属性，所以效率往往较高。
6
可编辑ppt
最短路由算法和非最短路由算法
最短路径算法
对给定的源-目标对给出一个代价最小的路径
路径的代价
所有跳步（连接）代价的线性和。
缺点：可能会导致网络某一部分的拥塞
非最短路由算法
可以将消息路由到一个更长的路径从而避免拥塞。
在某些情况下，随机路由可能是有效的。
7
可编辑ppt
确定型路由和适应型路由
确定型路径算法
路由路径只在网络的拓扑发生改变时才发生变化，
而且它不使用任何有关网络状态的消息。
适应型路由算法
路径根据网络流量而改变。
8
可编辑ppt
容错型路由和非容错型路由
容错型路由算法
即使出现错误，被路由消息也能保证送到。
非容错型路由算法
假定路由不会出错
路由算法不必动态调整自己的活动。
9
可编辑ppt
冗余型路由和非冗余路由
冗余型路由算法
用几个边分离（或节点分离）的路径向同一个目标发送多个拷贝。
只要这些路径中的一个是好的，那么就会至少有一个消息拷贝到达目标。
必须保证有且只有一个拷贝被接收
非冗余型路由算法
对每个目标只需转发消息的一个拷贝。
10
可编辑ppt