Scheduling for data center interactive services

To service requests with high quality, web search servers keep average server utilization low. As servers become busy, queuing delays increase, and requests miss their deadlines, resulting in degraded quality of service with poor user experience and potential revenue loss. In this paper, we propose a group of scheduling algorithms that can produce partial answers during overload. One of their key features is assigning processing time to each request based on system load with the objective of maximizing overall quality of responses. We propose three scheduling algorithms - offline, online clairvoyant and online nonclairvoyant. For applications with concave quality profile, we prove that the offline algorithm is optimal. We show the effectiveness of the online algorithms by conducting a simulation study modeling a web search engine. Simulation results show a significant improvement compared to traditional scheduling models with respect to average response quality.