Multi-Capacity Bin Packing with Dependent Items and its Application to the Packing of Brokered Workloads in Virtualized Environments

Focusing on offering predictability guarantees to data-intensive applications, we define a sub-problem of the MCBP-DI problem, namely the Network-Constrained Packing (NCP) problem, in which the items to be packed form a connected component, and the resources consumed by any subset of these items are equivalent to the cost of the cut of that subset from the component. Our definition of the NCP problem is presented as part of our proposed cloud brokerage framework, in which the optimal mapping of brokered resources to applications is decided with guaranteed performance predictability. We prove that NCP is NP-hard, and we define two special instances of the problem, for which exact solutions can be found efficiently. We develop a greedy heuristic to solve the general instance of the NCP problem, and we evaluate its efficiency using simulations on various application workloads, and network models.