分布式路由算法

(并行与分布式计算十)

分布式路由算法导论

进程间通信类型

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

通信延迟及其原因

在基于消息传递的分布式系统中，消息一般在到达目标节点之前可能要通过一个或多个中间节点，故存在通信延迟。

分布式系统中的通信延迟依赖于如下四个因素：
- 网络拓扑：
- - 通常用图表示
- - 定义处理单元（PE）之间是如何连接的
路由
- 决定如何选择路径以便将消息传递到目的地。
流量控制
- 流量控制决定在消息沿路径传递时如何分配网络资源，包括：
- - 信道
- - 缓冲区
交换
- 这是一个实际的机制，它决定消息如何从一个输人信道转到一个输出信道。

路由算法类型

路由算法类型包括：

特殊 vs. 一般
最短 vs. 非最短
确定型 vs. 适应型
容错型 vs. 非容错型
冗余型 vs. 非冗余型
死锁避免型 vs. 非死锁避免型

一般型路由和特殊型路由

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

最短路由算法和非最短路由算法

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

确定型路由和适应型路由

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

容错型路由和非容错型路由

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

冗余型路由和非冗余路由

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

死锁避免型路由

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

路由函数

路由函数
- 定义一个消息如何从源节点路由到目标节点。
- 每个PE在收到一个消息以后，都将决定：
- - 1）把这条消息传送到本地存储器，还是
- - 2）转发到一个邻接的PE

有许多不同的路由函数的定义，例如依赖于目标的、依赖于输入的、依赖于源的、依赖于路径的等等

这里介绍的仅使用依赖于目标的路由函数

一般类型网络的最短路径路由算法

许多分组交换网，如法国的Transpac或美国的ARPAnet都使用最短路径路由

介绍三个一般类型网络的最短路径路由算法：

Dijkstra集中式算法
Ford分布式算法
ARPAnet路由算法

分布式系统图示

一般地，一个分布式系统可以用图来表示：

节点代表PE（处理单元）
边代表通信链接
每个链接的数字代表链接代价

Dijkstra集中式算法

第一种类型的算法以集中式的风格进行路由
Dijkstra集中式算法可以发现一个源节点到所有其他节点的最短路径。
Dijkstra集中式算法需求：
- 需要了解给定网络的全局拓扑消息，即：
- - 网络中所有其他节点的列表
- - 节点之间的所有链接
- - 每个链接的代价

算法描述

设D(v)是从源s到节点v的距离(沿给定路径的链接的代价的和), l(v,w)是节点v和w之间的代价
1.设N={s}；对不在N中的每一个节点v，令D(v)=l(s,v)。对那些没有连接到s的节点赋值为 $\infty$
2.找到不在N中的一个节点w，使D(w)最小并将w加入N；然后对所有不在N中的其它节点计算并更新D(v)： D(v) := min[D(v), D(w)+l(w,v)]
重复步骤2，直到所有节点都在N中

算法举例

上述算法作用于如图所示的网络：以P5为源节点

1.集合N只包含源节点P5即N = { P5 }。
- 对不在N中的节点P1,P2,P3,P4计算：
- D(1)=D(2)= $\infty$ (由于P1和P2不与P5直接相连)
- D(3)=l(P5, P3) = 20
- D(4)=l(P5, P4)=2

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{$\infty$, 2+$\infty$}=$\infty$,
- D(2)=min{D(2), D(4)+l(4,2)} =min{$\infty$, 2+1}=3
- D(3)=min{D(3), D(4)+l(4,3)} =min{20, 2+2}=4

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{$\infty$,3+4}=7
- D(3)=min{D(3), D(2)+l(2,3)} =min{4, 3+3}=4

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

5.取D(1)中具有最小值的对应节点P1加入到集合N中, N= { P5,P4,P2,P3,P1}
- 此时，节点都在N中，算法结束

Ford分布式算法

第二种类型的路由算法采用分布式的方法进行路由
分布式算法: 每个节点在交互式的基础上和其邻节点交换代价和路由信息，直到这些节点的路由表到达最短路径的要求为止
Ford分布式算法也包括两个部分：
- 一个初始步骤
- 一个最短距离计算的步骤(最短距离指一个给定节点和目标节点之间的距离)
当所有节点都带有
1）一个表示它们到目标节点距离的标记以及
2）沿着最短路径到达目标节点要经过的下一个节点的标记时
算法结束

算法描述

每个节点v，都有(n,D(v))的标记。
- D(v)代表该节点到目标节点的最短距离的当前值；
- n是截至目前得到的最短路径的下一个节点。
初始步骤：
设d是目标节点, 令D(d)=0，将所有其它节点标记为(., $\infty$)
最短距离计算步骤：
对所有节点的最短路径做标记：
- 对每个节点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)
- - 对每个节点重复上述操作，直到不再有改变

举例

上述算法作用于如图所示的网络：以P5为目标节点

初始：令D(5) = 0，将其他节点P1,P2,P3,P4都标记为(., $\infty$)

1.对于P1，邻节点为P2,P3，由当前标记可知P2,P3距离P5都为$\infty$，则P1不能通过任何节点到达P5，P1仍标记为(., $\infty$)
同理，P2仍标记为(., $\infty$)
对于P3，邻节点为P1,P2,P4,P5，其中D(1)= D(2)=D(4)=$\infty$,D(5)=0
由于P3到P5的距离20+D(5)为20小于当前D(3)= $\infty$, 表明P3经P5有最短路径可达P5, 故P3标记为(P5, 20)
同理，P４标记为(P5, 2)

2.对于P1，邻节点为P2,P3，由当前标记可知P5距离P2为$\infty$，距离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)

4.按同样方法更新P1,P2,P3,P4的标记为： (P2,7),(P4,3),(P4,4),(P5,2)
由于此后再重复以上算法试图更新每一个节点的标记都不会改变其标记，算法结束

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

ARPAnet路由算法

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

举例说明

用ARPAnet路由算法时，P1，P2，P3，P4的一般路由表，仍以P5为目标节点
每个表格都包含通过每个邻居到达P5的最短距离
假设在时刻0前已经达到了一个稳定点, 网络延迟表如图

假设0时刻，P4与P5之间链接失效，则它更新它的路由延迟表，并传输给P4的所有邻节点，从而使那些节点的路由延迟表发生变化，直到产生一个新的稳定点

上述过程一直持续到达到一个新的稳定点，P1，P2，P3，P4分别用了20，19，17，20个时间间隔，如下图所示

ARPAnet路由算法中, 每个节点对所有邻居都发送相同消息，对接收节点不做任何标识。
这样，某些节点就会接收无用消息。
在链接节点失效时候，这些消息会导致我们不期望的循环。
例如, ，P4和P5链接失效时，P4的最短路径为4，但是这个4来自于P2，而P2到P5的最短路径原来就依赖于P4与P5的链接，由于P4使用P2的信息时，P2的信息尚未得到更新，导致出现不期望的循环：P4->P2->P4

不期望循环的消除

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

特殊类型网络的单播路由算法

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

双向环单播路由算法

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

算法一般化

双向环是k元1维立方，即只有一维度。
若维度大于1，例如网格和超立方，就用有序维度路由
- 每次将每个消息向一个维度路由
- 圆环：在一个维度中的各点以环的方式连接起来，带有周边连接
- 网格：一个维度中的各点以线性排列的形式连接起来，没有周边连接
环形路由方法可用于在一个维度中对消息进行路由。
- 沿着一个线性排列路由是很简单的。
- 当消息到达每个维度的对等者时，就使用下一个维度。
- 通过使经过的各个维度保持一个单调的顺序，就可以保证不会发生死锁。
- 但这种方法适应性差。

网格和圆环单播路由算法

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

2维网格的XY路由

在2维网格中，有序维度路由叫XY路由。
- 每个节点的地址为(x,y)。
- 消息首先沿着X维度转发，然后沿着Y维度路由。
- 特别地，若源和目标分别为(sx,sy)和(dx,dy)，则路由消息将在X维度上走|dx – sx| 步，然后在Y维度上走|dy– sy|步

最短且完全适应路由

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

适应性路由图示(只要dx–sx≠0且dy–sy≠0，每个节点在选择邻居时总有两个选择：X方向或者Y方向)

如果每个链接（信道）拥塞的概率是一样的，那么在最短路由的限制下，哪一个是最好的路由方法呢
这里的最好是指在这种路由方法下，消息到达目标的延迟最小。

折线路由

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

在2维圆环中，折线路由可能不是最优的，因为一个中间节点可能有多于两个的合格邻居。
特别，对一个n为偶数的n*n的圆环，存在一个具有四个合格邻居的节点。而且，有2(n-2)个节点，它们和源的距离为n／2个行或列，因此，在最短路径上就有多个方向。
对于最优解，Wu在k元M维立方的最短路径路由算法的基础上提出了一个最大最短路径(MP)路由算法：路由消息总是被转发到与目标节点存在最大个数的最短路径的那个邻居节点。
基于最大最短路径的路由算法是一个对2维网格和M维立方都是最优的路由算法。
然而，关于最大最短路径对2维圆环是不是最优的仍然是一个未决的问题。
若源和目标都有四个邻居，那么很容易在它们之间建立四个边(或点)分离的路径，如图。
一般地，设k(k<=4)是源和目标节点所具有的最小的邻居的数目，那么，在源和目标之间就存在k个边〔点〕分离的路径。

超立方单播路由算法

对超立方的单播路由可采用一种相对简单的方法，不必在每个节点中存储路由延迟表。
一个n维超立方（n-cube）可定义为：
- Q0，是一个只有一个节点的退化图
- $Q_n＝K2 x Q{n-1}$, 这里：$K_2$是具有两个节点的完全图；x是两个图的笛卡尔乘积。
- Qn中的一个节点的地址可以表示为$ u = un u{n-1}…u_1(u_i＝0/1, 1<=i<=n) $

海明距离

两个节点$u=u_n u{n-1}…u_1$和$w=w_n w{n-1}…w1$间最短路径长度就是u和w间的海明距离，表示为H(u,w)。
$$ H(u, w) = \sum{i=1}^{n}h(u_i, w_i),
h(u_i,w_i)=\begin{cases}
1&\text{if $u_i \not= w_i$},\
0&\text{if $u_i = w_i$}.
\end{cases}
$$
u和w间的异或操作$u \oplus w＝rn r{n-1}… r_1$定义为：
- 如果$u_i＝w_i$，则$r_i＝0$
- 如果$u_i \not= w_i$，则$r_i＝1,1<=i<=n$
显然，H(u,w)等于$u \oplus w$中1的个数
u(i)表示改变u的第i位(也叫维)．例如1101(3)=1001

超立方路由

在超立方路由中
- 当前节点u和目标节点w的相对地址为$w_i \oplus u_i$，它和将要发送到下一个节点(这个节点也叫转发节点)的消息一起传送
- 在每个跳步，相对距离都会通过将$w_i \oplus u_i$中的一个1替换而进行更新
在下面的算法中，节点u是当前节点(可以是源节点)，节点w是目标节点。

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

一个3维立方路由的例子

例中：源节点u=000目标节点w＝110。从点000到点110有下列三个点分离路径：

路径1（红色）：000$\to$100$\to$110
路径2（蓝色）：000$\to$010$\to$110
路径3（绿色）：000$\to$001$\to$011$\to$111$\to$110

超立方多路径路由的性质

超立方多路径路由具有如下性质：若两个节点u和w在n维立方中的海明距离是k, 则在u和w之间就有n个点分离路径。在这n条路径中，有k个路径长度为k，其余n-k个路径长度为k+2
000和110之间的距离|000$\oplus$110|＝2。因此，上述路径中有两条长度为2，一条长度为4
路径1（红色）：000$\to$100$\to$110
路径2（蓝色）：000$\to$010$\to$110
路径3（绿色）：000$\to$001$\to$011$\to$111$\to$110
类似地．000和100之间的三条点分离路径为：
路径1（红色）：000$\to$100
路径2（绿色）：000$\to$001$\to$101$\to$100
路径3（蓝色）：000$\to$010$\to$110$\to$100
000和100之间的海明距离|000$\oplus$100|=1

特殊类型网络的多播路由算法

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

一般的多播路由算法

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

多播优化问题

通常，多播存在下列四个优化问题：
- 多播路径优化问题: 一个最优的多播路径是一个包括所有目标的最短路径。
- 多播回路优化问题: 最优多播回路是包含所有目标的最短长度的回路。
steiner树优化问题
- 一个包含所有目标节点的给定拓扑的一个子树
- 最小steiner树具有最小的总长度
- 注意：不一定每个通向目标的路径长度都是最短的。
多播树优化问题
- 一个包含所有目标的给定拓扑的子树，且树中每个通向目标的路径的长度对于给定的拓扑是最小的。
- 一个最优的多播树具有最小的通信量
不幸的是，对网格和超立方的多播优化问题都是NP完全问题。因此，一般使用启发式多播算法。
目前，已有人给出了在使用分割-通过路由技术(如虫孔路由)的网络中进行最优化多播通信的充分条件。
考虑两种算法：一个是基于路径的；另一个是基于树的。

基于路径的多播路由算法

基本思想：
- 首先建立一个哈密尔顿回路，
- 然后根据这个回路把多播集合转发出去。
- 如果有一个邻居位于目标前面，但距离目标更近，那么就可以抄近路。

1895年，爱尔兰数学家哈密尔顿首先提出“环球周游”问题。他用一个正十二面体的20个顶点代表世界上20个城市，要求旅游者能否找到沿着正十二面体的棱，从某一个顶点（即城市）出发，经过每一个顶点（即每一座城市）恰好一次，然后回到出发顶点？这便是著名的哈密尔顿问题。它的解称为哈密尔顿回路。

主要步骤:

在给定的网格或超立方上建立哈密尔顿回路；
将哈密尔顿回路上的节点排序。
- 这个顺序起始于源节点，并包括所有目标节点。
- 这样哈密尔顿回路就被分割成了哈密尔顿路径；
对每个中间节点，
- 若它是一个目标节点，
- - 保留消息的一个拷贝，删除该目标节点的地址。
- - 将消息和目标列表传给一个邻居。这个邻居必须在当前节点之前（按顺序)，离下一个目标最近，且仍在这个目标之前(或就是这个目标)。
若使用双向链接，则只需一个哈密尔顿路径(而不是哈密尔顿回路)即可。
哈密尔顿路径为系统中的所有节点定义了一个顺序。
在整个顺序中，每个节点(x,y)都被赋予一个数字r：
$$
r(x, y)=\begin{cases}
yn+x&\text{if y is even}\
yn+n-x-1&\text{if y is odd}
\end{cases}
$$
例如，一个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