# Rearrangeable and Repackable S-W-S Elastic Optical Networks for Connections with Limited Bandwidths
## 4 RNB and RPNB SWS1(\(q\), \(p\), \(n\)) Switching Fabrics with \(2\leq m_{\max}\leq n\)  
### RNB SWS1(\(q\), \(p\), \(n\)) switching fabrics with \(2\leq m_{\max}\leq n\)  
Recall that an RNB switching fabric is defined as one in which each frame of connections given in the switching fabric can be routed simultaneously. We considered this definition in Section 3. An alternate definition of an RNB switching fabric is one in which the nonblocking state can be maintained by rearranging existing connections upon the arrival of a connection. Note that this definition, as with the RPNB switching fabric, considers connections that arrive and depart the switching fabric sequentially. In order to extend the RNB results for \(2\leq m_{\max}\leq n\), which will be given in Theorem 2 later, to easily being RPNB (see Section 4.2 for details), in this section, we consider the RNB switching fabric given by the alternate definition. That is, we route each connection sequentially as it arrives in the switching fabric. In addition, the connection which requires rearrangement has to be rearranged not only inside the switching fabric but also in the input and the output links. Given an SWS1(\(q\), \(p\), \(n\)) switching fabric for \(m\)-slot connections where \(1\leq m\leq m_{\max}\) with \(2\leq m_{\max}\leq n\), we partition all internal links in each stage into \(q\) groups numbered from \(1\), each of which consists of \(q\) internal links (see Figure 2(a)), and allow the \(i\)th link of group \(j\), i.e., \(\mathbf{I}^{\prime}_{q\cdot(j-1)+i}\) and \(\mathbf{O^{\prime}}_{q\cdot(j-1)+i}\), to carry only connections from input \(\mathbf{I}_{i}\) and destined to output \(\mathrm{O}_{j}\). That is, connections from the same input can be carried by \(q\) internal links per stage according to their destinations, and connections carried in the same internal link are destined to the same output. Note \(q^{2}\) internal links, i.e., \(p=q^{2}\), are required in each link stage under this scheme. We use the algorithm shown in the following to set up each arrival connection (\(i\), \(j\), \(m\)). **Routing Algorithm 2 (for Arrivals):**  
**Step 1:** (\(i\), \(j\), \(m\)) is routed in the leftmost \(m\) adjacent available FSUs of \(\mathrm{I}_{i}\) and the same FSUs of \(\mathrm{\mathsf{O}^{\prime}}_{q\cdot(j-1)+i}\). Figure 3a gives an example, where connections (1, 1, 1), (1, 2, 1), (1, 3, 1), (1, 2, 1), (2, 1, 2), (2, 2, 3), and (3, 3, 3) arrive in an SWS1(3, 3, 5) switching fabric sequentially and Routing Algorithm 2 (for Arrivals) is applied. Suppose Routing Algorithm 2 (for Arrivals) is applied on an SWS1(\(q\), \(p\), \(n\)) switching fabric for \(m\)-slot connections where \(1\leq m\leq m_{\max}\) with \(2\leq m_{\max}\leq n\), and no existing connection departs. In Property 1, we derive the sufficient condition under which an SWS1(\(q\), \(p\), \(n\)) switching fabric will be nonblocking. Figure 3: Suppose connections (1, 1, 1), (1, 2, 1), (1, 3, 1), (1, 2, 1), (2, 1, 2), (2, 3), and (3, 3, 3) arrive sequentially in an SWS1(3, 9, 5) switching fabric. Note each dashed box is a group of internal links. (**a**) These connections are routed by Routing Algorithm 2 (for Arrivals). (**b**) Suppose connection (1, 1, 1) departs, and (1, 1, 2) arrives. Then, connection (1, 1, 2) is blocked. (**c**) Connections marked in green, orange, yellow, and purple are rearranged according to Routing Algorithm 2 (for Rearrangements), and (1, 1, 2) can be routed in the SWS1(3, 9, 5) switching fabric. **Property 1**. : _Suppose Routing Algorithm 2 (for Arrivals) is applied on an SWS1(\(q\), \(p\), \(n\)) switching fabric for \(m\)-slot connections where \(1\leq m\leq m_{max}\) with \(2\leq m_{max}\leq n\). If connections are only allowed to be added into the switching fabric and no existing connections can be deleted, then the switching fabric will never go into a blocking state if \(p\geq q^{2}\)._  
**Proof.