分布式系统中的路由算法.ppt

该【分布式系统中的路由算法 】是由【sanshenglu2】上传分享，文档一共【87】页，该文档可以免费在线阅读，需要了解更多关于【分布式系统中的路由算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。分布式系统中的路由算法
进程间通信类型
有效的进程间通信对分布式系统的性能很重要
根据目标个数的不同,进程间通信的类型
一对一(单播)
一对多(组播)
一对所有(广播)
分布式系统中的路由算法
通信延迟及其原因
在基于消息传递的分布式系统中,消息一般在到达目标节点之前可能要通过一个或多个中间节点,故存在通信延迟。
分布式系统中的通信延迟依赖于如下四个因素:
网络拓扑:
通常用图表示
定义处理单元(PE)之间是如何连接的
路由
决定如何选择路径以便将消息传递到目的地。
分布式系统中的路由算法
通信延迟及其原因(cont'd)
流量控制
流量控制决定在消息沿路径传递时如何分配网络资源,包括:
信道
缓冲区
交换
这是一个实际的机制,它决定消息如何从一个输入信道转到一个输出信道。
分布式系统中的路由算法
路由算法类型
路由算法类型包括:







分布式系统中的路由算法
一般型路由和特殊型路由
一般型路由算法
适合于所有类型的网络
但是对于某种特定网络不是很有效
特殊型路由算法
只对特定的网络类型有效,如超立方、网格等
这些算法由于利用了特定网络的拓扑属性,所以效率往往较高。
分布式系统中的路由算法
最短路由算法和非最短路由算法
最短路径算法
对给定的源-目标对给出一个代价最小的路径
路径的代价
所有跳步(连接)代价的线性和。
缺点:可能会导致网络某一部分的拥塞
非最短路由算法
可以将消息路由到一个更长的路径从而避免拥塞。
在某些情况下,随机路由可能是有效的。
分布式系统中的路由算法
确定型路由和适应型路由
确定型路径算法
路由路径只在网络的拓扑发生改变时才发生变化,
而且它不使用任何有关网络状态的消息。
适应型路由算法
路径根据网络流量而改变。
分布式系统中的路由算法
容错型路由和非容错型路由
容错型路由算法
即使出现错误,被路由消息也能保证送到。
非容错型路由算法
假定路由不会出错
路由算法不必动态调整自己的活动。
分布式系统中的路由算法
冗余型路由和非冗余路由
冗余型路由算法
用几个边分离(或节点分离)的路径向同一个目标发送多个拷贝。
只要这些路径中的一个是好的,那么就会至少有一个消息拷贝到达目标。
必须保证有且只有一个拷贝被接收
非冗余型路由算法
对每个目标只需转发消息的一个拷贝。
分布式系统中的路由算法