Robert Ricci, Chris Alfeld, Jay Lepreau
ricci@cs.utah.edu, alfeld@math.cs.wisc.edu, lepreau@cs.utah.edu
April 2003
Flux Research Group
School of Computing, University of Utah
50 S. Central Campus Drive Rm. 3190
Salt Lake City, Utah 84112-9205 USA
Network experiments of many types, especially emulation, require the ability to map virtual resources requested by an experimenter onto available physical resources. These resources include hosts, routers, 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 should be conserved when physical resources are shared. In the face of these constraints, this mapping becomes an NP-hard problem. Yet, in order to prevent mapping time from becoming a serious hindrance to 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 it, and explore its application to emulation and other spaces, such as distributed simulation. We present the design, implementation, and evaluation of a solver for this problem, which is in production use on the Netbed shared network testbed. Our solver 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 appears in SIGCOMM Computer Communications Review, Volume 33 Number 2, pages 65-81, April 2003.
Slides from a talk on assign given by Robert Ricci at INFORMS '05: