This paper presents a distributed server allocation model with preventive start-time optimization against a single server failure. The presented model preventively determines the assignment of servers to users under each failure pattern to minimize the largest maximum delay among all failure patterns. We formulate the proposed model as an integer linear programming (ILP) problem. We prove the NP-completeness of the considered problem. As the number of users and that of servers increase, the size of ILP problem increases; the computation time to solve the ILP problem becomes excessively large. We develop a heuristic approach that applies simulated annealing and the ILP approach in a hybrid manner to obtain the solution. Numerical results reveal that the developed heuristic approach reduces the computation time by 26% compared to the ILP approach while increasing the largest maximum delay by just 3.4% in average. It reduces the largest maximum delay compared with the start-time optimization model; it avoids the instability caused by the unnecessary disconnection permitted by the run-time optimization model.
Souhei YANASE
Kyoto University
Shuto MASUDA
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
Souhei YANASE, Shuto MASUDA, Fujun HE, Akio KAWABATA, Eiji OKI, "Heuristic Approach to Distributed Server Allocation with Preventive Start-Time Optimization against Server Failure" in IEICE TRANSACTIONS on Communications,
vol. E104-B, no. 8, pp. 942-950, August 2021, doi: 10.1587/transcom.2020EBP3145.
Abstract: This paper presents a distributed server allocation model with preventive start-time optimization against a single server failure. The presented model preventively determines the assignment of servers to users under each failure pattern to minimize the largest maximum delay among all failure patterns. We formulate the proposed model as an integer linear programming (ILP) problem. We prove the NP-completeness of the considered problem. As the number of users and that of servers increase, the size of ILP problem increases; the computation time to solve the ILP problem becomes excessively large. We develop a heuristic approach that applies simulated annealing and the ILP approach in a hybrid manner to obtain the solution. Numerical results reveal that the developed heuristic approach reduces the computation time by 26% compared to the ILP approach while increasing the largest maximum delay by just 3.4% in average. It reduces the largest maximum delay compared with the start-time optimization model; it avoids the instability caused by the unnecessary disconnection permitted by the run-time optimization model.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2020EBP3145/_p
Copy
@ARTICLE{e104-b_8_942,
author={Souhei YANASE, Shuto MASUDA, Fujun HE, Akio KAWABATA, Eiji OKI, },
journal={IEICE TRANSACTIONS on Communications},
title={Heuristic Approach to Distributed Server Allocation with Preventive Start-Time Optimization against Server Failure},
year={2021},
volume={E104-B},
number={8},
pages={942-950},
abstract={This paper presents a distributed server allocation model with preventive start-time optimization against a single server failure. The presented model preventively determines the assignment of servers to users under each failure pattern to minimize the largest maximum delay among all failure patterns. We formulate the proposed model as an integer linear programming (ILP) problem. We prove the NP-completeness of the considered problem. As the number of users and that of servers increase, the size of ILP problem increases; the computation time to solve the ILP problem becomes excessively large. We develop a heuristic approach that applies simulated annealing and the ILP approach in a hybrid manner to obtain the solution. Numerical results reveal that the developed heuristic approach reduces the computation time by 26% compared to the ILP approach while increasing the largest maximum delay by just 3.4% in average. It reduces the largest maximum delay compared with the start-time optimization model; it avoids the instability caused by the unnecessary disconnection permitted by the run-time optimization model.},
keywords={},
doi={10.1587/transcom.2020EBP3145},
ISSN={1745-1345},
month={August},}
Copy
TY - JOUR
TI - Heuristic Approach to Distributed Server Allocation with Preventive Start-Time Optimization against Server Failure
T2 - IEICE TRANSACTIONS on Communications
SP - 942
EP - 950
AU - Souhei YANASE
AU - Shuto MASUDA
AU - Fujun HE
AU - Akio KAWABATA
AU - Eiji OKI
PY - 2021
DO - 10.1587/transcom.2020EBP3145
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E104-B
IS - 8
JA - IEICE TRANSACTIONS on Communications
Y1 - August 2021
AB - This paper presents a distributed server allocation model with preventive start-time optimization against a single server failure. The presented model preventively determines the assignment of servers to users under each failure pattern to minimize the largest maximum delay among all failure patterns. We formulate the proposed model as an integer linear programming (ILP) problem. We prove the NP-completeness of the considered problem. As the number of users and that of servers increase, the size of ILP problem increases; the computation time to solve the ILP problem becomes excessively large. We develop a heuristic approach that applies simulated annealing and the ILP approach in a hybrid manner to obtain the solution. Numerical results reveal that the developed heuristic approach reduces the computation time by 26% compared to the ILP approach while increasing the largest maximum delay by just 3.4% in average. It reduces the largest maximum delay compared with the start-time optimization model; it avoids the instability caused by the unnecessary disconnection permitted by the run-time optimization model.
ER -