Cost-Efficient Request Dispatching in Geo-distributed Cloud Gaming Infrastructure

Cloud gaming is a recent approach to gaming, where processing for the games occurs on well-equipped servers within the cloud and a video stream is returned to the user, meaning users can play high-end games on devices that lack computational power. Different games require different amounts of computational resources and computation times. It would be desirable to efficiently pack a number of servers with multiple games at once, however this is complicated within a geo-distributed cloud system as we must consider that not every data center can fulfil every game request due to latency requirements. Within this work, we present shadow routing algorithms to distribute game requests to cloud data centers and also to pack the servers within the data centers with these game requests. These algorithms are designed to operate in order to minimize total cost from server hire and bandwidth usage, and we prove their performance is asymptotically close to optimal. An experiment using realistic arrival rates is given, and the results verify our theory within a realistic context. Also shown using proof and experimentation is that the algorithms can adapt themselves to periodic changes as demand raises and falls while remaining close to the optimal, which is a particular weak point of other schemes.