Reliable Communication Performance of Recursive Networks Based on Inter-Subgraph Matching

Large-scale parallel and distributed applications and platforms rely heavily on high-performance network architectures, which greatly emphasize factors including network latency, bandwidth, communication reliability (e.g., connectivity and fault-tolerant routing), etc. Due to the expansion of network scales and the increase of component failures, the demand for the network’s high reliability has grown substantially. Enhancing fault tolerance is the key to improving the network’s reliability, which can be achieved by establishing the connectivity under the “<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$</tex-math> </inline-formula>-good-neighbor condition”. In the presence of component failures, to maintain normal network operation and minimize communication delays, effective fault-tolerant routing strategies are required. This paper proposes a new class of recursive networks with small diameter, named generalized recursive match networks (GRMNs). GRMNs include well-known networks like generalized hypercubes, BC networks, BCube, HyperX, FBFLY, 2DFB, etc, and other future networks. We investigate the classical connectivity and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$</tex-math> </inline-formula>-good-neighbor connectivity (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g\geq 0$</tex-math> </inline-formula>) of the GRMN. In addition, we present an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(N)$</tex-math> </inline-formula> fault-tolerant unicast routing algorithm with the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$</tex-math> </inline-formula>-good-neighbor faulty set, called F-TRouting, where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> is the number of edges in the GRMN. The algorithm and results can be directly applied to all networks falling within the description of GRMNs, including generalized hypercubes, BC networks, BCube, HyperX, FBFLY, 2DFB, and other future networks. Finally, we give simulation experiment results on the performances of the GRMN and the F-TRouting algorithm, which demonstrate that the GRMN and the F-TRouting have advantageous performances.