# 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\)
** As we can see from Routing Algorithm 2 (for Arrivals), connections assigned in each link of an SWS1(\(q\), \(p\), \(n\)) switching fabric occupy (at most \(n\)) consecutive FSUs from FSU 1 if no connection departs. Since each link has \(n\) FSUs, the \(m\) available common adjacent FSUs of \(\mathrm{I}_{i}\) and \(\mathrm{I^{\prime}}_{q\cdot(j-1)+i}\) (or \(\mathrm{O}_{j}\) and \(\mathrm{O^{\prime}}_{q\cdot(j-1)+i}\)) can always be found for each arrival connection \((i,j,m)\) if no connection departs. In addition, connections from the same input are routed in \(q\) internal links per stage according to their destinations (Routing Algorithm 2 (for Arrivals)), and there are \(q\) input links. Thus, at most \(q^{2}\) internal links, i.e., \(p\geq q^{2}\), are required for an SWS1(\(q,p,n\)) switching fabric to be nonblocking if no connection departs. Once an existing connection departs, the \(m\) available common adjacent FSUs of \(\mathrm{I}_{i}\) and \(\mathrm{I^{\prime}}_{q\cdot(j-1)+i}\) (or \(\mathrm{O}_{j}\) and \(\mathrm{O^{\prime}}_{q\cdot(j-1)+i}\)) may not be found for some connection \((i,j,m)\). This may lead to a blocking state, and rearrangements are required. Figure 2(b) gives an example, where after connection \((1,1,1)\) departs, \((1,1,2)\) arrives and is blocked since no two available common adjacent FSUs of links \(\mathrm{I}_{1}\) and \(\mathrm{I^{\prime}}_{1}\) can be found. Suppose \((i,j,m)\) arrives in the switching fabric and it is blocked. In order to maintain a nonblocking state, all existing connections held in links \(\mathrm{I}_{i}\) and \(\mathrm{O}_{j}\) are packed together, and they are rearranged from the left side of \(\mathrm{I}_{i}\) and \(\mathrm{O}_{j}\); that is, all of these connections use the leftmost adjacent FSUs of \(\mathrm{I}_{i}\) and \(\mathrm{O}_{j}\), such that the remaining free FSUs of links \(\mathrm{I}_{i}\) and \(\mathrm{O}_{j}\) are still consecutive and available for \((i,j,m)\) (Figure 2(c)). Once a blocking state occurs due to \((i,j,m)\), the algorithm given below is adopted to rearrange all of the existing connections held in \(\mathrm{I}_{i}\), say \((i,j^{\prime},m)\), and \(\mathrm{O}_{j}\), say \((i^{\prime},j,m)\) for \(1\leq i,i^{\prime},j,j^{\prime}\leq q\). **Routing Algorithm 2 (for Rearrangements): Step 1:** All connections held in \(\mathrm{I}_{i}\), that is, \((i,j^{\prime},m)\) for \(1\leq j^{\prime}\leq q\), are rearranged to the leftmost \(m\) adjacent available FSUs of \(\mathrm{I}_{i}\) and the same FSUs of \(\mathrm{I^{\prime}}_{q\cdot(j^{\prime}-1)+i}\). Step 2:** All connections held in \(\mathrm{O}_{j}\), that is, \((i^{\prime},j,m)\) for \(1\leq i^{\prime}\leq q\), are rearranged to the leftmost \(m\) adjacent available FSUs of \(\mathrm{O}_{j}\) and the same FSUs of \(\mathrm{O^{\prime}}_{q\cdot(j-1)+i^{\prime}}\). Figure 2(c) gives an example where the arrival connection \((1,1,2)\) can be routed in the SWS1(\(3,9,5\)) switching fabric after all existing connections carried in links \(\mathrm{I}_{1}\) and \(\mathrm{O}_{1}\) are rearranged by Routing Algorithm 2 (for Rearrangements). Suppose Routing Algorithm 2 (for both Arrivals and Rearrangements) is used 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\). In Theorem 2, we derive the sufficient condition under which the SWS1(\(q\), \(p\), \(n\)) switching fabric will be RNB. **Theorem 2**. : _An SWS1(\(q\), \(p\), \(n\)) switching fabric for \(m\)-slot connections, \(1\leq m\leq m_{max}\) and \(2\leq m_{max}\leq n\), is RNB if \(p\geq q^{2}\)._  
**Proof. ** Routing Algorithm 2 (for Arrivals) guarantees 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\) is nonblocking and all connections carried on each link occupy adjacent FSUs from FSU 1 if \(p\geq q^{2}\) and no connection departs (Property 1).