## 4 System Design and Analysis
### Optimal Network Utilization Mechanism
#### 4.2.2 Optimal Network Utilization Model  
As mentioned above, there are three objects involved when performing long flow scheduling in a data center. They are long flows, switches and links. Long flows are flows whose packet number is greater than threshold. Switches is the set of entire network switches, including core switches, aggregation switches and edge switches. Links is the set of all links that connect switch to server and connect switch to switch. Some denotations and symbols used in optimal network utilization model and algorithm are described in Table 2.  
Then we can define the Link Resource Utilization (LRU) of \(j\)th section in path \(p(s,d)_{i}\):  
\[LRU_{p(s,d)_{i}}=\frac{ll(s,d)_{ij}}{lc(s,d)_{ij}},j=1,...,2^{l-1} \tag{8}\]  
the Switch Resource Utilization (SRU) of the \(k\)th switch in path \(p(s,d)_{i}\):  
\[SRU_{p(s,d)_{i}}=\frac{mf(s,d)_{ik}}{mf(s,d)_{ik}},k=1,...,2^{l-1}-1 \tag{9}\]  
So, the Network Resource Utilization(NRU) of path \(p(s,d)_{i}\):  
\[NRU_{p(s,d)_{i}}=\max\{LRU_{p(s,d)_{i}},SRU_{p(s,d)_{i}}\} \tag{10}\]  
\(NRU_{p(s,d)_{i}}\) contains \(j+k\) parts: \(j\) LRUs and \(k\) SRUs.  
Therefore, the long flow scheduling problem of the data center network can be described as:  
Given the network paths set of \(P=\{P_{s_{1},d_{1}},...,P_{s_{m},d_{n-1}}\}\) and long flow set \(F=\{f(s,d)_{1},f(s,d)_{2},...\}\), to find a matching \(M_{F,P}=\{f(s,d)_{m},p(s,d)_{i}|f(s,d)_{m}\in F,p(s,d)_{i}\in P(s,d)\}\) with minimum entire NRU.  
Obviously, NRU can also be expressed as  
\[NRU\Longleftrightarrow\sum_{s}\sum_{d}\sum_{i}NRU_{p(s,d)_{i}} \tag{11}\]  
In summary, long flow scheduling can be described as:  
\begin{table}
\begin{tabular}{c c} \hline
**Denotations** & **Description** \\ \hline \(F\) & The set of all long flows \\ \(P\) & The set of all paths in entire network \\ \(S\) & The set of all switches \\ \(L\) & The set of all links \\ \(l\) & The number of network layers \\ \(n\) & The number of all servers \\ \(P(s,d)\) & The set of all paths from server \(s\) to server \(d\) \\ \(p(s,d)_{i}\) & The \(i\)th path in \(P_{(s,d)_{i}}=1,2,\ldots,|P|\) \\ \(l(s,d)_{ij}\) & The \(j\)th section of \(i\)th path in \(P_{(s,d)_{i}}=1,2,\ldots,|P|\), and \(j=1,2,3,4\) if \(l=3\) \\ \(s(s,d)_{ik}\) & The \(k\)th switch of \(i\)th path in \(P_{(s,d)},i=1,2,\ldots,|P|\), and \(k=1,2,3,4,5\) if \(l=3\) \\ \(lc(s,d)_{ij}\) & The link capacity of \(j\)th section of \(i\)th path in \(P_{(s,d)_{i}}\) \\ \(ll(s,d)_{ij}\) & The link load of \(i\)th section of \(i\)th path in \(P_{(s,d)_{i}}\) \\ \(mc(s,d)_{ik}\) & The memory capacity of \(k\)th switch of \(i\)\[min \sum_{s}\sum_{d}\sum_{i}NRU_{p(s,d)_{i}} \tag{12}\] \[s.t. \left(lc(s,d)_{ij}-ll(s,d)_{ij}\right)\geq\sum_{f_{m}\in M(p(s,d)_{ i})}r_{m}\] (13) \[\left(mc(s,d)_{ik}-mf(s,d)_{ik}\right)\geq\sum_{f_{m}\in M(p(s,d)_ {i})}r_{m}\] (14) \[E(f_{m},M(f_{m}))=0\] (15) \[|M(f_{m})|\geq 1\] (16) \[1\leq j\leq 2^{l-1},j\in Z\] (17) \[1\leq k\leq 2^{l-1}-1,k\in Z\] (18) \[1\leq s,d\leq 2^{n},s,d\in Z \tag{19}\]  
The goal of long flow scheduling is to minimize the overall network resource utilization, including switch resource and link resource. The constraint (13) is to ensure that all links do not saturate. The constraint (14) is to ensure that all switches do not experience memory overflow. The constraints (15)-(16) are to ensure that each long flow should be mapped to at least one path. This mapping problem has been proven to be an NP-Hard problem.