Practical and Efficient Customized Multicast Routing in Fat-Tree Topology
-
摘要: 在高性能计算领域，多播路由算法对硬件集合操作的性能具有至关重要的影响.随着系统规模的不断扩大，多播组的个数急剧增加，可能会超过硬件支持的多播表条目数，而现有的多播路由算法要么没有给出解决方案，要么存在时间开销大、多播路由经常变化等问题.为此，首先对胖树中的无冲突多播生成树数量进行了量化研究，并以此为基础提出了一种适用于胖树的高效实用的定制多播路由算法(customized multicast routing for limited multicast forwarding table size, C-MR4LMS).C-MR4LMS在构建多播树时，根据多播组的MGID(multicast global identification)静态地将多播组映射到1棵生成树中，从而快速完成多播树的构建；而在合并多播树时，仅需合并使用同一生成树的多播组，且不会改变被合并多播组的路由.然后提出了2种减少多播树冲突的方法：一是分层的MGID分配策略，以避免出现同一终端节点使用同一颜色加入多个多播组的情况；二是相互无干扰的作业节点分配策略，保证2个作业的多播组互不干扰.最后，在ibsim模拟器及神威E级原型机上对C-MR4LMS进行了测试，该多播路由算法计算多播路由的时间比现有的多播路由算法有了显著下降，最大下降了94%.Abstract: In high performance computing, multicast routing algorithms have important impact on the performance of collective operations supported by hardware. As the supercomputers become larger and larger, the number of MCGs (multicast groups) increases rapidly, and it may exceed the number of MFT (multicast forwarding table) entries supported by hardware. However, the existing multicast routing algorithms either do not provide solutions to this problem, or have problems such as heavy time overhead and variability for multicast routing. To address this problem, we first quantitatively study the number of conflict-free multicast spanning trees in fat-tree, and propose a practical and efficient customized multicast routing algorithm called C-MR4LMS (customized multicast routing for limited multicast forwarding table size). When constructing multicast tree, the MCG is statically mapped to a spanning tree according to the MGID (multicast global identification); thus we can construct the multicast tree quickly. When merging multicast trees, only the ones using the same spanning tree need to be merged, and the route of the merged MCGs will not be changed. Then we propose two methods to reduce the confliction of multicast routes. One is the layered MGID allocation strategy to avoid the situation that the terminal node uses the same color to join multiple MCGs. The other one is the interference-free node allocation strategy for different jobs to ensure that the MCGs of two jobs do not interfere with each other. Finally, we test the performance of C-MR4LMS in ibsim simulator and Sunway exascale prototype system and obtain the satisfying results. In particular, the running time of the algorithm compared with the existing algorithms is significantly reduced, and we get up to 94% reduction in runtime.
-
-
期刊类型引用(9)
1. 杨秀璋，彭国军，刘思德，田杨，李晨光，傅建明. 面向APT攻击的溯源和推理研究综述. 软件学报. 2025(01): 203-252 . 
百度学术
2. 马涛，杨峰，刘霞. 物联网技术在降低成本提高效率中的应用. 电子技术. 2024(01): 282-283 . 百度学术
3. 万丽娟，笪枫. 电力监控系统的多源威胁情报分析. 电子技术. 2024(03): 248-249 . 百度学术
4. 张进军，周锐. 基于多源数据分析的物联网智能跨层资源分配算法. 安徽电气工程职业技术学院学报. 2024(02): 73-81 . 百度学术
5. 蒋伟进，李恩，罗田甜，周文颖，杨莹. 基于区块链和可信执行环境的细粒度访问控制方案研究与应用——以物联网为例. 系统工程理论与实践. 2024(07): 2394-2410 . 百度学术
6. 陈泽恩. 物联网中多源异构数据安全漏洞检测技术研究. 物联网技术. 2024(09): 124-126 . 百度学术
7. 武丹丹，陈捷，谢瑞云，陈轲. OntoCSD：基于本体的网络空间防御综合解决方案安全模型（英文）. Frontiers of Information Technology & Electronic Engineering. 2024(09): 1209-1226 . 百度学术
8. 刘奇旭，刘嘉熹，靳泽，刘心宇，肖聚鑫，陈艳辉，朱洪文，谭耀康. 基于人工智能的物联网恶意代码检测综述. 计算机研究与发展. 2023(10): 2234-2254 . 本站查看
9. 杜文玲. 基于多源数据整合的大学生多级别心理压力智能预测方法. 赤峰学院学报(自然科学版). 2023(09): 74-77 . 百度学术
其他类型引用(9)
计量
- 文章访问数: 176
- HTML全文浏览量: 9
- PDF下载量: 108
- 被引次数: 18
下载:
