On the game server network selection with delay and delay variation constraints

摘要

Recent advances in multimedia software and hardware technologies and the availability of high-speed Internet service have been instrumental for growth in the online gaming industry. Multiple servers distributed across the network are commonly used to provide the desired quality-of-service (QoS) for the network game in order to achieve a higher quality-of-experience (QoE) to the players (clients). Each player in this distributed multi-player gaming environment connects to a particular server and it distributes each of the actions to all other players through the servers they are connected to. We imagine the server network to be an overlay network, wherein the latency on a link between two servers is the latency of the Internet path connecting them. We assume that we are given an overlay network of servers with link latencies and a set of players each with a different latency to each of the servers. Now our goal is to develop algorithms that perform the following actions in such a way that delay related QoS constraints are satisfied: (a) choose a subnetwork of the server network (server network selection) and (b) assign each player to a server in the subnetwork (client-assignment). More specifically, the QoS constraints that we address in this paper are a bound on the maximum delay in propagating a player's move to all other players (delay bound) and a bound on the maximum difference in the arrival times of a player's move at all other players (delay-variation bound). We have provided polynomial-time heuristics to determine a minimal cardinality server network and the corresponding client-assignment that satisfy both delay bound and that minimize delay-variation, if such a solution exists. We have considered cases in which the server network follows two communication models: client-server (CS) and peer-to-peer (P2P). Our extensive empirical studies indicate that our heuristic uses significantly less run-time in achieving the tightest delay variation for a given end---to-end delay bound while choosing a minimal number of servers.