OPTIMAL FLOW-CONTROL ALLOCATION POLICIES IN COMMUNICATION-NETWORKS WITH MULTIPLE MESSAGE CLASSES

We consider M (greater-than-or-equal-to 2) transmitting stations sendi ng packets to a single receiver over a slotted time-multiplexed link. For each phase consisting of T consecutive slots, the receiver dynamic ally allocates these slots among the M transmitters. The cost per slot for holding a packet may vary among the transmitters, and may be inte rpreted in terms of multiple classes of messages. Our objective is to characterize policies that minimize the discounted and long-term avera ge costs due to holding packets at the M stations, based on delayed in formation on the numbers of packets being held at the respective trans mitters. We derive properties of optimal (discounted) policies that re duce the computational complexity of the optimal How control algorithm . For M = 2, we show that the minimal total cost is convex and submodu lar in the state, and we prove the following properties of optimal pol icies: 1) when the state at transmitter i increases by unity while the state at the other transmitter j is fixed, the optimal allocation is either unchanged, or increases by one at transmitter i and decreases h y one at transmitter j; and 2) the optimal policy is of the threshold type. We use these properties to show that the optimization reduces to the calculation of optimal allocations for a finite number of states. In addition, for each such state (excluding the origin), property 1) implies a significant reduction in the computation of optimal allocati ons. As an application, we further characterize optimal policies when the message generation at the transmitter of higher priority is stocha stically larger than the message generation at the other. Under additi onal restrictions on the average arrival rate and the second moment of the number of arrivals per slot, similar results are derived for opti mal policies with time-average costs.