## 4 The Dynamic Form of the Problem
### Heuristic Scheduling  
The objective of dynamic scheduling is to get higher throughput given the capacity of the network and to maintain a relative fairness among all flows when the network is saturated. The starting point of this scheduling method is the naive solution that we mention above. First, we translate the offered loads of flows into the expected number of packets that would arrive in one second. These figures are used as the weight in WCCP, and from here, a static solution is obtained in the form of a set of weighted cliques. We will refer to this solution as the initial plan. The first heuristic rule is to overcome the restriction of transmission capacity. The capacity of a node can be estimated by monitoring the transmission history. When the capacity is smaller than the arrival rate, flows with heavy traffic should be cut off, while flows with less traffic remain intact. Basically, we use the generate-quota algorithm shown in Algorithm 1 to allocate the limited transmission capacity. The final set of weights for all cliques obtained in this step is called a quota, and it is the starting point for further steps. The idea is to maximize the minimum share of quota, while utilizing the coding benefits. If the flow with the smallest offered load can be fully processed, we first allocate the quota accordingly to cover this smallest offered load for all flows, effectively removing this flow from our computation. This allocation is recursively executed until the transmission capacity is not enough to fully process the flow with the smallest offered load. Then, we use a trial-and-error method to allocate same amount of weight to all flows. In this way, we can achieve higher throughput, whereby fairness is achieved. The core of this algorithm is the WCCP problem. In the worst case, the WCCP problem is solved \(2|V|\) times, where \(|V|\) is the number of vertices in the graph. Therefore, the worst case time complexity of the generate-quota algorithm is \(O(\binom{Q+D-1}{D-1}*|V|)\). The second heuristic rule is to exploit the order of packet arrival. In order to enforce a quota plan with out-of-order packet arrivals, we employ a probabilistic scheduling method. If multiple cliques are ready to transmit (_i.e._, their corresponding flows have packets in the queue), each of them is given a probability to transmit in this round. The probability for one clique is its quota minus the amount that has been transmitted in this instance, and then, this count is normalized by the sum across all cliques. The randomness achieved by this probabilistic scheduling method avoids many problems faced by a fixed scheduling method. There would be no bias towards any flow due to the absence of a sequential decision model. Cliques with a higher quota are given higher probabilities in the beginning. With more packets sent for this clique, its probability would decrease and other cliques will have higher probabilities. In the equilibrium state, the number of packets sent for each clique would be generally proportional to its quota. In cases when no clique has positive probability, the first packet in the queue is sent regardless of whether other packets in its clique are ready. The third heuristic rule is to exploit the opportunity to code more \"leftover\" packets. In our scheduling scheme, packets are checked for on-the-spot coding opportunities before sending out. For example, there may be a single-vertex clique representing one flow in the initial plan and quota plan. When this clique gains the right to transmit as a result of the probabilistic scheduling, we check for hidden coding opportunities right before sending out packets from this flow, _i.e._, if this packet can be coded with another packet in the same queue, they are coded together and sent with the other flow marked with one packet reserve. In future schedules, flows with a reserve are eligible for probabilistic scheduling even if they do not have packets in their queue. The reserve works as if the packets are not sent until the reserve is used.