DaVinci: dynamically adaptive virtual networks for a customized internet

ABSTRACT

Running multiple virtual networks, customized for different performance objectives, is a promising way to support diverse applications over a shared substrate. Despite being simple, a static division of resources between virtual networks can be highly inefficient, while dynamic resource allocation runs the risk of instability. This paper uses optimization theory to show that adaptive resource allocation can be stable and can maximize the aggregate performance across the virtual networks. In the DaVinci architecture, each substrate link periodically reassigns bandwidth shares between its virtual links; while at a smaller timescale, each virtual network runs a distributed protocol that maximizes its own performance objective independently. Numerical experiments with a mix of delay-sensitive and throughput-sensitive traffic show that the bandwidth shares converge quickly to the optimal values. We demonstrate that running several custom protocols in parallel and allocating resource adaptively can be more efficient, more flexible, and easier to manage than a compromise "one-size-fits-all" design.

REFERENCES

• 1: Thomas Anderson , Larry Peterson , Scott Shenker , Jonathan Turner, Overcoming the Internet Impasse through Virtualization, Computer, v.38 n.4, p.34-41, April 2005 [doi>10.1109/MC.2005.136]
• 2: J. S. Turner and D. E. Taylor, "Diversifying the Internet," in Proc. IEEE GLOBECOM, November 2005.
• 3: Nick Feamster , Lixin Gao , Jennifer Rexford, How to lease the internet in your spare time, ACM SIGCOMM Computer Communication Review, v.37 n.1, January 2007 [doi>10.1145/1198255.1198265]
• 4: D. McPherson, D. O'Leary, D. Ward, E. Brendel, O. Aruj, P. Agarwal, R. Hartani, and S. Poretsky, "Core Network Design and Vendor Prophecies," in Proc. NANOG, June 2003.
• 5: "Juniper Networks: Intelligent Logical Router Service." http://www.juniper.net/solutions/literature/white_papers/200097.pdf.
• 6: "Cisco opening up IOS," December 2007. http://www.networkworld.com/news/2007/121207-cisco-ios.html.
• 7: "Partner Solution Development Platform Opens Opportunity to Accelerate the Pace of Network Innovation with JUNOS Software," December 2007. http://www.juniper.net/company/presscenter/pr/2007/pr-071210.html.
• 8: R. Braden , D. Clark , S. Shenker, Integrated Services in the Internet Architecture: an Overview, RFC Editor, 1994
• 9: S. Chen and K. Nahrstedt, "An overview of quality-of-service routing for the next generation high-speed networks: Problems and solutions," IEEE Network Magazine, November/December 1998.
• 10: F. Kuipers, T. Korkmaz, M. Krunz, and P. V. Mieghem, "Overview of constraint-based path selection algorithms for QoS routing," IEEE Communication Magazine, pp. 50--55, December 2002.
• 11: S. Blake , D. Black , M. Carlson , E. Davies , Z. Wang , W. Weiss, An Architecture for Differentiated Service, RFC Editor, 1998
• 12: I. Matta and A. U. Shankar, "Type-of-service routing in datagram delivery systems," IEEE J. on Selected Areas in Communications, vol. 13, pp. 1411--1425, October 1995.
• 13: P. Psenak, S. Mirtorabi, A. Roy, L. Nguyen, and P. Pillay-Esnault, "Multi-Topology (MT) Routing in OSPF." RFC 4915, June 2007.
• 14: Kin Wah Kwong , Roch Guérin , Anees Shaikh , Shu Tao, Improving service differentiation in IP networks through dual topology routing, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York [doi>10.1145/1364654.1364675]
• 15: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 16: David X. Wei , Cheng Jin , Steven H. Low , Sanjay Hegde, FAST TCP: motivation, architecture, algorithms, performance, IEEE/ACM Transactions on Networking (TON), v.14 n.6, p.1246-1259, December 2006 [doi>10.1109/TNET.2006.886335]
• 17: John Jannotti , David K. Gifford , Kirk L. Johnson , M. Frans Kaashoek , James W. O'Toole, Jr., Overcast: reliable multicasting with on overlay network, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.14-14, October 22-25, 2000, San Diego, California
• 18: Yang Chu , Sanjay Rao , Srinivasan Seshan , Hui Zhang, Enabling conferencing applications on the internet using an overlay muilticast architecture, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.55-67, August 2001, San Diego, California, United States
• 19: Lakshminarayanan Subramanian , Ion Stoica , Hari Balakrishnan , Randy H. Katz, OverQos: an overlay based architecture for enhancing internet Qos, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.6-6, March 29-31, 2004, San Francisco, California
• 20: Ram Keralapura , Chen-Nee Chuah , Nina Taft , Gianluca Iannaccone, Race conditions in coexisting overlay networks, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.1-14, February 2008 [doi>10.1109/TNET.2007.897959]
• 21: E. Rosen , Y. Rekhter, BGP/MPLS VPNs, RFC Editor, 1999
• 22: Andy Bavier , Nick Feamster , Mark Huang , Larry Peterson , Jennifer Rexford, In VINI veritas: realistic and controlled network experimentation, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 23: Jonathan S. Turner, A proposed architecture for the GENI backbone platform, Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, December 03-05, 2006, San Jose, California, USA [doi>10.1145/1185347.1185349]
• 24: M. Chiang, S. H. Low, R. A. Calderbank, and J. C. Doyle, "Layering as optimization decomposition," Proceedings of the IEEE, January 2007.
• 25: Jiayue He , Martin Suchara , Ma'ayan Bresler , Jennifer Rexford , Mung Chiang, Rethinking internet traffic management: from multiple decompositions to a practical protocol, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York [doi>10.1145/1364654.1364676]
• 26: U. Javed, M. Suchara, J. He, and J. Rexford, "Multipath protocol for delay-sensitive traffic," in Proc. the First International Conference on COMmunication Systems and NETworkS (COMSNETS), January 2009.
• 27: J. He and J. Rexford, "Towards Internet-wide Multipath Routing," IEEE Network Magazine, March 2008.
• 28: J. He, M. Suchara, M. Bresler, J. Rexford, and M. Chiang, "From Multiple Decompositions to TRUMP: Traffic Management Using Multipath Protocol," March 2008. in submission to IEEE/ACM Transactions on Networking, www.cs.princeton.edu/~jrex/papers/conext07-long.pdf.
• 29: Dilip Joseph , Jayanth Kannan , Ayumu Kubota , Karthik Lakshminarayanan , Ion Stoica , Klaus Wehrle, OCALA: an architecture for supporting legacy applications over overlays, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.20-20, May 08-10, 2006, San Jose, CA
• 30: H. V. Madhyatha, A. Venkataramani, A. Krishnamurthy, and T. Anderson, "Oasis: An overlay-aware network stack," in Proc. ACM SIGOPS, January 2006.
• 31: "GENI opt-in working group." http://geni.net/wg/opt-in-wg.html.
• 32: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 33: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 34: I. Avramopoulos, J. Rexford, D. Syrivelis, and S. Lalis, "Counteracting discrimination against network traffic." Princeton University Computer Science Technical Report TR-794-07, August 2007.
• 35: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 36: Steven H. Low, A duality model of TCP and queue management algorithms, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.525-536, August 2003 [doi>10.1109/TNET.2003.815297]
• 37: J. Pongsajapan and S. Low, "Reverse engineering TCP/IP-like networks using delay-sensitive utility functions," in Proc. IEEE INFOCOM, May 2007.
• 38: Y. Li, M. Chiang, A. R. Calderbank, and S. Diggavi, "Optimal delay-rate-reliability tradeoff in networks with composite links," in Proc. IEEE INFOCOM, May 2007.
• 39: X. Lin and N. B. Shroff, "Utility Maximization for Communication Networks with Multi-path Routing," IEEE Trans. Automatic Control, vol. 51, May 2006.
• 40: L. S. Lasdon, Optimization Theory for Large Systems. Macmillian, 1970.
• 41: D. P. Bersekas, Nonlinear Programming. Athena Scientific, second ed., 1999.
• 42: Abilene Backbone. http://abilene.internet2.edu/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
      C.2.1 Network Architecture and Design

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance