Client assignment for improving interactivity in distributed interactive applications

Distributed Interactive Applications (DIAs) are networked systems that allow multiple participants to interact with one another in real time. Wide spreads of client locations in larges-cale DIAs often require geographical distribution of servers to meet the latency requirements of the applications. In the distributed server architecture, how the clients are assigned to the servers directly affects the network latency involved in the interactions between clients. This paper focuses on the client assignment problem for enhancing the interactivity performance of DIAs. We formulate the problem as a combinational optimization problem on graphs and prove that it is NP-complete. Several heuristic algorithms are proposed for fast computation of good client assignments and are experimentally evaluated. The experimental results show that the proposed greedy algorithms perform close to the optimal assignment and generally outperform the Nearest-Assignment algorithm that assigns each client to its nearest server.