\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}
\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
linkcolor = blue,
urlcolor = blue,
citecolor = blue,
anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
\errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother
\usepackage{natbib}
\renewenvironment{abstract}
{{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
{\bigskip}
\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}
\usepackage{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}
\usepackage[utf8]{inputenc}
\usepackage[ngerman,english]{babel}
\usepackage{CJKutf8}
\begin{document}
\title{Mesh-of-Torus: A New~ Topology for Server-Centric Data Center Networks}
\author[1]{Lianghui LI}%
\affil[1]{Affiliation not available}%
\vspace{-1em}
\date{\today}
\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup
\selectlanguage{english}
\begin{abstract}
\emph{Various topologies have been proposed for High Performance
Computing(HPC). i.e., fat-tree, Torus topology. Compared with
conventional fat-tree topology, torus performs much better when applied
in HPC. Unfortunately, due to its wraparound links, Torus topology
naturally has a tendency to trigger deadlock incidents inside the
network. People solve this problem by means of virtual channel, but this
approach will also restrict the routing of message. In this paper, we
propose a deadlock-free topology for HPC, without the utilization of
virtual channel approach, called Mesh-of-Torus, which incarnates the
good characteristics of mesh and torus topology. The new topology
possesses the same network diameter as the torus topology does.
Furthermore, we have proposed a corresponding port assignment mechanism
in consideration of deadlock avoidance without the employment of virtual
channel, complicated internal arbitration and scheduling mechanism when
dimension-order routing algorithm is employed. The switching fabric of
server in Mesh-of-Torus is simplified when compared with classical torus
topology. Finally, simulations and mathematical analysis have shown that
Mesh-of-Torus outperforms hierarchical mesh and traditional torus in
terms of average end-to-end latency and network load distribution.}
\par\null%
\end{abstract}%
\sloppy
\par\null
\section*{Introduction}
{\label{874460}}
To enhance the performance of High Performance Computing(HPC), people
have proposed many methods {[}1{]}{[}2{]}{[}3{]}{[}4{]}. With HPC we can
run application programs through parallel processors {[}5{]} efficiently
and reliably. It can be applied in several advancing and promising
areas, such as the cosmic cube{[}6{]} and Blue Gene/Q interconnection
network{[}7{]}. The device technology evolution has reached its
stagnation--no other hardware system outperforms CMOS---meaning that we
cannot expect to improve large-scale computing capabilities on hardware
levels. HPC has the potential to unclog computing bottleneck by taking
full advantages of node interconnection among clustering computers to
effectively process massive data {[}8{]} {[}9{]} {[}10{]}. The
characteristics of HPC closely rely on inter-node communications. So,
network topology and routing algorithms will greatly influence its
computing performance. That's why we focus on the progress of network
topology.
Torus and fat tree are two prime interconnection topology
infrastructures for HPC {[}11{]}. Fat tree can perform well in massive
data processing, but its performance will be limited by scalability,
reliability and power consumption as the scale of network increases.
Compared with fat tree, torus network possesses desirable
features---lower cost on hardware, more achievable on implementation and
lower latency. {[}12{]}. In addition, routing algorithms, used to
improve path diversity and failure detecting ability inside the
interconnection network, can be better implemented on torus network.
Traditional Torus topology naturally has circular link paths in every
dimension, and this architecture feature will inevitably result in
circular waiting for node resources inside network when transaction
comes from various nodes if we do not install packet routing. This will
trigger deadlock incidents and correspondingly influence performance
characteristics of networks {[}14{]} {[}15{]} {[}16{]} {[}17{]}.
Experimental~results~and~theoretical~analysis show that each port of
each node in torus network will require at least two virtual channels to
avoid deadlock even if we introduce deterministic routing algorithm or
partial adaptive routing algorithm inside network of this type.
{[}18{]}.
To solve problems this network may bring about as well as take advantage
of its superiority, we propose a new torus-based topology called
Mesh-of-Torus topology. In Mesh-of-Torus topology, we can achieve in
deadlock free even without the deployment of virtual channels. This new
structure will connect the network in three levels--a 4*4 torus network
is considered as the basic cell to construct higher level network. And
we connect cells of higher level network by mesh topology. In this way,
four links are utilized to connect two adjacent torus networks. To be
more specific, a second level cell consists of four basic cells and a
third level cell consists of four second level cells in the same way. In
addition, we implement a corresponding port assignment mechanism that
can forestall deadlock in the network on the top level. We will discuss
our new topology and related port assignment mechanism in this paper.
The remainder of this paper is organized as follows: In section 2, we
place our work in the context of the deadlock nature of torus and
deadlock avoidance mechanism without using virtual channels. And in
section 3, we will offer detailed information of our new topology and we
will compare it with mesh and torus topology, respectively, on their
network parameters. A deadlock-free routing algorithm is illustrated in
Section 4. And in Section 5 we will give various scaling rules of
Mesh-of-Torus data center networks for plane and three-dimension forms.
The simulations and results will be analyzed in Section 6. Finally, we
end the paper in Section 7 by drawing conclusion and discussing prospect
of the application of this new-type network topology.
\par\null\par\null
\par\null\par\null
Section
\section*{I. deadlock nature of torus and avoidance without using virtual
channel}
{\label{507127}}
~~~~Torus is basically a modified form of mesh topology by connecting
every initial point to the end point. Its wraparound links inside the
network will decrease the communicating time since its structure
features enable remote servers to connect with each other directly in
each dimension. In addition, torus will have a shorter network diameter,
so it will not be limited in its scalability as well as regularity.
~~~~But torus network also has some drawbacks. Torus network naturally
has the tendency to be immersed in deadlock situation due to its ring
structure. Deadlock is a phenomena that all the resources are waiting
for the other resource to release a block. To be more specific, traffics
from different locations will compete for the limited resources the
whole network possesses, such as buffer resources and link bandwidth.
They occupy partial resources that others are applying for while others
are waiting for resources occupied by them. Unless external interrupts
break this dilemma, they will keep asking for the resources for their
advancing. The circular structure of torus is easier to arrange for
resources traffic deadlock in the network. To solve this problem, people
have put forward a concept called virtual channels that will tackle with
this problem by remapping the number of nodes. But the employment of
virtual channel will increase the complexity of routing node considering
of its mounting additional resource expenditure rate and arbitration as
well as judgment expense for each node. So, we shift our focus on
finding a revised deadlock-free topology with the implementation of
virtual channels. And we will present our new topology in the next
section.
\section*{II. MESH-OF-TORUS TOPOLOGY}
{\label{790078}}
~~~~Figure 1 illustrates a Mesh-of-Torus hybrid-interconnected data
center network. 16\selectlanguage{ngerman}×16 servers compose the whole network of three levels.
A 4×4 torus network is considered as the basic cell to construct higher
level network. Multiple torus networks are connected in mesh network.
And two adjacent torus networks are connected by four links. The whole
network are divided into\selectlanguage{english}(2x2\selectlanguage{english})x\selectlanguage{english}(2x2\selectlanguage{english})x\selectlanguage{english}(4x4\selectlanguage{english})hierarchical network. 2x2
torus networks form a third-level subnet and 2x2 third-level subnets
cover the whole network. {And we employ the routing and port assignment
mechanism proposed by us in chapter 4 into this 4x4 torus network.~} And
we will discuss the effectiveness of the routing algorithm in the
subsequent section. So, we can see that in this new structure, no
virtual channels are applied in the switching fabric of each server.
~~~~Compared with hierarchical mesh and traditional torus, Mesh-of-Torus
has the following structure characteristics:
~~~~1) The network diameter is considerably smaller than that of
hierarchical mesh. 4x4 torus network are employed as the basic cell of
the whole network. Compared with hierarchical mesh, the introduction of
wraparound links can notably reduce the number of intermediate nodes
that packets will pass by. Especially when the source node and the
destination node are not in the same subnet, hops will greatly reduce,
making it possible for packets to reach their terminations in even
shorter durations. The diameter of Mesh-of-Torus is less than that of
traditional torus. Additionally, the switching fabric of a server in
Mesh-of-Torus network can be simplified without the implementation of
virtual channels and corresponding complicated arbitration as well as
the scheduling mechanism. More detailed comparisons of various network
parameters, such as node degrees, network diameters, total number of
links and the employment of virtual channels are listed in table 4
within the same network size in different kinds of networks.
~~~~2) A hierarchical mesh has different routing table scale for servers
in various locations. Compared with servers at the brim of hierarchical
mesh, servers at the center of mesh are supposed to store more paths. To
uniform the memory size for routing table, we have to expand the network
according to its routing table scale. But in a Mesh-of-Torus, paths are
independent of their location in the net when passing through servers.
In particular, using the routing and port assignment mechanism proposed
by us in the 4*4 torus, all the servers will store equally 32 paths that
passing them. The analysis and comparison of the composition of the
routing table for a server in a three hierarchical mesh and
Mesh-of-Torus are given in table 5.
~~~~3) Mesh-of-Torus is unable to balance the node degree. When it is
scaled up in the domain of 2D plane, partial server ports are idling and
they will never be utilized. But if it is extended to 3D data center
network, those dormant ports will be activated to construct effective
data center network for better performance. Details on extension rules
for a 2D Mesh-of-Torus network will be illustrated in {chapter}~ 5.
\par\null\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Figure-1/Figure-1}
\caption{{Mesh-of-Torus hybrid-interconnected data center network
{\label{192042}}%
}}
\end{center}
\end{figure}
\section*{III. ROUTING AND DEADLOCK
AVOIDANCE}
{\label{553969}}
~~~~We choose dimension-order routing to guide packets' transmission in
consideration of its simplicity and fast routing characteristics.
Dimension-order routing algorithm is the higher level decision that it
will guide packets to firstly transit forwarded in one dimension, x
dimension for example, until it reaches its target columns. Then it
continues to route in the other dimension and arrives at its
destination.~
~~~~Dimension-order routing algorithm is deadlock-free in full-duplex
meshes and binary hypercube {[}19{]}{[}20{]}{[}21{]}. However, according
to what we have discussed in previous chapter, we have developed
traditional torus network to avoid deadlock in the network. So we need
to propose a corresponding routing mechanism to adapt to this the new
topology we have proposed.
~~~~A map-based systematic approach called IRN has been introduced to
design algorithms for interconnection networks. IRN will determine
routing direction for each node to another node inside network. In a 4*4
torus network with the radix of n(n\textgreater{}=5). IRN map will be
generated when adding a row above IRN map of radix n-1 and adding a
column on the left side of the IRN map of radix n-1. The two leftmost
boxes in the IRN map will be filled with ``-1'' signs and others with
``1'' signs to complete the new column. As for the new column added to
the IRN map, the two lowest boxes in the IRN map will be filled with
``1'' signs and others will be filled with ``-1'' signs. The ``1'' ,
``-1'', ``0'' signs represent for positive, negative and current
position, respectively.
~~~~In this IRN with radix of n, we can find a node that moves towards
positive direction no more than one step, and it moves towards negative
direction no more than one step as well. So in this way, it can avoid
deadlock inside the network even if it does not introduce a virtual
channel in the network. The IRN map is shown in Table 1.\selectlanguage{english}
\begin{table}[h!]
\centering
\normalsize\begin{tabulary}{1.0\textwidth}{CCCCCCCCCCCCC}
& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\
0 & -1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & -1 & -1 \\
1 & -1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & -1 & -1 \\
2 & -1 & -1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & -1 & -1 \\
3 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & -1 & -1 \\
4 & -1 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & 1 & 1 & -1 & -1 \\
5 & -1 & -1 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & 1 & -1 & -1 \\
6 & -1 & -1 & -1 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & -1 & -1 \\
7 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 0 & 1 & 1 & -1 & -1 \\
8 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 0 & 1 & 1 & -1 \\
9 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 0 & 1 & -1 \\
10 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & -1 & 0 & 1 \\
11 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & -1 & -1 & 0 \\
\end{tabulary}
\caption{{(a) The IRN map for 12x12 torus network
{\label{731217}}%
}}
\end{table}\selectlanguage{english}
\begin{table}[h!]
\centering
\normalsize\begin{tabulary}{1.0\textwidth}{CCCCCCCCCCCCC}
& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\
0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & -1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
2 & -1 & -1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
3 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
4 & -1 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
5 & -1 & -1 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
6 & -1 & -1 & -1 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & 1 & 1 \\
7 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 0 & 1 & 1 & 1 & 1 \\
8 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 0 & 1 & 1 & 1 \\
9 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 0 & 1 & -1 \\
10 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & -1 & 0 & 1 \\
11 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & -1 & -1 & 0 \\
\end{tabulary}
\caption{{(b) Migrate the proposed design to torus network
{\label{453189}}%
}}
\end{table}\selectlanguage{english}
\begin{table}[h!]
\centering
\normalsize\begin{tabulary}{1.0\textwidth}{CCCCCCCCCCCCC}
& 0~1 & 1~2 & 2~3 & 3~4 & 4~5 & 5~6 & 6~7 & 7~8 & 8~9 & 9~10 & 10~11 & 11~0 \\
--> & 25 & 30 & 33 & 34 & 33 & 30 & 25 & 18 & 10 & 2 & 10 & 18 \\
<-- & 25 & 30 & 33 & 34 & 33 & 30 & 25 & 18 & 10 & 2 & 10 & 18 \\
\end{tabulary}
\caption{{Theoretical computations of links load at different positions of the
same dimension for 12x12 torus network.
{\label{369220}}%
}}
\end{table}\begin{CJK}{UTF8}{gbsn}\subsection*{2.1Optimize Port Assignment
Rules(编号)}\end{CJK}\selectlanguage{english}
{\label{525886}}
~~~~According to the discussion above, we can know that IRN map can work
effectively in small-scale network. However, IRN map cannot always find
optimal and minimal paths, because each packet guided by IRN map
traverses the shortest possible paths that are deadlock-free instead of
through the shortest physical paths that may lead to deadlocks. Links
fail to balancing the load under all-to-all pattern when the size of
network scales up. Theoretical computations on links load for a 12x12
torus network at different positions in one dimension have been listed
in the Table 2. We use ``--\textgreater{}'' and ``\textless{}--'' signs
to represent for the directions of traffic between two adjacent nodes,
respectively. Traffic between node 9 and 10 is at a low pressure because
in node 9, all the positive movements more than one step are forbidden
and in node 10, all the negative movements more than one step are not
allowed as well. But this will aggravate traffic loads on nodes far from
node 9 and node 10. So, IRN map will not able to make optimal decisions
in this case. New assignment rules are necessary to guide the fast
transmission of packets.
~~~~We should achieve three objectives when designing new port
assignment rules:
i) Packets should reach their destinations in a limited period or no
Ping-Pong phenomenon occurs inside network;
ii) No cyclic dependence forms in the channel dependence graph;
iii) Rules should balance the load of each links as much as possible.
~~~~These objectives are closely independent with each other. A channel
dependence graph will generate according to the path between arbitrary
pair of servers in the torus network. Some potential deadlock-free port
assignments may generate in this process. We will choose the port
assignment that can perform best in balancing load among links as the
optimal choice. So, we will divide optimal port assignment searching
processes into three sub-steps.
~~~~For example, we can apply well-designed routing and assignment
mechanisms to this network. According to the dimension-order routing
algorithm, packets will keep transferring in one dimension until it
reaches the column where the destination node locates. Packets will
select appropriate routing directions in each dimension to avoid
deadlock. To attain this goal, we will simplify the selecting routing
direction process by integrating the multi-dimension into a single
dimension and shift it to another dimension. To raise a 4*4 torus
network as an example, it is a torus structure consisting of 4 nodes in
each dimension. So, data packets can be sent to those two adjacent nodes
by one hop, but if packets will be sent to nodes that far away, they
have multiple options. Table 3 lists all the available choices for the
torus topology, but some of them may result in deadlock inside network.
(a)Different node to other nodes in the routing direction within a ring
structure consisting 4 nodes. ``---'' represents either positive or
negative direction.\selectlanguage{english}
\begin{longtable}[]{@{}l@{}}
\toprule
\begin{minipage}[t]{0.97\columnwidth}\raggedright\strut
\textbf{Node{}}
\textbf{Node 0{}}
\textbf{Node 1{}}
\textbf{Node 2{}}
\textbf{Node 3{}}
\textbf{Node 0{}}
0{}
1{}
---{}
-1{}
\textbf{Node 1{}}
-1{}
0{}
1{}
---{}
\textbf{Node 2{}}
---{}
-1{}
0{}
1{}
\textbf{Node 3{}}
1{}
---{}
-1{}
0{}\strut
\end{minipage}\tabularnewline
\bottomrule
\end{longtable}
\par\null\par\null
~
\par\null
(a). Different node to other nodes in the routing direction within a
ring structure consisting 4 nodes. ``---'' represents either positive or
negative direction.
\par\null
~
\par\null\par\null\selectlanguage{english}
\begin{longtable}[]{@{}ll@{}}
\toprule
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
\textbf{Port direction{}}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
\textbf{~~~~~~~~~~~~~ Network performance{}}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
Node0{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
Node1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
-1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage} & \begin{minipage}[t]{0.48\columnwidth}\raggedright\strut
1{}\strut
\end{minipage}\tabularnewline
\bottomrule
\end{longtable}
\par\null\par\null
~
\par\null
(b). Distribution of deadlock and load under different routing
direction. ``[?]'' represents port assignments are deadlock-free and make
the load balanced. ``\selectlanguage{ngerman}×'' has the contrary meanings.
\par\null
Table 3. The available selections for the ring
\subsection*{4.1 Theorem}
{\label{971900}}
Dimension-order routing algorithm is deadlock-free in Mesh-of-Torus
networks.
\subsection*{4.2 Proof}
{\label{671998}}
~~~~Mesh-of-Torus network is the combination of mesh and torus network.
To be more specific, the basic unit of this network is mesh network, but
it borrows the idea of torus network to connect those basic units into a
whole. It is meaningless for us to simplify the deadlock avoidance
problem and employ dimension-order routing algorithm in Mesh-of-Torus
network on a single dimension on the basis of following reasons:
~~~~1) When packets are transferring in the 4×4 torus network, our port
assignment have already guaranteed the formation of cyclic-relationship
in every dimension as well as the prevention of deadlock.
~~~~2) When packets are transferring in a 4*4 torus network and boundary
nodes of adjacent torus network, such as the clockwise and anticlockwise
channels in a single dimension illustrated in Figure 3, we can prevent
deadlock by the employment of port assignment rules in each 4*4 torus
network, even if we add some boundary nodes of other torus network in
it.
~~~~3) When packets are transferring among multiple subnets, such as the
clockwise and anticlockwise channels in a single dimension illustrated
in Figure4, we can avoid deadlock by preventing the formation of cyclic
relationship by the application of the port assignment rules for all the
subnet.
~~~~In a word, when dimension-order routing algorithm is applied, a
single-dimension Mesh-of-Torus network is deadlock-free spontaneously.
\par\null
{}
\par\null
\textbf{Figure 2.} Packet routing process in data center with
Mesh-of-Torus network.
\par\null
{}
\par\null
\textbf{Figure 3.} The clockwise and anticlockwise channels in a single
dimension. (Packets advance between the 4×4 torus network and boundary
nodes of adjacent torus network)
\par\null
\par\null\par\null
\textbf{Figure 4.} The clockwise and anticlockwise channels in a single
dimension. (Packets advance between multiple subnets)
\section*{IV.~SCALABILITY OF MESH-OF-TORUS
NETWORK}
{\label{259121}}
\subsection*{5.1 Scaling to 2D}
{\label{119837}}
In the previous section, we have discussed the routing algorithm for
Mesh-of-Torus topology and we have analyzed the implementation on a
single dimension. In this section, we will scale up the Mesh-of-Torus
network in higher dimension.
A 4*4 torus network is the smallest component unit of Mesh-of-Torus
network. Unlike the virtual hierarchical mesh network, Mesh-of-Torus
network can be constructed by mesh into arbitrary size. So, we can
express the size of the Mesh-of-Torus network as
, and items for routing table or the number of path stored in a single
server is
Assuming the maximum size of routing table is N, the number of server
contains of data center with Mesh-of-Torus network satisfied:
\textbf{5.2 Scaling to 3D}
Mesh-of-Torus network can also be extended to 3D fields for the
construction of 3D Mesh-of-Torus network data center. Each plane of the
3D Mesh-of-Torus network data center is composed of 2D Mesh-of-Torus
network, and 3D network will inherit the classification and network
configuration mechanisms of 2D network. And each node in 2D
Mesh-of-Torus network are able to communicate with nodes in the other
planes. The node degree in 4*4 torus network is unequal when forming a
2D Mesh-of-Torus network, so we will utilize those nodes as the
communication path during the extension to 3D to balance the node degree
in the whole network. Specifically, as shown in Figure 5, the node
degree for four vertices in torus network is 6 and that for other edge
nodes is 5, but the node degree for nodes inside the torus network is 4.
Node in this network can be represented in a coordinate (F, S, T, H).
And F, S, T represent for the node hierarchical number in the plane,
while H for the plane H the node located in. When extending 2D network
to 3D fields, we choose to connect only four nodes inside the network
with nodes in another plane respectively instead of connecting all the
nodes inside in a plane with nodes in another plane.
The routing process for packets in the 3D Mesh-of-Torus network consists
of three steps:
1) For packets routing in the plane where source node is located, if
they are in the plane where the source node is in, they will find out
the same coordinate of node Dtemp~ firstly, and then route packets to
their corresponding intermediate nodes that are closest to Dtemp in the
smallest subnet. Figure 6. Defines four intermediate nodes and divide
the whole network into several small areas according to the location of
the nodes in the net. So, nodes belong to the same area have the same
corresponding intermediate nodes. Packets have to be routed to their
corresponding intermediate node before routing to another plane.
2) For packets routing in the third dimension, the point-to-point path
will be applied and each intermediate node will store the path and
calculate the corresponding output ports for arrived packets. After
these processes, it will guide packets to those ports.
3) For packets routing in the plane where destination node located in,
packets will go to the corresponding intermediate nodes in the
destination plane after passing through the point-to-point path. And
from those intermediate nodes, they will continue to route to the
destination nodes. Figure 7 lists multiple routing directions from
intermediate nodes to other nodes in a 4×4 torus network.
\par\null
{}
\par\null
\textbf{Figure 5.} 3D expansion of Mesh-of-Torus network.
\par\null
\par\null\par\null
\textbf{Figure 6.} Center nodes of the torus network.
\subsection*{5.3 Proof of the Deadlock-Free in 3D Mesh-of-Torus
Network}
{\label{908262}}
The routing process of packets in the 3D Mesh-of-Torus network consists
of three steps under the guidance of dimension-order routing algorithm:
{1) In Chapter} 4, we have proven that the process of packets routing in
source node plane is deadlock-free.
2) Packets will follow the rules defined in chapter 4 when routing in
the third dimension. And we will prove it in chapter 4 that under this
routing mechanism, we can forbid the formation of circular waiting and
thus achieve in deadlock-free.
~3) We introduce the dimension order algorithm when packets transfer in
the plane of destination node to prevent deadlock.
\par\null
\section*{}
{\label{675427}}\par\null
\par\null\par\null
\textbf{Figure 7.} Routing direction from center nodes to side nodes in
torus network.
\section*{VI. SIMULATION AND RESULTS
ANALYSIS}
{\label{681339}}
We have studied various approaches to balance the distribution of work
load in the network. In this section we will use OPNET to simulate the
hierarchical mechanism of the Mesh-of-Torus network and the
corresponding routing algorithm {[}26{]} {[}27{]}. In this part, we will
also compare the performance of Mesh-of-Torus network with that of mesh
network.
\subsection*{6.1 Simulation Design}
{\label{358804}}
The simulation platform is composed of data and control planes viewing
from the system constitution point. The data plane includes the topology
we used for the simulation platform, server microstructure, physical
link parameters and so on. And we need to use control plane to govern
the duration of simulation, time and space of packets flow, business
scale or other parameters.
Simulation will choose a switching mechanism to employ in the network
automatically. At the beginning of this simulation, the automatic
routing algorithm will configure routing table for each server in
accordance with the topology, scale and hierarchical mechanism of the
network.
Servers should generate business along with the change of flow pattern.
And they are also responsible for defining the business format and
recording data during the simulation process. We judge the performance
of network by the utilization of end-to-end and link. The end-to-end
latency can be represented as:
{}We use
~to represent for time that i-th packet arrive at the node and
~for the number of received packets.
\subsection*{The link utilization rate can be expressed
as:}
{\label{352060}}\par\null
{}
In the above equation,
and
~represent for the throughput per unit time and link bandwidth
respectively.
\textbf{6.2 Simulation of the Mesh-of-Torus Hybrid Interconnection Data
Center Network and Analysis}
We first use OPNET to build a complete Mesh-of-Torus data center network
system for simulation, and then we utilize the network model to evaluate
the performance of a hierarchical strategy and routing algorithm based
on the network architecture we build up in the first step. A 8*8
Mesh-of-Torus network built by OPNET is shown in Figure 8.
\textbf{End-to-End Latency:} Statistic end-to-end Latency
\par\null
{}
\textbf{Figure 8.} 8×8 Mesh-of-Torus network
\par\null\par\null
\textbf{Figure 9.} End-to-end Latency of the 8×8 Mesh-of-Torus network
in different flow patterns.
\par\null
~
\par\null
Simulation results for the 8×8 Mesh-of-Torus network with a 256 byte
packets size and different flow patterns are shown in Figure 9. We can
conclude from the figure that end-to-end latency can remain at an
extremely low level before the network reaches its saturation point. But
if the infusion rate exceeds the saturation point, end-to-end latency
are expected to soar. And if we use all-to-all traffic patterns, the
network will reach its saturation point in a short time, but if we use
the local traffic patterns, the network can get a higher network
saturation point. That is because that in the local traffic patterns,
the network can fully utilize the long torus network links. And this
property is a firm proof for the idea that Mesh-of-Torus network can be
more suitable for data center network with more local traffics. We use
Figure 10 (a),(b),(c),(d) to show different flow patterns of the network
link load distribution in a same network model, respectively.(a)~~~
all-to-all
\par\null\par\null\selectlanguage{english}
\begin{longtable}[]{@{}@{}}
\toprule
\tabularnewline
\bottomrule
\end{longtable}
~
\textbf{{}}
(b)~~~ 30\% local traffic{}
{}
~
~
~~~~~~~~~~~~~~~~~~~~~~~
~
{}
~
~
~
~
~
(c)~~~ 50\% local traffic
~
~
{}
~
~
\par\null\par\null
~
\par\null
~
\par\null
~
\par\null
~
\par\null
~
\par\null
(d) 70\% local traffic
\par\null
\textbf{Figure 10.} Link load distribution of the 8\selectlanguage{ngerman}×8 Mesh-of-Torus
network in different flow patterns.
\par\null
Left column represents the horizontal link; Right column represents the
longitudinal link.
The results have shown that when the flow occurs in the internal subnet,
the peak value of the central link load in the network will fall down
such that the link load in each part of the whole network will be
balanced. In addition, Mesh-of-Torus network can satisfy the actual
needs since in the real world since majority of the traffic
distributions among internal servers are in the rack.
We record load distributions of long link in different rows for our more
detailed analysis. And it can be observed from the figure that in an
all-to-all model, the long link have~a~high~rate~of~utilization. That is
because that routing algorithm introduced in this network will guide the
packets to the edge server before routing to another subnet. But as the
flow distributions within the subnet increase, they will be controlled
by reducing the utilization rate of long link. Then, the distributions
of link load in the whole network will be balanced well. The same
situation will exist in the longitudinal link as well.
\par\null
{}
(a)~~~ Long link load distribution for left part of 8×8 Mesh-of-Torus
network.
{}
(b)~~~ Long link load distribution for right part of 8×8 Mesh-of-Torus
network.
\textbf{Figure 11.} Load distribution of long link in different rows.
\textbf{{}}
\textbf{Figure 12.} End-to-end latency of the 8×8 Mesh-of-Torus network
and mesh network
\par\null\par\null
\textbf{Figure 13.} Throughput under different packet injection rates of
the 8×8 Mesh-of-Torus network and mesh network in different flow
patterns.
\par\null
~
\par\null\par\null\selectlanguage{english}
\begin{longtable}[]{@{}lll@{}}
\toprule
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
\textbf{Serial number{}}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
\textbf{Time interval{}}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
\textbf{Injection rate{}}
\textbf{(packets/node/s){}}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
1{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
0.000001\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
1,000,000{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
2{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
0.0000009{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
1,111,111{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
3{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
0.0000008{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
1,250,000{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
4{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
0.0000007{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
1,428,571{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
5{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
0.0000006{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
1,666,666{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
6{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
0.0000005{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
2,000,000{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
7{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
0.0000004{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
2,500,000{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
8{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
0.0000003{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
3,333,333{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
9{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
0.0000002{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
5,000,000{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
10\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
0.0000001{}\strut
\end{minipage} & \begin{minipage}[t]{0.32\columnwidth}\raggedright\strut
10,000,000{}\strut
\end{minipage}\tabularnewline
\begin{minipage}[t]{0.30\columnwidth}\raggedright\strut
\strut
\end{minipage} & \begin{minipage}[t]{0.30\columnwidth}\raggedright\strut
\strut
\end{minipage} & \begin{minipage}[t]{0.30\columnwidth}\raggedright\strut
\strut
\end{minipage}\tabularnewline
\bottomrule
\end{longtable}
\par\null\par\null
\textbf{Table 6.} Control table between simulation serial and packet
injection rates
\par\null
\textbf{~}
\par\null
\textbf{6.3 Comparison between Mesh-of-Torus network and mesh network}
\par\null
\textbf{Latency:} Figure 12 shows the statistic end-to-end latency
simulation results for the 8\selectlanguage{ngerman}×8 Mesh-of-Torus network and mesh network
with a 256 bytes packets size and different flow pattern {[}28{]}. From
the Figure 12 we can see that the saturation point of the Mesh-of-Torus
network is higher than that of mesh network, that is because that long
links that used to reduce the network diameter can enable packets to
reach the destination node in a higher speed. Besides, the latency of
the Mesh-of-Torus network is naturally lower than that of mesh network
because that when the diameter of the network is reduced, the latency of
packet transmission will decrease simultaneously.
\par\null
{It will also help to support the fact that both mesh network and
Mesh-of-Torus network are in line with real world data
center.}\protect\hyperlink{_msocom_4}{{[}O4{]}}~
\par\null
\textbf{Throughput:} Figure 13 have shown statistic of throughput of in
different packet infusion rates and the simulation results for the 8*8
Mesh-of-Torus network and mesh network with a 256 bytes packets size in
differentiated flow pattern. The network will basically attain the same
throughput when the network is not saturated. However, when the network
is saturated, the throughput of Mesh-of-Torus is obviously higher than
that of esh network. More detailed infusion rates for the test have been
listed in table 6.
\par\null
Figure 13. Abscissa represents infusion rates for different groups, and
the coordinate represents for the throughout for the entire network. And
the unit represents for the packets number.
\par\null
\textbf{Link Load Distribution:} Figure 14 have shown the statistics
\textbf{} of \textbf{} the link load distribution in the same network
model deploying Mesh-of-Torus network and mesh network {[}30{]}. Long
links in Mesh-of-Torus network can uniform the load distribution better
by sharing some of the traffic inside different parts in the network.
And simulation results also prove the excellent performance of
Mesh-of-Torus network in traffic distribution balancing as well as
latency reduction. Based on all we have discussed above, Mesh-of-Torus
network is much more suitable for the data center whose local traffic is
much heavier than global traffic, so the higher practicality in real
world data center employment {since data centers in real life are common
in the use of local traffics.}
\par\null\par\null\par\null\par\null\par\null\par\null\par\null\par\null\par\null\par\null
\section*{}
{\label{507127}}
Nunc a aliquet sem, eget aliquet purus. Vestibulum ac placerat mauris.
Proin sed dolor ac justo semper iaculis. Donec varius, nibh sit amet
finibus tristique, sapien ante interdum odio, et pretium sapien libero
nec massa. In hac habitasse platea dictumst. Donec vel augue ac sapien
imperdiet pretium. Maecenas gravida risus id ultricies dignissim.
Maecenas gravida felis quis dolor faucibus, sed maximus lorem
tristique~\(e^{i\pi}+1=0\)
\section*{Acknowledgements}
{\label{687807}}
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Cras egestas
auctor molestie. In hac habitasse platea dictumst. Duis turpis tellus,
scelerisque sit amet lectus ut, ultricies cursus enim. Integer fringilla
a elit at fringilla. Lorem ipsum dolor sit amet, consectetur adipiscing
elit. Nulla congue consequat consectetur. Duis ac mi ultricies, mollis
ipsum nec, porta est.
\selectlanguage{english}
\FloatBarrier
\end{document}