A decentralized discrete-time controller for dynamic routing

Abstract

A decentralized controller for dynamic routing in multi-destination large-scale data communication networks is presented. A dynamic model, which can incorporate possibly time-varying different processing delays at different nodes, is developed to describe the network dynamics. A knowledge of these delays is, however, not required for the actual implementation of the controller. It is assumed that the rate of messages being sent out from one node to another (the control signals) are updated at discrete time instants, which is the usual case in practice. The proposed controller is decentralized in the sense that all on-line computations can be done locally at the individual nodes without any information transfer from the other nodes. The design of the controller involves a linear programming optimization problem, which can be solved off-line. The resulting controller has the property that it allows the maximum possible magnitude on each external message arrival rate of the system to occur, without violating any constraints on the system. It is also shown that the proposed controller guarantees stability and clears the queues of the system in the absence of external message arrivals. The controller also avoids any looping of messages and keeps the queue lengths bounded in the presence of external message arrival rates which do not exceed a certain maximum rate. Some simulation results are presented to illustrate the controller's performance in a number of practical cases.