高级操作系统AdvancedOperatingSystem课件.ppt

1、Click to add Text高级操作系统高级操作系统Advanced Operating System熊焰0551_3607394中国科学技术大学计算机系8/7/2022Advanced Operating System2/97第三章第三章 分布式路由算法分布式路由算法主要内容主要内容分布式路由算法导论一般类型网络的最短路径路由算法 特殊类型网络的单播算法特殊类型网络中的多播算法虚信道和虚网络 完全自适应和无死锁路由算法8/7/2022Advanced Operating System3/97第三章第三章 分布式路由算法分布式路由算法主要内容（主要内容（contd）几个自适应和无死锁路由

2、算法 容错单播的一般方法 网格和圆环中的容错单播算法超立方中的容错单播算法容错组播算法8/7/2022Advanced Operating System4/97第三章第三章 分布式路由算法分布式路由算法主要内容主要内容分布式路由算法导论分布式路由算法导论一般类型网络的最短路径路由算法 特殊类型网络的单播算法特殊类型网络中的多播算法8/7/2022Advanced Operating System5/97一、进程间通信类型二、通信延迟及其原因三、路由算法类型四、路由函数8/7/2022Advanced Operating System6/973.1分布式路由算法导论一、进程间通信类型一、进程间通

3、信类型有效的进程间通信对分布式系统的性能很重要根据目标个数的不同，本章讨论的进程间通信的类型有：一对一（单播）一对多（组播）一对所有（广播）8/7/2022Advanced Operating System7/973.1分布式路由算法导论：二、通信延迟及其原因二、通信延迟及其原因在基于消息传递的分布式系统中，消息一般在到达目标节点之前可能要通过一个或多个中间节点，故存在通信延迟。分布式系统中的通信延迟依赖于如下四个因素：网络拓扑、路由、流量控制、交换8/7/2022Advanced Operating System8/973.1分布式路由算法导论：二、通信延迟及其原因（二、通信延迟及其原因（c

4、ontd）1、网络拓扑，也叫互连网络通常用图表示，定义处理单元（PE）之间是如何连接的分类特殊类型的网络使用k元n维立方表示8/7/2022Advanced Operating System9/973.1分布式路由算法导论：二、通信延迟及其原因（二、通信延迟及其原因（contd）2、路由决定如何选择路径以便将消息传递到目的地。本章主要考虑路由8/7/2022Advanced Operating System10/973.1分布式路由算法导论：二、通信延迟及其原因（二、通信延迟及其原因（contd）3、流量控制流量控制决定在消息沿路径传递时如何分配网络资源网络资源包括：信道缓冲区8/7/2022

5、Advanced Operating System11/973.1分布式路由算法导论：二、通信延迟及其原因（二、通信延迟及其原因（contd）4、交换技术这是一个实际的机制，它决定消息如何从一个输入信道转到一个输出信道。8/7/2022Advanced Operating System12/973.1分布式路由算法导论：三、三、路由算法类型路由算法类型路由算法类型包括：1.特殊 vs.一般2.最短 vs.非最短3.确定型 vs.适应型4.源路由 vs.目标路由5.容错型 vs.非容错型6.冗余型 vs.非冗余型7.死锁避免型 vs.非死锁避免型8/7/2022Advanced Operatin

6、g System13/973.1分布式路由算法导论：1、一般型路由和特殊型路由、一般型路由和特殊型路由 一般型路由算法适合于所有类型的网络但是对于某种特定网络不是很有效特殊型路由算法只对特定的网络类型有效，如超立方、网格等这些算法由于利用了特定网络的拓扑属性，所以效率往往较高。8/7/2022Advanced Operating System14/973.1分布式路由算法导论：2、最短路由算法和非最短路由算法最短路由算法和非最短路由算法最短路径算法对给定的源-目标对，给出一个代价最小的路径路径的代价所有跳步（连接）代价的线性和。缺点：可能会导致网络某一部分的拥塞非最短路由算法可以将消息路由到一

7、个更长的路径从而避免拥塞。在某些情况下，随机路由可能是有效的。8/7/2022Advanced Operating System15/973.1分布式路由算法导论：3、确定型路由和适应型路由确定型路由和适应型路由确定型路径算法（静态）路由路径只在网络的拓扑发生改变时才发生变化而且不使用任何有关网络状态的消息。适应型路由算法（动态）路径根据网络流量而改变。8/7/2022Advanced Operating System16/973.1分布式路由算法导论：5、容错型路由和非容错型路由容错型路由和非容错型路由容错型路由算法即使出现错误，被路由消息也能保证送到。非容错型路由算法假定路由不会出错路由算

8、法不必动态调整自己的活动。8/7/2022Advanced Operating System17/973.1分布式路由算法导论：6、冗余型路由和非冗余路由冗余型路由和非冗余路由冗余型路由算法用几个边分离（或节点分离）的路径向同一个目标发送多个拷贝。只要这些路径中的一个是好的，则至少有一个消息拷贝能到达目标。必须保证有且只有一个拷贝被接收非冗余型路由算法对每个目标只需转发消息的一个拷贝。8/7/2022Advanced Operating System18/973.1分布式路由算法导论：7、死锁避免型路由和非死锁避免型路由、死锁避免型路由和非死锁避免型路由死锁避免型路由算法通过仔细设计的路由算法

9、，保证不发生死锁。非死锁避免型路由算法没有特别的设施来预防或避免死锁。可能发生死锁，也可能不发生死锁。8/7/2022Advanced Operating System19/973.1分布式路由算法导论：四、路由函数四、路由函数路由函数定义一个消息如何从源节点路由到目标节点每个PE在收到一个消息以后，都将决定：1）把这条消息传送到本地存储器，还是2）转发到一个邻接的PE有许多不同的路由函数的定义，例如依赖于目标的、依赖于输入的、依赖于源的、依赖于路径的等等一般而言，路由函数参考的信息越多，效果可能就越好本章仅使用依赖于目标的路由函数仅仅依赖于当前和目标节点依赖于当前、目标节点，以及输入的邻接节

10、点依赖于源、当前、目标节点依赖于目标节点和从源节点到当前节点的路径8/7/2022Advanced Operating System20/97第三章第三章 分布式路由算法分布式路由算法主要内容主要内容分布式路由算法导论一般类型网络的最短路径路由算法一般类型网络的最短路径路由算法 特殊类型网络的单播算法特殊类型网络中的多播算法8/7/2022Advanced Operating System21/973.2 一般类型网络的最短路径路由算法一般类型网络的最短路径路由算法许多分组交换网，如法国的Transpac或美国的ARPAnet都使用最短路径路由这里介绍三个一般类型网络的最短路径路由算法：1.D

11、ijkstra集中式算法2.Ford分布式算法3.ARPAnet路由算法8/7/2022Advanced Operating System22/973.2 一般类型网络的最短路径路由算法：一般类型网络的最短路径路由算法：预备、分布式系统图示预备、分布式系统图示一般地，一个分布式系统可以用图来表示：节点代表PE（处理单元）；边代表通信链接；每个链接的数字代表链接代价。例：8/7/2022Advanced Operating System23/97三个一般类型网络的最短路径路由算法：1.Dijkstra集中式算法集中式算法2.Ford分布式算法3.ARPAnet路由算法8/7/2022Advanc

12、ed Operating System24/973.2.1 Dijkstra集中式算法集中式算法第一种类型的算法以集中式的风格进行路由Dijkstra集中式算法可以发现一个源节点到所有其他节点的最短路径。算法需求：需要了解给定网络的全局拓扑消息，即：1、网络中所有其它节点的列表；2、节点之间的所有链接；3、每个链接的代价。8/7/2022Advanced Operating System25/97设D(v)是从源s到节点v的距离（沿给定路径的链接的代价的和）l(v,w)是节点v和w之间的代价Dijkstra算法如下：1.设N=s；对不在N中的每一个节点v，令D(v)=l(s,v)。对那些没有连

13、接到s的节点赋值为。2.找到不在N中的一个节点w，使D(w)最小并将w加入N；然后对所有不在N中的其它节点计算并更新D(v)：D(v):=minD(v),D(w)+l(w,v)重复步骤2，直到所有节点都在N中N3.2.1 Dijkstra集中式算法：集中式算法：一、算法描述一、算法描述svwD(v)D(w)N?即与s相邻的节点8/7/2022Advanced Operating System26/973.2.1 Dijkstra集中式算法：集中式算法：二、算法举例二、算法举例上述算法作用于如图所示的网络：以P5为源节点1、集合N只包含源节点P5即N=P5。对不在N中的节点P1,P2,P3,P4

14、计算：D(1)=D(2)=；（由于P1和P2不与P5直接相连）D(3)=l(P5,P3)=20D(4)=l(P5,P4)=2=2=20=8/7/2022Advanced Operating System27/973.2.1 Dijkstra集中式算法：集中式算法：二、算法举例（二、算法举例（contd）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(

15、3),D(4)+l(4,3)=min20,2+2=4。=2=20=4=3 8/7/2022Advanced Operating System28/973.2.1 Dijkstra集中式算法：集中式算法：二、算法举例（二、算法举例（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。=2=4=3=78/7/2022Advanced Operating System29/

16、97 3.2.1 Dijkstra集中式算法：集中式算法：二、算法举例（二、算法举例（contd）4、取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=2=4=3=78/7/2022Advanced Operating System30/973.2.1 Dijkstra集中式算法：集中式算法：二、算法举例（二、算法举例（contd）5、取D(1)中具有最小值的对应节点P1加入到集合N中,N=P5,P4,P2,P3,P1,此时，节点都在N中，算法结束。8/7/2

17、022Advanced Operating System31/973.2.1 Dijkstra集中式算法：集中式算法：连续的步骤，如下表：连续的步骤，如下表：8/7/2022Advanced Operating System32/973.2.2Ford分布式算法分布式算法第二种类型的路由算法采用分散式的方法进行路由分布式算法每个节点和其邻节点交换代价和路由信息，直到这些节点的路由表到达最短路径的要求为止8/7/2022Advanced Operating System33/973.2.2Ford分布式算法（分布式算法（contd）Ford分布式算法也包括两个部分：一个初始步骤一个最短距离计算的

18、步骤这里，最短距离指一个给定节点和目标节点之间的距离当所有节点都带有1）一个表示它们到目标节点距离的标记以及2）沿着最短路径到达目标节点要经过的下一个节 点的标记时，算法结束。8/7/2022Advanced Operating System34/973.2.2Ford分布式算法：分布式算法：一、算法描述一、算法描述每个节点v，都有(n,D(v)的标记。D(v)代表该节点到目标节点的最短距离的当前值；n是截至目前得到的最短路径上的下一个节点。1.初始步骤：设d是目标节点。令D(d)=0，将所有其它节点标记为(.,)8/7/2022Advanced Operating System35/973.

19、2.2Ford分布式算法：分布式算法：一、算法描述（一、算法描述（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)。对每个节点重复上述操作，直到不再有改变8/7/2022Advanced Operating System36/973.2.2Ford分布式算法：分布式算法：二、举例二、举例上述算法作用于如图所示的网络：以P5为目标节点初始：令D(5)=0，将其他节点P1,P2

20、,P3,P4都标记为(.,)8/7/2022Advanced Operating System37/973.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)。8/7/2022Advanced Ope

21、rating System38/973.2.2Ford分布式算法：分布式算法：二、举例：第二轮二、举例：第二轮对于P1，邻节点为P2,P3，由当前标记可知P5距离P2为，距离P3为20，则P1通过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)8/7/2

22、022Advanced Operating System39/973.2.2Ford分布式算法：分布式算法：二、举例：第三轮二、举例：第三轮按同样方法更新P1,P2,P3,P4的标记为：(P2,7),(P4,3),(P4,4),(P5,2)；由于此后再重复以上算法试图更新每一个节点的标记都不会改变其标记，算法结束。8/7/2022Advanced Operating System40/973.2.2Ford分布式算法：分布式算法：举例小结举例小结(.,)(.,)(.,)(.,)(.,0)(P5,20)(P5,2)(P3,25)(P4,3)(P4,4)(P2,7)8/7/2022Advanced

23、 Operating System41/973.2.2Ford分布式算法（分布式算法（contd）上例中，所有节点的行为在经过3轮之后都被同步了上述同步方法仅仅是为了便于演示同步方法是指所有节点在每一轮中都更新一次标记Ford算法也适用于异步系统，其中每个节点以随机的速率更新其D(v)值。8/7/2022Advanced Operating System42/973.2.3 ARPAnet路由算法路由算法ARPAnet的路由算法是一个可靠、实用的分布式路由算法，也是今天流行的Internet 路由算法的前身。与Ford算法比较相似不同的是算法中的节点都维护一个一般化的路由表，以便记录通过不同邻

24、接节点的最短路径。这个路由表包含从这个节点到所有其它节点的最优路径的延迟。每隔固定的时间间隔，路由表就被传送到它的所有邻接节点，直到最小延迟表在某一点达到稳定为止。8/7/2022Advanced Operating System43/973.2.3 ARPAnet路由算法：路由算法：举例举例举例说明：用ARPAnet路由算法时，P1，P2，P3，P4的一般路由表，仍以P5为目标节点每个表格都包含通过每个邻居到达P5的最短距离假设在时刻0前已经达到了一个稳定点即网络延迟表如右图P27P39P111P37P43P112P26P44P520P24P36P52想一想，从每个节点的路由表上，可以看出最

25、短路由的问题么？8/7/2022Advanced Operating System44/973.2.3 ARPAnet路由算法：路由算法：举例（举例（contd）假设0时刻，P4与P5之间链接失效，则P4更新其路由延迟表，并传输给其所有邻节点，从而使那些节点的路由延迟表发生变化，直到产生一个新的稳定点想一想，新的稳定点可能是怎样的？P27P39P111P37P43P112P26P44P520P24P36P528/7/2022Advanced Operating System45/973.2.3 ARPAnet路由算法：路由算法：举例（举例（contd）P27P39P111P37P435P112

26、P26P446P520P24P36P5P279P3911P111P379P45P112P268P46P520P246P368P58/7/2022Advanced Operating System46/973.2.3 ARPAnet路由算法：路由算法：举例（举例（contd）上述过程一直持续到达到一个新的稳定点，P1，P2，P3，P4分别用了20，19，17，20个时间间隔，如下图所示。8/7/2022Advanced Operating System47/973.2.3 ARPAnet路由算法（路由算法（contd）ARPAnet路由算法中 每个节点对所有邻居都发送相同消息，对接收节点不做任何

27、标识。这样，某些节点就会接收无用消息。在链接节点失效时候，这些消息会导致我们不期望的循环。例如8/7/2022Advanced Operating System48/973.2.3 ARPAnet路由算法：路由算法：不期望的循环，举例不期望的循环，举例例如，P4和P5链接失效时，P4的最短路径为4，但是这个4来自于P2，而P2到P5的最短路径原来就依赖于P4与P5的链接，由于P4使用P2的信息时，P2的信息尚未得到更新，导致出现不期望的循环：P4P2P4P27P39P111P37P43P112P26P44P520P24P36P528/7/2022Advanced Operating Syste

28、m49/973.2.3 ARPAnet路由算法：路由算法：不期望循环的消除不期望循环的消除循环的消除是在路由消息中包含路径的所有节点，并把这些消息发给邻居节点。然而，它的效率较底，因为它的额外开销太大。Shin和Chou，提出了一个避免循环算法：只需在路由消息中存储路径中最近的k个节点，k与相应网络中循环的最大长度有关8/7/2022Advanced Operating System50/97第三章第三章 分布式路由算法分布式路由算法主要内容主要内容分布式路由算法导论一般类型网络的最短路径路由算法 特殊类型网络的单播算法特殊类型网络的单播算法特殊类型网络中的多播算法8/7/2022Advanc

29、ed Operating System51/973.3特殊类型网络的单播路由算法特殊类型网络的单播路由算法一般类型网络的路由算法适用于所有拓扑类型的网络。但，每个节点需要维持路由延迟表，而且效率太低，不适用于特殊类型的网络。得益于特殊网络的拓扑特性，可以不使用路由延迟表而构造最短路径路由算法本节介绍三种特殊网络的单播路由算法：1、双向环单播路由算法2、网格和圆环单播路由算法3、超立方单播路由算法8/7/2022Advanced Operating System52/973.3.1 双向环单播路由算法双向环单播路由算法一、双向环单播路由算法一、双向环单播路由算法在双向环上进行决定型单播路由非常简

30、单：消息沿着一个方向被转发：顺时针或者逆时针由于消息可以沿两个方向发送，所以由源节点根据目标节点的位置决定发送方向：如果目标离顺时针方向近，则用顺时针方向；否则选择逆时针方向。一个消息通过几个中间节点按照顺时针或逆时针方向传递，直到到达目标节点。8/7/2022Advanced Operating System53/973.3.1 双向环单播路由算法双向环单播路由算法一、双向环单播路由算法（一、双向环单播路由算法（contd）双向环上的单播路由算法可以使用两条路径：一条沿着顺时针，另一条沿着逆时针。消息也可以被复制，然后每个方向发一个拷贝；也可以分成两半，每半转发到一个方向。8/7/2022A

31、dvanced Operating System54/973.3.1 双向环单播路由算法：双向环单播路由算法：二、算法的一般化二、算法的一般化双向环是k元1维立方，即只有一个维度。若维度大于1，如网格和超立方，就用有序维度路由每次将每个消息沿一个维度路由注意：圆环：在一个维度中的各点以环的方式连接起来，带有周边连接网格：一个维度中的各点以线性排列的形式连接起来，没有周边连接（x1，y1，）（x2，y2，）8/7/2022Advanced Operating System55/973.3.1 双向环单播路由算法：双向环单播路由算法：二、算法一般化（二、算法一般化（contd）环形路由方法可用于在

32、一个维度中对消息进行路由。沿着一个线性排列路由是很简单的。当消息到达每个维度的对等者时，就使用下一个维度。通过使经过的各个维度保持一个单调的顺序，就可以保证不会发生死锁。但这种方法适应性差。8/7/2022Advanced Operating System56/973.3.2 网格和圆环单播路由算法网格和圆环单播路由算法网格和圆环是k元2维立方。圆环有周边邻接，网格没有周边连接。类似地，3维网格和圆环是k元3维立方。本小节介绍1、2维网格的XY路由2、最短且完全适应路由3、折线路由4、最大最短路径路由8/7/2022Advanced Operating System57/973.3.2 网格和

33、圆环单播路由算法：网格和圆环单播路由算法：1、2维网格的维网格的XY路由路由在2维网格中，有序维度路由叫XY路由。每个节点的地址为(x,y)。消息首先沿着X维度转发，然后沿着Y维度路由。特别地，若源和目标分别为(sx,sy)和(dx,dy)，则路由消息将在X维度上走|dx sx|步，然后在Y维度上走|dy sy|步8/7/2022Advanced Operating System58/973.3.2 网格和圆环单播路由算法：网格和圆环单播路由算法：2、最短且完全适应路由最短且完全适应路由在最短且完全适应路由中，每个中间节点，包括源节点，都要充分利用所有可行的最短路径。在2维网格中，只要dxsx

34、0且dysy0，每个节点在选择邻居时总有两个选择。一个好的适应性路由算法应该能选择任意个邻居并能尽可能地保持dx sx0且dysy0的情况。显然，XY路由是最不灵活的一个。8/7/2022Advanced Operating System59/973.3.2 网格和圆环单播路由算法：网格和圆环单播路由算法：适应性路由图示适应性路由图示只要dxsx0且dysy0，每个节点在选择邻居时总有两个选择：X方向或者Y方向8/7/2022Advanced Operating System60/973.3.2 网格和圆环单播路由算法：网格和圆环单播路由算法：3、折线路由折线路由Badr和Podar提出了一个

35、2维网格的折线路由方法首先建立一个包含源和目标的矩形源s=(sx,sy)和目标d=(dx,dy)分别位于矩形的两个对角从端点d=(dx,dy)引出一条线L，这条线将平分经过点d的矩形的两边所组成的角。消息将沿着直线L 路由，但仍在矩形内部。即所有的中间节点都是依照它们到L的距离来选择的在所有合格的节点中，总是选择距离L 最近的一个。直线L8/7/2022Advanced Operating System61/97 3.3.2 网格和圆环单播路由算法：网格和圆环单播路由算法：折线路由（折线路由（contd）在2维圆环中，折线路由可能不是最优的，因为一个中间节点可能有多于两个的合格邻居。8/7/2

36、022Advanced Operating System62/973.3.2 网格和圆环单播路由算法网格和圆环单播路由算法4、最大最短路径最大最短路径(MP)路由路由对于最优解，Wu在k元M维立方的最短路径路由算法的基础上提出了一个最大最短路径最大最短路径(MP)路由算法：路由消息总是被转发到与目标节点存在最大个数的路由消息总是被转发到与目标节点存在最大个数的最短路径（但并不一定是点分离的路径）的那个邻最短路径（但并不一定是点分离的路径）的那个邻居节点。居节点。基于最大最短路径的路由算法是一个对2维网格和M维立方都是最优的路由算法。然而，关于最大最短路径对2维圆环是不是最优的仍然是一个未决的问

37、题。8/7/2022Advanced Operating System63/973.3.2 网格和圆环单播路由算法网格和圆环单播路由算法关于关于边（点）分离边（点）分离路经路经若源和目标都有四个邻居，那么很容易在它们之间建立四个边(或点)分离的路径。一般地，设k(k4)是源和目标节点所具有的最小的邻居的数目，那么，在源和目标之间就存在k个边点分离的路径。8/7/2022Advanced Operating System64/973.3.3 超立方单播路由算法超立方单播路由算法对超立方的单播路由可采用一种相对简单的方法，不必在每个节点中存储路由延迟表。一个n维超立方（n-cube）可定义为：1.

38、Q0，是一个只有一个节点的退化图2.QnK2xQn-1，这里：K2是具有两个节点的完全图；x是两个图的笛卡尔乘积。Qn中的一个节点的地址可以表示为u=unun-1u1（ui0或1，1in）对于两个n-1维立方，在对应的点之间连线8/7/2022Advanced Operating System65/973.3.3 超立方单播路由算法：超立方单播路由算法：一、一、海明距离海明距离两个节点u=unun-1u1和w=wnwn-1w1间最短路径长度就是u和w间的海明距离，表示为H(u,w)。u和w间的异或操作u wrn rn-1.r1定义为：如果uiwi，则ri0;如果uiwi，则ri1,1in。显然

39、，H(u,w)等于u w中1的个数。u(i)表示改变u的第i位(也叫维)例如1101(3)=1001。u=unun-1u1w=wnwn-1w18/7/2022Advanced Operating System66/973.3.3 超立方单播路由算法：超立方单播路由算法：二、二、超立方路由超立方路由在超立方路由中，当前节点u和目标节点w的相对地址为u w，它和将要发送到下一个节点(也叫转发节点)的消息一起传送。在每个跳步，相对距离都会通过将相对地址中的一个1替换而进行更新。8/7/2022Advanced Operating System67/973.3.3 超立方单播路由算法：超立方单播路由算

40、法：二、超立方路由（二、超立方路由（contd）在下面的算法中，节点u是当前节点(可以是源节点)，节点w是目标节点。根据相对地址，选中存在差异的那一维将消息发送给这个维度上对等的节点一个节点，或者开始一次路由，或者收到一个消息发送给本节点的？根据相对地址，选中存在差异的那一维将消息发送给这个维度上对等的节点8/7/2022Advanced Operating System68/973.3.3 超立方单播路由算法：超立方单播路由算法：二、超立方路由（二、超立方路由（contd）在上述算法中，i的选择是随机的，这意味着可能有不止一条最短路径。实际上，最短边分离的个数等于源节点和目标节点的海明距离。

41、如果遵循一个预定的顺序，这种算法就是决定性的，叫做e立方路由。例如，维的顺序遵循升序：首先是1维，然后2维，等等。n维在最后；8/7/2022Advanced Operating System69/973.3.3 超立方单播路由算法：超立方单播路由算法：三、一个三、一个3维立方路由的例子维立方路由的例子例中：源节点u=000目标节点w110。从点000到点110有下列三个点分离路径：路径1（红色）：000100110路径2（蓝色）：000010110路径3（绿色）：000001011111110最短8/7/2022Advanced Operating System70/973.3.3 超立方单

42、播路由算法：超立方单播路由算法：四、超立方多路径路由的性质四、超立方多路径路由的性质超立方多路径路由具有如下性质：若两个节点u和w在n维立方中的海明距离是k则，在u和w之间就有n个点分离路径。在这n条路径中，有k个路径长度为k，其余n-k个路径长度为k+2。例如上一页中，000和110之间的距离|000 110|2。因此，上述路径中有两条长度为2，一条长度48/7/2022Advanced Operating System71/973.3.3 超立方单播路由算法：超立方单播路由算法：四、超立方多路径路由的性质四、超立方多路径路由的性质类似地000和100之间的三条点分离路径为：路径1（红色）：

43、000100路径2（绿色）：000001101100路径3（蓝色）：000010110100000和100之间的海明距离|000 100|=18/7/2022Advanced Operating System72/97第三章第三章 分布式路由算法分布式路由算法主要内容主要内容分布式路由算法导论一般类型网络的最短路径路由算法 特殊类型网络的单播算法特殊类型网络中的多播算法特殊类型网络中的多播算法8/7/2022Advanced Operating System73/973.4特殊类型网络的多播路由算法特殊类型网络的多播路由算法多播（一到多）是指从一个源向任意多个目标节点传送同样的消息。单播和广播

44、都是多播的特例。多播在数据并行编程操作中有一些应用，例如复制，障碍同步，对共享存储器失效以及分布式共享内存系统更新的支持等。8/7/2022Advanced Operating System74/973.4.1 一般的多播路由算法一般的多播路由算法两个主要的多播路由参数是通信量和时间。通信量是以将消息发送到所有的目标所需的通信链接的数目来衡量的。时间就是消息传送的时间。当两个多播路由算法有相同的时间步数时，应该选择具有较小的通信量步数的那一个。通信量可以通过不同的目标共享链接来降低。8/7/2022Advanced Operating System75/973.4.1 一般的多播路由算法：一般

45、的多播路由算法：一、多播优化问题一、多播优化问题通常，多播存在下列四个优化问题：1、多播路径优化问题一个最优的多播路径是一个包括所有目标的最短路径。2、多播回路优化问题最优多播回路是包含所有目标的最短长度的回路。8/7/2022Advanced Operating System76/973.4.1 一般的多播路由算法：一般的多播路由算法：一、多播优化问题（一、多播优化问题（contd）3、steiner树优化问题一个包含所有目标节点的给定拓扑的一个子树最小steiner树具有最小的总长度注意：不一定每个通向目标的路径长度都是最短的。4、多播树优化问题一个包含所有目标的给定拓扑的子树，且树中每个

46、通向目标的路径的长度对于给定的拓扑是最小的。一个最优的多播树具有最小的通信量 8/7/2022Advanced Operating System77/973.4.1 一般的多播路由算法：一般的多播路由算法：一、多播优化问题（一、多播优化问题（contd）不幸的是，对网格和超立方的多播优化问题都是NP完全问题。一般使用启发式多播算法。目前已有人给出了在使用分割-通过路由技术(如虫孔路由)的网络中进行最优化多播通信的充分条件本节考虑两种算法：一是基于路径的；二是基于树的。8/7/2022Advanced Operating System78/973.4.2基于路径的多播路由算法基于路径的多播路由算

47、法一、基本思想：首先建立一个哈密尔顿回路，然后根据这个回路把多播集合转发出去。如果有一个邻居位于目标前面，但距离目标更近，那么就可以抄近路。1895年，爱尔兰数学家哈密尔顿首先提出“环球周游”问题。他用一个正十二面体的20个顶点代表世界上20个城市，要求旅游者能否找到沿着正十二面体的 棱，从某一个顶点（即城市）出发，经过每一个顶点（即每一座城市）恰好一次，然后回到出发顶点？这便是著名的哈密尔顿问题。它的解称为哈密尔顿回路。8/7/2022Advanced Operating System79/973.4.2基于路径的多播路由算法：基于路径的多播路由算法：二、主要步骤二、主要步骤1.在给定的网格

48、或超立方上建立哈密尔顿回路；2.将哈密尔顿回路上的节点排序。这个顺序起始于源节点，并包括所有目标节点。这样哈密尔顿回路就被分割成了哈密尔顿路径；3.对每个中间节点，若它是一个目标节点，保留消息的一个拷贝，删除该目标节点的地址。将消息和目标列表传给一个邻居。这个邻居必须在当前节点之前（按顺序)，离下一个目标最近，且仍在这个目标之前(或就是这个目标)。考虑抄近路8/7/2022Advanced Operating System80/973.4.2基于路径的多播路由算法：基于路径的多播路由算法：三、哈密尔顿路径三、哈密尔顿路径若使用双向链接，则只需一个哈密尔顿路径(而不是哈密尔顿回路)即可。哈密尔顿

49、路径为系统（nn的网格）中的所有节点定义了一个顺序。在整个顺序中，每个节点(x,y)都被赋予一个数字r：x代表第x行；y代表第y列自下而上排序自上而下排序8/7/2022Advanced Operating System81/973.4.2基于路径的多播路由算法：基于路径的多播路由算法：四、哈密尔顿路径举例四、哈密尔顿路径举例例如，一个4X4的网格上每个节点具有的r值如图所示：n=4若y是偶数，r值沿X方向递增r(x,y)=yn+x若y是奇数，r值沿X方向递减r(x,y)=yn+n-x-1=yn+(n-1)-x8/7/2022Advanced Operating System82/973.4.

50、2基于路径的多播路由算法：基于路径的多播路由算法：五、哈密尔顿路径定义五、哈密尔顿路径定义哈密尔顿路径定义两个节点在路径中相邻当且仅当|r(v)-r(u)|=1例如：4X4网格中，使用粗线连接两个相邻节点8/7/2022Advanced Operating System83/973.4.2基于路径的多播路由算法：基于路径的多播路由算法：六、六、低信道网络和高信道网络低信道网络和高信道网络使用顺序定义，整个网格可以分成两个子网：一个包括从低序节点到高序节点的链接；另一个包括从高序节点到低序节点的链接。在两个子网中，除了哈密尔顿路径上的链接以外，其它链接也包含在其中。向高序走向低序走8/7/202