Software Defined Networking (SDN) supports diverse
network policies by offering direct, network-wide control
over how the switches handle traffic. However, today’s controller
platforms force applications to grapple with the space
limits on each switch and the interaction between the packet-handling
rules at different hops in a path. Instead, we believe
SDN applications should specify high-level policies,
and rely on the controller to generate the rules for each switch.
A high-level policy defines the handling of traffic on a single
abstract switch (indicating how packets should be modified,
and dropped or forwarded to egress ports), as well as the
routing of traffic across the “switching fabric.” Transforming
the high-level policy into an equivalent set of switch-level
rules is computationally difficult, since the policy may
route traffic on arbitrary paths and match traffic on multiple
dimensions of packet-header fields. We present a family
of efficient rule-placement algorithms, starting with the simple
case of policies matching one packet-header field along
a chain, and building up to the general case which involves
arbitrary routing, multi-dimensional patterns and the need
to enable dynamic, incremental update of policies. Our experiments
with synthetic benchmarks, and real firewall and
routing policies, demonstrate that our algorithms can support
realistic policies using the small rule tables available in
commodity switches.
----------------------------------
Reading List
[1] L. L. Peterson and B. S. Davie, Computer networks: a systems approach. Morgan Kaufmann, 2007.
[2] J. H. Saltzer, D. P. Reed, and D. D. Clark, “End-to-end arguments in system design,” ACM Transactions on Computer Systems (TOCS), vol. 2, no. 4, 1984.
[3] M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. Gude, N. McKeown, and S. Shenker, “Rethinking enterprise network control,” IEEE/ACM Trans. Networking, vol. 17, August 2009.
[4] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling innovation in campus networks,” SIGCOMM Computer Communications Review, vol. 38, no. 2, 2008.
[5]C. Monsanto, J. Reich, N. Foster, J. Rexford, and D. Walker, "Composing software dened networks," in NSDI, Apr 2013.
[6] M. Yu, J. Rexford, M. J. Freedman, and J. Wang, "Scalable flow-based networking with DIFANE," In ACM SIGCOMM, pp. 351-362, Sep 2010.
[7] M. Moshref, M. Yu, A. Sharma, and R. Govindan, "VCRIB: Virtualized rule management in the cloud," in NSDI, Apr 2013.
[8] Y. Kanizo, D. Hay, and I. Keslassy, "Palette: Distributing tables in software-dened networks," in IEEE INFOCOM Mini-conference, Apr 2013.
[9] C. R. Meiners, A. X. Liu, and E. Torng, "TCAM Razor: A systematic approach towards minimizing packet classiers in TCAMs," IEEE/ACM Trans. Netw., vol. 18, pp. 490-500, Apr 2010.
[10] P. Gupta and N. McKeown, "Packet classication on multiple fields," in ACM SIGCOMM, pp. 147-160, 1999.
[11] S. Singh, F. Baboescu, G. Varghese, and J. Wang, "Packet classication using multidimensional cutting," in ACM SIGCOMM, pp. 213-224, 2003.
[12] Y. Ma and S. Banerjee, "A smart pre-classier to reduce power consumption of tcams for multi-dimensional packet classication," in ACM SIGCOMM, pp. 335-346, Aug 2012.