Algorithms for Distributed Server Allocation Problem

Takaaki SAWA
Fujun HE
Akio KAWABATA
Eiji OKI

Publication
IEICE TRANSACTIONS on Communications   Vol.E103-B    No.11    pp.1341-1352
Publication Date: 2020/11/01
Publicized: 2020/05/08
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2020EBP3006
Type of Manuscript: PAPER
Category: Network
Keyword: 
distributed processing,  server allocation problem,  polynomial-time algorithm,  

Full Text: PDF(1.7MB)>>
Buy this Article



Summary: 
This paper proposes two algorithms, namely Server-User Matching (SUM) algorithm and Extended Server-User Matching (ESUM) algorithm, for the distributed server allocation problem. The server allocation problem is to determine the matching between servers and users to minimize the maximum delay, which is the maximum time to complete user synchronization. We analyze the computational time complexity. We prove that the SUM algorithm obtains the optimal solutions in polynomial time for the special case that all server-server delay values are the same and constant. We provide the upper and lower bounds when the SUM algorithm is applied to the general server allocation problem. We show that the ESUM algorithm is a fixed-parameter tractable algorithm that can attain the optimal solution for the server allocation problem parameterized by the number of servers. Numerical results show that the computation time of ESUM follows the analyzed complexity while the ESUM algorithm outperforms the approach of integer linear programming solved by our examined solver.