Fault-tolerant unicast paths constructive algorithms in a family of recursive networks

ABSTRACT

In parallel and distributed systems, interconnection networks and data center networks are two crucial networks. They are also crucial parts of high-performance computing and cloud computing services. With the rapid growth of high-performance computing and cloud computing, both networks are growing in size. At the same time, vertex faults are unavoidable. In computer/communication networks, unicast refers to one-to-one communication between the source vertex and the destination vertex. Fault-tolerant routing of vertices in networks is an important problem that has been widely discussed. In this paper, for a class of recursive networks with less than $\mathit{g}$-restrict connectivity fault vertices and each fault-free vertex having at least $\mathit{g}$ fault-free neighbors, we provide a fault-tolerant unicast path design algorithm in this study. The algorithm’s correctness is then demonstrated and its time complexity is analyzed. In addition, the results obtained can be used for unknown and known networks, including the dragonfly network, DCell, and generalized DCell.

CO EDITOR-IN-CHIEF:

• Hsieh, Sun-Yuan

ASSOCIATE EDITOR:

• Hsieh, Sun-Yuan

KEYWORDS:

• $\mathit{G}$-restrict connectivity
• dragonfly network
• DCell

Nomenclature

CGRN	=	complete graph-based recursive network
DCN	=	data center network
$d_G(\mathit{w})$	=	the degree of vertex $\mathit{w}$in $\mathit{G}$
$\mathit{G}[\mathit{U}]$	=	a subgraph of $\mathit{G}$induced by $\mathit{U}$
$\mathit{G}-\mathit{W}$	=	the subgraph of $\mathit{G}$by deleting the vertex of $\mathit{W}$
IN	=	interconnection network
$\mathit{\kappa }(\mathit{G})$	=	graph $\mathit{G}$’s connectivity
${\kappa }^g(\mathit{G})$	=	graph $\mathit{G}$’s $\mathit{g}$-restricted connectivity
MIN	=	multiprocessor interconnection network
$N_G(\mathit{u})$	=	the set of neighbors of vertex $\mathit{u}$
$N_G(\mathit{U})$	=	be the set of neighbors of vertex subset $\mathit{U}\subset \mathit{V}(\mathit{G})$
$Q_n^k$	=	$\mathit{k}$-ary $\mathit{n}$-cube
SIN	=	switch interconnection network
$\mathit{T}=(z_1,z_2,\dots ,z_{\mathit{m}+1})$	=	a path of length $\mathit{m}$
$\mathit{\delta }(\mathit{G})$	=	the minimum degree of $\mathit{G}$
$\mathrm{\Delta }(\mathit{G})$	=	the maximum degree of $\mathit{G}$
$⟨n_{\mathit{r}-1}⟩$	=	the set of the positive integers $1,2,\dots ,n_{\mathit{r}-1}$

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the National Natural Science Foundation of China under Grant [No. 62172291, U1905211, 62272333], the Postgraduate Research & Practice Innovation Program of Jiangsu Province [No. KYCX23_3258].