计算机科学 ›› 2021, Vol. 48 ›› Issue (6): 253-260.doi: 10.11896/jsjkx.200900203

• 计算机网络 • 上一篇    下一篇

BCube在2-限制连通度下的容错路由算法

易怡, 樊建席, 王岩, 刘钊, 董辉   

  1. 苏州大学计算机科学与技术学院 江苏 苏州215006
  • 收稿日期:2020-09-29 修回日期:2021-01-25 出版日期:2021-06-15 发布日期:2021-06-03
  • 通讯作者: 樊建席(jxfan@suda.edu.cn)
  • 基金资助:
    国家自然科学基金联合基金(U1905211);国家自然科学基金(61972272);江苏高校优势学科建设工程资助

Fault-tolerant Routing Algorithm in BCube Under 2-restricted Connectivity

YI Yi, FAN Jian-xi, WANG Yan, LIU Zhao, DONG Hui   

  1. School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
  • Received:2020-09-29 Revised:2021-01-25 Online:2021-06-15 Published:2021-06-03
  • About author:YI Yi,born in 1996,postgraduate.Her main research interests include parallel and distributed systems and graph algorithms.(20194227013@stu.suda.edu.cn)
    FAN Jian-xi,born in 1965,Ph.D,Professor,Ph.D supervisor.His main research interests include parallel and distributed systems,computer networks and graph algorithms.
  • Supported by:
    Joint Fund of the National Natural Science Foundation of China(U1905211),National Natural Science Foundation of China(61972272) and Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.

摘要: BCube是具有良好性能的数据中心网络。相比传统的树形数据中心网络,BCube在扩展和容错性能方面都表现出很大的优势。目前,对于BCube的研究可以归结为对其逻辑图BCn,k(广义超立方体的一种特例)的研究,其中交换机被视为透明设备。在实际应用中,随着网络规模的不断增加,顶点发生故障已经成为一种常态。因此,研究网络的容错路由很有意义。目前,有不少关于BCn,k容错路由的研究,但其2-限制连通度下的容错路由目前还没有被研究。在提出容错路由算法之前,首先证明了BCn,k的2-限制连通度为3(k+1)(n-1)-2n,其中k≥3n≥3。然后在此基础上提出了一个时间复杂度为O(κ(BCn,k)3)的容错路由算法,其中κ(BCn,k)=(k+1)(n-1)BCn,k的连通度。该算法可以在故障顶点个数小于3(k+1)(n-1)-2n且每个无故障顶点至少有两个无故障邻居时找到任意两个不同的无故障顶点之间的一条无故障路径。

关键词: 2-限制连通度, BCube, 容错路由, 时间复杂度, 数据中心网络

Abstract: BCubeis a data center network with good performance.Compared to traditional tree-shaped data center network,BCube has not only higher fault-tolerance performance but also superior scalability.Currently,the research on BCube can be reduced to logical structure (a special generalized hypercube),in which the switches are regarded as transparent devices.In actual application,with the continuous increase of network scale,vertex failure has become inevitable.Therefore,it is meaningful to study the fault-tolerant routing of the network.At present,there is some research on fault-tolerant routing of BCn,k.However,the fault-tolerant routing of BCn,k under the 2-restricted connectivity has not been studied yet.Before proposing the algorithm,the 2-restricted connectivity of BCn,k is firstly proved which is 3(k+1)(n-1)-2n for k≥3 and n≥3.Then a fault-tolerant routing algorithm with a time complexity of O(κ(BCn,k)3) is proposed where κ(BCn,k)=(k+1)(n-1) denotes the connectivity of BCn,k.The proposed algorithm can find a fault-free path between any two distinct fault-free vertices when the number of faulty vertices is less than 3(k+1)(n-1)-2n and every fault-free vertex has at least two fault-free neighbors.

Key words: 2-restricted connectivity, BCube, Data center networks, Fault-tolerant routing, Time complexity

中图分类号: 

  • TP393
[1]GHEMAWAT S,GOBIOFF H,LEUNG S T.The google filesystem[J].ACM Symposium on Operating System Principles,2003,37(5):29-43.
[2]CHANG F,DEAN J,GHEMAWAT S,et al.Bigtable:A distri-buted storage system for structured data[C]//7th Symposium on Operating Systems Design and Implementation.ACM,2006:6-8.
[3]ISARD M,BUDIU M,YU Y,et al.Dryad:Distributed data-pa-rallel programs from sequential building blocks[J].Operating Systems Review,2007,41(3):59-72.
[4]AZIZI S,HASHEMI N,KHONSARI A.HHS:An efficient network topology for large-scale data centers[J].Journal of Supercomputing,2016,72(3):1-26.
[5]GREENBER A G,HAMILTON J R,JAINT N,et al.VL2:A scalable and flexible data center network[J].ACM SIGCOMM Computer Communication Review,2011,39(4):51-62.
[6]HAMEDAZIMI N,QAZI Z,GUPTA H,et al.FireFly:A reconfigurable wireless data center fabric using free-space optics[J].ACM SIGCOMM Computer Communication Review,2014,44(4):319-330.
[7]ZHANG Z,DENG Y H,MIN G Y,et al.HSDC:A highly scalable data center network architecture for greater incremental scalability[J].IEEE Transactions on Parallel and Distributed Systems,2019,30(5):1105-1119.
[8]GUO C X,WU H T,TAN K,et al.DCell:A scalable and fault-tolerant network structure for data centers[J].ACM SIGCOMM Computer Communication Review,2008,38(4):75-86.
[9]WANG X,FAN J X,LIN C K,et al.BCDC:A high-perfor-mance,server-centric data center network[J].Journal of Compu-ter Science and Technology,2018,33(2):400-416.
[10]GUO C X,LU G H,LI D,et al.BCube:A high performance,server-centric network architecture for modular data centers[J].ACM SIGCOMM Computer Communication Review,2009,39(4):63-74.
[11]PUSHPARAJ J,VEDA B P,SOUMYA J.A link fault tolerant routing algorithm for mesh of tree based network-on-chips[C]//2019 IEEE International Symposium on Smart Electronic Systems.IEEE,2019:181-184.
[12]HANG Y X,XU J F,NAN L M.Congestion-aware adaptive fault-tolerant routing algorithm for network-on-chip[J].Journal of Chinese Mini-Micro Computer Systems,2018,39(2):262-269.
[13]CHAKIB N,MOHAMED S.A new fault tolerant routing algorithm for networks on chip[J].Embedded and Real-Time Communication Systems,2019,10(3):68-85.
[14]THUAN B T,NGOC L B,KANEKO K.A stochastic link-fault-tolerant routing algorithm in folded hypercubes[J].Journal of Supercomputing,2018,74(10):5539-5557.
[15]WANG G J,FAN J X,LV Y L,et al.The constructive algo-rithm of vertex disjoint paths in the generalized hypercube under restricted connectivity[J].Journal of Internet Technology,2019,20(6):1995-2006.
[16]GUO L L,WANG X,LIN C K,et al.A fault-free unicast algorithm in the generalized hypercube with restricted faulty vertices[J].International Journal of Foundations of Computer Science,2017,28(7):915-929.
[17]WANG G J,LIN C K,FAN J X,et al.The fault-tolerant hamiltonicity and hamiltonian connectivity of BCube with various faulty elements[J].Journal of Computer Science and Technology,2020,35(5):1064-1083.
[18]DUH D R,CHEN G H,HSU D F.Combinatorial properties of generalized hypercube graphs[J].Information Processing Letters,1996,57(1):41-45.
[19]TONG M S,LIU C H,FAN T Y.Routing algorithms for shortest paths in faulty generalized hypercubes[J].Chinese Journal of Computers,1998,21(12):1074-1083.
[20]ESFAHANIAN A H,HAKIMI S L.On computing a conditio-nal edge-connectivity of a graph[J].Information Processing Letters,1988,27(4):195-199.
[21]LATIFIFI S,HEGD M V,NARAGHIPOUR M.Conditionalconnectivity measures for large multiprocessor systems[J].IEEE Transactions on Computers,1994,43(2):218-222.
[22]GUO L L.Research on conditional connectivity and fault-tole-rant routing of generalized hypercubes[D].Suzhou:Soochow University,2018.
[23]WEI C C,HSIEH S Y.H-restricted connectivity of locally twisted cubes[J].Discrete Applied Mathematics,2016,615:78-90.
[24]LV M J,CHENG B L,FAN J X,et al.The conditional reliability evaluation of data center network BCDC[J/OL].The Computer Journal,2020,https://doi.org/10.1093/comjnl/bxaa078.
[25]WANG X,FAN J X,ZHOU J Y,et al.The restricted h-connectivity of the data center network DCell[J].Discrete Applied Mathematics,2016,203:144-157.
[1] 潘志勇, 程宝雷, 樊建席, 卞庆荣.
数据中心网络BCDC上的顶点独立生成树构造算法
Algorithm to Construct Node-independent Spanning Trees in Data Center Network BCDC
计算机科学, 2022, 49(7): 287-296. https://doi.org/10.11896/jsjkx.210500170
[2] 张登科, 王兴伟, 何强, 曾荣飞, 易波.
可重构数据中心网络研究综述
State-of-the-art Survey on Reconfigurable Data Center Networks
计算机科学, 2021, 48(3): 246-258. https://doi.org/10.11896/jsjkx.201100038
[3] 金勇, 刘亦星, 王欣欣.
基于SDN的数据中心网络多路径流量调度算法
SDN-based Multipath Traffic Scheduling Algorithm for Data Center Network
计算机科学, 2019, 46(6): 90-94. https://doi.org/10.11896/j.issn.1002-137X.2019.06.012
[4] 樊自甫,李书,张丹.
基于流量调度的SDN数据中心网络拥塞控制算法
Traffic Scheduling Based Congestion Control Algorithm for Data Center Network on Software Defined Network
计算机科学, 2017, 44(Z6): 266-269. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.061
[5] 林政宽,王铭成,郭莉莉,杜满意.
基于有故障区域的Mesh网络目标结点间的最短路由算法
Shortest Routing Algorithm Based on Target Node in Mesh Network with Faulty Area
计算机科学, 2017, 44(Z6): 252-257. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.058
[6] 乔焰,焦俊,饶元.
基于数据中心流量特征的端到端流量估计算法
Traffic Estimation for Data Center Network Based on Traffic Characteristics
计算机科学, 2017, 44(2): 171-175. https://doi.org/10.11896/j.issn.1002-137X.2017.02.026
[7] 方贤进,王丽,康佳,刘佳.
树突细胞算法及其理论研究
On Dendritic Cell Algorithm and its Theoretical Investigation
计算机科学, 2015, 42(2): 131-133. https://doi.org/10.11896/j.issn.1002-137X.2015.02.028
[8] 王树西,李安渝.
Dijkstra算法中的多邻接点与多条最短路径问题
Multi-adjacent-vertexes and Multi-shortest-paths Problem of Dijkstra Algorithm
计算机科学, 2014, 41(6): 217-224. https://doi.org/10.11896/j.issn.1002-137X.2014.06.043
[9] 金亦挺,王万良,赵燕伟,蒋一波.
基于点到弦距离累加的快速角点检测
Fast Corner Detector Based on Chord-to-Point Distance Accumulation
计算机科学, 2014, 41(4): 306-308.
[10] 周毅敏,李光耀.
一种根据决策树结合信息论的经典算法复杂度可能下界分析
Analysis of Probable Lower Bound of Time Complexity of Some Classical Algorithms Based on Decision Tree and Information Theory
计算机科学, 2013, 40(Z11): 238-241.
[11] 张赣,梁伟,毕经平,邵定宏.
基于支点的数据中心网络地址快速自动配置方法研究
PFAC:Pivot-based Fast Automatic Configuration for Data Center Networks
计算机科学, 2013, 40(5): 62-66.
[12] 冷飞,徐进华,栾仕喜.
DCNS:一种高可用性的数据中心网络
DCNS:A High Available Data Center Network Topology
计算机科学, 2013, 40(12): 177-181.
[13] 尹栋,慕德俊,戴冠中.
一种以服务器为通信节点的数据中心网络设计
Research on Server Centric Data Center Network Design
计算机科学, 2012, 39(3): 110-112.
[14] 王沁,李磊,陆成勇,孙富明.
平均计算时间复杂度优化的动态粒子群优化算法
Average Computational Time Complexity Optimized Dynamic Particle Swarm Optimization Algorithm
计算机科学, 2010, 37(3): 191-194288.
[15] .
一种改进的BMH模式匹配算法

计算机科学, 2008, 35(11): 164-165.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!