Nobody fancies a long wait between requesting some kind of online service and actually receiving that service. Therefore, in many situations, ICT-specialists aim to design their servers in such a way that their customers are served in an efficient manner. Theoretically assessing the efficiency of such algorithms is particularly challenging when the customers’ requirements are unknown (the algorithm is “blind”). The PhD-research of Bart Kamphorst contributes a number of performance analyses of blind algorithms and moreover identifies a blind algorithm that is in some sense optimal.
Literature offers a wide range of blind scheduling policies. Most of these blind scheduling policies work very efficiently in some settings, but rather inefficiently in other settings. In fact, it turns out that it is not even possible for a blind scheduling policy to perform optimally (extremely efficiently) in all settings. We were able to quantify this fundamental inefficiency – that is; the minimum amount of inefficiency that any blind scheduling policy necessarily suffers in an unfavorable setting. Thereafter, we showed that there exists a blind scheduling policy that is never less efficient than our calculated minimum inefficiency. This roughly means that we identified a blind scheduling policy that performs reasonably efficient regardless of the stochastic nature of the customers’ requirements, and there cannot exist another blind scheduling policy that is more efficient in such a general setting.
Not only is the above result is novel in its conclusion, but it is also innovative in its derivation. The analysis displays a successful combination of techniques from the mathematical areas of scheduling theory and queueing theory. Scheduling theory generally investigates the worst-case behaviour of scheduling policies, whereas queueing theory investigates the average-case behaviour of scheduling policies in specified stochastic settings. It is inspiring to see how insights from both communities contribute to our analysis, and we hope that this result stimulates researchers from both areas to explore the interface.
If instead of the general setting above one focusses on special settings, then there exist blind scheduling policies that perform (almost) as good as their non-blind counterparts. It is usually hard to obtain these kind of results, since scheduling policies are generally complex to analyze. We introduced a framework that potentially facilitates a more thorough analysis of many scheduling policies, and used this framework to obtain several new insights of the efficiency of the Foreground-Background policy.
More information
Everyone is welcome to attend the public defence of Bart Kamphorst, of his thesis 'Heavy-traffic behaviour of scheduling policies in
queues' on 31 May from 16.00-18.00 hrs in the Senaatszaal of the Auditorium van de Technische Universiteit Eindhoven, Den Dolech 2 in Eindhoven
PhD-thesis: Heavy-traffic behaviour of scheduling policies in queues. Supervisors: Bert Zwart (CWI, TU/e) and Nikhil Bansal (CWI, TU/e).
Learn more about the work of CWI’s Stochastics group by watching their video on YouTube
