计算机科学 ›› 2021, Vol. 48 ›› Issue (6): 253-260.doi: 10.11896/jsjkx.200900203
易怡, 樊建席, 王岩, 刘钊, 董辉
YI Yi, FAN Jian-xi, WANG Yan, LIU Zhao, DONG Hui
摘要: BCube是具有良好性能的数据中心网络。相比传统的树形数据中心网络,BCube在扩展和容错性能方面都表现出很大的优势。目前,对于BCube的研究可以归结为对其逻辑图BCn,k(广义超立方体的一种特例)的研究,其中交换机被视为透明设备。在实际应用中,随着网络规模的不断增加,顶点发生故障已经成为一种常态。因此,研究网络的容错路由很有意义。目前,有不少关于BCn,k容错路由的研究,但其2-限制连通度下的容错路由目前还没有被研究。在提出容错路由算法之前,首先证明了BCn,k的2-限制连通度为3(k+1)(n-1)-2n,其中k≥3且n≥3。然后在此基础上提出了一个时间复杂度为O(κ(BCn,k)3)的容错路由算法,其中κ(BCn,k)=(k+1)(n-1)是BCn,k的连通度。该算法可以在故障顶点个数小于3(k+1)(n-1)-2n且每个无故障顶点至少有两个无故障邻居时找到任意两个不同的无故障顶点之间的一条无故障路径。
中图分类号:
[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. |
|