Advanced

Linear programming relaxations and marginal productivity index policies for the buffer sharing problem

Cao, Jianhua LU and Nyberg, Christian LU (2008) In Queueing Systems 60(3-4). p.247-269
Abstract
We study the dynamic admission control for a finite shared buffer with support of multiclass traffic under Markovian assumptions. The problem is often referred to as buffer sharing in the literature. From the linear programming (LP) formulation of the continuous-time Markov decision process (MDP), we construct a hierarchy of increasingly stronger LP relaxations where the hierarchy levels equal the number of job classes. Each relaxation in the hierarchy is obtained by projecting the original achievable performance region onto a polytope of simpler structure. We propose a heuristic policy for admission control, which is based on the theory of Marginal Productivity Index (MPI) and the Lagrangian decomposition of the first order LP relaxation.... (More)
We study the dynamic admission control for a finite shared buffer with support of multiclass traffic under Markovian assumptions. The problem is often referred to as buffer sharing in the literature. From the linear programming (LP) formulation of the continuous-time Markov decision process (MDP), we construct a hierarchy of increasingly stronger LP relaxations where the hierarchy levels equal the number of job classes. Each relaxation in the hierarchy is obtained by projecting the original achievable performance region onto a polytope of simpler structure. We propose a heuristic policy for admission control, which is based on the theory of Marginal Productivity Index (MPI) and the Lagrangian decomposition of the first order LP relaxation. The dual of the relaxed buffer space constraint in the first order LP relaxation is used as a proxy to the cost of buffer space. Given that each of the decomposed queueing admission control problems satisfies the indexability condition, the proposed heuristic accepts a new arrival if there is enough buffer space left and the MPI of the current job class is greater than the incurred cost of buffer usage. Our numerical examples for the cases of two and eight job classes show the near-optimal performance of the proposed MPI heuristic. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Marginal productivity index policy, Markov decision, process, 60K25, 60K30, 68M20, 90B05, 90B22, 90B18, 90C08, 90C59, 90C40, relaxation, Linear programming, Multi-class queueing system, Buffer sharing problem
in
Queueing Systems
volume
60
issue
3-4
pages
247 - 269
publisher
Kluwer
external identifiers
  • wos:000261344600005
  • scopus:57349143633
ISSN
0257-0130
DOI
10.1007/s11134-008-9096-3
language
English
LU publication?
yes
id
861404fb-57d1-4f89-81ea-9af3ba405331 (old id 1304418)
date added to LUP
2009-03-23 15:07:28
date last changed
2017-01-01 06:09:10
@article{861404fb-57d1-4f89-81ea-9af3ba405331,
  abstract     = {We study the dynamic admission control for a finite shared buffer with support of multiclass traffic under Markovian assumptions. The problem is often referred to as buffer sharing in the literature. From the linear programming (LP) formulation of the continuous-time Markov decision process (MDP), we construct a hierarchy of increasingly stronger LP relaxations where the hierarchy levels equal the number of job classes. Each relaxation in the hierarchy is obtained by projecting the original achievable performance region onto a polytope of simpler structure. We propose a heuristic policy for admission control, which is based on the theory of Marginal Productivity Index (MPI) and the Lagrangian decomposition of the first order LP relaxation. The dual of the relaxed buffer space constraint in the first order LP relaxation is used as a proxy to the cost of buffer space. Given that each of the decomposed queueing admission control problems satisfies the indexability condition, the proposed heuristic accepts a new arrival if there is enough buffer space left and the MPI of the current job class is greater than the incurred cost of buffer usage. Our numerical examples for the cases of two and eight job classes show the near-optimal performance of the proposed MPI heuristic.},
  author       = {Cao, Jianhua and Nyberg, Christian},
  issn         = {0257-0130},
  keyword      = {Marginal productivity index policy,Markov decision,process,60K25,60K30,68M20,90B05,90B22,90B18,90C08,90C59,90C40,relaxation,Linear programming,Multi-class queueing system,Buffer sharing problem},
  language     = {eng},
  number       = {3-4},
  pages        = {247--269},
  publisher    = {Kluwer},
  series       = {Queueing Systems},
  title        = {Linear programming relaxations and marginal productivity index policies for the buffer sharing problem},
  url          = {http://dx.doi.org/10.1007/s11134-008-9096-3},
  volume       = {60},
  year         = {2008},
}