Heuristic Approach to Distributed Server Allocation with Preventive Start-Time Optimization against Server Failure

Souhei YANASE  Shuto MASUDA  Fujun HE  Akio KAWABATA  Eiji OKI  

Publication
IEICE TRANSACTIONS on Communications   Vol.E104-B    No.8    pp.942-950
Publication Date: 2021/08/01
Publicized: 2021/02/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2020EBP3145
Type of Manuscript: PAPER
Category: Network
Keyword: 
server allocation problem,  preventive start-time optimization,  server failure,  simulated annealing,  

Full Text: PDF>>
Buy this Article


Summary: 
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.