Title :
Approximating the optimal weights for discrete-time generalized processor sharing
Author :
Vanlerberghe, Jasper ; Walraevens, J. ; Maertens, Tom ; Bruneel, H.
Author_Institution :
Dept. of Telecommun. & Inf. Process, Ghent Univ., Ghent, Belgium
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. In this paper 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. The main contribution of this article is that power series approximations can be used effectively for optimization purposes.
Keywords :
approximation theory; differentiation; extrapolation; minimisation; queueing theory; Padé approximants; customer classes; delay differentiation; discrete-time GPS queueing system; discrete-time generalized processor sharing; fair scheduling mechanism; flexible scheduling mechanism; mean queue length; optimal weight approximation; power series expansions; two-class GPS queueing system; weighted sum-of-functions minimization; Approximation methods; Cost function; Delays; Global Positioning System; Mathematical model; Optimized production technology; Servers; Generalized Processor Sharing (GPS); approximation; optimization; queueing;
Conference_Titel :
Networking Conference, 2014 IFIP
Conference_Location :
Trondheim
DOI :
10.1109/IFIPNetworking.2014.6857105