高级操作系统 Advanced Operating System

Presentation on theme: "高级操作系统 Advanced Operating System"— Presentation transcript:

1 高级操作系统 Advanced Operating System
陈香兰（代） 0551_ 中国科学技术大学计算机系

2 第四章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法
第四章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 虚信道和虚网络 完全自适应和无死锁路由算法

3 第四章 分布式路由算法 主要内容（ cont'd ）
几个自适应和无死锁路由算法 容错单播的一般方法 网格和圆环中的容错单播算法 超立方中的容错单播算法 容错组播算法

4 4.1分布式路由算法导论 进程间通信类型 有效的进程间通信对分布式系统的性能很重要 根据目标个数的不同，进程间通信的类型有： 一对一（单播）
一对多（组播） 一对所有（广播）

5 4.1分布式路由算法导论： 通信延迟及其原因 在基于消息传递的分布式系统中，消息一般在到达目标节点之前可能要通过一个或多个中间节点，故存在通信延迟。 分布式系统中的通信延迟依赖于如下四个因素： 网络拓扑： 通常用图表示 定义处理单元（PE）之间是如何连接的 路由 决定如何选择路径以便将消息传递到目的地。

6 4.1分布式路由算法导论： 通信延迟及其原因（cont'd）
流量控制 流量控制决定在消息沿路径传递时如何分配网络资源，包括： 信道 缓冲区 交换 这是一个实际的机制，它决定消息如何从一个输入信道转到一个输出信道。

7 4.1分布式路由算法导论： 路由算法类型 路由算法类型包括： 1）特殊 vs. 一般 2）最短 vs. 非最短 3）确定型 vs. 适应型

8 1）一般型路由和特殊型路由 一般型路由算法 特殊型路由算法 适合于所有类型的网络 但是对于某种特定网络不是很有效
只对特定的网络类型有效，如超立方、网格等 这些算法由于利用了特定网络的拓扑属性，所以效率往往较高。

9 2）最短路由算法和非最短路由算法 最短路径算法 非最短路由算法 对给定的源-目标对给出一个代价最小的路径 路径的代价
所有跳步（连接）代价的线性和。 缺点：可能会导致网络某一部分的拥塞 非最短路由算法 可以将消息路由到一个更长的路径从而避免拥塞。 在某些情况下，随机路由可能是有效的。

10 3）确定型路由和适应型路由 确定型路径算法 适应型路由算法 路由路径只在网络的拓扑发生改变时才发生变化，
而且它不使用任何有关网络状态的消息。 适应型路由算法 路径根据网络流量而改变。

11 5）容错型路由和非容错型路由 容错型路由算法 非容错型路由算法 即使出现错误，被路由消息也能保证送到。 假定路由不会出错
路由算法不必动态调整自己的活动。

12 6）冗余型路由和非冗余路由 冗余型路由算法 非冗余型路由算法 用几个边分离（或节点分离）的路径向同一个目标发送多个拷贝。
只要这些路径中的一个是好的，那么就会至少有一个消息拷贝到达目标。 必须保证有且只有一个拷贝被接收 非冗余型路由算法 对每个目标只需转发消息的一个拷贝。

13 7）死锁避免型路由和非死锁避免型路由 死锁避免型路由算法 非死锁避免型路由算法 通过仔细设计的路由算法，保证不发生死锁。
没有特别的设施来预防或避免死锁。 可能发生死锁，也可能不发生死锁。

14 4.1分布式路由算法导论： 路由函数 路由函数 有许多不同的路由函数的定义，例如 本章仅使用依赖于目标的路由函数
定义一个消息如何从源节点路由到目标节点。 每个PE在收到一个消息以后，都将决定： 1）把这条消息传送到本地存储器，还是 2）转发到一个邻接的PE 有许多不同的路由函数的定义，例如 依赖于目标的、依赖于输入的、依赖于源的、依赖于路径的等等 本章仅使用依赖于目标的路由函数

15 4.2 一般类型网络的最短路径路由算法 许多分组交换网，如法国的Transpac或美国的ARPAnet都使用最短路径路由
本节介绍三个一般类型网络的 最短路径路由算法： Dijkstra集中式算法 Ford分布式算法 ARPAnet路由算法

16 4.2 一般类型网络的最短路径路由算法： 分布式系统图示
一般地，一个分布式系统可以用图来表示： 节点代表PE（处理单元）； 边代表通信链接； 每个链接的数字代表链接代价。 一个分布式系 统的例子

17 4.2.1 Dijkstra集中式算法 第一种类型的算法以集中式的风格进行路由
算法需求： 需要了解给定网络的全局拓扑消息，即： 1）网络中所有其他节点的列表； 2）节点之间的所有链接； 3）每个链接的代价。

18 4.2.1 Dijkstra集中式算法： 算法描述 设：D(v)是从源s到节点v的距离； l(v,w)是节点v和w之间的链接代价
沿给定路径的链接 的代价的和 设：D(v)是从源s到节点v的距离； l(v,w)是节点v和w之间的链接代价 Dijkstra算法如下： 1） 设N={s}； 对不在N中的每一个节点v，若v与s相连，则令D(v)=l(s, v)。否则，D(v)为∞。 2） 找到不在N中的一个节点w，并且D(w)最小，将w加入N； 然后对所有不在N中的其它节点计算并更新D(v)： D(v) := min[D(v), D(w)+l(w,v)] 重复步骤2，直到所有节点都在N中

19 4.2.1 Dijkstra集中式算法： 算法举例 上述算法作用于如图所示的网络： 以P5为源节点
1）一开始，集合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

20 4.2.1 Dijkstra集中式算法： 算法举例（cont'd）
2）取D(1),D(2),D(3),D(4)中具最小值的对应节点P4加入到集合N中, N= { P5,P4}, 对不在N中的其它节点P3,P2,P1更新 D(1)=min{D(1),D(4)+l(4,1)} =min{∞,2+∞}=∞, D(2)=min{D(2),D(4)+l(4,2)} =min{∞,2+1}=3, D(3)=min{D(3),D(4)+l(4,3)} =min{20,2+2}=4。

21 4.2.1 Dijkstra集中式算法： 算法举例（cont'd）
3）取D(1),D(2),D(3)中具最小值的对应节点P2加入到集合N中，N={P5,P4,P2}, 对不在N中的其它节点P3,P1更新 D(1)=min{D(1),D(2)+l(2,1)} =min{∞,3+4}=7 D(3)=min{D(3),D(2)+l(2,3)} =min{4, 3+3}=4。

22 4.2.1 Dijkstra集中式算法： 算法举例（cont‘d）
4）取D(1),D(3)中具最小值的对应节点P3加入到集合N中, N= { P5,P4,P2,P3} 对不在N中的其它节点P1更新 D(1)=min{D(1),D(3)+l(3,1)} =min{7,4+5}=7

23 4.2.1 Dijkstra集中式算法： 算法举例（cont'd）
取D(1)中具有最小值的对应节点P1加入到集合N中, N= { P5,P4,P2,P3,P1}, 此时，节点都在N中，算法结束。

24 4.2.1 Dijkstra集中式算法： 连续的步骤，如下表：
轮 N D(1) D(2) D(3) D(4) 初始 1 2 3 4 {P5} {P5, P4} {P5, P4 , P2} {P5, P4 , P2 , P3} {P5, P4 , P2 , P3 , P1} ∞ 7 20

25 4.2.2Ford分布式算法 第二种类型的路由算法采用分散式的方法进行路由 分布式算法
每个节点在交互式的基础上和其邻节点交换代价和路由信息，直到这些节点的路由表到达最短路径的要求为止

26 4.2.2Ford分布式算法（cont‘d） Ford分布式算法也包括两个部分： 当所有节点都带有下面两个标记时，算法结束 一个初始步骤
一个最短距离计算的步骤 这里，最短距离指一个给定节点和目标节点之间的距离 当所有节点都带有下面两个标记时，算法结束 一个表示它们到目标节点距离的标记 以及，一个沿着最短路径到达目标节点要经过的下一个节点的标记

27 4.2.2Ford分布式算法： 算法描述 每个节点v，都有(next, D(v))的标记。 1）初始步骤：
令D(d)=0，将所有其它节点标记为(.,∞)

28 4.2.2Ford分布式算法： 算法描述（cont'd）
2）最短距离计算步骤： 对所有节点的最短路径做标记： 对每个节点v≠d： 使用v的每个邻节点w的当前D(w) 计算D(w)+l(w, v)，使得 D(v):=min{D(v), D(w)+l(w, v)} 更新v的标记：用使上述表达式取值最小的邻接节点代替next，并用新值代替D(v)。 对每个节点重复上述操作，直到不再有改变

29 4.2.2Ford分布式算法： 举例 上述算法作用于如图所示的网络： 以P5为目标节点
初始： 令D(5) = 0，其他节点P1,P2,P3,P4都标记为(.,∞)

30 4.2.2Ford分布式算法： 举例：第一轮 对于P1， 同理，P2仍标记为(.,∞) 对于P3， 同理，P４标记为(P5, 2)。
邻节点为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)。

31 4.2.2Ford分布式算法： 举例：第二轮 对于P1， 对于P2， 同理，更新P3和P4的标记为 (P4,4)，(P5,2)
邻节点为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)

32 4.2.2Ford分布式算法： 举例：第三轮 按同样方法更新P1,P2,P3,P4的标记为： (P2,7),(P4,3),(P4,4),(P5,2)； 由于此后再重复以上算法试图更新 每一个节点的标记都不会改变其 标记，算法结束。

33 4.2.2Ford分布式算法： 举例小结 轮 P1 P2 P3 P4 初始 (., ∞) 1 (P5, 20) (P5, 2) 2

34 4.2.2Ford分布式算法（cont’d） 上例中，所有节点的行为在经过几轮之后都被同步了 上述同步方法仅仅是为了便于演示
同步方法是指所有节点在每一轮中都更新一次标记 Ford算法也适用于异步系统， 其中每个节点以随机的速率更新其D(v)值。

35 4.2.3 ARPAnet路由算法 ARPAnet的路由算法是一个可靠、实用的分布式路由算法，也是今天流行的Internet 路由算法的前身。 与Ford算法比较相似 不同的是 算法中的节点都维护一个一般化的路由表，以便记录通过所有不同邻接节点的最短路径。 这个路由表包含从这个节点到所有其它节点的最优路径的延迟。 每隔固定的时间间隔，路由表就被传送到它的所有邻接节点，直到最小延迟表在某一点达到稳定为止。

36 4.2.3 ARPAnet路由算法： 举例 举例说明：用ARPAnet路由算法时，P1，P2，P3，P4的一般路由表，仍以P5为目标节点
11 P3 7 P4 3 举例说明：用ARPAnet路由算法时，P1，P2，P3，P4的一般路由表，仍以P5为目标节点 每个表格都包含通过每个邻居到达P5的最短距离 假设在时刻0前已经达到了一个稳定点 即网络延迟表如右图 P2 4 P3 6 P5 2 P2 7 P3 9 P1 12 P2 6 P4 4 P5 20

37 4.2.3 ARPAnet路由算法： 举例（cont'd）
11 P3 7 P4 3 假设0时刻，P4与P5之间链接失效，则P4更新它的路由延迟表，并传输给它的所有邻节点，从而使那些节点的路由延迟表发生变化，直到产生一个新的稳定点 P2 4 P3 6 P5 2∞ P2 7 P3 9  P1 12 P2 6 P4 4 P5 20

38 4.2.3 ARPAnet路由算法： 举例（cont'd）
11 P3 7 P4 35 P1 11 P3 79 P4 5 P2 4 P3 6 P5 ∞ P2 46 P3 68 P5 ∞ P2 7 P3 9 P2 79 P3 911   P1 12 P2 6 P4 46 P5 20 P1 12 P2 68 P4 6 P5 20 ……

39 4.2.3 ARPAnet路由算法： 举例（cont'd）
上述过程一直持续到达到一个新的稳定点，P1，P2，P3，P4分别用了20，19，17，20个时间间隔，如下图所示。

40 4.2.3 ARPAnet路由算法（cont'd） ARPAnet路由算法中 每个节点对所有邻居都发送相同消息，对接收节点不做任何标识。
这样，某些节点就会接收无用消息。 在链接节点失效时候，这些消息会导致我们不期望的循环。 例如

41 4.2.3 ARPAnet路由算法： 不期望的循环，举例
11 P3 7 P4 3 例如，P4和P5链接失效时，P4的最短路径为4，但是这个4来自于P2，而P2到P5的最短路径原来就依赖于P4与P5的链接，由于P4使用P2的信息时，P2的信息尚未得到更新，导致出现不期望的循环：P4P2P4 P2 4 P3 6 P5 2∞ P2 7 P3 9  P1 12 P2 6 P4 4 P5 20

42 4.2.3 ARPAnet路由算法： 不期望循环的消除
循环的消除是在路由消息中包含路径的所有节点，并把这些消息发给邻居节点。 然而，它的效率较底，因为它的额外开销太大。 Shin和Chou，提出了一个避免循环算法：只需在路由消息中存储路径中最近的 个节点， 与相应网络中循环的最大长度有关

43 4.3特殊类型网络的单播路由算法 一般类型网络的路由算法适用于所有拓扑类型的网络。但是，
每个节点需要维持路由延迟表，而且 不适用于特殊类型的网络，原因是效率太低。 得益于特殊网络的拓扑特性，可以不使用路由延迟表而构造最短路径路由算法 本节介绍三种特殊网络的单播路由算法： 双向环单播路由算法 网格和圆环单播路由算法 超立方单播路由算法

44 4.3.1 双向环单播路由算法 在双向环上进行决定型单播路由非常简单： 消息沿着一个方向被转发：顺时针或者逆时针
由于消息可以沿两个方向发送，所以由源节点根据目标节点的位置决定发送方向： 如果目标离顺时针方向近，则用顺时针方向； 否则选择逆时针方向。 一个消息通过几个中间节点按照顺时针或逆时针方向传递，直到到达目标节点。

45 4.3.1 双向环单播路由算法（ cont'd ） 因此，双向环上的单播路由算法可以使用两条路径： 消息 一条沿着顺时针，
另一条沿着逆时针。 消息 也可以被复制，然后每个方向发一个拷贝； 也可以分成两半，每半转发到一个方向。

46 4.3.1 双向环单播路由算法： 算法一般化 双向环是k元1维立方，即只有一维度。 若维度大于1，例如网格和超立方，就用有序维度路由
每次将每个消息向一个维度路由 圆环：在一个维度中的各点以环的方式连接起来，带有周边连接 网格：一个维度中的各点以线性排列的形式连接起来，没有周边连接

47 4.3.1 双向环单播路由算法： 算法一般化（ cont'd ）
环形路由方法可用于在一个维度中对消息进行路由。 沿着一个线性排列路由是很简单的。 当消息到达每个维度的对等者时，就使用下一个维度。 通过使经过的各个维度保持一个单调的顺序，就可以保证不会发生死锁。 但这种方法适应性差。

48 4.3.2 网格和圆环单播路由算法 网格和圆环是k元2维立方。 类似地，3维网格和圆环是k元3维立方。 本小节介绍 圆环有周边邻接，
网格没有周边连接。 类似地，3维网格和圆环是k元3维立方。 本小节介绍 2维网格的XY路由 最短且完全适应路由 折线路由 最大最短路径路由

49 4.3.2 网格和圆环单播路由算法： 2维网格的XY路由
特别地，若源和目标分别为 (sx,sy)和(dx,dy)，则路由消 息将在X维度上走|dx – sx| 步， 然后在Y维度上走|dy– sy|步

50 4.3.2 网格和圆环单播路由算法： 最短且完全适应路由
在最短且完全适应路由中， 每个中间节点，包括源节点，都要充分利用所有可行的最短路径。 在2维网格中， 只要dx–sx≠0且dy–sy≠0，每个节点在选择邻居时总有两个选择。 一个好的适应性路由算法应该能选择任意－个邻居并能尽可能地保持dx –sx≠0且dy–sy≠0的情况。 显然，XY路由是最不灵活的一个。

51 4.3.2 网格和圆环单播路由算法： 适应性路由图示 只要dx–sx≠0且dy–sy≠0， 每个节点在选择邻居时总有
两个选择：X方向或者Y方向

52 4.3.2 网格和圆环单播路由算法（ cont'd ） 如果每个链接（信道）拥塞的概率是一样的，那么在最短路由的限制下，哪一个是最好的路由方法呢？ 这里的最好是指在这种路由方法下，消息到达目标的延迟最小。

53 4.3.2 网格和圆环单播路由算法： 折线路由 Badr和Podar提出了一个2维网格的折线路由方法 首先建立一个包含源和目标的矩形．
源s=(sx, sy)和目标d=(dx, dy)分别位于矩形的两个对角 从目标d=(dx,dy)引出一条线L，这条线将平分经过点d的矩形的两边所组成的角。 消息将沿着直线L 路由，但仍在矩 形内部。 即所有的中间节点都是依照它们到 L的距离来选择的——在所有合格 的节点中，总是选择距离L 最近的 一个。 直线L

54 4.3.2 网格和圆环单播路由算法： 折线路由（ cont'd ）
在2维圆环中，折线路由可能不是最优的，因为一个中间节点可能有多于两个的合格邻居。 特别，对一个n为偶数的n×n的圆环，存在一个具有四个合格邻居的节点。而且，有2(n-2)个节点，它们和源的距离为n／2个行或列，因此，在最短路径上就有三个方向。

55 4.3.2 网格和圆环单播路由算法（ cont'd ） 对于最优解，Wu在k元M维立方的最短路径路由算法的基础上提出了一个最大最短路径(MP)路由算法： 路由消息总是被转发到与目标节点存在最大个数的最短路径的那个邻居节点。 基于最大最短路径的路由算法是一个对2维网格和M维立方都是最优的路由算法。 然而，关于最大最短路径对2维圆环是不是最优的仍然是一个未决的问题。

56 4.3.2 网格和圆环单播路由算法（ cont'd ） 若源和目标都有四个邻居， 那么很容易在它们之间建立 四个边（或点）分离的路径， 如图。 一般地，设k(k≤4)是源和目 标节点所具有的最小的邻居 的数目，那么，在源和目标 之间就存在k个边（点）分离 的路径。

57 4.3.3 超立方单播路由算法 对超立方的单播路由可采用一种相对简单的方法，不必在每个节点中存储路由延迟表。
一个n维超立方（n-cube）可定义为： Q0，是一个只有一个节点的退化图 Qn＝K2×Qn-1，这里： K2是具有两个节点的完全图； ×是两个图的笛卡尔乘积。 Qn中的一个节点的地址可以表示为 u=unun-1…u1（ui＝0或1，1≤i≤n）

58 4.3.3 超立方单播路由算法： 海明距离 两个节点u=unun-1…u1和w =wnwn-1…w1间最短路径长度就是u和w间的海明距离，表示为H(u,w)。 u和w间的异或操作u⊕w＝rn rn-1 …. r1定义为： 如果ui＝wi，则ri＝0; 如果ui≠wi，则ri＝1,1≤i ≤ n。 显然，H(u,w)等于u⊕w中1的个数。 u(i)表示改变u的第i位(也叫维)．例如1101(3)=1001。

59 4.3.3 超立方单播路由算法： 超立方路由 在超立方路由中，
当前节点u和目标节点w的相对地址为u⊕w，它和将要发送到下一个节点(这个节点也叫转发节点)的消息一起传送。 在每个跳步，相对地址都会通过将u⊕w中的一个1替换而进行更新。

60 4.3.3 超立方单播路由算法： 超立方路由（ cont'd ）
在下面的算法中，节点u是当前节点(可以是源节点)，节点w是目标节点。

61 4.3.3 超立方单播路由算法： 超立方路由（ cont'd ）
在上述算法中，i的选择是随机的， 这意味着可能有不止一条最短路径。 实际上，最短边分离的个数等于源节点和目标节点的海明距离。 如果遵循一个预定的顺序，这种算法就是决定性的，叫做e立方路由。 例如，维的顺序遵循升序：首先是1维，然后2维，等等。n维在最后；

62 4.3.3 超立方单播路由算法： 一个3维立方路由的例子
例中：源节点u=000，目标节点w＝110。 从点000到点110有下列三个点分离路径： 路径1（红色）：000100110 路径2（蓝色）：000010110 路径3（绿色）：000001011111110

63 4.3.3 超立方单播路由算法： 超立方多路径路由的性质
超立方多路径路由具有如下性质： 若两个节点u和w在n维立方中的海明距离是k． 则，在u和w之间就有n个点分离路径。 在这n条路径中，有k个路径长度为k， 其余n-k个路径长度为k+2。 000和110之间的距离|000⊕110|＝2。 因此，上述路径中有两条长度为2，一条长度为4 路径1（红色）：000100110 路径2（蓝色）：000010110 路径3（绿色）：000001011111110

64 4.3.3 超立方单播路由算法： 超立方多路径路由的性质
类似地．000和100之间的三条点分离路径为： 路径1（红色）：000100 路径2（绿色）：000001101100 路径3（蓝色）：000010110100 000和100之间的海明距离 |000⊕100|=1

65 4.4特殊类型网络的多播路由算法 多播（一到多）是指从一个源向任意多个目标节点传送同样的消息。
只有一个目标的单播和以网络中的所有节点为目标的广播都是多播的特例。 多播在数据并行编程操作中有一些应用，例如 复制，障碍同步， 对共享存储器失效以及分布式共享内存系统更新的支持等。

66 4.4.1 一般的多播路由算法 两个主要的多播路由参数是通信量和时间。
通信量是以将消息发送到所有的目标所需的通信链接的数目来衡量的。 时间就是消息传送的时间。 当两个多播路由算法有相同的时间步数时，应该选择具有较小的通信量步数的那一个。 通信量可以通过不同的目标共享链接来降低。

67 4.4.1 一般的多播路由算法： 多播优化问题 通常，多播存在下列四个优化问题： 一个最优的多播路径是一个包括所有目标的最短路径。
1）多播路径优化问题 一个最优的多播路径是一个包括所有目标的最短路径。 2）多播回路优化问题 最优多播回路是包含所有目标的最短长度的回路。

68 4.4.1 一般的多播路由算法： 多播优化问题（ cont'd ）
3）steiner树优化问题 一个包含所有目标节点的给定拓扑的一个子树 最小steiner树具有最小的总长度 注意：不一定每个通向目标的路径长度都是最短的。 4）多播树优化问题 一个包含所有目标的给定拓扑的子树，且树中每个通向目标的路径的长度对于给定的拓扑是最小的。 一个最优的多播树具有最小的通信量

69 4.4.1 一般的多播路由算法： 多播优化问题（ cont'd）
不幸的是，对网格和超立方的多播优化问题都是NP完全问题。因此，一般使用启发式多播算法。 目前，已有人给出了在使用分割-通过路由技术(如虫孔路由)的网络中进行最优化多播通信的充分条件。 本节考虑两种算法：一个是基于路径的；另一个是基于树的。

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

71 4.4.2基于路径的多播路由算法： 主要步骤 在给定的网格或超立方上建立哈密尔顿回路； 将哈密尔顿回路上的节点排序。 对每个中间节点，
这个顺序起始于源节点，并包括所有目标节点。 这样哈密尔顿回路就被分割成了哈密尔顿路径； 对每个中间节点， 若它是一个目标节点， 保留消息的一个拷贝，删除该目标节点的地址。 将消息和目标列表传给一个邻居。 这个邻居必须在当前节点之前（按顺序)，离下一个目标最近，且仍在这个目标之前(或就是这个目标)。

72 4.4.2基于路径的多播路由算法： 哈密尔顿路径 若使用双向链接，则只需一个哈密尔顿路径(而不是哈密尔顿回路)即可。
哈密尔顿路径为系统中的所有节点定义了一个顺序。 在整个顺序中，每个节点(x, y)都被赋予一个数字r：

73 4.4.2基于路径的多播路由算法： 哈密尔顿路径举例
例如，一个4×4的网格上每个节点具有的r值如图所示： n=4 若y是偶数，r值沿X方向递增 r(x, y)=yn+x 若y是奇数，r值沿X方向递减 r(x, y)=yn+n-x-1 =yn+(n-1)-x 偶数 奇数

74 4.4.2基于路径的多播路由算法： 哈密尔顿路径定义
两个节点在路径中相邻当且仅当|r(v)-r(u)|=1 例如： 4×4网格中，使用红粗线连接两个节点相邻

75 4.4.2基于路径的多播路由算法： 低信道网络和高信道网络
使用顺序定义，整个网格可以分成两个子网： 一个包括从低序节点到高序节点的链接； 另一个包括从高序节点到低序节点的链接。 在两个子网中，除了哈密尔顿路径上的链接以外，其它链接也包含在其中。

76 4.4.2基于路径的多播路由算法： 最短路径路由函数
目标依据它们与源的相对位置也分为两个子集。 一个子集将沿着高信道网络传送， 另外一个将沿着低信道网络传送。 为了将消息沿着最短路径传送，定义如下路由函数。 假定使用高信道网络。 v和d（r(v)<r(d)）分别是中间节点和目标节点。 若d是v的一个邻居，那么消息将直接转发到d； 否则，选择一个满足下式的v的邻居u：

77 4.4.2基于路径的多播路由算法： 举例 下图显示了一个在4X4网格中进行多播的例子 哈密尔顿路径连接了那些r值依次递增的节点
假定节点6(地址为(1,1))为源节点，目标节点为0、2、10、13和14。 紫色：源节点； 蓝色：目标节点

78 4.4.2基于路径的多播路由算法： 举例（ cont'd ）
显然，转发消息到节点0和2时，应该使用低信道网络。 依据路由函数，可以得到如下路径： 同样，转发消息到节点10，13和14时应使用高信道网络 红色：低信道网络路径和 具有最小r值的邻居 深紫色：高信道网络路径和 具有最大r值的邻居

79 4.4.3基于树的多播路由算法 Lan的贪婪多播算法可以应用于超立方。在这个算法中，
每个节点(包括源节点)在收到包含目标节点地址列表的消息后，就把自己的地址和目标节点的地址相比较。 若发现匹配，消息的一个拷贝将被送往本地的处理器 若多播集合非空，当前节点将决定把目标列表中的地址转发到哪些邻居。

80 4.4.3基于树的多播路由算法： 根据维度顺序进行转发
维度顺序由目标节点的相对地址来决定 n位地址的每一位都有一个计数器。 计数器的内容代表相应维度的信息。 具有最大计数值的那一维将被选中。 所有在这一位为1的目标将被转发到这一维上的那个邻居 在剩余的目标中，将利用下一个被选中的维度重复上述步骤。 当剩余的多播集合为空时，这一过程就结束。

81 4.4.3基于树的多播路由算法： 4维立方中的多播例子
考虑一个4维立方体（目标用蓝色节点代表） 节点0010打算向组播集 {0000，0001，1001，1100，1110} 中的每个节点发送消息 所有目标节点的实际地址和源节点0010 的实际地址做异或操作，得到 多播集合的相对地址 {0010，0011，1011， 1110，1100}。 每一列的1的数目组成 了一个称为列总和的 向量(3, 2, 4, 2)

82 4.4.3基于树的多播路由算法： 4维立方中多播例子（ cont'd ）
沿着第2维的邻居拥有最受欢迎的维度。即节点0000成为下一个转发节点，发往节点0000的消息包含子集(0000，0001，1001，1100)。 只有节点1110被剩下了，这个节点可以通过第3维的邻居转发，也可以通过第4维的邻居转发。 上述过程将在每个转发节点重复操作。 每个多播树的分支都将继续到剩余的 多播集合变空为止

83 4.4.3基于树的多播路由算法： 基于递归倍增的启发式算法
当使用分割-通过网络时，可以使用递归倍增方法构造启发式算法。 以单端口模型下的2维网格为例来说明McKinIey等人提出的u-网格算法。 先为2维网格的节点地址定义一个字典序(<t)，即 若x1<tx2或者x1=x2,但y1<ty2，则有(x1,y1)<(x2,y2)。 边分离性质： 假定P(n1,n2)是n1和n2间最短路径，易知， 若n1<tn2<tn3<tn4，则P(n1,n2)和P(n3,n4)边分离

84 4.4.3基于树的多播路由算法： 基于递归倍增的启发式算法
利用边分离性质，可建立下面避免竞争且具有最少步数的多播算法 假定源节点是(0,0)，按照字典顺序重新排列目标节点、并将源节点放在前面。 将列表分成两个相等的子列表。源节点将多播消息发往第二个子列表的第一个节点。 重复上述分割步骤直到每个子列表中只有一个节点； 若源节点不是(0,0)，可重新定义排列顺序以便源节点成为第一个节点

85 4.4.3基于树的多播路由算法： 举例 考虑一个4×4网格，(0,0)是源节点，(1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和(3,2)是目标节点。 源节点和目标节点的字典顺序是：(0,0),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和(3,2)

86 4.4.3基于树的多播路由算法： 举例（ cont'd ）
第一步，这个列表被分成两个子列表{(0,0),(1,0),(1,1),(1,2)}和{(1,3),(2,0),(2,1),(3,2)} 源(0,0)将信息发送到第二个子列表的第一个节点(1,3) 使用XY路由建立(0,0)到(1,3)的路由路径

87 4.4.3基于树的多播路由算法： 举例（ cont'd ）
在每个子列表上重复上述过程，有：

88 本课小结 本课主要内容（4小节） 分布式路由算法导论 一般类型网络的最短路径路由算法 进程间通信类型 通信延迟及其原因 路由算法分类
路由函数定义 一般类型网络的最短路径路由算法 Dijkstra集中式算法 Ford分布式算法 ARPAnet的路由算法

89 特殊类型网络的单播算法 特殊类型网络中的多播算法 双向环上的单播算法及其一般化 网格和圆环上的单播算法 超立方 基于（哈密尔顿）路径
2维网格的XY路由、适应性路由、折线路由等 超立方 基于海明距离的一种简单的路由算法 特殊类型网络中的多播算法 基于（哈密尔顿）路径 基于树的多播 应用于超立方的Lan的贪婪多播算法 U-网格算法