CS 856: Programmable Networks (Winter 2023)

Instructor	Mina Tahmasbi Arashloo
Schedule	Tuesdays and Thursdays, 1:00 PM - 2: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 2568

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):

• History of software-defined and programmable networks
• Common languages for programming the network data plane
• Programmable network switches and network interface cards (NICs)
• Programmability in software packet procesing frameworks
• Network verification
• Applications of network programmability in:
  • Traditional networks
  • Network monitoring and measurement
  • Network quality of service (QoS)
  • Acceleration of distributed applications

Grading

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

Reviews (25%): 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:

• A concise summary of the paper (1 paragraph)
• A list of the paper's main strengths (at least 2 bullet points)
• A list of opportunities for improvement (at least 2 bullet points)
• Critical analysis and comments (justifying the strengths and improvement opportunities listed in the previous sections)

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.

Assignments (10%): There are two assignments, each comprising 5% of the final grade. The purpose of the assignments is for the students to gain hands-on experience in using some of the common techniques and technologies used in programmable networks. One assignment focuses on implementing a simple network functionality using P4, one of the most common languages for programming the network data plane. The other assignment 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:

• Proposal: Students are expected to discuss their project ideas with the instructor at the beginning of the term, and submit a one page proposal, providing a clear problem statement, context and motivation, and a high-level overview of related work, by the end of week 3.
• Progress Report: A month after the proposal, the students are expected to submit a 2 page progress report.
• Presentation: In the last week of classes, students will present their projects to the class.
• Final Report: The final report, due at the end of the term, is a 6-page conference-style paper describing the problem statement and motivation, design, evaluation, related work, and future research directions.

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

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:

• Campus Wellness: https://uwaterloo.ca/campus-wellness/
• Counselling Services: counselling.services@uwaterloo.ca 519-888-4567 ext. 32655 
• MATES: one-to-one peer support program offered by Waterloo Undergraduate Student Association (WUSA) and Counselling Services: mates@wusa.ca
• Health Services: located across the creek from the Student Life Centre, 519-888-4096.

Off-campus Resources:

• Good2Talk (24/7): Free confidential help line for post-secondary students. Phone: 1-866-925-5454 (Ontario and Nova Scotia only)
• Here 24/7: Mental Health and Crisis Service Team. Phone: 1-844-437-3247 (Waterloo Region only)
• OK2BME: set of support services for lesbian, gay, bisexual, transgender, or questioning teens. Phone: 519-884-0000 extension 213 (Waterloo Region only)
• EMPOWER ME  1-833-628-5589 for Cdn./USA other countries
  see: http://studentcare.ca/rte/en/IHaveAPlan_WUSA_EmpowerMe_EmpowerMe
• EMPOWER ME in China:
  China North  108007142831 
  China South  108001402851 

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:

• We will gladly honour your request to address you by an alternate/preferred name or gender pronoun. Please advise us of this preference early in the term so we may make appropriate changes to our records.
• We will honour your religious holidays and celebrations. Please inform us of these at the start of the course.
• We will follow AccessAbility Services guidelines and protocols on how to best support students with different learning needs.

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 at the beginning of each academic term.

University 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. The Office of Academic Integrity’s website contains detailed information on University of Waterloo policies for students and faculty. This site explains why Academic Integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in--and out--of the classroom.

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, Student Petitions and Grievances, 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’s website for more information). 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 graduate/undergraduate associate dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline.

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 a ground for an appeal can be established. For more information, refer to Policy 72 - Student Appeals.

Land Acknowledgement

We acknowledge that we live and work on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. The University of Waterloo is situated on the Haldimand Tract, the land promised to the Six Nations that includes six miles on each side of the Grand River.

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.