The Virtual Network Scheduling Problem for Heterogeneous Network Emulation Testbeds
Charlie Wisemen · Open Scholarship Institutional Repository (Washington University in St. Louis) · 2009
Network testbeds such as Emulab and the Open Network Laboratory use virtualization to enable users to define end user virtual networks within a shared substrate. This involves mapping users' virtual network nodes onto distinct substrate components and mapping virtual network links onto substrate paths. The mappings guarantee that different users' activities can not interfere with one another. The problem of mapping virtual networks onto a shared substrate is a variant of the general graph embedding problem, long known to be NP-hard. In this paper, we focus on a more general version of the problem that supports advance scheduling of virtual network mappings. We experimentally study the performance of heuristic testbed schedulers in the context of the Open Network Laboratory. Our algorithms incorporate Mixed Integer Programs to optimally solve key subproblems, are fast enough to respond to reservation requests in under one second, and rarely reject requests needlessly.