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 un modèle d'optimisation robuste pour la protection probabiliste sous des demandes de capacité incertaines afin de minimiser la capacité totale requise contre de multiples pannes simultanées de machines physiques. Le modèle proposé détermine simultanément les allocations de machines virtuelles principales et de sauvegarde sous la garantie de protection probabiliste. Pour exprimer l'incertitude des demandes de capacité, nous introduisons un ensemble d'incertitudes qui prend en compte la limite supérieure de la demande totale ainsi que les limites supérieure et inférieure de chaque demande. La technique d'optimisation robuste est appliquée au modèle d'optimisation pour traiter deux incertitudes : l'événement de défaillance et la demande de capacité. Avec cette technique, le modèle est formulé comme un problème de programmation linéaire en nombres entiers mixtes (MILP). Pour résoudre des problèmes de plus grande taille, une heuristique de recuit simulé (SA) est introduite. En SA, nous obtenons les demandes de capacité en résolvant des problèmes de débit maximum. Les résultats numériques montrent que notre modèle proposé réduit la capacité totale requise par rapport au modèle conventionnel en déterminant simultanément les allocations de machines virtuelles principales et de sauvegarde. Nous comparons également les résultats de MILP, SA et d'un algorithme glouton de base. Pour un problème de plus grande taille, nous obtenons des solutions approchées en un temps pratique en utilisant SA et l'algorithme glouton.
Mitsuki ITO
Kyoto University
Fujun HE
Kyoto University
Kento YOKOUCHI
Kyoto University
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
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
Copier
@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},}
Copier
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 -