Adaptive back-pressure congestion control based on local information

Abstract

The problem of distributed congestion control as it arises in communication networks as well as in manufacturing systems is studied in this paper. In particular, a multistage queueing system that models virtual circuit and datagram communication networks and a class of manufacturing systems are considered. The topology may be arbitrary, there are multiple traffic classes, and the routing can be class dependent, with routes that may form direct or indirect loops. The model incorporates the functions of transmission scheduling, flow control, and routing, through which congestion control is performed in the network. A policy is given that performs these functions jointly. According to the policy, heavily loaded queues are given higher priority in service. A congested node may reduce the how from upstream nodes through a flow control mechanism. Whenever routing is required, it is performed in such a manner that the lightly loaded queues receive most of the traffic. For arrival processes with bounded burstiness, the policy guarantees bounded backlogs in the network, as long as the load of each server is less than one. The actions of each server are based on the state of its own queues and of the queues one hop away. Therefore, they are implementable in a distributed fashion. An adaptive version of the policy is also provided which makes it independent of the arrival rates.