# Rearrangeable and Repackable S-W-S Elastic Optical Networks for Connections with Limited Bandwidths
## 2 Preliminaries
### Routing Algorithm 1:  
Each connection (\(i\), \(j\), \(1\)) is routed in the \(c\)th FSU of links I\({}_{i}\), I\({}^{\prime}\)\({}_{j}\), O\({}^{\prime}\)\({}_{j}\) and O\({}_{j}\), if the corresponding edge of (\(i\), \(j\), \(1\)) in graph \(G_{F}\) is assigned color \(c\).  
As we can see in Routing Algorithm 1, output \(j\) determines the selection of internal links, i.e., I\({}^{\prime}_{j}\) and O\({}^{\prime}\)\({}_{j}\), and the FSU assignment is determined by the edge coloring of \(G_{F}\). An example is given in Figure 2, where a frame \(F\) consisting of connections (1, 1, 1), (1, 2, 1), (2, 3, 1), (2, 1, 1), and (3, 3, 1) is routed in an SWS1(3, 3, 5) switching fabric according to Routing Algorithm 1. Next, in Theorem 1, we derive the sufficient and necessary conditions under which an SWS1(\(q\), \(p\), \(n\)) switching fabric is RNB for 1-slot connections.  
**Theorem 1**.: _An SWS1(\(q\), \(p\), \(n\)) switching fabric for 1-slot connections is RNB if and only if \(p\geq q\)._  
Figure 2: A frame \(F\) consisting of connections (1, 1, 1), (1, 2, 1), (2, 3, 1), (2, 1, 1), and (3, 3, 1) is given in an SWS1(3, 3, 5) switching fabric. (**a**) A routing of connections in \(F\) under Routing Algorithm 1 referring to the edge-coloring given in (**b**). (**b**) The corresponding graph \(G_{F}\) of (**a**), in which colors 1 and 2 (marked in red font) are adopted for edge-coloring.  
**Proof.** The necessary condition is true when each input \(\mathbf{I}_{i}\) holds \(q\) connections (\(i\), \(i\), \(1\)), each of which is routed in internal links \(\mathbf{I}^{\prime}_{i}\) and \(\mathbf{O^{\prime}}_{i}\) according to Routing Algorithm 1, for \(1\leq i\leq q\). Next, we consider the sufficient condition. From the design of Routing Algorithm 1, we can see that all connections destined to the same output, say \(\mathrm{O}_{j}\), are routed in the same internal links \(\mathbf{I}^{\prime}_{j}\) and \(\mathbf{O^{\prime}}_{j}\). Since each output has \(n\) FSUs, at most \(n\) 1-slot connections can be destined to the same output link. Thus, at most \(n\) 1-slot connections can be assigned to each internal link, which occupies \(n\) FSUs. Recall that for each frame \(F\) of connections given in an SWS1(\(q\), \(p\), \(n\)) switching fabric, the corresponding graph \(G_{F}\) is \(n\)-edge colorable. This implies that there exists an FSU assignment, i.e., a nonblocking routing, to rearrange all connections assigned in the same link by Routing Algorithm 1. Thus, an SWS1(\(q\), \(p\), \(n\)) switching fabric is RNB if its number of internal links, i.e., \(p\), is sufficient to carry all connections. Recall that each connection (\(i\), \(j\), \(1\)) is held by internal links \(\mathbf{I}^{\prime}_{j}\) and \(\mathbf{O^{\prime}}_{j}\) (Routing Algorithm 1), and an SWS1(\(q\), \(p\), \(n\)) switching fabric has only \(q\) output links. Therefore, \(q\) internal links per stage, i.e., \(p\leq q\), are sufficient for the SWS1(\(q\), \(p\), \(n\)) switching fabric to be RNB.  
For an SWS1(\(q\), \(p\), \(n\)) switching fabric with given parameters \(q\) and \(n\), reducing the value of \(p\), namely, the number of BV-WSs in stage 2, leads to lowering the hardware cost, area requirements, and power consumption. Theorem 1 shows that the upper bound of the proposed RNB SWS1(\(q\), \(p\), \(n\)) switching fabric for 1-slot connections reduces by around half the number of middle switches compared to the number in the SNB SWS1(\(q\), \(p\), \(n\)) switching fabric given in [7]. It is worth noting that the left \(q\times p\) BV-SS of the SWS1(\(q\), \(p\), \(n\)) switching fabric for 1-slot connections is RNB as well if and only if \(p\geq q\). This is true since each connection (\(i\), \(j\), \(1\)) is routed in the \(c\)th FSU of links \(\mathbf{I}_{i}\) and \(\mathbf{I}^{\prime}_{j}\) if color \(c\) is assigned for its corresponding edge in graph \(G_{F}\). In other words, an RNB SWS1(\(q\), \(p\), \(n\)) switching fabric for 1-slot connections can be reduced to a \(q\times q\) BV-SS. \(\Box\)