Marginal Productivity Indices and Linear Programming Relaxations for Dynamic Resource Allocation in Queueing Systems
(2008) In Series of Licentiate and Doctoral Thesis- Abstract
- Many problems concerning resource management in modern communication systems can be simplified to queueing models under Markovian assumptions. The computation of the optimal policy is however often hindered by the curse of dimensionality especially for models that support multiple traffic or job classes. The research focus naturally turns to computationally efficient bounds and high performance heuristics. In this thesis, we apply the indexability theory to the study of admission control of a single server queue and to the buffer sharing problem for a multi-class queueing system. Our main contributions are the following: we derive the Marginal Productivity Index (MPI) and give a sufficient indexability condition for the admission control... (More)
- Many problems concerning resource management in modern communication systems can be simplified to queueing models under Markovian assumptions. The computation of the optimal policy is however often hindered by the curse of dimensionality especially for models that support multiple traffic or job classes. The research focus naturally turns to computationally efficient bounds and high performance heuristics. In this thesis, we apply the indexability theory to the study of admission control of a single server queue and to the buffer sharing problem for a multi-class queueing system. Our main contributions are the following: we derive the Marginal Productivity Index (MPI) and give a sufficient indexability condition for the admission control model by viewing the buffer as the resource; we construct hierarchical Linear Programming (LP) relaxations for the buffer sharing problem and propose an MPI based heuristic with its performance evaluated by discrete event simulation. In our study, the admission control model is used as the building block for the MPI heuristic deployed for the buffer sharing problem. Our condition for indexability only requires that the reward function is concavelike. We also give the explicit non-recursive expression for the MPI calculation. We compare with the previous result of the indexability condition and the MPI for the admission control model that penalizes the rejection action. The study of hierarchical LP relaxations for the buffer sharing problem is based on the exact but intractable LP formulation of the continuous-time Markov Decision Process (MDP). The number of hierarchy levels is equal to the number of job classes. The last one in the hierarchy is exact and corresponds to the exponentially sized LP formulation of the MDP. The first order relaxation is obtained by relaxing the constraint that no buffer overflow may occur in any sample path to the constraint that the average buffer utilization does not exceed the available capacity. Based on the Lagrangian decomposition of the first order relaxation, we propose a heuristic policy based on the concept of MPI. Each one of the decomposed subproblems corresponds to the admission control model we described above. The link to the decomposed sub-problems is the Lagrangian multiplier for the relaxed buffer size constraint in the first order relaxation. Our simulation study indicates the near optimal performance of the heuristic in the (randomly generated) instances investigated. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1261521
- author
- Cao, Jianhua LU
- supervisor
- opponent
-
- Prof. Niño-Mora, José, Department of Statistics, Universidad Carlos III de Madrid
- organization
- publishing date
- 2008
- type
- Thesis
- publication status
- published
- subject
- keywords
- Markov decision process, Indexability, Linear programming, Queueing theory, Optimization
- in
- Series of Licentiate and Doctoral Thesis
- pages
- 88 pages
- defense location
- Lecture hall E:1406, Department of Electrical and Information Technology, Ole Römers väg 3, Lund University Faculty of Engineering
- defense date
- 2008-11-28 13:15:00
- ISSN
- 1654-790X
- project
- Tele- och datakommunikationssystem: Performance Analysis of distributed Applications
- language
- English
- LU publication?
- yes
- id
- f86a0819-76c4-4de4-9635-034c1a3f4f32 (old id 1261521)
- date added to LUP
- 2016-04-04 09:45:22
- date last changed
- 2020-05-19 16:38:37
@phdthesis{f86a0819-76c4-4de4-9635-034c1a3f4f32,
abstract = {{Many problems concerning resource management in modern communication systems can be simplified to queueing models under Markovian assumptions. The computation of the optimal policy is however often hindered by the curse of dimensionality especially for models that support multiple traffic or job classes. The research focus naturally turns to computationally efficient bounds and high performance heuristics. In this thesis, we apply the indexability theory to the study of admission control of a single server queue and to the buffer sharing problem for a multi-class queueing system. Our main contributions are the following: we derive the Marginal Productivity Index (MPI) and give a sufficient indexability condition for the admission control model by viewing the buffer as the resource; we construct hierarchical Linear Programming (LP) relaxations for the buffer sharing problem and propose an MPI based heuristic with its performance evaluated by discrete event simulation. In our study, the admission control model is used as the building block for the MPI heuristic deployed for the buffer sharing problem. Our condition for indexability only requires that the reward function is concavelike. We also give the explicit non-recursive expression for the MPI calculation. We compare with the previous result of the indexability condition and the MPI for the admission control model that penalizes the rejection action. The study of hierarchical LP relaxations for the buffer sharing problem is based on the exact but intractable LP formulation of the continuous-time Markov Decision Process (MDP). The number of hierarchy levels is equal to the number of job classes. The last one in the hierarchy is exact and corresponds to the exponentially sized LP formulation of the MDP. The first order relaxation is obtained by relaxing the constraint that no buffer overflow may occur in any sample path to the constraint that the average buffer utilization does not exceed the available capacity. Based on the Lagrangian decomposition of the first order relaxation, we propose a heuristic policy based on the concept of MPI. Each one of the decomposed subproblems corresponds to the admission control model we described above. The link to the decomposed sub-problems is the Lagrangian multiplier for the relaxed buffer size constraint in the first order relaxation. Our simulation study indicates the near optimal performance of the heuristic in the (randomly generated) instances investigated.}},
author = {{Cao, Jianhua}},
issn = {{1654-790X}},
keywords = {{Markov decision process; Indexability; Linear programming; Queueing theory; Optimization}},
language = {{eng}},
school = {{Lund University}},
series = {{Series of Licentiate and Doctoral Thesis}},
title = {{Marginal Productivity Indices and Linear Programming Relaxations for Dynamic Resource Allocation in Queueing Systems}},
url = {{https://lup.lub.lu.se/search/files/5408841/1261523.pdf}},
year = {{2008}},
}