# Link Load Correlation-Based Blocking Performance Analysis for Tree-Type Data Center Networks
## 3 Blocking Performance Analysis for Tree-Type Data Center Networks
### Link Load Correlation-Based Blocking Probability Performance Analysis
#### 3.3.2 Blocking Probabilities for Core Class Connections  
Each CC connection includes two \(L_{0}\) layer links and two \(L_{1}\) layer links. Taking the \(C_{4}\) connection in Figure 1 as an example, its path includes links \(l_{0,1}\), \(l_{0,5}\), \(l_{1,1}\), and \(l_{1,2}\). We divide the path of \(C_{4}\) into two symmetric segments, one including \(l_{0,1}\) and \(l_{1,1}\), and the other including \(l_{0,5}\) and \(l_{1,2}\). Similarly, all \(L_{1}\) layer links and the core switch form a star network, and the blocking rates of the two segments can be seen to be independent. When calculating the blocking segment of segment \(l_{0,1}-l_{1,1}\), which is denoted by \(P_{l_{0,1}-1,1}\), we consider the load correlation between link \(l_{0,1}\) and \(l_{1,1}\). Define \(P_{l_{0,1}-1,1}\) as the probability that \(l_{0,1}\) and \(l_{1,1}\) are simultaneously fully occupied, which can be expressed by  
\[P_{l_{0,1}-1,1}=P_{l_{0,1}}+P_{l_{1,1},0,1}, \tag{7}\]  
where \(P_{l_{0,1}}=EB\big{(}\rho_{l_{0,1}},M_{0},M_{0}\big{)}\) is the blocking probability of \(l_{0,1}\), and \(P_{l_{1,1},0,1}\) is the probability that \(l_{0,1}\) is not congested but \(l_{1,1}\) is congested. Considering different possible connection numbers in \(l_{0,1}\), as well as the corresponding conditional blocking probabilities of \(l_{1,1}\), \(P_{l_{1,1}\setminus 0,1}\) in the above equation can be rewritten as (8). \[P_{l_{1,1}\setminus 0,1}=\sum\limits_{i=0}^{M_{0}-1}P(l_{1,1}\text{ congested}|\text{ $i$ connections in $l_{0,1}$})P(i\text{ connections in $l_{0,1}$}) \tag{8}\] \[=\sum\limits_{i=0}^{M_{0}-1}P_{B}(i)P_{A}(i)\]  
The probability that \(l_{0,1}\) is accommodating \(i\) connections can be represented by  
\[P_{A}(i)=EB\Big{(}\rho_{l_{0,1}},M_{0},i\Big{)}, \tag{9}\]  
and the conditional probability that \(l_{1,1}\) is blocked when \(l_{0,1}\) is carrying \(i\) connections is denoted by \(P_{B}(i)\). In the two-layer tree DCN with tree factor \(K,l_{0,1}\), hosts \(K-1\) types of EC connections and \(N-K\) types of CC connections. Therefore, if \(l_{0,1}\) is carrying \(i\) connections, the average number of CC connections among them is \(\frac{(N-K)(1-P_{cc})i}{(K-1)(1-P_{cc})+(N-K)(1-P_{cc})}\). Those CC connections from \(l_{0,1}\) will continue to occupy sub-channels at \(l_{1,1}\), and, thus, the average number of sub-channels available at \(l_{1,1}\) is  
\[N_{l_{1,1}\setminus 0,1}(i)=M_{1}-\Big{[}\frac{(N-K)(1-P_{cc})i}{(K-1)(1-P_{ cc})+(N-K)(1-P_{cc})}\Big{]}. \tag{10}\]When \(l_{1,1}\) is blocked, those \(N_{l_{1,1\backslash 0,1}}(i)\) sub-channels will be fully occupied by the CC connections from \(L_{0}\) layer links, except for \(l_{0,1}\), and their effective loads can be approximated by  
\[\rho_{l_{1,1\backslash 0,1}}=\frac{K(K-1)^{2}\rho_{0}(1-P_{cc})}{1-P_{L_{1}}}. \tag{11}\]  
Thus, we have  
\[P_{B}(i)=EB\Big{(}\rho_{l_{1,1\backslash 0,1}},N_{l_{1,1\backslash 0,1}}(i),N_{l _{1,1\backslash 0,1}}(i)\Big{)}, \tag{12}\]  
and thus the blocking probability of CC connections is  
\[ \begin{split}& P_{cc}=1-(1-P_{l_{0,1\backslash 1,1}})^{2}\\ &=1-\left(1-EB(\rho_{l_{0}},M_{0},M_{0})-\sum\limits_{i=0}^{M_{0}- 1}P_{B}(i)P_{A}(i)\right)^{2}.\end{split}  \tag{13}\]  
Based on the relationships among \(P_{cc}\), \(P_{cc}\), \(\rho_{l_{i,i}}\), and \(P_{l_{i,i}}\), the network blocking probability \(P_{nt}\) can be determined iteratively. The detailed link load correlation (LLC)-based blocking performance analysis procedures for the two-layer tree-type DCN are shown in Algorithm 1. When a DCN topology and the load \(\rho_{0}\) for each connection type is given, the effective loads and probabilities of \(L_{0}\) and \(L_{1}\) layer links are initialized and then updated during each iteration. ```
1:Initialization:
2:Set \(n=0\) and initialize \(P_{net}(0)=P_{cc}(0)=P_{cc}(0)=0\), \(\rho_{L_{0}}(0)=(N-1)\rho_{0}\), \(\rho_{L_{1}}(0)=(N-K)\rho_{0}\), \(P_{L_{0}}(0)=EB\big{(}\rho_{L_{0}}(0),M_{0},M_{0}\big{)}\), \(P_{L_{1}}(0)=EB\big{(}\rho_{L_{1}}(0),M_{1},M_{1}\big{)}\).