Transmission Failure Analysis of Multi-Protection Routing in Data Center Networks With Heterogeneous Edge-Core Servers
Xiaoyan Li, Wanling Lin, Jou–Ming Chang, Xiaohua Jia
Abstract
The recently proposed RCube network is a cube-based server-centric data center network (DCN), including two types of heterogeneous servers, called core servers and edge servers. Remarkably, it takes the latter as backup servers to deal with server failures and thus achieve high availability. This paper first points out that RCube is suitable as a candidate topology of DCNs for edge computing. Three transmission types are among core and edge servers based on the demand for applications’ computation and instant response. We then employ protection routing to analyze the transmission failure of RCube DCNs. Unlike traditional protection routing, which only tolerates a single link or node failure, we use the multi-protection routing scheme to improve fault-tolerance capability. To configure a protection routing in a network, according to Tapolcai’s suggestion, we need to construct two completely independent spanning trees (CISTs), which are edge-disjoint and inner-vertex-disjoint spanning trees. It is well-known that the problem of determining whether there exists a dual-CIST (i.e., two CISTs) in a network is NP-complete. A logic graph of RCube, denoted by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$L$ </tex-math></inline-formula> - <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$RCube(n,m,k)$ </tex-math></inline-formula> , is a network with a recursive structure. Each basic building element consists of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> core servers and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> edge servers, where the order <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> is the number of recursions applied in the structure. In this paper, we provide algorithms to construct <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\min \{n,\lfloor (n+m)/2\rfloor \}$ </tex-math></inline-formula> CISTs in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$L$ </tex-math></inline-formula> - <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$RCube(n,m,k)$ </tex-math></inline-formula> for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n+m\geqslant 4$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n>1$ </tex-math></inline-formula> . From a combination of the multiple CISTs, we can configure the desired multi-protection routing. In our simulation, we configure up to 10 protection routings for RCube DCNs. As far as we know, in past research, there were at most three protection routings developed in other network structures. Finally, we summarize some crucial analysis viewpoints about the transmission efficiency of DCNs with heterogeneous edge-core servers from the simulation results.