% Reehan's LaTeX article template
% July 1, 2007
% Reehan Shaikh - reehan.shaikh@cs.mcgill.ca
% Very basic but helps in managing large documents
% If you need any help, email me! The point of this
% is so that you can separate your document into
% smaller files for easier navigation and preparation.
% All the "inclusion" of external files is done for
% you. Just fill in your content.

% IMPORTANT - any external files you want to include
% must have the .tex file extension. This should be
% case anyways because the sub-files you write will
% have LaTeX style commands so it can included here.
% Also, it is better to have no spaces in the file name.

% default article has one column and 10pt font
% Uncomment the one you prefer (for twocolumn)
% Can change font to 10, 11 or 12pt
\documentclass[runningheads]{llncs}
%\documentclass[twocolumn,11pt]{article}

% set paragraph indent (LaTeX's is too small)
\parindent = 0.25in

% import package to include external TEX input
\usepackage{moreverb}
% import package to include EPS images
\usepackage{epsfig}
% import package to have nice mathematics
\usepackage{amsmath}

\usepackage{graphicx}   % need for figures
\usepackage{subfigure}  % use for side-by-side figures

% beginning actual document, NO MORE preamble stuff
\begin{document}

% single author, if more than one, see below
% \\ means a line break
% two authors. if you need more authors, add a c to the
% end of the next \author line for an extra centered column
% and after the information for the second author, separate
% the third authors info with a '&'.
%\author{\begin{tabular}[t]{cc}
%   First Author & Second Author\\
%   Lab Affiliation & Second Lab\\
%   Faculty Affiliation & Second Faculty\\
%   University, City, Prov, Country & Second Univ, City, Prov, Country\\
%   author@some.email.com & second@email.com
%   \end{tabular}}

% title, if title too long, separate with \\ (line breaks)
\author{Sina Meraji\\
   McGill University, Montreal, Quebec, Canada\\
   smeraj@cs.mcgill.ca}

\institute{School of Computer Science}

\title{An Introduction to Interconnection Networks and Xmulator}

% today's date, changes everytime you compile
\date{\today}
% specific date
%\date{May 2007}
% no date
%\date{}

% make title page
\maketitle

% I like ALL my paragraphs indented, so I have to add the \indent
% command {twice for some reason) because LaTeX doesn't like to
% indent the first paragraph. If you don't like it, comment it out.

% begin abstract. This command actually make the font and side margins
% smaller if using one column. It also adds the "Abstract" heading.
\begin{abstract}
\indent
Today, Communication and interconnection between different components of a system limit the performance of most digital systems. In a high-end system today, most of the power is used to drive wires, and most of the clock cycle is spent on wire delay, not gate delay. As technology improves, memories and processors become smaller, faster, and less expensive. The speed of light, however, remains unchanged. The pin density and wiring density that govern interconnections between system components are scaling at a slower rate than the components themselves. Also, the frequency of communication between components is lagging far beyond the clock rates of modern processors. These factors combine to make interconnection the key factor in the success of future digital systems.
% include the file abstract.tex
%\input{content/abstract}
\end{abstract}

% From here on, you can insert or delete sections and subsections at
% your will. Just make sure your included file has the proper path
% and a .tex extension and no spaces in the name of the file.

\section{Introduction}
One way for processors to communicate data is to use a shared memory and shared variables. A realistic assumption is that each processor has its own private memory and data communication takes place using message passing via an interconnection network. Interconnection networks are beginning to replace buses as the standard system-level interconnection. They are also replacing dedicated wiring in special-purpose systems as designers discover that routing packets is both faster and more economical than routing wires \cite{5}. We will introduce some of the most important interconnection networks in section 2. \textit{Routing} and \textit{Switching} are two main concepts of computer networks (also interconnection networks) that we describe them here.\\

Routing algorithms specify the path to be taken by the messages sent from the source nodes to the destination nodes. A routing algorithm must provide low-latency message delivery, be aware of deadlocks, starvation, and livelock, and be able to work well under various traffic loads. The message latency is dependent to the number of hops taken by a message, hence minimal routing algorithms are usually considered as per which a message always moves closer to its destination with each hop taken; another advantage of minimal routing is that livelocks are avoided. Starvation can also be avoided by allocating resources such as channels and buffers in a proper manner. Ensuring deadlock-freedom is a difficult issue and must be taken care of when designing the routing algorithm \cite{12}. A simple routing algorithm is shown in section 3.\\

A switching mechanism determines how and when the router switch is set; that is, the input channel is connected to the output channel selected by the routing algorithm. In other words, the switching mechanism determines how network resources are allocated for message transmission \cite{5}. One of the most popular switching techniques is Wormhole switching \cite{19} in which a message is divided into a sequence of flits (the smallest fixed-size units of data). If a communication channel transmits the first flit (also called the \textit{header} flit) of a message, it must transmit all the remaining flits of the same message before transmitting flits of another message. At any given time, the flits corresponding to a message occupy contiguous channels in the network. As a result, the message latency is proportional to the sum of the number of cycles spent in waiting for suitable channels to route message flits, number of hops from the source node to the destination node, and message length \cite{12}.\\

The rest of the paper is as follows in section 2 we introduce the most famous interconnection networks. Section 3 shows two simple routing algorithms for heypercube and necklace hypercube interconnection networks. In section 4 Xmulator introduce as simulation platform for interconnection networks. Finally section 5 concludes this report.\\
%\indent\indent
%\input{content/intro}

\section{Interconnection Networks}
A large number of interconnection networks have been proposed and studied for highly parallel distributed-memory computers \cite{1,3,2,18,4,6,10,8,15,16,17}. Here we introduce some of the most important of them. Before introducing the network topologies let's define some important properties of interconnection networks.\\ \\
\textbf{Node degree:} Number of channels connecting that node to its neighbors.\\
\textbf{Diameter:} The maximum distance between two nodes in the network.\\
\textbf{Regularity:} A network is regular when all the nodes have the same degree.\\
\textbf{Symmetry:} A network is symmetric when it looks alike from every node.\\

\subsection{Fully Connected}
This is one of the most power full interconnection networks in which each node is connected to all other nods via a direct path. An instance of this network is shown in figure 1.\\

If we have N nodes, node degree is equal to $N-1$ and the total number of edges in this network is equal to $N(N-1)/2$. Fully Connected is a regular and symmetric network with a diameter equal to 1. Although it is a very power full network 
the construction cost is so much when we have large number of nodes \cite{20}.

\begin{figure}[h!]
\begin{center}
\includegraphics[width=45mm, height=40mm]{Figures/pic11}
\caption{\label{Fig:fig1} An example pf fully connected interconnection network.}
\end{center}
\end{figure}



\subsection{Mesh and Torus}
In a \textit{Mesh} network nodes are arranged in a k dimensional lattice and we have a total number of $w^k$ nodes. It is neither regular nor symmetric. An example of 2 dimensional mesh with width equal to 4 is shown in figure 2-a. A special case of mesh network in which we have a direct path (wraparound) between the first and the last node of each array is called \textit{Torus}. Torus is a regular and symmetric network. Two instances of 2 dimensional and 3 dimensional Tours topologies are shown in figure 2-b and 2-c \cite{20}.\\


\begin{figure}[h!]
\begin{center}
\subfigure[2 dimensional mesh]{
\includegraphics[width=45mm, height=35mm]{figures/pic2a1}}
\subfigure[2 dimensional Torus]{
\includegraphics[width=45mm, height=35mm]{figures/pic2b1}}
\subfigure[3 dimentional Torus]{
\includegraphics[width=45mm, height=35mm]{figures/pic2c1}}
\caption{\label{fig2} Different examples of Mesh network.}
\end{center}
\end{figure}



\subsection{hypercube (binary n-Cube)}
One of the most power full and well structured interconnection networks is \textit{n-Cube} in which $2^k$ nodes are arranged in a k dimensional hypercube. The nodes are numbered $0 , 1, \ldots, 2^k -1$ and two nodes are connected if their binary labels differ by exactly one bit. Hypercube is regular and symmetric network with a diameter equal to $k$. an instance of 1, 2 and 3 dimensional hypercubes are shown in figure 3-a, 3-b and 3-c.\\

\begin{figure}[h!]
\begin{center}
\subfigure[1 dimensional]{
\includegraphics[width=35mm, height=15mm]{figures/pic3a1}}
\subfigure[2 dimensional]{
\includegraphics[width=35mm, height=25mm]{figures/pic3b1}}
\subfigure[3 dimentional]{
\includegraphics[width=35mm, height=25mm]{figures/pic3c1}}
\caption{\label{fig3} Different examples of hypercube topology.}
\end{center}
\end{figure}


%\subsection{Necklace Hypercube}
%Among different interconnection network topologies, hypercube has many desirable properties. It is not, however, scalable, i.e. when adding some few nodes to it, we must duplicate the network size to reach the next specified network size. The \textit{Necklace Hypercube}, introduced in [13], is a new interconnection network based on hypercube network which constructed by appending a necklace of processors (or nodes, interchangeably) to each edge. We connect $ith$ dimension neighbours by an array of nodes, as a necklace. The necklace length may be fixed or variable for different edge necklaces. In the former, there are fixed number of nodes between each two adjacent neighbours on a necklace. The network is called \textit{regular necklace hypercube}, and can be defined as $(n, k)-RNH$, where $n$ is the number of dimensions and $k$ is the necklace size. It has many desirable properties such as its scalability and efficient VLSI layout that make it more attractive than the hypercube network [13]. Actually necklace-hypercube is an undirected graph $G = (V, E)$, where $u \in V$  is defined as $u = (b, d, i)$ with $b$ (denoting the Base Vertex) being the hypercube node address of the node with smaller address in its dimension, $d$ (difference), $0 \leq d \leq n$, is the dimension of the necklace (containing the node), and $i$ (as the index) is the index of the node in its necklace.  Note that $d$ for the hypercube vertices (or base vertices) is zero. A $(3,4)-RNH$ is shown in figure 4 [12].


%\begin{figure}[h!]
%\begin{center}
%\includegraphics[width=55mm, height=50mm]{Figures/pic41}
%\caption{\label{fig4} A regular necklace hypercube with n=3 and k=4.}
%\end{center}
%\end{figure}



\subsection{Star Graph}
The star graph is an attractive alternative to the hypercube, and compares favorably with it in several aspects. Let $V_n$  be the set of all $ n! $  permutations of symbols $ 1, 2, 3, \ldots, n $. For any permutation $ v \in V_n $ , if we denote the $ith$ symbol of $v$ by $v(i)$, then $v$ can be written as $ v(1)v(2)\ldots…v(n) $.\\
A \textit{star graph} on $n$ symbols, $S_n = (V_n , E_n)$, is an undirected graph with $n!$ nodes, where each node $v$ is connected to $n-1$ nodes which can be obtained by interchanging the first and ith symbols of $v$, i.e. $ [v(1)v(2) \ldots v(i)v(i+1) \ldots v(n),v(i)v(2) \ldots v(i-1)v(1)v(i+1) \ldots v(n)] \in E_n$, for $2 \leq i \leq n$.  We call these $n - 1$ connections as dimensions. Thus each node is connected to $n - 1$ nodes through dimensions $2, 3, \ldots… ,n$. $S_n$ is also called an n-star or an n-dimensional star. Figure 4 shows a $S_4$ \cite{9}.


\begin{figure}[h!]
\begin{center}
\includegraphics[width=55mm, height=50mm]{Figures/pic51}
\caption{\label{fig5} An instance of Star graph ($s_4$).}
\end{center}
\end{figure}


\section{Routing Algorithm}
\textit{Routing} is the process of selecting paths in a network along which to send data or physical traffic. Routing directs forwarding, the passing of logically addressed packets from their source toward their ultimate destination through intermediary nodes; typically hardware devices called routers, bridges, gateways, firewalls, or switches. Ordinary computers with multiple network cards can also forward packets and perform routing, though with more limited performance \cite{21}. Here we show a famous routing algorithm for hypercube which named e-Cube and also a routing algorithm for Necklace hypercube which is based on e-Cube routing.\\

For n-dimensional hypercubes, e-Cube routing produces deadlock-free paths between sources and destinations. This algorithm is described in Figures 5, where FirstOne() is a function that returns the position of the first bit set to one, and Internal is the channel connecting to the local node. The first sentence in algorithm computes the offset from the current node to the destination node. This offset is the value carried by the header when relative addressing is used. If the offset equals to 0 it means that the current node is the destination node, otherwise we send the packet on first link which has a non-zero value in the offset \cite{5}.\\

\begin{figure}[h!]
\begin{center}
\includegraphics[width=	80mm, height=60mm]{Figures/doc11}
\caption{\label{fig6} e-Cube routing for hypercube.}
\end{center}
\end{figure}

%Here we also show a deterministic routing algorithm for the necklace hypercube which is based on e-cube routing algorithm. Consider a minimal one-to-one routing from node $u=(b_1,d_1,i_1)$ to node $v=(b_2,d_2,i_2)$ . Let us start with an example in the $(3,4)-RNH$ network (figure 4) with source node $u=(100,10,001)$ and destination node $v=(011,11,100)$. Thus, the base vertices for the source node are  $s_1=100$ and  $s_2= 110$, and for the destination node are  $d_1=011$ and  $d_2=111$. Let for any node $x, NBV(x)$ be the distance to the neighbour base vertex. We have $NBV(s_1)=1, NBV(s_2), NBV(d_1)=2, NBV(d_2)=1$. Note that $H(s_1,d_1)=3$  indicates a distance of $3+1+2=6$, $H(s_1,d_2)=2$ indicates a distance of $2+1+1=4$, $H(s_2,d_1)=2$  indicates a distance of $2+2+2=6$, and $H(s_2,d_2)=1$ indicates a distance of $1+2+1=4$  hops. Thus, the minimum distance is 4 hops, and the optimal path is $(u,100,110,111,v)$.\\

%\begin{figure}[h!]
%\begin{center}
%\includegraphics[width=	150mm, height=100mm]{Figures/doc21}
%\caption{\label{fig7} One-to-one routing algorithm for Necklace Hypercube.}
%\end{center}
%\end{figure}


%Figure 7 shows the routing algorithm between nodes $u=(b_1,d_1,i_1)$ and $v=(b_2,d_2,i_2)$ in pseudo code. This algorithm generates a path with a length of, at most, \textit{optimal path length +1}. Note that the algorithm contains three main steps: At first we move towards the nearest base neighbour and it is optimal, because if the other base node has been located on the optimal path, the algorithm reaches to it by one hop more which is at most equal to the length of the path from source to this base vertex, then we move towards the nearest neighbour of the destination by the use of e-cube routing. Now the current node is one of the base vertices of the destination's necklace. Since only these two vertices know the number of nodes on their necklace (in general), it is possible that, if we are in one of these nodes, the other node must be on the optimal path and just in this situation we should pass one hop more \cite{13}.

\section{Xmulator}
Simulation is the most effective way to evaluate the performance of an interconnection network. \textit{XMulator}, is an object-oriented listener-based simulation environment for evaluating multicomputer interconnection networks. The simulator involves a toolbox of various network topologies, routing algorithms, switching techniques, and flexible router models. Xmulator uses listenerbased integration   methodology, which has a great impact on extensibility of the system. Mixed-mode event processing improves the performance of the simulator. By decoupling individual parts of the code, XMulator enables independent code development and creates a flexible and extensible environment for different aspects of network design. This simulator uses XML format to define network topologies, input parameters, and outputs reports providing a high level of flexibility. To the best of the designers' knowledge, it is the first simulator enabled to simulate any arbitrary interconnection topology under different working conditions including in the presence of faults \cite{14}. Two main features of Xmulator in comparison with other simulators are listener-based integration and multilayered architecture which we described here briefly.\\

One of the main features of Xmulator is Listener-based integration which solves the problem of two-way dependency that leads to a non-extensible design. For example, consider a Queue component developed by developer A and a Generator inserts the objects to the Queue and developed by developer B. Each one must know the design of the other one because Generator must provide a link to Queue and awake it when a new object is ready to be inserted, and on the other hand, Queue must know the architecture of Generator to accept the objects. In listener-based integration, Queue provides an event, say onObjectReceived, generally to everyone who may be interested in this event. Designer of the Generator does not know about the architecture of the other components that would potentially use it later. On the other hand, Queue knows the Generator and simply registers a method on the list of listeners of the event that is called every time a new object is received by Generator.\\

Xmulator also uses a multilayer architecture which is one of the most important differences with other simulators. In multilayer architecture each layer provides service to upper layers and depends on the lower layers. Using the listener-based integration helps the designers to build multi-layered architecture simply. The lowest layer consists of general tools like different continues and discrete distributions. The second layer consists of base components. We have some events, basic components, and a simulation engine in this layer which are essential for a simple simulation. The engine holds and manages a queue of events. The main role of the engine is processing of events sorted by the fire time. Execution of a event may generate some other new events. The lighter the engine structure is, the more modular and more extensible the architecture could be developed. The engine does not need to know the event types and their internal processes. It is sufficient to know which event belongs to which component and when it must be fired.\\

Events are sorted according to the firing time in apriority queue. The data structure to save this queue is so important and has a great impact on the performance of simulator. Arrays and linked lists have lower performance than AVL trees. In this simulator the red-black tree is used, a special case of an AVL tree, as the data structure for saving the data. Each data node of the tree contains a queue of events that have the same firing time. This is one of the main differences of the current simulator and previous simulators like DEVS in which arrays or linked lists are used as date structures.\\
Different layers could be defined at the top of this layer to use the features of this layer for simulation any specific applications. One of the most important layers which is defined on the top of the based component layer is interconnection network layer. In this layer we can implement different types of regular and semi-regular interconnection network topologies such as meshes, hypercubes and necklace hypercubes. Different routing algorithms for different interconnection topologies can also be implemented in this layer.
\section{Conclusion and future work}

In the current report, we introduced the main basics of interconnection networks. The main topologies of interconnection networks are introduced. We also show the e-cube routing algorithm for hypercube topology which is one of the famous topologies in this area. Necklace hypercube and Stretched hypercube are two subsets of hypercube topology which has a better VLSI layout than hypercube and as a result they can be constructed with a lower cost. In the future work, we use atom3 which is a tool for multi-paradigm modelling to model different instances of hypercube topology. A comparison between these topologies will be shown in the final report.
% if you don't want everything in your biblio.bib file to be
% inserted into the bibliography, comment the nocite{*}. If
% not, only those entries you cite will be included. Make
% sure your biblio has a .bib extension and not .tex! And
% if you don't cite anything, you will get an error.
\nocite{*}
\bibliographystyle{plain}
\bibliography{biblo}

% end document
\end{document}
