Paper 1:
Implementation of SRPT Scheduling in Web Servers
Mor Harchol-Balter, Nikhil Bansal, Bianca Schroeder, Mukesh Agrawal

Paper 2:
Analysis of SRPT Scheduling: Investigating Unfairness
Mor Harchol-Balter, Nikhil Bansal
SIGMETRICS '01
 

• Paper Overview (Background)
• Implementation
• Results
• Unfairness Analysis and Starvation
• Discussion

• Motivation
• Web servers are very busy. Servicing hundreds of requests at the same time.
• Cause large queuing delays at the web server.
• Most of the requests are static.
• Size of the request is approximated by the size of the file.
• Size of the request is used to affect the scheduling order to minimize the queuing delay.
• Instead of FAIR scheduling, used UNFAIR scheduling in accordance with the Shortest Remaining Processing Time (SRPT) scheduling policy.
• Bottleneck resource is the bandwidth on the access link out of the web site. Deploy SRPT at the bottleneck resource.

 
• Relevant Previous Work
• Alemeida et al : Used both a user - level approach and a kernel level approach. Allows very coarse grained control over the scheduling of the processes.
• Crovella et al : Connection scheduling at the application level only. Controls the order in which read() and write() calls are made. No control over the low level scheduling. Improve the mean response time but reduce the server throughput.
• Bender, Chakrabarti et al : Reject the idea of using SRPT scheduling because large files will have an arbitrarily high max. slowdown.
• Roberts & Massoulie suggest that SRPT may be beneficial in the case of heavy tailed flow sizes.

 
• Goals of this Paper
• Improving client experience ( the client's response time) while maintaining the same server throughput.
• Reduce queuing delays at the server.
• Improve the performance of web servers servicing static HTTP requests.
• Whether performance improvements are significant?
• Do large jobs starve?

Corresponding to each connection, there is a socket buffer on the web server end into which the server writes the contents of the requested file. Traditionally, the sockets are drained in a Round Robin order.
For the experiments conducted, the OS used was Linux 2.2.16 running Apache on it.

• Default Linux Configuration (Paper 1, Fig. 1)
• Data Streaming into each socket buffer is encapsulated into packets which obtain TCP and IP headers.
• Throughout the processing, the packet streams corresponding to each connection is kept separate.
• A single priority queue into which all streams feed.

 
• SRPT Configuration (Paper 1, Fig. 2)
• Linux kernel is built with certain options set.
• "tc" user space tool is used to switch the device queue from default 3-band queue to the 16-band prio queue.
• Queues are numbered 0-15; 0 has the highest priority and 15 has the lowest.
• Connections of priority "i" feed into the "ith" priority queue.
• Priority queue "i" is only allowed to flow if 0 through "i-1" are empty.
• In the experiments throughout the paper, only 5 priority queues were used.

 
• Final Algorithm
• Priorities 1, 2, 3... are associated with size ranges.
• When request arrives, it is given a socket with priority 0.
• After the request size is determined, the priority of the socket is reset based on the size of the request. ( paper 1, section 3.3.3 for details)
• As the remaining size of the request diminishes, the priority of the socket is dynamically updated to reflect the remaining size of the request.

 
• Design Choice
• Problems:
• Overhead of system calls to modify priorities.
• Need to modify server code.
• When does the socket priority changes?
• Does it require checking for the file size at random or defined intervals?
• Leads to packet reordering issues.
• Claims:
• System calls are limited. At most 5 times or the very largest of files. Low system call overhead in Linux.
• Modification to the server code are minimal.
• Assumptions
• How precise is the ranking of the remaining processing requirements of requests? Ideally should be infinite.
• Size cut offs based on "rules-of-thumb" coined by the authors.

• Some Definitions
• System Load: Bandwidth used on an Average/ Max. Available Bandwidth
• Mean Response Time: Time from when the client submits the requests until the time the client receives the last byte.
• Mean Slowdown: Mean Response Time/(Time it would have taken if it were the sole request in the system). In Paper 2, mean slowdown has been defined as (Mean Response Time)/ (Size of the job)
• Mean Response Time as a function of request size: To indicate whether big requests are being treated unfairly.

 
• Mean Response Time (Paper 1, Fig. 3)
• Lower Loads: same under FAIR scheduling and SRPT scheduling.
• Loads > 0.5: mean response time is lowered by a factor of 3-8.

 
• Mean Slowdown (Paper 1, Fig. 4)
• Lower Loads: same under FAIR scheduling and SRPT scheduling.
• Loads > 0.5: mean slowdown is lowered by a factor of 4 - 16.

 
• Unfairness (Paper 1, Fig. 5)
• For files > 1 MB, performs slightly worse under SRPT.
• For lower loads, unfairness is practically non existent. ( analysis in paper 2)
• For higher loads, unfairness to big requests increases. ( analysis in paper 2)

• Results are different for Surge-modified workloads and trace-driven workloads. (Paper 1, Fig. 7)
• Quick Fix shows  results with 3 bands, what happens with 4 bands?
• How to obtain the Quick Fix?

The second paper attempts to prove that when SRPT is compared with PS scheduling, improvement is significant under high loads w.r.t. mean response time and mean slowdown and the degree of unfairness for larger jobs has an upper bound as opposed to an arbitrarily max. value.
 

• For all job size distributions, as load -> 1,  mean response time as well as mean slowdown improve atleast by a factor of 2.
• For job size distributions with a heavy tailed propoerty, as load -> 1, mean slowdown improves by a factor of 100.
• A Bounded Pareto distribution has been defined as B(k, p, alpha). For k = 332, p=10^10, alpha = 1.1, the distribution has a heavy tailed property.
• There exist job size distributions such that every job does better under SRPT than under PS. ( Paper 2, Fig. 1)
• For any job size distribution and any load, expected response time for jobs of size <= x for SRPT is less than the expected response time for PS such that jobs of size <= x comprise less than half the load.
• If load <= 0.5, then all jobs have a lower expected response time under SRPT as compared to PS.
• Even if load > 0.5, a majority of the jobs have better expected response times under SRPT.
• For a given load, the expected response time for a job cannot be arbitrarily worse under SRPT, as compared with PS.
• For job size distributions with the HT property, atleast 99% of the jobs have an expected slowdown of atmost 4, irrespective of the system load.
• For any job size distribution, there is a load (less than 1) such that the largest job has a higher expected response time under SRPT than under PS but it is not arbitrarily max.

• If  propagation delays are introduced, how to define a request size?
• My work deals in investigating the behavior of such a scheduling policy if the size of a request is determined by the transfer time of the requested file.