Placement and Scheduling of Network Traffic on Virtual Network Functions

Hardware MiddleBoxes represent a vital part in today's networks. Despite their important roles, they are accompanied by several problems, namely, their lack of flexibility, high capital and operational expenditures, and power consumption. Network Function Virtualization is one promising solution to address these problems. This trend replaces the MiddleBoxes by software-based entities. Indeed, these Virtual Network Functions promise to alleviate the numerous disadvantages brought by their hardware counterparts. One of these most serious issues is the steadily increasing power consumption. Studies suggest that the Virtual Network Functions will reduce the electricity costs needed to turn on and operate the hardware functions. In order to further optimize the power consumption of the network, an efficient framework, capable of placing and scheduling traffic on these VNFs, is needed. Such a framework allows to optimally map and schedule the flows to be serviced, and place the unused servers in energy saving modes. In this thesis, we assume VNFs are already placed on physical machines. We consider traffic flows with deadlines. We aim at assigning and scheduling flows to VNFs in the most energy efficient manner. We formulate this problem mathematically and, owing to its complexity, present an efficient algorithmic method for solving the problem. We compare our heuristic with two other approaches, one of which aims to minimize the makespan, and the other to minimize number of servers used. We show that our heuristic combines the advantages of both approaches and generates better results by consuming up to 31.3% and 46.1% energy less than other two approaches respectively. Further, we extend the existing work in the literature, and solve the problem of placement of traffic flows on VNFs while taking into account the transmission delay between pairs of VNFs, and the routing of the virtual links on the underlying physical network