An Index Policy for Congestion Control in Routers with Future-Path Information

We address the problem of congestion control of randomly appearing and disappearing flows in a bottleneck router by modeling it as a stochastic and dynamic resource allocation problem. In future telecommunication networks, routers may have access to information about current congestion at other network nodes. This information is exploited to improve congestion control mechanisms so that the network suffers lower packets losses, lower end- to-end delays, and provides higher amount of delivered packets (goodput).

We discuss how a novel concept of network-capability fairness arises if the network objective is to maximize the expected overall goodput. We model the congestion control problem in the framework of Markov decision processes with special structure, known as the multi-armed restless bandit problem. The sample-path constraint of bounded buffer space makes the congestion control problem PSPACE-hard. Therefore, our focus narrows to designing a tractable, implementable, and well-performing heuristic. We employ Lagrangian relaxation in order to decompose the multi-flow problem into single-flow parametric subproblems. These subproblems are under a concavity condition optimally solved in terms of marginal productivity indices.

In the context of the problem, the indices can be interpreted as transmission indices, or prices, as they evaluate the usefulness of flow transmission at the current moment. These indices form an index policy for the multiflow problem, which prescribes to give higher transmission priority to flows with higher indices. This index policy is optimal in the problem without the sample-path buffer constraint; otherwise optimality cannot be assured.