Abstract
Network virtualization allows one to build dynamic distributed systems in
which resources can be dynamically allocated at locations where they are most
useful. In order to fully exploit the benefits of this new technology,
protocols need to be devised which react efficiently to changes in the demand.
This paper argues that the field of online algorithms and competitive analysis
provides useful tools to deal with and reason about the uncertainty in the
request dynamics, and to design algorithms with provable performance
guarantees. As a case study, we describe a system (e.g., a gaming application)
where network virtualization is used to support thin client applications for
mobile devices to improve their QoS. By decoupling the service from the
underlying resource infrastructure, it can be migrated closer to the current
client locations while taking into account migration cost. This paper
identifies the major cost factors in such a system, and formalizes the
corresponding optimization problem. Both randomized and deterministic, gravity
center based online algorithms are presented which achieve a good tradeoff
between improved QoS and migration cost in the worst-case, both for service
migration within an infrastructure provider as well as for networks supporting
cross-provider migration. The paper reports on our simulation results and also
presents an explicit construction of an optimal offline algorithm which allows,
e.g., to evaluate the competitive ratio empirically.
