IEICE TRANSACTIONS on Communications
Algorithms for Distributed Server Allocation Problem
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.
- 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
Authors
Takaaki SAWA
Kyoto University
Fujun HE
Kyoto University
Akio KAWABATA
NTT Network Technology Laboratories
Eiji OKI
Kyoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takaaki SAWA, Fujun HE, Akio KAWABATA, Eiji OKI, "Algorithms for Distributed Server Allocation Problem" in IEICE TRANSACTIONS on Communications,
vol. E103-B, no. 11, pp. 1341-1352, November 2020, doi: 10.1587/transcom.2020EBP3006.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2020EBP3006/_p
Copy
@ARTICLE{e103-b_11_1341,
author={Takaaki SAWA, Fujun HE, Akio KAWABATA, Eiji OKI, },
journal={IEICE TRANSACTIONS on Communications},
title={Algorithms for Distributed Server Allocation Problem},
year={2020},
volume={E103-B},
number={11},
pages={1341-1352},
abstract={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.},
keywords={},
doi={10.1587/transcom.2020EBP3006},
ISSN={1745-1345},
month={November},}
Copy
TY - JOUR
TI - Algorithms for Distributed Server Allocation Problem
T2 - IEICE TRANSACTIONS on Communications
SP - 1341
EP - 1352
AU - Takaaki SAWA
AU - Fujun HE
AU - Akio KAWABATA
AU - Eiji OKI
PY - 2020
DO - 10.1587/transcom.2020EBP3006
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E103-B
IS - 11
JA - IEICE TRANSACTIONS on Communications
Y1 - November 2020
AB - 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.
ER -
English
