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.
Book
[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.