# Rearrangeable Nonblocking Conditions for Four Elastic Optical Data Center Networks
## 4 RNB DCN2 and DCN4 Networks  
Similar to Section 3, we first consider the RNB DCN2 network and then the RNB DCN4 network. For the DCN2 network (Figure 2b), \(I_{u\cdot i}\) (or O\({}_{v\cdot j}\)) is used to represent the fiber connecting ToR-T \(u\cdot i\) (or ToR-R \(v\cdot j\)) and the \(u\)th PC (or \(v\)th BV-WSS), and \(I^{\prime}_{u}\) (or O\({}^{v}_{v}\)) is used to represent the fiber connecting the \(u\)th PC (or \(v\)th BV-WSS) and the BV-SS for \(1\leq u\), \(v\leq r\) and \(1\leq i\), \(j\leq s\). Next, we will propose Multigraph Approach B and Routing Algorithm B for the DCN2 network in the sense of being RNB by modifying Multigraph Approach A and Routing Algorithm A, respectively. **Multigraph Approach B:**  
Given a DCN2(\(s\), \(r\), \(q\), \(k\)) network and a frame \(F\) of connections, multigraph \(G^{\prime}_{F}\) is constructed in the following way. Let each left vertex \(u\) (or right vertex \(v\)) in \(G^{\prime}_{F}\) be the \(u\)th (or \(v\)th) group of \(s\) ToR-Ts \(u\cdot i\) (or ToR-Rs \(v\cdot j\)) for \(1\leq i\), \(j\leq s\). An edge is added between two vertexes \(u\) and \(v\) in \(G^{\prime}_{F}\) if there is an \(m\)-slot connection from the \(u\)th ToR-T group destined to the \(v\)th ToR-R group (see Figure 5a). Figure 5: Given a DCN2(\(2\), \(2\), \(2\), \(8\)) network and a frame \(F\) of connections (1-1, 2-1, 2), (1-1, 2-2, 1), (1-2, 1-2, 1), (2-1, 1-1, 2) and (2-2, 1-2, 2): (a) The corresponding multigraph \(G^{\prime}_{F}\) generated by Multigraph Approach B. Note that \(G^{\prime}_{F}\) is edge-colored by colors 1, 2, 3 and 4 (marked in red font), and left and right vertices are marked in blue and black, respectively. (b) A routing of connections in frame \(F\) according to Routing Algorithm B in association with the edge-coloring of \(G^{\prime}_{F}\). Since each group of ToR switches can generate at most \(sq\)\(m\)-slot connections, we derive that \(\Delta(G^{\prime}_{F})\leq sq\), and thus \(G^{\prime}\)_F is \(sq\)_-edge-colorable [17]. Let colors 1, 2, \(\ldots,sq\) be used to edge-color \(G^{\prime}_{F}\). We adopt Routing Algorithm B, shown below, to route each (\(u\)-\(i\), \(v\)-\(j\), \(m\)) in association with the edge-coloring of \(G^{\prime}_{F}\) for the RNB condition. **Routing Algorithm B:**  
Connection (\(u\)-\(i\), \(v\)-\(j\), \(m\)) is routed in windows I\({}_{u\)-\(i\), \(c\), \(I_{u,c}\), \(O_{v,c}\) and \(O_{v\)-\(j\), \(c\) if color \(c\) is assigned to the corresponding edge of (\(u\)-\(i\), \(v\)-\(j\), \(m\)) in \(G^{\prime}_{F}\) (see Figure 5b). Similar to Properties 2-4, we have Properties 5-7, as follows. **Property 5. ** A DCN2(\(s\), \(r\), \(q\), \(k\)) network for \(m\)-slot connections with \(1\leq m\leq m_{\max}\) is RNB if  
\[k\geq k^{\prime}_{\text{RNB}}=sq\cdot m_{\max} \tag{4}\]  
**Proof. ** The proof is similar to that of Property 2. **Property 6. ** Suppose only one connection rate, \(m_{\max}\), is considered. Then a DCN2(\(s\), \(r\), \(q\), \(k\)) network is RNB if and only if \(k\geq k^{\prime}_{\text{RNB}}=sq\cdot m_{\max}\). **Proof. ** The proof is similar to that of Property 3. **Property 7. ** A DCN4(\(s\), \(r\), \(q\), \(k\), \(p\)) network for \(m\)-slot connections with \(1\leq m\leq m_{\max}\) and \(k\geq sq\cdot m_{\max}\) is RNB if \(p\geq 1\). **Proof. ** From the topology of the DCN4 architecture (see Figure 3b), we can see that a DCN4(\(s\), \(r\), \(q\), \(k\), \(p\)) network with \(p=1\) and \(k\geq sq\cdot m_{\max}\) functions as well as a DCN2(\(s\), \(r\), \(q\), \(k\)) network. According to Property 5, the property holds immediately. Comparing Equation (2) with Equation (4), we have \(k^{\prime}_{\text{RNB}}/k^{\prime}_{\text{SNB}}\leq 1/2\) for \(m_{\max}\geq 2\) and \(sq\geq 3\). Property 5 implies that \(k^{\prime}_{\text{RNB}}\) reduces the SNB DCN2 result given in [13], namely, \(k^{\prime}_{\text{SNB}}\), down to at least half for most cases, and even down to one third.