Xiaoqi Chen will present his General Exam on Tuesday, Oct 23, 2018 at 10am in CS 302. The members of his committee are Jennifer Rexford (adviser), Mark Braverman, and David Walker. 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. Abstract: Network measurement is a vital tool for network operators to diagnose outages, optimize performance, and detect attacks. Recently, the development of programmable switches has enabled us to run measurement algorithms in the network switch directly, and analyze packets up to Tbps in throughput. However, the programming model of programmable switches is extremely constrained, which restricts the types of algorithms we can run in them. To achieve much-needed measurement goals of network operators, we design tailored algorithms to adapt to the programming constraints imposed by practical programmable switches. We first present PRECISON, which attempts to answer the Heavy-Hitter Flow Detection problem (find out which flows sent the largest number of packets). PRECISION can accurately identify the heavy-hitter flows using a small amount of memory, by recirculating a small number of packets probabilistically. Then, we present Snappy, which tries to solve the Heavy Flow in the Queue problem (which flows occupied a large fraction of queuing buffer). Snappy can pinpoint the bursty flows causing ephemeral long queues and potential packet loss, by maintaining multiple traffic snapshots of short time intervals. Our measurement algorithms enable network operators to perform immediate actions against these specific network flows, inhibiting congestion in real-time, while potentially improving service quality for other network flows. Reading list: Textbook: * Larry L. Peterson and Bruce S. Davie. Computer Networks: A Systems Approach . Elsevier, 2011 (5th ed). Papers: 1. [E2E ‘84] Jerome H. Saltzer, David P. Reed, and David D. Clark. "End-to-end arguments in system design." ACM Transactions on Computer Systems (TOCS) 2.4 (1984): 277-288. 2. [Ether ’99] Will E. Leland, Murad S. Taqqu, Walter Willinger, and Daniel V. Wilson. "On the self-similar nature of Ethernet traffic (extended version)." IEEE/ACM Transactions on Networking (ToN) 2.1 (1994): 1-15. 3. [Click ’00] Eddie Kohler, Robert Morris, Benjie Chen, John Jannotti, and M. Frans Kaashoek. "The Click modular router." ACM Transactions on Computer Systems (TOCS) 18.3 (2000): 263-297. 4. [SS ’05] Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. "Efficient computation of frequent and top-k elements in data streams." International Conference on Database Theory . Springer, Berlin, Heidelberg, 2005. 5. [pFabric ’13] Mohammad Alizadh, Shuang Yang, Milad Sharif, Sachin Katti, Nick McKeown, Balaji Prabhakar, and Scott Shenker. "pfabric: Minimal near-optimal datacenter transport." ACM SIGCOMM Computer Communication Review . Vol. 43. No. 4. ACM, 2013. 6. [P4 ‘14] Pat Bosshart, Dan Daly, Glen Gibb, Martin Izzard, Nick McKeown, Jennifer Rexford, Cole Schlesinger* Dan Talayco, Amin Vahdat, George Varghese, and David Walker. "P4: Programming protocol-independent packet processors." ACM SIGCOMM Computer Communication Review 44.3 (2014): 87-95. 7. [UnivMon ‘16] Zaoxing Liu, Antonis Manousis, Gregory Vorsanger, Vyas Sekar, and Vladimir Braverman. "One sketch to rule them all: Rethinking network flow monitoring with UnivMon." Proceedings of the 2016 ACM SIGCOMM Conference . ACM, 2016. 8. [RAP ‘16] Ran Ben Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. "Randomized admission policy for efficient top-k and frequency estimation." INFOCOM 2017-IEEE Conference on Computer Communications, IEEE . IEEE, 2017. 9. [StarFlow ‘18] John Sonchack, Oliver Michel, Adam J. Aviv, Eric Keller, and Jonathan M. Smith. "Scaling Hardware Accelerated Network Monitoring to Concurrent and Dynamic Queries With* Flow." 2018 USENIX Annual Technical Conference (USENIX ATC 18) . USENIX Association, 2018. 10. [AFQ ’18] Naveen Kr. Sharma, Ming Liu, Kishore Atreya, and Arvind Krishnamurthy. "Approximating Fair Queueing on Reconfigurable Switches." USENIX Symposium on Networked Systems Design and Implementation . 2018. Catching heavy network flows using programmable switches