## 3 Network Congestion Detection Model Based on Flow Watermarking
### Watermark Mechanism Based on Sparsity of Packet  
The flow watermarking based on sparsity of packet uses four consecutive intervals to encode two bits of watermark data, which modifies the number of packets in the middle two intervals and compares it with the average number of packets in the four intervals, that is, the sparsity of packet.  
We divide flow \(F\) (with a series of packets) into intervals \(Ii\) (\(i<0\), slot index) of length \(T\) (\(>\)0) starting at random time offset \(o\) (\(>\)0) and choose four consecutive intervals. The first to fourth intervals are denoted as \(I_{1,k}\), \(I_{2,k}\), \(I_{3,k}\), and \(I_{4,k}\) (\(k=1,2,\ldots,r\)), where the number of packets contained is expressed as \(X_{1,k}\), \(X_{2,k}\), \(X_{3,k}\) and \(X_{4,k}\) (\(k=1,2,\ldots,r\)). For flows that are sufficiently long duration and contain many intervals, \(X_{j,k}\) (\(j=1,2,3,4\); \(k=1,2,\ldots,r\)) satisfy random sample drawn from a sufficiently large general distribution. Therefore, \(X_{j,k}\) satisfy the \(iid\) (independent and identical distribution). Assume  
\[E\left(X_{j,k}\right)=\mu_{x},V\left(X_{j,k}\right)=\sigma_{x}^{2}. \tag{5}\]Given four continuous intervals, the difference between the number of packets in the second interval and the mean number of packets is defined as:  
\[Y_{k2}=X_{2,k}-\overline{X_{k}}, \tag{6}\]  
where  
\[\overline{X_{k}}=\frac{1}{4}(X_{1,k}+X_{2,k}+X_{3,k}+X_{4,k}). \tag{7}\]  
Therefore  
\[E\big{(}\overline{X_{k}}\big{)}=\mu_{x},V\big{(}\overline{X_{k}}\big{)}= \sigma_{x}^{2}/4, \tag{8}\]  
\[E(Y_{k2})=0,V(Y_{k2})\leq 5\sigma_{x}^{2}/4. \tag{9}\]  
Similarly  
\[Y_{k3}=X_{3,k}-\overline{X_{k}},E(Y_{k3})=0,V(Y_{k3})\leq 5\sigma_{x}^{2}/4. \tag{10}\]  
Because \(X_{2,k}\) satisfy the \(iid\), so do \(Y_{k2}\) and \(Y_{k3}\).  
To improve the accuracy of watermark codec and avoid the influence of accidental factors, redundant coding \(r\) (\(>\)0) is introduced, that is, \(r\) shares of four consecutive intervals are used to embed two bits of watermark. Thus, the mean of sampling \(Y_{k}\) is defined as  
\[\overline{Y_{r}}=\frac{1}{r}\sum_{k=1}^{r}Y_{k}. \tag{11}\]  
Since \(Y_{k}\) (\(k=1;2;\,\ldots\,;r\)) satisfy the \(iid\), then  
\[E\big{(}\overline{Y}_{r}\big{)}=0,\ V\big{(}\overline{Y_{r}}\big{)}\leq\frac{ 5\sigma_{x}^{2}}{4r}. \tag{12}\]  
\(Y_{k}\) is symmetric about mean 0, so is \(\overline{Y_{r}}\).  
According to the watermark data, the watermark coding module directly forwards or delays packets in the specific interval to embed information. Figure 3 shows the schematic diagram of the watermark encoding. When redundant coding is not used (i.e., \(r=1\)), four consecutive intervals are used to encode the two bits of watermark. By delaying the forwarding time of packets, the \(Y_{k2}\) and \(Y_{k3}\) are increased or decreased to be larger or smaller than the average number of packets in four intervals to encode four watermarks.  
When the watermark '00' is encoded, the packets in the second interval are delayed to the third interval. At the third interval, the delayed packets are sent first. Then the packets arriving this interval are sent. The operation lets \(Y_{k2}\) decrease by \(\mu_{x}\), and \(Y_{k3}\) increase by \(\mu_{x}\). At this time, \(Y_{k2}\) is less than the average number of packets in four intervals, and \(Y_{k3}\) is greater than the average value. The encoding operations of other three watermarks are similar.  
Figure 3: The schematic diagram of the watermark encoding.