Multi-capacity bin packing with dependent items and its application to the packing of brokered workloads in virtualized environments
Files
Accepted manuscript
Date
2017-07-01
Authors
Bassem, Christine
Bestavros, Azer
Version
OA Version
Citation
Christine Bassem, Azer Bestavros. 2017. "Multi-Capacity Bin Packing with Dependent Items and its Application to the Packing of Brokered Workloads in Virtualized Environments." FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, Volume 72, pp. 129 - 144 (16).
Abstract
Providing resource allocation with performance
predictability guarantees is increasingly important in cloud
platforms, especially for data-intensive applications, in which
performance depends greatly on the available rates of data
transfer between the various computing/storage hosts underlying
the virtualized resources assigned to the application. Existing
resource allocation solutions either assume that applications
manage their data transfer between their virtualized resources, or
that cloud providers manage their internal networking resources.
With the increased prevalence of brokerage services in cloud
platforms, there is a need for resource allocation solutions that
provides predictability guarantees in settings, in which neither
application scheduling nor cloud provider resources can be
managed/controlled by the broker. This paper addresses this
problem, as we define the Network-Constrained Packing (NCP)
problem of finding the optimal mapping of brokered resources
to applications 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.