Advanced search
1 file | 421.74 KB Add to list

On generalized processor sharing and objective functions: analytical framework

Author
Organization
Abstract
Today, telecommunication networks host a wide range of heterogeneous services. Some demand strict delay minima, while others only need a best-effort kind of service. To achieve service differentiation, network traffic is partitioned in several classes which is then transmitted according to a flexible and fair scheduling mechanism. Telecommunication networks can, for instance, use an implementation of Generalized Processor Sharing (GPS) in its internal nodes to supply an adequate Quality of Service to each class. GPS is flexible and fair, but also notoriously hard to study analytically. As a result, one has to resort to simulation or approximation techniques to optimize GPS for some given objective function. In this paper, we set up an analytical framework for two-class discrete-time probabilistic GPS which allows to optimize the scheduling for a generic objective function in terms of the mean unfinished work of both classes without the need for exact results or estimations/approximations for these performance characteristics. This framework is based on results of strict priority scheduling, which can be regarded as a special case of GPS, and some specific unfinished-work properties in two-class GPS. We also apply our framework on a popular type of objective functions, i.e., convex combinations of functions of the mean unfinished work. Lastly, we incorporate the framework in an algorithm to yield a faster and less computation-intensive result for the optimum of an objective function.
Keywords
objective function, queueing, optimization, Generalized Processor Sharing (GPS), QUEUE, BUFFER, PRIORITY, FLOW-CONTROL, PERFORMANCE ANALYSIS, INTEGRATED SERVICES NETWORKS, scheduling

Downloads

  • analyzing cost function.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 421.74 KB

Citation

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

MLA
Vanlerberghe, Jasper, et al. “On Generalized Processor Sharing and Objective Functions: Analytical Framework.” Lecture Notes in Computer Science, edited by Marta Beltrán et al., vol. 9272, Springer International Publishing, 2015, pp. 96–111, doi:10.1007/978-3-319-23267-6_7.
APA
Vanlerberghe, J., Walraevens, J., Maertens, T., De Vuyst, S., & Bruneel, H. (2015). On generalized processor sharing and objective functions: analytical framework. In M. Beltrán, W. Knottenbelt, & J. Bradley (Eds.), Lecture Notes in Computer Science (Vol. 9272, pp. 96–111). https://doi.org/10.1007/978-3-319-23267-6_7
Chicago author-date
Vanlerberghe, Jasper, Joris Walraevens, Tom Maertens, Stijn De Vuyst, and Herwig Bruneel. 2015. “On Generalized Processor Sharing and Objective Functions: Analytical Framework.” In Lecture Notes in Computer Science, edited by Marta Beltrán, William Knottenbelt, and Jeremy Bradley, 9272:96–111. Springer International Publishing. https://doi.org/10.1007/978-3-319-23267-6_7.
Chicago author-date (all authors)
Vanlerberghe, Jasper, Joris Walraevens, Tom Maertens, Stijn De Vuyst, and Herwig Bruneel. 2015. “On Generalized Processor Sharing and Objective Functions: Analytical Framework.” In Lecture Notes in Computer Science, ed by. Marta Beltrán, William Knottenbelt, and Jeremy Bradley, 9272:96–111. Springer International Publishing. doi:10.1007/978-3-319-23267-6_7.
Vancouver
1.
Vanlerberghe J, Walraevens J, Maertens T, De Vuyst S, Bruneel H. On generalized processor sharing and objective functions: analytical framework. In: Beltrán M, Knottenbelt W, Bradley J, editors. Lecture Notes in Computer Science. Springer International Publishing; 2015. p. 96–111.
IEEE
[1]
J. Vanlerberghe, J. Walraevens, T. Maertens, S. De Vuyst, and H. Bruneel, “On generalized processor sharing and objective functions: analytical framework,” in Lecture Notes in Computer Science, Madrid, Spain, 2015, vol. 9272, pp. 96–111.
@inproceedings{6922130,
  abstract     = {{Today, telecommunication networks host a wide range of heterogeneous services. Some demand strict delay minima, while others only need a best-effort kind of service. To achieve service differentiation, network traffic is partitioned in several classes which is then transmitted according to a flexible and fair scheduling mechanism. Telecommunication networks can, for instance, use an implementation of Generalized Processor Sharing (GPS) in its internal nodes to supply an adequate Quality of Service to each class. GPS is flexible and fair, but also notoriously hard to study analytically. As a result, one has to resort to simulation or approximation techniques to optimize GPS for some given objective function. In this paper, we set up an analytical framework for two-class discrete-time probabilistic GPS which allows to optimize the scheduling for a generic objective function in terms of the mean unfinished work of both classes without the need for exact results or estimations/approximations for these performance characteristics. This framework is based on results of strict priority scheduling, which can be regarded as a special case of GPS, and some specific unfinished-work properties in two-class GPS. We also apply our framework on a popular type of objective functions, i.e., convex combinations of functions of the mean unfinished work. Lastly, we incorporate the framework in an algorithm to yield a faster and less computation-intensive result for the optimum of an objective function.}},
  author       = {{Vanlerberghe, Jasper and Walraevens, Joris and Maertens, Tom and De Vuyst, Stijn and Bruneel, Herwig}},
  booktitle    = {{Lecture Notes in Computer Science}},
  editor       = {{Beltrán, Marta and Knottenbelt, William and Bradley, Jeremy}},
  isbn         = {{9783319232669}},
  issn         = {{0302-9743}},
  keywords     = {{objective function,queueing,optimization,Generalized Processor Sharing (GPS),QUEUE,BUFFER,PRIORITY,FLOW-CONTROL,PERFORMANCE ANALYSIS,INTEGRATED SERVICES NETWORKS,scheduling}},
  language     = {{eng}},
  location     = {{Madrid, Spain}},
  pages        = {{96--111}},
  publisher    = {{Springer International Publishing}},
  title        = {{On generalized processor sharing and objective functions: analytical framework}},
  url          = {{http://doi.org/10.1007/978-3-319-23267-6_7}},
  volume       = {{9272}},
  year         = {{2015}},
}

Altmetric
View in Altmetric
Web of Science
Times cited: