高级操作系统 Advanced Operating System 熊焰 yxiong@ustc.edu.cn 0551_3607394 中国科学技术大学计算机系

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

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

第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 5/7/2019 Advanced Operating System

一、进程间通信类型 二、通信延迟及其原因 四、路由函数 三、路由算法类型 5/7/2019 Advanced Operating System

3.1分布式路由算法导论 一、进程间通信类型 有效的进程间通信对分布式系统的性能很重要 根据目标个数的不同，本章讨论的进程间通信 的类型有： 一对一（单播） 一对多（组播） 一对所有（广播） 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 二、通信延迟及其原因 在基于消息传递的分布式系统中，消息一般在 到达目标节点之前可能要通过一个或多个中间 节点，故存在通信延迟。 分布式系统中的通信延迟依赖于如下四个因素： 网络拓扑、路由、流量控制、交换 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 1、网络拓扑，也叫互连网络 通常用图表示，定义处理单 元（PE）之间是如何连接的 分类 特殊类型的网络使用 k元n维立方表示 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 2、路由 决定如何选择路径以便将消息传递到目的地。 本章主要考虑路由 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 3、流量控制 流量控制决定在消息沿路径传递时如何分配网络资 源 网络资源包括： 信道 缓冲区 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 二、通信延迟及其原因（cont'd） 4、交换技术 这是一个实际的机制，它决定消息如何从一个输入信 道转到一个输出信道。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 三、路由算法类型 路由算法类型包括： 特殊 vs. 一般 最短 vs. 非最短 确定型 vs. 适应型 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 1、一般型路由和特殊型路由 一般型路由算法 适合于所有类型的网络 但是对于某种特定网络不是很有效 特殊型路由算法 只对特定的网络类型有效，如超立方、网格等 这些算法由于利用了特定网络的拓扑属性，所以效 率往往较高。 5/7/2019 Advanced Operating System

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

3.1分布式路由算法导论： 3、确定型路由和适应型路由 确定型路径算法（静态） 路由路径只在网络的拓扑发生改变时才发生变化 而且不使用任何有关网络状态的消息。 适应型路由算法（动态） 路径根据网络流量而改变。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 5、容错型路由和非容错型路由 容错型路由算法 即使出现错误，被路由消息也能保证送到。 非容错型路由算法 假定路由不会出错 路由算法不必动态调整自己的活动。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 6、冗余型路由和非冗余路由 冗余型路由算法 用几个边分离（或节点分离）的路径向同一个目标 发送多个拷贝。 只要这些路径中的一个是好的，则至少有一个消息 拷贝能到达目标。 必须保证有且只有一个拷贝被接收 非冗余型路由算法 对每个目标只需转发消息的一个拷贝。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 7、死锁避免型路由和非死锁避免型路由 3.1分布式路由算法导论： 7、死锁避免型路由和非死锁避免型路由 死锁避免型路由算法 通过仔细设计的路由算法，保证不发生死锁。 非死锁避免型路由算法 没有特别的设施来预防或避免死锁。 可能发生死锁，也可能不发生死锁。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论： 四、路由函数 路由函数定义一个消息如何从源节点路由到目标节点 有许多不同的路由函数的定义，例如 每个PE在收到一个消息以后，都将决定： 1）把这条消息传送到本地存储器，还是 2）转发到一个邻接的PE 有许多不同的路由函数的定义，例如 依赖于目标的、依赖于输入的、依赖于源的、依赖于路径的 等等 一般而言，路由函数参考的信息越多，效果可能就越好 本章仅使用依赖于目标的路由函数 仅仅依赖于当前和目标节点 依赖于当前、目标节点，以及输入的邻接节点 依赖于目标节点和从源节点到当前节点的路径 依赖于源、当前、目标节点 5/7/2019 Advanced Operating System

第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 5/7/2019 Advanced Operating System

3.2 一般类型网络的最短路径路由算法 许多分组交换网，如法国的Transpac或美国 的ARPAnet都使用最短路径路由 这里介绍三个一般类型网络的最短路径路由 算法： Dijkstra集中式算法 Ford分布式算法 ARPAnet路由算法 5/7/2019 Advanced Operating System

3.2 一般类型网络的最短路径路由算法： 预备、分布式系统图示 一般地，一个分布式系统可以用图来表示： 节点代表PE（处理单元）； 边代表通信链接； 每个链接的数字代表链接代价。 例： 5/7/2019 Advanced Operating System

三个一般类型网络的最短路径路由算法： Dijkstra集中式算法 Ford分布式算法 ARPAnet路由算法 5/7/2019 Advanced Operating System

3.2.1 Dijkstra集中式算法 第一种类型的算法以集中式的风格进行路由 需要了解给定网络的全局拓扑消息，即： 1、网络中所有其它节点的列表； 2、节点之间的所有链接； 3、每个链接的代价。 5/7/2019 Advanced Operating System

3.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； 然后对所有不在N中的其它节点计算并更新D(v)： D(v) := min[D(v), D(w)+l(w,v)] 重复步骤2，直到所有节点都在N中 即与s相邻的节点 N N D(w) w s ? 5/7/2019 Advanced Operating System D(v) v

3.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 = ∞  =2 = ∞ 5/7/2019 Advanced Operating System =20

3.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。   =∞ =3 =2 =∞ 5/7/2019 Advanced Operating System  =20 =4

3.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。 =3 =2  =∞ =7 5/7/2019 Advanced Operating System  =4

3.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 =3 =2 =7  5/7/2019 Advanced Operating System =4

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

3.2.1 Dijkstra集中式算法： 连续的步骤，如下表： 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法 第二种类型的路由算法采用分散式的方法进行 路由 分布式算法 每个节点和其邻节点交换代价和路由信息，直到这 些节点的路由表到达最短路径的要求为止 5/7/2019 Advanced Operating System

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

3.2.2Ford分布式算法： 一、算法描述 每个节点v，都有(n,D(v))的标记。 初始步骤： 令D(d)=0，将所有其它节点标记为(.,∞) 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法： 一、算法描述（cont'd） 最短距离计算步骤： 对所有节点的最短路径做标记： 对每个节点v≠d： 考虑v的每个邻节点w，根据当前D(w)， 计算D(w)+l(w, v)，令 D(v):=min{D(v),D(w)+l(w,v)} 更新v的标记：用使上述表达式取值最小的邻 接节点代替n，并用新值代替D(v)。 对每个节点重复上述操作，直到不再有改变 5/7/2019 Advanced Operating System

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

3.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)。 5/7/2019 Advanced Operating System

3.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) 5/7/2019 Advanced Operating System

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

3.2.2Ford分布式算法： 举例小结 (P4,3) (.,∞) (P3,25) (.,∞) (P2,7) (.,0) (P5,2) 5/7/2019 Advanced Operating System (P4,4) (.,∞) (P5,20)

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

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

3.2.3 ARPAnet路由算法： 举例 P1 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 想一想，从每个节点的路由表上，可以看出最短路由的问题么？ 5/7/2019 Advanced Operating System

3.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 5/7/2019 Advanced Operating System

3.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 …… 5/7/2019 Advanced Operating System

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

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

3.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 5/7/2019 Advanced Operating System

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

第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 5/7/2019 Advanced Operating System

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

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

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

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

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

3.3.2 网格和圆环单播路由算法 网格和圆环是k元2维立方。 类似地，3维网格和圆环是k元3维立方。 本小节介绍 圆环有周边邻接， 网格没有周边连接。 类似地，3维网格和圆环是k元3维立方。 本小节介绍 1、2维网格的XY路由 2、最短且完全适应路由 3、折线路由 4、最大最短路径路由 5/7/2019 Advanced Operating System

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

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

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

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

3.3.2 网格和圆环单播路由算法： 折线路由（ cont'd ） 在2维圆环中，折线路由可能不是最优的，因为 一个中间节点可能有多于两个的合格邻居。 5/7/2019 Advanced Operating System

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

3.3.2 网格和圆环单播路由算法 关于边（点）分离路经 若源和目标都有四个邻居， 那么很容易在它们之间建立 四个边(或点)分离的路径。 一般地，设k(k≤4)是源和目 标节点所具有的最小的邻居 的数目，那么，在源和目标 之间就存在k个边〔点〕分离 的路径。 5/7/2019 Advanced Operating System

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

3.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。 u=unun-1…u1 w=wnwn-1…w1 5/7/2019 Advanced Operating System

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

3.3.3 超立方单播路由算法： 二、超立方路由（ cont'd ） 在下面的算法中，节点u是当前节点(可以是源节点)， 节点w是目标节点。 一个节点，或者开始一次路由， 或者收到一个消息 根据相对地址， 选中存在差异的那一维 将消息发送给这个维度上对等的节点 发送给本节点的？ 根据相对地址， 选中存在差异的那一维 将消息发送给这个维度上对等的节点 5/7/2019 Advanced Operating System

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

3.3.3 超立方单播路由算法： 三、一个3维立方路由的例子 例中：源节点u=000目标节点w＝110。 从点000到点110有下列三个点分离路径： 路径1（红色）：000100110 路径2（蓝色）：000010110 路径3（绿色）：000001011111110 最短 5/7/2019 Advanced Operating System

3.3.3 超立方单播路由算法： 四、超立方多路径路由的性质 超立方多路径路由具有如下性质： 若两个节点u和w在n维立方中的海明距离是k． 则，在u和w之间就有n个点分离路径。 在这n条路径中，有k个路径长度为k， 其余n-k个路径长度为k+2。 例如上一页中， 000和110之间的距离|000⊕110|＝2。 因此，上述路径中有两条长度为2，一条长度4 5/7/2019 Advanced Operating System

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

第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 5/7/2019 Advanced Operating System

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

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

3.4.1 一般的多播路由算法： 一、多播优化问题 通常，多播存在下列四个优化问题： 一个最优的多播路径是一个包括所有目标的 最短路径。 1、多播路径优化问题 一个最优的多播路径是一个包括所有目标的 最短路径。 2、多播回路优化问题 最优多播回路是包含所有目标的最短长度的 回路。 5/7/2019 Advanced Operating System

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

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

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

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

3.4.2基于路径的多播路由算法： 三、哈密尔顿路径 若使用双向链接，则只需一个哈密尔顿路径 (而不是哈密尔顿回路)即可。 哈密尔顿路径为系统（n×n的网格）中的所有 节点定义了一个顺序。 在整个顺序中，每个节点(x,y)都被赋予一个数字r： 自上而下排序 自下而上排序 x代表第x行； y代表第y列 5/7/2019 Advanced Operating System

3.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)-x 5/7/2019 Advanced Operating System

3.4.2基于路径的多播路由算法： 五、哈密尔顿路径定义 两个节点在路径中相邻当且仅当|r(v)-r(u)|=1 例如： 4X4网格中，使用粗线连接两个相邻节点 5/7/2019 Advanced Operating System

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

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

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

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

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

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

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

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

3.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)边分离 5/7/2019 Advanced Operating System

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

3.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) 5/7/2019 Advanced Operating System

3.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)的路由路径 5/7/2019 Advanced Operating System

3.4.3基于树的多播路由算法： 举例（ cont'd ） 在每个子列表上重复上述 过程，有： 5/7/2019 Advanced Operating System

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

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