BCCC Disjoint Path Construction Algorithm and Fault-Tolerant Routing Algorithm under Restricted Connectivity

Autor: Jialiang Lu, Xiaoyu Du, Huiping Li, Zhijie Han
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Algorithms, Vol 15, Iss 12, p 481 (2022)
Druh dokumentu: article
ISSN: 15120481
1999-4893
DOI: 10.3390/a15120481
Popis: Connectivity in large-scale data center networks is a critical indicator to evaluate network state. A feasible and performance-guaranteed algorithm enables us to find disjoint paths between network vertices to ensure effective data transfer and to maintain the normal operation of network in case of faulty nodes. As an important data center network, BCube Connected Crossbars (BCCC) has many excellent properties that have been widely studied. In this paper, we first propose a vertex disjoint path algorithm with the time complexity of O(nk) in BCCC, where n denotes a switch connected to n servers and k denotes dimension. Then, we prove that the restricted connectivity of BCCC(n,k). Finally, we present an O(knκ1(G)) fault-free algorithm in BCCC, where κ1(G) is the restricted connectivity. This algorithm can obtain a fault-free path between any two distinct fault-free vertices under the condition that each vertex has at least one fault-free neighbor in the BCCC and a set of faulty vertices F with |F|<κ1(G).
Databáze: Directory of Open Access Journals
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje