Optimal resource allocation in synchronized multi-tier Internet services

Modern Internet systems have evolved from simple monolithic systems to complex multi-tiered architectures. For these systems, providing good response times is a key business requirement. Human computer interaction studies show that online users are highly influenced by the variability in the response times. Moreover, synchronization between different tiers is a complicating factor in the optimal control and analysis of the performance. In this paper, we study a generic multi-tier model with synchronization. The system is able to share processing capacity between arriving jobs that need to be send to other tiers and the responses that have arrived after processing from these tiers. We provide structural results on the optimal resource allocation policy and provide a full characterization of the policy in the framework of Markov decision theory. We also highlight important effects of synchronization in the model and discuss their implications for practice. We validate our expressions through extensive experimentations for a wide range of resource configurations.