Postdoctoral Fellow, Waterloo University
Email
Abstract
A Cut-and-Solve Based Approach for the VNF Assignment Problem
Middleboxes have gained popularity due to the significant value-added services these network elements provide to traffic flows, in terms of enhanced performance and security. Policy-aware traffic flows usually need to traverse multiple middleboxes in a predefined order to satisfy their associated policy, also known as Service Function Chaining. Typically, Middleboxes run on specialised hardware, which make them highly inflexible to handle the unpredictable and fluctuating-nature of traffic, and contribute to significant capital and operational expenditures (Cap-ex and Op-ex) to provision, accommodate, and maintain them. Network Function Virtualization is a promising technology with the potential to tackle the aforementioned limitations of hardware middleboxes. Yet, NFV is still in its infancy, and there exists several technical challenges that need to be addressed, among which, the Virtual Network Function (VNF) assignment problem tops the list. The VNF assignment problem stems from the newly gained flexibility in instantiating VNFs (on-demand) anywhere in the network. Subsequently, network providers must decide on the optimal placement of VNF instances which maximises the number of admitted policy-aware traffic flows across their network. Existing work consists of Integer Linear Program (ILP) models, which are fairly unscalable, or heuristic-based approaches with no guarantee on the quality of the obtained solutions. This work proposes a novel Cut-and-Solve based approach to solve the VNF assignment problem. It consists of decomposing the problem into two sub-problems: a master and a sub-problem; and at every iteration constructive piercing cuts are introduced to the master to tighten its search space. Compared to ILP and a heuristic method, the Cut-and-Solve based approach achieves the optimal solution (as opposed to heuristic-based methods) 700 times faster than the ILP.
Bio
Dr. Sara Ayoubi received her MSc in 2012 from the Lebanese American University, and her Ph.D. in 2016 from the Concordia Institute for Information and Systems Engineering. Her Ph.D. thesis garnered her best dissertation award, and she was selected as Valedictorian for the joint faculties of Engineering, Computer Science, and Fine arts. She is currently a postdoctoral fellow at the Cheriton School of Computer Science at the University of Waterloo. Dr.Ayoubi is a co-founder of the Montreal Operations Research Student Chapter. Her research interests are in the fields of Operations Research, Networks, and Computer Systems.