## 5 Fine-Grained Network Congestion Detection Algorithm Based on Flow Watermarking
### Fine-Grained Network Congestion Detection Algorithm  
The fine-grained network congestion detection algorithm is based on the flow watermarking, and it judges the changes in network status according to the difference between the proportion of the number of packets in a certain interval and the ideal proportion of the number of packets in the interval, that is, the Crps (Change ratio of sparsity of packet). Since the delay operations are different for different codes in different intervals, the Crps of four codes need to be analyzed in detail. After a small packet delay or packet loss occurs, \(X^{f}_{i,k}\) (\(i\) = 1, 2, 3, 4), \(\overline{Y^{f}_{r2}}\) and \(\overline{Y^{f}_{r3}}\) are defined as \(X^{N}_{i,k}\) (\(i\) = 1, 2, 3, 4), \(\overline{Y^{N}_{r2}}\) and \(\overline{Y^{N}_{r3}}\). Let \(N_{j}\) (\(j\) = 0, 1, 2, 3) be the number that \(X^{f}_{i,k}\) increase or decrease when encoding '\(j\)', and \(n_{j}\) (\(j\) = 0, 1, 2, 3) be the proportion of the number that \(X^{f}_{i,k}\) change. For different codes, \(N_{j}\) and \(n_{j}\) are analyzed in different intervals. For the code '00', without external interference, \(X^{f}_{2,k}=0\), \(X^{f}_{3,k}=2u_{x}\). In realistic scenes, if some packets in the third interval are congested until the fourth interval or some packets in the third interval are lost, it can be inferred that when \(N_{0}\) is less than \(u_{x}\), network congestion has occurred, but the correct result can still be obtained. We have  
\[X^{N}_{3,k}-u_{x}=n_{0}*u_{x}\;(0<n_{0}<100\%), \tag{39}\]  
\[n_{0}=(X^{N}_{3,k}-u_{x})/u_{x}\;(0<n_{0}<100\%). \tag{40}\]  
At this time \(\overline{Y^{N}_{r3}}\geq 0\). The smaller the \(n_{0}\), the greater the change of sparsity of packet. At this time, the greater the changes in network status, correspondingly. Therefore, when the decoding result is '00', \(n_{0}\) can reflect the small packet delay and packet loss, which is more helpful for the analysis of the change in network status. The analysis of the code '00' is analogized to other codes. For code '01', ideally, \(X^{f}_{2,k}=2u_{x}\), \(X^{f}_{3,k}=0\). In realistic scenes, some packets in the second interval are congested until the third interval, or some packets in the second interval are lost; it can be inferred that when \(N_{1}\) is less than \(u_{x}\), network congestion has occurred, but the correct result can still be obtained. We have  
\[X^{N}_{2,k}-u_{x}=n_{1}*u_{x}\;0<n_{1}<100\%, \tag{41}\]  
\[n_{1}=(X^{N}_{2,k}-u_{x})/u_{x}\;0<n_{1}<100\% \tag{42}\]  
The smaller \(n_{1}\), the greater the change of sparsity of packet. For code '10', ideally, \(X^{f}_{2,k}=0\), \(X^{f}_{3,k}=0\), \(X^{f}_{4,k}=3u_{x}\). In realistic scenes, some packets in the fourth interval are congested until the next interval, or some packets in the fourth interval are lost; it can be inferred that when \(N_{2}\) is less than \(2u_{x}\), network congestion has occurred, but the correct result can still be obtained. We have  
\[3u_{x}-X^{N}_{4,k}=n_{2}*u_{x}\;(0<n_{2}<200\%), \tag{43}\]  
\[n_{2}=(3u_{x}-X^{N}_{4,k})/u_{x}\;(0<n<200\%). \tag{44}\]  
Figure 6: An example of the decoding result of watermark ‘00’ when micro-packet delay and micro-packet loss occur. The larger \(n_{2}\), the greater the change in sparsity of packet. For code '11', ideally, \(X_{2,k}^{f}=1.5u_{x},\ X_{3,k}^{f}=1.5u_{x}\). In realistic scenes, some packets in the third interval are congested until the fourth interval, or some packets in the third interval are lost; it can be inferred that when \(N_{3}\) is less than \(0.5u_{x}\), network congestion has occurred, but the correct result can still be obtained. We have  
\[X_{3,k}^{N}-u_{x}=n_{3}*u_{x}\ (0<n_{3}<50\%), \tag{45}\]  
\[n_{3}=(X_{3,k}^{N}-u_{x})/u_{x}\ (0<n_{3}<50\%). \tag{46}\]  
The smaller the \(n_{3}\), the greater the change of sparsity of packet. We define the DRW(detection rate of the watermark) as the percentage of the number of correctly identified bits of the watermark in the total number of encoded bits of the watermark.