Name
Abstract | ||
|---|---|---|
In this paper we study rerouting policies for queueing systems with two Pois- son arrival streams and two exponential servers. The arrival customers can be rerouted from their normal server to the other server depending on limited information on the two queue length. The policies are compared on the basis of necessary and sucient conditions for ergodicity. For this purpose we make use of Lyapunov functions. In the seminal work of Foster (4), Lyapunov functions were used as a tool for nding necessary conditions for ergodicity of simple Markov processes. In recent years there has been a lot of work on the much harder problem of nding necessary and sucien t conditions for ergodicity, using test functions similar to Lyapunov functions. The work of Malyshev (3),(6),(9),(10) on random walks in simplices with boundary conditions, the work of Hajek (5) on adaptive ALOHA, and the work of Meyn and Tweedie (11) should be cited in this respect. Application of this work to specic examples with several regions of uniform transition probabilities, with fairly general behavior on the boundaries between the regions, turns out to be often quite hard. In this paper we treat a few examples of Markov processes occurring in the analysis of rerouting strategies for queueing systems with several arrival streams and several servers. Specically we consider models with two independent Poisson arrival streams and two exponential service stations. We assume that arrival stream i, i = 1; 2, is associated to and normally served by its preferred service station i. However, provided one pays a certain penalty, it is possible to have tasks from arrival stream i served on station 3 i. To obtain a simple Markovian model we assume that the penalty consists of creating t (t 1) tasks instead of one task each time a rerouting away from the preferred service station occurs. We consider two rerouting strategies. Rerouting can occur if the preferred service station has a queue length exceeding a certain threshold and if in the other one the number of jobs is less than a given threshold. Another rerouting strategy reroutes a task as soon as the preferred queue length is longer, by a certain threshold, than the other queue length. In both cases we consider both the asymmetrical case where only tasks from arrival stream 1 can be rerouted to server |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1007/BF01149177 | Queueing Syst. |
Keywords | Field | DocType |
Inhomogeneous random walks,ergodicity,Lyapunov functions,rerouting policies | Lyapunov function,Mathematical optimization,Ergodicity,Markov process,Exponential function,Random walk,Server,Queueing theory,Poisson distribution,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 3-4 | 0257-0130 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| René Boel | 1 | 56 | 5.58 |
| Johan Van Horebeek | 2 | 20 | 3.38 |