[talks] N Katta generals

Melissa M. Lawson mml at CS.Princeton.EDU
Fri May 17 13:27:44 EDT 2013

Naga Katta will present his research seminar/general exam on Wednesday 
May 22 at 2PM in Room 402. The members of his committee are: Jennifer 
Rexford (advisor), David Walker, and Michael Freedman. Everyone is 
invited to attend his talk and those faculty wishing to remain for the oral exam 
following are welcome to do so. His abstract and reading list follow below. 


The \emph{network update problem} requires that a network operator 
replace the current, global network configuration with a new, global 
network configuration while preserving key correctness invariants. 
One way to solve the problem is by ensuring \emph{per-packet} or 
\emph{per-flow consistency}. The former ensures that every packet 
traverses either the old network configuration, or the new configuration, 
but not some combination of the two. The latter generalizes the 
former by ensuring in addition that every packet in the same flow 
traverses the same configuration. A consequence of either consistency 
model is that if both old and new configuration share some property 
of their paths through the network, such as loop-freedom, access control or 
connectivity then that property is guaranteed to persist across an update. 
A disadvantage of past implementation mechanisms for these consistency 
models is that the transition from one configuration to the next can 
double the configuration rule-space requirements on a network switch. we 
present general-purpose algorithms for solving the network update 
problem, that are designed to trade the time required to perform an 
update against the additional rule-space needed. More specifically, 
we break a global consistent update in to $K$ rounds, with each round 
transferring some subset of the network traffic from old to new configuration. 
The more rounds used, the longer the update time, but the less rule space 
overhead is required. To ensure consistency, we perform an analysis of 
old and new configurations, determining the rules that must be added and may be 
removed from a switch in each round. To determine the optimal use of rule space, we 
demonstrate how to represent the optimization problem as a mixed integer linear 
program. We also show how to extend the mixed integer linear program 
to additionally optimize for rapid update of the largest flows. Finally, 
we present initial empirical results that illustrate the tradeoff between 
time and space. 

Reading List: 

[1] L. Peterson, and B. Davie, "Computer Networks: A Systems Approach", Morgan Kaufmann, 5e, 2011 

Research Papers 
[2] D. Clark, "The Design Philosophy of the DARPA Internet Protocols", ACM SIGCOMM, August 1988 
[3] J.Saltzer, D.Reed and D.Clark, "End-to-End Arguments in System Design", ACM Transactions on Computer Systems, Nov 1984 
[4] Ethane: Taking Control of the Enterprise, Martìn Casado, Michael J. Freedman, Justin Pettit, Jianying Luo, Nick McKeown, Scott Shenker, Sigcomm 2007 
[5] Onix: A Distributed Control Platform for Large-scale Production Networks, Teemu Koponen, Martìn Casado, Natasha Gude, Jeremy Stribling, Leon Poutievski, Min Zhu, Rajiv Ramanathan, Yuichiro Iwata, Hiroaki Inoue, Takayuki Hama, Scott Shenker, OSDI 2010 
[6] Abstractions for Network Update, Mark Reitblatt, Nate Foster, Jennifer Rexford, Cole Schlesinger, David Walker, Sigcomm 2012 
[7] Header space analysis: static checking for networks. Peyman Kazemian, George Varghese, and Nick McKeown, (NSDI'12). 
[8] A Safe, Efficient Update Protocol for OpenFlow Networks, Rick McGeer, HotSDN 2012 
[9] DevoFlow: Scaling Flow Management for High-performance Networks, Andrew R. Curtis, Jeffrey C. Mogul, Jean Tourrilhes, Praveen Yalagandula, Puneet Sharma, Sujata Banerjee, Sigcomm 2011 
[10] TCAM Razor: a systematic approach towards minimizing packet classifiers in TCAMs, Alex X. Liu, Chad R. Meiners, and Eric Torng, IEEE/ACM Transactions on Networking (TON) 
[11] Using CPU as a Traffic Co-processing Unit in Commodity Switches, Guohan Lu, Rui Miao, Yongqiang Xiong, Chuanxiong Guo, HotSDN 2012 
[12] OFLOPS: An Open Framework for OpenFlow Switch Evaluation, Charalampos Rotsos, Nadi Sarrar, Steve Uhlig, Rob Sherwood, Andrew W. Moore, PAM 2012 
[13] Flyways To Decongest Data Center Networks., S. Kandula, J. Padhye, and P. Bahl. In Proc. of HotNets, 2005. 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20130517/af42465c/attachment.htm>

More information about the talks mailing list