Please use this identifier to cite or link to this item:
Title: Server provisioning for distributed interactive applications
Authors: Zheng, Han Ying
Keywords: DRNTU::Engineering::Computer science and engineering
Issue Date: 2014
Source: Zheng, H. Y. (2014). Server provisioning for distributed interactive applications. Doctoral thesis, Nanyang Technological University, Singapore.
Abstract: 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.
DOI: 10.32657/10356/61880
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Theses

Files in This Item:
File Description SizeFormat 
thesis-Zheng Hanying.pdf4.65 MBAdobe PDFThumbnail

Page view(s) 50

Updated on Feb 24, 2021

Download(s) 50

Updated on Feb 24, 2021

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.