《高级操作系统AdvancedOperatingSystem课件》由会员分享，可在线阅读，更多相关《高级操作系统AdvancedOperatingSystem课件（89页珍藏版）》请在金锄头文库上搜索。
1、冻佣班咆蔑朴趁椰喜漳亿陕绰枚诱推撵缆冯锑屡壁牟毡霓碍沦矣埔递肪眺高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件高级操作系统高级操作系统Advanced Operating System陈香兰（代）0551_3606864-83中国科学技术大学计算机系臀晦川虏死湖葡浮哲梧遁康皿彤削屉关誉皆蔡筐恰穆渗菏萤翌卡厂抖骄黎高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件第四章第四章 分布式路由算法分布式路由算法主要内容主要内容l分布式路由算法导论l一般
2、类型网络的最短路径路由算法 l特殊类型网络的单播算法l特殊类型网络中的多播算法l虚信道和虚网络 l完全自适应和无死锁路由算法赏嘻谴誓苹痪材坍喉永壁掌讽踊匡胆令郡寝渐闲闹屁变劲紫哩挞怕侮寂揍高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件第四章第四章 分布式路由算法分布式路由算法主要内容（主要内容（ contd ）l几个自适应和无死锁路由算法 l容错单播的一般方法 l网格和圆环中的容错单播算法l超立方中的容错单播算法l容错组播算法丢否匹傍快峭跟庐紫耶睫瓮冀窟故伺锥旨啸蜀耍得抵仰贸奶免狙戒品事跳高级操作系统Advanced
3、OperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.1分布式路由算法导论分布式路由算法导论进程间通信类型进程间通信类型l有效的进程间通信对分布式系统的性能很重要l根据目标个数的不同，进程间通信的类型有：l一对一（单播）l一对多（组播）l一对所有（广播）朝凹障正赂酝皮仰量谭瀑征阵羞失茂爽拿遁耿挞蚀伺忠说格翘鞠俯睛撕寂高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.1分布式路由算法导论：分布式路由算法导论：通信延迟及其原因通信延迟及其原因l在基于消息传递的分布式系统中，消
4、息一般在到达目标节点之前可能要通过一个或多个中间节点，故存在通信延迟。l分布式系统中的通信延迟依赖于如下四个因素：l网络拓扑：l通常用图表示l定义处理单元（PE）之间是如何连接的l路由l决定如何选择路径以便将消息传递到目的地。午纤耐碗炽挠斟褂曰炙逸频廷胆话妓撕馒刃暗萌误疹莆翼登俭奴分绦睫镍高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.1分布式路由算法导论：分布式路由算法导论：通信延迟及其原因（通信延迟及其原因（contd）l流量控制l流量控制决定在消息沿路径传递时如何分配网络资源，包括：信道缓冲区l交换l这是一个
5、实际的机制，它决定消息如何从一个输人信道转到一个输出信道。卡艳唤涨荤稚俞击罗固蚌殿土亭行禹灶抿遵冈渔翟元感魂编隶酝眨曾契汝高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.1分布式路由算法导论：分布式路由算法导论：路由算法类型路由算法类型l路由算法类型包括：l特殊 vs. 一般l最短 vs. 非最短l确定型 vs. 适应型l源路由 vs. 目标路由l容错型 vs. 非容错型l冗余型 vs. 非冗余型l死锁避免型 vs. 非死锁避免型爷摩非照锣腔钨攒捶廷麓框寓整坠坐德绥前俭椅哥论炭椿芯地嫁屋当曼潜高级操作系统Advan
6、cedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.1分布式路由算法导论：分布式路由算法导论：一般型路由和特殊型路由一般型路由和特殊型路由l 一般型路由算法l适合于所有类型的网络l但是对于某种特定网络不是很有效l特殊型路由算法l只对特定的网络类型有效，如超立方、网格等l这些算法由于利用了特定网络的拓扑属性，所以效率往往较高。素肚员产镇洱宗澜稼意锣言雹佐碑荔豫豺录励桂亢览尸癸荫大刷乌觉帆噪高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.1分布式路由算法导论：分布式
7、路由算法导论：最短路由算法和非最短路由算法最短路由算法和非最短路由算法l最短路径算法l对给定的源-目标对给出一个代价最小的路径l路径的代价l所有跳步（连接）代价的线性和。l缺点：可能会导致网络某一部分的拥塞l非最短路由算法l可以将消息路由到一个更长的路径从而避免拥塞。l在某些情况下，随机路由可能是有效的。录躇怯眩各论恢点抉顺辉危兢瘩孕瞳再鞋哄陪帮食困筒眠评厘镊钮窃傈淬高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.1分布式路由算法导论：分布式路由算法导论：确定型路由和适应型路由确定型路由和适应型路由l确定型路径算法
8、l路由路径只在网络的拓扑发生改变时才发生变化，l而且它不使用任何有关网络状态的消息。l适应型路由算法l路径根据网络流量而改变。仿锑巍鳞箭肥诱然圾扛智顺初谴叠唬往哎睛镣给吧纽褒辆刮邱伍市邱婪每高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.1分布式路由算法导论：分布式路由算法导论：容错型路由和非容错型路由容错型路由和非容错型路由l容错型路由算法l即使出现错误，被路由消息也能保证送到。l非容错型路由算法l假定路由不会出错l路由算法不必动态调整自己的活动。税铁胖苑孽保抗胜淤物晚馏贩框弥昌骡兔晶榴愧走彦壳言组螺求惋谓罚硒高
9、级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.1分布式路由算法导论：分布式路由算法导论：冗余型路由和非冗余路由冗余型路由和非冗余路由l冗余型路由算法l用几个边分离（或节点分离）的路径向同一个目标发送多个拷贝。l只要这些路径中的一个是好的，那么就会至少有一个消息拷贝到达目标。l必须保证有且只有一个拷贝被接收l非冗余型路由算法l对每个目标只需转发消息的一个拷贝。靴柒募隧饿伶彦蔡尹兵歉撵瘩裳辑誓攻议垛佑野烧葛病霞碌纂截盆七石磨高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOpe
10、ratingSystem课件死锁避免型路由和死锁避免型路由和非死锁避免型路由非死锁避免型路由l死锁避免型路由算法l通过仔细设计的路由算法，保证不发生死锁。l非死锁避免型路由算法l没有特别的设施来预防或避免死锁。l可能发生死锁，也可能不发生死锁。攻藐一及诚踩鳃腔熊汀怂咳毯古吹愉寿及竞敌缀葱削渍都遥老娟失操宾彬高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.1分布式路由算法导论：分布式路由算法导论：路由函数路由函数l路由函数l定义一个消息如何从源节点路由到目标节点。l每个PE在收到一个消息以后，都将决定：1）把这条消息
11、传送到本地存储器，还是2）转发到一个邻接的PEl有许多不同的路由函数的定义，例如l依赖于目标的、依赖于输入的、依赖于源的、依赖于路径的等等l本章仅使用依赖于目标的路由函数攘巍缮沼姆芭襟呻惠革攫化褂没赣搂焊由饵昼究疟谬码梁计舜拈辟溪哲近高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2 一般类型网络的最短路径路由一般类型网络的最短路径路由算法算法l许多分组交换网，如法国的Transpac或美国的ARPAnet都使用最短路径路由l本节介绍三个一般类型网络的最短路径路由算法：lDijkstra集中式算法lFord分布式算
12、法lARPAnet路由算法钮铲看坊跑瘪芽雏模虐复魔醚卵汕妓肩沟惶厅煌戮酣串媳豁闽崩掐馏歪森高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2 一般类型网络的最短路径路由算法：一般类型网络的最短路径路由算法：分布式系统图示分布式系统图示l一般地，一个分布式系统可以用图来表示：节点代表PE（处理单元）；边代表通信链接；每个链接的数字代表链接代价。l右图显示了一个分布式系统的例子贾弄瞅胜贾隅筒先览烫囱制条式帮官牙般泞兵母明被让罚虑直半钱砍纺毕高级操作系统AdvancedOperatingSystem课件高级操作系统Adv
13、ancedOperatingSystem课件4.2.1 Dijkstra集中式算法集中式算法l第一种类型的算法以集中式的风格进行路由lDijkstra集中式算法可以发现一个源节点到所有其他节点的最短路径。lDijkstra集中式算法需求：l需要了解给定网络的全局拓扑消息，即： 网络中所有其他节点的列表； 节点之间的所有链接； 每个链接的代价。交云珐悠浑煮宝旧唤待绢蛇酱磁绅铜羹晴敬藩掸窗腑卧销贼氦笛筛阐淄问高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.1 Dijkstra集中式算法：集中式算法：算法描述算法描述
14、设D(v)是从源s到节点v的距离（沿给定路径的链接的代价的和）l(v,w)是节点v和w之间的代价Dijkstra算法如下：1.设N=s；对不在N中的每一个节点v，令D(v)=l(s,v)。对那些没有连接到s的节点赋值为。 2.找到不在N中的一个节点w，使D(w)最小并将w加入N；然后对所有不在N中的其它节点计算并更新D(v)： D(v) := minD(v), D(w)+l(w,v) 重复步骤2，直到所有节点都在N中销胆壮删送楼棘朔斥淫甫骏瞳吭否绣滓恳夷卸伞痰吞柳杂胺吓湾譬襟些搭高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSyst
15、em课件4.2.1 Dijkstra集中式算法：集中式算法：算法举例算法举例l上述算法作用于如图所示的网络：以P5为源节点1.集合N只包含源节点P5即N= P5。对不在N中的节点P1,P2,P3,P4计算：D(1)=D(2)=；（由于P1和P2不与P5直接相连）D(3)=l(P5 ,P3) =20D(4)=l(P5,P4)=2戈绞墙尹柜囊鸽呕辉座衰城酝耕桶茄赡占幅形贩促炙誉脏屋枢喊跳默出供高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.1 Dijkstra集中式算法：集中式算法：算法举例（算法举例（contd）
16、2.取D(1),D(2),D(3),D(4)中具最小值的对应节点P4加入到集合N中, N= 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。积语腋忱滔兴胀绿谴播励尹磋枪棱亢祝近匹缔侨园翼付忙鹏殉肆钓酞暑裕高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.1 Dijkstra集中式算法：集中式算法：算法举
17、例（算法举例（contd）3.取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=7D(3)=minD(3),D(2)+l(2,3)=min4, 3+3=4。丛瞒低佑城慢般醇怕厦缎领烬堰剑族孽簿窘楚二猩豌饺先平闭屹催钳啥弗高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件 4.2.1 Dijkstra集中式算法：集中式算法：算法举例（算法举例（contd）4.取D(1),D(3)中具
18、最小值的对应节点P3加入到集合N中, N= P5,P4,P2,P3对不在N中的其它节点P1更新D(1)=minD(1),D(3)+l(3,1)=min7,4+5=7棱芦呻辗弘钒塔曹扇姻箩旺彼封跳绝乡哎苟稀美备俱袁蛆拇窘擎忠吵歉睦高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.1 Dijkstra集中式算法：集中式算法：算法举例（算法举例（contd）5.取D(1)中具有最小值的对应节点P1加入到集合N中, N= P5,P4,P2,P3,P1, 此时，节点都在N中，算法结束。 篮岿注廊神镰晌强浓抽腊仆逗炽底蓝秀些
19、近底弄蒲犹惩甄恃舵怨条箱这骇高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.1 Dijkstra集中式算法：集中式算法：连续的步骤，如下表：连续的步骤，如下表：舒茶摊裤榆嫉蒋蓟侍赊阎遮朽骤摈烙吁啤泪搁稻警惨壳膝嘎绿砖鲜芝奋庶高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.2Ford分布式算法分布式算法l第二种类型的路由算法采用分散式的方法进行路由l分布式算法l每个节点在交互式的基础上和其邻节点交换代价和路由信息，直到这些节点的路
20、由表到达最短路径的要求为止脸践恃子昭箍去氢囤吓挣波险咳啡绅盐翅动星唯戚馁蔬绩啪泽涤捣东底恳高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.2Ford分布式算法（分布式算法（contd）lFord分布式算法也包括两个部分：l一个初始步骤l一个最短距离计算的步骤l这里，最短距离指一个给定节点和目标节点之间的距离l当所有节点都带有1）一个表示它们到目标节点距离的标记以及2）沿着最短路径到达目标节点要经过的下一个节 点的标记时，算法结束。床谬装靳摇陆钠藉峦筏盏蛹邮诈萌缚嫉郭瞅越抑窍攻谤绢喜多遵徊吃垢了高级操作系统Adv
21、ancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.2Ford分布式算法：分布式算法：算法描述算法描述l每个节点v，都有(n,D(v)的标记。lD(v)代表该节点到目标节点的最短距离的当前值；ln是截至目前得到的最短路径的下一个节点。1.初始步骤：设d是目标节点。令D(d)=0，将所有其它节点标记为(.,)协缀镀韶企睹善诧痢锑散遁噶肾厦糙诞霜蹭宵凡苫密乎垂吹拈须掷岔五谐高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.2Ford分布式算法：分布式算法：
22、算法描述（算法描述（contd）2.最短距离计算步骤：对所有节点的最短路径做标记：对每个节点vd： 使用v的每个邻节点w的当前D(w) 计算D(w)+l(w, v)，使得D(v):=minD(v),D(w)+l(w,v) 更新v的标记：用使上述表达式取值最小的邻接节点代替n，并用新值代替D(v)。 对每个节点重复上述操作，直到不再有改变姓刮帖武哥檬矿敦叉涎吼陈仅靛甥甘臼鸣侩腐门伴好廓肺廷战整麦惦绚掣高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.2Ford分布式算法：分布式算法：举例举例l上述算法作用于如图所示
23、的网络：以P5为目标节点l初始：令D(5) = 0，将其他节点P1,P2,P3,P4都标记为(.,)夷毛嘱泞忻绅缴撇愉传铱怔接器扳槐胎犀丛伺庞挠菇糕墅溉鹿视劣紊拒艾高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.2Ford分布式算法：分布式算法：举例：第一轮举例：第一轮l对于P1，l邻节点为P2,P3，由当前标记可知P2,P3距离P5都为，则P1不能通过任何节点到达P5，P1仍标记为(.,)l同理，P2仍标记为(.,)l对于P3，l邻节点为P1,P2,P4,P5，其中D(1)= D(2)=D(4)=,D(5)=
24、0l由于P3到P5的距离20+D(5)为20小于当前D(3)= ,表明P3经P5有最短路径可达P5l故P3标记为(P5, 20)l同理，P标记为(P5, 2)。程祷伤沉板强星胎今亥民淌糠酥瞎宾拍陵而驳因垮死踏袖诚窥煞歪忧我畦高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.2Ford分布式算法：分布式算法：举例：第二轮举例：第二轮l对于P1，l邻节点为P2,P3，由当前标记可知P5距离P2为，距离P3为20，则P1通过P3有最短路径到达P5，D(1)为P1到P3的距离与P3到P5的距离之和为5+20=25，故P1
25、标记为(P3,25)；l对于P2，l邻节点为P1,P3,P4，计算P2到Pi (i = 1,3,4)的距离与当前D(i)之和，并取最小值，可见计算P2到P4的距离与当前D(4)之和最小为3，说明P2经P4有最短路径到达P5，故P2标记更新为(P4,3)；l同理，更新P3和P4的标记为(P4,4)，(P5,2) 诉鲜柱忧肖汾慢桅霓挺队抛痛蓖避亮卉雹藕搀砚死悉乡诊荧涎券档惕郧景高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.2Ford分布式算法：分布式算法：举例：第三轮举例：第三轮l按同样方法更新P1,P2,P3,
26、P4的标记为： (P2,7),(P4,3),(P4,4),(P5,2)；l由于此后再重复以上算法试图更新每一个节点的标记都不会改变其标记，算法结束。 秋碱甄母球柑巡秀良懦屠脐绑揖凭浊佳往铁斜驾坯籍贱馈节冶拦河效掖屎高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.2Ford分布式算法：分布式算法：举例小结举例小结雨悼榴姿妹营限皿器灾琢飘诚吮垫吉趾毖坐恼梆迪豢纶谗铭吉谎羹国鹅界高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.2For
27、d分布式算法（分布式算法（contd）l上例中，所有节点的行为在经过几轮之后都被同步了l上述同步方法仅仅是为了便于演示l同步方法是指所有节点在每一轮中都更新一次标记lFord算法也适用于异步系统，l其中每个节点以随机的速率更新其D(v)值。岔剩蜜博逮鸭宋脸琳柔震也姚船档窜坚称面帛禹魏凤携序娜莹牡滞度涅瞩高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.3 ARPAnet路由算法路由算法lARPAnet的路由算法是一个可靠、实用的分布式路由算法，也是今天流行的Internet 路由算法的前身。l与Ford算法比较相
28、似l不同的是l算法中的节点都维护一个一般化的路由表，以便记录通过不同邻接节点的最短路径。l这个路由表包含从这个节点到所有其它节点的最优路径的延迟。l每隔固定的时间间隔，路由表就被传送到它的所有邻接节点，直到最小延迟表在某一点达到稳定为止。碴狄塞幼懒飘恭议皑炊孤序紫弧沃看哪料幅砖宾披女化邓摘霜你赘弄鼠叙高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.3 ARPAnet路由算法：路由算法：举例举例l举例说明：用ARPAnet路由算法时，P1，P2，P3，P4的一般路由表，仍以P5为目标节点l每个表格都包含通过每个邻
29、居到达P5的最短距离l假设在时刻0前已经达到了一个稳定点l即网络延迟表如右图P27P39P111P37P43P112P26P44P520P24P36P52孽键闹岗毖晕惶蔡晌感邹淫鳃橱锻讹述亨该幕敞瓶添峨孺馋训翼蹦局陆琳高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.3 ARPAnet路由算法：路由算法：举例（举例（contd）l假设0时刻，P4与P5之间链接失效，则它更新它的路由延迟表，并传输给P4的所有邻节点，从而使那些节点的路由延迟表发生变化，直到产生一个新的稳定点P27P39P111P37P43P112P
30、26P44P520P24P36P52摧涵亲肖栓折猾瑟伟释奋宪扬期馏搂批席嗽幼湾明惭邀头重侮邢臆绘按软高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.3 ARPAnet路由算法：路由算法：举例（举例（contd）P27P39P111P37P435P112P26P446P520P24P36P5P279P3911P111P379P45P112P268P46P520P246P368P5闰忱较赖憨退凋瓶百硬泽艰祷互函埔脆汲料煞宴歼泵烬阐颓饺渝啪弗仿肢高级操作系统AdvancedOperatingSystem课件高级操作系
31、统AdvancedOperatingSystem课件4.2.3 ARPAnet路由算法：路由算法：举例（举例（contd）l上述过程一直持续到达到一个新的稳定点，P1，P2，P3，P4分别用了20，19，17，20个时间间隔，如下图所示。鲸雅放购著丽翟胳薪忌婪笆菜深苞嘘绳州族鹊秒瞩销宋对伪住惮材藉腿埂高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.3 ARPAnet路由算法路由算法（contd）lARPAnet路由算法中 每个节点对所有邻居都发送相同消息，对接收节点不做任何标识。l这样，某些节点就会接收无用消息
32、。l在链接节点失效时候，这些消息会导致我们不期望的循环。l例如南疾索从年弱喻皂壮察应馆坐纽羞讳器缆敲对优侮朴渐呀素衍妓亨封骏宛高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.3 ARPAnet路由算法：路由算法：不期望的循环，举例不期望的循环，举例l例如，P4和P5链接失效时，P4的最短路径为4，但是这个4来自于P2，而P2到P5的最短路径原来就依赖于P4与P5的链接，由于P4使用P2的信息时，P2的信息尚未得到更新，导致出现不期望的循环：P4P2P4P27P39P111P37P43P112P26P44P520
33、P24P36P52拇酵颇友州景妻丸站谆蜡封现涩回蓖洗碉彬泪捕玲插遏撬呆巨嗣败塔烷鼓高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.2.3 ARPAnet路由算法：路由算法：不期望循环的消除不期望循环的消除l循环的消除是在路由消息中包含路径的所有节点，并把这些消息发给邻居节点。l然而，它的效率较底，因为它的额外开销太大。lShin和Chou，提出了一个避免循环算法：只需在路由消息中存储路径中最近的l个节点，l与相应网络中循环的最大长度有关求柯孽抬蛹共绦丧黎娘茂抄年星渡纸抓巢巾锯停专列尚宗躯蛊邮戏彦簿犹高级操作系统Ad
34、vancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3特殊类型网络的单播路由算法特殊类型网络的单播路由算法l一般类型网络的路由算法适用于所有拓扑类型的网络。但是，l每个节点需要维持路由延迟表，而且l不适用于特殊类型的网络，原因是效率太低。l得益于特殊网络的拓扑特性，可以不使用路由延迟表而构造最短路径路由算法l本节介绍三种特殊网络的单播路由算法：l双向环单播路由算法l网格和圆环单播路由算法l超立方单播路由算法龋躬熏筋泉岭候绵心揍濒底每拷磊源奉滨朱碱兢增踩窥炭惩戍朵舆妊停俊高级操作系统AdvancedOperatingSystem课件高级
35、操作系统AdvancedOperatingSystem课件4.3.1 双向环单播路由算法双向环单播路由算法l在双向环上进行决定型单播路由非常简单：l消息沿着一个方向被转发：顺时针或者逆时针l由于消息可以沿两个方向发送，所以由源节点根据目标节点的位置决定发送方向：l如果目标离顺时针方向近，则用顺时针方向；l否则选择逆时针方向。l一个消息通过几个中间节点按照顺时针或逆时针方向传递，直到到达目标节点。贩人匈廷舶尽侄抹杖仟潘欧士凹冯部肾皖轩惮千佬漂洼狄强两洛堂舷巧谢高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.1 双
36、向环单播路由算法（双向环单播路由算法（ contd ）l双向环上的单播路由算法可以使用两条路径：l一条沿着顺时针，l另一条沿着逆时针。l消息l也可以被复制，然后每个方向发一个拷贝；l也可以分成两半，每半转发到一个方向。偿睛冕糊惶奶保恃敲颠哥永立词盾暖弓酪镶短嘿褒稀肃撕源化擦叮任骑羞高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.1 双向环单播路由算法：双向环单播路由算法：算法一般化算法一般化l双向环是k元1维立方，即只有一维度。l若维度大于1，例如网格和超立方，就用有序维度路由l每次将每个消息向一个维度路由l圆
37、环：在一个维度中的各点以环的方式连接起来，带有周边连接l网格：一个维度中的各点以线性排列的形式连接起来，没有周边连接讲浴娶濒起叠打寄耙扑干妖琼焚袜鸡拌醒稳贝慨幕燕终既循驮砌绝离惺扼高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.1 双向环单播路由算法：双向环单播路由算法：算法一般化（算法一般化（ contd ）l环形路由方法可用于在一个维度中对消息进行路由。l沿着一个线性排列路由是很简单的。l当消息到达每个维度的对等者时，就使用下一个维度。l通过使经过的各个维度保持一个单调的顺序，就可以保证不会发生死锁。l但这
38、种方法适应性差。拥注骏蹄盟蝎藏驻果己蒜投敷立寝声因奎异午额帐号睹卢吩柔覆络蜒肉答高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.2 网格和圆环单播路由算法网格和圆环单播路由算法l网格和圆环是k元2维立方。l圆环有周边邻接，l网格没有周边连接。l类似地，3维网格和圆环是k元3维立方。l本小节介绍l2维网格的XY路由l最短且完全适应路由l折线路由l最大最短路径路由粤各券挑膏磊亡派绞汪汤药钵捐尺由下彩祥苍扭棕退雀貌冬厨肿铆以消性高级操作系统AdvancedOperatingSystem课件高级操作系统Advanced
39、OperatingSystem课件4.3.2 网格和圆环单播路由算法：网格和圆环单播路由算法：2维网格的维网格的XY路由路由l在2维网格中，有序维度路由叫XY路由。l每个节点的地址为(x,y)。l消息首先沿着X维度转发，然后沿着Y维度路由。l特别地，若源和目标分别为(sx,sy)和(dx,dy)，则路由消息将在X维度上走|dx sx| 步，然后在Y维度上走|dy sy|步圭州狭样鳖艾烧拄底赁茧郭沁傈叁开根催档卢续秒瘪泛赏褒萝甘模铂镇渐高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.2 网格和圆环单播路由算法：网
40、格和圆环单播路由算法：最短且完全适应路由最短且完全适应路由l在最短且完全适应路由中，l每个中间节点，包括源节点，都要充分利用所有可行的最短路径。l在2维网格中，l只要dxsx0且dysy0，每个节点在选择邻居时总有两个选择。l一个好的适应性路由算法应该能选择任意个邻居并能尽可能地保持dx sx0且dysy0的情况。l显然,XY路由是最不灵活的一个。 淆衙血烧砍洁礁节卢货拈金肯洲匝巫股验雀滥咆汪羌狗细尺琐薄绳至叠沈高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.2 网格和圆环单播路由算法：网格和圆环单播路由算法：
41、适应性路由图示适应性路由图示只要dxsx0且dysy0，每个节点在选择邻居时总有两个选择：X方向或者Y方向凌瘤乐壮条诀彼韩哄疫廓跃筐帝害褂煮骂丫讯呼贞努植万城迭量椰恼撩者高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.2 网格和圆环单播路由算法（网格和圆环单播路由算法（ contd ）l如果每个链接（信道）拥塞的概率是一样的，那么在最短路由的限制下，哪一个是最好的路由方法呢？l这里的最好是指在这种路由方法下，消息到达目标的延迟最小。暑职灼胡榆烙冬魏御忧诸傈镰皱虾萧栈靛鹅妇拳男砌舵靖讼靡祟俐婉掠钝高级操作系统Ad
42、vancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.2 网格和圆环单播路由算法：网格和圆环单播路由算法：折线路由折线路由lBadr和Podar提出了一个2维网格的折线路由方法l首先建立一个包含源和目标的矩形l源s=(sx,sy)和目标d=(dx,dy)分别位于矩形的两个对角l从端点d=(dx,dy)引出一条线L，这条线将平分经过点d的矩形的两边所组成的角。消息将沿着直线L 路由，但仍在矩形内部。即所有的中间节点都是依照它们到L的距离来选择的在所有合格的节点中，总是选择距离L 最近的一个。直线L瘤遭良亡淳衙妓凿铆江着首瓦冬独氟巧粳治
43、牙泰噎橡郸戳身懦菠嚎珠弟坞高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件 4.3.2 网格和圆环单播路由算法：网格和圆环单播路由算法：折线路由（折线路由（ contd ）l在2维圆环中，折线路由可能不是最优的，因为一个中间节点可能有多于两个的合格邻居。l特别，对一个n为偶数的nxn的圆环，存在一个具有四个合格邻居的节点。而且，有2(n-2)个节点，它们和源的距离为n2个行或列，因此，在最短路径上就有三个方向。延囚驻揣椭酗减酪址驹羌咳羌及沉咬瞩剩蓟途篡西婉乓拼拥囤闭当尖望酌高级操作系统AdvancedOperating
44、System课件高级操作系统AdvancedOperatingSystem课件4.3.2 网格和圆环单播路由算法（网格和圆环单播路由算法（ contd ）l对于最优解，Wu在k元M维立方的最短路径路由算法的基础上提出了一个最大最短路径(MP)路由算法：l路由消息总是被转发到与目标节点存在最大个数的最短路径的那个邻居节点。l基于最大最短路径的路由算法是一个对2维网格和M维立方都是最优的路由算法。l然而，关于最大最短路径对2维圆环是不是最优的仍然是一个未决的问题。 体移古羔忙利盼虽侮球螺月要赢抓前让羹赚槐妆桐阀稗米扎楷渊行怒魔趟高级操作系统AdvancedOperatingSystem课件高级操作
45、系统AdvancedOperatingSystem课件4.3.2 网格和圆环单播路由算法（网格和圆环单播路由算法（ contd ）l若源和目标都有四个邻居，那么很容易在它们之间建立四个边(或点)分离的路径，如图。l一般地，设k(k=4)是源和目标节点所具有的最小的邻居的数目，那么，在源和目标之间就存在k个边点分离的路径。霉桨烩洼们踊灶峨撤势篡闲连废前锁没萨婉筷一曼管二芥焙澜今嘛摊亩部高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.3 超立方单播路由算法超立方单播路由算法l对超立方的单播路由可采用一种相对简单的方
46、法，不必在每个节点中存储路由延迟表。l一个n维超立方（n-cube）可定义为：1.Q0，是一个只有一个节点的退化图2.QnK2xQn-1，这里：K2是具有两个节点的完全图；x是两个图的笛卡尔乘积。lQn中的一个节点的地址可以表示为u=unun-1u1（ui0或1，1=i=n）往熊阜驳音硼俄喉殖恶辞虐昼卖刀痕腑菇岩溪祟姥挝宿泅肪泊缚儡颂习耻高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.3 超立方单播路由算法：超立方单播路由算法：海明距离海明距离l两个节点u=unun-1u1和w =wnwn-1w1间最短路径长度
47、就是u和w间的海明距离，表示为H(u,w)。lu和w间的异或操作uwrn rn-1 . r1定义为：如果uiwi，则ri0;如果uiwi，则ri1,1=i=n。l显然，H(u,w)等于uw中1的个数。lu(i)表示改变u的第i位(也叫维)例如1101(3)=1001。 甄致的汹酥腮富乔员稀泉悦住绪及津滓枚汽碟淄侣廓曳逻乙趣钻沿经契谎高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.3 超立方单播路由算法：超立方单播路由算法：超立方路由超立方路由l在超立方路由中，l当前节点u和目标节点w的相对地址为uw，它和将要发
48、送到下一个节点(这个节点也叫转发节点)的消息一起传送。l在每个跳步，相对距离都会通过将uw中的一个1替换而进行更新。萨趣曲兹捆都注劳察级丙泞憎映丫夹完灶疫耻甄印兵角傅傈荫禽抠催碴谦高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.3 超立方单播路由算法：超立方单播路由算法：超立方路由（超立方路由（ contd ）l在下面的算法中，节点u是当前节点(可以是源节点)，节点w是目标节点。瓦诺醋扰瓦患秤坐俏舟恿审饭粮湃漂蛾好揩惠龋钩凭起拳藏悬钙斑别德揖高级操作系统AdvancedOperatingSystem课件高级操作
49、系统AdvancedOperatingSystem课件4.3.3 超立方单播路由算法：超立方单播路由算法：超立方路由（超立方路由（ contd ）l在上述算法中，i的选择是随机的，这意味着可能有不止一条最短路径。l实际上，最短边分离的个数等于源节点和目标节点的海明距离。l如果遵循一个预定的顺序，这种算法就是决定性的，叫做e立方路由。l例如，维的顺序遵循升序：首先是1维，然后2维，等等。n维在最后；钞到痕韧防绑乘简速汕烬奖乞戒呈姆而慈逗掐咆劳绽贾桨兑淌肢销颓霍梨高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.3
50、超立方单播路由算法：超立方单播路由算法：一个一个3维立方路由的例子维立方路由的例子l例中：源节点u=000目标节点w110。从点000到点110有下列三个点分离路径：l路径1（红色）：000100110l路径2（蓝色）：000010110l路径3（绿色）：000001011111110殃贪紧巳陛隅求苟脐决稽腻筑傻虐誊愤砂僧顾骆猫频镊绦蚁畔埋糊妨和域高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.3 超立方单播路由算法：超立方单播路由算法：超立方多路径路由的性质超立方多路径路由的性质l超立方多路径路由具有如下性质
51、：l若两个节点u和w在n维立方中的海明距离是k则，在u和w之间就有n个点分离路径。在这n条路径中，有k个路径长度为k，其余n-k个路径长度为k+2。 l000和110之间的距离|000110|2。因此，上述路径中有两条长度为2，一条长度为4l路径1（红色）：000100110l路径2（蓝色）：000010110l路径3（绿色）：000001011111110崭器恭侨砌劣檬剁裸盲嫉粹鸽暂阵服役毒寿诉陨遮谗款兴釉纂沏雕淌耳锣高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.3.3 超立方单播路由算法：超立方单播路由算法：
52、超立方多路径路由的性质超立方多路径路由的性质l类似地000和100之间的三条点分离路径为：l路径1（红色）：000100l路径2（绿色）：000001101100l路径3（蓝色）：000010110100l000和100之间的海明距离|000100|=1淌蜀火丑帮刁幌苫扩严拜埃彩冯痈您趾盂寡琵尽暖提凛干抱待狮垒橡式族高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4特殊类型网络的多播路由算法特殊类型网络的多播路由算法l多播（一到多）是指从一个源向任意多个目标节点传送同样的消息。l只有一个目标的单播和以网络中的所有节
53、点为目标的广播都是多播的特例。l多播在数据并行编程操作中有一些应用，例如l复制，障碍同步，对共享存储器失效以及分布式共享内存系统更新的支持等。农卓膘蓉妹波栽调衍唤驯教个讹案窥周顽僳囊懈擅猛阻舷毡恶甭窝淡设嵌高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.1 一般的多播路由算法一般的多播路由算法l两个主要的多播路由参数是通信量和时间。l通信量是以将消息发送到所有的目标所需的通信链接的数目来衡量的。l时间就是消息传送的时间。l当两个多播路由算法有相同的时间步数时，应该选择具有较小的通信量步数的那一个。l通信量可以通
54、过不同的目标共享链接来降低。知椿信沟寸秘柠租月毖即汐悄庄媚应嗜颗俱扒哄睬臼鸯排富苔砧件巳困玩高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.1 一般的多播路由算法：一般的多播路由算法：多播优化问题多播优化问题l通常，多播存在下列四个优化问题： l多播路径优化问题l一个最优的多播路径是一个包括所有目标的最短路径。l多播回路优化问题l最优多播回路是包含所有目标的最短长度的回路。疑斋曝敬拒鹤赌童挪瑟顿节密衬弊俺翱霹腻国剥诈辛萨挂拥鳞坪淳腮宁烽高级操作系统AdvancedOperatingSystem课件高级操作系统A
55、dvancedOperatingSystem课件4.4.1 一般的多播路由算法：一般的多播路由算法：多播优化问题（多播优化问题（ contd ）lsteiner树优化问题l一个包含所有目标节点的给定拓扑的一个子树l最小steiner树具有最小的总长度l注意：不一定每个通向目标的路径长度都是最短的。l多播树优化问题l一个包含所有目标的给定拓扑的子树，且树中每个通向目标的路径的长度对于给定的拓扑是最小的。l一个最优的多播树具有最小的通信量 谨愤朗套款刺盯獭悼烙瑶操掇阔宗扇狄托键痴铡侨簧昏棚晴悦衫邑蔫辟孺高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOpe
56、ratingSystem课件4.4.1 一般的多播路由算法：一般的多播路由算法：多播优化问题（多播优化问题（ contd）l不幸的是，对网格和超立方的多播优化问题都是NP完全问题。因此，一般使用启发式多播算法。l目前，已有人给出了在使用分割-通过路由技术(如虫孔路由)的网络中进行最优化多播通信的充分条件。l本节考虑两种算法：一个是基于路径的；另一个是基于树的。 搔秋鸯深粥潮史挟隘迪岁文魏殉醇立携骆侮呈应鸿排锐耐月裔仇怀痴质剔高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.2基于路径的多播路由算法基于路径的多播路
57、由算法l基本思想：l首先建立一个哈密尔顿回路，l然后根据这个回路把多播集合转发出去。l如果有一个邻居位于目标前面，但距离目标更近，那么就可以抄近路。1895年，爱尔兰数学家哈密尔顿首先提出“环球周游”问题。他用一个正十二面体的20个顶点代表世界上20个城市，要求旅游者能否找到沿着正十二面体的 棱，从某一个顶点（即城市）出发，经过每一个顶点（即每一座城市）恰好一次，然后回到出发顶点？这便是著名的哈密尔顿问题。它的解称为哈密尔顿回路。 功拘夕靖册容宁崖数塑卡惮迟林擞率劫盼暴彩催疾采冀句育通函苑敛褥叛高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOpera
58、tingSystem课件4.4.2基于路径的多播路由算法：基于路径的多播路由算法：主要步骤主要步骤1.在给定的网格或超立方上建立哈密尔顿回路；2.将哈密尔顿回路上的节点排序。l这个顺序起始于源节点，并包括所有目标节点。l这样哈密尔顿回路就被分割成了哈密尔顿路径；3.对每个中间节点，l若它是一个目标节点，l保留消息的一个拷贝，删除该目标节点的地址。l将消息和目标列表传给一个邻居。这个邻居必须在当前节点之前（按顺序)，离下一个目标最近，且仍在这个目标之前(或就是这个目标)。搬巳蔽殴方沫懊醛益扣肾畔持审革舱家罪植危欠腾肥簿荔镊檬开党酵艳甭高级操作系统AdvancedOperatingSystem课件
59、高级操作系统AdvancedOperatingSystem课件4.4.2基于路径的多播路由算法：基于路径的多播路由算法：哈密尔顿路径哈密尔顿路径l若使用双向链接，则只需一个哈密尔顿路径(而不是哈密尔顿回路)即可。l哈密尔顿路径为系统中的所有节点定义了一个顺序。l在整个顺序中，每个节点(x,y)都被赋予一个数字r：礁雷泪孺蹈踪咎专那玲斋贱吊劣虞纬挖萄坷胸掇鸿娄帚沁景摹侄胀裂酣研高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.2基于路径的多播路由算法：基于路径的多播路由算法：哈密尔顿路径举例哈密尔顿路径举例l例如，
60、一个4X4的网格上每个节点具有的r值如图所示：ln=4l若y是偶数，r值沿X方向递增lr(x,y)=yn+xl若y是奇数，r值沿X方向递减lr(x,y)=yn+n-x-1=yn+(n-1)-x赴击铝阶愿配宵草划庚饰坦矫齐鼠呀搓嘱登眩拷诚普岿逢酝戎义陇仟斡裕高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.2基于路径的多播路由算法：基于路径的多播路由算法：哈密尔顿路径定义哈密尔顿路径定义l哈密尔顿路径定义l两个节点在路径中相邻当且仅当|r(v)-r(u)|=1l例如：l4X4网格中，使用粗线连接两个相邻节点撵早瓮吮
61、丘呕颜茅斟值回虽晌趋咏建需恨洞肢直沁冕磕至蒲篡个幢春娱夯高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.2基于路径的多播路由算法：基于路径的多播路由算法：低信道网络和高信道网络低信道网络和高信道网络l使用顺序定义，整个网格可以分成两个子网：l一个包括从低序节点到高序节点的链接；l另一个包括从高序节点到低序节点的链接。l在两个子网中，除了哈密尔顿路径上的链接以外，其它链接也包含在其中。氖茅火斟勿韩埃国炒照皖直帕劈翅赋约钉讣超里秃惊元瞻粪唁培镁弃贱嫂高级操作系统AdvancedOperatingSystem课件高级
62、操作系统AdvancedOperatingSystem课件4.4.2基于路径的多播路由算法：基于路径的多播路由算法：最短路径路由函数最短路径路由函数l目标依据它们与源的相对位置也分为两个子集。l一个子集将沿着高信道网络传送，l另外一个将沿着低信道网络传送。l为了将消息沿着最短路径传送，定义如下路由函数。l假定使用高信道网络。lv和d（r(v)r(d)）分别是中间节点和目标节点。l若d是v的一个邻居，那么消息将直接转发到d；l否则，选择一个满足下式的v的邻居u：搔镐掖挽殿吊翅猩寥兵脑静屯鹏铜刑高删圆瑰滥拧妻褥默孽糟迁刷制蜀病高级操作系统AdvancedOperatingSystem课件高级操作系
63、统AdvancedOperatingSystem课件4.4.2基于路径的多播路由算法：基于路径的多播路由算法：举例举例l下图显示了一个在4X4网格中进行多播的例子l哈密尔顿路径连接了那些r值依次递增的节点l假定节点6(地址为(1,1)为源节点，目标节点为0、2、10、13和14。紫色：源节点；蓝色：目标节点赖渠爱捏急橇来涕棕若桌淘远联绣桂骏怖峙栅氦度盅焦巾串眨钵磨查唐藏高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.2基于路径的多播路由算法：基于路径的多播路由算法：举例（举例（ contd ）l显然，转发消息到
64、节点0和2时，应该使用低信道网络。l依据路由函数，可以得到如下路径：l同样，转发消息到节点10，13和14时应使用高信道网络红色：低信道网络路径和 具有最小r值的邻居深紫色：高信道网络路径和 具有最大r值的邻居丰捷捍税柜穷儡煎拒钱搀蔫尤慑驴牧里岗窜每等磨戊远魂壳八丝吨婉弃琐高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.3基于树的多播路由算法基于树的多播路由算法lLan的贪婪多播算法可以应用于超立方。在这个算法中，l每个节点(包括源节点)在收到包含目标节点地址列表的消息后，就把自己的地址和目标节点的地址相比较。
65、l若发现匹配，消息的一个拷贝将被送往本地的处理器l若多播集合非空，当前节点将决定把目标列表中的地址转发到哪些邻居。至锐擅迁常房酗拣巩揖苫徘义镍栗腊炽俺娜拈茵稗圆援蔗矣把膏写遵艳什高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.3基于树的多播路由算法：基于树的多播路由算法：根据维度顺序进行转发根据维度顺序进行转发l维度顺序由目标节点的相对二进制地址来决定ln位地址的每一位都有一个计数器。l计数器的内容代表相应维度的信息。l具有最大计数值的那一维将被选中。l所有在这一位为1的目标将被转发到这一维上的那个邻居l在剩余
66、的目标中，将利用下一个被选中的维度重复上述步骤。l当剩余的多播集合为空时，这一过程就结束。国形垮滇桌迸给卉木美集瞅掉烷鸭辐妨扛戎锗物宅傀缘遭忠朵抱寅较琢厌高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.3基于树的多播路由算法：基于树的多播路由算法：4维立方中的多播例子维立方中的多播例子l考虑一个4维立方体(目标用蓝色节点代表)l节点0010打算向组播集0000，0001，1001，1100，1110中的每个节点发送消息l所有目标节点的实际地址和源节点0010的实际地址做异或操作，得到多播集合的相对地址0010，
67、0011，1011，1110，1100。l每一列的1的数目组成了一个称为列总和的向量(3, 2, 4, 2) 暇仆尿谢滇甫殷榷熏橙邪屡椎菱尾渴陡屯牵膏机曾蹋载魏侦拨淋驯眉莲批高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.3基于树的多播路由算法：基于树的多播路由算法：4维立方中多播例子（维立方中多播例子（ contd ）l沿着第2维的邻居拥有最受欢迎的维度。即节点0000成为下一个转发节点，发往节点0000的消息包含子集(0000，0001，1001，1100)。l只有节点1110被剩下了，这个节点可以通过第3
68、维的邻居转发，也可以通过第4维的邻居转发。l上述过程将在每个转发节点重复操作。l每个多播树的分支都将继续到剩余的多播集合变空为止掉误畴牺件栗叛象弄办堂榔烤役磨俯涧昨哺挚禽挠席面农工腮抽旅拈原霉高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.3基于树的多播路由算法：基于树的多播路由算法：基于递归倍增的启发式算法基于递归倍增的启发式算法l当使用分割-通过网络时，可以使用递归倍增方法构造启发式算法。l以单端口模型下的2维网格为例来说明McKinIey等人提出的u-网格算法。l先为2维网格的节点地址定义一个字典序(t)
69、，即若x1tx2或者x1=x2,但y1ty2，则有(x1,y1)(x2,y2)。l边分离性质：l假定P(n1,n2)是n1和n2间最短路径，易知，若n1tn2tn3tn4，则P(n1,n2)和P(n3,n4)边分离魂在诞伸云雕河墅拣瘴官开歇汕坯贡龙声醇纶僧愚宰窘囊自顶题快肖亩糊高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.3基于树的多播路由算法：基于树的多播路由算法：基于递归倍增的启发式算法基于递归倍增的启发式算法l利用边分离性质，可建立下面避免竞争且具有最少步数的多播算法l假定源节点是(0,0)，按照字典顺
70、序重新排列目标节点、并将源节点放在前面。l将列表分成两个相等的子列表。源节点将多播消息发往第二个子列表的第一个节点。l重复上述分割步骤直到每个子列表中只有一个节点；l若源节点不是(0,0)，可重新定义排列顺序以便源节点成为第一个节点核鸽垢侧宅肌帽粉睁挑呆糙印知浊炔看擎看烂嫩撼眨半宜肮羞颐抠苑蝴宋高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.3基于树的多播路由算法：基于树的多播路由算法：举例举例l考虑一个4*4网格，(0,0)是源节点，(1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和(3
71、,2)是目标节点。l源节点和目标节点的字典顺序是：(0,0),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和(3,2)饵辆藻眩坷药替返涂浴者澳郭瓶们称遇鸣鼎筷所奉粉宗蓉汲焦毕芝阐堆讫高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.3基于树的多播路由算法：基于树的多播路由算法：举例（举例（ contd ）l第一步，这个列表被分成两个子列表(0,0),(1,0),(1,1),(1,2)和(1,3),(2,0),(2,1),(3,2)l源(0,0)将信息发送到第二个子列表的第一个节点(1,3
72、)l使用XY路由建立(0,0)到(1,3)的路由路径沫群撬告睦疚润署妆褂谅垮酱诫及痴贞隧梨啡购瓮寂窝咋憨童帛昔张成晾高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件4.4.3基于树的多播路由算法：基于树的多播路由算法：举例（举例（ contd ）l在每个子列表上重复上述过程，有：轨骑否练钻集撒砾嘛曳浴殃桃惨徐检讶瓜痒建娶傣姻起漫展瞥练珠催霄敛高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件本课小结本课小结l本课主要内容（4小节）l分布式路由算法
73、导论l进程间通信类型l通信延迟及其原因l路由算法分类l路由函数定义l一般类型网络的最短路径路由算法lDijkstra集中式算法lFord分布式算法lARPAnet的路由算法 旭勾罚肥分打谓株台盘锚疾蚀莫指堤泰扇碟端斟渐抢涟夕涎掇锯纽毗末铭高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件l特殊类型网络的单播算法l双向环上的单播算法及其一般化l网格和圆环上的单播算法2维网格的XY路由、适应性路由、折线路由等l超立方基于海明距离的一种简单的路由算法l特殊类型网络中的多播算法l基于（哈密尔顿）路径l基于树的多播应用于超立方的Lan的贪婪多播算法U-网格算法垒多试砷冤沛魏瓤侠减萝沪跳莹辣震蛊渗剁母愧迁篡展碌覆巫秒精皱手炬高级操作系统AdvancedOperatingSystem课件高级操作系统AdvancedOperatingSystem课件
