Heavy Tails: Performance Models and Scheduling Disciplines

ITC-18 Tutorial

Heavy Tails: Performance Models and Scheduling Disciplines

O.J. Boxma, S.C. Borst, R. Núñez Queija, M. Harchol-Balter

In this tutorial we focus on the role of scheduling disciplines in controlling the effect of heavy-tailed traffic characteristics on network performance. The tutorial is based on a collection of papers (see full list of papers) and consists of four related parts, each presented by one of the speakers.

(i) Introduction and motivation of heavy tails; performance models; numerical issues; asymptotic scalings; various methodologies, such as probabilistic, transform, and sample-path approaches.

[Presented by Onno Boxma; see slides (PDF), see relevant papers]

(ii) Workload asymptotics for Generalized Processor Sharing systems; in particular the qualitative difference between various regimes as a function of the service weights and traffic loads.

[Presented by Sem Borst; see slides (PDF), see relevant papers]

(iii) Delay asymptotics for a variety of scheduling strategies, such as Processor Sharing (PS), Foreground-Background Processor Sharing (FB-PS), Shortest Remaining Processing Time First (SRPT), and PS in integrated-services environments.

[Presented by Sindo Núñez Queija; see slides (PDF), see relevant papers]

(iv) Scheduling in practice: connection scheduling in Web servers. Classification of scheduling policies with respect to unfairness properties, with special attention to heavy-tailed service requirements.

[Presented by Mor Harchol-Balter; see slides (Power Point), see relevant papers]