Dynamic aspects of network virtualization
Arne Ludwig · DepositOnce · 2016
The virtualization trend decouples services from the constraints of the underlying physical infrastructure. This decoupling facilitates more flexible and efficient resource allocations: the service can be realized at any place in the substrate network which fulfills the service specification requirements. This thesis studies such flexibilities in the context of virtual networks (VNets). A VNet describes a set of virtual nodes which are connected by virtual links; both nodes and links provide certain QoS or resource guarantees. The network virtualization paradigm envisions an Internet where customers can request arbitrary VNets from one or multiple substrate providers (e.g., an ISP or even indirectly via a broker). Indeed, network virtualization not only introduces flexibilities but also economical opportunities or even VNet markets: an aspect which has hardly been studied so far. We, in the first part of this thesis, investigate opportunities and challenges of such a possible market. We identify a fundamental tradeoff between specification details given by the customer and embedding efficiency on the provider side. In particular, we introduce a formal framework, called the Price of Specificity (PoS), to reason about and quantify this tradeoff. Subsequently, we study buying and pricing strategies for VNets: taking into account the multi-resource nature of VNets as well as possible discounts for larger quantities. We observe that the problem can be seen as multi-dimensional parking permit problem and present online algorithms as well as a competitive analysis, showing that our algorithms are asymptotically optimal. Network virtualization not only introduces challenges in terms of embedding and pricing. Especially long-lived VNets also need to be adapted and reconfigured over time (e.g., due to maintenance, new specifications, or load balancing). However, we observe that changing VNets adaptively in a consistent manner is non-trivial, as changes typically need to be communicated to and implemented at different and distributed components simultaneously. At the same time, ensuring consistency during updates is critical in virtualized environments where isolation needs to be provided between users and services sharing the same resources. Hence, in the second part of the thesis we study how to dynamically update VNets in a consistent way. In particular, we present a formal model and devise efficient algorithms to update SDN (Software Defined Networking)-based VNets such that security-critical functionality (like firewalls) are always traversed and loops avoided. We formally prove the correctness and efficiency of these algorithms, but also prove computational hardness results.