【论文阅读】互连网络的负载平衡路由算法 (RLB & RLBth)

这篇具有很好参考价值的文章主要介绍了【论文阅读】互连网络的负载平衡路由算法 (RLB & RLBth)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  • 前言
  • Oblivious Load Balancing 不经意路由负载平衡
    • 1. oblivious routing 不经意/无关路由的背景知识
      • 1. oblivious routing, adaptive routing & minimal/non-minimal routing algorithms
    • 2. Balancing a 1-Dimensional ring: RLB and RLBth 一维 ring 的 RLB and RLBth
      • 1. Motivation of Balancing load 平衡负载的动机
      • 2. 一维 ring 的 RLB and RLBth
  • References

前言

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

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

Oblivious Load Balancing 不经意路由负载平衡

文章提出了用于 torus 网络的随机、非最小、不经意路由算法——RLB和RLBth

1. oblivious routing 不经意/无关路由的背景知识

不经意算法仅使用源节点和目标节点的身份来选择从源到目标的路径。换句话说,路由决策是“忽略”网络状态的。不经意的算法可能会使用随机化来在可能的路径之间进行选择。根据路线的长度,它们也可以被分类为最小或非最小。

1. oblivious routing, adaptive routing & minimal/non-minimal routing algorithms

  • 不经意路由算法(oblivious routing algorithms)仅根据消息源和目的地的身份在这些路径之间进行选择,而自适应算法(adaptive algorithms)则可以根据网络状态(拥塞信息)做出决策。

  • 不经意的算法和自适应算法都可以使用**随机化(Randomization)**来在替代路径中进行选择。

  • 最小算法(Minimal algorithms)沿着从源到目的地的最短路径路由所有数据包,而非最小算法(non-minimal)可能沿着更长的路径路由数据包,即进行了绕远如 VAL 路由算法。

  • 常见的不经意算法 oblivious routing 包括——DOR、VAL 和 ROMM

    • 维序路由(DOR),有时称为 e-cube routing,首先由 Sullivan 和 Bashkow 在A LARGE SCALE, HOMOGENOUS, FULLY DISTRIBUTED PARALLEL MACHINE, II 一文中首次提出[1]。**在 DOR 算法中,每个数据包首先只在一个维度上传递,只有当该维度的坐标一致后,再进入下一个维度进行传输。**由于其简单性,它已被大量用于互连网络中。但 DOR 在对抗性流量(adversarial traffic)模式上的糟糕表现引出了自适应路由方面的大量工作。
    • Valiant 首先提出了如何使用随机化为任意流量模式提供有保证的吞吐量[2]。即将**路由分为两个阶段,第一阶段从源节点路由至全局中随机选择的中间节点(intermediate node),第二阶段从中间节点路由至目标节点。两个阶段的具体路由算法都使用 DOR。**虽然 VAL 路由算法能够进行负载的平衡,在最坏模式下保证一定的性能,但是其破坏了局部性(locality),在本地流量甚至平均流量上性能较差。
    • 为了在获得随机化优势的同时保留局部性,Nesson 和 Johnson 提出了 ROMM 路由算法[3],即随机、不经意、多阶段最小路由(Randomized, Oblivious, Multi-phase Minimal routing)。**与 VAL 一样需要两个阶段,但 ROMM 通过从最小象限(minimal quadrant)(即源节点和目标节点坐标所构成的象限)中随机选择的中间节点路由每个数据包,确保生成的路径严格最小。**虽然[31]报告了一些排列的良好结果,但 ROMM 实际上比 DOR 具有更低的最坏情况吞吐量。问题在于使用最小路由(minimal routing),不可能在对抗模式上实现良好的负载平衡。

2. Balancing a 1-Dimensional ring: RLB and RLBth 一维 ring 的 RLB and RLBth

1. Motivation of Balancing load 平衡负载的动机

下图 1.4 显示了8 node的 ring 的简化版本。对于良性流量模式,如最近邻居 (NN),来自节点的所有流量均等分配到其相邻节点之间(一半到节点 i+1,一半到节点 i-1,模8/模k)。由于每个单向通道具有带宽b,因此如果流量只是沿着最小路径路由,则每个节点都可以以最佳速率2b (吞吐量, 2b) 注入流量。我们称这种流量为良性(benign),因为如果使用最小路由来路由数据包,所有通道自然会实现负载平衡

【论文阅读】互连网络的负载平衡路由算法 (RLB & RLBth),互连网络 interconnection network,科研相关知识,论文阅读,网络,算法,系统架构

而对于对抗流量模式,我们考虑 ring 的 MR 的最坏情况流量(worst-case traffic)、龙卷风(TOR)流量。在 TOR 中,来自节点 i 的所有流量几乎绕环的一半发送到节点 i+3(i + k/2 - 1)。图 1.5 显示了最小路由 TOR 导致顺时针通道上的高负载,保持逆时针通道完全空闲。这会导致相当大的负载不平衡,吞吐量较差(单向通道带宽为b,每个顺时针通道需要维持3条不同数据流,故吞吐量为b/3)。

【论文阅读】互连网络的负载平衡路由算法 (RLB & RLBth),互连网络 interconnection network,科研相关知识,论文阅读,网络,算法,系统架构

如果要在 TOR 等对抗模式上获得良好的性能,需要非最小路由(绕环的长距离)路由一些流量以平衡负载。先按照 Valiant 的建议,通过完全随机化路由 (VAL) 来平衡 TOR 流量,从节点 i 发送到随机中间节点 j,然后从 j 发送到 i+3。这两个阶段中的每一个阶段都是完全随机的路由,因此每个阶段平均使用 2 个 links,故整个路由使用 4 个 links。而最小路由是 3 个 links。即使 VAL 平均比最小路由多遍历一个链路 link,VAL 的每节点吞吐量在 TOR 上更高,为b/2(其使用了双向的channels,且每条 link 上平均有两条数据流)。纯随机路由的问题在于它破坏了局部性。对于 NN 流量模式,吞吐量仍然为 b/2,而 MR 为 2b。文章提出的路由算法,努力在不牺牲良性流量固有的局部性的情况下实现良好的最坏情况性能

2. 一维 ring 的 RLB and RLBth

**在对抗性流量中,最小路由算 MIN 无法均衡负载,使得一个 8 node ring 的吞吐量降低至 b/3。**任何 k-ary n-cube 的网络容量为 2B/N = 8b/k(用 UR 流量的理想吞吐量作为网络容量,将吞吐量和提供的负载归一化为网络容量,Bw 为对分带宽,一般为双向带宽,B/N 为一个单向通道的带宽,故网络容量为 2B/N)。

所以一个 8 node ring 在最小路由和 TOR 流量模式下的吞吐量为 b/3 即 0.33b,33.3%的网络容量。一般而言,最小路由 MIN 的吞吐量会逐渐降低到 25% 的容量,这意味着最坏情况下的性能非常差。即 b/(k/2-1) / (8b/k) = k/8 / (k/2-1),当对于较大的 k 时,吞吐量小于 0.25。

未完待续…

References

[1] L. G. Valiant and G. J. Brebner, “Universal schemes for parallel communication,” in Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC ’81, Milwaukee, Wisconsin, United States: ACM Press, 1981, pp. 263–277. doi: 10.1145/800076.802479.
[2] H. Sullivan, S. Associates, T. R. Bashkow, and D. Klappholz, “A LARGE SCALE, HOMOGENOUS, FULLY DISTRIBUTED PARALLEL MACHINE, II”.
[3] T. Nesson and S. L. Johnsson, “ROMM routing on mesh and torus networks,” in Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures - SPAA ’95, Santa Barbara, California, United States: ACM Press, 1995, pp. 275–287. doi: 10.1145/215399.215455.文章来源地址https://www.toymoban.com/news/detail-857085.html

到了这里,关于【论文阅读】互连网络的负载平衡路由算法 (RLB & RLBth)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【论文阅读及代码实现】BiFormer: 具有双水平路由注意的视觉变压器

    BiFormer: Vision Transformer with Bi-Level Routing Attention 视觉转换器的核心组成部分,注意力是捕捉长期依赖关系的有力工具 计算跨所有空间位置的成对token交互时,计算负担和沉重的内存占用 提出了一种新的动态稀疏注意,通过双层路由实现更灵活的内容感知计算分配     过程:

    2024年02月12日
    浏览(51)
  • 3D卷积网络论文阅读笔记

    数据集 BraTS 2020 数据增强方法 • Flipping翻转: 以1/3的概率随机沿着三个轴之一翻转 • Rotation旋转: 从限定范围(0到 15◦或到30◦或到60◦或到90◦)的均匀分布中随机选择角度旋转 • Scale缩放: 通过从范围为±10%或为±20%的均匀分布中随机选择的因子,对每个轴进行缩放 • Br

    2023年04月10日
    浏览(47)
  • Azure虚拟网络对等互连

    Azure虚拟网络对等互联(Azure Virtual Network peering)是一种连接两个虚拟网络的方法,使得这两个虚拟网络能够在同一地理区域内进行通信。它通过私有IP地址在虚拟网络之间建立网络连接,不论是在同一订阅内还是不同订阅,也不论是在同一个区域还是不同的区域。 对等互联可

    2024年02月12日
    浏览(41)
  • 图像生成论文阅读:GLIDE算法笔记

    标题:GLIDE: Towards Photorealistic Image Generation and Editing with Text-Guided Diffusion Models 会议:ICML2022 论文地址:https://proceedings.mlr.press/v162/nichol22a.html 官方代码:https://github.com/openai/glide-text2im 作者单位:OpenAI 扩散模型最近已被证明可以生成高质量的合成图像,特别是在与引导技术结合

    2024年02月02日
    浏览(48)
  • 强化学习论文阅读(二)SAC算法

    原文传递:SAC算法原文 作者指出深度强化学习样本效率低下的原因是:策略学习,TRPO、PPO、A3C每次策略更新都需要收集样本。学习有效的策略需要的步骤和样本数量伴随着任务的复杂性呈现增加的趋势。Off-Policy为了重复使用过去产生的经验值,但是在传统的策略公式当中不

    2024年02月06日
    浏览(46)
  • 【论文阅读】StyleganV1 算法理解

    听过Stylegan的人都觉得他很强!目前stylegan已经发展到第三代v3了,但是为了搞清思想,我还是从v1开始了解,以下是我个人的一些理解。 传统GAN采用端对端的输入输出,可以尽可能使用训练集数据的信息,但是会出现两个问题。 仅保持一种输入,纵使网络有再强的能力,也可

    2024年02月12日
    浏览(52)
  • 对比学习论文阅读:CoCLR算法笔记

    标题:Self-supervised Co-training for Video Representation Learning 会议:NIPS2020 论文地址:https://dl.acm.org/doi/abs/10.5555/3495724.3496201 官方代码:https://www.robots.ox.ac.uk/~vgg/research/CoCLR/ 作者单位:牛津大学 本文的研究目标是纯视觉的自监督视频表征学习。我们做出了以下贡献:①我们研究了在

    2024年02月03日
    浏览(62)
  • 论文阅读:通过时空生成卷积网络合成动态模式(重点论文)

    原文链接 github code 介绍视频 视频序列包含丰富的动态模式,例如在时域中表现出平稳性的动态纹理模式,以及在空间或时域中表现出非平稳的动作模式。 我们证明了时空生成卷积网络可用于建模和合成动态模式。 该模型定义了视频序列上的概率分布,对数概率由时空ConvN

    2024年01月19日
    浏览(48)
  • 论文阅读--用于小物体检测的增强算法

    Title: Augmentation for small object detection Abstract: In the recent years, object detection has experienced impressive progress. Despite these improvements, there is still a significant gap in the performance between the detection of small and large objects. We analyze the current state-of-the-art model, Mask-RCNN, on a challenging dataset, MS COCO. We sh

    2024年02月15日
    浏览(58)
  • 软路由的负载均衡设置:优化网络性能和带宽利用率

    在现代网络环境中,提升网络性能和最大化带宽利用率至关重要。通过合理配置软路由IP的负载均衡设置,可以有效地实现这一目标,并提高整体稳定性与效果。本文将详细介绍如何进行软路由IP的负载均衡设置,从而优化网络表现、增加带宽利用效率,并为读者呈现一个完善

    2024年02月09日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包