[talks] Minlan Yugeneral exam

Melissa M Lawson mml at CS.Princeton.EDU
Tue Jan 15 13:25:04 EST 2008

 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 


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


L. Peterson, and B. Davie, "Computer Networks: A Systems Approach", Morgan Kaufmann, 3e,


D. Clark, "The Design Philosophy of the DARPA Internet Protocols," ACM SIGCOMM, August

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. 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.cs.princeton.edu/pipermail/talks/attachments/20080115/67462ad2/attachment.htm 

More information about the talks mailing list