# Rearrangeable and Repackable S-W-S Elastic Optical Networks for Connections with Limited Bandwidths
## 2 Preliminaries  
The SWS1 switching fabric considered in this paper, represented as SWS1(\(q\), \(p\), \(n\)), is given in Figure 1. It uses bandwidth-variable space switches (BV-SSs) in stages 1 and 3, and bandwidth-variable wavelength-converting switches (BV-WSs) in stage 2. The BV-SS has no spectrum conversion capability, and the BV-WS has full-range conversion capability. Specifically, in a BV-SS, an \(m\)-slot connection, which uses \(m\) adjacent FSUs in the input, must be switched to the \(m\) adjacent FSUs of the _same_ nominal frequencies in the output; in a BV-WS, an \(m\)-slot connection, which uses \(m\) adjacent FSUs in the input, can be switched to any other \(m\) adjacent FSUs in the output. The internal architectures of a BV-SS and a BV-WS can be found in [7]. In the SWS1(\(q\), \(p\), \(n\)) switching fabric (Figure 1), the first (or input) stage contains one BV-SS of capacity \(q\times p\). The middle stage contains \(p\) BV-WSs, each of capacity \(1\times 1\). The last (or output) stage contains one BV-SS of capacity \(p\times q\). Each link has \(n\) FSUs, which are numbered from \(1\). I\({}_{i}\) (or O\({}_{i}\)) represents the \(i\)th input (or output) for \(1\leq i\leq q\), and I\({}^{\prime}_{j}\) (or O\({}^{\prime}_{j}\)) represents the input (or output) of the \(j\)th BV-WS for \(1\leq j\leq p\). We also call I\({}^{\prime}_{j}\) and O\({}^{\prime}_{j}\) internal links. The SWS1 switching fabric serves \(m\)-slot connections. An \(m\)-slot connection is represented as \((i,j,m)\) if it is from I\({}_{i}\) and destined to O\({}_{j}\). In order to route each \((i,j,m)\) in an SWS1(\(q\), \(p\), \(n\)) switching fabric, we have to find two internal links I\({}^{\prime}_{k}\) and O\({}^{\prime}_{k}\) where \(1\leq k\leq p\), which have \(m\) adjacent FSUs, using the same nominal frequencies, available for \((i,j,m)\) in the input I\({}_{i}\) and output O\({}_{j}\), respectively (see Figure 1). That is, we have to find two links, I\({}^{\prime}_{k}\) and O\({}^{\prime}_{k}\), such that there are \(m\) available common  
Figure 1: An SWS1(\(q\), \(p\), \(n\)) switching fabric. adjacent FSUs of links I\({}_{i}\) and I\({}^{\prime}\)\({}_{k}\) (or O\({}_{j}\) and O\({}^{\prime}\)\({}_{k}\)). When two such internal links can be found, the SWS1(\(q\), \(p\), \(n\)) switching fabric is nonblocking to (\(i\), \(j\), \(m\)); otherwise, (\(i\), \(j\), \(m\)) is blocked. Sufficient and necessary conditions under which an SWS1(\(q\), \(p\), \(n\)) switching fabric will be SNB were derived in [7], which showed that an SWS1(\(q\), \(p\), \(n\)) switching fabric for \(m\)-slot connections with \(1\leq m\leq m_{\max}\), is SNB if and only if  
\[p\ \geq\ \left\{ \begin{array}{ll}2m_{\max}\cdot(q-1)+1,&\text{for $m_{\max} \leq\ \frac{nq}{2q-1}$,}\\ nq-\frac{nq}{2q-1}+1,&\text{for $m_{\max}\geq\frac{nq}{2q-1}+1$.}\end{array} \right. \tag{1}\]  
In this paper, two different approaches are proposed to generate RNB SWS1(\(q\), \(p\), \(n\)) switching fabrics for \(m\)-slot connections where \(1\leq m\leq m_{\max}\) with \(m_{\max}=1\) and \(2\leq m_{\max}\leq n\), respectively. A similar approach to that for generating RNB SWS1(\(q\), \(p\), \(n\)) switching fabrics with \(2\leq m_{\max}\leq n\) is also applied to generate an RPNB SWS1(\(q\), \(p\), \(n\)) switching fabric with \(2\leq m_{\max}\leq n\). Rearrangeable Nonblocking (RNB) SWS1(\(q\), \(p\), \(n\)) Switching Fabrics with \(m_{\max}=1\)  
Suppose a frame \(F\) of connections is given in an SWS1(\(q\), \(p\), \(n\)) switching fabric for \(m\)-slot connections with \(1\leq m\leq m_{\max}\) (Figure 2a). The routing of connections includes two parts: (1) Internal link selection and (2) FSU assignment. In this section, we propose a graph-theoretic approach to study the FSU assignment in the case of \(m_{\max}=1\). We construct a graph \(G_{F}\) in which each left vertex \(i\) (or right vertex \(j\)) denotes an I\({}_{i}\) (or O\({}_{j}\)) and an edge between two vertexes \(i\) and \(j\) denotes a connection (\(i\), \(j\), \(1\)) in frame \(F\) (Figure 2b).