Sierpinski triangle based data center architecture in cloud computing

Abstract

Computational clouds are increasingly becoming popular for the provisioning of computing resources and service on demand basis. As a backbone in computational clouds, a set of applications are configured over virtual machines running on a large number of server machines in data center networks (DCNs). Currently, DCNs use tree-based architecture which inherits the problems of limited bandwidth capacity and lower server utilization. This requires a new design of scalable and inexpensive DCN infrastructure which enables high-speed interconnection for exponentially increasing number of client devices and provides fault-tolerant and high network capacity. In this paper, we propose a novel architecture for DCN which uses Sierpinski triangle fractal to mitigate throughput bottleneck in aggregate layers as accumulated in tree-based structure. Sierpinski Triangle Based (STB) is a fault-tolerant architecture which provides at least two parallel paths for each pair of servers. The proposed architecture is evaluated in NS2 simulation. The performance of STB-based architecture is then validated by comparing the results with DCell and BCube DCN architecture. Theoretical analysis and simulation results verify that the proportion of switches to servers is 0.167 in STB, lower than BCube (3.67); the average shortest path length is limited between 5.0 and 6.7, whenever node failure proportion remains between 0.02 and 0.2, shorter than DCell and BCube in a four-level architecture. Network throughput is also increased in STB, which spends 87 s to transfer data than DCell and BCube in a given condition. The simulation results validate the significance of STB based DCN architecture for datacenter in computational clouds.

Appendices

Appendix: A Proof of the Theorem 1

• 1. As $S_{0}$ has $k$ servers, thus the proportion of servers to switches is $SV_{n}:SW_{n}=k:1$; similarly, the proportion in $Cell$ is also true. As the STB architecture is constructed by adding multiple $Cells$ based on previous level, so it is obvious that the proportion $SV_{n}:SW_{n}=k:1$.

• 2. As the STB is a recursive architecture, when $n=0$, we can easily get $SW_{0}=1=k^{0}$; similarly, when $n=1$, $SW_{1}=k+SW_{0}=k^{0}+k^{1}$, and $SW_{2}=k+SW_{0}+SW_{1}=k^{0}+k^{1}+k^{2}$. Hence we can get $SW_{n}=k^{0}+k^{1}+k^{2}+\cdots + k^{n-1}+k^{n}$, $n\epsilon (0,\infty )$, that is $SW_{n} = 1+\sum \nolimits _{i=1}^{n}k^{i}$.

• 3. From the Eqs. 1 and 2, we get $SV_{n-1} = k\times SW_{n-1} = k\left( 1+\sum \nolimits _{i=1}^{n-1}k^{i}\right) = k + k\times \sum \nolimits _{i=1}^{n-1}k^{i} = k + \sum \nolimits _{i=2}^{n}k^{i} = 1+\sum \nolimits _{i=1}^{n}k^{i}$.

Appendix: B Proof of the Theorem 2

We assume that a source node $S$ and a destination node $D$ locate at $M$-level and $N$-level of STB architecture, $S_{M}$ and $S_{N}$, respectively, where $(M, N\le n)$. The maximum path for $S$ to a $S_{0}$ server is $S_{M}, S_{M-1}, S_{M-2}, ..., S_{M-n},..., S_{1}, S_{0}$. Similarly, the maximum path for $D$ to the a random $S_{0}$ server is $S_{N}, S_{N-1}, S_{N-2},..., S_{N-n},..., S_{1}, S_{0}$. As only $1$ hop between each $S_{0}$ server, so the maximum path length from $S$ to $D$ is $M+N+1$. When $M=N=n$, the maximum path length in STB is $2n+1$.

Appendix: C Proof of the Theorem 3

As we break the virtual link(s) between servers of $(n-1)$-level and add $Cell$ to construct $n$-level STB network, we have at least $2$ parallel paths for each of two servers. According to the Theorem 1, the maximum path length from source node $S$ to destination node $D$ is $M+N+1$; thus we have $2^{M}$ parallel path between $S$ and $S_{0}$, and $2^{N}$ for $D$ node. Therefore, when both $S$ and $D$ locate in same level $M=N=n$, we have that the number of most parallel paths for two nodes is $2^{M}\cdot 2^{N}\cdot 1=2^{2n}$.