Minlan Yu will present her research seminar/general exam on Monday January 21 at 10AM in Room 402. The members of her committee are: Jennifer Rexford (advisor), Kai Li, and David August. Everyone is invited to attend her talk and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Rethinking Virtual Network Embedding: Substrate Support for Path Splitting and Migration 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 has focused on two main approaches: (i) significantly restricting the problem space to allow efficient solutions or (ii) proposing heuristic algorithms that do not use the substrate resources efficiently. 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. A paper in submission about this work is available online at http://www.cs.princeton.edu/~minlanyu/embed-CCR.pdf http://www.cs.princeton.edu/%7Eminlanyu/embed-CCR.pdf Book: L. Peterson, and B. Davie, "Computer Networks: A Systems Approach", Morgan Kaufmann, 3e, 2003 Papers: D. Clark, "The Design Philosophy of the DARPA Internet Protocols," ACM SIGCOMM, August 1988 J.Saltzer, D.Reed and D.Clark, "End-to-End Arguments in System Design", ACM Transactions on Computer Systems, Nov 1984. T. Anderson, L. Peterson, S. Shenker, and J. Turner, "Overcoming the Internet impasse through virtualization," IEEE Computer Magazine, vol. 38, no. 4, pp. 34-41, 2005. A.Bavier, N.Feamster, M.Huang, L.Peterson, and J.Rexford, "In VINI Veritas: Realistic and Controlled Network Experimentation", in Proc. ACM SIGCOMM, Sep 2006. N. Feamster, L. Gao, and J. Rexford, "How to lease the Internet in your spare time," SIGCOMM Comput. Commun. Rev., vol. 37, no. 1, pp. 61-64, 2007. Y. Zhu and M. Ammar, "Algorithms for assigning substrate network resources to virtual network components," in Proc. IEEE INFOCOM, 2006. R. Ricci, C. Alfeld, and J. Lepreau, "A solver for the network testbed mapping problem," ACM Computer Communication Review, vol. 33, no. 2, pp. 65-81, 2003. J. Fan and M. Ammar, "Dynamic topology configuration in service overlay network: A study of reconfiguration policies", in Proc. IEEE INFOCOM, 2006. J. Lu and J. Turner, "Efficient mapping of virtual networks onto a shared substrate", Washington University, Technical Report WUCSE-2006-35, 2006. N. G. Duffield, 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. Netw., vol. 10, no. 5, pp. 679-692, 2002.