IEICE TRANSACTIONS on Communications
Robust Optimization Model for Primary and Backup Capacity Allocations against Multiple Physical Machine Failures under Uncertain Demands in Cloud
Summary :
This paper proposes a robust optimization model for probabilistic protection under uncertain capacity demands to minimize the total required capacity against multiple simultaneous failures of physical machines. The proposed model determines both primary and backup virtual machine allocations simultaneously under the probabilistic protection guarantee. To express the uncertainty of capacity demands, we introduce an uncertainty set that considers the upper bound of the total demand and the upper and lower bounds of each demand. The robust optimization technique is applied to the optimization model to deal with two uncertainties: failure event and capacity demand. With this technique, the model is formulated as a mixed integer linear programming (MILP) problem. To solve larger sized problems, a simulated annealing (SA) heuristic is introduced. In SA, we obtain the capacity demands by solving maximum flow problems. Numerical results show that our proposed model reduces the total required capacity compared with the conventional model by determining both primary and backup virtual machine allocations simultaneously. We also compare the results of MILP, SA, and a baseline greedy algorithm. For a larger sized problem, we obtain approximate solutions in a practical time by using SA and the greedy algorithm.
- Publication
- IEICE TRANSACTIONS on Communications Vol.E106-B No.1 pp.18-34
- Publication Date
- 2023/01/01
- Publicized
- 2022/07/05
- Online ISSN
- 1745-1345
- DOI
- 10.1587/transcom.2022EBP3024
- Type of Manuscript
- PAPER
- Category
- Network
Authors
Mitsuki ITO
Kyoto University
Fujun HE
Kyoto University
Kento YOKOUCHI
Kyoto University
Eiji OKI
Kyoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Mitsuki ITO, Fujun HE, Kento YOKOUCHI, Eiji OKI, "Robust Optimization Model for Primary and Backup Capacity Allocations against Multiple Physical Machine Failures under Uncertain Demands in Cloud" in IEICE TRANSACTIONS on Communications,
vol. E106-B, no. 1, pp. 18-34, January 2023, doi: 10.1587/transcom.2022EBP3024.
Abstract: This paper proposes a robust optimization model for probabilistic protection under uncertain capacity demands to minimize the total required capacity against multiple simultaneous failures of physical machines. The proposed model determines both primary and backup virtual machine allocations simultaneously under the probabilistic protection guarantee. To express the uncertainty of capacity demands, we introduce an uncertainty set that considers the upper bound of the total demand and the upper and lower bounds of each demand. The robust optimization technique is applied to the optimization model to deal with two uncertainties: failure event and capacity demand. With this technique, the model is formulated as a mixed integer linear programming (MILP) problem. To solve larger sized problems, a simulated annealing (SA) heuristic is introduced. In SA, we obtain the capacity demands by solving maximum flow problems. Numerical results show that our proposed model reduces the total required capacity compared with the conventional model by determining both primary and backup virtual machine allocations simultaneously. We also compare the results of MILP, SA, and a baseline greedy algorithm. For a larger sized problem, we obtain approximate solutions in a practical time by using SA and the greedy algorithm.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2022EBP3024/_p
Copy
@ARTICLE{e106-b_1_18,
author={Mitsuki ITO, Fujun HE, Kento YOKOUCHI, Eiji OKI, },
journal={IEICE TRANSACTIONS on Communications},
title={Robust Optimization Model for Primary and Backup Capacity Allocations against Multiple Physical Machine Failures under Uncertain Demands in Cloud},
year={2023},
volume={E106-B},
number={1},
pages={18-34},
abstract={This paper proposes a robust optimization model for probabilistic protection under uncertain capacity demands to minimize the total required capacity against multiple simultaneous failures of physical machines. The proposed model determines both primary and backup virtual machine allocations simultaneously under the probabilistic protection guarantee. To express the uncertainty of capacity demands, we introduce an uncertainty set that considers the upper bound of the total demand and the upper and lower bounds of each demand. The robust optimization technique is applied to the optimization model to deal with two uncertainties: failure event and capacity demand. With this technique, the model is formulated as a mixed integer linear programming (MILP) problem. To solve larger sized problems, a simulated annealing (SA) heuristic is introduced. In SA, we obtain the capacity demands by solving maximum flow problems. Numerical results show that our proposed model reduces the total required capacity compared with the conventional model by determining both primary and backup virtual machine allocations simultaneously. We also compare the results of MILP, SA, and a baseline greedy algorithm. For a larger sized problem, we obtain approximate solutions in a practical time by using SA and the greedy algorithm.},
keywords={},
doi={10.1587/transcom.2022EBP3024},
ISSN={1745-1345},
month={January},}
Copy
TY - JOUR
TI - Robust Optimization Model for Primary and Backup Capacity Allocations against Multiple Physical Machine Failures under Uncertain Demands in Cloud
T2 - IEICE TRANSACTIONS on Communications
SP - 18
EP - 34
AU - Mitsuki ITO
AU - Fujun HE
AU - Kento YOKOUCHI
AU - Eiji OKI
PY - 2023
DO - 10.1587/transcom.2022EBP3024
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E106-B
IS - 1
JA - IEICE TRANSACTIONS on Communications
Y1 - January 2023
AB - This paper proposes a robust optimization model for probabilistic protection under uncertain capacity demands to minimize the total required capacity against multiple simultaneous failures of physical machines. The proposed model determines both primary and backup virtual machine allocations simultaneously under the probabilistic protection guarantee. To express the uncertainty of capacity demands, we introduce an uncertainty set that considers the upper bound of the total demand and the upper and lower bounds of each demand. The robust optimization technique is applied to the optimization model to deal with two uncertainties: failure event and capacity demand. With this technique, the model is formulated as a mixed integer linear programming (MILP) problem. To solve larger sized problems, a simulated annealing (SA) heuristic is introduced. In SA, we obtain the capacity demands by solving maximum flow problems. Numerical results show that our proposed model reduces the total required capacity compared with the conventional model by determining both primary and backup virtual machine allocations simultaneously. We also compare the results of MILP, SA, and a baseline greedy algorithm. For a larger sized problem, we obtain approximate solutions in a practical time by using SA and the greedy algorithm.
ER -
English
