Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Greedy Algorithms for the Temporal Bin Packing Problem with Failure Domain. / Akentyev, Vsevolod; Davydov, Ivan.
Communications in Computer and Information Science. Springer Science and Business Media Deutschland GmbH, 2024. p. 143-160 10 (Communications in Computer and Information Science; Vol. 2239 CCIS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Greedy Algorithms for the Temporal Bin Packing Problem with Failure Domain
AU - Akentyev, Vsevolod
AU - Davydov, Ivan
N1 - Conference code: 23
PY - 2024/12/20
Y1 - 2024/12/20
N2 - The main directions of development in cloud computing systems are aimed at increasing the efficiency of using server resources and the reliability of virtual machines (VMs), as well as reducing operating costs. A common goal in such systems is to minimize the number of servers required to maintain a given set of VMs, satisfying server capacity constraints. This goal practically leads to the well-known temporal bin packing problem. This study explores a generalization of this problem by introducing a concept of fault domains, where specific sets of VMs must operate in independent domain zones. For this NP-hard problem, we developed a heuristic for calculating the upper bound, based on the First Fit algorithm. Using the structural properties of the new constraints, we propose several efficient VM sequencing algorithms for the First Fit algorithm. Preliminary computational experiments on a publicly available benchmark library showed that the proposed heuristic method is capable of efficiently solving both small and large scale problems in a short time.
AB - The main directions of development in cloud computing systems are aimed at increasing the efficiency of using server resources and the reliability of virtual machines (VMs), as well as reducing operating costs. A common goal in such systems is to minimize the number of servers required to maintain a given set of VMs, satisfying server capacity constraints. This goal practically leads to the well-known temporal bin packing problem. This study explores a generalization of this problem by introducing a concept of fault domains, where specific sets of VMs must operate in independent domain zones. For this NP-hard problem, we developed a heuristic for calculating the upper bound, based on the First Fit algorithm. Using the structural properties of the new constraints, we propose several efficient VM sequencing algorithms for the First Fit algorithm. Preliminary computational experiments on a publicly available benchmark library showed that the proposed heuristic method is capable of efficiently solving both small and large scale problems in a short time.
KW - NUMA architecture
KW - cloud computing
KW - failure domain
KW - temporal bin packing
UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85214195325&origin=inward&txGid=796d59421aa46c90953693bfdef0778a
UR - https://www.mendeley.com/catalogue/1528d512-5c94-3311-a4a1-ea0c5c44e37b/
U2 - 10.1007/978-3-031-73365-9_10
DO - 10.1007/978-3-031-73365-9_10
M3 - Conference contribution
SN - 978-303173364-2
T3 - Communications in Computer and Information Science
SP - 143
EP - 160
BT - Communications in Computer and Information Science
PB - Springer Science and Business Media Deutschland GmbH
T2 - 23rd International Conference on Mathematical Optimization Theory and Operations Research
Y2 - 30 June 2024 through 6 July 2024
ER -
ID: 61412804