  Network virtualization is an important concept to overcome the ossification
of today's Internet as it facilitates innovation also in the network core and
as it promises a more efficient use of the given resources and infrastructure.
Virtual networks (VNets) provide an abstraction of the physical network:
multiple VNets may cohabit the same physical network, but can be based on
completely different protocol stacks (also beyond IP). One of the main
challenges in network virtualization is the efficient admission control and
embedding of VNets. The demand for virtual networks (e.g., for a video
conference) can be hard to predict, and once the request is accepted, the
specification / QoS guarantees must be ensured throughout the VNet's lifetime.
This requires an admission control algorithm which only selects high-benefit
VNets in times of scarce resources, and an embedding algorithm which realizes
the VNet in such a way that the likelihood that future requests can be embedded
as well is maximized.
  This article describes a generic algorithm for the online VNet embedding
problem which does not rely on any knowledge of the future VNet requests but
whose performance is competitive to an optimal offline algorithm that has
complete knowledge of the request sequence in advance: the so-called
competitive ratio is, loosely speaking, logarithmic in the sum of the
resources. Our algorithm is generic in the sense that it supports multiple
traffic models, multiple routing models, and even allows for nonuniform
benefits and durations of VNet requests.

Networking and Internet Architecture