高级操作系统AdvancedOperatingSystem课件.ppt
《高级操作系统AdvancedOperatingSystem课件.ppt》由会员分享,可在线阅读,更多相关《高级操作系统AdvancedOperatingSystem课件.ppt(89页珍藏版)》请在三一文库上搜索。
1、高级操作系统 Advanced Operating System,陈香兰(代) 0551_3606864-83 中国科学技术大学计算机系,第四章 分布式路由算法 主要内容,分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 虚信道和虚网络 完全自适应和无死锁路由算法,第四章 分布式路由算法 主要内容( contd ),几个自适应和无死锁路由算法 容错单播的一般方法 网格和圆环中的容错单播算法 超立方中的容错单播算法 容错组播算法,4.1分布式路由算法导论 进程间通信类型,有效的进程间通信对分布式系统的性能很重要 根据目标个数的不同,进程间通信
2、的类型有: 一对一(单播) 一对多(组播) 一对所有(广播),4.1分布式路由算法导论: 通信延迟及其原因,在基于消息传递的分布式系统中,消息一般在到达目标节点之前可能要通过一个或多个中间节点,故存在通信延迟。 分布式系统中的通信延迟依赖于如下四个因素: 网络拓扑: 通常用图表示 定义处理单元(PE)之间是如何连接的 路由 决定如何选择路径以便将消息传递到目的地。,4.1分布式路由算法导论: 通信延迟及其原因(contd),流量控制 流量控制决定在消息沿路径传递时如何分配网络资源,包括: 信道 缓冲区 交换 这是一个实际的机制,它决定消息如何从一个输人信道转到一个输出信道。,4.1分布式路由算
3、法导论: 路由算法类型,路由算法类型包括: 特殊 vs. 一般 最短 vs. 非最短 确定型 vs. 适应型 源路由 vs. 目标路由 容错型 vs. 非容错型 冗余型 vs. 非冗余型 死锁避免型 vs. 非死锁避免型,4.1分布式路由算法导论: 一般型路由和特殊型路由,一般型路由算法 适合于所有类型的网络 但是对于某种特定网络不是很有效 特殊型路由算法 只对特定的网络类型有效,如超立方、网格等 这些算法由于利用了特定网络的拓扑属性,所以效率往往较高。,4.1分布式路由算法导论: 最短路由算法和非最短路由算法,最短路径算法 对给定的源-目标对给出一个代价最小的路径 路径的代价 所有跳步(连接
4、)代价的线性和。 缺点:可能会导致网络某一部分的拥塞 非最短路由算法 可以将消息路由到一个更长的路径从而避免拥塞。 在某些情况下,随机路由可能是有效的。,4.1分布式路由算法导论: 确定型路由和适应型路由,确定型路径算法 路由路径只在网络的拓扑发生改变时才发生变化, 而且它不使用任何有关网络状态的消息。 适应型路由算法 路径根据网络流量而改变。,4.1分布式路由算法导论: 容错型路由和非容错型路由,容错型路由算法 即使出现错误,被路由消息也能保证送到。 非容错型路由算法 假定路由不会出错 路由算法不必动态调整自己的活动。,4.1分布式路由算法导论: 冗余型路由和非冗余路由,冗余型路由算法 用几
5、个边分离(或节点分离)的路径向同一个目标发送多个拷贝。 只要这些路径中的一个是好的,那么就会至少有一个消息拷贝到达目标。 必须保证有且只有一个拷贝被接收 非冗余型路由算法 对每个目标只需转发消息的一个拷贝。,死锁避免型路由和 非死锁避免型路由,死锁避免型路由算法 通过仔细设计的路由算法,保证不发生死锁。 非死锁避免型路由算法 没有特别的设施来预防或避免死锁。 可能发生死锁,也可能不发生死锁。,4.1分布式路由算法导论: 路由函数,路由函数 定义一个消息如何从源节点路由到目标节点。 每个PE在收到一个消息以后,都将决定: 1)把这条消息传送到本地存储器,还是 2)转发到一个邻接的PE 有许多不同
6、的路由函数的定义,例如 依赖于目标的、依赖于输入的、依赖于源的、依赖于路径的等等 本章仅使用依赖于目标的路由函数,4.2 一般类型网络的最短路径路由算法,许多分组交换网,如法国的Transpac或美国的ARPAnet都使用最短路径路由 本节介绍三个一般类型网络的 最短路径路由算法: Dijkstra集中式算法 Ford分布式算法 ARPAnet路由算法,4.2 一般类型网络的最短路径路由算法: 分布式系统图示,一般地,一个分布式系统可以用图来表示: 节点代表PE(处理单元); 边代表通信链接; 每个链接的数字代表链接代价。 右图显示了一个分布式系 统的例子,4.2.1 Dijkstra集中式算
7、法,第一种类型的算法以集中式的风格进行路由 Dijkstra集中式算法可以发现一个源节点到所有其他节点的最短路径。 Dijkstra集中式算法需求: 需要了解给定网络的全局拓扑消息,即: 网络中所有其他节点的列表; 节点之间的所有链接; 每个链接的代价。,4.2.1 Dijkstra集中式算法: 算法描述,设 D(v)是从源s到节点v的距离(沿给定路径的链接的代价的和) l(v,w)是节点v和w之间的代价 Dijkstra算法如下: 设N=s; 对不在N中的每一个节点v,令D(v)=l(s,v)。 对那些没有连接到s的节点赋值为。 找到不在N中的一个节点w,使D(w)最小并将w加入N; 然后对
8、所有不在N中的其它节点计算并更新D(v): D(v) := minD(v), D(w)+l(w,v) 重复步骤2,直到所有节点都在N中,4.2.1 Dijkstra集中式算法: 算法举例,上述算法作用于如图所示的网络: 以P5为源节点 集合N只包含源节点P5即N= P5。 对不在N中的节点P1,P2,P3,P4计算: D(1)=D(2)=; (由于P1和P2不与P5直接相连) D(3)=l(P5 ,P3) =20 D(4)=l(P5,P4)=2,4.2.1 Dijkstra集中式算法: 算法举例(contd),取D(1),D(2),D(3),D(4)中具最小值的对应节点P4加入到集合N中, N
9、= P5,P4, 对不在N中的其它节点P3,P2,P1更新 D(1)=minD(1),D(4)+l(4,1) =min,2+=, D(2)=minD(2),D(4)+l(4,2) =min,2+1=3, D(3)=minD(3),D(4)+l(4,3) =min20,2+2=4。,4.2.1 Dijkstra集中式算法: 算法举例(contd),取D(1),D(2),D(3)中具最小值的对应节点P2加入到集合N中,N=P5,P4,P2, 对不在N中的其它节点P3,P1更新 D(1)=minD(1),D(2)+l(2,1) =min,3+4=7 D(3)=minD(3),D(2)+l(2,3)
10、=min4, 3+3=4。,4.2.1 Dijkstra集中式算法: 算法举例(contd),取D(1),D(3)中具最小值的对应节点P3加入到集合N中, N= P5,P4,P2,P3 对不在N中的其它节点P1更新 D(1)=minD(1),D(3)+l(3,1) =min7,4+5=7,4.2.1 Dijkstra集中式算法: 算法举例(contd),取D(1)中具有最小值的对应节点P1加入到集合N中, N= P5,P4,P2,P3,P1, 此时,节点都在N中,算法结束。,4.2.1 Dijkstra集中式算法: 连续的步骤,如下表:,4.2.2Ford分布式算法,第二种类型的路由算法采用分
11、散式的方法进行路由 分布式算法 每个节点在交互式的基础上和其邻节点交换代价和路由信息,直到这些节点的路由表到达最短路径的要求为止,4.2.2Ford分布式算法(contd),Ford分布式算法也包括两个部分: 一个初始步骤 一个最短距离计算的步骤 这里,最短距离指一个给定节点和目标节点之间的距离 当所有节点都带有 1)一个表示它们到目标节点距离的标记以及 2)沿着最短路径到达目标节点要经过的下一个节 点的标记 时,算法结束。,4.2.2Ford分布式算法: 算法描述,每个节点v,都有(n,D(v)的标记。 D(v)代表该节点到目标节点的最短距离的当前值; n是截至目前得到的最短路径的下一个节点
12、。 初始步骤: 设d是目标节点。 令D(d)=0,将所有其它节点标记为(.,),4.2.2Ford分布式算法: 算法描述(contd),最短距离计算步骤: 对所有节点的最短路径做标记: 对每个节点vd: 使用v的每个邻节点w的当前D(w) 计算D(w)+l(w, v),使得 D(v):=minD(v),D(w)+l(w,v) 更新v的标记:用使上述表达式取值最小的邻接节点代替n,并用新值代替D(v)。 对每个节点重复上述操作,直到不再有改变,4.2.2Ford分布式算法: 举例,上述算法作用于如图所示的网络: 以P5为目标节点 初始: 令D(5) = 0,将其他节点P1,P2,P3,P4都标记
13、为(.,),4.2.2Ford分布式算法: 举例:第一轮,对于P1, 邻节点为P2,P3,由当前标记可知P2,P3距离P5都为,则P1不能通过任何节点到达P5,P1仍标记为(.,) 同理,P2仍标记为(.,) 对于P3, 邻节点为P1,P2,P4,P5,其中 D(1)= D(2)=D(4)=,D(5)=0 由于P3到P5的距离20+D(5)为20 小于当前D(3)= , 表明P3经P5有最短路径可达P5 故P3标记为(P5, 20) 同理,P标记为(P5, 2)。,4.2.2Ford分布式算法: 举例:第二轮,对于P1, 邻节点为P2,P3,由当前标记可知P5距离P2为,距离P3为20,则P1
14、通过P3有最短路径到达P5,D(1)为P1到P3的距离与P3到P5的距离之和为5+20=25,故P1标记为(P3,25); 对于P2, 邻节点为P1,P3,P4,计算P2到 Pi (i = 1,3,4)的距离与当前D(i)之 和,并取最小值,可见计算P2到 P4的距离与当前D(4)之和最小为 3,说明P2经P4有最短路径到达 P5,故P2标记更新为(P4,3); 同理,更新P3和P4的标记为 (P4,4),(P5,2),4.2.2Ford分布式算法: 举例:第三轮,按同样方法更新P1,P2,P3,P4的标记为: (P2,7),(P4,3),(P4,4),(P5,2); 由于此后再重复以上算法试
15、图更新 每一个节点的标记都不会改变其 标记,算法结束。,4.2.2Ford分布式算法: 举例小结,4.2.2Ford分布式算法(contd),上例中,所有节点的行为在经过几轮之后都被同步了 上述同步方法仅仅是为了便于演示 同步方法是指所有节点在每一轮中都更新一次标记 Ford算法也适用于异步系统, 其中每个节点以随机的速率更新其D(v)值。,4.2.3 ARPAnet路由算法,ARPAnet的路由算法是一个可靠、实用的分布式路由算法,也是今天流行的Internet 路由算法的前身。 与Ford算法比较相似 不同的是 算法中的节点都维护一个一般化的路由表,以便记录通过不同邻接节点的最短路径。 这
16、个路由表包含从这个节点到所有其它节点的最优路径的延迟。 每隔固定的时间间隔,路由表就被传送到它的所有邻接节点,直到最小延迟表在某一点达到稳定为止。,4.2.3 ARPAnet路由算法: 举例,举例说明:用ARPAnet路由算法时,P1,P2,P3,P4的一般路由表,仍以P5为目标节点 每个表格都包含通过每个邻居到达P5的最短距离 假设在时刻0前已经达到了一个稳定点 即网络延迟表如右图,4.2.3 ARPAnet路由算法: 举例(contd),假设0时刻,P4与P5之间链接失效,则它更新它的路由延迟表,并传输给P4的所有邻节点,从而使那些节点的路由延迟表发生变化,直到产生一个新的稳定点,4.2.
17、3 ARPAnet路由算法: 举例(contd),4.2.3 ARPAnet路由算法: 举例(contd),上述过程一直持续到达到一个新的稳定点,P1,P2,P3,P4分别用了20,19,17,20个时间间隔,如下图所示。,4.2.3 ARPAnet路由算法(contd),ARPAnet路由算法中 每个节点对所有邻居都发送相同消息,对接收节点不做任何标识。 这样,某些节点就会接收无用消息。 在链接节点失效时候,这些消息会导致我们不期望的循环。 例如,4.2.3 ARPAnet路由算法: 不期望的循环,举例,例如,P4和P5链接失效时,P4的最短路径为4,但是这个4来自于P2,而P2到P5的最短
18、路径原来就依赖于P4与P5的链接,由于P4使用P2的信息时,P2的信息尚未得到更新,导致出现不期望的循环:P4P2P4,4.2.3 ARPAnet路由算法: 不期望循环的消除,循环的消除是在路由消息中包含路径的所有节点,并把这些消息发给邻居节点。 然而,它的效率较底,因为它的额外开销太大。 Shin和Chou,提出了一个避免循环算法:只需在路由消息中存储路径中最近的l个节点,l与相应网络中循环的最大长度有关,4.3特殊类型网络的单播路由算法,一般类型网络的路由算法适用于所有拓扑类型的网络。但是, 每个节点需要维持路由延迟表,而且 不适用于特殊类型的网络,原因是效率太低。 得益于特殊网络的拓扑特
19、性,可以不使用路由延迟表而构造最短路径路由算法 本节介绍三种特殊网络的单播路由算法: 双向环单播路由算法 网格和圆环单播路由算法 超立方单播路由算法,4.3.1 双向环单播路由算法,在双向环上进行决定型单播路由非常简单: 消息沿着一个方向被转发:顺时针或者逆时针 由于消息可以沿两个方向发送,所以由源节点根据目标节点的位置决定发送方向: 如果目标离顺时针方向近,则用顺时针方向; 否则选择逆时针方向。 一个消息通过几个中间节点按照顺时针或逆时针方向传递,直到到达目标节点。,4.3.1 双向环单播路由算法( contd ),双向环上的单播路由算法可以使用两条路径: 一条沿着顺时针, 另一条沿着逆时针
20、。 消息 也可以被复制,然后每个方向发一个拷贝; 也可以分成两半,每半转发到一个方向。,4.3.1 双向环单播路由算法: 算法一般化,双向环是k元1维立方,即只有一维度。 若维度大于1,例如网格和超立方,就用有序维度路由 每次将每个消息向一个维度路由 圆环:在一个维度中的各点以环的方式连接起来,带有周边连接 网格:一个维度中的各点以线性排列的形式连接起来,没有周边连接,4.3.1 双向环单播路由算法: 算法一般化( contd ),环形路由方法可用于在一个维度中对消息进行路由。 沿着一个线性排列路由是很简单的。 当消息到达每个维度的对等者时,就使用下一个维度。 通过使经过的各个维度保持一个单调
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高级 操作系统 AdvancedOperatingSystem 课件
链接地址:https://www.31doc.com/p-3165699.html