The search functionality is under construction.

The search functionality is under construction.

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

Takaaki SAWA

Kyoto University

Fujun HE

Kyoto University

Akio KAWABATA

NTT Network Technology Laboratories

Eiji OKI

Kyoto University

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.

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 -