Advanced

Linear programming relaxations and a heuristic for the buffer sharing model - Discounted case

Cao, Jianhua LU and Nyberg, Christian LU (2005) 19th International Teletraffic Congress (ITC 19) In Performance Challenges for Efficient Next Generation Networks, Vols 6A-6C 6A-6C. p.939-948
Abstract
We investigate a model for buffer management of multi-class traffic into a finite shared buffer. A hierarchy of increasingly stronger linear programming relaxations for this model is proposed. The number of hierarchies equals the number of job classes. Each relaxation in the hierarchy is constructed by projecting the original achievable performance region into a polytope with fewer variables and fewer constraints. Based on the first order LP relaxation, we propose a heuristic buffer management policy which can be obtained efficiently and is applicable to a wide range of reward functions including weighted sum of throughputs and weighted sum of buffer utilization. According to our simulations, the proposed heuristic performs close to... (More)
We investigate a model for buffer management of multi-class traffic into a finite shared buffer. A hierarchy of increasingly stronger linear programming relaxations for this model is proposed. The number of hierarchies equals the number of job classes. Each relaxation in the hierarchy is constructed by projecting the original achievable performance region into a polytope with fewer variables and fewer constraints. Based on the first order LP relaxation, we propose a heuristic buffer management policy which can be obtained efficiently and is applicable to a wide range of reward functions including weighted sum of throughputs and weighted sum of buffer utilization. According to our simulations, the proposed heuristic performs close to optimum in all traffic conditions when the objective is to maximize the weighted sum of throughputs. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Performance Challenges for Efficient Next Generation Networks, Vols 6A-6C
volume
6A-6C
pages
939 - 948
publisher
Beijing University of Posts and Telecommunications
conference name
19th International Teletraffic Congress (ITC 19)
external identifiers
  • WOS:000232398500094
language
English
LU publication?
yes
id
20a77c21-7e01-4b93-aa43-347927c1c279 (old id 1406441)
date added to LUP
2009-06-05 09:34:46
date last changed
2016-04-16 08:18:05
@misc{20a77c21-7e01-4b93-aa43-347927c1c279,
  abstract     = {We investigate a model for buffer management of multi-class traffic into a finite shared buffer. A hierarchy of increasingly stronger linear programming relaxations for this model is proposed. The number of hierarchies equals the number of job classes. Each relaxation in the hierarchy is constructed by projecting the original achievable performance region into a polytope with fewer variables and fewer constraints. Based on the first order LP relaxation, we propose a heuristic buffer management policy which can be obtained efficiently and is applicable to a wide range of reward functions including weighted sum of throughputs and weighted sum of buffer utilization. According to our simulations, the proposed heuristic performs close to optimum in all traffic conditions when the objective is to maximize the weighted sum of throughputs.},
  author       = {Cao, Jianhua and Nyberg, Christian},
  language     = {eng},
  pages        = {939--948},
  publisher    = {ARRAY(0xa012850)},
  series       = {Performance Challenges for Efficient Next Generation Networks, Vols 6A-6C},
  title        = {Linear programming relaxations and a heuristic for the buffer sharing model - Discounted case},
  volume       = {6A-6C},
  year         = {2005},
}