Advanced search
Add to list

Using a power series approximation for the optimization of generalized processor sharing

Jasper Vanlerberghe (UGent) , Joris Walraevens (UGent) , Tom Maertens (UGent) and Herwig Bruneel (UGent)
Author
Organization
Abstract
Generalized Processor Sharing (GPS) is a simple, flexible and fair scheduling mechanism to achieve delay differentiation between several customer classes. The amount of delay differentiation is regulated by the weights given to the classes. We assume a discrete-time, two-class GPS queueing system. Our goal is to derive the optimal weights in order to minimize a weighted sum of functions of the mean delays of both classes. As analytical results are scarce we use an approximation method. The approximation is based on power series expansions of the mean queue length of each of the queues for certain weights. Padé approximants are used to extrapolate the approximation to the whole domain of possible weights, resulting in a set of approximations. An algorithm is proposed to filter out the infeasible solutions (with regard to monotonicity and other characteristics of the system) and aggregate the others, resulting in a single approximation. The result proves to be an accurate approximation of the optimal weights w.r.t. the cost function. For a load of 90\% we have a maximum misprediction of 1\% of the cost, in the case of a weighted sum of squares of the mean delays.

Citation

Please use this url to cite or link to this publication:

MLA
Vanlerberghe, Jasper, Joris Walraevens, Tom Maertens, et al. “Using a Power Series Approximation for the Optimization of Generalized Processor Sharing.” BESTCOM Meeting, Abstracts. 2014. Print.
APA
Vanlerberghe, J., Walraevens, J., Maertens, T., & Bruneel, H. (2014). Using a power series approximation for the optimization of generalized processor sharing. BESTCOM meeting, abstracts. Presented at the BESTCOM meeting.
Chicago author-date
Vanlerberghe, Jasper, Joris Walraevens, Tom Maertens, and Herwig Bruneel. 2014. “Using a Power Series Approximation for the Optimization of Generalized Processor Sharing.” In BESTCOM Meeting, Abstracts.
Chicago author-date (all authors)
Vanlerberghe, Jasper, Joris Walraevens, Tom Maertens, and Herwig Bruneel. 2014. “Using a Power Series Approximation for the Optimization of Generalized Processor Sharing.” In BESTCOM Meeting, Abstracts.
Vancouver
1.
Vanlerberghe J, Walraevens J, Maertens T, Bruneel H. Using a power series approximation for the optimization of generalized processor sharing. BESTCOM meeting, abstracts. 2014.
IEEE
[1]
J. Vanlerberghe, J. Walraevens, T. Maertens, and H. Bruneel, “Using a power series approximation for the optimization of generalized processor sharing,” in BESTCOM meeting, abstracts, Ghent, Belgium, 2014.
@inproceedings{4384589,
  abstract     = {Generalized Processor Sharing (GPS) is a simple, flexible and fair scheduling mechanism to achieve delay differentiation between several customer classes. The amount of delay differentiation is regulated by the weights given to the classes. We assume a discrete-time, two-class GPS queueing system. Our goal is to derive the optimal weights in order to minimize a weighted sum of functions of the mean delays of both classes. As analytical results are scarce we use an approximation method. The approximation is based on power series expansions of the mean queue length of each of the queues for certain weights. Padé approximants are used to extrapolate the approximation to the whole domain of possible weights, resulting in a set of approximations. An algorithm is proposed to filter out the infeasible solutions (with regard to monotonicity and other characteristics of the system) and aggregate the others, resulting in a single approximation. The result proves to be an accurate approximation of the optimal weights w.r.t. the cost function. For a load of 90\% we have a maximum misprediction of 1\% of the cost, in the case of a weighted sum of squares of the mean delays.},
  author       = {Vanlerberghe, Jasper and Walraevens, Joris and Maertens, Tom and Bruneel, Herwig},
  booktitle    = {BESTCOM meeting, abstracts},
  language     = {eng},
  location     = {Ghent, Belgium},
  title        = {Using a power series approximation for the optimization of generalized processor sharing},
  year         = {2014},
}