Robert Ricci, Chris Alfeld, Jay Lepreau
University of Utah Flux Group Technical Note 2002-05
December 2002
A revised version of this paper, published in SIGCOMM CCR V33(2), is available here. Please read and cite the published CCR 2003 paper in preference to this report.
Flux Research Group
School of Computing, University of Utah
50 S. Central Campus Drive Rm. 3190
Salt Lake City, Utah 84112-9205 USA
Network experimentation of many types require the ability to map virtual resources requested by an experimenter onto available physical resources. These resources include hosts, switches, and the links that connect them. Experimenter requests, such as nodes with special hardware or software, must be satisfied, and bottleneck links and other scarce resources in the physical topology must be conserved. In the face of these constraints, this mapping becomes an NP-hard problem. Yet, in order to prevent mapping time from becoming a serious hinderance to such experimentation, this process cannot consume an excessive amount of time.
In this paper, we explore this problem, which we call the "network testbed mapping problem." We describe the interesting challenges that characterize this problem, and explore its application to other spaces, such as distributed simulation. We present the design, implementation, and evaluation of a solver for this problem, which is currently in use on the Netbed network testbed. It builds on simulated annealing to find very good solutions in a few seconds for our historical workload, and scales gracefully on large well-connected synthetic topologies.
Full paper: