Efficient Approximation Algorithms for Server Allocation to Minimize Total Capacity under Server Failure

Real-time applications, such as ticket booking systems, video streaming systems, social networking services, and online games, are prevalent nowadays. Low latency between a user and a server is required in such applications. A distributed server approach is used instead of a single server one to achieve this. In such a situation, selecting which users connect to which servers significantly determines the system’s performance. There is a problem with the distributed server approach; each server may fail due to maintenance or breakdown. Single-server failure is more popular than multiple-server failure, so this paper focuses on single-server failure. In this paper, we assume that the capacity of each server is variable and minimize the total capacity of the servers. We also set the assumption that each user is allowed to connect exactly two servers. Under this assumption, we select each user’s main and backup servers. This paper proposes two approximation algorithms for a server allocation problem to minimize total capacity under server failure. We formulate the problem as an integer linear programming (ILP) problem. We show that the proposed algorithms have an approximation rate of$4/3$. One of them is an improved version of the other one. The algorithms are based on a 2-approximation algorithm of a vertex cover problem, in which taking a maximal matching is the key idea. Numerical results show that the proposed algorithms run significantly faster than ILP. The performance of the proposed algorithms depends on the topology; still, in randomly generated general networks, it increases the total capacity by 2.03% or less than ILP on average.