On Server Provisioning for Distributed Interactive Applications

Increasing geographical spreads of modern distributed interactive applications (DIAs) make distributed server deployment vital for combating network latency and improving the interactivity among participants. In this paper, we investigate the server provisioning problem that concerns where to place servers in DIAs. We formulate the server provisioning problem with an objective of reducing the network latency involved in the interaction between participants. We prove that the problem is NP-hard under any one of the following three scenarios that may be common in practice: (a) the network latency does not satisfy the triangle inequality; or (b) the choices of server locations in the network are restricted; or (c) the number of server locations to select is limited. Then, we propose an efficient greedy server provisioning heuristic, analyze its approximation ratio and give a tight example. Experiments using real Internet latency data show that our proposed algorithm significantly outperforms traditional k-median and k-center server placements.