## 4 The Dynamic Form of the Problem
### Performance with Poisson Arrivals  
The effectiveness of our heuristic scheduling rules is examined next. In this subsection, we test our scheduling scheme with Poisson packet arrivals. MASON (A multi-agent simulation environment) [21] is chosen to be the simulator used, because it is a fast discrete-time Java-based simulator. In this simulation, we simply model the behavior of a queuing system. We are interested to see whether, in an isolated environment, our scheduling scheme can perform better than other existing scheduling schemes. A more extensive and more realistic simulation is done in Section 5, so as to evaluate the overall performance of our scheduling scheme with all network factors considered. Two frequently used scheduling schemes are taken as the comparison group. One is FIFO-based, and the other is round-robin-based. Basically these two-packet scheduling schemes cover all existing literature on network coding protocols. In the FIFO-based scheduling scheme, all packets arrive at a single queue, each with a tag denoting which flow it is coming from. When the node obtains the right to transmit, the first packet in the queue is dequeued first, and it checks sequentially in the queue for coding-possible packets. On the other hand, the round-robin-based scheduling scheme maintains multiple queues, each for a flow. The scheduler then polls these queues in a round-robin fashion. This scheme overcomes the problem in the FIFO-based method that a busy flow can crowd out all other flows. Among all generated coding graphs using the baseline parameters (_cf._ Table 1), the one that corresponds to the median processing time is used in this experiment. This choice guarantees that the generated coding graph is neither too plain, nor too complex. In the baseline test bench, a total of 20 flows are present. The total offered load is 1868 packets per second (pps), with the minimum flow being 48 pps and the maximum being 282 pps. Each simulation is run for 60 s (time in simulation). The average throughput and minimum throughput among all flows are sampled from the end of the 10 th second until the end of the simulation. After 10 s, the system has already stabilized, so we choose to measure the throughputs from 10 s onward to the end of the simulation. All experiments are done with 10 different random seeds, and the average is plotted in Figures 7 and 8. In the static version of this scheme, a round-robin-based scheduling scheme requires 1198 transmissions to clear the queued packets. However, our static solution requires only 1010 transmissions. This is almost a 20% improvement. Figure 7: Average throughput performance with Poisson arrivals. In the dynamic case, the average throughput improvement is not as significant. We scale the offered packets with a multiplier and generate different offered loads. The distribution of service rates follows a Poisson distribution with mean service time as 100 packets per second. It is observed that our heuristic scheduling scheme (HEU) can outperform round-robin (RR) when the offered load is below 400. This is four-times the transmission capacity. The maximum improvement can reach 13%. This amount is smaller than the 20% promised in the static form. This is generally because our heuristic scheduling method balances between better performance and higher anomaly tolerance. Only if we can always stick to the optimal scheduling scheme can we achieve the highest performance improvement. However, a fixed scheme cannot adapt to the dynamic network conditions. With the introduction of probabilistic scheduling and the allowance mechanism, we achieve adaptability to network contingencies at a small cost of potential performance gain. When the offered load continues to rise above 400, RR provides higher average throughput as compared to HEU. At the same time, we turn to Figure 8 for more insight about this underperformance. One can soon discover that the minimum throughput of HEU is slightly below 10 pps, while the average throughput is slightly above 10 pps.