Algorithms for Distributed Server Allocation Problem

Sawa, Takaaki ✉; He, Fujun; Kawabata, Akio; Oki, Eiji

English Scientific Article (Journal Article)
Published: IEICE TRANSACTIONS ON COMMUNICATIONS 0916-8516 E103B (11) pp. 1341-1352 2020
  • SJR Scopus - Computer Networks and Communications: Q3
    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 ES UM 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.
    Citation styles: IEEEACMAPAChicagoHarvardCSLCopyPrint
    2021-04-16 09:48