TY - JOUR

T1 - Completely Independent Spanning Trees on BCCC Data Center Networks with an Application to Fault-Tolerant Routing

AU - Li, Xiao Yan

AU - Lin, Wanling

AU - Liu, Ximeng

AU - Lin, Cheng Kuan

AU - Pai, Kung Jui

AU - Chang, Jou Ming

N1 - Publisher Copyright:
© 1990-2012 IEEE.

PY - 2022/8/1

Y1 - 2022/8/1

N2 - A set of k spanning trees in a graph G are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices x and y in any two trees have neither vertex nor edge in common, except for x and y. The existence of multiple CISTs in the underlying graph of a network has applications in fault-tolerant broadcasting and secure message distribution. In this paper, we investigate the construction of CISTs in a server-centric data center network called BCube connected crossbars (BCCC), which can provide good network performance using inexpensive commodity off-the-shelf switches and commodity servers with only two network interface card (NIC) ports. The significant advantages of BCCC are its good expandability, lower communication latency, and higher robustness in component failure. Based on the structure of compound graphs of BCCC, we provide efficient algorithms to construct\lceil\frac{n}{4}\rceil$⌈n4⌉ CISTs in the logical graph of BCCC, denoted by LL-BCCC(n,k)BCCC(n,k), for n ≥ 5. As a by-product, we obtain a fault-tolerant routing that takes the constructed CISTs as its routing table. We then evaluate the performance of the fault-tolerant routing through simulation results.

AB - A set of k spanning trees in a graph G are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices x and y in any two trees have neither vertex nor edge in common, except for x and y. The existence of multiple CISTs in the underlying graph of a network has applications in fault-tolerant broadcasting and secure message distribution. In this paper, we investigate the construction of CISTs in a server-centric data center network called BCube connected crossbars (BCCC), which can provide good network performance using inexpensive commodity off-the-shelf switches and commodity servers with only two network interface card (NIC) ports. The significant advantages of BCCC are its good expandability, lower communication latency, and higher robustness in component failure. Based on the structure of compound graphs of BCCC, we provide efficient algorithms to construct\lceil\frac{n}{4}\rceil$⌈n4⌉ CISTs in the logical graph of BCCC, denoted by LL-BCCC(n,k)BCCC(n,k), for n ≥ 5. As a by-product, we obtain a fault-tolerant routing that takes the constructed CISTs as its routing table. We then evaluate the performance of the fault-tolerant routing through simulation results.

KW - BCube connected crossbars (BCCC)

KW - Completely independent spanning trees (CISTs)

KW - compound graphs

KW - data center networks (DCNs)

KW - server-centric DCNs

UR - http://www.scopus.com/inward/record.url?scp=85121388641&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2021.3133595

DO - 10.1109/TPDS.2021.3133595

M3 - Article

AN - SCOPUS:85121388641

VL - 33

SP - 1939

EP - 1952

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 8

ER -