The Virtual Network Scheduling Problem for Heterogeneous Network Emulation Testbeds

Authors

Charlie Wisemen, Washington University in St Louis
Jonathan Turner, Washington University in St LouisFollow

Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2009

Filename

wucse-2009-68.pdf

Technical Report Number

wucse-2009-68

Abstract

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7M32T10

Recommended Citation

Wisemen, Charlie and Turner, Jonathan, "The Virtual Network Scheduling Problem for Heterogeneous Network Emulation Testbeds" Report Number: wucse-2009-68 (2009). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/21