Project 3: TCP :telephone_receiver:

Deadlines

  • Milestone 1: Arrange meeting on/before Friday, November 1
  • Milestone 2: Arrange meeting on/before Tuesday, November 12
  • Final deadline: Friday, November 22 by 11:59pm EST

Introduction

In this project, you will implement an RFC-compliant version TCP on top of your virtual IP layer from the previous assignment. In doing so, you will extend your virtual network stack to implement sockets, the key networking abstraction at the transport layer that allows hosts to keep track of multiple, simultaneous connections. Thus, you will not only learn about how TCP works, but you’ll learn about the OS infrastructure involved to support a networking stack.

Students report that this project is very challenging, but also very rewarding. When you are done here, you will really understand TCP, and the challenges involved in building a real-world network protocol.

Teams: You may work on this project on the same team you used for IP, or you may switch teams. At this point, you should have already filled out the TCP team form to tell us your team preferences. If you have any further concerns about your team or collaborating on this project, please contact the instructor ASAP.

Warning: You have roughly 5 weeks to complete this assignment, with two intermediate milestone deadlines for you to implement part of the functionality and check in with the course staff. We strongly recommend that you start early and take full advantage of this time–you will need it!

During this time, we remind you that we are here to help at all stages of the process! If you have questions at the design or implementation stage, we implore you to ask for help early so that we can make sure you are on the right track.

What you will build

In the IP project, you implemented handling to deliver virtual IP packets between nodes. To implement TCP, you will extend your vhost to use TCP to reliably send data between hosts. Ultimately, our goal will be to reliably send whole files between hosts, even under a lossy network that intentionally drops packets.

Your TCP implementation will have four major components:

  1. An abstraction for sockets which maps packets to individual connections. To work with sockets, you will build your own Socket API, similar to a real networking API, that allows “applications” to use your sockets to interact with the virtual network
  2. An implementation of the TCP state machine that implements connection setup and teardown
  3. The sliding window protocol that determines when to send and receive data, acknowledges received data, and retransmits data as necessary
  4. A new set of REPL commands that will allow you (and us) to test your API and send/receive files

Additionally, capstone students must also implement a congestion control algorithm and document its performance.

The first three items make up what we call the TCP stack, which is another “layer” in your node that implements TCP. You can think about how your TCP stack fits into your existing IP implementation based on the figure below:

Fundamentally, your TCP stack will be another component in your host that receives packets from the IP layer, similar to how you handled RIP and test packets in the IP project. TCP uses IP protocol number 6—to receive packets, you will start by adding another protocol handler for TCP packets, and then your handler will map them to sockets.

In keeping with our emphasis on building good abstractions similar to a real networking stack, you should think of your socket API as the interface between your REPL commands and the rest of your TCP stack. This API should be similar to the socket API for the language you are using, though you are welcome to draw ideas from other languages as well. Even though your TCP stack will only be used by your vhost program, we recommend building your TCP implementation in a library/module/packge/etc, similar to your IP stack, which will help you keep your code organized.

How to navigate the docs

The remainder of this page outlines the major components of the implementation and points to relevant specifications—both in this document, and in RFC standards—and then provides information on grading and the project timeline.

Sockets and a Socket API

To interface with your TCP stack, you will create a representation for sockets within your node and an API to interact with them. Just like in a real OS, our virtual sockets will allow your node to maintain multiple simultaneous connections with other nodes on which you can send and receive data.

To do this, you will build your own API for creating and operating on virtual sockets, similar to the socket functions you have been using all semester, such as Listen, Dial/Connect, Read, Write, Close). You will add commands in your driver program that will interact with your sockets using your API, similar to how applications interact with the OS.

See the Socket API specification for a description of the main API features you will need and an example of what an API could look like. You don’t need to exactly implement the API shown here, but yours should have similar components.

TCP protocol

The core of your implementation will be what happens inside your TCP stack on each API call, and each time a socket receives a packet. In general, your implementation should follow RFC9293, the now-primary Internet standard for TCP—however, we have made some modifications to the standard to simplify certain elements and remove certain features that are not required. Thus, your implementation will be a minimal form of TCP that implements the most important features, with a few exceptions to help reduce the complexity.

See the TCP Implementation notes for a detailed description of the major features, our modifications, pointers to relevant RFCs, and other implementation-specific notes.

TCP REPL commands

To work with sockets and your socket API, you will add several new REPL commands that can create and send/receive on sockets, as well as send files.

For full details, see the REPL Commands specification.

Congestion Control (Capstone only)

Each student taking this course for capstone is responsible for implementing one of the following congestion control algorithms. Your TCP design should be able to selectively enable and disable any congestion control module that is available, and only 1 congestion control algorithm can be enabled per tcp socket at any given time. If you would like to implement a different congestion control algorithm than the two provided below (since there are many more out there), please ask on Ed first.

The algorithms we recommend are:

  • TCP Tahoe: Slow Start, Congestion Avoidance, Fast Retransmit
  • TCP Reno: TCP Tahoe + Fast Recovery

If both students on a team are taking the course for capstone credit, they must develop separate congestion control algorithm implementation. To do this, both team members should work out an API for their TCP to select which algorithm to use, and then implement their algorithms independently. (It’s okay for both team members to work in the same repo, but you shouldn’t be sharing code.)

To use your congestion control implementation, you should implement a few more REPL commands that allow us to turn congestion control on and off. For details, see this section.

Lastly, you will be required to provide Wireshark capture files as well as a summary of how your congestion control algorithm fared against your implementation without congestion control.

SRC component: Navigating contexts traffic filtering

After Milestone I, we’ll release details of a short SRC component that you’ll complete independently of the rest of your TCP implementation. In this part, you’ll modify your vrouter to filter packets based on certain header info to block or limit certain types of content.

This part won’t require a lot of code, but should be an insightful look at how network devices can filter traffic, and the kinds of decisions that need to be made to implement it.

We’ll provide more details about this part after Milestone I–stay tuned!

Getting Started

To get started, see the TCP getting started guide guide for information on how to start your new repository, pull our updated reference code, and how to run it. This document also lists the most important conceptual resources you should review before starting.

Gearups

We will have three gearups for TCP, one for each phase of your implementation:

  • Gearup I (overview, prep for Milestone I): Thursday, October 24
  • Gearup II (prep for Milestone II): Thursday, October 31
  • Gearup III (everything else): Thursday, November 14

Unless otherwise specified, all gearups will take place from 6-8pm in CIT 368 on the specified day, and will also be streamed live on Zoom–for details, see Edstem. Notes and a recording will be posted afterward.

We’ve also posted the notes/recordings from last year’s gearups if you want to read ahead–for the latest links, see the getting started guide.

Reference implementation and interoperation

Like with IP, your implementation MUST be able to interoperate with the reference version, so please make sure you use it to test your work.

We will primarily grade your work by watching packets in Wireshark, so it is important that you build and format your packets correctly. For details on how to do this, see the getting started guide and this list of testing resources.

If you encounter issues forwarding packets with the reference vrouter, you should aim to fix these issues at the start of the project. If you have questions on how to do this, please contact the course staff–we can help!

Reference vhost (by request only)

If you do not feel confident in extending your work from the previous assignment to support TCP, please talk to us. We can advise you on critical areas of your IP implementation to prioritize. For example, your TCP implementation will not require RIP, so don’t worry if you had issues with this part.

If necessary, we may be to provide a reference implementation for a vhost that you can use as a starting point instead of your own implementation. If you are interested in this, please contact the instructor.

Roadmap and Grading

To help provide a framework for your work, this project is divided into three implementation phases with two intermediate milestone deadlines. At each milestone deadline, you’ll schedule a meeting with your mentor TA to check in on your implementation and ask questions.

Each phase will also have its own gearup, which will demonstrate the required functionality and provide an overview of the most important implementation details.

Milestone I – 10%

Similar to the IP milestone, you will complete this part by scheduling a meeting with the course staff (preferably your mentor TA) on or before Friday, November 1, subject to TA availability.

For this meeting, your implementation should be able to demonstrate the following:

  • Establishing new connections by properly following the TCP state diagram under ideal conditions. Sending data, handling error cases, or connection teardown are not required.
  • When creating new connections, you should allocate a data structure pertaining to the socket—be prepared to discuss what you need to include in this data structure for the rest of your implementation
  • To test establishing new connections, you should implement the a, c, and (partially) ls commands to listen for, create, and list connections, respectively.
  • You should be able to view your TCP traffic in Wireshark to confirm you are using the packet header correctly. However, computing the TCP checksum is not required.

In addition, you should consider how you will tackle the following:

  • What data structures/state variables would you need to represent each TCP socket?
  • How do you map incoming packets to sockets?
  • How does the connection’s state (eg. SYN_RECEIVED, ESTABLISHED, etc.) affect how you handle a packet?

Milestone II – 10%

You should schedule a subsequent milestone checkin with the course staff on or before Tuesday, November 12.

For this meeting, you should be able to implement the following:

  • Aim to have the send and receive commands working over non-lossy links, based on our specifications for VRead and VWrite. To do this, your send and receive should each be utilizing the sliding window, ACKing the data received, and updating the window. Implementing your sliding window will require an implementation for your send and receive buffers, including handling sequence numbers.
  • Retransmission, connection teardown, and handling out-of-order packets are NOT required yet. However, you should be able to talk about a plan for for how you will implement these (this is a great time to ask questions!).
  • You should sketch an implementation for your REPL commands to send and receive files (sf and rf) using your socket API. These commands do NOT need to work (nor is it expected that you’ll even run them yet!)–we just want to see how you plan to use your socket API to implement them. For any API functions you need that aren’t implemented yet (eg. VClose), just define empty functions so your code compiles.

Like the other milestone meetings, don’t worry too much about having a perfectly working implementation–the goal of this meeting is to give you time to check in with the course staff about your understanding and your design and so you have feedback for the remainder of the project. If you are stuck or are having issues, just bring what you have—you’ll receive credit so long as it’s clear you’ve been working on the problem.

Final deadline: Sending and receiving files

After Milestone II, you should implement the remaining components required to send and receive files using the sf and rf commands. Broadly, this will entail the following additional components:

  • Retransmissions based on a computed RTO interval (from a measurement of SRTT)
  • Receiving out-of-order packets
  • Connection teardown
  • Adhering to the receiver’s flow control window (including zero-window probing)
  • A README and performance measurement (described in the next section)

To test your implementation, you should attempt to send files using the reference router under ideal conditions, and using a 2% loss rate. We will not test loss rates higher than 2%.

This final stage is where you should be spending the most time consulting the RFC. If you have questions on whether you need to handle a certain edge case not mentioned in our specifications, just ask! We don’t want you to be bogged down handling more edge cases than necessary to have a working implementation that can tolerate lossy links.

Documentation and Performance Measurement – 20%

In addition to your implementation, we want you to understand how your design decisions affect your TCP’s behavior and performance. For your final submission, you should include a README that documents your major design decisions and your reasoning for using them, including:

  1. What are the key data structures that represent a connection? (No need to list every field of every struct—just focus on what’s most critical for the major features, e.g., “to handle retransmissions, we use a queue that contains Y and Z”)
  2. At a high level, how does your TCP logic (sending, receiving, retransmissions, etc.) use threads, and how do they interact with each other (and your data structures)? (eg. “thread X is responsible for …, it waits for events Y and Z, and then sends Q”)
  3. If you could do this assignment again, what would you change? Any ideas for how you might improve performance?
  4. If you have any other major bugs or limitations not mentioned in the previous question, please describe the bug and how you have tried to debug the problem

In addition to your readme, we ask that you submit two other documentation components: a post-project form (similar to IP), and a measurement/discussion of your implementation’s performance.

Post-project forms

Before your grading meeting, you should complete two post-project forms (links and details will be available once the Gradescope submission is open):

  1. TCP design survey (complete as a group): a super-quick survey about your major design decisions. We’ll use this info to help understand common ways to implement the project, which will help us calibrate recommendations for future years.

  2. Post-project form (complete individually): a survey about your feedback on the project, and how your team collaborated (similar to IP)

Measuring performance

When you submit, we also ask that you investigate your implementation’s performance, but you are not required to highly optimize your implementation to meet a certain performance goal. While performance is key in all systems design, spending many iterations on optimizing your design is beyond the scope of this project. Instead, we only ask that you measure your implementation’s performance relative to the reference node and comment on it in your README.

To do this, measure the time to send a file of at least 1MB for both your node and the reference node using the linear-r1h2 network with no packet loss and compare the times. Ideally, your implementation should have performance on the same order of magnitude as the reference under the same test conditions.

Note Since our network runs exclusively on the loopback interface, your implementation’s performance is limited by CPU speed, so it’s not valid to compare measurements made on different systems. When taking measurements, you should always try with the reference first to establish a baseline, and then compare the relative times.

Packet capture: Finally, you should include a packet capture of a 1 MB file transmission between two of your nodes. To do this, send a file on the linear-r1h2 network with a 2% drop rate.

When submitting, you should “annotate” the following items in your capture file:

  • The 3-way handshake
  • One segment sent and acknowledged
  • One segment that is retransmitted
  • Connection teardown

To do this, list the frame numbers for each item in your README. For each annotation, you should evaluate if your implementation is responding appropriately per the specification–If you notice any issues, please document them.

For a demonstration of how to create a packet capture, see the Gearup III video.

Capstone students should also provide packet captures for their congestion control implementation. For details, expand the item below:

Click to expand

To do this, send a file using your congestion control (CC) algorithm in a drop-free network, and a network with 2% packet loss. In addition, you should also try running multiple simultaneous file transmissions (eg. 1x congestion control, 1x no CC; 2x CC) to see how your algorithm performs in response to competition.

In Wireshark, take a look at the TCP stream graphs (example tutorial) for one or more of your captures and try to analyze if your your CC implementation is working as expected. Note that, since our network has nearly zero latency and runs entirely on the CPU, the way our network sends and buffers packets creates very different performance conditions from the normal Internet, so it’s fine if your stream graphs do not have the expected shape. All we ask is that you examine your CC implementation’s behavior and identify that it is working as you expect.

Handing In and Interactive Grading

Before each milestone and the final deadline, you should submit your work by pushing to your git repository. Before the final deadline, we will also release instructions on how to submit your work to Gradescope.

After the Thanksgiving break, your mentor TA will arrange to meet with you for an interactive grading session to demonstrate the functionality of your program and grade the majority of it.

Similar to IP, you may continue to make minor tweaks/bugfixes and updates to your documentation (Readme, SRC, code cleanup) before grading meeting without incurring late days, but you should not be implementing major features or “fixing” code you have not previously tested. We may ask you about you original version when grading, any changes you have made since that time.

Final Thoughts

Once again, we highly recommend getting started on this assignment soon—don’t wait to start until a few days before the deadlines! If you have questions, or need help with your implementation, always feel free ask for help or clarification or debugging. This is a hard assignment, but we are here to help you and provide resources, and we will be most effective at doing so if you ask early!

Although we expect compatibility between your TCP implementation and our own, do not get bogged down in the RFC from the start. It is much more important that you understand how TCP works on an algorithmic/abstract level and design the interface to your buffers from your TCP stack and from the virtual socket layer. For any corner cases or small details, the RFC will be your best friend, and our reference implementation should provide a useful example. Always feel free to ask if you have any questions about what you are required to do, or how to handle corner cases. We are here to help! You got this!

Table of contents