# Rearrangeable Nonblocking Conditions for Four Elastic Optical Data Center Networks
## 3 RNB DCN1 and DCN3 Networks
### Multigraph Approach and Routing Algorithm  
Given a DCN1(\(r\), \(q\), \(k\)) network and a frame \(F\) of connections, we propose Multigraph Approach A, given below, to convert the DCN1(\(r\), \(q\), \(k\)) network for frame \(F\) into a multigraph \(G_{F}\).  
**Multigraph Approach A:**  
Let each left vertex \(u\) (or right vertex \(v\)) in multigraph \(G_{F}\) be ToR-T \(u\) (or ToR-R \(v\)) of the DCN1(\(r\), \(q\), \(k\)) network. In multigraph \(G_{F}\), there is an edge connecting vertexes \(u\) and \(v\) if there is an \(m\)-slot connection from a BVT-T in ToR-T \(u\) and it is destined to a BVT-R in ToR-R \(v\), i.e., \((u,v,m)\) (see Figure 4a). Note that we call \(G_{F}\) a multigraph [17] because multiple connections between ToR-T \(u\) and ToR-R \(v\) are allowed, and thus there could be more than one edge connecting vertexes \(u\) and \(v\) in \(G_{F}\).  
In Property 1, we show that \(G_{F}\) is \(q\)-edge-colorable.  
**Property 1.** Given a DCN1(\(r\), \(q\), \(k\)) network and a frame \(F\) of connections, let \(G_{F}\) be the corresponding multigraph constructed by Multigraph Approach A. Multigraph \(G_{F}\) is \(q\)-edge-colorable.  
Proof.: Let \(\Delta(G_{F})\) be the maximum degree of \(G_{F}\). Since each ToR switch consists of \(q\) BVT-Ts and \(q\) BVT-Rs, at most \(q\)\(m\)-slot connections can be generated from a ToR-T (or destined to a ToR-R). Thus, we have \(\Delta(G_{F})\leq q\). From the construction of \(G_{F}\), we can see that \(G_{F}\) is a bipartite multigraph. In addition, \(G_{F}\) is \(q\)-edge-colorable according to graph theory [17] if \(G_{F}\) is a bipartite multigraph with \(\Delta(G_{F})\leq q\).  
In a DCN1(\(r\), \(q\), \(k\)) network, we use \(\mathrm{I}_{u}\) (or O\({}_{v}\)) to denote the fiber connecting ToR-T \(u\) (or ToR-R \(v\)) and the BV-SS, where \(k\geq qm_{\rm{max}}\) and \(1\leq u\), \(v\leq r\). In addition, we partition each fiber with \(k\) FSUs into \(q\) parts, each of which consists of \(m_{\rm{max}}\) consecutive FSUs. Each part is called a window, and these \(q\) windows, denoted by \(W_{l}\) for \(1\leq l\leq q\), are numbered from \(1\) from left to right. We use \(|W_{l}|\) to represent the size of window \(W_{l}\), and also use \(\mathrm{I}_{u,l}\) (or O\({}_{v,l}\)) to represent the \(l\)th window in fiber \(\mathrm{I}_{u}\) (or O\({}_{v}\)) for \(1\leq u\), \(v\leq r\) and \(1\leq l\leq q\).  
Figure 4: Given a DCN1(\(4\), \(3\), \(9\)) network and a frame \(F\) of connections (\(1\), \(1\), \(3\)), (\(1\), \(2\), \(3\)), (\(1\), \(3\), \(2\)), (\(2\), \(2\)), (\(2\), \(4\), \(3\)), (\(3\), \(1\), \(1\)), (\(4\), \(3\), \(2\)) and (\(4\), \(4\), \(2\)): (**a**) The corresponding multigraph \(G_{F}\) constructed by Multigraph Approach A. Note that \(G_{F}\) is edge-colored by colors \(1\), \(2\), and \(3\) (marked in red), and left and right vertices are marked in blue and black, respectively. (**b**) A routing of connections in frame \(F\) according to Routing Algorithm A in association with the edge-coloring of \(G_{F}\).  
Recall that \(G_{F}\) is \(q\)-edge-colorable (Property 1). Let colors 1, 2,..., \(q\) be adopted to edge color \(G_{F}\). We route each (\(u\), \(v\), \(m\)) for the RNB condition [14] using Routing Algorithm A given below.  
**Routing Algorithm A:**  
Connection (\(u\), \(v\), \(m\)) is routed in windows \(\mathrm{I}_{u,c}\) and \(\mathrm{O}_{v,c}\) if color \(c\) is assigned to the corresponding edge of (\(u\), \(v\), \(m\)) in \(G_{F}\) (see Figure 4b).