Groupe d’études et de recherche en analyse des décisions

Signaling for decentralized routing in a queueing network

Yi Ouyang Étudiant au doctorat, Department of Electrical Engineering and Computer Science, University of Michigan, États-Unis

Routing problems arise in many modern technological systems such as communication networks, transportation networks and sensor networks. There are many results on centralized routing in networked systems. However, as the size of these networks grows, it may be impossible for a centralized controller to collect all information in a large scale network to do the routing. In modern large scale networks, it becomes increasingly important to develop theory for decentralized routing.

We consider a decentralized routing problem in a queueing network consisting of two service stations and two controllers. Each controller is affiliated with one station. Each station has an infinite size queue. At any time, a controller can route one of the customers waiting in its own station to the other station. The queueing system is informationally decentralized: each controller only knows perfectly the information about its own station; there is no direct communication between controllers to exchange queue length information. At each time a holding cost is incurred at each station due to the customers waiting at that station. The objective is to determine routing policies for the two controllers that minimize either the total expected holding cost over a finite horizon or the average cost per unit time over an infinite horizon.

In this problem there is implicit communication between the two controllers; whenever a controller decides to send or not to send a customer from its own station to the other station it communicates partial information about its queue length to the other station. This implicit communication through control actions is referred to as signaling in decentralized control. Signaling results in complex communication and decision making problems. In spite of the complexity of signaling involved, we show that an optimal signaling strategy is described by a threshold policy which depends on the common information between the two controllers. We explicitly determine this threshold policy and discuss how the policy uses signaling to balance the queueing network.

Entrée gratuite.
Bienvenue à tous!