Optimal hop-by-hop flow control in computer communication networks with multiple transmitters.
Redha M. Bournas · Deep Blue (University of Michigan) · 1990
We consider a flow control problem that arises in the performance modelling of packet-switched communication networks. There are M $\geq$ 2 transmitting stations sending packets to a single receiver over a slotted time-multiplexed link. For each phase consisting of T consecutive slots, the receiver allocates the slots ($\leq$T) among the M transmitters based on: (i) the arrival statistics at the transmitters, (ii) the history of previous allocations, and (iii) the one-step delayed information on the queue lengths of the transmitting stations. The objective is to determine policies that minimize an infinite planning horizon cost due to holding packets at the M stations. We analyze the expected discounted cost problem by stochastic dynamic programming. For equal holding costs at the transmitters, we derive qualitative properties of optimal policies that reduce the optimization to the calculation of optimal allocations for T states, as optimal allocations for all the other states are determined explicitly. For M = 2, convexity and submodularity of the minimal total cost lead to further properties of optimal policies, one of which is monotonicity. For independent and identically distributed arrivals, we exhibit an optimal policy in explicit form. For non-identical holding costs, we derive analogous but weaker properties of optimal policies that reduce the complexity of the optimal flow control algorithm. We derive necessary and sufficient conditions on the arrival statistics that ensure the existence of finite cost time-average policies. Under these conditions, we exhibit a pure strategy that attains a finite average cost. This allows us to prove that: (i) there exists an optimal policy for each phase length T; (ii) an optimal policy can be obtained as a limit of infinite horizon optimal discounted policies as the discounting factor $\beta$ $\to$ 1; and (iii) the properties of this optimal policy are the same as those derived for optimal discounted policies. Finally, we prove that in the absence of costs accrued by messages within the phase, there exists a policy such that the time-average cost tends toward zero as the phase length T $\to$ $\infty$. (Abstract shortened with permission of author.).