CS 856: Programmable Networks (Winter 2024)

Instructor Mina Tahmasbi Arashloo
Schedule Tuesdays and Thursdays, 12:00 PM - 1:20 PM
Contact Email. Please prefix the subject line of your email with [CS856] for a timely reply.
Office Hours By appointment.
Prerequisites Familiarity with basic networking concepts such as different networking layers (e.g., data link, network, and transport layers), forwarding and routing, and common protocols (e.g., Ethernet, IP, UDP, TCP, HTTP, and DNS), through CS 456/656 or an equivalent course.
Location DC 2585

Overview

Modern computer networks are complex distributed systems, with thousands of heterogeneous software and hardware components working together to deliver traffic from sources to destinations. They serve applications that demand much more than basic network connectivity, asking for certain levels of performance and reliability from the network. Meeting these growing expectations requires running new and increasingly sophisticated algorithms and protocols in networking software and hardware.

As such, as networks continue to grow in complexity, scale, and speed, it is simply not sustainable to operate and manage them by manually configuring a fixed set of algorithms and protocols through low-level command-line interfaces. That is why the networking community has spent the last decade rethinking how to design and operate networks using programming abstractions and automation. This includes, but is not limited to, designing programmable network hardware, developing domain-specific languages for programming it, and building automated tools to analyze and implement network functionality by distributing high-level programs across the network, compiling them to low-level instructions for the underlying hardware, or verifying their correctness.

In this course, we will study the literature on how programming abstractions and automation have been applied in different parts of the networking ecosystem and the benefits that have followed. Specifically, we will discuss the following (tentative list):

Grading

The final grade for the course will be based on the following components:

Reviews (20%): A major component of this course is reading, reviewing, and discussing networking and systems papers. In preparation for in-class discussions, students are expected to write reviews for two papers each week. Each review should be ~500 words and contain the following sections, following the typical format of reviews in networking and systems conferences:
  1. Summary: A concise summary of the paper (1 paragraph)
  2. Strenghts: A list of the paper's main strengths (at least 2 bullet points)
  3. Opportunities for improvement: A list of opportunities for improvement (at least 2 bullet points)
  4. Critical analysis: bulk of the review, justifying the strengths and improvement opportunities listed in the previous sections)
  5. Trade-offs: When it comes to systems, there is almost never a free lunch -- every system has to make some sort of trade-off. Some examples are latency vs throughput or flexibility vs performance. This is a paragraph or two about the trade-off space that is relevant to the proposed approach of the paper, and where the proposed approach is in that trade-off space.
Paper Presentation (15%): Each paper discussion starts by a 10-minute presentation by a student. Specifically, the presenter will describe the context and motivation behind the paper, the main problem the paper is trying to solve, the main design choices and/or techniques used in the solution, a summary of evaluation results, and 4-5 discussion questions. Each student is expected to do 1-2 presentations.

In-class Discussion (10%): Effective participation in in-class discussions about papers.

Light programming assignment (5% + Bonus): The purpose of the programming assignment is for the students to gain hands-on experience in using some of the common techniques and technologies used in programmable networks. The required assignment focuses on implementing a simple network functionality using P4, one of the most common languages for programming the network data plane. There is an optional assignment, worth an extra 5%, which focuses on analyzing the correctness of a simple network functionality using existing analysis tools. Assignments are to be completed by each student individually.

Project (50%): Student are expected to work (individually or in groups) on original research projects related to programmable networks. There are four deliverables for the project:

Schedule

Following is the schedule of lectures and paper discussions.

Topic Dates Slides Papers for Review Other Resources Project and Assignments
0. Course Introduction Tue - Jan 9 [lec00]
1. SDN and OpenFlow Thu - Jan 11
Tue - Jan 16 		[lec01] 4D, Frenetic OpenFlow, NetKAT
2. Programming the Data Plane with P4 Thu - Jan 18
Tue - Jan 23 		[lec02] P4, P416 p4.org, Domino, Mantis, MicroP4, P4All Assignment 1 is released (Jan 22)
3. Programmable Switch Architectures Thu - Jan 25
Tue - Jan 30 		[lec03] RMT, JYV+15 dRMT, FlexCore, Trio, Menshen, Chipmunk Project proposal is due (Jan 31)
4. "Smart" Network Interface Cards Thu - Feb 1
Tue - Feb 6 		[lec04] AccelNet, iPipe ClickNP, PANIC, Clara
5. Programming Software Network Stacks Thu - Feb 8
Tue - Feb 13 		[lec05] OvS, CCP OvS'21, XDP, K2, NetBricks
6. Applications to Traditional Networks Thu - Feb 15 [lec06] Assignment 1 is due
Reading Week
6. Applications to Traditional Networks (Continued) Tue - Feb 27 Fibbing, Propane SwitchV, PINS
7. Network Verification Thu - Feb 29
Tue - Mar 5 		[lec07] p4v, RCDC Netverify website, Network verification course, Anteater, HSA, Veriflow, GRooT, FPerf Assignment 2 (optional) is released
8. Flexible & Fine-Grained Network Monitoring Thu - Mar 7
Tue - Mar 12 		[lec08] Sonata, UnivMon Top-down Telemetry, BeauCoup, SpiderMon Project progress report is due
9. Applications to Transport, Network QoS,
and In-Network Computing 		Thu - Mar 14
Tue - Mar 19
Thu - Mar 21		 [lec09] HPCC, AFQ,
ATP 		BFC, PIFO, Loom, ConQuest, ABM, INC, NetCache, NetChain, NetLock, P4xos, NetRPC, NCL, Bertha
Project Presentations: Tue - Mar 26 & Thu - Mar 28
Final Project Report Due Mon - Apr 15

Territorial Acknowledgement

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within the Office of Indigenous Relations.

Faculty of Math's Statement on Mental Health and Diversity

Mental Health Support: The Faculty of Math encourages students to seek out mental health support if needed.

On-campus Resources: Off-campus Resources: Diversity: It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students’ learning needs be addressed both in and out of class. We recognize the immense value of the diversity in identities, perspectives, and contributions that students bring, and the benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular:

Note for Students with Disabilities

AccessAbility Services, located in Needles Hall, Room 1401, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.

University and Faculty of Math Policy on Academic Integrity

Academic Integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. [Check the Office of Academic Integrity for more information.]

Grievance: A student who believes that a decision affecting some aspect of their university life has been unfair or unreasonable may have grounds for initiating a grievance. Please read Policy 70, Section 4. When in doubt, please be certain to contact the department’s administrative assistant who will provide further assistance.

Discipline: A student is expected to know what constitutes academic integrity to avoid committing an academic offence, and to take responsibility for their actions. [Check the Office of Academic Integrity.] A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about “rules” for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate associate dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties, check Guidelines for the Assessment of Penalties.

Avoiding Academic Offenses: Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Office of Academic Integrity's site on Academic Misconduct and the Faculty of Mathematics' site on Academic Integrity.

Appeals: A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes they have a ground for an appeal should refer to Policy 72 - Student Appeals.

References

4D Albert Greenberg, Gisli Hjalmtysson, David A. Maltz, Andy Myers, Jennifer Rexford, Geoffrey Xie, Hong Yan, Jibin Zhan, Hui Zhang. A clean slate 4D approach to network control and management. ACM SIGCOMM CCR 2005.
Frenetic Nate Foster, Rob Harrison, Michael J. Freedman, Christopher Monsanto, Jennifer Rexford, Alec Story, David Walker. Frenetic: A network programming language. ACM ICFP 2011.
OpenFlow Nick McKeown, Tom Anderson, Hari Balakrishnan, Guru Parulkar, Larry Peterson, Jennifer Rexford, Scott Shenker, Jonathan Turner. OpenFlow: enabling innovation in campus networks. ACM SIGCOMM CCR 2008.
NetKAT Carolyn Jane Anderson, Nate Foster, Arjun Guha, Jean-Baptiste Jeannin, Dexter Kozen, Cole Schlesinger, David Walker. NetKAT: Semantic foundations for networks. ACM POPL 2014.
P4 Pat Bosshart, Dan Daly, Glen Gibb, Martin Izzard, Nick McKeown, Jennifer Rexford, Cole Schlesinger et al. P4: Programming protocol-independent packet processors. ACM SIGCOMM CCR 2014.
P416 Mihai Budiu, Chris Dodd. The P416 programming language. ACM SIGOPS OSR 2017.
Domino Anirudh Sivaraman, Alvin Cheung, Mihai Budiu, Changhoon Kim, Mohammad Alizadeh, Hari Balakrishnan, George Varghese, Nick McKeown, Steve Licking. Packet transactions: High-level programming for line-rate switches. ACM SIGCOMM 2016.
Mantis Liangcheng Yu, John Sonchack, Vincent Liu. Mantis: Reactive programmable switches. ACM SIGCOMM 2020.
MicroP4 Hardik Soni, Myriana Rifai, Praveen Kumar, Ryan Doenges, Nate Foster. Composing dataplane programs with µP4. ACM SIGCOMM 2020.
P4All Mary Hogan, Shir Landau-Feibish, Mina Tahmasbi Arashloo, Jennifer Rexford, David Walker. Modular switch programming under resource constraints. USENIX NSDI 2022.
RMT Pat Bosshart, Glen Gibb, Hun-Seok Kim, George Varghese, Nick McKeown, Martin Izzard, Fernando Mujica, Mark Horowitz. Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN. ACM SIGCOMM 2013.
JYV+15 Lavanya Jose, Lisa Yan, George Varghese, Nick McKeown. Compiling packet programs to reconfigurable switches. USENIX NSDI 2015.
dRMT Sharad Chole, Andy Fingerhut, Sha Ma, Anirudh Sivaraman, Shay Vargaftik, Alon Berger, Gal Mendelson et al. dRMT: Disaggregated programmable switching. ACM SIGCOMM 2017.
FlexCore Jiarong Xing, Kuo-Feng Hsu, Matty Kadosh, Alan Lo, Yonatan Piasetzky, Arvind Krishnamurthy, Ang Chen. Runtime programmable switches. USENIX NSDI 2022.
Trio Mingran Yang, Alex Baban, Valery Kugel, Jeff Libby, Scott Mackie, Swamy Sadashivaiah Renu Kananda, Chang-Hong Wu, Manya Ghobadi. Using Trio: juniper networks' programmable chipset-for emerging in-network applications. ACM SIGCOMM 2022.
Menshen Tao Wang, Xiangrui Yang, Gianni Antichi, Anirudh Sivaraman, and Aurojit Panda. Isolation mechanisms for high-speed packet-processing pipelines. USENIX NSDI 2022.
Chipmunk Xiangyu Gao, Taegyun Kim, Michael D. Wong, Divya Raghunathan, Aatish Kishan Varma, Pravein Govindan Kannan, Anirudh Sivaraman, Srinivas Narayana, and Aarti Gupta. Switch code generation using program synthesis. ACM SIGCOMM 2020.
AccelNet Daniel Firestone, Andrew Putnam, Sambhrama Mundkur, Derek Chiou, Alireza Dabagh, Mike Andrewartha, Hari Angepat et al. Azure Accelerated Networking: SmartNICs in the public cloud. USENIX NSDI 2018.
iPipe Ming Liu, Tianyi Cui, Henry Schuh, Arvind Krishnamurthy, Simon Peter, and Karan Gupta. Offloading distributed applications onto SmartNics using iPipe. ACM SIGCOMM 2019.
ClickNP Bojie Li, Kun Tan, Layong Luo, Yanqing Peng, Renqian Luo, Ningyi Xu, Yongqiang Xiong, Peng Cheng, and Enhong Chen. ClickNP: Highly flexible and high performance network processing with reconfigurable hardware. ACM SIGCOMM 2016.
PANIC Jiaxin Lin, Kiran Patel, Brent E. Stephens, Anirudh Sivaraman, and Aditya Akella. PANIC: A high-performance programmable NIC for multi-tenant networks. USENIX NSDI 2020.
Clara Yiming Qiu, Jiarong Xing, Kuo-Feng Hsu, Qiao Kang, Ming Liu, Srinivas Narayana, and Ang Chen. Automated SmartNIC Offloading Insights for Network Functions. ACM SOSP 2021.
OvS Ben Pfaff, Justin Pettit, Teemu Koponen, Ethan Jackson, Andy Zhou, Jarno Rajahalme, Jesse Gross et al. The design and implementation of Open vSwitch. USENIX NSDI 2015.
CCP Akshay Narayan, Frank Cangialosi, Deepti Raghavan, Prateesh Goyal, Srinivas Narayana, Radhika Mittal, Mohammad Alizadeh, and Hari Balakrishnan. Restructuring endpoint congestion control. ACM SIGCOMM 2018.
OVS'21 William Tu, Yi-Hung Wei, Gianni Antichi, and Ben Pfaff. Revisiting the Open vSwitch dataplane ten years later. ACM SIGCOMM 2021.
XDP Toke Høiland-Jørgensen, Jesper Dangaard Brouer, Daniel Borkmann, John Fastabend, Tom Herbert, David Ahern, and David Miller. The eXpress Data Path: Fast programmable packet processing in the operating system kernel. ACM CoNEXT 2018.
K2 Qiongwen Xu, Michael D. Wong, Tanvi Wagle, Srinivas Narayana, and Anirudh Sivaraman. Synthesizing safe and efficient kernel extensions for packet processing. ACM SIGCOMM 2021.
NetBricks Aurojit Panda, Sangjin Han, Keon Jang, Melvin Walls, Sylvia Ratnasamy, and Scott Shenker. Netbricks: Taking the V out of NFV. USENIX OSDI 2016.
Fibbing Stefano Vissicchio, Olivier Tilmans, Laurent Vanbever, and Jennifer Rexford. Central control over distributed routing. ACM SIGCOMM 2015.
Propane Ryan Beckett, Ratul Mahajan, Todd Millstein, Jitendra Padhye, and David Walker. Don't mind the gap: Bridging network-wide objectives and device-level configurations. ACM SIGCOMM 2016.
SwitcHV Kinan Dak Albab, Jonathan DiLorenzo, Stefan Heule, Ali Kheradmand, Steffen Smolka, Konstantin Weitz, Muhammad Timarzi, Jiaqi Gao, and Minlan Yu. SwitchV: automated SDN switch validation with P4 models. ACM SIGCOMM 2022.
p4v Jed Liu, William Hallahan, Cole Schlesinger, Milad Sharif, Jeongkeun Lee, Robert Soulé, Han Wang, Călin Caşcaval, Nick McKeown, and Nate Foster. P4v: Practical verification for programmable data planes. ACM SIGCOMM 2018.
RCDC Karthick Jayaraman, Nikolaj Bjørner, Jitu Padhye, Amar Agrawal, Ashish Bhargava, Paul-Andre C. Bissonnette, Shane Foster et al. Validating datacenters at scale. ACM SIGCOMM 2019.
Anteater Haohui Mai, Ahmed Khurshid, Rachit Agarwal, Matthew Caesar, P. Brighten Godfrey, and Samuel Talmadge King. Debugging the data plane with Anteater. ACM SIGCOMM 2011.
HSA Peyman Kazemian, George Varghese, and Nick McKeown. Header space analysis: Static checking for networks. USENIX NSDI 2012.
Veriflow Ahmed Khurshid, Xuan Zou, Wenxuan Zhou, Matthew Caesar, and P. Brighten Godfrey. VeriFlow: Verifying network-wide invariants in real time. USENIX NSDI 2013.
GRooT Siva Kesava Reddy Kakarla, Ryan Beckett, Behnaz Arzani, Todd Millstein, and George Varghese. GRooT: Proactive verification of DNS configurations. ACM SIGCOMM 2020.
FPerf Mina Tahmasbi Arashloo, Ryan Beckett, Rachit Agarwal. Formal methods for network performance analysis. USENIX NSDI 2023.
Sonata Arpit Gupta, Rob Harrison, Marco Canini, Nick Feamster, Jennifer Rexford, and Walter Willinger. Sonata: Query-driven streaming network telemetry. ACM SIGCOMM 2018.
UnivMon Zaoxing Liu, Antonis Manousis, Gregory Vorsanger, Vyas Sekar, and Vladimir Braverman. One sketch to rule them all: Rethinking network flow monitoring with UnivMon. ACM SIGCOMM 2016.
Top-Down Telemetry Minlan Yu. Network Telemetry: Towards A Top-Down Approach. ACM SIGCOMM CCR 2019.
BeauCoup Xiaoqi Chen, Shir Landau-Feibish, Mark Braverman, and Jennifer Rexford. Beaucoup: Answering many network traffic queries, one memory update at a time. ACM SIGCOMM 2020.
SpiderMon Weitao Wang, Xinyu Crystal Wu, Praveen Tammana, Ang Chen, and TS Eugene Ng. Closed-loop network performance monitoring and diagnosis with SpiderMon. USENIX NSDI 2022.
HPCC Yuliang Li, Rui Miao, Hongqiang Harry Liu, Yan Zhuang, Fei Feng, Lingbo Tang, Zheng Cao et al. HPCC: High Precision Congestion Control. ACM SIGCOMM 2019.
AFQ Naveen Kr Sharma, Ming Liu, Kishore Atreya, and Arvind Krishnamurthy. Approximating fair queueing on reconfigurable switches. USENIX NSDI 2018.
BFC Prateesh Goyal, Preey Shah, Naveen Kr Sharma, Mohammad Alizadeh, and Thomas E. Anderson. Backpressure flow control. USENIX NSDI 2022.
PIFO Anirudh Sivaraman, Suvinay Subramanian, Mohammad Alizadeh, Sharad Chole, Shang-Tse Chuang, Anurag Agrawal, Hari Balakrishnan, Tom Edsall, Sachin Katti, and Nick McKeown. Programmable packet scheduling at line rate. ACM SIGCOMM 2016.
Loom Brent E. Stephens, Aditya Akella, and Michael M. Swift. Loom: Flexible and Efficient NIC Packet Scheduling. USENIX NSDI 2019.
ConQuest Xiaoqi Chen, Shir Landau Feibish, Yaron Koral, Jennifer Rexford, Ori Rottenstreich, Steven A. Monetti, and Tzuu-Yi Wang. Fine-grained queue measurement in the data plane. ACM CoNEXT 2019.
ABM Vamsi Addanki, Maria Apostolaki, Manya Ghobadi, Stefan Schmid, and Laurent Vanbever. ABM: active buffer management in datacenters. ACM SIGCOMM 2022.
ATP ChonLam Lao, Yanfang Le, Kshiteej Mahajan, Yixi Chen, Wenfei Wu, Aditya Akella, and Michael Swift. ATP: In-network aggregation for multi-tenant learning. USENIX NSDI 2021.
INC Dan RK Ports, and Jacob Nelson. When should the network be the computer?. ACM HotOS 2019.
NetCache Xin Jin, Xiaozhou Li, Haoyu Zhang, Robert Soulé, Jeongkeun Lee, Nate Foster, Changhoon Kim, and Ion Stoica. Netcache: Balancing key-value stores with fast in-network caching. ACM SOSP 2017.
NetChain Xin Jin, Xiaozhou Li, Haoyu Zhang, Nate Foster, Jeongkeun Lee, Robert Soulé, Changhoon Kim, and Ion Stoica. Netchain: Scale-free sub-RTT coordination. USENIX NSDI 2018.
NetLock Zhuolong Yu, Yiwen Zhang, Vladimir Braverman, Mosharaf Chowdhury, and Xin Jin. Netlock: Fast, centralized lock management using programmable switches.. ACM SIGCOMM 2020.
P4xos Huynh Tu Dang, Pietro Bressana, Han Wang, Ki Suh Lee, Noa Zilberman, Hakim Weatherspoon, Marco Canini, Fernando Pedone, and Robert Soulé. P4xos: Consensus as a network service. IEEE/ACM Transactions on Networking.
NCL George Karlos, Henri Bal, and Lin Wang. Don't You Worry'Bout a Packet: Unified Programming for In-Network Computing. ACM HotNets 2021.
Bertha Akshay Narayan, Aurojit Panda, Mohammad Alizadeh, Hari Balakrishnan, Arvind Krishnamurthy, and Scott Shenker. Bertha: Tunneling through the network API. ACM HotNets 2020.
SWAN Chi-Yao Hong, Srikanth Kandula, Ratul Mahajan, Ming Zhang, Vijay Gill, Mohan Nanduri, and Roger Wattenhofer. Achieving high utilization with software-driven WAN. ACM SIGCOMM 2013.
B4 Sushant Jain, Alok Kumar, Subhasree Mandal, Joon Ong, Leon Poutievski, Arjun Singh, Subbaiah Venkata et al. B4: Experience with a globally-deployed software defined WAN. ACM SIGCOMM 2013.
OWAN Xin Jin, Yiran Li, Da Wei, Siming Li, Jie Gao, Lei Xu, Guangzhi Li, Wei Xu, and Jennifer Rexford. Optimizing bulk transfers with software-defined optical WAN. ACM SIGCOMM 2016.
Jupiter Leon Poutievski, Omid Mashayekhi, Joon Ong, Arjun Singh, Mukarram Tariq, Rui Wang, Jianan Zhang et al. Jupiter evolving: Transforming google's datacenter network via optical circuit switches and software-defined networking. ACM SIGCOMM 2022.