% Template article for preprint document class `elsart'
% SP 2001/01/05
% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/
\documentclass{ctwart}
% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}
% if you use PostScript figures in your article
% use the graphics package for simple commands
%\usepackage{graphics}
% or use the graphicx package for more complicated commands
\usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}
% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\begin{document}
\begin{frontmatter}
% Title, authors and addresses
% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}
\title{Wide - sense nonblocking $\log_d(N,0,p)$ networks}
% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}
\author[1]{ Maja Rotovnik }
\ead{maja.rotovnik@imfm.si}
\author[1,2]{ Janez \v{Z}erovnik }
\ead{janez.zerovnik@imfm.uni-lj.si}
\address[1]{IMFM, Jadranska 19, SI-1000 Ljubljana, Slovenia }
\address[2]{FME, University of Ljubljana, A\v{s}ker\v{c}eva 6, SI-1000 Ljubljana, Slovenia}
\begin{keyword}
% keywords here, in the form: keyword \sep keyword
switching network \sep WSNB \sep strong product \sep chromatic number
\end{keyword}
\end{frontmatter}
% main text
\section{Introduction}
\label{introduction}
\noindent
One of the common architectures that are used in high-speed photonic and electronic switching networks
is the $\log_d (N,m,p)$ switching network \cite{Lea,LeSh}.
In this paper we consider a special case of such network, $\log_d(N,0,p)$ network.
Usually, the architecture is accompanied with the control algorithm that works online, i.e. after arrival of
a connection request, a path through the network is assigned that connects the input and output of the new connection
\cite{KaMi,Danilewicz}.
%The multi $\log_d (N,m,p)$ switching network was first proposed by Lea \cite{Lea}. In this paper we consider
%a special case of such network, $\log_d(N,0,p)$ network, where number of extra stages is $m=0.$
A switching network is wide sense nonblocking (WSNB) if a new call is always routable as long as all previous requests
were routed according to a given routing algorithm \cite{Hwang}. WSNB switching networks were first introduced by
Bene\v{s} \cite{benes} for symmetric $3-$stage Clos network. He proved that $C(n,m,2)$ is WSNB if and only
if $m\geq\left\lfloor \frac{3n}{2}\right\rfloor.$
Here we introduce an auxiliary {\em path graph} of switching network such that the number of required planes
is the chromatic number of the path graph.
From the structure of the path graphs it follows that the minimal
$ p$ is $d^{\left\lfloor \frac{n}{2}\right\rfloor}-1$ for every $n.$
Furthermore, our analysis implies that at least $p$ planes are needed regardless of the control algorithm used.
A special case of this result was proved for a particular algorithm and even $n$
(for $d=2$ in \cite{KaMi1} and for general $d$ in \cite{DaKaMiZa}).
For other cases only bounds in terms of so-called non-blocking conditions
were known \cite{Hwang,Pattavina,kabacinski}.
\section{Basic definitions and notations}
\label{definitions}
\noindent The basic conponents of switching network are crossbar switches and links which connect switches.
The $\log_d(N,0,p)$ switching network consist of $p$ copies of $\log_d(N,0,1),$ called the planes.
Each plane contains $n \cdot d^{n-1}$ switches divided into $n$ stages. In each stage there are $d^{n-1}$
switches and each switch has $d$ inputs and $d$ outputs. Inputs and outputs are numbered $0,1,...,N-1$, $N=d^{n}$, from
top to bottom, and stages are numbered $0,1,...,n$ from left to right.
Examples of $\log_2(8,0,1)$, $\log_2(16,0,1)$, and $\log_3(27,0,1)$ switching networks
are given on figures \ref{fig:lihin}, \ref{fig:sodin}, and \ref{fig:lihin1} respectively.
\begin{figure}[h!]
\centering
\includegraphics[width=8cm]{lihin}
\caption{Example of switching network for $n=3$ and $d=2.$}
\label{fig:lihin}
\end{figure}
\begin{figure}[h!]
\centering
\includegraphics[width=9cm]{sodin}
\caption{Example of switching network for $n=4$ and $d=2.$}
\label{fig:sodin}
\end{figure}
\begin{figure}[h!]
\centering
\includegraphics[width=10cm]{lihin1}
\caption{Example of switching network for $n=3$ and $d=3.$}
\label{fig:lihin1}
\end{figure}
\noindent \textbf{Definition: }
%\begin{definition}
\label{path_graph}
The {\bf path graph} $G_P(n,d)$ of a switching network $\log_d(N=d^{n},0,1)$ is the graph with a vertex $(i,j)$
for every connection $\left\langle i,j\right\rangle$ in the switching network.
Two vertices $(i_1,j_1)$ and $(i_2,j_2)$ are adjacent in $G_P$ if
connections $\left\langle i_1,j_1\right\rangle$ and $\left\langle i_2,j_2\right\rangle$ share an
interstage link in switching network.
%\end{definition}
\noindent For example in figure \ref{fig:sodin} the connections $<0,0>,<1,5>$ share the link between stages $1$ and $2$,
so they are adjacent.
The connections $<0,0>,<2,9>$ are independent because they do not share a link.
\noindent \textbf{Proposition. }
The {\bf path graph} $G_P(n,d)$ is in the worst case isomorphic to the strong product
$(K_d \Box K_d)\boxtimes K_{d^{k-2}}$ when $n=2k-1,$
$k\in \mathbb{N}$ and isomorphic to the $d^k$ copies of $K_{d^k},$ when $n=2k,~k\in \mathbb{N}.$
\bigskip
Proof ommited in the abstract.
\noindent \textbf{Proposition. }
The number of planes $p$ needed to make $\log_d(N,0,p)$ switching network a WSBN is equal to the chromatic number of the path graph.
$$ p = \chi \left( G_P(n,d)\right)
$$
(Proof ommited in the abstract.)
Idea of proof: by construction of the path graph, the vertices corresponding to independent connections are independent and
two vertices are connected when the connections share a link.
Hence any subset of connections can be can be divided into $ p = \chi \left( G_P(n,d)\right)$ independent sets and each of them can
be realized in a different plane.
On the othere hand, it is easy find a set of connections that forms a clique, so it can not be realized in less than $p$ planes
without blocking.
\noindent
Remark. From details of our construction one can find a formula which assigns the color (the plane) on which it should be realized,
so there is no complicated algorithm for assigning the planes needed. Compare to \cite{KaMi1}.
Recall that the chromatic number of the strong product of graphs is less than or equal to product of chromatic numbers
of factors. Equality holds when chromatic number of both factors is equal to their clique number \cite{ImKl}.
Hence we have
%\begin{theorem}
\noindent \textbf{Theorem:}
The $\log_d(N,0,p)$ switching network, $n=\log_dN$, is WSNB if and only if
$$
p\geq \left\{ \begin{array}{l}
d^k,~ \hspace{0.2cm} if ~n=2k,~k\in \mathbb{N}\\
d^{k-1},~ \hspace{0.2cm} if ~n=2k-1,~k\in \mathbb{N}.
\end{array} \right.
$$
%\end{theorem}
% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix
% \section{}
% \label{}
\begin{thebibliography}{00}
% \bibitem{label}
% Text of bibliographic item
% notes:
% \bibitem{label} \note
% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}
\bibitem{Lea}
C.~T.~Lea.
\newblock Multi-$log_2N$ networks and their applications in high-speed electronic and photonic switching systems.
\newblock {\em IEEE Trans. Commun.}, \textbf{38} (1990) 1740--1749.
\bibitem{LeSh}
C.~T. Lea and D.~J. Shyy.
\newblock Tradeoff of horizontal decomposition versus vertical stacking in rearrangeable nonblocking networks.
\newblock {\em IEEE Trans. Commun.}, \textbf{39}, (1991) 899–904.
\bibitem{KaMi}
W.~Kabacinski, M.~Michalski.
\newblock Lower Bounds for WSNB Multi-$log_2N$ Switching Networks.
\newblock {\em Conference on Telecommunications A-ICT 2005}, (Lisbon,Portugal), (2005) 202--206.
\bibitem{Danilewicz}
G. Danilewicz.
\newblock Wide-Sense Nonblocking $Log_d (N, 0, p)$ Multicast Switching Networks.
\newblock {\em IEEE Trans. Commun.}, \textbf{55} (2007) 2193-2200.
\bibitem{Hwang}
F.~K.~Hwang.
\newblock {\em The Mathematical Theory of Nonblocking Switching Networks.}
\newblock World Scientific, Singapore, first ed., 1998; second ed., 2004.
\bibitem{benes}
V.~E.~Bene\v{s}.
\newblock {\em Mathematical Theory of Connecting Networks and Telephone Traffic.}
\newblock Academic Press, New York, 1965.
\bibitem{KaMi1}
W.~Kabacinski, M.~Michalski.
\newblock Wide-Sense Nonblocking $log_2(N,0,p)$ Switching Networks with Even Number of Stages.
\newblock {\em IEEE ICC 2005}, (Seul, South Korea), (2005).
\bibitem{DaKaMiZa}
G.~Danilewicz, W.~Kabacinski, M.~Michalski and M.~Zal.
\newblock Wide-Sense Nonblocking Multiplane Baseline Switching Networks Composed of $d \times d$ Switches.
\newblock {\em IEEE ICC 2007}, (Glasgow, Scotland), (2007).
\bibitem{Pattavina}
A. Pattavina.
\newblock {\em Switching Theory - Architectures and Performance in Broadband ATM Networks.}
\newblock John Wiley \& Sons, England, 1998.
\bibitem{kabacinski}
W. Kabacinski.
\newblock {\em Nonblocking Electronic and Photonic Switching Fabrics.}
Springer, 2005.
%\bibitem{KaDa}
%W.~Kabacinski, G.~Danilewicz.
%\newblock Wide-sense and strict-sense nonblocking operation of multicast multi-$log_2N$ switching networks.
%\newblock {\em IEEE Trans. Commun.}, \textbf{50} (2002) 1025--1036.
%\bibitem{HwLi}
%F. K. Hwang, W.~D. Lin.
%\newblock Necessary and sufficient conditions for rearrangeable $log_d(N,m, p)$.
%\newblock {\em IEEE Transactions on Communications.}, \textbf{53} (2005) 2020-2023.
\bibitem{ImKl}
W.~ Imrich,~S.~Klav\v{z}ar.
\newblock {\em Product graphs: structure and recognition.}
\newblock JohnWiley $\&$ Sons, New York, USA, 2000.
\end{thebibliography}
\end{document}