Budget-based Control for Interactive Services with Adaptive Execution

We study the problem of managing a class of interactive services to meet a response time target while achieving high service quality. We focus here on interactive services that support adaptive execution, such as web search engines and finance servers. With adaptive execution, when a request receives more processing time, its result improves, posing new challenges and opportunities for resource management.

We propose a new budget-based control model for interactive services with adaptive execution. The budget represents the amount of resources assigned to all pending requests. The budget-based control model consists of two components: (1) a hybrid control mechanism, which combines adaptive and integral controllers and controls the budget in order to meet the response time target with small steady-state error, fast settling time and little runtime overhead, and (2) an optimization procedure, which takes advantage of adaptive execution to maximize the total response quality of all pending requests under a given budget.

We implement and evaluate the budget-based control model experimentally in Microsoft Bing, a commercial web search engine. The experimental results show that it achieves more accurate control of mean response time and higher response quality than traditional static and dynamic admission control techniques that control the queue length. We also apply the model to a finance server that estimates option prices, and conduct a simulation study. The simulation results show large benefits for budget-based control. For example, under the same response time and quality requirements, the budget-based model accommodates double the system throughput compared to a traditional queue-based control model.