AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

Fault-Tolerant Hamiltonicity and Hamiltonian Connectivity of BCube with Various Faulty Elements

School of Computer Science and Technology, Soochow University, Suzhou 215006, China
School of Computer Science and Technology, Qilu University of Technology (Shandong Academy of Sciences) Jinan 250353, China
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
Show Author Information

Abstract

BCube is one kind of important data center networks. Hamiltonicity and Hamiltonian connectivity have significant applications in communication networks. So far, there have been many results concerning fault-tolerant Hamiltonicity and fault-tolerant Hamiltonian connectivity in some data center networks. However, these results only consider faulty edges and faulty servers. In this paper, we study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity of BCube(n,k) under considering faulty servers, faulty links/edges, and faulty switches. For any integers n ≥ 2 and k ≥ 0, let BCn,k be the logic structure of BCube(n,k) and F be the union of faulty elements of BCn,k. Let fv, fe, and fs be the number of faulty servers, faulty edges, and faulty switches of BCube(n,k), respectively. We show that BCn,k − F is fault-tolerant Hamiltonian if fv +fe + (n − 1)fs ≤ (n − 1)(k + 1) − 2 and BCn,k −F is fault-tolerant Hamiltonian-connected if fv + fe + (n − 1)fs ≤ (n − 1)(k + 1) − 3. To the best of our knowledge, this paper is the first work which takes faulty switches into account to study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity in data center networks.

Keywords

data center networkBCubefault-toleranceHamiltonicityHamiltonian connectivity

Electronic Supplementary Material

Download File(s)
jcst-35-5-1064-Highlights.pdf (276.5 KB)

References

[1]
Guo C, Wu H, Tan K, Shi L, Zhang Y, Lu S. DCell: A scalable and fault-tolerant network structure for data centers. In Proc. the 2008 ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, August 2008, pp.75-86.
Crossref
[2]
Ahn J H, Binkert N, Davis A, McLaren M, Schreiber R S. HyperX: Topology, routing, and packaging of efficient large-scale networks. In Proc. the Conference on High Performance Computing Networking, Storage and Analysis, November 2009, Article No. 41.
Crossref
[3]
Guo C, Lu G, Li D et al. BCube: A high performance, server-centric network architecture for modular data centers. In Proc. the ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, August 2009, pp.63-74.
Crossref
[4]

Liao Y, Yin J, Yin D, Gao L. DPillar: Dual-port server interconnection network for large scale data centers. Computer Networks, 2012, 56(8): 2132-2147.
Crossref Google Scholar
[5]

Guo D, Chen T, Li D, Li M, Liu Y, Chen G. Expandable and cost-effective network structures for data centers using dual-port servers. IEEE Transaction on Computers, 2013, 62(7): 1303-1317.
Crossref Google Scholar
[6]
Li D, Wu J. On the design and analysis of data center network architectures for interconnecting dual-port servers. In Proc. the 2004 IEEE Conference on Computer Communications, April 2014, pp.1851-1859.
Crossref
[7]
Li D, Wu J, Liu Z, Zhang F. Dual-centric data center network architectures. In Proc. the 44th International Conference on Parallel Processing, September 2015, pp.679-688.
Crossref
[8]

Wang X, Fan J, Lin C K, Zhou J, Liu Z. BCDC: A high-performance, server-centric data center network. Journal of Computer Science and Technology, 2018, 33(2): 400-416.
Crossref Google Scholar
[9]
Leighton F T. Introduction to Parallel Algorithms and Architecture: Arrays Trees Hypercubes (1st edition). Morgan Kaufmann Pub, 1991.
Crossref
[10]
Xu J. Topological Structure and Analysis of Interconnection Networks. Springer, 2002.
Crossref
[11]

Xu J M, Ma M. Survey on path and cycle embedding in some networks. Frontiers of Mathematics in China, 2009, 4(2): 217-252.
Crossref Google Scholar
[12]

Xu D, Fan J, Jia X, Zhang S, Wang X. Hamiltonian properties of honeycomb meshes. Information Sciences, 2013, 240: 184-190.
Crossref Google Scholar
[13]

Xue L, Yang W, Zhang S. Number of proper paths in edge-colored hypercubes. Applied Mathematics and Computation, 2018, 332: 420-424.
Crossref Google Scholar
[14]

Lv M, Zhou S, Sun X, Lian G, Liu J. Reliability of (n,k)-star network based on g-extra conditional fault. Theoretical Computer Science, 2019, 757: 44-55.
Crossref Google Scholar
[15]

Lin L, Xu L, Huang Y, Xiang Y, He X. On exploiting priority relation graph for reliable multi-path communication in mobile social networks. Information Sciences, 2019, 477: 490-507.
Crossref Google Scholar
[16]

Li X J, Liu B, Ma M, Xu J M. Many-to-many disjoint paths in hypercubes with faulty vertices. Discrete Applied Mathematics, 2017, 217: 229-242.
Crossref Google Scholar
[17]

Sabir E, Meng J. Parallel routing in regular networks with faults. Information Processing Letters, 2019, 142: 84-89.
Crossref Google Scholar
[18]
Fujita S, Araki T. Three-round adaptive diagnosis in binary n-cubes. In Proc. the 15th International Symposium on Algorithms and Computation, December 2004, pp.442-451.
Crossref
[19]

Ye L C, Liang J R. Five-round adaptive diagnosis in Hamiltonian networks. IEEE Transaction on Parallel and Distributed Systems, 2015, 26(9): 2459-2464.
Crossref Google Scholar
[20]
Lin X, Ni L M. Deadlock-free multicast wormhole routing in multicomputer networks. In Proc. the 18th Annual International Symposium on Computer Architecture, May 1991, pp.116-125.
Crossref
[21]
Bahrebar P, Stroobandt D. The Hamiltonian-based odd-even turn model for adaptive routing in interconnection networks. In Proc. the 2013 International Conference on Reconfigurable Computing and FPGAs, December 2013.
Crossref
[22]

Yang Y, Zhang L. Fault-tolerant-prescribed Hamiltonian laceability of balanced hypercubes. Information Processing Letters, 2019, 145: 11-15.
Crossref Google Scholar
[23]

Liu H, Hu X, Gao S. Hamiltonian cycles and paths in faulty twisted hypercubes. Discrete Applied Mathematics, 2019, 257: 243-249.
Crossref Google Scholar
[24]

Zhou S, Xu J M. Conditional fault tolerance of arrangement graphs. Information Processing Letters, 2011, 111(21): 1037-1043.
Crossref Google Scholar
[25]

Wang X, Fan J, Zhou J, Lin C K. The restricted h-connectivity of the data center network DCell. Discrete Applied Mathematics, 2016, 203: 144-157.
Crossref Google Scholar
[26]

Tsai C H, Tan J J M, Liang T, Hsu L H. Fault-tolerant hamiltonian laceability of hypercubes. Information Processing Letters, 2002, 83(6): 301-306.
Crossref Google Scholar
[27]
Liu M, Liu H. Conditional edge-fault-tolerant hamiltonicity of enhanced hypercube. In Proc. the 2011 International Conference on Computer Science and Service System, June 2011, pp.297-300.
Crossref
[28]

Lee C W, Lin T J, Hsieh S Y. Hamiltonicity of product networks with faulty elements. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(9): 2318-2331.
Crossref Google Scholar
[29]

Hsieh S Y, Lee C W, Huang C H. Conditional edge-fault hamiltonian-connectivity of restricted hypercube-like networks. Information and Computation, 2016, 251: 314-334
Crossref Google Scholar
[30]

Lv Y, Lin C K, Fan J, Jia X. Hamiltonian cycle and path embeddings in 3-ary n-cubes based on K1, 3-structure faults. Journal of Parallel and Distributed Computing, 2018, 120: 148-158.
Crossref Google Scholar
[31]

Wang X, Erickson A, Fan J, Jia X. Hamiltonian properties of DCell networks. The Computer Journal, 2015, 58(11): 2944-2956.
Crossref Google Scholar
[32]

Qin X, Hao R. Conditional edge-fault-tolerant Hamiltonicity of the data center network. Discrete Applied Mathematics, 2018, 247: 165-179.
Crossref Google Scholar
[33]

Li X, Fan J, Lin C K, Jia X. Diagnosability evaluation of the data center network DCell. The Computer Journal, 2017, 61(1): 129-143.
Crossref Google Scholar
[34]
Hsu L H, Lin C K. Graph Theory and Interconnection Networks (1st edition). CRC press, 2008.
Crossref
[35]

Tsai C H, Tan J J M, Liang T, Hsu L H. Fault-tolerant Hamiltonian laceability of hypercubes. Information Processing Letters, 2002, 83(6): 301-306.
Crossref Google Scholar
[36]
Hsieh S Y, Lin T J. Super fault-tolerant Hamiltonicity of product networks. In Proc. the 2010 IEEE International Symposium on Parallel and Distributed Processing with Applications, September 2010, pp.236-243.
Crossref
[37]

Cheng C W, Lee C W, Hsieh S Y. Conditional edge-fault Hamiltonicity of Cartesian product graphs. IEEE Transactionson Parallel and Distributed Systems, 2013, 24(10): 1951-1960.
Crossref Google Scholar
[38]

Bhuyan L N, Agrawal D P. Generalized hypercube and hyperbus structures for a computer network. IEEE Transactions on Computers, 1984, 33(4): 323-333.
Crossref Google Scholar
[39]

Hsu H C, Li T K, Tan J J M. Fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graphs. IEEE Transactions on Computers, 2004, 53(1): 39-53.
Crossref Google Scholar
Journal of Computer Science and Technology
Volume 35 Issue 5,
September 2020
Pages 1064-1083
DOI: 10.1007/s11390-020-9508-3
Cite this article:
Wang G-J, Lin C-K, Fan J-X, et al. Fault-Tolerant Hamiltonicity and Hamiltonian Connectivity of BCube with Various Faulty Elements. Journal of Computer Science and Technology, 2020, 35(5): 1064-1083. https://doi.org/10.1007/s11390-020-9508-3

397

Views

15

Crossref

N/A

Web of Science

13

Scopus

1

CSCD

Altmetrics
Received: 25 February 2019
Revised: 24 November 2019
Published: 30 September 2020
©Institute of Computing Technology, Chinese Academy of Sciences 2020
Return