Client assignment problems for distributed interactive computing

• Main Author: Zhang, Lu
• Other Authors: Tang Xueyan
• Format: Theses and Dissertations
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Computer science and engineering::Computer systems organization::Computer-communication networks
• Online Access: https://hdl.handle.net/10356/51873
• Institution: Nanyang Technological University

The steady growth in broadband Internet accesses and PC penetration is leading to a shift in emphasis from individual computers to distributed interactive computing that allows multiple participants at different locations to interact with each other in real time. Recent years have witnessed rapid development of Distributed Interactive Applications (DIAs) in many areas such as interactive digital media and entertainment, distributed interactive simulation, and collaborative computer-aided design and engineering. Interactivity is a primary performance measure of DIAs owing to their human-in-the-loop nature. To support graceful interactions, it is required that when a participant of the DIA performs an operation, other participants are able to see the effect of the operation quickly. Network latency is a major barrier to propagating and reflecting the effects of operations timely. Wide geographical spreads of participants in large-scale DIAs necessitate distributed deployment of servers to combat network latency and achieve high interactivity. In a distributed server architecture, the interactivity performance depends not only on client-to-server latencies but also interserver latencies. Meanwhile, the consistency and fairness requirements of DIAs, which are important to providing pleasant user experiences, may introduce artificial synchronization delays in the interaction that can also influence the interactivity performance. All these factors are directly affected by how the clients are assigned to the servers. In this thesis, we investigate how to assign clients to appropriate servers in an effective and efficient manner for enhancing the interactivity performance of DIAs. Based on whether the application's state changes due to the passing of time, DIAs can be classified into discrete DIAs and continuous DIAs. We study the client assignment problems for both types of DIAs. We first mathematically model the interactivity performance of these two types of DIAs, taking the consistency and fairness requirements into consideration. Based on the analysis, we formulate the client assignment problems of discrete and continuous DIAs as combinatorial optimization problems. We show that both client assignment problems are NP-complete via polynomial time reductions from existing NP-complete problems. Then, a number of heuristics, including both centralized and distributed algorithms, are proposed for fast computation of good client assignments to each problem. The approximation ratios of these algorithms are theoretically analyzed and examples are given to show the tightness of these ratios. The performance of these algorithms is also experimentally evaluated using real Internet latency data. The results show that our proposed greedy and modification-based algorithms normally perform close to the optimal assignments, and they significantly outperform the intuitive Nearest-Server Assignment algorithm that assigns each client to its nearest server. For the client assignment problem of discrete DIAs, we further show that there exists a polynomial-time optimal solution for the special case of tree network topologies. An efficient algorithm is developed to compute the optimal client assignment.