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
Cet article propose deux algorithmes, à savoir l'algorithme Server-User Matching (SUM) et l'algorithme Extended Server-User Matching (ESUM), pour le problème d'allocation de serveurs distribués. Le problème d'allocation de serveur consiste à déterminer la correspondance entre les serveurs et les utilisateurs afin de minimiser le délai maximum, qui est le temps maximum nécessaire pour terminer la synchronisation des utilisateurs. Nous analysons la complexité du temps de calcul. Nous prouvons que l'algorithme SUM obtient les solutions optimales en temps polynomial pour le cas particulier où toutes les valeurs de délai serveur-serveur sont identiques et constantes. Nous fournissons les limites supérieure et inférieure lorsque l'algorithme SUM est appliqué au problème général d'allocation de serveur. Nous montrons que l'algorithme ESUM est un algorithme traitable à paramètres fixes qui peut atteindre la solution optimale pour le problème d'allocation de serveurs paramétré par le nombre de serveurs. Les résultats numériques montrent que le temps de calcul d'ESUM suit la complexité analysée tandis que l'algorithme ESUM surpasse l'approche de programmation linéaire en nombres entiers résolue par notre solveur examiné.
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.
Copier
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
Copier
@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},}
Copier
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 -