The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
본 논문에서는 분산 서버 할당 문제에 대해 SUM(Server-User Matching) 알고리즘과 ESUM(Extended Server-User Matching) 알고리즘의 두 가지 알고리즘을 제안합니다. 서버 할당 문제는 서버와 사용자 간의 매칭을 결정하여 사용자 동기화를 완료하는 데 걸리는 최대 시간인 최대 지연을 최소화하는 것입니다. 계산 시간 복잡도를 분석합니다. 우리는 SUM 알고리즘이 모든 서버 간 지연 값이 동일하고 일정한 특수한 경우에 대해 다항식 시간에서 최적의 솔루션을 얻음을 증명합니다. 일반적인 서버 할당 문제에 SUM 알고리즘을 적용할 때 상한과 하한을 제공합니다. 우리는 ESUM 알고리즘이 서버 수에 따라 매개변수화된 서버 할당 문제에 대한 최적의 솔루션을 얻을 수 있는 고정 매개변수 다루기 쉬운 알고리즘임을 보여줍니다. 수치 결과는 ESUM의 계산 시간이 분석된 복잡성을 따르는 반면 ESUM 알고리즘은 조사된 솔버로 해결된 정수 선형 계획법의 접근 방식보다 성능이 우수하다는 것을 보여줍니다.
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.
부
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
부
@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},}
부
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 -