Algorithms for Distributed Server Allocation Problem

• SAWA Takaaki

  Graduate School of Informatics, Kyoto University

• HE Fujun

  Graduate School of Informatics, Kyoto University

• KAWABATA Akio

  NTT Network Technology Laboratories

• OKI Eiji

  Graduate School of Informatics, Kyoto University

抄録

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.

収録刊行物

• IEICE Transactions on Communications

  IEICE Transactions on Communications E103.B (11), 1341-1352, 2020-11-01

  一般社団法人 電子情報通信学会

キーワード

• distributed processing
• server allocation problem
• polynomial-time algorithm

詳細情報

• CRID: 1391130851443764480
• NII論文ID: 130007933919
• DOI: 10.1587/transcom.2020ebp3006
• ISSN: 17451345
• ISSN: 09168516
• Web Site: https://www.jstage.jst.go.jp/article/transcom/E103.B/11/E103.B_2020EBP3006/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可