Advanced Topics in Networked Systems: Lab Assignment One - Programmable Networks

Due Oct. 25, 2023 in class or by email to the instructor. This assignment gives you a chance to become familiar with P4 syntax, and programming using P4 for basic network application.

Our experiments involve two different P4 targets, namely the BMV2 software switch and the Tofino programmable switch. Everyone needs to complete labs 1 and 2 on BMV2. Lab 3 is a bonus and is not required for every student to complete. If you want to complete Lab 3, you can contact the teaching assistant in advance.



[Obtaining required software]

We have prepared a virtual machine for the experiment, which you can download and import directly. This virtual machine was obtained online from [P4 tutorials](https://github.com/p4lang/tutorials). We strongly recommend that you complete the examples in this tutorial, which will make you more familiar with P4-based programming. You need to use username `P4` and password `P4` to enter the virtual machine. The relevant experimental code is in the directory `/home/p4/tutorials/exercises`. Or you can follow the guide in the [P4 tutorials](https://github.com/p4lang/tutorials) to create a virtual machine yourself and place our experimental code in the directory `/home/p4/tutorials/exercises`.
Or you can get our pre-configured virtual machines directly from one of the three links below:

1. Link 1: https://box.xmu.edu.cn/share/b8d704a759a74dc36a48cf9150
2. Link 2: https://share.weiyun.com/OIT9M9GN
3. Link 3: https://drive.google.com/file/d/1n5g4shEHll4C46Nv6vfBrFUrrdWUY4C9/view?usp=sharing

In addition, we also provide basic source code for this assignment. We have prepared a basic module for sending and receiving data packets for you, and provided simple p4 source code. You can complete your assignment based on the 'ToDo' in the p4 source code. You can download our base code via this link.

[Part 1: Heavy Hitter Detection; 60 points]

The objective of this part is to use Count-Min Sketch to detect heavy hitters in the network. Heavy hitters (HHs) are large-volume flows that consume considerably more network resources than other flows combined. Heavy hitters can be defined simply as traffic sources sending unusually large amounts of traffic, or it can be categorized by each application sending the traffic.
Count-Min Sketch is a probabilistic algorithm that can be implemented in the data plane to detect heavy hitters. The execution process of Count-Min Sketch is to calculate the hash of some header values and then use the hash value to index the counters in the register. We use the minimum value among the obtained counters as the estimated value of the flow size. If the estimated value is greater than the threshold, we consider the flow to be a heavy hitter.
You will get the starting code for sending and receiving packets and the p4 program. Your job is to write the switch code for heavyhitter and extend it.
A complete `heavyhitter.p4` will contain the following components:


1. Definitions of metadata (5 points)
2. An action that implements updating Count-Min Sketch: (20 points)

1. Hash on the 5-tuple of the packet (10 points)
2. Read from sketch's counter array and update the value (10 points)

3. An action that implements L3 forwarding (5 points)
4. An control that: (30 points)

1. Updates sketch and gets an estimate of flow size (10 points)
2. If the estimated value of the flow is greater than the threshold (100 in the code), then we will drop the packets of the flow (10 points)
3. If the estimated value of the flow is less than the threshold (100 in the code), then we will perform L3 forwarding on the packet (10 points)


[Part 2: ECN; 40 points]

The objective of this part is to extend basic L3 forwarding with an implementation of Explicit Congestion Notification (ECN).
ECN allows end-to-end notification of network congestion without dropping packets. If an end-host supports ECN, it puts the value of 1 or 2 in the `ipv4.ecn` field. For such packets, each switch may change the value to 3 if the queue size is larger than a threshold. The receiver copies the value to sender, and the sender can lower the rate.
As before, we have already defined the control plane rules for routing, so you only need to implement the data plane logic of your P4 program.
A complete `ecn.p4` will contain the following components:


1. Header type definitions for Ethernet (`ethernet_t`) and IPv4 (`ipv4_t`) (1 points)
2. Parsers for Ethernet, IPv4 (1 points)
3. An action to drop a packet, using `mark_to_drop()` (5 points)
4. An action (called `ipv4_forward`), which will: (20 points)

1. Set the egress port for the next hop. (5 points)
2. Update the ethernet destination address with the address of the next hop. (5 points)
3. Update the ethernet source address with the address of the switch. (5 points)
4. Decrement the TTL. (5 points)

5. An egress control block that checks the ECN and `standard_metadata.enq_qdepth` and sets the ipv4.ecn. (5 points)
6. A deparser that selects the order in which fields inserted into the outgoing packet. (5 points)
7. A `package` instantiation supplied with the parser, control, checksum verification and recomputation and deparser. (3 points)


[Part 3: BONUS; 20 points]

You should implement one of the above assignments on the Tofino programmable switch. We also welcome you to propose and implement your own ideas. You need to contact the teaching assistant in advance to obtain permission to use the experimental platform.


[Submission]

Your submission should include the source code for Part 1 and Part 1, and a file named Report that shows the results from Part 1 and Part 2. The report file can be either in .txt or .pdf format.