Design and Analysis of Schedules for Virtual Network Migration
MetadataShow full item record
The Internet faces well-known challenges in realizing modifications to the core architecture. To help overcome these limitations, virtual networks run over physical networks and use Internet paths and protocols as essentially a link layer in the virtual network. Effective use of the underlying network requires intelligent placement of virtual networks so that underlying resources do not incur over-subscription. Additionally, because virtual networks may come and go over time, and underlying networks may experience their own dynamic changes, virtual networks may need to be migrated— re-mapped to the physical network during active operation— to maintain good performance. In this paper we consider the problem of scheduling the sequence of node moves that take a virtual network from an original placement to a new placement. We build on prior work that achieves migration of a single node with minimal disruption to develop a model for the migration cost and latency for a given network migration schedule. We then develop algorithms for determining a single-node-at-a-time sequence of moves to minimize migration cost, and further consider multiple node moves in parallel to minimize migration time and cost. Our algorithms are the first we are aware of to systematically address the virtual network migration scheduling problem.