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

《第8章分布式系统中的路由算法.ppt》由会员分享，可在线阅读，更多相关《第8章分布式系统中的路由算法.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 分布式路由算法分布式路由算法 主要内容（主要内容（contd）l一般类型网络的分布式路由算法l自适应和无死锁路由算法 l网格和圆环中的容错单播算法l超立方中的容错单播算法l容错组播算法 进程间通信类型进程间通信类型l有效的进程间通信对分布式系统的性能很重要l根据目标个数的不同，进程间通信的类型有：l一对一（单播）l一对多（组播）l一对所有（广播）通信延迟及其原因通信延迟及其原因l在基于消息传递的分布式系统中，消息一般在到达目标节点之前可能要通过一个或多个中间节点，故存在通信延迟。l分布式系统中的通信延迟依赖于如下四个因素：l网络拓扑：l通常用图表示l定义处理单元（PE）之间是如何连接的l路由

2、l决定如何选择路径以便将消息传递到目的地。通信延迟及其原因通信延迟及其原因（contd）l流量控制l流量控制决定在消息沿路径传递时如何分配网络资源，包括：信道缓冲区l交换l这是一个实际的机制，它决定消息如何从一个输入信道转到一个输出信道。路由算法类型路由算法类型l路由算法类型包括：l特殊 vs.一般l最短 vs.非最短l确定型 vs.适应型l源路由 vs.目标路由l容错型 vs.非容错型l冗余型 vs.非冗余型l死锁避免型 vs.非死锁避免型 一般型路由和特殊型路由一般型路由和特殊型路由l 一般型路由算法l适合于所有类型的网络l但是对于某种特定网络不是很有效l特殊型路由算法l只对特定的网络类型

3、有效，如超立方、网格等l这些算法由于利用了特定网络的拓扑属性，所以效率往往较高。最短路由算法和非最短路由算法最短路由算法和非最短路由算法l最短路径算法l对给定的源-目标对给出一个代价最小的路径l路径的代价l所有跳步（连接）代价的线性和。l缺点：可能会导致网络某一部分的拥塞l非最短路由算法l可以将消息路由到一个更长的路径从而避免拥塞。l在某些情况下，随机路由可能是有效的。确定型路由和适应型路由确定型路由和适应型路由l确定型路径算法l路由路径只在网络的拓扑发生改变时才发生变化，l而且它不使用任何有关网络状态的消息。l适应型路由算法l路径根据网络流量而改变。容错型路由和非容错型路由容错型路由和非容错

4、型路由l容错型路由算法l即使出现错误，被路由消息也能保证送到。l非容错型路由算法l假定路由不会出错l路由算法不必动态调整自己的活动。冗余型路由和非冗余路由冗余型路由和非冗余路由l冗余型路由算法l用几个边分离（或节点分离）的路径向同一个目标发送多个拷贝。l只要这些路径中的一个是好的，那么就会至少有一个消息拷贝到达目标。l必须保证有且只有一个拷贝被接收l非冗余型路由算法l对每个目标只需转发消息的一个拷贝。死锁避免型路由和死锁避免型路由和 非死锁避免型路由非死锁避免型路由l死锁避免型路由算法l通过仔细设计的路由算法，保证不发生死锁。l非死锁避免型路由算法l没有特别的措施来预防或避免死锁。l可能发生死

5、锁，也可能不发生死锁。路由函数路由函数l路由函数l定义一个消息如何从源节点路由到目标节点。l每个PE在收到一个消息以后，都将决定：1）把这条消息传送到本地存储器，还是2）转发到一个邻接的PEl有许多不同的路由函数的定义，例如l依赖于目标的、依赖于输入的、依赖于源的、依赖于路径的等等l本章仅使用依赖于目标的路由函数 路由函数类型路由函数类型l依赖于源的：依赖于源节点、当前节点和目标节点l依赖于目标的：仅仅依赖于当前节点和目标节点l依赖于输入的：依赖于当前节点和目标节点以及邻近的链接l依赖于路径的：依赖于目标节点和从源节点到达当前节点的路径 一般类型网络的最短路径路由算一般类型网络的最短路径路由算

6、法法l许多分组交换网，如法国的Transpac或美国的ARPAnet都使用最短路径路由l本节介绍三个一般类型网络的最短路径路由算法：lDijkstra集中式算法lFord分布式算法lARPAnet路由算法 一般类型网络的最短路径路由算法：一般类型网络的最短路径路由算法：分布式系统图示分布式系统图示l一般地，一个分布式系统可以用图来表示：节点代表PE（处理单元）；边代表通信链接；每个链接的数字代表链接代价。l右图显示了一个分布式系统的例子 Dijkstra集中式算法集中式算法l第一种类型的算法以集中式的风格进行路由lDijkstra集中式算法可以发现一个源节点到所有其他节点的最短路径。lDijk

7、stra集中式算法需求：l需要了解给定网络的全局拓扑消息，即：网络中所有其他节点的列表；节点之间的所有链接；每个链接的代价。Dijkstra集中式算法：集中式算法：算法描述算法描述设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中 Dijks

8、tra集中式算法：集中式算法：算法举例算法举例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 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

9、(4)+l(4,2)=min,2+1=3,D(3)=minD(3),D(4)+l(4,3)=min20,2+2=4。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。Dijkstra集中式算法：集中式算法：算法举例（算法举例（contd）4.取D(1),D(3)中具最小值的对应节点P3加入到集合N中,N=P

10、5,P4,P2,P3对不在N中的其它节点P1更新D(1)=minD(1),D(3)+l(3,1)=min7,4+5=7 Dijkstra集中式算法：集中式算法：算法举例（算法举例（contd）5.取D(1)中具有最小值的对应节点P1加入到集合N中,N=P5,P4,P2,P3,P1,此时，节点都在N中，算法结束。Dijkstra集中式算法：集中式算法：连续的步骤，如下表：连续的步骤，如下表：Ford分布式算法分布式算法l第二种类型的路由算法采用分散式的方法进行路由l分布式算法l每个节点在交互式的基础上和其邻节点交换代价和路由信息，直到这些节点的路由表到达最短路径的要求为止 Ford分布式算法（分

11、布式算法（contd）lFord分布式算法也包括两个部分：l一个初始步骤l一个最短距离计算的步骤l这里，最短距离指一个给定节点和目标节点之间的距离l当所有节点都带有1）一个表示它们到目标节点距离的标记以及2）沿着最短路径到达目标节点要经过的下一个节 点的标记时，算法结束。Ford分布式算法：分布式算法：算法描述算法描述l每个节点v，都有(n,D(v)的标记。lD(v)代表该节点到目标节点的最短距离的当前值；ln是截至目前得到的最短路径的下一个节点。1.初始步骤：设d是目标节点。令D(d)=0，将所有其它节点标记为(.,)Ford分布式算法：分布式算法：算法描述（算法描述（contd）2.最短距

12、离计算步骤：对所有节点的最短路径做标记：对每个节点vd：使用v的每个邻节点w的当前D(w)计算D(w)+l(w,v)，使得D(v):=minD(v),D(w)+l(w,v)更新v的标记：用使上述表达式取值最小的邻接节点代替n，并用新值代替D(v)。对每个节点重复上述操作，直到不再有改变 Ford分布式算法：分布式算法：举例举例l上述算法作用于如图所示的网络：以P5为目标节点l初始：令D(5)=0，将其他节点P1,P2,P3,P4都标记为(.,)Ford分布式算法：分布式算法：举例：第一轮举例：第一轮l对于P1，l邻节点为P2,P3，由当前标记可知P2,P3距离P5都为，则P1不能通过任何节点到

13、达P5，P1仍标记为(.,)l同理，P2仍标记为(.,)l对于P3，l邻节点为P1,P2,P4,P5，其中D(1)=D(2)=D(4)=,D(5)=0l由于P3到P5的距离20+D(5)为20小于当前D(3)=,表明P3经P5有最短路径可达P5l故P3标记为(P5,20)l同理，P4标记为(P5,2)。Ford分布式算法：分布式算法：举例：第二轮举例：第二轮l对于P1，l邻节点为P2,P3，由当前标记可知P5距离P2为，距离P3为20，则P1通过P3有最短路径到达P5，D(1)为P1到P3的距离与P3到P5的距离之和为5+20=25，故P1标记为(P3,25)；l对于P2，l邻节点为P1,P3

14、,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)Ford分布式算法：分布式算法：举例：第三轮举例：第三轮l按同样方法更新P1,P2,P3,P4的标记为：(P2,7),(P4,3),(P4,4),(P5,2)；l由于此后再重复以上算法试图更新每一个节点的标记都不会改变其标记，算法结束。Ford分布式算法：分布式算法：举例小结举例小结 Ford分布式算法（分布式算法（contd）l上例中，所有节点的

15、行为在经过几轮之后都被同步了l上述同步方法仅仅是为了便于演示l同步方法是指所有节点在每一轮中都更新一次标记lFord算法也适用于异步系统，l其中每个节点以随机的速率更新其D(v)值。ARPAnet路由算法路由算法lARPAnet的路由算法是一个可靠、实用的分布式路由算法，也是今天流行的Internet 路由算法的前身。l与Ford算法比较相似l不同的是l算法中的节点都维护一个一般化的路由表，以便记录通过不同邻接节点的最短路径。l这个路由表包含从这个节点到所有其它节点的最优路径的延迟。l每隔固定的时间间隔，路由表就被传送到它的所有邻接节点，直到最小延迟表在某一点达到稳定为止。ARPAnet路由算

16、法：路由算法：举例举例l举例说明：用ARPAnet路由算法时，P1，P2，P3，P4的一般路由表，仍以P5为目标节点l每个表格都包含通过每个邻居到达P5的最短距离l假设在时刻0前已经达到了一个稳定点l即网络延迟表如右图P27P39P111P37P43P112P26P44P520P24P36P52ARPAnet路由算法：路由算法：举例（举例（contd）l假设0时刻，P4与P5之间链接失效，则它更新它的路由延迟表，并传输给P4的所有邻节点，从而使那些节点的路由延迟表发生变化，直到产生一个新的稳定点P27P39P111P37P83P112P26P44P520P24P36P52 ARPAnet路由算

17、法：路由算法：举例（举例（contd）P27P39P111P37P435P112P26P446P520P24P36P5P279P3911P111P379P45P112P268P46P520P246P368P5ARPAnet路由算法：路由算法：举例（举例（contd）l上述过程一直持续到达到一个新的稳定点，P1，P2，P3，P4分别用了20，19，17，20个时间间隔，如下图所示。ARPAnet路由算法（路由算法（contd）lARPAnet路由算法中 每个节点对所有邻居都发送相同消息，对接收节点不做任何标识。l这样，某些节点就会接收无用消息。l在链接节点失效时候，这些消息会导致我们不期望的循环

18、。l例如ARPAnet路由算法：路由算法：不期望的循环，举例不期望的循环，举例l例如，P4和P5链接失效时，P4的最短路径为4，但是这个4来自于P2，而P2到P5的最短路径原来就依赖于P4与P5的链接，由于P4使用P2的信息时，P2的信息尚未得到更新，导致出现不期望的循环：P4P2P4P27P39P111P37P43P112P26P44P520P24P36P52ARPAnet路由算法：路由算法：不期望循环的消除不期望循环的消除l循环的消除是在路由消息中包含路径的所有节点，并把这些消息发给邻居节点。l然而，它的效率较低，因为它的额外开销太大。lShin和Chou，提出了一个避免循环算法：只需在路

19、由消息中存储路径中最近的l个节点，l与相应网络中循环的最大长度有关特殊类型网络的单播路由算法特殊类型网络的单播路由算法l一般类型网络的路由算法适用于所有拓扑类型的网络。但是，l每个节点需要维持路由延迟表，而且l不适用于特殊类型的网络，原因是效率太低。l得益于特殊网络的拓扑特性，可以不使用路由延迟表而构造最短路径路由算法l本节介绍三种特殊网络的单播路由算法：l双向环单播路由算法l网格和圆环单播路由算法l超立方单播路由算法双向环单播路由算法双向环单播路由算法l在双向环上进行决定型单播路由非常简单：l消息沿着一个方向被转发：顺时针或者逆时针l由于消息可以沿两个方向发送，所以由源节点根据目标节点的位置

20、决定发送方向：l如果目标离顺时针方向近，则用顺时针方向；l否则选择逆时针方向。l一个消息通过几个中间节点按照顺时针或逆时针方向传递，直到到达目标节点。双向环单播路由算法（双向环单播路由算法（contd）l双向环上的单播路由算法可以使用两条路径：l一条沿着顺时针，l另一条沿着逆时针。l消息l也可以被复制，然后每个方向发一个拷贝；l也可以分成两半，每半转发到一个方向。双向环单播路由算法：双向环单播路由算法：算法一般化算法一般化l双向环是k元1维立方，即只有一维度。l若维度大于1，例如网格和超立方，就用有序维度路由l每次将每个消息向一个维度路由l圆环：在一个维度中的各点以环的方式连接起来，带有周边连

21、接l网格：一个维度中的各点以线性排列的形式连接起来，没有周边连接双向环单播路由算法：双向环单播路由算法：算法一般化（算法一般化（contd）l环形路由方法可用于在一个维度中对消息进行路由。l沿着一个线性排列路由是很简单的。l当消息到达每个维度的对等者时，就使用下一个维度。l通过使经过的各个维度保持一个单调的顺序，就可以保证不会发生死锁。l但这种方法适应性差。网格和圆环单播路由算法网格和圆环单播路由算法l网格和圆环是k元2维立方。l圆环有周边邻接，l网格没有周边连接。l类似地，3维网格和圆环是k元3维立方。网格和圆环单播路由算法：网格和圆环单播路由算法：2维网格的维网格的XY路由路由l在2维网格

22、中，有序维度路由叫XY路由。l每个节点的地址为(x,y)。l消息首先沿着X维度转发，然后沿着Y维度路由。l特别地，若源和目标分别为(sx,sy)和(dx,dy)，则路由消息将在X维度上走|dx sx|步，然后在Y维度上走|dy sy|步网格和圆环单播路由算法：网格和圆环单播路由算法：最短且完全适应路由最短且完全适应路由l在最短且完全适应路由中，l每个中间节点，包括源节点，都要充分利用所有可行的最短路径。l在2维网格中，l只要dxsx0且dysy0，每个节点在选择邻居时总有两个选择。l一个好的适应性路由算法应该能选择任意个邻居并能尽可能地保持dx sx0且dysy0的情况。l显然,XY路由是最不

23、灵活的一个。网格和圆环单播路由算法：网格和圆环单播路由算法：适应性路由图示适应性路由图示只要dxsx0且dysy0，每个节点在选择邻居时总有两个选择：X方向或者Y方向网格和圆环单播路由算法（网格和圆环单播路由算法（contd）l如果每个链接（信道）拥塞的概率是一样的，那么在最短路由的限制下，哪一个是最好的路由方法呢？l这里的最好是指在这种路由方法下，消息到达目标的延迟最小。网格和圆环单播路由算法：网格和圆环单播路由算法：折线路由折线路由lBadr和Podar提出了一个2维网格的折线路由方法l首先建立一个包含源和目标的矩形l源s=(sx,sy)和目标d=(dx,dy)分别位于矩形的两个对角l从端

24、点d=(dx,dy)引出一条线L，这条线将平分经过点d的矩形的两边所组成的角。消息将沿着直线L 路由，但仍在矩形内部。即所有的中间节点都是依照它们到L的距离来选择的在所有合格的节点中，总是选择距离L 最近的一个。直线L网格和圆环单播路由算法：网格和圆环单播路由算法：折线路由（折线路由（contd）l在2维圆环中，折线路由可能不是最优的，因为一个中间节点可能有多于两个的合格邻居。l特别，对一个n为偶数的nxn的圆环，存在一个具有四个合格邻居的节点。而且，有2(n-2)个节点，它们和源的距离为n2个行或列，因此，在最短路径上就有三个方向。网格和圆环单播路由算法（网格和圆环单播路由算法（contd）

25、l对于最优解，Wu在k元M维立方的最短路径路由算法的基础上提出了一个最大最短路径(MP)路由算法：l路由消息总是被转发到与目标节点存在最大个数的最短路径的那个邻居节点。l基于最大最短路径的路由算法是一个对2维网格和M维立方都是最优的路由算法。l然而，关于最大最短路径对2维圆环是不是最优的仍然是一个未决的问题。网格和圆环单播路由算法（网格和圆环单播路由算法（contd）l若源和目标都有四个邻居，那么很容易在它们之间建立四个边(或点)分离的路径，如图。l一般地，设k(k=8)是源和目标节点所具有的最小的邻居的数目，那么，在源和目标之间就存在k个边点分离的路径。超立方单播路由算法超立方单播路由算法l

26、对超立方的单播路由可采用一种相对简单的方法，不必在每个节点中存储路由延迟表。l一个n维超立方（n-cube）可定义为：1.Q0，是一个只有一个节点的退化图2.QnK2xQn-1，这里：K2是具有两个节点的完全图；x是两个图的笛卡尔乘积。lQn中的一个节点的地址可以表示为u=unun-1u1（ui0或1，1=i=n）超立方单播路由算法：超立方单播路由算法：海明距离海明距离l两个节点u=unun-1u1和w=wnwn-1w1间最短路径长度就是u和w间的海明距离，表示为H(u,w)。lu和w间的异或操作uwrn rn-1.r1定义为：如果uiwi，则ri0;如果uiwi，则ri1,1=i=n。l显然

27、，H(u,w)等于uw中1的个数。lu(i)表示改变u的第i位(也叫维)例如1101(3)=1001。超立方单播路由算法：超立方单播路由算法：超立方路由超立方路由l在超立方路由中，l当前节点u和目标节点w的相对地址为uw，它和将要发送到下一个节点(这个节点也叫转发节点)的消息一起传送。l在每个跳步，相对距离都会通过将uw中的一个1替换而进行更新。超立方单播路由算法：超立方单播路由算法：超立方路由（超立方路由（contd）l在下面的算法中，节点u是当前节点(可以是源节点)，节点w是目标节点。超立方单播路由算法：超立方单播路由算法：超立方路由（超立方路由（contd）l在上述算法中，i的选择是随机

28、的，这意味着可能有不止一条最短路径。l实际上，最短边分离的个数等于源节点和目标节点的海明距离。l如果遵循一个预定的顺序，这种算法就是决定性的，叫做e立方路由。l例如，维的顺序遵循升序：首先是1维，然后2维，等等。n维在最后；超立方单播路由算法：超立方单播路由算法：一个一个3维立方路由的例子维立方路由的例子l例中：源节点u=000目标节点w110。从点000到点110有下列三个点分离路径：l路径1（红色）：000100110l路径2（蓝色）：000010110l路径3（绿色）：000001011111110超立方单播路由算法：超立方单播路由算法：超立方多路径路由的性质超立方多路径路由的性质l超立

29、方多路径路由具有如下性质：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超立方单播路由算法：超立方单播路由算法：超立方多路径路由的性质超立方多路径路由的性质l类似地000和100之间的三条点分离路径为：l路径1（红色）：000100l路径2（绿色）：000001101100l路径3（蓝色）

30、：000010110100l000和100之间的海明距离|000100|=1特殊类型网络的多播路由算法特殊类型网络的多播路由算法l多播（一到多）是指从一个源向任意多个目标节点传送同样的消息。l只有一个目标的单播和以网络中的所有节点为目标的广播都是多播的特例。l多播在数据并行编程操作中有一些应用，例如l复制，障碍同步，对共享存储器失效以及分布式共享内存系统更新的支持等。一般的多播路由算法一般的多播路由算法l两个主要的多播路由参数是通信量和时间。l通信量是以将消息发送到所有的目标所需的通信链接的数目来衡量的。l时间就是消息传送的时间。l当两个多播路由算法有相同的时间步数时，应该选择具有较小的通信量

31、步数的那一个。l通信量可以通过不同的目标共享链接来降低。一般的多播路由算法：一般的多播路由算法：多播优化问题多播优化问题l通常，多播存在下列四个优化问题：l多播路径优化问题l一个最优的多播路径是一个包括所有目标的最短路径。l多播回路优化问题l最优多播回路是包含所有目标的最短长度的回路。一般的多播路由算法：一般的多播路由算法：多播优化问题（多播优化问题（contd）lsteiner树优化问题l一个包含所有目标节点的给定拓扑的一个子树l最小steiner树具有最小的总长度l注意：不一定每个通向目标的路径长度都是最短的。l多播树优化问题l一个包含所有目标的给定拓扑的子树，且树中每个通向目标的路径的长

32、度对于给定的拓扑是最小的。l一个最优的多播树具有最小的通信量 一般的多播路由算法：一般的多播路由算法：多播优化问题（多播优化问题（contd）l网格和超立方的多播优化问题都是NP完全问题。因此，一般使用启发式多播算法。l目前，已有人给出了在使用分割-通过路由技术(如虫孔路由)的网络中进行最优化多播通信的充分条件。l本节考虑两种算法：一个是基于路径的；另一个是基于树的。基于路径的多播路由算法基于路径的多播路由算法l基本思想：l首先建立一个哈密尔顿回路，l然后根据这个回路把多播集合转发出去。l如果有一个邻居位于目标前面，但距离目标更近，那么就可以抄近路。1895年，爱尔兰数学家哈密尔顿首先提出“环

33、球周游”问题。他用一个正十二面体的20个顶点代表世界上20个城市，要求旅游者能否找到沿着正十二面体的 棱，从某一个顶点（即城市）出发，经过每一个顶点（即每一座城市）恰好一次，然后回到出发顶点？这便是著名的哈密尔顿问题。它的解称为哈密尔顿回路。基于路径的多播路由算法：基于路径的多播路由算法：主要步骤主要步骤1.在给定的网格或超立方上建立哈密尔顿回路；2.将哈密尔顿回路上的节点排序。l这个顺序起始于源节点，并包括所有目标节点。l这样哈密尔顿回路就被分割成了哈密尔顿路径；3.对每个中间节点，l若它是一个目标节点，l保留消息的一个拷贝，删除该目标节点的地址。l将消息和目标列表传给一个邻居。这个邻居必须

34、在当前节点之前（按顺序)，离下一个目标最近，且仍在这个目标之前(或就是这个目标)。基于路径的多播路由算法：基于路径的多播路由算法：哈密尔顿路径哈密尔顿路径l若使用双向链接，则只需一个哈密尔顿路径(而不是哈密尔顿回路)即可。l哈密尔顿路径为系统中的所有节点定义了一个顺序。l在整个顺序中，每个节点(x,y)都被赋予一个数字r：基于路径的多播路由算法：基于路径的多播路由算法：哈密尔顿路径举例哈密尔顿路径举例l例如，一个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)

35、-x基于路径的多播路由算法：基于路径的多播路由算法：哈密尔顿路径定义哈密尔顿路径定义l哈密尔顿路径定义l两个节点在路径中相邻当且仅当|r(v)-r(u)|=1l例如：l4X4网格中，使用粗线连接两个相邻节点基于路径的多播路由算法：基于路径的多播路由算法：低信道网络和高信道网络低信道网络和高信道网络l使用顺序定义，整个网格可以分成两个子网：l一个包括从低序节点到高序节点的链接；l另一个包括从高序节点到低序节点的链接。l在两个子网中，除了哈密尔顿路径上的链接以外，其它链接也包含在其中。基于路径的多播路由算法：基于路径的多播路由算法：最短路径路由函数最短路径路由函数l目标依据它们与源的相对位置也分为

36、两个子集。l一个子集将沿着高信道网络传送，l另外一个将沿着低信道网络传送。l为了将消息沿着最短路径传送，定义如下路由函数。l假定使用高信道网络。lv和d（r(v)r(d)）分别是中间节点和目标节点。l若d是v的一个邻居，那么消息将直接转发到d；l否则，选择一个满足下式的v的邻居u：基于路径的多播路由算法：基于路径的多播路由算法：举例举例l下图显示了一个在4X4网格中进行多播的例子l哈密尔顿路径连接了那些r值依次递增的节点l假定节点6(地址为(1,1)为源节点，目标节点为0、2、10、13和14。紫色：源节点；蓝色：目标节点基于路径的多播路由算法：基于路径的多播路由算法：举例（举例（contd）

37、l显然，转发消息到节点0和2时，应该使用低信道网络。l依据路由函数，可以得到如下路径：l同样，转发消息到节点10，13和18时应使用高信道网络红色：低信道网络路径和 具有最小r值的邻居深紫色：高信道网络路径和 具有最大r值的邻居基于树的多播路由算法基于树的多播路由算法lLan的贪婪多播算法可以应用于超立方。在这个算法中，l每个节点(包括源节点)在收到包含目标节点地址列表的消息后，就把自己的地址和目标节点的地址相比较。l若发现匹配，消息的一个拷贝将被送往本地的处理器l若多播集合非空，当前节点将决定把目标列表中的地址转发到哪些邻居。基于树的多播路由算法：基于树的多播路由算法：根据维度顺序进行转发根

38、据维度顺序进行转发l维度顺序由目标节点的相对二进制地址来决定ln位地址的每一位都有一个计数器。l计数器的内容代表相应维度的信息。l具有最大计数值的那一维将被选中。l所有在这一位为1的目标将被转发到这一维上的那个邻居l在剩余的目标中，将利用下一个被选中的维度重复上述步骤。l当剩余的多播集合为空时，这一过程就结束。基于树的多播路由算法：基于树的多播路由算法：4维立方中的多播例子维立方中的多播例子l考虑一个4维立方体(目标用蓝色节点代表)l节点0010打算向组播集0000，0001，1001，1100，1110中的每个节点发送消息l所有目标节点的实际地址和源节点0010的实际地址做异或操作，得到多播

39、集合的相对地址0010，0011，1011，1110，1100。l每一列的1的数目组成了一个称为列总和的向量(3,2,4,2)基于树的多播路由算法：基于树的多播路由算法：4维立方中多播例子（维立方中多播例子（contd）l沿着第2维的邻居拥有最受欢迎的维度。即节点0000成为下一个转发节点，发往节点0000的消息包含子集(0000，0001，1001，1100)。l只有节点1110被剩下了，这个节点可以通过第3维的邻居转发，也可以通过第4维的邻居转发。l上述过程将在每个转发节点重复操作。l每个多播树的分支都将继续到剩余的多播集合变空为止基于树的多播路由算法：基于树的多播路由算法：基于递归倍增的

40、启发式算法基于递归倍增的启发式算法l当使用分割-通过网络时，可以使用递归倍增方法构造启发式算法。l以单端口模型下的2维网格为例来说明McKinIey等人提出的u-网格算法。l先为2维网格的节点地址定义一个字典序(t)，即若x1tx2或者x1=x2,但y1ty2，则有(x1,y1)(x2,y2)。l边分离性质：l假定P(n1,n2)是n1和n2间最短路径，易知，若n1tn2tn3tn4，则P(n1,n2)和P(n3,n4)边分离基于树的多播路由算法：基于树的多播路由算法：基于递归倍增的启发式算法基于递归倍增的启发式算法l利用边分离性质，可建立下面避免竞争且具有最少步数的多播算法l假定源节点是(0

41、,0)，按照字典顺序重新排列目标节点、并将源节点放在前面。l将列表分成两个相等的子列表。源节点将多播消息发往第二个子列表的第一个节点。l重复上述分割步骤直到每个子列表中只有一个节点；l若源节点不是(0,0)，可重新定义排列顺序以便源节点成为第一个节点基于树的多播路由算法：基于树的多播路由算法：举例举例l考虑一个4*4网格，(0,0)是源节点，(1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和(3,2)是目标节点。l源节点和目标节点的字典顺序是：(0,0),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和(3,2)基于树的多播路由算法：基于树的多播路

42、由算法：举例（举例（contd）l第一步，这个列表被分成两个子列表(0,0),(1,0),(1,1),(1,2)和(1,3),(2,0),(2,1),(3,2)l源(0,0)将信息发送到第二个子列表的第一个节点(1,3)l使用XY路由建立(0,0)到(1,3)的路由路径基于树的多播路由算法：基于树的多播路由算法：举例（举例（contd）l在每个子列表上重复上述过程，有：本课小结本课小结l本课主要内容（8小节）l分布式路由算法导论l进程间通信类型l通信延迟及其原因l路由算法分类l路由函数定义l一般类型网络的最短路径路由算法lDijkstra集中式算法lFord分布式算法lARPAnet的路由算法 l特殊类型网络的单播算法l双向环上的单播算法及其一般化l网格和圆环上的单播算法2维网格的XY路由、适应性路由、折线路由等l超立方基于海明距离的一种简单的路由算法l特殊类型网络中的多播算法l基于（哈密尔顿）路径l基于树的多播应用于超立方的Lan的贪婪多播算法U-网格算法