Nanxi Kang will present her research seminar/general exam on Friday May 3 at Noon in Room 301 (note room!). The members of her committee are: Jennifer Rexford (advisor), David Walker, and Vivek Pai. 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. ----- Original Message ----- Abstract 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.