## 5 Evaluation  
In this section, we evaluate our work in a sophisticated network environment, specifically, an environment with upstream/downstream nodes, contentions and interferences. We first tune our heuristic scheduling scheme to counter the adverse effects that we may encounter in real networks. Then, the tuned  
Figure 8: Minimum throughput performance with Poisson arrivals.  
scheduling scheme is tested in Qualnet simulations, where a set of network topologies with multiple nodes are constructed. The evaluation results would reveal that with some tailored packet scheduling algorithms, we can, for example, improve the fairness among flows without severely impacting overall throughput. If fairness is of less importance in some scenarios, one can modify the ideas underlying our algorithm to improve throughput. One simple idea is to shift some quota from flows with less coding degree to flows with higher coding degree, as in the generate-quota algorithm.  
There are mainly three assumptions in the evaluation of our heuristic scheduling scheme, as described in the last section. However, they are not immediately valid in real network settings.  
1. The offered load of each flow is known and fixed.
2. The transmission capacity of each node is known and fixed.
3. The arrival of packets follows the Poisson process.  
Therefore, we have to make adjustments to fit the scheduling scheme in a real protocol. Hence, we designed DPSA (dynamic packet scheduling algorithm), on top of the routing protocol proposed in [22]--SCAR. SCAR is a routing protocol based on DSR (The dynamic source routing protocol for multi-hop wireless ad hoc networks) [23]. Routes are selected in an on-demand fashion, and source routing is used to navigate packets through the network. SCAR is able to discover coding opportunities and compare potential throughput gain among multiple paths.  
The first adjustment is the design of a cross-layer channel. Using this channel, the application layer can give hints to the offered load to lower layers. Consider a flow with three nodes, \(S\), \(I\) and \(D\). The offered load information is directly available through the cross-layer channel in Node \(S\). However, the offered load in Node \(I\) is usually smaller, because Node \(S\) may not have processed all packets from the flow. At the same time, some packets may be dropped due to queue overflow.  
Therefore, the second adjustment is the delivery of offered load information from the upstream nodes to the downstream nodes. An upstream node calculates the offered load for a downstream node by subtracting the amount of packets dropped from its own offered load, periodically. This delivery of information is encoded in the source routing header.  
The third adjustment is the introduction of changing transmission capacity. This is a critical value used in the heuristic scheduling scheme. Overstating this value will generally lead to unfair scheduling, and understating this will lead to lower throughput gain. In our protocol, this value is measured as the number of packets processed per second, averaged over a window of 5 s. Therefore, it can reflect changes in the network condition, but filter out unnecessary noises.  
In the following text, we test our scheduling method in two types of topologies. The first one is specially designed to contain plentiful coding opportunities. The second one is a randomly generated mesh network, which resembles real-world _ad hoc_ networks. In this topology, the amount of coding opportunity is intermediate. In topologies where coding opportunities are rarely seen, our scheduling method is retrograded to a round-robin scheme and, thus, is omitted in this analysis.