Abstract: We consider an NP-hard temporal bin packing problem that arises in cloudcomputing. Each item represents a virtual machine, de ned by its creation anddeletion timestamps, as well as a vector of resource allocation requests. Virtualmachines are divided into two categories: large and small. Each container representsa server consisting of multiple NUMA nodes. A small virtual machine can be fullyplaced on one node, while a large virtual machine is split into two identical halvesthat are placed on di erent nodes. Servers are located in xed-size racks. Somevirtual machines are grouped together, and each group is further divided intosubgroups called partitions. Virtual machines from di erent partitions withinthe same group con ict with each other, meaning they cannot be co-located onservers from the same rack at the same time. This constraint is crucial for ensuringsystem fault tolerance. Our goal is to e ciently pack all virtual machines intoa minimum number of racks. To solve the problem, we use a column generationmethod to create packing templates for virtual machines, which are then distributedacross servers. The templates are adapted to take into account con icts relatedto partition existence. The e ectiveness of the approach has been tested on anextensive open benchmark [1], which contains up to 70,000 virtual machines

Cite: Ratushnyi A.V. , Panin A.A. , Brazhnikov E.A.
Template-based approach to dynamic bin packing with placement groups
In compilation Proceedings of the 8th International School-Seminar on Nonlinear Analysis and Extremal Problems (NLA-2024). – ISDCT SB RAS., 2024. – C.223-224. – ISBN 978-5-6041814-5-4. РИНЦ

Dates:

Published print:	Sep 1, 2024
Published online:	Sep 1, 2024

Identifiers:

Elibrary:

68637476

Citing: Пока нет цитирований