Server provisioning for distributed interactive applications

• Main Author: Zheng, Han Ying
• Other Authors: Tang Xueyan
• Format: Theses and Dissertations
• Language: English
• Published: 2014
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/61880
• Institution: Nanyang Technological University

Recent years have witnessed the enormous popularity of distributed interactive applications (DIAs), which allow participants that are distributed in the network to interact with each other simultaneously. The rapid growth of DIAs has raised stringent requirements on providing realistic sense of interaction between participants. To deliver high quality service and guarantee good experiences for participants, it is necessary for the DIA operators to deploy the servers hosting DIAs in a distributed manner. In such model, the information exchanged between clients is transmitted through servers. Servers communicate with each other to maintain consistent and cohesive application states. Since DIAs are latency sensitive, message transmission between clients should be performed in a timely manner. Otherwise, participants may experience inconsistent states and lags in response. However, due to the presence of inevitable network latencies between clients and servers as well as among servers, it is a critical challenge to guarantee the quality of interactions. To tackle the impact of network latencies on consistency, techniques like local-lag and dead reckoning have been animatedly explored. Unfortunately, these approaches could not actually reduce network latencies, and they may introduce even more delays or additional computational overheads to the network. For example, the local-lag approach maintains consistency by prolonging the waiting time of operation execution on the servers. In this way, the interactivity performance could not be improved due to the decrease in responsiveness. Although it is unrealistic to completely eliminate the network latency involved in the interaction, it is possible to reduce it by a smart combination of server locations. This is because the locations of servers influence not only the inter-server latencies, but also the latencies from clients to servers. Thus, the placement of servers is an important factor to the overall performance of distributed interactive applications. In this thesis, we study the problem of how to place servers appropriately on the network to host DIAs, with the goal of improving the interactivity performance of DIAs. We consider two different types of DIAs, i.e., discrete DIAs and continuous DIAs, which are differentiated by their ways of updating the application states. We formulate the server provisioning problems for both discrete DIAs and continuous DIAs by taking their specific Quality of Service requirements into account. We show that the two server provisioning problems are challenging by presenting their NP-hardness and non-approximability results under several conditions which may be prevalent in practice: (i) the network latencies do not satisfy the triangle inequality; or (ii) the locations where servers can be placed in the network are restricted; or (iii) the number of server locations to select is limited. For each problem, we present four server placement algorithms and theoretically analyze their approximation ratios in networks satisfying the triangle inequality as well as networks violating the triangle inequality. To the best of our knowledge, this is the first work that analyzes the asymptotic approximability of server placement algorithms with respect to the extent of triangle inequality violations. The performance of the algorithms is also studied by experimental evaluations using real Internet latency data. The results show that our proposed algorithms produce near-optimal server placements.