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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asmussen, S., Glynn, P.W.: Stochastic Simulation: Algorithms and Analysis, vol. 57. Springer (2007)
Bruneel, H., Kim, B.G.: Discrete-time models for communication systems including ATM. Kluwer Academic Publishers (1992)
Demoor, T., Walraevens, J., Fiems, D., Bruneel, H.: Performance analysis of a priority queue: Expedited forwarding PHB in diffserv. AEU-International Journal of Electronics and Communications 65(3), 190–197 (2011)
Fiedler, M., Hossfeld, T., Tran-Gia, P.: A generic quantitative relationship between quality of experience and quality of service. IEEE Network 24(2), 36–41 (2010)
Homg, M.F., Lee, W.T., Lee, K.R., Kuo, Y.H.: An adaptive approach to weighted fair queue with QoS enhanced on IP network. In: Proceedings of IEEE Region 10 International Conference on Electrical and Electronic Technology, TENCON 2001, vol. 1, pp. 181–186. IEEE (2001)
Huang, T.Y.: Analysis and modeling of a threshold based priority queueing system. Computer Communications 24(3), 284–291 (2001)
Lee, H.W., Kim, C., Chong, S.: Scheduling and source control with average queue-length control in cellular networks. In: IEEE International Conference on Communications, ICC 2007, pp. 109–114. IEEE (2007)
van Moorsel, A.: Metrics for the internet age: quality of experience and quality of business. In: Fifth International Workshop on Performability Modeling of Computer and Communication Systems, vol. 34, pp. 26–31. Arbeitsberichte des Instituts für Informatik, Universität Erlangen-Nürnberg, Germany (2001)
Neely, M.J.: Delay-based network utility maximization. IEEE/ACM Transactions on Networking (TON) 21(1), 41–54 (2013)
Parekh, A.K., Gallager, R.G.: A generalized processor sharing approach to flow control in integrated services networks: the single-node case. IEEE/ACM Transactions on Networking (TON) 1(3), 344–357 (1993)
Parekh, A.K., Gallagher, R.G.: A generalized processor sharing approach to flow control in integrated services networks: the multiple node case. IEEE/ACM Transactions on Networking (TON) 2(2), 137–150 (1994)
Spall, J.C.: Introduction to stochastic search and optimization: Estimation, simulation and control, vol. 65. John Wiley & Sons (2005)
Vanlerberghe, J., Maertens, T., Walraevens, J., De Vuyst, S., Bruneel, H.: A hybrid analytical/simulation optimization of generalized processor sharing. In: Proceedings of The 25th International Teletraffic Congress (ITC 25), Shanghai, September 2013
Verloop, I.M., Ayesta, U., Borst, S.: Monotonicity properties for multi-class queueing systems. Discrete Event Dynamic Systems 20(4), 473–509 (2010)
Walraevens, J., Steyaert, B., Bruneel, H.: Performance analysis of a single-server ATM queue with a priority scheduling. Computers & Operations Research 30(12), 1807–1829 (2003)
Walraevens, J., Steyaert, B., Bruneel, H.: Performance analysis of a GI-Geo-1 buffer with a preemptive resume priority scheduling discipline. European Journal of Operational Research 157(1), 130–151 (2004)
Walraevens, J., Steyaert, B., Bruneel, H.: Analysis of a discrete-time preemptive resume priority buffer. European Journal of Operational Research 186(1), 182–201 (2008)
Walraevens, J., Vanlerberghe, J., Maertens, T., De Vuyst, S., Bruneel, H.: Strict monotonicity and continuity of mean unfinished work in two queues sharing a processor (forthcoming)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Vanlerberghe, J., Walraevens, J., Maertens, T., De Vuyst, S., Bruneel, H. (2015). On Generalized Processor Sharing and Objective Functions: Analytical Framework. In: Beltrán, M., Knottenbelt, W., Bradley, J. (eds) Computer Performance Engineering. EPEW 2015. Lecture Notes in Computer Science(), vol 9272. Springer, Cham. https://doi.org/10.1007/978-3-319-23267-6_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-23267-6_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23266-9
Online ISBN: 978-3-319-23267-6
eBook Packages: Computer ScienceComputer Science (R0)