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

server/2024/9/24 14:12:47/
  • 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 的优势扩展到任意常规网络拓扑。将把最小和非最小象限的概念推广到任意拓扑中的路由集,并开发基于通道队列的方法来感知这些路径集中的拥塞


http://www.ppmy.cn/server/28748.html

相关文章

Fast-DetectGPT 无需训练的快速文本检测

本文提出了一种新的文本检测方法 ——Fast-DetectGPT&#xff0c;无需训练&#xff0c;直接使用开源小语言模型检测各种大语言模型&#xff0c;如GPT等生成的文本内容。 Fast-DetectGPT 将检测速度提高了 340 倍&#xff0c;将检测准确率相对提升了 75%&#xff0c;超过商用系…

上市企业数字赋能指数数据集-2001到2022年(TF-IDF)

01、数据简介 上市公司数字赋能指数是一个用来衡量上市公司利用数字技术提高业务能力和效率的指标。这个指数反映了上市公司利用大数据、云计算和人工智能等数字技术&#xff0c;高效地利用商业资源和信息&#xff0c;并扩展供应关系的能力。市公司数字赋能指数是一种综合性的…

搭建vue3组件库(三): CSS架构之BEM

文章目录 1. 通过 JS 生成 BEM 规范名称1.1 初始化 hooks 目录1.2 创建 BEM 命名空间函数1.3 通过 SCSS 生成 BEM 规范样式 2. 测试 BEM 规范 BEM 是由 Yandex 团队提出的一种 CSS 命名方法论&#xff0c;即 Block&#xff08;块&#xff09;、Element&#xff08;元素&#xf…

什么是RabbitMQ,RabbitMQ基本概念,RabbitMQ的使用场景

目录 面试官:什么是RabbitMQ,RabbitMQ的使用场景什么是RabbitMQ?RabbitMQ基本概念RabbitMQ的使用场景举例该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:什么是RabbitMQ,RabbitMQ的使用场景 …

OpenHarmony实战开发-动画曲线、如何实现动画衔接

UI界面除了运行动画之外&#xff0c;还承载着与用户进行实时交互的功能。当用户行为根据意图变化发生改变时&#xff0c;UI界面应做到即时响应。例如用户在应用启动过程中&#xff0c;上滑退出&#xff0c;那么启动动画应该立即过渡到退出动画&#xff0c;而不应该等启动动画完…

PG数据库结构与oracle比较

1.数据库集簇逻辑结构 数据库集簇概念&#xff1a;一个大的数据库是由若干个小的数据库组成&#xff0c;实现数据的隔离存放&#xff0c;在概念上应该是与mysql一样的 在mysql中可以用show database列出数据库 PG中用\l 数据库对象存放在数据库中&#xff1a; PG中的所有数据…

cve-2018-19518漏洞复现

一、靶场的启动 在相应的文件夹位置打开终端后进行如下操作 1.运行此靶场 sudo docker-compose up -d 2.查看启动环境 sudo docker ps 3.关闭此靶场环境 docker-compose down 二、漏洞内容简介 php imap扩展用户在php中执行邮件收发操作&#xff0c;其imap_open函数会调用rsh…

微信小程序常用的api

基础API&#xff1a; wx.request&#xff1a;用于发起网络请求&#xff0c;支持GET、POST等方式&#xff0c;是获取网络数据的主要手段。wx.showToast&#xff1a;显示消息提示框&#xff0c;通常用于向用户展示操作成功、失败或加载中等状态。wx.showModal&#xff1a;显示模态…