Three edge-disjoint Hamiltonian cycles in crossed cubes with applications to fault-tolerant data broadcasting

Abstract

Multiple edge-disjoint Hamiltonian cycles (EDHCs) provide the advantages of data broadcast in parallel and edge fault-tolerance in network communications. This paper investigates how to construct more EDHCs in a hypercube-variant network called crossed cube, denoted as $CQ_n$. The topology of $CQ_n$ has more wealth than normal hypercubes in network properties, e.g., it has about half of the diameter of a hypercube with the same dimension. Then, we obtain the following results in this paper: (1) We first provide the construction of three EDHCs in $CQ_6$. (2) According to the recursive structure of $CQ_n$, we prove by induction that there exist also three EDHCs in $CQ_n$ for $n\geqslant 7$. (3) Finally, we evaluate the performance of data broadcasting by simulation through three EDHCs and compare it against the best previous result in [18] using two EDHCs. In particular, our findings significantly improved the average success rate in edge fault-tolerant data broadcasting and two specific metrics concerning the broadcasting delivery time (latency).

1 Introduction

The ring structure is essential for high-performance computing architecture, which is often used as the baseband for data transmission in interconnection networks and control flow in parallel and distributed environments. Many efficient algorithms with low communication costs have been developed based on the ring structure [1,2,3,4]. To acquire a ring structure passing through every node in a network, it relies on Hamiltonian cycles in the corresponding network topology. In particular, edge-disjoint Hamiltonian cycles (EDHCs for short) can provide advantages in many applications, as described below.

Consider the all-to-all communication in a network system with n nodes, where every node needs to send a distinct message to all other nodes. Applying a ring structure, once a message starts sending, a node can receive a new message from the previous node at each step, keeps a copy of the new message for itself, and sends the received message to the next node. Thus, the process can be done through $n-1$ steps. Suppose that the system now contains multiple EDHCs. Then, a message can be partitioned into small packets (e.g., called “frames" in Ethernet), each of which can be sent along the multiple EDHCs. Therefore, the time required for transmission can be reduced. That is, adopting multiple EDHCs as broadband channels in a network can provide multiple data signals/streams simultaneously at the same time in parallel and provide advantages of data transmission. Furthermore, one way to achieve fault-tolerant interprocessor communication is by effectively utilizing disjoint paths between source and destination node pairs. Especially when considering link failure tolerance, the technique of using edge-disjoint paths is a common strategy. Thus, if a fault occurs on one edge of a Hamiltonian cycle, the message can be transmitted along another Hamiltonian cycle. Accordingly, constructing multiple EDHCs has applications to enhance edge fault-tolerant capability in data transmission [5,6,7].

Networks are usually modeled as undirected simple graphs $G=(V,E)$, where the node set $V(=V(G))$ and the edge set $E(=E(G))$ represent the set of processors and the set of communication channels between processors, respectively. A cycle in a graph that contains every node exactly once is called a Hamiltonian cycle. A graph is Hamiltonian if it possesses a Hamiltonian cycle. Two cycles in a graph are edge-disjoint (resp. node-disjoint) if they share no common edge (resp. common node). It is well-known that finding a Hamiltonian cycle in a graph is an NP-hard problem [8], let alone the problem of finding multiple EDHCs.

Some previous works related to the construction of multiple EDHCs in specific networks are described below. The known existence of two EDHCs include butterfly networks [9], Gaussian networks [10], locally twisted cubes [11, 12], balanced hypercubes [13], augmented cubes [14], twisted cubes [15], parity cubes [16], crossed cubes [17, 18], and some kinds of hypercube-like networks [18] etc. However, so far, only a few studies have been devoted to constructing more than two EDHCs on specific networks. Hussain et al. [19] gave a construction of three EDHCs in Eisenstein-Jacobi networks. Hung [18] showed that the n-dimensional transposition networks for $n\geqslant 5$ contains four EDHCs. For concerning the existence of more EDHCs in graphs or networks, please refer to [20] for hypertournaments, [21] for WK-recursive networks, [5] for hypercubes and k-ary n-cubes, and [22] for generalized hypercubes.

This paper studies the problem of constructing three EDHCs in a class of hypercube-variant networks called crossed cubes and denoted by $CQ_n$ (see Definition 1). As constructing beyond two EDHCs in $CQ_n$ for $n\geqslant 6$ is currently an open problem, our study of demonstrating the existence of three EDHCs on $CQ_n$ is a theoretical breakthrough. This result improves the previous ones of Pai [17] and Hung [18] in terms of quantity of Hamiltonian cycles, where the former first designed a recursive algorithm to construct two EDHCs of $CQ_n$ in $\mathcal O(n2^n)$ time when $n\geqslant 4$, and the latter presented an elegant parallel construction to yield two EDHCs in ${\mathcal {O}}(n)$ time using $2^n$ nodes of $CQ_n$ as processors. Using the three EDHCs in $CQ_n$ as the transmission channels, we can easily carry out an edge fault-tolerant broadcast from an arbitrary node. In addition, using three EDHCs instead of two EDHCs can improve the performance of fault-tolerant and latency in data broadcasting.

So far, the Hamiltonicity of the crossed cube has been studied extensively in the literature. For instance, research on fault-tolerant Hamiltonicity (or pancyclicity) [23,24,25,26], Hamiltonicity with conditional link faults [27, 28], and Hamiltonicity (or panconnectedness) with required nodes in the fixed positions [29, 30]. Excepting the above research, the recent issues that have paid more attention to crossed cubes are the construction of multiple spanning trees [31,32,33,34,35,36,37,38], node-to-set disjoint paths [39], and the study of (conditional) diagnosability [40, 41]. For more properties and results of $CQ_n$, the reader can refer to [42, 43].

The rest of the paper is organized as follows. Section 2 formally gives the definition of crossed cubes and introduces a previous result showing two EDHCs of $CQ_4$. Section 3 presents how to construct three EDHCs of $CQ_6$. Section 4 provides a recursive algorithm to construct three EDHCs of $CQ_n$ for $n\geqslant 7$. Section 5 simulates edge fault-tolerant data broadcasting in $CQ_n$ for $6\leqslant n\leqslant 10$ and compares the experimental performance with the best previous results. Finally, the concluding remarks are given in the last section.

2 Preliminaries

Suppose that G is a labeled graph whose nodes are associated with distinct binary strings, and let $G^x$ be the graph obtained from G by prefixing the binary string on every node with x. Efe [44] defined two binary strings $x=x_1x_0$ and $y=y_1y_0$ to be pair-related, denoted $x\sim y$, if and only if $(x,y)\in \{(00,00),(10,10),(01,11),(11,01)\}$.

Definition 1

(Efe [44].) The n-dimensional crossed cube $CQ_n$ is the labeled graph with the following recursive fashion:

• (1) $CQ_1$ is the complete graph on two nodes with labels 0 and 1.

• (2) For $n\geqslant 2$, $CQ_n$ is composed of two subcubes $CQ_{n-1}^0$ and $CQ_{n-1}^1$ such that two nodes $x=0x_{n-2}\cdots x_1x_0\in V(CQ_{n-1}^0)$ and $y=1y_{n-2}\cdots y_1y_0\in V(CQ_{n-1}^1)$ are joined by an edge if and only if

  • $x_{n-2}=y_{n-2}$ if n is even, and

  • $x_{2i+1}x_{2i}\sim y_{2i+1}y_{2i}$ for $0\leqslant i<\lfloor (n-1)/2\rfloor$,

  where x and y are called the $(n-1)$-neighbors to each other, and denote as $N_{n-1}(x)=y$ or $N_{n-1}(y)=x$.

For conciseness of representation, sometimes the labels of nodes are changed to the use of decimal. For instance, Fig. 1 shows two EDHCs of the 4-dimensional crossed cube $CQ_4$ that was provided in [17], where each node is labeled by the binary code and its corresponding decimal (inside the circle). We can see that each Hamiltonian cycle in $HC_1$ and $HC_2$ contains 16 distinct edges, of which eight edges are evenly distributed in four subcubes $CQ_2^{00}$, $CQ_2^{01}$, $CQ_2^{10}$, and $CQ_2^{11}$, and then through eight different outer edges are joined to form a Hamiltonian cycle of $CQ_4$.

Fig. 1

Two EDHCs $HC_1$ and $HC_2$ in $CQ_4$, where thick lines indicate edges of cycles

3 Three edge-disjoint Hamiltonian cycles in $CQ_6$

In this section, we first give two EDHCs of $CQ_6$ that were built from [17]. Then, we fine-tune some edges in the second Hamiltonian cycle so that the remaining edges are sufficient to construct the third Hamiltonian cycle.

A cycle with length $\ell$ is said to be an $\ell$-cycle. Let C be a cycle. For notational convenience, we write $e\in C$ instead of $e\in E(C)$. Let $HC_1$ and $HC_2$ be two EDHCs of $CQ_4$ (see Fig. 1). By the recursive structure in Definition 1, $CQ_6$ can be decomposed into four copies of $CQ_4$, and each copy has two Hamiltonian cycles mentioned above. Hence, Pai [17] provided the following way to construct two Hamiltonian cycles of $CQ_6$. Partition $CQ_6$ into four disjoint subcubes $CQ_4^{ij}$ for $i,j\in \{0,1\}$, and let $HC_k^{ij}$ for $k\in \{1,2\}$ be the corresponding kth Hamiltonian cycle in the subcube $CQ_4^{ij}$ such that each cycle maps to $HC_k$ in $CQ_4$. For each $k=1,2$, since each subcube contains Hamiltonian cycles passing through distinct nodes, the four Hamiltonian cycles in the subcubes are easily constructed in a parallel fashion. Then, the two Hamiltonian cycles of $CQ_6$, say ${\mathcal {H}}{\mathcal {C}}_1$ and ${\mathcal {H}}{\mathcal {C}}_2$, can be constructed from the merge of $HC_k^{ij}$ for $k=1,2$ by adjusting four edges in each cycle, which are described as follows:

$$\begin{aligned} E({\mathcal {H}}{\mathcal {C}}_1)= & {} \bigg (\bigcup _{i,j\in \{0,1\}}E(HC_1^{ij})\bigg ) \cup \,\{(0,32),(8,24),(16,48),(40,56)\} \nonumber \\&-\,\{(0,8),(16,24),(32,40),(48,56)\} \end{aligned}$$

(1)

and

$$\begin{aligned} E({\mathcal {H}}{\mathcal {C}}_2)= & {} \bigg (\bigcup _{i,j\in \{0,1\}}E(HC_2^{ij})\bigg ) \cup \,\{(2,34),(10,26),(18,50),(42,58)\} \nonumber \\&-\,\{(2,10),(18,26),(34,42),(50,58)\}. \end{aligned}$$

(2)

For instance, Fig. 2 depicts the Hamiltonian cycle ${\mathcal {H}}{\mathcal {C}}_1$ of $CQ_6$ constructed from Eq. (1). From the drawing, we may imagine that two dashed lines (horizontal and vertical) partition the whole $CQ_6$ into four subcubes with equal size, where nodes in the upper part and lower part (resp. left part and right part) are mirrored, and their labels have the difference $\pm 16$ (resp. $\pm 32$). Due to saving the space, we omit the drawing of ${\mathcal {H}}{\mathcal {C}}_2$ constructed from Eq. (2). However, since certain edges are contained in $HC_2$ (see Fig. 1), we can be sure that some corresponding edges exist in ${\mathcal {H}}{\mathcal {C}}_2$, e.g., we have the following mapping of edges from $HC_2$ to ${\mathcal {H}}{\mathcal {C}}_2$:

Fig. 2

The Hamiltonian cycle ${\mathcal {H}}{\mathcal {C}}_1$ of $CQ_6$ constructed from Eq. (1), where thick lines indicate edges of the cycle

$$\begin{aligned} (8,12)\in HC_2\rightarrow & {} (56,60)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +48\\ (4,5)\in HC_2\rightarrow & {} (20,21)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +16 \\ (15,9)\in HC_2\rightarrow & {} (63,57)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +48 \\ (11,1)\in HC_2\rightarrow & {} (27,17)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +16 \\ (3,5)\in HC_2\rightarrow & {} (51,53)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +48 \\ (5,4)\in HC_2\rightarrow & {} (\,\;5,\,\;4)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +0 \\ (12,14)\in HC_2\rightarrow & {} (44,46)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +32 \\ (6,14)\in HC_2\rightarrow & {} (54,62)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +48 \\ (6,7)\in HC_2\rightarrow & {} (38,39)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +32 \\ (13,7)\in HC_2\rightarrow & {} (61,55)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +48 \\ (13,15)\in HC_2\rightarrow & {} (45,47)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +32 \\ (15,9)\in HC_2\rightarrow & {} (47,41)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +32 \\ (11,1)\in HC_2\rightarrow & {} (59,49)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +48 \\ (3,2)\in HC_2\rightarrow & {} (19,18)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +16 \\ (10,8)\in HC_2\rightarrow & {} (26,24)\in {\mathcal {H}}{\mathcal {C}}_2\qquad \text {//} +16 \\ \end{aligned}$$

Let A be the set consisting of the above fifteen edges in ${\mathcal {H}}{\mathcal {C}}_2$. Since $CQ_6$ contains 192 edges, it has the remaining 64 edges after removing two EDHCs ${\mathcal {H}}{\mathcal {C}}_1$ and ${\mathcal {H}}{\mathcal {C}}_2$. With brute force checking, we can find that $E(CQ_6)-\{E({\mathcal {H}}{\mathcal {C}}_1)\cup E({\mathcal {H}}{\mathcal {C}}_2)\}$ includes two 8-cycles and twelve 4-cycles, and all these cycles are node-disjoint. We list all fourteen cycles in detail as follows:

$$\begin{aligned} &C_1=(56,48,32,40,8,0,16,24,56),\qquad &C_2=(60,36,12,20,60),\\ &C_3=(21,15,37,63,21), \qquad \qquad &C_4 =(57,43,9,27,57),\\ &C_5=(17,3,33,51,17), \qquad \qquad &C_6 =(53,31,5,47,53),\\ &C_7=(4,28,52,44,4), \qquad \qquad &C_8 =(46,6,30,54,46),\\ &C_9=(62,22,14,38,62), \qquad \qquad &C_{10} =(39,61,23,13,39),\\ &C_{11}=(55,29,7,45,55),\qquad \qquad &C_{12}=(11,25,59,41,11),\\ &C_{13}=(35,1,19,49,35),\qquad \qquad \qquad &C_{14}=(2,10,42,34,50,58,26,18,2). \end{aligned}$$

Let B be the set of edges picking from these cycles:

$$\begin{aligned} &(24,56)\in C_1, \, \qquad (20,60)\in C_2, \;\qquad (63,21)\in C_3,\\ &(27,57)\in C_4, \, \qquad (51,17)\in C_5, \;\qquad (5,47),(47,53)\in C_6,\\ &(44,\;\,4)\in C_7, \, \qquad (54,46)\in C_8, \;\qquad (38,62)\in C_9,\\ &(39,61)\in C_{10}, \qquad (45,55)\in C_{11}, \qquad (59,41)\in C_{12},\\ &(19,49)\in C_{13}, \qquad (26,18)\in C_{14}. \end{aligned}$$

Note that we pick two edges of $C_6$ in B, and thus B contains fifteen edges.

The third Hamiltonian cycle of $CQ_6$, say ${\mathcal {H}}{\mathcal {C}}_3$, can be constructed as follows (see Fig. 3 for illustration):

$$\begin{aligned} E({\mathcal {H}}{\mathcal {C}}_3)=\bigg (\bigcup _{i=1}^{14}E(C_i)-B\bigg )\cup A. \end{aligned}$$

(3)

Fig. 3

The Hamiltonian cycle ${\mathcal {H}}{\mathcal {C}}_3$ of $CQ_6$ constructed from Eq. (3)

Figure 3 illustrates the construction of ${\mathcal {H}}{\mathcal {C}}_3$, where the bold lines indicate the edges belonging to A, which will be added to the edge set of ${\mathcal {H}}{\mathcal {C}}_3$. While lines with cross marks are edges belonging to B, which will be removed from ${\mathcal {H}}{\mathcal {C}}_3$. In fact, the construction of the third Hamiltonian cycle mentioned above is done using the edge-swapping technique. Therefore, with the above adjustments, we need to modify the edge set of ${\mathcal {H}}{\mathcal {C}}_2$ obtained from Eq. (2) by swapping two edge sets, A and B, as follows (see Fig. 4 for illustration):

$$\begin{aligned} E({\mathcal {H}}{\mathcal {C}}_2)=(E({\mathcal {H}}{\mathcal {C}}_2)-A)\cup B. \end{aligned}$$

(4)

Fig. 4

The Hamiltonian cycle ${\mathcal {H}}{\mathcal {C}}_2$ of $CQ_6$ constructed from Eq. (4)

Similarly, in Fig. 4, the bold lines indicate the edges of B that will be added, while lines with cross marks are edges of A that will be removed in the construction. We now easily check $\{u,v:(u,v)\in A\}=\{u,v:(u,v)\in B\}$, i.e., the unions of ends of edges in the two sets are identical. From an arbitrary starting node, by visiting the paths formed by the edges in Figs. 3 and 4 in sequence, we finally obtain two EDHCs, and hence the result is shown below.

Lemma 1

The three Hamiltonian cycles ${\mathcal {H}}{\mathcal {C}}_i$ for $i=1,2,3$ constructed from Eqs. (1)-(4) are edge-disjoint in $CQ_6$.

Clearly, $|E(CQ_n)|=(nN)/2$, where $N=2^n$ is the number of nodes of $CQ_n$. When $n=6$, we have $N=2^6=64$ and $|E(CQ_6)|=(6\times 64)/2=192$. Since each Hamiltonian cycle contains 64 edges in $CQ_6$, all edges of $CQ_6$ will be exhausted when we construct the above three EDHCs. By Eqs. (1)-(4), the time required in the above construction is proportional to the number of edges, and thus it requires $|E(CQ_6)|=3N=\mathcal {O}(N)$ time.

4 Three edge-disjoint Hamiltonian cycles in $CQ_n$ for $n\geqslant 7$

For constructing three EDHCs in high-dimensional crossed cubes, the results of $CQ_6$ can be viewed as the induction base, and the construction for $CQ_n$, $n\geqslant 7$, will be proceeded by recursion. Before this, we need the following prefatory works.

For $n\geqslant 6$, a node $x=x_{n-1}x_{n-2}\cdots x_1x_0$ in $CQ_n$ is said to be a stable node if $x_{2i+1}x_{2i}\in \{00,10\}$ for all $0\leqslant i<\lfloor n/2\rfloor$. Let $SN_n$ be the set consisting of all stable nodes of $CQ_n$. An edge is called a stable edge in a subgraph of $CQ_n$ provided its two ends are stable nodes. A Hamiltonian cycle of $CQ_n$ is sustainable if it contains a stable edge.

For example, $CQ_6$ contains eight stable nodes as follows:

$SN_6=\{\underline{00}\,\underline{00}\,\underline{00}\, ( 0),\ \underline{00}\,\underline{00}\,\underline{10}\, ( 2),\ \underline{00}\,\underline{10}\,\underline{00}\, ( 8),\ \underline{00}\,\underline{10}\,\underline{10}\, (10)$,

$\hspace{1.4cm}\underline{10}\,\underline{00}\,\underline{00}\, (32),\ \underline{10}\,\underline{00}\,\underline{10}\, (34),\ \underline{10}\,\underline{10}\,\underline{00}\, (40),\ \underline{10}\,\underline{10}\,\underline{10}\, (42)\}$.

Let us check Figs. 2, 4, and 3 to realize whether the three EDHCs obtained in the previous section for $CQ_6$ are sustainable. Since $(0,2)\in {\mathcal {H}}{\mathcal {C}}_1$, $(8,10)\in {\mathcal {H}}{\mathcal {C}}_2$, and $(32,40)\in {\mathcal {H}}{\mathcal {C}}_3$, all three Hamiltonian cycles are indeed sustainable.

For $n\geqslant 7$ and $j\in \{0,1\}$, let $SN_n^j=\{jx:x\in SN_{n-1}\}$. Clearly, from the definition of stable nodes, we have the following recursion.

$$\begin{aligned} SN_n= {\left\{ \begin{array}{ll} SN_{n-1}^0\cup SN_{n-1}^1 &{} \text {if}\ n\!\geqslant \! 7\ \text {is odd};\\ \{jx:x\in SN_{n-2}^0,j\in \{0,1\}\} &{} \text {if}\ n\!\geqslant \! 8\ \text {is even}. \end{array}\right. } \end{aligned}$$

(5)

Lemma 2

For $n\geqslant 7$, if $x\in SN_{n-1}$, then $(0x,1x)\in E(CQ_{n})$.

Proof

Let $x=x_{n-2}x_{n-3}\cdots x_1x_0$ be a stable node of $CQ_{n-1}$. Then, $x_{2i+1}x_{2i}\in \{00,10\}$ for $0\leqslant i<\lfloor (n-1)/2\rfloor$. Clearly, $0x\,(=0x_{n-2}x_{n-3}\cdots x_1x_0)\in V(CQ_{n-1}^0)$ and $1x\,(=1x_{n-2}x_{n-3}\cdots x_1x_0)\in V(CQ_{n-1}^1)$. Since the two nodes 0x and 1x have different only at the leftmost bit, by the pair-related property of crossed cubes, it follows from Definition 1 that $(0x,1x)\in E(CQ_{n})$. $\square$

Suppose that we have constructed three EDHCs $HC_i$ for all $i=1,2,3$ in $CQ_{n-1}$, where $n\geqslant 7$. In what follows, we use Algorithm 1, taking $HC_i$ as the input, to construct the required Hamiltonian cycle ${\mathcal {H}}{\mathcal {C}}_i$ for each $i\in \{1,2,3\}$ in $CQ_n$. For notational convenience, we omit the subscript i of the Hamiltonian cycle (see Fig. 5 for illustration.)

Fig. 5

A Hamiltonian cycle ${\mathcal {H}}{\mathcal {C}}$ of $CQ_n$ constructed from Algorithm 1

We now show that Hamiltonian cycles described in Algorithm 1 have the following properties.

Lemma 3

For odd $n\geqslant 7$, if the Hamiltonian cycle HC of $CQ_{n-1}$ is sustainable, then so is ${\mathcal {H}}{\mathcal {C}}$ of $CQ_{n}$.

Proof

Let $(x,y)\in HC$ be a stable edge in the Hamiltonian cycle HC of $CQ_{n-1}$. Since $x,y\in SN_{n-1}$, Lemma 2 shows the existence of edges (0x, 1x), $(0y,1y)\in E(CQ_{n})$, where $0x,0y\in SN_{n-1}^0$ and $1x,1y\in SN_{n-1}^1$. Since $n\geqslant 7$ is odd, by Eq. (5), it follows that $0x,0y,1x,1y\in SN_n$. Thus, by the construction of Algorithm 1 (see Line 4), the two edges $(0x,1x),(0y,1y)\in {\mathcal {H}}{\mathcal {C}}$ are stable edges. $\square$

Lemma 4

For even $n\geqslant 8$, if the Hamiltonian cycle HC of $CQ_{n-1}$ is sustainable, then so is ${\mathcal {H}}{\mathcal {C}}$ of $CQ_{n}$.

Proof

Since $(n-1)\geqslant 7$ is odd, by Lemma 3, the Hamiltonian cycle HC constructed by Algorithm 1 in $CQ_{n-1}$ contains a specific stable edge (0x, 1x), where $x\in SN_{n-2}$. Let $x'=0x$ and $y'=1x$. Since $x\in SN_{n-2}$, we have $x'(=0x)\in SN_{n-2}^0$ and $y'(=1x)\in SN_{n-2}^1$. Since $n-1$ is odd, it follows $x',y'\in SN_{n-1}$. By Lemma 2, $(0x',1x'),(0y',1y')\in E(CQ_{n})$. Also, since $x'\in SN_{n-2}^0$ and $n\geqslant 8$ is even, by Eq. (5), it follows that $0x',1x'\in SN_n$. Thus, by the construction of Algorithm 1 (see Line 4), the edge $(0x',1x')\in {\mathcal {H}}{\mathcal {C}}$ is a stable edge. $\square$

The three sustainably EDHCs of $CQ_6$ are the base of the recursive construction. The correctness of constructing sustainably Hamiltonian cycles for high-dimensional crossed cubes in Algorithm 1 is directly followed from the induction rules described in Lemmas 3 and 4. The edge-disjoint property is evident because the distinct Hamiltonian cycles ${\mathcal {H}}{\mathcal {C}}_i$ obtained in $CQ_{n}$ are derived from the EDHCs $HC_i$ of $CQ_{n-1}$. Also, the construction of each Hamiltonian cycle is in a linear time. Therefore, we have the following main result.

Theorem 1

For $n\geqslant 6$, there exist three edge-disjoint Hamiltonian cycles in $CQ_n$. In particular, each Hamiltonian cycle can be constructed in $\mathcal {O}(N)$ time, where $N=2^n$ is the number of nodes in $CQ_n$.

5 Simulation of data broadcasting using multiple EDHCs

This section aims to simulate data broadcasting using multiple EDHCs as the transmission channels in crossed cubes. We compare our results against those of Hung [18] by analyzing the performance using three or two EDHCs. Particularly, we evaluate the capability of fault tolerance by the average success rate in broadcasting with multiple edge failures. In addition, we also assess the efficiency through two metrics related to the broadcasting delivery time (or call the broadcasting latency) in the experiment.

The networks dealt with by the simulation are $CQ_n$ for $n\in \{6,7,8,9,10\}$. Technically, algorithms of constructing EDHCs and of simulating data broadcasting are implemented using C programs. We proceed the experiment by using a 3.60GHz $\text {Intel}^{\circledR } \text {Core}^\text {TM}$ i7-8700 CPU and 8 GB RAM under the Linux operating system.

5.1 Evaluation of average success rate in fault-tolerant data broadcasting

Firstly, we are interested in evaluating the average success rate (ASR for short), which is the ratio of the number of successful data broadcasts over generated instances. Let F be the set of faulty edges and the number of edge in F considered in this section is within the range between 1 and 10. Here we carry out $10^{8}$ simulation instances for each situation. The source node of broadcasting and the set of faulty edges are randomly generated by the uniform distribution over the whole network $CQ_n$ for $6\leqslant n\leqslant 10$.

Tables 1 and 2 show the simulation results of ASR for data broadcasting in crossed cubes $CQ_n$ adopting Hung’s two EDHCs [18] and our three EDHCs as the broadcasting channels, respectively.

In addition, two quantities, namely hit rate (HR for short) and density of non-Hamiltonian edges (DnHe for short) are compared (see the two rightmost columns in the tables). The former refers to the ratio of randomly generated edge failures that occur on non-Hamiltonian cycles, and the latter means the ratio of the edges of non-Hamiltonian cycles to the entire network. Let t be the number of EDHCs simulated in the experiment, and let $e_j$ denote the faulty edge in the jth simulation (where $1\leqslant j\leqslant 10^{8}$) when $|F|=1$. Specifically, for a certain dimension of crossed cubes $CQ_n$, we use the following formula to compute the hit rate:

$$\begin{aligned} \text {HR}=\sum _{j=1}^{10^{8}}\frac{\prod _{i=1}^{t}(1-{\mathcal {H}}{\mathcal {C}}_i(e_j))}{10^8}, \end{aligned}$$

where ${\mathcal {H}}{\mathcal {C}}_i(e_j)$ is an indicator, i.e., ${\mathcal {H}}{\mathcal {C}}_i(e_j)=1$ if the faulty edge $e_j$ is contained in the ith Hamiltonian cycle, and ${\mathcal {H}}{\mathcal {C}}_i(e)=0$ otherwise. Also, the term DnHe is only depending on n and t as follows:

$$\begin{aligned} \text {DnHe}=\frac{|E(CQ_n)|-\sum _{i=1}^t|E({\mathcal {H}}{\mathcal {C}}_i)|}{|E(CQ_n)|}=1-\frac{t\cdot 2^n}{n\cdot 2^{n-1}}=1-\frac{2t}{n}. \end{aligned}$$

We observe from Tables 1 and 2 that the two quantities HR and DnHe are almost very near or even the same. Figure 6 shows the corresponding trend of the ASR concerning the scales of $CQ_n$ and the number of faulty edges when $t=2$ (i.e., Hung’s two EDHCs in [18]) and $t=3$ (i.e., three EDHCs developed in this paper), respectively.

Table 1 ASR of fault-tolerant data broadcasting in crossed cubes using two EDHCs of Hung [18] under the variation of multiple edge failures

Table 2 ASR of fault-tolerant data broadcasting in crossed cubes using three EDHCs developed in this paper under the variation of multiple edge failures

Fig. 6

The trend of the ASR with respect to the scales of $CQ_n$ for $6\leqslant n\leqslant 10$ and the number of faulty edges $1\leqslant |F|\leqslant 10$: (a) Simulation using two EDHCs of Hung [18]; (b) Simulation using three EDHCs developed in this paper

From Tables 1, 2 and Fig. 6, we are aware of the following three phenomenons:

• Because our result (resp. Hung’s result in [18]) provides three EDHCs (resp. two EDHCs) as broadcasting channels, no matter what scale of $CQ_n$ for $6\leqslant n\leqslant 10$, its transmission can reach 100% success when $|F|=1,2$ (resp. $|F|=1)$. The intuitive idea is that ASR should present a decreasing function to the number of faulty nodes. As expected, all simulations are consistent with this phenomenon. For instance, we take $CQ_{10}$ in Table 2 as an example for illustration. If we ask $\text {ASR}\geqslant 80\%$, then it only permits four faulty nodes, while it can tolerate seven faulty nodes when we allow no more than half of the broadcasts to fail. Accordingly, this means that the least number of edge failures, the larger the corresponding ASR.

• For $|F|>2$, the ASR increases with expanding the scale of $CQ_n$. The reason is evident because when |F| is fixed, the edge failures that occur in Hamiltonian cycles will reduce their probability as the network expands, and thus leading to an increase in the success rate. Similarly, by the reasoning that the density of non-Hamiltonian edges gradually increases as the network grows, the hit rate also increases with the scale of the network.

• To highlight the difference in the performance of ASR using our three EDHCs and Hung’s two EDHCs as broadcasting channels, we take the extreme cases of $CQ_6$ and $CQ_{10}$ as examples to illustrate. Obviously, the former is always better than the latter when $|F|\geqslant 2$ (see Fig. 7). In the low-dimensional $CQ_6$, the amplitude of the ASR difference varies more apparent, but the difference will gradually decrease with the increase of |F|. In contrast, in high-dimensional $CQ_{10}$, the magnitude of the ASR difference is relatively stable with the change of |F|.

Fig. 7

The comparisons of ASR between our three EDHCs and Hung’s two EDHCs as the fault-tolerant broadcasting channels: a Simulation in $CQ_6$; b Simulation in $CQ_{10}$

5.2 Evaluation of packet delivery time in data broadcasting

Next, we simulate the scenario that there exists a message of size no more than 5 M from a source node in $CQ_n$ to broadcast through multiple EDHCs. With the most common Ethernet frame, its frame length can carry about 1500 bytes of the message (excluding the initial preamble, frame delimiter, and the frame check sequence at the end). Hence, the message can be divided into at most $5\text {M}/1500\,\text {bytes}=3500$ (data packets). To comprehend the difference in broadcasting efficiency between two EDHCs (generated by Hung [18]) and three EDHCs (developed in this paper), we carry out $10^6$ simulation instances for each case. For the sake of fairness, the same message scripts are used for both cases.

For each dimension n with $6\leqslant n\leqslant 10$, the source node s at each broadcasting is randomly generated by the uniform distribution over the whole network $CQ_n$. Let m be the number of data packets for broadcasting that is randomly chosen in the range $1\leqslant m\leqslant 3500$. As the source s has two adjacent nodes in a Hamiltonian cycle, the broadcasting randomly picks a direction to carry out the propagation. A data packet will be sent to the next node sequentially along the Hamiltonian cycle at each time slot until it finally returns to the origin to represent the success of this round of transmission. Suppose we take t EDHCs as transmission channels for data broadcasting (actually, $t=2$ or $t=3$ in the following simulation). To balance the load of all transmission channels, we use a round-robin strategy to invoke these channels for packet propagation sequentially. That is, the first t packets are propagated by the channel to which they belong in sequence, the first channel bears the $(t+1)$-th packet, the second channel bears the $(t+2)$-th packet..., and so on.

For each node $v\in V(CQ_n)-\{s\}$ and each j with $1\leqslant j\leqslant m$, let $t_v(j)$ be the delivery time that v receives the jth packet, which is calculated from the beginning. Then, the time for node v receiving the whole message can be represented by $t(v)=\max _{j=1}^{m}\,\{t_v(j)\}$. For broadcasting the message $ms_i$ (where $1\leqslant i\leqslant 10^6$) containing m packets, we define two specific metrics called the average delivery time and the maximum delivery time as follows:

$$\begin{aligned} \mu (ms_i)=\frac{\sum _{v\in V(CQ_n)-\{s\}}\max _{j=1}^{m}\,\big \{t_v(j)\big \}}{|V(CQ_n)|-1} \end{aligned}$$

and

$$\begin{aligned} \eta (ms_i)=\max _{v\in V(CQ_n)}\left\{ \max _{j=1}^{m}\,\big \{t_v(j)\big \}\right\} . \end{aligned}$$

Specifically, for a certain dimension of crossed cubes $CQ_n$, we use the following two measures to evaluate broadcasting efficiency, one is called the average broadcasting latency (ABL for short), and the other is the maximum broadcasting latency (MBL for short):

$$\begin{aligned} \text {ABL}=\frac{\sum _{i=1}^{10^{6}}\mu (ms_i)}{10^6} \end{aligned}$$

and

$$\begin{aligned} \text {MBL}=\max _{i=1}^{10^{6}}\,\big \{\eta (ms_i)\big \}. \end{aligned}$$

All experimental results showing ABL and MBL are depicted in Fig. 8. From this figure, we are aware of the following three phenomenons:

Fig. 8

The comparisons of ABL and MBL between our three EDHCs and Hung’s two EDHCs as the broadcasting channels

• As the network size grows, the two measures ABL and MBL will also rise. That is, both ABL and MBL should exhibit a positive correlation with the network scale.

• For both measures ABL and MBL, the performance of broadcasting latency using three EDHCs is better than that using two EDHCs. For example, the ratio of ABL of three EDHCs to that of two EDHCs approaches 68.85% in $CQ_6$ and is near 85.54% in $CQ_{10}$. In contrast, the ratio of MBL of three EDHCs to that of two EDHCs comes to 67.83% in $CQ_6$ and is near 78.97% in $CQ_{10}$.

• Within the network dimension range of our experiments, the value of MBL is approximately twice that of ABL. For example, for $CQ_n$ with n from 6 to 10, the ratios appear in order 1.98, 1.97, 1.94, 1.89, and 1.83 for broadcasting using two EDHCs, while the ratios appear in order 1.95, 1.92, 1.86, 1.78, and 1.68 for broadcasting using three EDHCs. Obviously, this ratio gets farther away from twice as the network dimension increases.

6 Concluding remarks

In this paper, we study the construction of multiple edge-disjoint Hamiltonian cycles as broadband channels in the crossed cube networks for fault-tolerant data broadcasting. The main contributions of this research are as follows:

• (1) Using the result of [17] and the technique of edge exchange, we provide the construction of three EDHCs in $CQ_6$.

• (2) By induction, we present a recursive algorithm to construct three EDHCs in $CQ_n$ for $n\geqslant 7$.

• (3) Based on (1) and (2), we simulate data broadcasting through the developed three EDHCs (resp. two EDHCs generated by Hung [18]) in $CQ_n$ as the transmission channels, where $n\in \{6,7,8,9,10\}$.

• (4) The comparison results show that broadcasting using three EDHCs is better than two EDHCs in performance, including the ASR in edge fault-tolerant broadcasting and two measures ABL and MBL related to broadcasting latency.

Before closing this paper, we will reflect on the research limitations. Although it is easy to implement a Hamiltonian path or cycle as a channel for data broadcasting, it is well known that such broadcasting delivery time is notoriously inefficient. Hence, if the number of nodes in the network is exponential, the topological scheme of broadcasting channels needs to be adequately adjusted. Usually, a tree structure can reduce the broadcasting delivery time by a logarithmic level, e.g., see [45,46,47].

In general, the reliability of a network depends on its connectivity, edge connectivity, or other related variants, which are important measures for the fault tolerance of networks. However, if the network topology is determined, these connectivities are invariants. Usually, a network with higher edge connectivity can construct more EDHCs. As future works, we are interested to see if there exist four EDHCs of $CQ_n$ for $n\geqslant 8$. So far, this is still an open problem. Also, we can take experiments to simulate edge fault-tolerant data broadcasting under the conditional link faults, i.e., the condition means that every node must be incident with at least two fault-free edges [27, 28].