具有原路返回特征的改进OSRM胖树路由算法研究

J4 ›› 2014, Vol. 36 ›› Issue (06): 997-1004.

• 论文 • 下一篇

具有原路返回特征的改进OSRM胖树路由算法研究

曹继军，郑义，王克非，肖立权

国防科学技术大学计算机学院，湖南长沙 410073

收稿日期:2013-08-10 修回日期:2013-11-16 出版日期:2014-06-25 发布日期:2014-06-25

Study on the improved OSRM routing algorithm
with back-track feature for fat-tree networks

CAO Jijun，ZHENG Yi，WANG Kefei，XIAO Liquan

（College of Computer,National University of Defense Technology,Changsha 410073,China）

Received:2013-08-10 Revised:2013-11-16 Online:2014-06-25 Published:2014-06-25

摘要/Abstract

摘要：

胖树是最重要的互连网络拓扑结构之一。针对胖树拓扑结构，已经提出了多种路由算法，其中OSRM被证明是一种最优化的路由算法，但是所有算法都忽略了网络链路故障的易诊断性。为此，提出一种对OSRM改进的新型路由算法BT-OSRM。该算法定义了节点间的大小关系并通过比较节点大小而从OSRM路由路径与其反向路径中选择路由路径。此外，还针对常用的2级和3级胖树结构，分别详细给出了BT-OSRM2和BT-OSRM3路由算法。理论分析表明，BTOSRM路由算法不但继承了OSRM路由算法无死锁、负载均衡和性能最优等优点，而且保证了任意两节点间的路由路径具有原路返回特性，从而提高了网络故障链路的易诊断性。

关键词: 胖树, 原路返回, 路由算法, 无死锁, 负载均衡, 确定性能比率

Abstract:

Fat-tree is one of the most important topologies of interconnection networks. Several routing algorithms have been proposed for fat-tree topology. Among them, the OSRM routing algorithm is proved to be an optimal routing algorithm. However, all these algorithms ignore the ease of diagnosis of linkfault. Therefore, based on OSRM, a novel routing algorithm, named BT-OSRM, is proposed. In the BT-OSRM algorithm, the less-equal-great relationship between any pairs of processing nodes is defined, and hence the routing path is chosen from the OSRM routing path and its back-track routing path based on the defined relationship. Further, the BT-OSRM2 and BT-OSRM3 algorithms are described in detail for the commonly used two stages and three stages fattree topologies respectively. Theoretical analysis shows that the BTOSRM algorithm not only is as deadlockfree, loadbalanced and optimal as the OSRM algorithm, but also can guarantee the back-track feature for routing between any two endnodes, thus facilitating the diagnosis of linkfault in interconnection networks.

Key words: fat-tree;back-track;routing algorithm;deadlock freedom;load balance;oblivious performance ratio

曹继军，郑义，王克非，肖立权. 具有原路返回特征的改进OSRM胖树路由算法研究[J]. J4, 2014, 36(06): 997-1004.

CAO Jijun，ZHENG Yi，WANG Kefei，XIAO Liquan. Study on the improved OSRM routing algorithm
with back-track feature for fat-tree networks [J]. J4, 2014, 36(06): 997-1004.

参考文献

［1］Leiserson C. Fat tree:Universal networks for hardwareefficient supercomputing［J］. IEEE Transactions on Computers, 1985,34(10):892901.
［2］http://www.top500.org.
［3］Petrini F,Vanneschi M.kary ntrees:High performance networks for massively parallel architecture［C］∥Proc of International Parallel Processing Symposium, 1997:8793.
［4］Xin Yuan,Nienaber W,Duan Zhenhai,et al. Oblivious routing for fattree based system area networks with uncertain traffic demands［C］∥Proc of SIGMETRICS’07,2007:1216.
［5］Lin X, Chung Y, Huang T. A multiple LID routing scheme for fattreebased Infiniband network［C］∥Proc of the 18th IEEE International Parallel and Distributed Processing Symposium, 2004:1.
［6］Leighton F T. Introduction to parallel algorithms and architectures:Arrays, trees, hyper cubes［M］. San Francisco:Morgan Kaufmann Publishers, 1992.
［7］Gomez C. Lowmemory techniques for routing and faulttolerance on the fattree topology［D］. Spain:Technical University of Valencia, 2010.
［8］Applegate D, Cohen E. Making intradomain routing robust to changing and uncertain traffic demands:Understanding fundamental tradeoffs［C］∥Porc of ACM SGICOMM’03, 2003:313324.
［9］Gomez M E, Lopez P, Duato J. A memoryeffective routing strategy for regular interconnection network［C］∥Proc of the 19th IEEE International Parallel and Distributed Processing Symposium’05, 2005:114.
［10］Hu Nongda, Wang Dawei, Sun Ninghui. Distributed dynamic faulttolerant routing in fattree［J］. Chinese Journal of Computers, 2010,33(10):17991808. (in Chinese)
［11］Dally W J,Seitz C L.Deadlockfree message routing in multiprocessor interconnection networks［J］. IEEE Transactions on Computers, 1987,C36(5):547553.
［12］Schroeder M D, Birrell A D, Burrows M, et al. Autonet:A highspeed, selfconfiguring local area network in communication［J］.IEEE Journal of Selected Areas in Communications, 1991,9(8):13181335.
［13］Villar J A, Andujar F J, Sanchez J L, et al. An alternative for building highradix switches:Application for special traffic patterns［R］. Technical Report DIAB11022, Ciudad Real: University of CastillaLa Mancha,2011.
［14］Martinez J C, Flich J, Robles A, et al. Supporting adaptive routing in IBA switches［J］. Journal of System and Architectures, 2003,49(1011):441456.
附中文参考文献：
［10］胡农达,王达伟,孙凝晖.胖树中的分布式动态容错路由［J］.计算机学报,2010,33(10):17991808.

[1]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[2]	康子扬, 彭凌辉, 周干, 林博, 王蕾. 一种用于片上网络的拥塞感知哈密尔顿最短路径路由算法[J]. 计算机工程与科学, 2022, 44(06): 986-993.
[3]	徐浩桐, 黄山, 孙国璋, 贺菲莉, 段晓东, . 面向云环境的Flink负载均衡策略[J]. 计算机工程与科学, 2022, 44(05): 779-787.
[4]	罗晓霞, 王佳, 罗香玉, 李嘉楠 . 一种基于GN算法的动态图划分方法[J]. 计算机工程与科学, 2022, 44(02): 306-311.
[5]	李力, 汪硕, 黄韬, 刘韵洁, . 数据中心网络四层负载均衡技术综述[J]. 计算机工程与科学, 2022, 44(01): 48-59.
[6]	黄山, 房六一, 徐浩桐, 段晓东, . 面向容器环境的Flink的任务调度优化研究[J]. 计算机工程与科学, 2021, 43(07): 1173-1184.
[7]	陈俊彦, 李玥, 梁楚欣, 雷晓春. SDN多控制器部署及流量均衡研究[J]. 计算机工程与科学, 2021, 43(05): 830-835.
[8]	丁峻宏, 苗新强, 李根国. 面向异构超算的结构分析高效并行计算方法[J]. 计算机工程与科学, 2020, 42(12): 2133-2140.
[9]	王丽, 郭振华, 曹芳, 高开, 赵雅倩, 赵坤. 面向模型并行训练的模型拆分策略自动生成方法[J]. 计算机工程与科学, 2020, 42(09): 1529-1537.
[10]	张开琦, 刘晓燕, 王信, 吉春山, 严馨. 基于动态权重的一致性哈希微服务负载均衡优化[J]. 计算机工程与科学, 2020, 42(08): 1339-1344.
[11]	刘梓璇，周建涛. 负载均衡的主导资源公平分配算法[J]. 计算机工程与科学, 2019, 41(09): 1574-1580.
[12]	孙婷婷，黄皓，王嘉伦，翁楚良. 面向CPU-GPU异构系统的数据分析负载均衡策略[J]. 计算机工程与科学, 2019, 41(03): 417-423.
[13]	谢果君，沈记全，杨焕焕. 基于柯西码的HDFS存储优化策略[J]. 计算机工程与科学, 2019, 41(03): 440-445.
[14]	陈华鹏1,2,林杰1. 基于负载基尼系数的服务网络公平均衡调度[J]. 计算机工程与科学, 2018, 40(07): 1155-1164.
[15]	樊自甫，张丹，李书. 基于软件定义网络的数据中心网络负载均衡算法研究[J]. 计算机工程与科学, 2018, 40(06): 1017-1022.

具有原路返回特征的改进OSRM胖树路由算法研究

Study on the improved OSRM routing algorithm
with back-track feature for fat-tree networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

具有原路返回特征的改进OSRM胖树路由算法研究

Study on the improved OSRM routing algorithm with back-track feature for fat-tree networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

Study on the improved OSRM routing algorithm
with back-track feature for fat-tree networks