The Price of Specificity in the Age of Network Virtualization
The virtualization trend in today's Internet decouples services from the constraints of the underlying physical infrastructure. This decoupling has the potential to facilitate 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 paper studies such flexibilities in the context of Virtual Network (VNet) embeddings. The network virtualization paradigm envisions an Internet where users can request arbitrary VNets from a substrate provider (e.g., an ISP). A VNet describes a set of virtual nodes which are connected by virtual links; both nodes and links provide certain resource guarantees.