# One-to-One Disjoint Path Covers in DCell

Xi Wang, Jianxi Fan, Baolei Cheng, Wenjun Liu, Yan Wang

► To cite this version:

Xi Wang, Jianxi Fan, Baolei Cheng, Wenjun Liu, Yan Wang. One-to-One Disjoint Path Covers in DCell. 10th International Conference on Network and Parallel Computing (NPC), Sep 2013, Guiyang, China. pp.61-70, 10.1007/978-3-642-40820-5_6. hal-01513760

HAL Id: hal-01513760

https://inria.hal.science/hal-01513760

Submitted on 25 Apr 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# One-to-One Disjoint Path Covers in DCell

Xi Wang, Jianxi Fan*, Baolei Cheng, Wenjun Liu, and Yan Wang

School of Computer Science and Technology, Soochow University, Suzhou 215006,
China

{20124027002, jxfan, chengbaolei, 20114027003, wangyanme}@suda.edu.cn

**Abstract.** DCell has been proposed for one of the most important data center networks as a server centric data center network structure. DCell can support millions of servers with outstanding network capacity and provide good fault tolerance by only using commodity switches. In this paper, we prove that there exist $r$ vertex disjoint paths {$P_i$|1 ≤ $i$ ≤ $r$} between any two distinct vertices $u$ and $v$ of $DCell_k$ ($k \ge 0$) where $r = n+k-1$ and $n$ is the vertex number of $DCell_0$. The result is optimal because of any vertex in $DCell_k$ has $r$ neighbors with $r = n + k - 1$.

**Keywords:** DCell, Data Center Network, Disjoint Path Covers, Hamiltonian

## 1 Introduction

Data centers become more and more important with the development of cloud computing. Specifically, in recent years, data centers are critical to the business of companies such as Amazon, Google, Facebook, and Microsoft, which have already owned tremendous data centers with more than hundreds of thousands of servers. Their operations are important to offer both many on-line applications such as web search, on-line gaming, email, cloud disk and infrastructure services such as GFS [1], Map-reduce [2], and Dryad [3].

Researches showed that the traditional tree-based data center networks [4] have issues of bandwidth bottleneck, failure of single switch, etc.. In order to solve the defects of tree-based data center networks, there are many data center networks which have been proposed such as DCell [4], BCube [5], and FiConn [6, 7]. DCell has many good properties including exponential scalability, high network capacity, small diameter, and high fault tolerantly. In comparison with good capabilities of DCell, BCube is meant for container-based data center networks which only supports thousands of servers, and FiConn is not a regularly network which may raises the construction complexity.

DCells use servers as routing and forwarding infrastructure, and the multi-cast routing frequency between servers are quite high in data center networks. Multi-cast routing algorithms in DCells can be based on the Hamiltonian model as methods on [8, 9]. One-to-one disjoint path covers (also named spanning connectivity [10, 11]) are the extension of the Hamiltonian-connectivity which could

<footnote>* Corresponding author.</footnote>
as well as used on multi-cast routing algorithms in DCells to largely decrease
deadlock and congestion, compared with tree-based multi-cast routing. How-
ever, the problem of finding disjoint path covers is NP-complete [13]. Therefore,
a large amount researches on problems of disjoint path covers focused on dif-
ferent special networks, such as hypercubes [13–16], their variants [17–19], and
others [20–22].

So far there is no work reported about the one-to-one disjoint path cover
properties of DCell. In this paper, we prove that there exist $r$ vertex disjoint
paths $\{P_i|1 \le i \le r\}$ between any two distinct vertices $u$ and $v$ of $DCell_k$
$(k \ge 0)$ where $n$ is the vertex number of $DCell_0$ and $r = n + k - 1$. The result
is optimal because of any vertex in $DCell_k$ has $r$ neighbors with $r = n + k - 1$.

This work is organized as follows. Section 2 provides the preliminary knowl-
edge. Some basic one-to-one disjoint path covers properties are given in Section
3. We make a conclusion in Section 4.

2 Preliminaries

A data center network can be represented by a simple graph $G = (V(G), E(G))$,
where $V(G)$ represents the vertex set and $E(G)$ represents the edge set, and
each vertex represents a server and each edge represents a link between servers
(switches can be regarded as transparent network devices [4]). The edge from
vertex $u$ to vertex $v$ is denoted by $(u, v)$. In this paper all graphs are simple and
undirected.

We use $G_1 \cup G_2$ to denote the subgraph induced by $V(G_1) \cup V(G_2)$ of $G$. For $U \subseteq V(G)$, we use $G[U]$ to denote the subgraph induced by $U$ in $G$, i.e., $G[U] = (U, E')$, where $E' = \{(u, v) \in E(G) | u, v \in U\}$. A path in a graph is a sequence of vertices, $P: <u_0, u_1, \dots, u_j, \dots, u_{n-1}, u_n>$, in which no vertices are repeated and $u_j, u_{j+1}$ are adjacent for $0 \le j < n$. Let $V(P)$ denote the set of all vertices appearing in $P$. We call $u_0$ and $u_n$ the terminal vertices of $P$. $P$ can be denoted by $P(u_0, u_n)$, which is a path beginning with $u_0$ and ending at $u_n$. Let $P_1$ denote $<u_1, u_2, \dots, u_{k-1}, u_k>$ and $P_2$ denote $<u_k, u_{k+1}, \dots, u_{k+n}>$, then $P_1 + P_2$ denotes the path $<u_1, u_2, \dots, u_k, u_{k+1}, \dots, u_{k+n}>$. If $e = (u_k, u_{k+1})$, then $P_1 + e$ denote the path $<u_1, u_2, \dots, u_k, u_{k+1}>$. Furthermore, if $e = (u_{k-1}, u_k)$, $P_1 - e$ denote the path $<u_1, u_2, \dots, u_{k-1}>$.

A path in a graph $G$ containing every vertex of $G$ is called a Hamiltonian
path ($HP$). $HP(u, v, G)$ can be denoted by a Hamiltonian path beginning with
a vertex $u$ and ending with another vertex $v$ in graph $G$. Obviously, if $(v, u) \in
E(G)$, then $HP(u, v, G) + (v, u)$ is a Hamiltonian cycle in $G$. A Hamiltonian
graph is a graph containing a Hamiltonian cycle. $G$ is called a Hamiltonian-
connected graph if there exists a Hamiltonian path between any two different
vertices of $G$. Obviously, if $G$ is a Hamiltonian-connected graph, then $G$ must
be the Hamiltonian graph. Suppose that $u$ and $v$ are two vertices of a graph $G$.
We say a set of $r$ paths between $u$ and $v$ is an $r$-disjoint path cover in $G$ if the $r$
paths do not contain the same vertex besides $u$ and $v$ and their union covers all
vertices of $G$. An $r$-disjoint path cover is abbreviated as an $r$-DPC for simplicity.
A graph $G$ is one-to-one $r$-disjoint path coverable ($r$-DPC-able for short) if there is an $r$-DPC between any two vertices of $G$. In this paper $G$ is $r$-DPC-able is not same as $G$ is $(r+1)$-DPC-able.

For any other fundamental graph theoretical terminology, please refer to [12].

DCell uses recursively-defined structure to interconnect servers. Each server connects to different levels of DCell through multiple links. We build high-level DCell recursively form many low-level ones. Due to this structure, DCell uses only mini-switches to scale out instead of using high-end switches to scale up, and it scales doubly exponentially with server vertex degree.

We use $DCell_k$ to denote a $k$-dimension DCell ($k \ge 0$), $DCell_0$ is a complete graph on $n$ vertices ($n \ge 2$). Let $t_0$ denote the number of vertices in a $DCell_0$, where $t_0 = n$. Let $t_k$ denote the number of vertices in a $DCell_k$ ($k \ge 1$), where $t_k = t_{k-1} \times (t_{k-1} + 1)$. The vertex of $DCell_k$ can be labeled by $[\alpha_k, \alpha_{k-1}, \cdots, \alpha_i, \cdots, \alpha_0]$, where $\alpha_i \in \{0, 1, \cdots, t_{i-1}\}, i \in \{1, 2, \cdots, k\}$, and $\alpha_0 \in \{0, 1, \cdots, t_0 - 1\}$. According to the definition of $DCell_k$ [4, 23], we provide the recursive definition as Definition 1.

**Definition 1.** The $k$-dimensional DCell, $DCell_k$, is defined recursively as follows.

(1) $DCell_0$ is a complete graph consisting of $n$ vertices labeled with $[0],[1],\cdots,[n-1]$.

(2) For any $k \ge 1$, $DCell_k$ is built from $t_{k-1} + 1$ disjoint copies $DCell_{k-1}$, according to the following steps.

(2.1) Let $DCell_{k-1}^0$ denote the graph obtained by prefixing the label of each vertex of one copy of $DCell_{k-1}$ with 0. Let $DCell_{k-1}^1$ denote the graph obtained by prefixing the label of each vertex of one copy of $DCell_{k-1}$ with 1. \dots. Let $DCell_{k-1}^{t_{k-1}}$ denote the graph obtained by prefixing the label of each vertex of one copy of $DCell_{k-1}$ with $t_{k-1}$. Clearly, $DCell_{k-1}^0 \cong DCell_{k-1}^1 \cong \cdots \cong DCell_{k-1}^{t_{k-1}}$.

(2.2) For any $\alpha_k, \beta_k \in \{0, 1, \cdots, t_{k-1}\}$ and $\alpha_k \ge \beta_k$ (resp. $\alpha_k < \beta_k$), connecting the vertex $[\alpha_k, \alpha_{k-1}, \cdots, \alpha_i, \cdots, \alpha_1, \alpha_0]$ of $DCell_{k-1}^{\alpha_k}$ with the vertex $[\beta_k, \beta_{k-1}, \cdots, \beta_i, \cdots, \beta_1, \beta_0]$ of $DCell_{k-1}^{\beta_k}$ as follows:

$$ \left\{ \begin{array}{l} \alpha_k = \beta_0 + \sum_{j=1}^{k-1} (\beta_j \times t_{j-1}) + 1 \\ \\ \beta_k = \alpha_0 + \sum_{j=1}^{k-1} (\alpha_j \times t_{j-1}) \end{array} \right. \qquad (1) $$

(resp.

$$ \left\{ \begin{array}{l} \alpha_k = \beta_0 + \sum_{j=1}^{k-1} (\beta_j \times t_{j-1}) \\ \\ \beta_k = \alpha_0 + \sum_{j=1}^{k-1} (\alpha_j \times t_{j-1}) + 1 \end{array} \right. \qquad (2) $$

where $\alpha_i, \beta_i \in \{0, 1, \cdots, t_{i-1}\}, i \in \{1, 2, \cdots, k\}$, and $\alpha_0, \beta_0 \in \{0, 1, \cdots, t_0 - 1\}$.
By Definition 1, $DCell_{k-1}^{\alpha_k}$ is a subgraph of $DCell_k$, where $\alpha_k \in \{0, 1, \dots, t_{k-1}\}$.

Figure 1(1), 1(2), and 1(3) demonstrate $DCell_0$, $DCell_1$, and $DCell_2$ with $t_0 = 2$ respectively. 1(4) and 1(5) demonstrate $DCell_0$ and $DCell_1$ with $t_0 = 3$ respectively.

## 3 Main results

In this section, we will study one-to-one disjoint path cover properties of DCell.

**Theorem 1.** $DCell_k$ ($k \ge 0$) is Hamiltonian-connected with $t_0 \ge 2$ except for $DCell_1$ with $t_0 = 2$. In other word, $DCell_k$ ($k \ge 0$) is 1-DPC-able with $t_0 \ge 2$ except for $DCell_1$ with $t_0 = 2$.

*Proof.* We omit the proof due to the page limitation. □

**Theorem 2.** $DCell_k$ is a Hamiltonian graph for any $k \ge 0$. In other word, $DCell_k$ is 2-DPC-able for any $k \ge 0$.

*Proof.* We omit the proof due to the page limitation. □

**Lemma 1.** $DCell_0$ is $(t_0 - 1)$-DPC-able with $t_0 \ge 2$.

*Proof.* The lemma holds for $DCell_0$ which is a complete graph [12]. □

**Lemma 2.** $DCell_1$ is 2-DPC-able with $t_0 = 2$.

*Proof.* $DCell_1$ is a cycle with 6 vertices. Therefore, $DCell_1$ is 2-DPC with $t_0 = 2$ [12]. □

**Lemma 3.** $DCell_2$ is 3-DPC-able with $t_0 = 2$.

*Proof.* For $t_0 = 2$, we use construction method to proof this lemma. We can construct an 3-DPC between $u$ and $v$ in $DCell_2$ for any pair of vertices $\{u, v\} \in V(DCell_2)$.

For example, the 3-DPC $\{P_1, P_2, P_3\}$ (resp. $\{R_1, R_2, R_3\}$, $\{T_1, T_2, T_3\}$, $\{S_1, S_2, S_3\}$, $\{U_1, U_2, U_3\}$) from $[0, 0, 0]$ to $[0, 0, 1]$ (resp. $[0, 1, 0]$, $[0, 1, 1]$, $[0, 2, 0]$, $[0, 2, 1]$) whose union covers $V(DCell_2)$ with $t_0 = 2$ are listed below (Similarly for the other cases).

$$P_1 =< [0, 0, 0], [0, 0, 1] >,$$

$$P_2 =< [0, 0, 0], [0, 1, 0], [0, 1, 1], [0, 2, 1], [0, 2, 0], [0, 0, 1] >,$$

$$P_3 =< [0, 0, 0], [1, 0, 0], [1, 0, 1], [2, 0, 1], [2, 2, 0], [2, 2, 1], [2, 1, 1], [4, 1, 0],$$

$$[4, 0, 0], [4, 0, 1], [4, 2, 0], [5, 2, 0], [5, 2, 1], [6, 2, 1], [6, 1, 1], [6, 1, 0], [6, 0, 0], [6, 0, 1],$$

$$[6, 2, 0], [4, 2, 1], [4, 1, 1], [3, 1, 1], [3, 2, 1], [3, 2, 0], [5, 1, 1], [5, 1, 0], [5, 0, 0], [5, 0, 1],$$

$$[1, 2, 0], [1, 2, 1], [1, 1, 1], [1, 1, 0], [3, 0, 1], [3, 0, 0], [3, 1, 0], [2, 1, 0], [2, 0, 0], [0, 0, 1] >.$$

$$R_1 =< [0, 0, 0], [0, 1, 0] >,$$

$$R_2 =< [0, 0, 0], [0, 0, 1], [0, 2, 0], [0, 2, 1], [0, 1, 1], [0, 1, 0] >,$$

$$R_3 =< [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 2, 0], [1, 2, 1], [1, 1, 1], [1, 1, 0], [3, 0, 1],$$

$$[3, 2, 0], [3, 2, 1], [3, 1, 1], [4, 1, 1], [4, 2, 1], [6, 2, 0], [6, 0, 1], [6, 0, 0], [6, 1, 0], [6, 1, 1],$$

$$[6, 2, 1], [5, 2, 1], [5, 1, 1], [5, 1, 0], [5, 0, 0], [5, 0, 1], [5, 2, 0], [4, 2, 0], [4, 0, 1], [4, 0, 0],$$

$$[4, 1, 0], [2, 1, 1], [2, 2, 1], [2, 2, 0], [2, 0, 1], [2, 0, 0], [2, 1, 0], [3, 1, 0], [3, 0, 0], [0, 1, 0] >.$$

$$T_1 =< [0, 0, 0], [0, 1, 0], [0, 1, 1] >,$$

$$T_2 =< [0, 0, 0], [0, 0, 1], [0, 2, 0], [0, 2, 1], [0, 1, 1] >,$$

$$T_3 =< [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 2, 0], [1, 2, 1], [1, 1, 1], [1, 1, 0], [3, 0, 1],$$

$$[3, 0, 0], [3, 1, 0], [2, 1, 0], [2, 0, 0], [2, 0, 1], [2, 2, 0], [2, 2, 1], [2, 1, 1], [4, 1, 0], [4, 1, 1],$$

$$[3, 1, 1], [3, 2, 1], [3, 2, 0], [5, 1, 1], [5, 1, 0], [5, 0, 0], [5, 0, 1], [5, 2, 0], [5, 2, 1], [6, 2, 1],$$
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** (1), (2), and (3) demonstrate *DCell*₀, *DCell*₁, and *DCell*₂ with *t*₀ = 2 respectively. (4) and (5) demonstrate *DCell*₀ and *DCell*₁ with *t*₀ = 3 respectively.</figcaption></figure>
[6, 1, 1], [6, 1, 0], [6, 0, 0], [6, 0, 1], [6, 2, 0], [4, 2, 1], [4, 2, 0], [4, 0, 1], [4, 0, 0], [0, 1, 1] >.

$$S_1 = < [0, 0, 0], [0, 0, 1], [0, 2, 0] >,$$

$$S_2 = < [0, 0, 0], [0, 1, 0], [0, 1, 1], [0, 2, 1], [0, 2, 0] >,$$

$$S_3 = < [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 2, 0], [1, 2, 1], [1, 1, 1], [1, 1, 0], [3, 0, 1],$$

[3, 0, 0], [3, 1, 0], [3, 1, 1], [4, 1, 1], [4, 1, 0], [4, 0, 0], [4, 0, 1], [4, 2, 0], [4, 2, 1], [6, 2, 0],
[6, 0, 1], [6, 0, 0], [6, 1, 0], [2, 2, 1], [2, 1, 1], [2, 1, 0], [2, 0, 0], [2, 0, 1], [2, 2, 0], [5, 1, 0],

[5, 1, 1], [3, 2, 0], [3, 2, 1], [6, 1, 1], [6, 2, 1], [5, 2, 1], [5, 2, 0], [5, 0, 1], [5, 0, 0], [0, 2, 0] >.

$$U_1 = < [0, 0, 0], [0, 0, 1], [0, 2, 0], [0, 2, 1] >,$$

$$U_2 = < [0, 0, 0], [0, 1, 0], [0, 1, 1], [0, 2, 1] >,$$

$$U_3 = < [0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 2, 0], [1, 2, 1], [1, 1, 1], [1, 1, 0], [3, 0, 1],$$

[3, 0, 0], [3, 1, 0], [2, 1, 0], [2, 0, 0], [2, 0, 1], [2, 2, 0], [5, 1, 0], [5, 0, 0], [5, 0, 1], [5, 2, 0],
[4, 2, 0], [4, 0, 1], [4, 0, 0], [4, 1, 0], [2, 1, 1], [2, 2, 1], [6, 1, 0], [6, 1, 1], [6, 2, 1], [5, 2, 1],

[5, 1, 1], [3, 2, 0], [3, 2, 1], [3, 1, 1], [4, 1, 1], [4, 2, 1], [6, 2, 0], [6, 0, 1], [6, 0, 0], [0, 2, 1] >.

□

**Lemma 4.** For any $\alpha, \beta \in \{0, 1, \dots, t_k\}, m \in \{1, 2, \dots, t_k - 3\}$, and $\alpha \neq \beta$, let $x \in V(DCell_k^\alpha)$ be an arbitrary white vertex, $y \in V(DCell_k^\beta)$ be an arbitrary black vertex, and $G_0 = DCell_k^\alpha \cup DCell_k^\beta \cup (\bigcup_{\theta=0}^m DCell_k^{\omega_\theta})$, where $DCell_k^\alpha, DCell_k^\beta, DCell_k^{\omega_0}, \dots, DCell_k^{\omega_i}, \dots, DCell_k^{\omega_m}$ are internally vertex-independent with $i \in \{0, 1, \dots, m\}$ and $\omega_i \in \{0, 1, \dots, t_k\}$. Then there exists a path between $x$ and $y$ that containing every vertex in $DCell_k[V(G_0)]$ where $k \ge 1$ and $t_0 = 2$.

*Proof.* Let $G_1 = DCell_k^\alpha \cup DCell_k^\beta$. Select $z \in V(DCell_k^\alpha)$ and $u \in V(DCell_k^\gamma)$, such that $z \neq x$, $(u, z) \in E(DCell_k)$, and $DCell_k^\gamma \subseteq G_0$, where two graphs $G_1$ and $DCell_k^\gamma$ are internally vertex-independent. Select $\omega \in V(DCell_k^\beta)$ and $v \in V(DCell_k^\delta)$, such that $\omega \neq y$, $(\omega, v) \in E(DCell_k)$, and $DCell_k^\delta \subseteq G_0$ where three graphs $G_1, DCell_k^\gamma$, and $DCell_k^\delta$ are internally vertex-independent. According to Theorem 1, there exists a path $P$ from $x$ to $z$ that containing every vertex in $DCell_k^\alpha$ and a path $Q$ from $\omega$ to $y$ that containing every vertex in $DCell_k^\beta$. Let $G_2 = G_0[V(\bigcup_{\theta=0}^m DCell_k^{\omega_\theta})]$. We can construct a path $S$ from $u$ to $v$ that containing every vertex in $G_2$ which is similar to Theorem 1. Then there exists a path $P + (z, u) + S + (v, \omega) + Q$ between $x$ and $y$ that containing every vertex in $DCell_k[V(G_0)]$ where $k \ge 1$ and $t_0 = 2$. □

**Lemma 5.** $DCell_k$ is $(k+1)$-DPC-able with $k \ge 2$ and $t_0 = 2$.

*Proof.* We will prove this lemma by induction on the dimension $k$ of DCell. By lemma 3, the lemma holds for $t_0 = 2$ and $k = 2$. For $t_0 = 2$, supposing that the lemma holds for $k = \tau$ ($\tau \ge 2$), we will prove that the lemma holds for $k = \tau + 1$.

For any vertex $x, y \in V(DCell_{\tau+1})$ with $x \neq y$. Let $x \in V(DCell_\alpha)$ and $y \in V(DCell_\beta)$ with $\alpha, \beta \in \{0, 1, \dots, t_\tau\}$. We can identify $\alpha$ and $\beta$ as follows.

Case 1. $\alpha = \beta$. There exist $(\tau + 1)$ vertex disjoint paths $\{P_i|1 \le i \le \tau + 1\}$ between any two distinct vertices $x$ and $y$ of $DCell_\tau$. Select $u \in V(DCell_\gamma)$ and $v \in V(DCell_\delta)$, such that $(x, u), (y, v) \in E(DCell_{\tau+1})$, where three graphs $DCell_\alpha, DCell_\gamma$, and $DCell_\delta$ are internally vertex-independent. According to Lemma 4, there exists a path $P_{\tau+2}$ from $u$ to $v$ that visits every vertex in $DCell_{\tau+1}[V(DCell_{\tau+1} - DCell_\alpha)]$. Then there exist $(\tau+2)$ vertex disjoint paths $\{P_i|1 \le i \le \tau + 2\}$ between any two distinct vertices $x$ and $y$ of $DCell_{\tau+1}$.
Case 2. $\alpha \neq \beta$ and $(x, y) \in E(DCell_{\tau+1})$. Let $P_1 = \langle x, y \rangle$. Select $x_0 \in V(DCell_{\tau}^{\alpha})$ (resp. $y_0 \in V(DCell_{\tau}^{\beta})$), such that $(x, x_0) \in E(DCell_{\tau}^{\alpha})$ (resp. $(y, y_0) \in E(DCell_{\tau}^{\beta})$). According to the induction hypothesis, there exist $(\tau+1)$ vertex disjoint paths $\{P'_i|2 \le i \le \tau+2\}$ (resp. $\{Q'_j|2 \le j \le \tau+2\}$) between any two distinct vertices $x$ and $x_0$ (resp. $y_0$ and $y$) in $DCell_{\tau}^{\alpha}$ (resp. $DCell_{\tau}^{\beta}$). Let $P_2'' = \langle x, x_0 \rangle$ (resp. $Q_2'' = \langle y_0, y \rangle$), $P_i' = \langle x, \dots, x_i, x_0 \rangle$ (resp. $Q_j' = \langle y_0, y_j, \dots, y \rangle$), and $P_i'' = P_i' - (x_i, x_0)$ (resp. $Q_j'' = Q_j' - (y_0, y_j)$) with $3 \le i \le \tau+2$ (resp. $3 \le j \le \tau+2$). Furthermore, let $z_i \in V(DCell_{\tau}^{\gamma_i})$ (resp. $w_j \in V(DCell_{\tau}^{\delta_j})$) with $2 \le i \le \tau+2$ (resp. $2 \le j \le \tau+2$) and $(x_i, z_i) \in E(DCell_{\tau+1})$ (resp. $(y_i, w_j) \in E(DCell_{\tau+1})$). Let $W_0 = \cup_{\theta=2}^{\tau+2} DCell_{\tau}^{\theta}$, $W_1 = \cup_{\theta=2}^{\tau+2} DCell_{\tau}^{\theta'}$ and $W = W_0 \cup W_1 \cup DCell_{\tau}^{\alpha} \cup DCell_{\tau}^{\beta}$. For $2 \le i \le \tau+2$, we can claim the following two subcases with respect to $DCell_{\tau}^{\gamma_i}$.

Case 2.1. $DCell_{\tau}^{\gamma_i} \subseteq W_1$. Select $w_j \in V(DCell_{\tau}^{\gamma_i})$ such that $2 \le j \le \tau + 2$. According to Theorem 1, there exists a path $S$ from $z_i$ to $w_j$ in $DCell_{\tau}^{\gamma_i}$. Furthermore, let $W = W \cup DCell_{\tau}^{\gamma_i}$ and $P_i = P_i'' + (x_i, z_i) + S + (w_j, y_j) + Q_j''$.

Case 2.2. $DCell_{\tau}^{\gamma_i} \not\subseteq W_1$. Select $DCell_{\tau+1}^{\delta_j} \not\subseteq W$ such that $2 \le j \le \tau + 2$. Then, choose $DCell_{\tau}^{p}$ and $DCell_{\tau}^{q}$, such that three graphs $DCell_{\tau}^{p}$, $DCell_{\tau}^{q}$, and $W$ are internally vertex-independent with $p, q \in \{0, 1, \dots, t_k\}$. Let $W'_i = DCell_{\tau}^{\gamma_i} \cup DCell_{\tau}^{\delta_j} \cup DCell_{\tau}^{p} \cup DCell_{\tau}^{q}$, according to Lemma 4, there exists a path $S$ from $z_i$ to $w_j$ in $DCell_{\tau}[W'_i]$. Furthermore, let $W = W \cup W'_i$ and $P_i = P_i'' + (x_i, z_i) + S + (w_j, y_j) + Q_j''$.

Furthermore, select $P_i$, such that $z_i \notin V(W_1)$ and $w_j \in V(W'_i)$ where $2 \le i \le \tau + 2$ and $2 \le j \le \tau + 2$. According to Lemma 4, there exists path $S$ from $z_i$ to $w_j$ in $DCell_{\tau+1}[V(W'_i) \cup (V(DCell_{\tau+1}) - V(W))]$. Furthermore, let $P_i = P_i'' + (x_i, z_i) + S + (w_j, y_j) + Q_j''$.

According to above discussions, there exist $(\tau + 2)$ vertex disjoint paths $\{P_i|1 \le i \le \tau + 2\}$ between any two distinct vertices $x$ and $y$ of $DCell_{\tau+1}$.

Case 3. $\alpha \neq \beta$ and $(x, y) \notin E(DCell_{\tau+1})$. Select $u \in V(DCell_{\tau+1})$ (resp. $v \in V(DCell_{\tau+1})$), such that $(x, u) \in E(DCell_{\tau+1})$ (resp. $(y, v) \in E(DCell_{\tau+1})$), $u \in DCell_{\tau}^{\phi}$ (resp. $v \in DCell_{\tau}^{\psi}$), and $\phi, \psi \in \{0, 1, \dots, t_k\}$, where $DCell_{\tau}^{\alpha}$ and $DCell_{\tau}^{\beta}$ (resp. $DCell_{\tau}^{\phi}$ and $DCell_{\tau}^{\psi}$) are internally vertex-independent. We can claim the following three subcases with respect to $u$ and $v$.

Case 3.1. $u \in V(DCell_{\tau}^{\beta})$. Select $x_0 \in V(DCell_{\tau}^{\alpha})$, such that $(x, x_0) \in E(DCell_{\tau}^{\alpha})$. Let $y_0 = u$. According to the induction hypothesis, there exist $(\tau+1)$ vertex disjoint paths $\{P'_i|2 \le i \le \tau+2\}$ (resp. $\{Q'_j|1 \le j \le \tau+1\}$) between any two distinct vertices $x$ and $x_0$ (resp. $y_0$ and $y$) in $DCell_{\tau}^{\alpha}$ (resp. $DCell_{\tau}^{\beta}$). Let $P_1 = (x, y_0) + Q'_1$ and $Q''_{\tau+2} = \emptyset$. Then, let $P_2'' = \langle x, x_0 \rangle$, $P'_i = \langle x, \dots, x_i, x_0 \rangle$ (resp. $Q'_j = \langle y_0, y_j, \dots, y \rangle$), and $P_i'' = P_i' - (x_i, x_0)$ (resp. $Q_j'' = Q_j' - (y_0, y_j)$) with $3 \le i \le \tau + 2$ (resp. $2 \le j \le \tau + 2$). Furthermore, let $z_i \in V(DCell_{\tau}^{\gamma_i})$ (resp. $w_j \in V(DCell_{\tau}^{\delta_j})$), where $2 \le i \le \tau + 2$ (resp. $1 \le j \le \tau + 1$), $w_{\tau+2} = v \in V(DCell_{\tau}^{\delta_{\tau+2}})$, and $(x_i, z_i) \in E(DCell_{\tau+1})$ (resp. $(y_i, w_j) \in E(DCell_{\tau+1})$). The required $\{P_i|2 \le i \le \tau + 2\}$ paths can be derived by the similar approach as the Case 2, so we skip it.
According to discussions in Case 3 and Case 3.1, there exist $(\tau + 2)$ vertex disjoint paths $\{P_i|1 \le i \le \tau + 2\}$ between any two distinct vertices $x$ and $y$ of $\text{DCell}_{\tau+1}$.

Case 3.2. $v \in V(\text{DCell}_{\tau}^{\alpha})$. The required paths can be derived by the similar approach as the Case 3.1, so we skip it.

Case 3.3. $u \notin V(\text{DCell}_{\tau}^{\beta})$ and $v \notin V(\text{DCell}_{\tau}^{\alpha})$. Let $P_1'' = Q_1'' = \emptyset$, $x_1 = x$, $z_1 = u$, $w_1 = v$ and $y_1 = y$. Select $x_0 \in V(\text{DCell}_{\tau}^{\alpha})$ (resp. $y_0 \in V(\text{DCell}_{\tau}^{\beta})$), such that $(x, x_0) \in E(\text{DCell}_{\tau}^{\alpha})$ (resp. $(y, y_0) \in E(\text{DCell}_{\tau}^{\beta})$). According to the induction hypothesis, there exist $(\tau+1)$ vertex disjoint paths $\{P_i'|2 \le i \le \tau+2\}$ (resp. $\{Q_j'|2 \le j \le \tau+2\}$) between any two distinct vertices $x$ and $x_0$ (resp. $y_0$ and $y$) in $\text{DCell}_{\tau}^{\alpha}$ (resp. $\text{DCell}_{\tau}^{\beta}$). Let $P_2'' = \langle x, x_0 \rangle$ (resp. $Q_2'' = \langle y_0, y \rangle$), $P_i' = \langle x, \dots, x_i, x_0 \rangle$ (resp. $Q_j' = \langle y_0, y_j, \dots, y \rangle$), and $P_i'' = P_i' - (x_i, x_0)$ (resp. $Q_j'' = Q_j' - (y_0, y_j)$) with $3 \le i \le \tau+2$ (resp. $3 \le j \le \tau+2$). Furthermore, let $z_i \in V(\text{DCell}_{\tau+1}^{\gamma_i})$ (resp. $w_j \in V(\text{DCell}_{\tau+1}^{\delta_j})$), where $2 \le i \le \tau+2$ (resp. $2 \le j \le \tau+2$) and $(x_i, z_i) \in E(\text{DCell}_{\tau+1})$ (resp. $(y_i, w_j) \in E(\text{DCell}_{\tau+1})$). The required $\{P_i|1 \le i \le \tau+2\}$ paths can be derived by the similar approach as the Case 2, so we skip it.

According to discussions in Case 3 and Case 3.3, there exist $(\tau + 2)$ vertex disjoint paths $\{P_i|1 \le i \le \tau + 2\}$ between any two distinct vertices $x$ and $y$ of $\text{DCell}_{\tau+1}$.

In summary, for any two distinct vertices $x, y \in V(\text{DCell}_{\tau+1})$, there exist $(\tau+2)$ vertex disjoint paths $\{P_i|1 \le i \le \tau+2\}$ between any two distinct vertices $x$ and $y$ of $\text{DCell}_{\tau+1}$. $\square$

**Lemma 6.** For any $t_0 \ge 3$ and $k \ge 0$, $\text{DCell}_k$ is $(k + t_0 - 1)$-DPC-able.

*Proof.* We will prove this lemma by induction on the dimension $k$ of DCell. For any $t_0 \ge 3$, by Lemma 1, the lemma holds for $k = 0$. For any $t_0 \ge 3$, supposing that the lemma holds for $k = \tau$, where $\tau \ge 0$, the proof that the lemma holds for $k = \tau + 1$ is similar to that of lemma 5 and thus omitted. $\square$

**Theorem 3.** $\text{DCell}_k$ is $(k + t_0 - 1)$-DPC-able with $k \ge 0$.

*Proof.* By Lemma 1, the theorem holds for $k = 0$ and $t_0 \ge 2$. By Lemma 2, the theorem holds for $k = 1$ and $t_0 = 2$. By Lemma 5, the theorem holds for $k \ge 2$ and $t_0 = 2$. By Lemma 6, the theorem holds for $t_0 \ge 3$ and $k \ge 0$. $\square$

# 4 Conclusions

DCell has been proposed for one of the most important data center networks and can support millions of servers with outstanding network capacity and provide good fault tolerance by only using commodity switches. In this paper, we prove that there exist $r$ vertex disjoint paths $\{P_i|1 \le i \le r\}$ between any two distinct vertices $u$ and $v$ of $\text{DCell}_k$ ($k \ge 0$) where $n$ is the vertex number of $\text{DCell}_0$ and $r = n + k - 1$. The result is optimal because of any vertex in $\text{DCell}_k$ has $r$ neighbors with $r = n + k - 1$. According to our result, the method in [8, 9] can be used to decrease deadlock and congestion in multi-cast routing in DCell.
Acknowledgments

This work is supported by National Natural Science Foundation of China (61170021),
Specialized Research Fund for the Doctoral Program of Higher Education (20103201110018),
Application Foundation Research of Suzhou of China (SYG201240), and Grad-
uate Training Excellence Program Project of Soochow University (58320235).

References

1. S.Ghemawat, H.Gobioff, S.Leung: The Google file system. ACM SIGOPS Operating Systems Review. 37(5), 29-43 (2003)

2. J.Dean, S.Ghemawat: MapReduce: Simplified data processing on large clusters. Communications of the ACM. 51(1), 107-113 (2008)

3. M.Isard, M.Budiu, Y.Yu, A.Birrell, D.Fetterly: Dryad: distributed data-parallel programs from sequential building blocks. ACM SIGOPS Operating Systems Review, 41(3), 59-72 (2007)

4. C.Guo, H.Wu, K.Tan, L.Shi, Y.Zhang, S.Lu: Dcell: a scalable and fault-tolerant network structure for data centers. ACM SIGCOMM Computer Communication Review, 38(4), 75-86 (2008)

5. C.Guo, G.Lu, D.Li, H.Wu, X.Zhang, Y.Shi, C.Tian, Y.Zhang, S.Lu: BCube: a high performance, server-centric network architecture for modular data centers. ACM SIGCOMM Computer Communication Review, 39(4), 63-74 (2009)

6. D.Li, C.Guo, H.Wu, K.Tan, Y.Zhang, S.Lu: FiConn: Using backup port for server interconnection in data centers. IEEE INFOCOM, 2276-2285 (2009)

7. D.Li, C.Guo, H.Wu, K.Tan, Y.Zhang, S.Lu, J.Wu: Scalable and cost-effective interconnection of data-center servers using dual server ports. IEEE/ACM Transactions on Networking, 19(1), 102-114 (2011)

8. X.Lin, P.Philip, L.Ni: Deadlock-free multicast wormhole routing in 2-D mesh multi-computers. IEEE Transactions on Parallel and Distributed Systems, 5(8), 793-804 (1994)

9. N.Wang, C.Yen, C.Chu: Multicast communication in wormhole-routed symmetric networks with hamiltonian cycle model. Journal of Systems Architecture, 51(3), 165-183 (2005)

10. C.Lin, H.Huang, L.Hsu: On the spanning connectivity of graphs, Discrete Mathematics, 307(2):285-289, 2007.

11. C.Lin, H.Huang, J.Tan, L.Hsu: On spanning connected graphs. Discrete Mathematics, 308(7):1330-1333, 2008.

12. D.B.West and others: Introduction to graph theory. Prentice hall Englewood Cliffs, 2, (2001)

13. J.Park, C.Kim, S.Lim: Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements. IEEE Transactions on Parallel and Distributed Systems, 17(3), 227-240 (2006)

14. R.Caha, V.Koubek: Spanning multi-paths in hypercubes. Discrete mathematics, 307(16), 2053-2066 (2007)

15. X.Chen: Many-to-many disjoint paths in faulty hypercubes. Information Sciences, 179(18), 3110-3115 (2009)

16. X.Chen: Paired many-to-many disjoint path covers of hypercubes with faulty edges. Information Processing Letters, 112(3), 61-66 (2012)
17. J.Park, H.Kim, H.Lim: Many-to-many disjoint path covers in the presence of faulty elements. IEEE Transactions on Computers, 58(4), 528-540 (2009)

18. M.Ma: The spanning connectivity of folded hypercubes. Information Sciences, 180(17), 3373-3379 (2010)

19. Y.Shih, S.Kao: One-to-one disjoint path covers on k-ary n-cubes. Theoretical Computer Science, 412(35), 4513-4530 (2011)

20. H.Hsu, C.Lin, H.Hung, L.Hsu: The spanning connectivity of the (n,k)-star graphs. International Journal of Foundations of Computer Science, 17(2), 415-434 (2006)

21. X.Chen: Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs. Information processing letters, 110(6), 203-205 (2010)

22. P.Huanga, L.Hsub: The spanning connectivity of line graphs. Applied Mathematics Letters, 24(9), 1614-1617 (2011)

23. M.Kliegl, J.Lee, J.Li, X.Zhang, C.Guo, D.Rincon: Generalized DCell structure for load-balanced data center networks. IEEE INFOCOM Conference on Computer Communications Workshops, 1-5 (2010)