The SYNC project (Scheduling Your Network Connections)
Related Activities
Outreach Roadshow

Directed by Mor Harchol-Balter

A busy Web server services thousands of requests concurrently. Traditionally, these requests are scheduled independently of their size. The requests are time-shared, with each request receiving a FAIR share of the Web server resources. The SYNC project proposes, instead, UNFAIR scheduling, in which priority is given to SHORT requests, or those requests which have short remaining time, in accordance with the well-known scheduling algorithm SRPT (shortest-remaining-processing-time-first).

Initially, SRPT-like scheduling sounds like it will starve the large requests. However, our preliminary theoretical results and implementation results show that in fact, for Web-type workloads, ALL requests, including the largest ones, will benefit from SRPT-like scheduling.

The implementation testbed for the SYNC project involves a WAN setup with an Apache Web server running on Linux and multiple client machines distributed worldwide which send HTTP requests to the server. To instrument SRPT scheduling, modifications must be made both to the Web server software (in this case, Apache) and to the operating system software (in this case, Linux). The figures illustrate the kernel-level modifications necessary. Figure (a) shows traditional Linux. Here there is a socket for each connection and these take turns FAIRLY feeding into the single transmit queue. Figure (b) shows our modified Linux where there are multiple priority queues. Requests corresponding to connections for short files or files close to completion are directed into the higher priority queues.

(a) Original Linux

(b) Modified Linux


This material is based upon work supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation