We use cookies to improve your experience with our site.

在考虑各种故障元素的情况下BCube网络的容错哈密顿性质和容错哈密顿连通性

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

  • 摘要: BCube是一种重要的数据中心网络。哈密顿性质和哈密顿连通性在通信网络中具有重要的应用。到目前为止,在数据中心网络中,有许多的研究成果是关于容错哈密顿性质和容错哈密顿连通性的。然而,这些成果仅仅考虑在数据中心网络中链路和服务器发生故障的情况。在本文中,我们研究了服务器、链路、和交换机三种元素发生故障的情况下BCuben,k),的容错哈密顿性质和容错哈密顿连通性。对于任意整数n≥2和k≥0,设BCn,kBCuben,k)的逻辑结构,而F为故障元素的集合。假设fvfefs分别是BCn,k中故障服务器,故障链路和故障交换机的数量。我们证明了,如果fv+fe+(n-1)fs≤(n-1)(k+1)-2,那么BCn,k-F是容错哈密顿的。若fv+fe+(n-1)fs≤(n-1)(k+1)-3,则BCn,k-F是容错哈密顿连通的。据我们所知,本文是第一项在数据中心网络中将交换机作为故障元素后研究容错哈密顿性质和容错哈密顿连通性的工作。本文的研究结果表明,要保障BCn,k中存在无故障的哈密顿圈和无故障的哈密顿路径时,与传统方法相比,BCn,k在可以容许的故障元素方面有了显著的提升。此外,本文的结论也可用于HyperX网络。

     

    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.

     

/

返回文章
返回