【论文阅读】互连网络的负载平衡路由算法 (CQR, Channel Queue Routing 通道队列路由)

时间：2024-04-29 11:14:50
  • Channel Queue Routing (CQR) 通道队列路由
    • 1. Channel Queue Routing (CQR) 的动机
      • (1) 排队论(queueing theory)模型
      • (2) GAL’s latency on tornado traffic
      • (3) Routing tornado traffic with CQR
    • 2. Channel Queue Routing 通道队列路由
    • 3. CQR 的性能
    • 4. 总结

Channel Queue Routing (CQR) 通道队列路由

A. Singh. Load-Balanced Routing in Interconnection Networks.PhD thesis, Stanford University, 2005.

总结自 A. Singh 的博士毕业论文 —— Load-Balanced Routing in Interconnection Networks

1. Channel Queue Routing (CQR) 的动机

对于对抗性流量模式，自适应路由算法的重点必须随着负载的增加而改变。在低负载时，应尽量减少数据包的路由，以最大限度地减少延迟。随着负载的增加，最小化延迟需要将一些数据包转移到非最小路由，以平衡信道负载。在本节推导了 8-node ring 网络拓扑龙卷风流量模式的最佳自适应路由算法，并将其与 GAL 的性能进行比较。

虽然 GAL 在非常低的负载和接近饱和的负载下都匹配此最佳算法，但它在中间负载下从最小到非最小路由的转换太慢，导致延迟大约比最佳性能多 100 周期。这代表了 GAL 在所有对抗模式上的表现，因为它只能在超过阈值即网络延迟已经很大的情况下才会进行非最小路由。为了了解龙卷风流量应如何路由以获得最佳延迟，我们提出了排队论(queueing theory)的近似理论模型。

(1) 排队论(queueing theory)模型

对于排队模型，我们假设每个队列都是一个独立的 M/D/1 的队列，并且具有到达率 a 和服务率 1。此类队列中数据包的排队延迟由为：
在这里插入图片描述

如果数据包穿过“此类队列”的线性网络，则会因“队列和跳跃延迟”而产生排队延迟。其总延迟近似为：
在这里插入图片描述

当以最佳路由处理 TOR 时，有两类数据包 — 最小路由的数据包和沿非最小路径发送的数据包。令每个节点的注入负载为 a ，每个节点最小和非最小发送数据包的速率分别为 x1 和 x2。然后，低于饱和度时：
在这里插入图片描述

以最少(非最少)路由发送的数据包必须遍历 3(5) 个 M/D/1 队列，且每个队列的到达率为 3a(5a)。 因此，最小路由的数据包的延迟由下式给出：
在这里插入图片描述

非最小路由数据包的延迟由下式给出：
在这里插入图片描述

那么平均延迟就是这些延迟的加权和：
在这里插入图片描述

综上得到最佳性能的最小非最小流量比例，对于8节点环上的龙卷风流量：
在这里插入图片描述

证明 ：对于最小延迟，每个节点应该沿着最小路径发送所有流量，直到最小路由的增量延迟大于非最小路由的增量延迟。路由将严格最小化：
在这里插入图片描述

求解方程 5.5，得到 a<=0.13。因此，从严格最小到非最小的切换点发生在 as = 0.13。一旦每个节点开始发送非最小化流量( a > as)，最小化 (x1) 和非最小化 (x2) 发送的负载的最佳比例将使得沿任一方向的增量延迟相同：
在这里插入图片描述

求解方程 5.6、5.1 得出 x1 = (a+as)/2 for a > as。最后，当网络在 a=0.53 饱和后，x1=0.33 和 x2=0.2。沿最小和非最小路径的可接受吞吐量图如图 5.12 所示。
在这里插入图片描述

将 x1 和 x2 的值代入方程 5.2、5.3 和 5.4，我们根据模型得到数据包的平均最小延迟、非最小延迟和总体延迟。如图 5.13 所示，两条路径的平均延迟相似，总体平均延迟较低。
在这里插入图片描述

(2) GAL’s latency on tornado traffic

如果与数据包目的地关联的最小注入队列的占用率低于阈值，GAL 会最小化路由数据包。否则，超过阈值，数据包将被注入非最小注入队列并进行非最小路由。

通过这种方法，GAL 最小化路由数据包，直到沿最小路径的容量饱和。并且路由从严格最小注入切换到非最小注入队列。直到最小路径上的所有队列都完全填满时，才会发生这种切换，如图 5.14 所示。因此，发生此切换的负载只是龙卷风模式的严格最小路由的饱和负载，由 as = 0.33 给出。尽管饱和时可接受的吞吐量仍然是最优值 0.53。

在这里插入图片描述

然而，需要注意的一点是，虽然 GAL 路由在龙卷风模式下是吞吐量最优的，但就延迟而言，从严格最小到非最小的切换延迟会带来高昂的代价。

在这里插入图片描述

图 5.15 显示了 GAL 的平均最小、非最小和总体数据包延迟。由于 GAL 一直以最小路由方式到达严格最小路由的饱和点，因此负载后最小数据包所产生的延迟非常高。这导致平均总体数据包延迟(最小延迟和非最小延迟的加权平均值)在网络饱和点之前达到 100 个周期的数量级。

(3) Routing tornado traffic with CQR

可以观察到 GAL 在 tornado 流量上表现如此差的原因是它等待太长时间才能将其策略从严格最小化切换到非最小化。这样做是因为它的拥塞感知机制使用注入队列的占用情况，而这对网络拥塞的响应不是很灵敏。CQR 通过使用其通道队列感知网络负载不平衡来解决这个问题，同时依靠网络的隐式背压从网络的其他部分收集近似的全局信息。

在这里插入图片描述

考虑图 5.16 中突出显示的节点2。对于龙卷风流量模式，该节点的最小和非最小队列分别是顺时针和逆时针输出队列。这两个队列的瞬时占用率被标记为 qm 和 qnm 。如果最小路由(非最小路由)，数据包将遍历3(5)个队列，每个队列都有占用 qm(qnm) (此处将全局拥塞信息都默认为本地输出队列的拥塞信息)。为了保持两个方向上的延迟平衡，CQR 最小路由只要 3xqm <= 5xqnm，否则它是非最小路由。这种拥塞感知方案比 GAL 中使用的方案响应更快，因为与 GAL 不同的是切换发生在所有最小队列被填满之前，如图 5.16 所示。我们将这种路由方法称为通道队列路由(Channel Queue Routing, CQR) [1]。

2. Channel Queue Routing 通道队列路由

与 GAL 一样，CQR 自适应地选择一个象限来为每个数据包路由。假设源节点为 s={s1,s2,…,sn} ，目标节点为 d={d1,d2,…,dn} ，其中 xi 是节点 x 在维度 i 中的坐标。我们计算一个最小方向向量 r = {r1,r2,…,rn} ，其中对于每个维度 i ，如果短方向是顺时针方向增加节点索引我们选择 ri 是 +1，如果短方向是逆时针方向选择 ri 是 -1。选择要路由的象限也意味着选择一个象限向量，其中对于每个不匹配的维度 QRi，如果我们想要在该维度中最小(非最小)路由，我们可以选择 QRi = ri ( QRi = -ri )。

为了像一维情况一样获得近似象限拥塞信息，每个节点在每个维度上沿两个方向 (+ 和 -) 记录其输出通道队列的瞬时占用情况。然后象限 j 的拥塞信息 Qj，可通过该象限的最短输出队列的长度来近似(选择该象限所有方向中的最短输出队列)。如果 Qj 的跳数为 Hj，则大约为数据包产生的延
迟为 HjQj。为了平衡所有象限的延迟，我们必须使所有象限 j 的 HjQj 相等。因此 CQR 选择最小值 HjQj 对应的象限。

举例来说，图 5.19 显示了 8-ary 2-cube 网络的一部分。源 (0,0) 想要将数据包路由到目标节点 (2,3)。对于这个源-目的地对，有4个象限Q1(++)、Q2(±) 、Q3(-+) 、Q4(–) 的选择，其中跳数分别为 5、 8、 9 和 11。源节点记录每个输出通道的占用情况 qa、qb、qc、qd。最小象限Q1的拥塞情况近似为 min(qa,qb)。类似地，象限 Q2 、Q3 和 Q4 的拥塞情况分别由 min(qa,qd)、min(qb,qc) 和 min(qc,qd) 来近似。CQR 选择跳数-拥塞积最小的对应的象限，即 5Q1、8Q2、9Q3、11Q4 中最小值对应的象限。
在这里插入图片描述

一旦选择了象限，数据包就会使用 VC 在该象限内自适应路由，方式与 GOAL 和 GAL 中的方式相同。

3. CQR 的性能

CQR 能够在所有品质因数上与 GAL 的性能(吞吐量和延迟)完全匹配。与 GAL（具有固定阈值）不同，CQR 在饱和后是稳定的，因为它使用通道队列而不是注入队列来做出路由决策。由于饱和后注入负载导致的拥塞仍然保留在源队列中，因此 CQR 不会混淆由于负载不平衡和注入负载超过饱和而导致的拥塞。因此，即使在提供的负载超过饱和之后，接受的吞吐量仍保持平稳，如图 5.20 所示。应与GOAL中的最短输出队列一致。

在这里插入图片描述

CQR 相对于 GAL 的最大改进是，在中间负载时，对于需要算法非最小路由以获得最佳吞吐量的流量模式，它以比 GAL 低得多的延迟交付数据包。当必须使用非最小路径来提供更高的系统吞吐量时，对于接近饱和的注入负载，这种效果更加明显。
在这里插入图片描述

4. 总结

总而言之，CQR 感知近似全局拥塞，并使用通道队列拥塞做出自适应全局路由决策，以最小化本地流量路由，同时非最小路由以在高负载下平衡困难流量模式。 CQR 与 GAL 一样，可以匹配局部模式上的最小算法的吞吐量，以及困难模式上的负载平衡不经意算法的吞吐量——这是其他不做出全局自适应决策的算法无法实现的。

通道队列路由克服了与 GAL 相关的许多问题。最重要的是，在需要非最小路由的负载上，CQR 的延迟远低于 GAL。这是因为在切换到非最小路由之前，它不需要将最小流量运行到饱和状态，从而导致高延迟。一旦最小和非最小路由导致的延迟匹配，CQR 就开始沿着非最小路由发送数据包，从而实现最小延迟。 CQR 还具有比 GAL 快得多的瞬态响应。这是因为通道队列快速反映全局拥塞，而注入队列（用于 GAL 中的感知）要求在感知拥塞之前沿最小路径的所有队列都已填满。 CQR 也是无条件稳定的，而 GAL 需要阈值适应机制才能提供稳定的性能。最后，与 GAL 相比，CQR 的实现非常简单。

之后将着眼于将 CQR 和 GAL 的优势扩展到任意常规网络拓扑。将把最小和非最小象限的概念推广到任意拓扑中的路由集，并开发基于通道队列的方法来感知这些路径集中的拥塞。

相关文章