On team strategies for dynamic routing in packet-switching communication networks

The routing of customers in a network of queues (e.g., packets in a communication network) is considered, where decentralized routing decisions are taken dynamically, in discrete time, on the basis of on-line state information. Two basic models are examined, involving the presence of infinite or finite buffers at the network nodes, respectively, and the necessary exchange of control information among adjacent nodes is defined in order to obtain team decision problems with a partially nested information structure. These problems are first posed over a finite decision horizon, showing that they can be reduced to linear (in the infinite buffer case) or nonlinear integer programs. Then, the existence of a sufficient statistic is demonstrated, making it possible to introduce receding horizon control strategies as well as infinite horizon stationary strategies in the finite buffer case.