Minlan Yu
Jennifer Rexford
Abstract
Network virtualization is a powerful way to run multiple architectures or experiments simultaneously on a shared infrastructure. However, making efficient use of the underlying resources requires effective techniques for virtual network embedding--mapping each virtual network to specific nodes and links in the substrate network. Since the general embedding problem is computationally intractable, past research restricted the problem space to allow efficient solutions, or focused on designing heuristic algorithms. In this paper, we advocate a different approach: rethinking the design of the substrate network to enable simpler embedding algorithms and more efficient use of resources, without restricting the problem space. In particular, we simplify virtual link embedding by: i) allowing the substrate network to split a virtual link over multiple substrate paths and ii) employing path migration to periodically re-optimize the utilization of the substrate network. We also explore node-mapping algorithms that are customized to common classes of virtual-network topologies. Our simulation experiments show that path splitting, path migration,and customized embedding algorithms enable a substrate network to satisfy a much larger mix of virtual networks
- Akamai content distribution network. http://www.akamai.com/.Google Scholar
- GENI.http://www.geni.net/.Google Scholar
- Planetlab.https://www.planet-lab.org/.Google Scholar
- Virtual Network Embedding Simulator. http://www.cs.princeton.edu/~minlanyu/embed.tar.gzGoogle Scholar
- R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications Prentice Hall, 1993. Google ScholarDigital Library
- D.G. Andersen. Theoretical approaches to node assignment. Unpublished Manuscript, http://www.cs.cmu.edu/~dga/papers/andersen-assign.ps 2002.Google Scholar
- T. Anderson, L. Peterson, S. Shenker, and J. Turner. Overcoming the Internet impasse through virtualization. IEEE Computer Magazine 38(4):34--41, 2005. Google ScholarDigital Library
- B. Augustin, X. Cuvellier, B. Orgogozo, F. Viger, T. Friedman, M. Latapy, C. Magnien, and R. Teixeira. Avoiding traceroute anomalies with Paris traceroute. In Proc. Internet Measurement Conference 2006. Google ScholarDigital Library
- I. Avramopoulos, D. Syrivelis, J. Rexford, and S. Lalis. Secure availability monitoring using stealth probes. Technical Report TR-769-06, Princeton University, 2006.Google Scholar
- A. Bavier, N. Feamster, M. Huang, L. Peterson, and J. Rexford. In VINI veritas: Realistic and controlled network experimentation. In Proc. ACM SIGCOMM September 2006. Google ScholarDigital Library
- N.G. Dufield, P. Goyal, A. Greenberg, P. Mishra, K.K. Ramakrishnan, and J.E. van der Merwe. Resource management with hoses: Point-to-cloud services for virtual private networks. IEEE/ACM Trans. Networking 2002. Google ScholarDigital Library
- D. Eppstein. Finding the k shortest paths. In Proc. IEEE Symposium on Foundations of Computer Science 1994.Google Scholar
- J. Fan and M. Ammar. Dynamic topology configuration in service overlay networks: A study of reconfiguration policies. In Proc. IEEE INFOCOM 2006.Google ScholarCross Ref
- N. Feamster, L. Gao, and J. Rexford. How to lease the Internet in your spare time. ACM Computer Communication Review 37(1):61--64, 2007. Google ScholarDigital Library
- A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford. NetScope: Traffic engineering for IP networks. IEEE Network Magazine 14(2):11--19, March 2000. Google ScholarDigital Library
- A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener. Provisioning a virtual private network: A network design problem for multicommodity flow. In Proc. ACM Symposium on Theory of Computing 2001. Google ScholarDigital Library
- M. Harchol-Balter and A.B. Downey. Exploiting process lifetime distributions for dynamic load balancing. ACM Transactions on Computer Systems 15(3):253--285, 1997. Google ScholarDigital Library
- J. He and J. Rexford. Towards Internet-wide multipath routing. In IEEE Network Magazine Special Issue on Scalability March 2008. Google ScholarDigital Library
- P. Key, L. Massoulie, and D. Towsley. Path selection and multipath congestion control. In Proc. IEEE INFOCOM 2007.Google ScholarDigital Library
- S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi. Optimization by simulated annealing. Science, Number 4598, 13 May 1983 220, 4598:671--680, 1983.Google Scholar
- J. Kleinberg. Approximation algorithms for disjoint paths problems PhD thesis, MIT, 1996. Google ScholarDigital Library
- S.G. Kolliopoulos and C. Stein. Improved approximation algorithms for unsplittable flow problems. In Proc. IEEE Symposium on Foundations of Computer Science 1997. Google ScholarDigital Library
- J. Lu and J. Turner. Efficient mapping of virtual networks onto a shared substrate. Technical Report WUCSE-2006-35, Washington University, 2006.Google Scholar
- M. Mitzenmacher. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems 12(10):1094--1104, 2001. Google ScholarDigital Library
- S. Raghunath, K.K. Ramakrishnan, S. Kalyanaraman, and C. Chase. Measurement based characterization and provisioning of IP VPNs. In Proc. Internet Measurement Conference 2004. Google ScholarDigital Library
- R. Ricci, C. Alfeld, and J. Lepreau. A solver for the network testbed mapping problem. ACM Computer Communication Review 33(2):65--81, 2003. Google ScholarDigital Library
- J.S. Turner and D.E. Taylor. Diversifying the Internet. In Proc. IEEE GLOBECOM 2005.Google ScholarCross Ref
- K. Webb, M. Hibler, R. Ricci, A. Clements, and J. Lepreau. Implementing the Emulab-Planetlab portal: Experience and lessons learned. In Workshop on Real, Large Distributed Systems (WORLDS) 2004.Google Scholar
- T. Wood, P. Shenoy, A. Venkataramani, and M. Yousif. Black-box and gray-box strategies for virtual machine migration. In Proc. Networked Systems Design and Implementation 2007. Google ScholarDigital Library
- E.W. Zegura, K.L. Calvert, and S. Bhattacharjee. How to model an internetwork.In Proc. IEEE INFOCOM 1996. Google ScholarDigital Library
- Y. Zhu and M. Ammar. Algorithms for assigning substrate network resources to virtual network components. In Proc. IEEE INFOCOM 2006.Google ScholarCross Ref
Index Terms
- Rethinking virtual network embedding: substrate support for path splitting and migration
Recommendations
Virtual Network Embedding for telco-grade network protection and service availability
The decoupling of software from hardware by means of virtualization presents us with a unique opportunity to perform on-the-fly network deployment and reconfiguration. Virtual Machines could be instantiated and virtual links can connect these machines ...
Topology-aware virtual network embedding based on closeness centrality
Network virtualization aims to provide a way to overcome ossification of the Internet. However, making efficient use of substrate resources requires effective techniques for embedding virtual networks: mapping virtual nodes and virtual edges onto ...
A feedback control approach for energy efficient virtual network embedding
Network virtualization is an enabler for intelligent energy-aware network deployment. The existing research usually searches the subset of resources in the whole substrate network passively for the virtual networks (VNs), where resource consolidation ...
Comments