A deep dive into embedding algorithms for secure network virtualization

Tese de mestrado, Segurança Informática, Universidade de Lisboa, Faculdade de Ciências, 2018Network virtualization is a technique that aims to improve resource utilization in data- center and cloud environments by enabling multiple virtual networks to run over the same physical infrastructure. Yet, since traditional network infrastructures have limitations, namely the coupling of control and data planes, network virtualization was not possible until recently. The emergence of Software Defined Networks, a new paradigm that de- couples control and data planes, has enabled network virtualization. By using a logically centralized controller with a global view of the network architecture, it became possible to decouple the virtual networks from the physical infrastructure. Of the various challenges in network virtualization, this work focuses on efficient resource allocation, which affects scalability, resource utilization, and profitability for the infrastructure provider. In order to maximize profitability, resource utilization has to be maximized. Towards that goal, virtual resources have to be mapped to the substrate network in an optimal way. This problem is known as Virtual Network Embedding. There are several approaches for solving VNE: both optimal and heuristics. As optimal solutions are only feasible for small instances of the problem, heuristic or meta-heuristic approaches are needed for large scale, practical networks. Most VNE solutions only consider capacity requirements, like bandwidth or CPU, and neglect other factors, such as security and availability. In this dissertation we provide two major contributions. The first is a comparative study of several heuristics for VNE that consider security and dependability requirements. The idea is to compare these solutions in terms of acceptance ratio (that translates into revenue) and embedding cost. The second contribution is a reconfiguration mechanism proposed to deal with the fragmentation caused by the constant arrival and departure of virtual networks. The main goal of the reconfiguration mechanism is to reduce the average substrate path length between virtual nodes