We aim to build a basic setup that demonstrates how to implement and utilize the FRER (Frame Replication and Elimination for Reliability) protocol in P4. The FRER protocol consists of two primary components: replication and elimination. The replication function is responsible for duplicating packets and transmitting them over multiple interfaces to sustain reliability. On the other hand, the elimination function operates when packets arrive from different paths, retaining only a single copy and discarding any duplicates. This decision is made based on the R-tag, which is embedded in the packet header to uniquely identify each frame. Since both replication and elimination are applied per-flow, accurate flow identification is essential for both functions to operate correctly.
Our setup is intentionally designed to be as simple as possible, as the goal is to clearly demonstrate how the FRER protocol works—without requiring a complex network. This setup will be implemented using Mininet. The images illustrates the structure of our setup, which includes two PCs (PC1 and PC2) that communicate with each other through two P4 switches running the P4FRER implementation. When PC1 sends a packet to PC2, the packet first reaches Switch1. At this point, Switch1 modifies the VLAN ID, inserts an R-tag into the packet header, and replicates the packet across its egress interfaces. These replicated packets are then forwarded to Switch2. Upon arrival at Switch2, the elimination function determines which of the incoming packets is the original and which are replicas. The first received packet is forwarded to its destination, while duplicates are discarded. The green 'R' and 'E' symbols represent the replication and elimination path from PC1 to PC2. The communication in the reverse direction (from PC2 to PC1) follows the same process, but the replication and elimination functions are marked as blue.
Initially, the VLAN IDs will be included in the packets by default, as the PCs will insert them directly into the packet headers.
The VLAN IDs will be hardcoded at first to simplify the initial setup and ensure everything works as expected. Once the basic functionality is confirmed, we plan to enhance this aspect by enabling the control plane to assign VLAN IDs dynamically. This will allow users to define different VLAN IDs for different paths or routes, adding flexibility to the setup. Apart from this VLAN ID management, we do not plan to implement any additional functionality on the control plane.
The replication function begins by inspecting the incoming packet to verify the presence of a VLAN tag. It identifies the VLAN ID from the VLAN header, and if the VLAN tag is missing, the packet is dropped. If the packet passes these checks, the next step is to generate a sequence number, which will be included in the R-tag. We believe it is feasible to generate this sequence number within the data plane. After generating the sequence number, the R-tag is created and inserted into the packet. The R-tag consists of 6 bytes: the first 2 bytes represent the Ethertype, the following 2 bytes are reserved, and the final 2 bytes store the sequence number. The R-tag can be defined in P4 using the following structure:
header rtag_t {
bit<16> etherType;
bit<16> reserved;
bit<16> seq;
}Finally, once the R-tag is added, the function modifies the VLAN ID as required and the packet is replicated to the designated egress interfaces for transmission.
The elimination function begins by modifying the VLAN ID and then reading it. This VLAN ID is used to identify the appropriate history map associated with each flow. Each flow maintains a history window, which is essentially a small bit array capable of tracking at least two recent sequence numbers. Since we do not allocate memory to store the entire sequence number space (ranging from 0 to 65535), we instead track the highest sequence number seen so far for each flow.
When a packet arrives at the elimination point, we first locate the corresponding history window using the VLAN ID. Once the appropriate window is found, we remove the R-tag from the packet and extract the sequence number from it. Using this sequence number, we calculate a delta (i.e., the distance from the last seen sequence number) to determine whether the packet should be accepted or discarded. This decision is based on whether the sequence number falls within the valid window range.
We also keep track of various statistics with P4 counters as defined in the FRER specification or related patents, such as rogue_packets, discarded_packets, out_of_order_packets, and passed_packets. After processing the packet, the history window is updated to reflect the most recent valid sequence number. We believe that the history window can be implemented in the data plane.
Important note: each access to the history window should be atomic!
-
test environment -
vlan tag with the same ID; drop the packet if there's no vlan tag -
replace the vlan ID per interface from the control plane -
generate a sequence number for the rtag -
add and remove rtag -
implement the history window -
drop the replicas
.
├─ README.md // Project overview and instructions
├─ .gitignore // Git ignored files and directories
├─ LICENCE // Copyright licence
├─ src/
│ ├─ FRER.p4 // P4 program executed on P4-enabled switches
│ ├─ network.py // Initializes the testbed and launches control plane
│ ├─ control_plane.py // Implements the switch's control plane
│ ├─ s1-commands.txt // P4 table entries for switch s1
│ ├─ s2-commands.txt // P4 table entries for switch s2
│ └─ send_pkt.py // Script for sending packets
└─ images/
└─ setup.png // Illustrating the test setup
Note: Mininet does not support multigraphs. To run this setup, you will need to modify the following file:
File: p4-tools/p4-utils/p4utils/mininetlib/network_API.py
Comment out the three assert statements that block multigraph functionality:
# assert not self.is_multigraph()Once these lines are commented out, the setup will run correctly.
Use the command below to launch the test environment. This will compile the P4 code, populate the P4 tables using the .txt files, and start the control plane on the switches, which resets the counters and logs their values to the log files.
sudo python3 src/network.py
To access host h1, run this command:
mx h1
Use ping on h1 to test basic connectivity:
root@p4:/home/p4/P4FRER# ping 10.0.0.2 -c 3
PING 10.0.0.2 (10.0.0.2) 56(84) bytes of data.
64 bytes from 10.0.0.2: icmp_seq=1 ttl=64 time=4.05 ms
64 bytes from 10.0.0.2: icmp_seq=2 ttl=64 time=3.92 ms
64 bytes from 10.0.0.2: icmp_seq=3 ttl=64 time=5.60 ms
IPv6 is also supported. You can test it with:
root@p4:/home/p4/P4FRER# ping fe80::200:ff:fe02:202
PING fe80::200:ff:fe02:202(fe80::200:ff:fe02:202) 56 data bytes
64 bytes from fe80::200:ff:fe02:202%h1-eth1.10: icmp_seq=1 ttl=64 time=6.98 ms
64 bytes from fe80::200:ff:fe02:202%h1-eth1.10: icmp_seq=2 ttl=64 time=2.40 ms
64 bytes from fe80::200:ff:fe02:202%h1-eth1.10: icmp_seq=3 ttl=64 time=3.12 ms
Alternatively, you can send custom packets using the included Python script:
python3 src/send_pkt.py