Mechanism Design for Network Virtualization

Recently network virtualization has been proposed as a promising approach to thwart the current
ossification of the Internet by allowing multiple heterogeneous virtual networks (VN) to coexist on
a shared infrastructure which itself is controlled by self-interested infrastructure providers. A major
challenge in this respect is the VN embedding problem that deals with efficient mapping of virtual
nodes and virtual links onto the substrate network resources. Most previous research on this
problem has focused on designing heuristic and approximation algorithms for the VN embedding
problem. However a common aspect of these previous results is that they assume that the different
stake-holders in the network virtualization environment do not act in strategic ways.
In this paper, we propose to utilize mechanism design to address this issue. Mechanism design
is a branch of micro-economics that deals with protocols and algorithms for aligning the conflicting
preferences of self interested agents with the global objective of a central designer. Specifically we
show that the celebrated Vickrey Clarke Groves (VCG) mechanism can be used to find the optimal
cost minimizing embedding of a virtual network on top of a substrate network, where different parts
of the substrate network are owned by strategic agents. In the special case where each substrate
link is owned by a separate agent, we show the exact formulation of the VCG payment function and
develop simple algorithms for computing the payment functions based on shortest path algorithms.
We also discuss extensions of the basic model in terms of more realistic economic and network
models and also show how the VCG payment computation can be carried out in a distributed
fashion.