Robert Ricci
Abstract
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 applications 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.
- E. H. L. Aarts and J. Korst. Simulated Annealing and Boltzmann Machines. John Wiley & Sons, 1989. Google Scholar
Digital Library
- D. G. Andersen. Theoretical Approaches To Node Assignment, December 2002. Unpublished Manuscript. http://nms.lcs.mit.edu/papers/andersen-assign.p.s.Google Scholar
- Boost C++ Libraries. http://www.boost.org/.Google Scholar
- A. Boukerche and C. Tropper. A Static Partitioning and Mapping Algorithm for Conservative Parallel Simulations. In Proc. of the Eighth Workshop on Parallel and Distributed Simulation. ACM Press, 1994. Google ScholarDigital Library
- L. Breslau, D. Estrin, K. Fall, S. Floyd, J. Heidemann, A. Helmy, P. Huang, S. McCanne, K. Varadhan, Y. Xu, and H. Yu. Advances in Network Simulation. IEEE Computer, 33(5):59--67, May 2000. (An expanded version is available as USC CSD TR 99-702b.). Google ScholarDigital Library
- K. Fall. Network Emulation in the Vint/NS Simulator. In Proc. of the 44th IEEE Symposium on Computers and Communications, 1999. Google ScholarDigital Library
- D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989 Google ScholarDigital Library
- B. Hendrickson and R. Leland. An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations. SIAM Journal on Scientific Computing, 16(2):452--469, 1995. Google ScholarDigital Library
- E. Johnson and A. Kunze. IXP1200 Programming. Intel Press, 2002. Google ScholarDigital Library
- G. Karypis and V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing, 20(1):359--392, 1998. Google ScholarDigital Library
- S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):671--680, 1983.Google ScholarCross Ref
- A. Kumar, R. Rastogi, A. Silberschatz, and B. Yener. Algorithms for Provisioning Virtual Private Networks in the Hose Model. In Proc. of SIGCOMM 2001. ACM Press, August 2001. Google ScholarDigital Library
- O. C. Martin and S. W. Otto. Combining Simulated Annealing with Local Search Heuristics. Annals of Operations Research, 63:57--75, 1996.Google ScholarCross Ref
- A. Medina, A. Lakhina, I. Matta, and J. Byers. BRITE: An Approach to Universal Topology Generation. In Proc. of MASCOTS 2001, Cincinnati, Ohio, August 2001. Google ScholarDigital Library
- B. Monien and H. Sudborough. Embedding One Interconnection Network in Another, pages 257--282. Springer-Verlag/Wien, 1990. Computing Supplementum 7: Computational Graph Theory.Google Scholar
- L. Peterson, T. Anderson, D. Culler, and T. Roscoe. A Blueprint for Introducing Disruptive Technology into the Interned. In Proc. of HotNets-I, princeton, NJ, Oct. 2002.Google Scholar
- G. F. Riley, R. M. Fujimoto, and M. H. Ammar. A Generic Framework for Parallelization of Network Simulations. In Proc. of MASCOTS 1999, October 1999. Google ScholarDigital Library
- A. Vahdat, K. Yocum, K. Walsh, P. Mahadevan, D. Kostić, J. Chase, and D. Becker. Scalability and Accuracy in a Large-Scale Network Emulator. In Proc. of the Fifth Symposium on Operating Systems Design and Implementation, pages 271--284, Boston, MA, Dec. 2002. Google ScholarDigital Library
- P. van Hentenryck. Personal communication, Nov. 2001.Google Scholar
- P. J. M. van Laarhoven. Theoretical and Computational Aspects of Simulated Annealing. Centrum voor Wiskunde en Informatica, 1988.Google Scholar
- P. J. M. van Laarhoven and E. H. L. Aarts. Simulated Annealing: Theory and Applications. D. Reidel, 1987. Google ScholarDigital Library
- B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar. An Integrated Experimental Environment for Distributed Systems and Networks. In Proc. of the Fifth Symposium on Operating Systems Design and Implementation, pages 255--270, Boston, MA, Dec. 2002. Google ScholarDigital Library
- K. Yocum, E. Eade, J. Degesys, D. Becker, J. Chase, and A. Vahdat. Scaling Network Emulation using Topology Partitioning. Technical Report TR CS-2003-01, Duke University, February 2003.Google ScholarCross Ref
- K. Yocum, E. Eade, J. Degesys, D. Becker, J. Chase, and A. Vahdat. Toward Scaling Network Emulation using Topology Partitioning. In Proc. of MASCOTS 2003, October 2003.Google ScholarCross Ref
Recommendations
Efficient Online Virtual Network Mapping Using Resource Evaluation
Network virtualization is a promising solution that can prevent network ossification by allowing multiple heterogeneous virtual networks (VNs) to cohabit on a shared substrate network. It provides flexibility and promotes diversity. A key issue that ...
Virtual Network Mapping Based on Function Block Resources
CNIS '14: Proceedings of the 2014 International Conference on Computer Network and Information ScienceNetwork virtualization is one of the core technologies of SDN (Software Defined Networks) research. Network virtualization is to operate multiple virtual networks on a single substrate network independently. VN (Virtual Network) Mapping is one of the ...
Delay-tolerant network experiments on the meshtest wireless testbed
CHANTS '08: Proceedings of the third ACM workshop on Challenged networksDelay Tolerant Networks (DTNs) are a class of networks in which a contemporaneous end-to-end path from source to destination generally does not exist. Such networks use on a store-carry-forward communication model which relies on the mobility of nodes ...
Comments