Combinatorial optimization has its roots in combinatorics, operations research, and theoretical computer science. A main motivation is that thousands of real-life problems can be formulated as abstract combinatorial optimization problems.
Resource optimization in cloud computing and the domain of Network Functions Virtualization (NFV), is required to reduce cost and improve infrastructure utilization. To ensure system efficiency, we need new algorithms that scale well and converge rapidly to optimal solutions.
In this manuscript, we address NP-Hard combinatorial optimization problems in cloud computing and NFV areas. We focus on two problems such as virtual resources repacking and critical resource placement in a cloud federation. Next to that, we consider virtualized network functions (VNFs) placement and chaining problems in a physical network substrate. We provide near-optimal placement of Virtualized Network Functions (VNFs) chains in order to deliver, on demand, virtual networks with dedicated network functions according to a tenant specified chaining of their VNFs.
Our contribution in these areas consist in providing novel, scalable and cost-efficient algorithms based on graph theory, b-Matching, matroids and the Perfect 2-Factor theory to optimally solve the above problems. All of our algorithms have low complexity confirmed by simulation and performance evaluation results.
Our manuscript aims also to stimulate research on combinatorial optimization applied to cloud computing and NFV areas that are changing the way infrastructures and networks are developed, deployed and put into production. Thus, we provide throughout this manuscript, some open problems attracting interest of researchers and industrial companies.