## 3 Analysis of Queue Length Policy at a Coding Node
### Computation of Threshold Policy  
Assume in the queue-length based threshold policy, the thresholds for the both flows are \(L_{1}=L_{2}=L\). To prevent packet loss due to the queue overflow, the value of \(L\) is no more than the length of the coding queue, which can hold at most \(K\) packets. The regular ONC policy as used in existing coding-aware routing algorithms is a specific threshold policy. In ONC policy, we have \(L_{1}=L_{2}=0\). In the following, we shall first discuss the existence of the optimal threshold at the coding node by the analytical formula and the simulation result. According to (13), we obtain that the probability of coding opportunity (\(P_{r}(N,L)\)) increases with the threshold (\(L\) ) increasing. As \(L\) increases, forcing packets to be coded in coding nodes may induce large delay. This may in turn degrade the jitter benefits. We consider two extreme cases:  
Case (1) \(q=1\). The probability of coding opportunity is 0. There is no coding opportunity. The packet delay for waiting a future coding opportunity is 0. In this case, there are no jitter benefits, which means there is no network coding gain. Case (2) \(q=\infty\). The probability of coding opportunity is 1.Coding opportunities are always available, and waiting for such opportunities can cause substantial delay and jitter in transmission. The increased jitter benefits achieved through network coding may be offset by jitter incurred by waiting for these coding opportunities. In the extreme, network coding may in fact hurt the packet jitter performance. Given the above discussion, to improve long-term packet jitter, there is a trade-off between network coding and packet waiting delay. The optimal threshold exists. In the following, we use the simple scenario in Figure 2 and evaluate the jitter performance of the queue-length policy embedded in coding-aware routing with various thresholds via ns2 simulation. The routing metric design includes the coding opportunity related to local topology and the path length. In the experiment, we use 802.11 at the Mac layer with Two Ray Ground propagation model, and both data flows are generated by UDP traffic source with CBR model. The coding queue size is set to 50. There are two flows in this topology. For flow 1, the source node is node 1 and the destination node is node 4. For flow 2, the source node is node 4 and the destination node is node 3. Both flows have the same transmission rate. The rates of both flows equal 300 kbps. Figure 5 shows the average packet jitter of flow 1 in the queue-length based threshold policy by different thresholds. The figure shows that in the queue-length based threshold policy, when the threshold is different, the value of the average packet jitter is different as well. This is because there is a different trade-off between the positive influence of network coding on packet jitter and the negative influence of packet delay due to waiting for future coding opportunities. From Figure 5, we can also notice that the threshold selection is very important. If the threshold is not properly selected, the packet jitter performance can be largely influenced. The influence of the queue state on the network performance is serious. From the simulation result, we notice that the optimal threshold exists. We can use a Markov process to model the queue state of the coding node. Due to the steady-state property of Markov chain, the average packet jitter per observation window can characterize the long-run average packet jitter. We can introduce a training phase before the data transmission phase to search the optimal threshold for a coding node by recording the value of average packet jitter of the specific real-time flow corresponding to each threshold ranging from 1 to the maximum size of the queue minus 1. For each threshold, to characterize the long-run average packet jitter of specific real-time flow, we can measure the average variation in packet waiting delay to transmit successfully in a fixed sample interval (such as 0.2 s) when data transmission is stable.