Optimal routing into two heterogeneous service stations with delayed information

Author

Artiges, Damien

Author_Institution

Dept. of Electr. & Comput. Eng., North Carolina State Univ., Raleigh, NC, USA

fYear

1993

fDate

15-17 Dec 1993

Firstpage

2737

Abstract

We consider the problem of optimal routing of messages into two queues. The aim is to minimize some cost, composed of a holding cost which is linear in the queue lengths plus an admission cost. As often happens in high-speed communication networks, we assume that the decision maker has a delayed information on the state of the network. We study this problem in the framework of Markov decision processes with a countable state space and unbounded cost; both the discounted and the average cost are considered. We establish some supermodularity properties of the value function using “value-iteration” arguments, this in turn enables us to characterize the optimal policy. It is shown to be monotone, and is characterized by some switching curves

Keywords

Markov processes; decision theory; minimisation; queueing theory; telecommunication network routing; Markov decision processes; admission cost; average cost; cost minimization; countable state space; delayed information; discounted cost; heterogeneous service stations; high-speed communication networks; holding cost; monotone policy; optimal message routing; queues; supermodularity properties; switching curves; unbounded cost; value function; value-iteration arguments; Communication networks; Cost function; Delay effects; Dynamic programming; High-speed networks; Optimal control; Propagation delay; Queueing analysis; Routing; State-space methods;

fLanguage

English

Publisher

ieee

Conference_Titel

Decision and Control, 1993., Proceedings of the 32nd IEEE Conference on

Conference_Location

San Antonio, TX

Print_ISBN

0-7803-1298-8

Type

conf

DOI

10.1109/CDC.1993.325693

Filename

325693