Decentralized control strategies for dynamic routing

The routing problem in a multi-destination data communication networks is considered. A dynamic model, which can incorporate arbitrary, different, time-varying processing delays at different nodes, is developed to describe the network dynamics. Based on this model, controllers for routing control are proposed. The structures of the proposed controllers are motivated by an optimal control problem. These proposed controllers are completely decentralized in the sense that all necessary on-line computations are done locally at each node. Furthermore, the information needed for these computations is related only to the queue lengths at the present node and the adjacent downstream nodes. Both cases when the controls can be continuously changed and when the controls are updated at discrete time instants are considered. In the latter case the controls at different nodes may be updated at different time instants (i.e. the network is not necessarily synchronous). It is shown that the controllers enjoy many desirable properties; in particular, they clear all the queues of the network in the absence of external message arrivals, in finite time. Furthermore, the controllers do not direct messages around a loop. They also have certain robustness properties. Some simulation results relating to a number of realistic problems are presented to illustrate various features of the controllers.