Rethinking Virtual Network Embedding: Substrate Support for Path Splitting and Migration

Abstract:

Network virtualization is a powerful way to run multiple architectures or
experiments simultaneously on a shared infrastructure. However, making
efficient use of the underlying resources requires effective techniques for
\emph{virtual network embedding}---mapping each virtual network to specific
nodes and links in the substrate network. Since the general embedding
problem is computationally intractable, past research has focused on two
main approaches: (i) significantly restricting the problem space to allow
efficient solutions or (ii) proposing heuristic algorithms that do not use
the substrate resources efficiently. In this paper, we advocate a different
approach: rethinking the design of the substrate network to enable simpler
embedding algorithms and more efficient use of resources, without
restricting the problem space. First, we allow the substrate network to
split a virtual link over \emph{multiple} substrate paths. Second, we employ
\emph{path migration} to periodically re-optimize the utilization of the
substrate network to help accommodate new requests. In addition, we run
node-mapping algorithms that are \emph{customized} to common classes of
virtual-network topologies. Our simulation experiments show that path
splitting, path migration, and customized embedding algorithms enable a
substrate network to satisfy a much larger mix of virtual-network requests
in practice.