A unified model for BAM function that takes into account type Vc secretion and species differences in BAM composition

1.   Introduction

With the continuous expansion of the scale of the data center networks (DCNs), the number of servers in the network increases exponentially ^[1]. The server plays an important role in DCNs, which not only is used to process data but is also needed to forward data. In addition, the probability of server nodes fault is very high and the server failures cause data loss and abnormal data forwarding. Therefore, servers fault diagnosis becomes an inevitable measure to ensure a DCN reliable communication ^[2].

Preparata et al. ^[3] proposed the first system-level fault diagnosis model, namely, the PMC model, which was used to solve the problem of automatic fault diagnosis of the multiprocessor system. Every node in the system is capable of performing tests on its adjacent node. The PMC model assumes that the tests performed by fault-free nodes are always correct, whereas tests performed by faulty nodes are unreliable. Generally, a PMC model is divided into two steps. First, adjacent nodes in the system produce test results by testing each other, which is called syndrome. Second, syndrome be analyzed to find out the faulty nodes. Typically, PMC models focus on diagnostic strategies for the second stage syndrome. Diagnosis strategy contains precise diagnosis ^[3], pessimistic diagnostics ^[4] and $ t/k $ diagnostics ^[5] etc. If all fault-free nodes are not mistaken for faulty nodes, it is called precise diagnosis ^[6]; if there are fault-free nodes that are mistaken for faulty nodes, it is called pessimistic diagnosis ^[7]. $ t/k $ diagnostics is that $ k $ fault-free nodes may be mistaken for faulty nodes, so precise and pessimistic diagnosis are special cases of $ t/k $ diagnosis ^[8]. Specifically, $ t/k $ diagnosis is precise diagnosis when $ k $ = 0, and $ t/k $ diagnosis is pessimistic diagnosis when $ k = 1 $. Many diagnosis algorithms were proposed using precise, pessimistic or $ t/k $ diagnosis strategy ^[9,10].

In the past, system-level fault diagnosis was commonly used in small multiprocessor systems. Nowadays, system-level fault diagnosis is more studied in DCNs with the development of DCNs. For example, Li et al. ^[11] studied the diagnosability of precise diagnosis and pessimistic diagnosis of $ DCel{l_{n, k}} $ and studied the $ t/k $ diagnosability in literature ^[12]. The conclusions are that the precise diagnosability of $ DCel{l_{n, k}} $ is $ n + k - 1 $, the pessimistic diagnosability is $ 2k + n - 2 $ when $ n \ge 2 $ and $ k \ge 2 $ and the t/k diagnosability is $ \; {\left({k + 1} \right)\left({m - 1} \right) + n} $ when $ 1 \le m \le n - 1 $. Huang H ^[13] studied the diagnosability of precise diagnosis of $ BCub{e_{n, k}} $. The conclusion is that the precise diagnosability of $ BCub{e_{n, k}} $ is $ \; \left({n - 1} \right)\left({k + 1} \right) - 1 $ when $ \; n \ge 2 $ and $ k \ge 0 $. However, they are unable to deal with large numbers of fault nodes in DCN due to their limited diagnosability. For example, $ DCel{l_{3, 3}} $ contains 24,492 servers with precise diagnosability of five, pessimistic diagnosability of seven and t/k diagnosability of nine. Obviously, there may be more than nine fault nodes in this network.

To improve diagnosability, Heng et al. ^[14] proposed a probabilistic diagnosis method. Because it is unreliable for two unknown state nodes to test each other, the more times they tested, the more accurate the test results will be, and finally the states of the two nodes can be obtained. However, multiple tests can cause the low diagnostic efficiency and occupy the large network bandwidth, so it is not suitable for DCN networks with a large number of servers. Li et al. ^[15] proposed an algorithm with time complexity $ O\left(N \right) $ for hypercube-like networks by using the Hamiltonian hypercube network and gemini diagnosis structure, which greatly improves efficiency of the algorithm. Ye et al. ^[16] put forward five-round adaptive diagnosis in Hamiltonian networks, which greatly improves diagnosability.

However, traditional algorithms based on the PMC model have two stages of system-level diagnosis. The first stage is to test each other between adjacent nodes, in which there may be fault nodes. The test results of fault nodes are uncertain, so it is impossible to get the correct status of all nodes through the syndrome, and it is necessary to apply the diagnosis strategy (precise or pessimistic diagnosis) to the syndrome in the second step to determine the fault node. If the test node is fault-free, then the status of the tested node can be obtained, so there is no need for a second step. This paper first proposes a fault-tolerant Hamiltonian cycle fault diagnosis algorithm (FHFD), which tests nodes in the order of the Hamiltonian cycle to ensure that the test nodes are fault-free and then combines with probability diagnosis methods to improve the diagnosability ^[17]. In order to improve testing efficiency, a hierarchical diagnosis strategy is also proposed, which recursively divides high scale structures into a large number of low scale structures based on the recursive structure characteristics of DCN. Concretely, we make three main contributions in the strategy.

(1) Compared to traditional diagnosis strategies, the key difference is that our proposed strategy is more suitable for DCNs with multiple servers. This strategy greatly improves the diagnosability. $ 2(n - 2){n^{k - 1}} $ and $ (n - 2){t_{n, k}}/{t_{n, 1}} $ fault nodes can be accurately detected for $ BCub{e_{n, k}} $ and $ DCel{l_{n, k}} $ at most (when $ n \ge 3, k > 0 $).

(2) There is a misdiagnosis node in pessimistic diagnosis based on the traditional PMC model. The strategy we proposed ensures that the test node is fault-free by the fault-tolerant Hamiltonian cycle so that there is no misdiagnosis node.

(3) A hierarchical diagnosis mechanism is further proposed to improve testing efficiency, which recursively divides high scale structures into a large number of low scale structures based on the recursive structure characteristics of DCNs.

The rest of the paper is organized as follows. Preliminaries are introduced in Section 2 and diagnosis strategy based on DCNs is described in Section 3. Performance of the proposed algorithms are shown in Section 4. Finally, we conclude this paper in Section 5.

2.   Preliminaries

In Section 2.1, we will present some notations and terminologies used in this paper. Then, in Section 2.2, we will describe the definition of DCell and BCube structures and some properties of Hamiltonian. Finally, in Section 2.3, we will introduce the PMC model and probabilistic diagnosis method for diagnosis.

2.1.   Notations and Hamiltonian

The topology of DCNs can be represented by an undirected graph $ G = (V(G), E(G)) $, in which $ V(G) $ is the set of vertices and $ E(G) = \left \{ u, v|u, v\in V \right \} $ represents the set of edges. Vertices and edges represent servers and communication links in DCNs, respectively. For an undirected graph $ G = (V(G), E(G)) $, $ {\rm{|}}V{\rm{|}} $ represents the number of servers in $ G $. The edge between vertices $ {v_i} $ and $ {v_j} $ is denoted by $ ({v_i}, {v_j}) $. The neighbor set of a vertex $ x $ in $ G $ is defined as $ {N_G}(x) = \{ y \in V|(x, y) \in E\} $. Let$ \; L \subset V $, $ \; G - L $ be denoted as a subgraph with $ V(G - L) = V - L, \; E(G - L) = $$ \; \{ \left({{\rm{ }}x{\rm{ }}, {\rm{ }}y{\rm{ }}} \right) \in \; E|x, {\rm{ }}y \in (V - L)\} {\rm{.}} $ Path $ P({v_0}, {v_t}) = ({v_0}, {v_1}, ..., {v_t}) $ is a sequence of different vertices (except $ {v_0} $ and $ {v_t} $) from $ {v_0} $ to $ {v_t} $, and any two consecutive vertices are adjacent. Below are the following definitions of the Hamiltonian concept:

Hamiltonian Path: Given graph $ G $, $ \forall V_{i}, V_{j}\in V $, if $ P $ is a path from $ V_{i} $ to $ V_{j} $ that passes all vertices once, and only once, in $ G $, then $ P $ is called a Hamiltonian path from $ V_{i} $ to $ V_{j} $ in $ G $.

Hamiltonian Cycle: Given graph $ G $, $ \forall V_{i}, V_{j}\in V $, starting from $ V_{i} $, if $ P $ is a path from $ V_{i} $ to $ V_{j} $ that passes all vertices once, and only once, in $ G $ and finally returns to $ V_{i} $, then $ P $ is called a Hamiltonian cycle from $ V_{i} $ to $ V_{j} $ in $ G $.

Hamiltonian connected: Given graph $ G $, if there exists a Hamiltonian path between any distinct vertices in $ G $, then the graph $ G $ is called Hamiltonian connected or $ G $ is a Hamiltonian connected graph.

$ F(G) $ is used to represent the set of fault elements in graph $ G(V, E) $ (in this paper, only the set of fault servers), where $ F(G) \subseteq V(G) $. Let $ f(G) = {\rm{|}}F(G)| $ represent the number of fault servers, and if $ f(G) = 0 $, then $ G $ has no faulty servers.

Definition 1. $ F_k $-fault-tolerant Hamiltonian graph: If $ G-F(G) $ is a Hamiltonian graph, then $ G $ is an $ F_k $-fault-tolerant Hamiltonian graph where $ Fk = f(G) $.

Hamiltonian cycle is denoted by $ H({V_h}, {E_h}) $ in graph $ G $, while $ G(V, E) $ is an $ F_k $-fault-tolerant Hamiltonian graph, where $ {V_h} = V $, $ {E_h} \in E $, $ \forall {{\rm{x}}_i} \in {V_h}(1 \le i \le |V|) $, then the Hamiltonian cycle path is $ H < {{\rm{x}}_{i1}}, {{\rm{x}}_{i2}}, ..., \; {{\rm{x}}_{i|v|}}, {{\rm{x}}_{i1}} > $, where $ < i1, i2, ..., $$ i|V| > $ is the sequence combination of $ [1, ..., |V|] $.

$ X(n, k) $ or $ {X_{n, k}} $ denotes a DCN with fault-tolerant Hamiltonian cycle and recursive structure, where $ k $ represents the hierarchy of structure, $ n $ represents the number of servers in $ X(n, 0) $ and $ {t_{n, k}} $ represents the number of servers in $ X(n, k) $.

2.2.   DCell and BCube structures and properties of Hamiltonian

DCell and BCube structures exist fault-tolerant Hamiltonian cycle and are also recursive network structures. Next, the recursive construction rules of DCell and BCube and its Hamiltonian properties are introduced, which prepares for the diagnostic strategy proposed in this article.

Definition 2 ^[18]. The recursive definition of $ DCel{l_{n, k}} $ is as follows:

(1) $ DCel{l_{n, 0}} $ is a complete graph with $ n $ vertices.

(2) When $ k \ge 1 $, $ DCel{l_{n, k}} $ is composed of $ ({t_{n, k - 1}} + 1) \; DCel{l_{n, k{\rm{ - }}1}} $. The ($ i $+1)th $ DCel{l_{n, k{\rm{ - }}1}} $ is represented by $ DCel{l^i}_{n, k{\rm{ - }}1} $, where $ 0 \le i < {t_{n, k - 1}} + 1 $.

In $ DCel{l_{n, k}} $, the address of the server is represented by $ {a_k}{a_{k - 1}}...{a_0}({a_0} \in [0, n-1], \; {a_p} \in [0, {t_{p-1, n}}]p \in [1, k]) $. According to the coding rules of servers in literature ^[18], $ DCel{l^i}_{n, k{\rm{ - }}1} $ contains the address of the server, which is as follows:

Wang X ^[19] studied the Hamiltonian property of DCell and the conclusions are as follows:

Theorem 1. When $ n \ge 2, k \ge 2 $, $ DCel{l_{n, k}} $ (except $ DCel{l_{2, 1}} $) is Hamiltonian connected and is a (n+k-3)-fault-tolerant Hamiltonian graph.

Definition 3 ^[20]. The recursive definition of $ BCub{e_{n, k}} $ is as follows:

(1) $ BCub{e_{n, 0}} $ is a complete graph with $ n $ vertices.

(2) When $ k\ge1 $, $ BCub{e_{n, k}} $ is composed of $ n \; BCub{e_{n, k - 1}} $. The ($ i $+1)th $ BCub{e_{n, k - 1}} $ is represented by $ BCub{e^i}_{n, k - 1} $, where $ 0 \le i < n $.

In $ BCub{e_{n, k}} $, the address of the server is represented by $ {a_k}{a_{k - 1}}...{a_0}({a_0} \in [{a_p} \in [0, n-1], p \in [0, k]) $. According to the coding rules of servers in literature ^[20], $ BCub{e^i}_{n, k - 1} $ contains the address of the server, which is as follows:

Huang et al. ^[21] studied the Hamiltonian connection of BCube and Wang et al. ^[22] studied the fault-tolerant Hamiltonian property of BCube, and their conclusions are as follows:

Theorem 2. When $ n\ge 3, k\ge 0 $, $ BCub{e_{n, k}} $ is Hamiltonian connected, and when $ n\ge 4, k\ge 0 $, $ BCub{e_{n, k}} $ is a $ [(n- 1) $$ (k + 1) -2] $-fault-tolerant Hamiltonian graph.

2.3.   PMC model and probabilistic diagnosis method

In undirected graph $ G = \left({V, E} \right) $, for any two adjacent nodes $ ({v_i}, {v_j}) $, the notation $ {\sigma _{ij}} $ is used to represent the result of $ {v_i} $ test $ {v_j} $. $ {\sigma _{ij}} $ = 0 represents test result as fault-free. On the contrary, $ {\sigma _{ij}} $ = 1 represents test result as faulty.

When $ {v_i} $ is fault-free: If $ {v_j} $ is fault-free, then $ {\sigma _{ij}} = 0 $; if $ {v_j} $ is faulty, then $ {\sigma _{ij}} = 1 $.

When $ {v_i} $ is faulty: Whether $ {v_j} $ is fault-free or faulty, its test result may be $ {\sigma _{ij}} = 0 $ or $ {\sigma _{ij}} = 1 $, and assume that the probability of $ {\sigma _{ij}} = 0 $ is $ p $, where $ 0 < p < 1 $.

All possible comparison results are shown in Table 1 for the PMC model.

Table 1.  PMC model.

$ v_{i} $	$ v_{j} $	$ \sigma _{i, j} $
Fault-free	Fault-free	0
Fault-free	Faulty	1
Faulty	Fault-free	o or 1
Faulty	Faulty	0 or 1

---

 | Show Table

DownLoad: CSV

In the PMC model, if the result of the test is $ {\sigma _{ij}} $ = 0, from Table 1, we can get the corresponding three situations:

1) Both $ {v_i} $ and $ {v_j} $ are fault-free;

2) $ {v_i} $ is faulty, but $ {v_j} $ is fault-free;

3) Both $ {v_i} $ and $ {v_j} $ are faulty.

We cannot get the precise results though just one test; therefore, we test testing many times between two nodes before they are set to get their state and the probabilistic diagnosis method can be designed.

Theorem 3. Four diagnosis results would be obtained through the responses of tests executed by each other $ r $ times by a pair of adjacent nodes $ {{\rm{v}}_i} $ and $ {v_j} $ ($ r $ is large enough):

(1) If $ \sum\limits_1^r {{\sigma _{ij}}} = \sum\limits_1^r {{\sigma _{ji}}{\rm{ = }}0} $, then $ {v_i} $ and $ {v_j} $ are fault-free;

(2) If $ \sum\limits_1^r {{\sigma _{ij}}} = r\& 0 < \sum\limits_1^r {{\sigma _{ji}} < r} $, then $ {v_i} $ is fault-free and $ {v_j} $ is faulty;

(3) If $ 0 < \sum\limits_1^r {{\sigma _{ij}} < r} \& \sum\limits_1^r {{\sigma _{ji}} = r} $, then $ {v_i} $ is faulty and $ {v_j} $ is fault-free;

(4) If $ 0 < \sum\limits_1^{\rm{r}} {{\sigma _{ij}}} < r\& 0 < \sum\limits_1^{\rm{r}} {{\sigma _{ji}} < r} $, then $ {v_i} $ and $ {v_j} $ are faulty;

Proof:

(1) If $ {v_i} $ is faulty, the probability of $ \sum\limits_1^r {{\sigma _{ij}}} = 0 $ can be calculated by binomial distribution: $ P\{X = k\} = C_k^r{p^k}{(1 - p)^{r - k}} $$ {\rm{ = }}{p^k}. $

Assuming that the probability of $ {\sigma _{ij}} = 0 $ is $ p $ = 0.5, test times $ r $ = 9 and $ P\{ X = k\} = {0.5^9} = {\rm{0}}{\rm{.0019}} $. Since the probability is too small, it can be considered that $ {v_i}{\rm{ = 0}} $ and $ {v_j}{\rm{ = 0}} $.

(2) If $ {v_i} $ = 1, the probability of $ \sum\limits_1^r {{\sigma _{ij}}} = r $ can be calculated by binomial distribution: $ P\{ X = k\} = C_k^r{p^k}{(1 - p)^{r - k}} $$ {\rm{ = (1 - }}p{)^r}. $

Assuming that the probability of $ {\sigma _{ij}} = 0 $ is $ p $ = 0.5, test times $ r $ = 9 and $ P\{ X = k\} = {0.5^9} = {\rm{0}}{\rm{.0019}} $. Since the probability is too small, it can be considered that $ {v_i} \ne 1 $ and $ {v_j}{\rm{ = 0}} $. Since $ 0 < \sum\limits_1^r {{\sigma _{ji}} < r} $ and $ {v_i}{\rm{ = 0}} $, according to the PMC rule, $ {v_j}{\rm{ = 1}} $. Through the same logic, it can be proved that (3) holds.

(4) Since $ 0 < \sum\limits_1^r {{\sigma _{ij}}} < r\& 0 < \sum\limits_1^r {{\sigma _{ji}} < r} $, it means $ {\sigma _{ji}} = 0 $ or $ {\sigma _{ji}} = 1 $, and $ {\sigma _{ji}} = 0 $ or $ {\sigma _{ji}} = 1 $. According to the PMC rule, $ {v_i}{\rm{ = }}1 $ and $ {v_j}{\rm{ = 1}} $.

3.   Diagnosis Strategy Based On DCNs

We propose a novel fault diagnosis strategy, which tests nodes in the order of the Hamiltonian cycle to ensure that test nodes are fault-free. Specifically, the strategy consists of two parts: FHFD algorithm and hierarchical diagnosis method, which is suitable for DCNs with the following conditions:

(1) Topology $ G(V, E) $ of $ {X_{n, k}} $ is Hamiltonian connected and an Fk-fault-tolerant hamiltonian graph, where $ k > 0 $;

(2)$ \exists m > 2 $, when $ n > 2 $, $ k > 0 $, $ {X_{n, k}} $ consists of $ m \; {X_{n, k{\rm{ - }}1}}, $ as shown in equation (3.1):

$ {X^i}_{n, k{\rm{ - }}1} $ is the ($ i $+1)th $ {X_{n, k{\rm{ - }}1}} $, where $ 0 \le i < m $ and $ m $ has different values on different network structures. Both BCube and DCell construct rules are shown as in Table 2.

Table 2.  $ BCube $ and $ DCell $ construct rules.

	$ X_{n, 0} $	$ X_{n, 1} $	...	$ X_{n, k} $
$ BCube $	$ BCube_{n, 0} $	$ nBCube_{n, 0} $	...	$ nBCube_{n, k-1} $
2	$ DCell $	$ (t_{n, 0}+1)DCell_{n, 0} $	...	$ (t_{n, k-1}+1)DCell_{n, k-1} $

---

 | Show Table

DownLoad: CSV

(3) The address of the server in $ {X_{n, k}} $ is denoted by $ {a_k}{a_{k - 1}}...{a_0}({a_p} \in [0, m-1], p \in [0, k]) $. Through (1) and (2), we can distinguish different $ {X_{n, k{\rm{ - }}1}} $ by $ {a_k} $, as shown in equation (3.2):

3.1.   FHFD Algorithm

There exists a Hamiltonian cycle $ H({V_h}, {E_h}) $ while a graph $ G(V, E) $ is Fk-fault-tolerant Hamiltonian. Let the $ H({V_h}, {E_h}) $ path be $ H < {x_{i1}}, {x_{i2}}, ..., {x_{i|v|}}, {x_{i1}} > $. We first use probabilistic diagnosis in Theorem 3 to find a fault-free node as $ {x_{i1}} $, and the state of $ {x_{i2}} $ will be determined accurately according to the testing of $ {x_{i1}} $ to $ {x_{i2}} $. If $ {x_{i2}} $ is fault-free, the test outcome is accurate while $ {x_{i2}} $ tests $ {x_{i3}} $; Therefore, we can get the accurate outcome of $ {x_{i3}} $ testing $ {x_{i4}} $, for $ {x_{i3}} $ is fault-free. In turn, all nodes could be tested until the last node. On the other hand, if $ {x_{i2}} $ is faulty, two cases are discussed:

Case 1: $ f(G)\le Fk $

$ G(V, E) $ is Fk-fault-tolerant Hamiltonian, and deleting Fk faulty nodes can still form a new Hamiltonian cycle. If $ f(G)\le Fk $, the fault node $ {x_{i2}} $ can be deleted, then a new Hamiltonian cycle $ H({V_h} - {{\rm{x}}_{i2}}, {E_h}) $ is generated. Let $ {x_{i1}} $ continue to test $ {x_{i3}} $ following Hamiltonian cycle.

Case 2: $ f(G) > Fk $

If $ {x_{i2}} $ is deleted when $ f(G) > Fk $, the remaining nodes will not be able to construct a new Hamiltonian cycle, so let $ {x_{i3}} $ test $ {x_{i4}} $ using the probability diagnosis method. Due to the need for repeated tests between two nodes, the test efficiency is low and the network bandwidth is greatly occupied.

As shown in Figure 1, $ X(V, E) $ is 1-fault-tolerant Hamiltonian graph, and the generated Hamiltonian circle is represented by $ H({V_h}, {E_h}) $. Assuming $ p $ = 0.5, the number of test $ r $ = 9 and $ \sum_{1}^{9}(X_{i1}, X_{i2}) = \sum_{1}^{9}(X_{i2}, X_{i1}) = 0 $ satisfies Case 1 in Theorem 3, then $ {X_{i1}} $ and $ {X_{i2}} $ are fault-free. Let $ {X_{i2}} $ test $ {X_{i3}} $ so that $ {X_{i3}} $ is faulty node and a new Hamiltonian cycle $ H({V_h} - {X_{i3}}, {E_h}) $ is constructed, as shown in Figure 2. Let $ {X_{i2}} $ test $ {X_{i4}} $ so that $ {X_{i4}} $ is fault-free, and $ {X_{i4}} $ test $ {X_{i5}} $ so that $ {X_{i5}} $ is faulty. Since $ X(V, E) $ is 1-fault-tolerant Hamiltonian graph, deleting two nodes cannot construct a new Hamiltonian cycle and the remaining nodes can use the probability diagnosis method to detect the fault.

Figure 1.  Topology of $ H(V_{h}, E_{h} $).

DownLoad: Full-Size Img PowerPoint

Figure 2.  Topology of $ H(V_{h}-X_{i3}, E_{h}) $).

DownLoad: Full-Size Img PowerPoint

For Fk-fault-tolerant Hamiltonian graph $ G(V, E) $, the relationship between the number of fault nodes and the number of tests in diagnosis is as follows:

In equation (3.3), $ N $ is the total number of tests, $ |v| $ denotes the number of servers in $ G(V, E) $, $ f(G) $ denotes the number of fault nodes and $ r $ is the number of times that two nodes in the probability diagnosis method need to test each other.

$ BCub{e_{4, 4}} $ is 13-fault-tolerant Hamiltonian graph by Theorem 2, where $ Fk $ = 13. $ |v| $ is the number of servers, where $ |v| $ = 1024. Supposing $ n $ = 15, the numbers of tests required for different number of faulty nodes are shown in Figure 3 from equation (3.3). $ DCel{l_{5, 2}} $ is 4-fault-tolerant Hamiltonian graph by Theorem 1, where $ Fk $ = 4 and $ |v| $ = 930. Supposing $ n $ = 15, the numbers of tests required for different numbers of faulty nodes are shown in Figure 4 from equation (3.3).

Figure 3.  The number of $ BCube_{4, 4} $.

DownLoad: Full-Size Img PowerPoint

Figure 4.  The number of $ BCell_{5, 2} $.

DownLoad: Full-Size Img PowerPoint

As shown in Figure 3 and Figure 4, when $ f(G) > Fk $, the number of tests increases substantially with the number of faulty nodes. On the basis of the previous analysis, we can get that it will take up a lot of bandwidth and more time to test faulty nodes while $ f(G) > Fk $, and when the FHFD algorithms are applied to the node diagnosis of DCNs, there will be some problems as follows because of the large scale of its servers. First, a lot of time would be spent to build Hamiltonian cycles and fault tolerant Hamiltonian cycles. Second, the nodes should be tested in the order of Hamiltonian cycles, and a complete test for the DCNs with thousands of servers will also take a lot of time.

The total diagnostic time of the FHFD algorithm includes two parts. One part is the test time between nodes. The other part is the time consumed by constructing Hamiltonian cycles and fault-tolerant Hamiltonian cycles. We use MATLAB to simulate the FHFD algorithm for different scale networks, and the running times of the algorithm are shown in Figure 5 and Figure 6.

Figure 5.  The test time of different scale small network.

DownLoad: Full-Size Img PowerPoint

Figure 6.  The test time of different scale big network.

DownLoad: Full-Size Img PowerPoint

The experimental results show that:

1) In Figure 5, when the number of network nodes is small, the test time between nodes is greater than the time used to construct the Hamiltonian cycle. With the increase in the number of nodes, the test time between nodes does not increase much and all the time for constructing Hamiltonian cycles increases sharply.

2) In Figure 6, when the nodes in the network reach a certain scale, the construction of Hamiltonian cycles consumes a lot of time. For example, it takes 3,000 to construct Hamiltonian cycles for the network with 196 nodes.

The FHFD algorithm in the test process by breadth-first search to construct the fault-tolerant Hamiltonian cycle is an non-deterministic polynomial (NP)-complete problem, so when the number of nodes increases to a certain value, the time of constructing the Hamiltonian cycle increases sharply. Obviously, such a long diagnosis time cannot meet the actual situation. In the next section, we propose a hierarchical diagnosis method to solve the above problems.

3.2.   Hierarchical Diagnosis Method

By equation (3), we have that $ {X_{n, k}} $ can be divided into $ m \; {X_{n, k{\rm{ - }}1}} $. Each $ {X_{n, k{\rm{ - }}1}} $ can be divided into $ m \; {X_{n, k{\rm{ - 2}}}} $, and the lowest can be divided into $ {X_{n, 0}} $. Therefore, there is the following conclusion:

$ {X_{n, k}} $ can be divided into $ M \; {X_{n, b}} $s ($ 0 \le b < k $), where $ M $ is a constant (different structures have different $ M $ values):

We consider the following two cases according to $ b $.

Case 1: $ 0 < b < k $

$ {X_{n, k}} $ can be divided into $ M \; {X_{n, b}} $s ($ 0 < b < k $) and $ {X_{n, b}} $ is an Fk-fault-tolerant Hamiltonian graph. If $ M \; {X_{n, b}} $ are simultaneously tested, then $ {X_{n, k}} $ equals to having $ M $ Fk-fault-tolerant values. The network structure of $ BCub{e_{3, 2}} $ is shown in Figure 7, which can be divided into 3 $ BCub{e_{3, 1}} $ for simultaneous testing. By equation (4), $ {X^i}_{n, k{\rm{ - }}1} = \{ {a_k}{a_{k - 1}}...{a_0}|i \in [0, m], {a_k} = i\% m\} $; therefore, the nodes contained in $ BCub{e_{3, 2}} $ can be divided:

Figure 7.  The test time of different scale big network.

DownLoad: Full-Size Img PowerPoint

By theorem 2, $ BCub{e_{3, 2}} $ is 4-fault-tolerant Hamiltonian graph, where fault-tolerant values $ Fk $ = 4. $ BCub{e_{3, 1}} $ is 2-fault-tolerant Hamiltonian graph, where degree of diagnosability $ Fk $ = 2. When the FHFD algorithm is applied to $ BCub{e^0}_{3, 1} $, $ BCub{e^1}_{3, 1} $ and $ BCub{e^2}_{3, 1} $ to complete the test, the sum of fault-tolerant values of three $ BCub{e_{3, 1}} $ are $ Fk $ = 6, which is two more than fault-tolerant values of $ BCub{e_{3, 2}} $, thereby increasing the degree of diagnosability.

$ BCub{e_{4, 4}} $ can be divided into $ M \; BCub{e_{4, b}} $ ($ 0 < b < k $) and different values of $ b $ corresponding $ M $ and fault-tolerant values $ Fk $ are shown in Table 3.

Table 3.  Fault-tolerant values of $ BCube_{4, 4} $.

	$ M $	$ Fk $	$ MFk $
$ BCube_{4, 3} $	4	10	40
$ BCube_{4, 2} $	16	7	112
$ BCube_{4, 1} $	64	4	256

---

 | Show Table

DownLoad: CSV

Table 3 shows that the smaller $ b $, the greater the fault tolerance value $ Fk $ could be obtained. However, the central server needs to send and collect information to all $ BCub{e_{4, b}} $ at the same time during the parallel testing, and a higher performance central server is needed to increase costs with larger $ M $. Therefore, for a more appropriate division of $ {X_{n, k}} $ into M $ {X_{n, b}} $ ($ 0 < b < k $), there is the following equation (3.4):

In equation (3.4), $ |F| $ represents the sum of fault-tolerant values $ Fk $ of $ M \; {X_{n, b}} $s and $ T({t_{n, p}}) $ represents the time spent on $ {t_{n, p}} $ server tests. $ C(M) $ represents performance requirements for central servers. $ \alpha, \beta, \gamma $ are the weights, and their values of different network structures are also different. The larger the $ H $ value, the more reasonable the division.

For example, when $ \alpha = 0.1, \beta = 0.1, \gamma = 0.5 $, $ BCub{e_{4, 4}} $ can be divided into $ BCub{e_{4, 3}} $, $ BCub{e_{4, 2}} $ or $ BCub{e_{4, 1}} $. The equation (6) can get the following values by taking into the above value.

$ H(BCub{e_{4, 3}}) = 0.14 $

$ H(BCub{e_{4, 2}}) = 0.77 $

$ H(BCub{e_{4, 1}}) = 0.76 $

Since $ H(BCub{e_{4, 2}}) $ is the largest, it is most reasonable to divide $ BCub{e_{4, 4}} $ into 16 $ BCub{e_{4, 2}} $.

Case 2: $ b{\rm{ = }}0 $

$ {X_{n, k}} $ is divided into $ M \; {X_{n, 0}} $, where $ n $ is sufficiently large. By definition 2 and 3, $ {X_{n, 0}} $ is a complete graph $ G\left({V, E} \right) $ and $ \forall x, x \in V, {N_G}(x) = V - x $. That is, $ x $ is adjacent to all other nodes. If $ x $ is fault-free, using $ x $ to test the remaining nodes in $ {X_{n, 0}} $ can accurately measure the state of other nodes. This case does not need to generate a Hamiltonian cycle for diagnosis, which can greatly improve the test efficiency.

4.   Analysis Based on Fault-tolerant Hamiltonian Cycle

In this section, the FHFD algorithm and hierarchical testing method are applied to BCube and DCell networks, respectively, and their diagnosabilities are analyzed and compared with traditional diagnostic strategies.

4.1.   Diagnosability Analysis of DCell

The diagnosability of the FHFD algorithm (in only Case 1) combined with hierarchical test method for DCell is as follows:

Theorem 4: The maximum diagnosability of $ DCel{l_{n, k}} $ is $ (n - 2)({t_{n, k}}/{t_{n, 1}}) $ by combining the FHFD algorithm and hierarchical test method with $ n \ge 4 $ and $ k > 0 $.

Proof: $ DCel{l_{n, k}} $ can be divided into $ ({t_{n, k}}/{t_{n, 1}})DCel{l_{n, 1}} $ by equation (3) and $ DCel{l_{n, 1}} $ is (n-2)-fault tolerant Hamiltonian by Theorem 1, then the sum of fault tolerant value of $ ({t_{n, k}}/{t_{n, 1}})DCel{l_{n, 1}} $ is $ (n - 2)({t_{n, k}}/{t_{n, 1}}) $.

We summarize the diagnosability of $ DCel{l_{n, k}} $ based on different strategies in the PMC model in Table 4, which shows that the FHFD algorithm combined with hierarchical testing can greatly improve the diagnosability.

Table 4.  Diagnosability of $ DCell_{n, k} $.

	$ DCell_{3, 2} $	$ DCell_{4, 2} $	$ DCell_{3, 3} $	$ DCell_{4, 3} $
$ t_{nk} $	156	420	24492	176820
precise	4	5	5	6
pessimistic	5	6	7	8
$ t/c $	6	7	9	12
FHFD+Hierarchical	13	42	2041	17682

---

 | Show Table

DownLoad: CSV

4.2.   Diagnosability Analysis of BCube

This section will study the diagnosability of the FHFD algorithm (in only Case 1) combined with hierarchical test method for BCube.

Theorem 5: The maximum diagnosability of $ BCub{e_{n, k}} $ is $ 2(n - 2){n^{k - 1}} $ by combining the FHFD algorithm and hierarchical test method while $ n \ge 4 $ and $ k > 0 $.

Proof: By equation (3), $ BCub{e_{n, k}} = {n^{k - 1}}BCub{e_{n, 1}} $ and $ BCub{e_{n, 1}} $ is 2(n-2)-fault tolerant Hamiltonian by Theorem 2 and, thus, the sum of diagnosability of $ {n^{k - 1}}BCub{e_{n, 1}} $ is $ 2(n - 2){n^{k - 1}} $.

We summarize the diagnosability of $ BCub{e_{n, k}} $ based on different strategies in the PMC model in Table 5, which shows that the FHFD algorithm combined with hierarchical testing can greatly improve the degree of diagnosability.

Table 5.  Diagnosability of $ BCube_{n, k} $.

	$ BCube_{3, 2} $	$ BCube_{4, 2} $	$ BCube_{3, 3} $	$ BCube_{4, 3} $
$ t_{nk} $	64	256	1024	4096
precise	8	11	14	17
FHFD+Hierarchical	16	64	256	1024

---

 | Show Table

DownLoad: CSV

4.3.   Testing time analysis

This section simulates the test time of FHFD and the hierarchical method in BCube network by MATLAB, as shown in Figure 8.

Figure 8.  The testing time of FHFD algorithm and hierarchical method.

DownLoad: Full-Size Img PowerPoint

(1) $ BC{\rm{ub}}{{\rm{e}}_{3, 4}} $ has 243 server nodes, and diagnosis only spends 0.97s. $ BC{\rm{ub}}{{\rm{e}}_{4, 4}} $ has 1,024 nodes and diagnosis only spends 5.12s, which shows that the time consumed increases linearly as the number of server nodes increases. This result proves that server nodes have a significant impact on diagnostic time.

(2) $ BC{\rm{ub}}{{\rm{e}}_{4, 4}} $ has 1,024 nodes and spends 5.12s in the actual test. $ BC{\rm{ub}}{{\rm{e}}_{6, 3}} $ has 1296 nodes and spends 21.38s in the actual test, which shows that the size of the two networks is similar but the test time is quite different. The reason is that the two are divided into layers through the Hierarchical Diagnosis Based on Recursive (HDBR) algorithm. $ BC{\rm{ub}}{{\rm{e}}_{6, 1}} $contains 36 nodes, $ BC{\rm{ub}}{{\rm{e}}_{4, 1}} $ contains 16 nodes and the time is different to construct Hamiltonian cycles for 36 nodes and 16 nodes, resulting in a large difference in the final test time but it is still acceptable.

5.   Conclusion

In this paper, we proposed a novel node fault diagnosis strategy based on the PMC model in DCNs structure, satisfying recursiveness by using fault-tolerant Hamiltonian cycle property. Compared with the traditional diagnosis strategy, our proposed strategy can meet the characteristics of high diagnosability, high accuracy and high efficiency. Therefore, this strategy is more suitable for system-level fault diagnosis of DCNs.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (61672209, 61701170, 62173127, 61973104), Grain Information Processing Center in Henan University of Technology (KFJJ-2020-111), China Postdoctoral Science Foundation funded project (2014M560439), Jiangsu Planned Projects for Postdoctoral Research Funds (1302084B), Scientific & Technological Support Project of Jiangsu Province (BE2016185) and the Science and technology development plan of Henan Province (192102210282, 202102210327).

Conflict of interest

The authors declare there is no conflict of interest.