<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'>Naga Katta will present his research seminar/general exam on Wednesday <br>May 22 at 2PM in Room 402. The members of his committee are: Jennifer <br>Rexford (advisor), David Walker, and Michael Freedman. Everyone is <br>invited to attend his talk and those faculty wishing to remain for the oral exam <br>following are welcome to do so. His abstract and reading list follow below.<br>--------------------<div style="color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div><div><div><div><div style="border-collapse: separate; border-spacing: 0px; "><b><br></b></div><div style="border-collapse: separate; border-spacing: 0px; "><b>Abstract:</b></div><div style="border-collapse: separate; border-spacing: 0px; "><div>The \emph{network update problem} requires that a network operator</div><div>replace the current, global network configuration with a new, global</div><div>network configuration while preserving key correctness invariants.</div><div>One way to solve the problem is by ensuring \emph{per-packet} or</div><div>\emph{per-flow consistency}. The former ensures that every packet</div><div>traverses either the old network configuration, or the new configuration,</div><div>but not some combination of the two. The latter generalizes the</div><div>former by ensuring in addition that every packet in the same flow</div><div>traverses the same configuration. A consequence of either consistency</div><div>model is that if both old and new configuration share some property</div><div>of their paths through the network, such as loop-freedom, access control or </div><div>connectivity then that property is guaranteed to persist across an update.</div><div>A disadvantage of past implementation mechanisms for these consistency</div><div>models is that the transition from one configuration to the next can</div><div>double the configuration rule-space requirements on a network switch. we</div><div>present general-purpose algorithms for solving the network update</div><div>problem, that are designed to trade the time required to perform an</div><div>update against the additional rule-space needed. More specifically,</div><div>we break a global consistent update in to $K$ rounds, with each round</div><div>transferring some subset of the network traffic from old to new configuration.</div><div>The more rounds used, the longer the update time, but the less rule space</div><div>overhead is required. To ensure consistency, we perform an analysis of</div><div>old and new configurations, determining the rules that must be added and may be </div><div>removed from a switch in each round. To determine the optimal use of rule space, we </div><div>demonstrate how to represent the optimization problem as a mixed integer linear </div><div>program. We also show how to extend the mixed integer linear program</div><div>to additionally optimize for rapid update of the largest flows. Finally,</div><div>we present initial empirical results that illustrate the tradeoff between</div><div>time and space.</div><div style="font-weight: bold; "><br></div></div><div style="border-collapse: separate; border-spacing: 0px; "><b><br></b></div><div style="border-collapse: separate; border-spacing: 0px; "><b>Reading List:</b></div><div><div><br></div><div><b><i>Book</i></b></div><div>[1] L. Peterson, and B. Davie, "Computer Networks: A Systems Approach", Morgan Kaufmann, 5e, 2011</div><div> </div><div><b><i>Research Papers</i></b></div><div>[2] D. Clark, "The Design Philosophy of the DARPA Internet Protocols", ACM SIGCOMM, August 1988</div><div>[3] J.Saltzer, D.Reed and D.Clark, "End-to-End Arguments in System Design", ACM Transactions on Computer Systems, Nov 1984</div><div>[4] Ethane: Taking Control of the Enterprise, Martìn Casado, Michael J. Freedman, Justin Pettit, Jianying Luo, Nick McKeown, Scott Shenker, Sigcomm 2007</div><div>[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</div><div>[6] Abstractions for Network Update, Mark Reitblatt, Nate Foster, Jennifer Rexford, Cole Schlesinger, David Walker, Sigcomm 2012</div><div>[7] Header space analysis: static checking for networks. Peyman Kazemian, George Varghese, and Nick McKeown, (NSDI'12).</div><div>[8] A Safe, Efficient Update Protocol for OpenFlow Networks, Rick McGeer, HotSDN 2012</div><div>[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</div><div>[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)</div><div>[11] Using CPU as a Traffic Co-processing Unit in Commodity Switches, Guohan Lu, Rui Miao, Yongqiang Xiong, Chuanxiong Guo, HotSDN 2012</div><div>[12] OFLOPS: An Open Framework for OpenFlow Switch Evaluation, Charalampos Rotsos, Nadi Sarrar, Steve Uhlig, Rob Sherwood, Andrew W. Moore, PAM 2012</div><div>[13] Flyways To Decongest Data Center Networks., S. Kandula, J. Padhye, and P. Bahl. In Proc. of HotNets, 2005.</div></div></div><br></div></div></div></div><br></div></body></html>