Transport layer: TCP


Last class we saw the thinnest possible transport protocol. The User Datagram Protocol (UDP) adds ports and a checksum to the network layer and stops there, so a datagram that the network loses, corrupts, or reorders simply never reaches the application. Today we study the Transmission Control Protocol (TCP), which promises the opposite: every byte, in the order the sender wrote it, exactly once. The network underneath has not improved, so the whole protocol is built out of four modest mechanisms — a checksum, acknowledgements, a timer, and a receive buffer — plus a connection that both sides agree to establish before any data moves. We trace a real connection through Wireshark, write both ends in Python, and then look at how a server handles thousands of these connections at once.

Slides from class

Files:

pcaps

Additional information:

Agenda

These notes cover what TCP promises, the connection that makes those promises possible, the bytes of the TCP header, the Python code for both ends of a connection, and the two standard architectures for a server that must hold thousands of connections open at once. A supplemental section near the end develops reliable data transfer from first principles and sketches congestion control; we will cover congestion control properly in a later class.

Notes

We start from the service TCP offers the application above it, then work down into the mechanisms that deliver that service.

TCP overview: what the protocol promises

Recall the two options at Layer 4. UDP is not connection oriented, drops missing or corrupt data, is faster, and carries an 8-byte header. TCP is connection oriented and delivers data in order with no missing bytes, at the cost of speed. Several Requests for Comment (RFCs) specify TCP: RFC 9293 is the current core document, which replaced the original RFC 793, along with RFCs 1122, 2018, 5681, and 7323.

The promises in detail:

The maximum segment size (MSS) caps the payload of one segment. It derives from the maximum link-layer payload, the maximum transmission unit (MTU), which is 1500 bytes on Ethernet, minus the TCP and Internet Protocol (IP) headers at 20 bytes each. The typical MSS is therefore 1460 bytes, and TCP breaks larger messages into MSS-sized pieces.

And as always, the layering holds: Layer 4 TCP is a logical connection between processes, Layer 3 is a logical connection between hosts, and Layer 3 routers mostly do not see Layer 4 information at all. (Network address translation is the main exception.)

How a TCP socket differs from a UDP socket

Last class we deferred one question, and it is the right place to start. A UDP socket is identified by the destination IP address and destination port, and so a single socket receives datagrams sent to that port by any sender. TCP works differently. A server creates a listening socket bound to a specific port, 80 for a web server, for example. When a client initiates a connection, the server's operating system (OS) creates a new, dedicated socket for that one connection, and that new socket is uniquely identified by a 4-tuple: source IP address, source port, destination IP address, and destination port.

Two consequences follow. First, a single server handles many simultaneous connections by demultiplexing each arriving segment to the unique socket that its 4-tuple names, even when a thousand clients all arrive at port 80. Second, bytes from multiple segments on one connection are concatenated into a byte stream with no segment boundaries, so a call to recv may return bytes from several segments, or only part of one. Contrast UDP, where recvfrom reads bytes from exactly one datagram.

What can go wrong, and the four tools

When a sender transmits a packet to a receiver, three things can go wrong: the data can be corrupted by flipped bits, the packet can be lost, and packets can arrive out of order. Reliable data transfer at Layer 4 attempts to deal with each of these, and the channel it must use, Layer 3, may do any of them at any time. TCP attempts to provide reliable data transfer over an unreliable network.

TCP handles the three problems as follows:

So the entire toolkit is four items: a checksum, an acknowledgement (ACK) of bytes received, a timer, and a receive buffer. Everything in the rest of these notes is a consequence of combining those four.

Connection management

Before exchanging data the two sides handshake, both to agree that they are establishing a connection, each knowing the other is willing, and to exchange the parameters that the reliability machinery needs, above all the starting sequence numbers.

The three-way handshake

Three segments open a connection. Host A chooses a random starting sequence number x and sends a segment with the SYN flag set. Host B chooses its own random starting sequence number y and replies with SYN ACK, a segment with both the SYN and ACK flags set, carrying sequence y and acknowledgement number x+1, which is the byte B expects to receive from A next. Host A then replies with an ACK carrying acknowledgement number y+1. The handshake has exchanged starting sequence numbers and established the connection.

Why three messages rather than two? Because both sides need to know that the other side knows. Pilots use the same protocol when transferring control of an aircraft: "I have the airplane," "Roger, your airplane," "My airplane." After three messages no ambiguity remains about who is flying. Two messages would leave the first speaker unsure whether the other heard the acknowledgement.

Why start at a random sequence number rather than always at 0? Because packets from a prior connection between the same two hosts and ports may still be floating around the network. A random starting point makes it unlikely that a stale packet carries a sequence number that the new connection would accept as valid.

The states and the socket calls line up with the three segments. The server creates a socket, binds it, calls listen, and blocks in accept, which puts it in LISTEN. The client creates a socket and calls connect, which chooses x, sends the SYN, and moves the client to SYNSENT. The server receives the SYN and enters SYN RCVD — note that it does not go straight to ESTABLISHED — and sends the SYN ACK. The client receives the SYN ACK, which tells it the server is live, and sends the ACK; this third segment may already carry client-to-server data. Receipt of that ACK tells the server the client is live, both sides reach ESTABLISHED, and the server's accept call returns a new socket for this connection. UDP has no counterpart to any of this, because UDP has no notion of connect.

Sequence and acknowledgement numbers during data exchange

Two rules govern the numbers on every segment after the handshake. The acknowledgement number starts one greater than the other side's sequence number, and once bytes are flowing, the acknowledgement number is the next byte the receiver expects.

Work through the telnet example from class. Telnet sends one byte each time the user presses a key, and the receiver echoes the key back. Assume A starts at sequence 41 and B at 78.

  1. The user types 'C'. A has sent one byte, so this segment is byte 42: Seq=42, Ack=79, data='C'.
  2. B acknowledges receipt of 'C' and echoes the character back: Seq=79, Ack=43, data='C'. The acknowledgement of 43 is one more than A's sequence number of 42, so A now knows that B received byte 42 and is waiting for byte 43.
  3. A acknowledges the echoed 'C': Seq=43, Ack=80. B now knows that A received byte 79 and is waiting for byte 80.

Notice that these acknowledgements ride along on segments that also carry data. Acknowledgement is not a separate conversation.

Closing a connection

Closing takes four segments, a FIN and an ACK in each direction, because each side closes its own direction separately. Host A sends a FIN carrying sequence u; B acknowledges with u+1. At that moment B may still send data, and often does. When B finishes, it sends its own FIN carrying sequence v, and A acknowledges with v+1. Both sides close the connection by sending a FIN, and the side that closes first waits briefly afterward so that it can respond to a retransmitted FIN.

TCP as a byte stream

Sequence numbers count bytes, not segments, and that fact takes a moment to internalize. Work the example from class. Host A wants to send Host B a file of 500,000 bytes with an MSS of 1,000 bytes, and for simplicity A starts at sequence 0. A creates 500 segments of 1,000 bytes each: segment 0 carries bytes numbered 0 through 999, segment 1 carries 1,000 through 1,999, and segment 499 carries 499,000 through 499,999. A segment's sequence number is the byte-stream number of its first data byte. After segment 0 arrives, the receiver acknowledges 1,000, telling the sender that it expects byte 1,000 next.

Each side allocates both a send buffer and a receive buffer. The sender breaks the data into segments no larger than the MSS and hands them to the unreliable network layer. The receiver puts arriving bytes in order into its receive buffer, which creates gaps when packets are missing or arrive out of order. Three properties of the result deserve emphasis:

The sender's three events

A simplified TCP sender responds to three events, and the whole of its behavior fits in a paragraph.

On data received from the application, create a segment whose sequence number is the byte-stream number of its first data byte, and start the timer if the timer is not already running. Think of one timer, belonging to the oldest unacknowledged segment, with an expiration interval called TimeOutInterval. On timeout, retransmit the segment that caused the timeout and restart the timer. On ACK received, if the acknowledgement covers previously unacknowledged segments, update what the sender knows to be acknowledged, and start the timer again if unacknowledged segments remain.

The TCP header, byte by byte

The UDP and TCP headers share some structure, which makes the comparison a good way to see what reliability costs. Both carry a source port and a destination port for demultiplexing to a process, and both carry a checksum for detecting flipped bits. The UDP header is always 8 bytes and has only one other field, a length. The TCP header is normally 20 bytes, though options make that size variable, and it spends the extra 12 bytes on the fields below.

Flow control

Flow control addresses a problem separate from reliability. What happens if the network layer delivers data into the socket buffers faster than the application layer removes it? The buffer fills and data is lost, not because the network failed but because the receiver could not keep up. As the saying goes, nobody can drink from a firehose.

TCP's solution is direct. The receiver advertises its free buffer space in the rwnd (receive window) field of the TCP header, and the sender limits its unacknowledged, in-flight data to that amount, which guarantees that the receive buffer cannot overflow. Socket options set the RcvBuffer size; a typical default today is 128 KB and can rise into the megabytes, and many operating systems adjust RcvBuffer automatically as the connection runs. Since free space fluctuates as the application reads, the advertised value changes over time and the sender adapts.

Keep flow control and congestion control distinct, because the names invite confusion. Flow control concerns one sender overwhelming one receiver, and lives in the rwnd field. Congestion control concerns many senders together overwhelming the network. Different problems, different mechanisms, both present in TCP. We take up congestion control in a later class; the supplemental section below sketches it.

Retransmission scenarios

Three retransmission scenarios cover most of what the timer and the cumulative acknowledgement accomplish together. In each, A sends a segment with Seq=92 carrying 8 bytes of data, and SendBase is the oldest unacknowledged byte.

  1. Lost ACK. A sends Seq=92, B receives it and sends ACK=100, and that acknowledgement is lost. A's timer expires, A retransmits Seq=92, and B acknowledges again with ACK=100. The cost of the lost acknowledgement is one unnecessary retransmission.
  2. Premature timeout. A sends Seq=92 with 8 bytes and then Seq=100 with 20 bytes. A's timer for the first segment expires too early, so A retransmits Seq=92 even though B already has both segments. B responds with a cumulative ACK=120, acknowledging everything through byte 119 rather than just the retransmitted segment.
  3. A cumulative ACK covers an earlier lost ACK. A sends Seq=92 and Seq=100. B's ACK=100 is lost, but its ACK=120 arrives. A learns that both segments arrived, even though the acknowledgement for the first one never came back, and goes on to send Seq=120.

Scenario 3 is the payoff of cumulative acknowledgement: a later ACK makes an earlier lost ACK harmless.

Fast retransmit

Waiting for a timeout is slow, and often unnecessary. If the sender receives three additional acknowledgements for the same data, known as triple duplicate ACKs, it resends the unacknowledged segment with the smallest sequence number immediately rather than waiting for the timer.

The reasoning is that three duplicate acknowledgements mean three segments arrived after a segment that is missing. Segments are still flowing, so the path works; the one segment that is not being acknowledged is likely lost rather than merely delayed. Concretely, if a sender sends five segments and the second is lost, the receiver acknowledges the first with ACK=100 and then repeats ACK=100 three more times as segments 3, 4, and 5 arrive out of order. The sender recognizes the pattern and resends.

Pipelining, Go-Back-N, and selective repeat

A sender that transmits one segment and then waits for an acknowledgement before doing anything else — a stop-and-wait protocol — is correct but wastes nearly all of the available capacity. The supplemental section works the arithmetic; the headline is that on a 1 gbps link with a 15 ms propagation delay, stop-and-wait keeps the sender busy 0.027% of the time.

Pipelining is the fix: let the sender have multiple segments in flight, transmitted but not yet acknowledged. That change requires a wider range of sequence numbers, since two values no longer suffice, and buffering at the sender, the receiver, or both. Allowing three packets in flight triples utilization; allowing N multiplies it by N, until some other limit binds.

Two classic pipelined protocols handle loss differently, and TCP borrows from each.

Go-Back-N

In Go-Back-N (GBN) the sender maintains a window of up to N consecutive transmitted but unacknowledged packets, labeled with a k-bit sequence number in the header. Acknowledgements are cumulative: ACK(n) means the receiver has everything up to and including sequence number n, so on receiving ACK(n) the sender slides its window forward to begin at n+1. The sender keeps a single timer for the oldest in-flight packet, and on timeout it retransmits that packet and every higher-numbered packet in the window, which is the source of the name.

The receiver is simple, which is the appeal. It always acknowledges the highest in-order sequence number received so far, which may mean generating duplicate acknowledgements, and it need remember only one variable, the base of its window. On receiving an out-of-order packet it may either buffer the packet or discard it, an implementation decision, and it re-acknowledges the highest in-order packet either way. The cost is that one lost packet forces retransmission of everything after it, including packets that arrived intact. GBN can therefore cause many retransmissions when N and the delay are both large.

Selective repeat

In selective repeat (SR) the receiver individually acknowledges every correctly received packet and buffers out-of-order packets for eventual in-order delivery upward. The sender keeps a timer for each unacknowledged packet and retransmits only the packets that time out.

The receiver's rules: a packet with sequence number i inside the current window [rcvbase, rcvbase+N−1] is acknowledged, and is buffered when out of order or, when in order, delivered along with any buffered packets that are now in order, after which the window advances to the next not-yet-received packet. A packet in [rcvbase−N, rcvbase−1], already delivered, is acknowledged again. The receiver ignores anything else. Selective repeat wastes less capacity than GBN, at the cost of more state and more timers on both sides.

Selective repeat has a trap worth understanding, because it shows that the window size and the sequence space are not independent. Suppose the sequence numbers are {0, 1, 2, 3} and the window size is 3. In one scenario, packets 0, 1, and 2 arrive and are acknowledged, and the receiver now expects 3, 0, 1. In another, the acknowledgements for 0, 1, and 2 are all lost, so the sender times out and retransmits packet 0. The receiver cannot see the sender's side, and its behavior is identical in both cases: a packet labeled 0 arrives. Is that packet a retransmission of the old packet 0, or a new packet 0 from the next trip around the sequence space? Guessing wrong either duplicates data or drops it. The window must be small enough relative to the sequence space that old and new packets can never be confused, which in practice means no more than half the sequence space.

Following one real connection

Everything above shows up in a packet capture. Fetching a page from vibrantcloud.org with a browser exercises HTTP at Layer 7 over TCP at Layer 4. First resolve the name: 

$ nslookup -type=A vibrantcloud.org
Name:    vibrantcloud.org
Address: 173.201.179.249

Then filter Wireshark on that address. The virtual machine (VM) is 192.168.159.129 using ephemeral port 43786; the server is 173.201.179.249 on port 80.

  1. SYN. Source and destination ports, the SYN flag set, and a randomly chosen initial sequence number, 194256941. The segment also advertises MSS 1460 in an optional header component, which is the 1500-byte Ethernet maximum minus the 20-byte TCP header and the 20-byte IP header.
  2. SYN ACK. SYN and ACK flags both set. The acknowledgement number is one greater than the VM's 194256941, and the server supplies its own random initial sequence number, 4222840285.
  3. ACK. ACK flag set, acknowledgement number one greater than the server's sequence number, and the VM's sequence number one greater than its own initial choice. The connection is now established.
  4. HTTP GET. The VM requests the page, with a sequence number one larger than the one it originally chose. The request is 443 bytes.
  5. ACK. The server acknowledges the request, with an acknowledgement number of the previous value plus those 443 bytes: 194256942 + 443 = 194257385. Byte-counting sequence numbers, made visible.
  6. HTTP 200 OK. The server returns the 553-byte page, which contains the HTML the browser renders. Since the VM sent no new data, the server's acknowledgement number stays at 194257385.
  7. ACK. The VM acknowledges the page: 4222840286 + 553 = 4222840839.

Pressing refresh repeats the last four steps, and the pattern is easy to recognize once you have seen it: GET from the VM, ACK from the server, HTTP OK from the server, ACK from the VM.

Seven segments to fetch a 553-byte page, three of them pure connection setup. That ratio is why persistent connections matter, and why QUIC folds its handshake into a single round trip.

TCP in code

The Python for a TCP client differs from the UDP version in two places: the socket type, and a connection step for which UDP has no equivalent. send_tcp.py: 

import socket

# server's ip and port
HOST = '127.0.0.1'
PORT = 9090

# create TCP socket to connect to server
client_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client_socket.connect((HOST, PORT))

try:
    message = "Hello, Server!"
    client_socket.sendall(message.encode())   # encode converts to bytes

    # get server's response
    data = client_socket.recv(1024)
    print(f"Received from server: {data.decode()}")
finally:
    client_socket.close()

Three details matter here. SOCK_STREAM selects TCP, where SOCK_DGRAM selected UDP. The connect call is what starts the three-way handshake, and it has no counterpart in UDP. And sendall loops until it has sent every byte, whereas send returns the number of bytes it managed to send and leaves you to loop over the remainder yourself.

The server side, receive_tcp.py, handles a single client: 

import socket

# host ip and port
HOST = '0.0.0.0'    # '127.0.0.1' is localhost
PORT = 9090

# create TCP socket listening on ip address and port
server_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server_socket.bind((HOST, PORT))

# listen for connections
server_socket.listen()
print(f"Server listening on {HOST}:{PORT}...")
client_socket = None

try:
    client_socket, addr = server_socket.accept()   # accept returns a new socket for client
    print(f"Connected by {addr}")

    while True:
        data = client_socket.recv(1024)
        if not data:
            break
        print(f"Received: {data.decode()}")        # decode converts bytes to string
        client_socket.sendall(b"Message received: " + data)   # echo back to client
finally:
    if client_socket:
        client_socket.close()
    server_socket.close()

Reading it against the UDP server from last class:

Handling many clients

The server above serves one client and then exits, which no real server can do. A production server listens on one port, port 80 for example, and holds thousands of connections open at once. Two architectures dominate, and you may choose either one for Lab 2.

Approach 1: one thread per connection

The structure follows directly from what accept returns. For each connection, accept hands back a new socket; the server creates a new thread, passes that socket to it, and returns immediately to listening on the main socket. Each thread blocks in its own recv loop, and the OS scheduler switches between threads, so a slow client blocks only its own thread. A thread ends when its client hangs up. Apache is the best-known server built this way.

The appeal is simplicity: the code inside a thread is ordinary blocking code with no callbacks, and it looks much like the single-client server above. The cost is that every worker needs its own stack, so 10,000 clients means 10,000 stacks. That scaling wall is well known enough to have a name, the C10k problem, meaning the difficulty of serving ten thousand concurrent connections on one machine.

In Python, receive_tcp_multithreaded.py: 

import socket
import threading

# host ip and port
HOST = '0.0.0.0'    # '127.0.0.1' is localhost
PORT = 9090

# everything that used to be the body of the while loop now lives in here.
# one thread runs this function per connected client, so the loop below is
# free to go straight back to accept() and pick up the next client
def handle_client(client_socket, addr):
    print(f"Connected by {addr}")
    try:
        while True:
            data = client_socket.recv(1024)
            if not data:   # empty bytes means the client sent FIN, not "no data yet"
                break
            print(f"Received from {addr}: {data.decode()}")
    except ConnectionError:   # one client crashing should not take down the server
        print(f"Connection lost: {addr}")
    finally:
        client_socket.close()
        print(f"Disconnected: {addr}")

# create TCP socket listening on ip address and port
server_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server_socket.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
server_socket.bind((HOST, PORT))

# listen for connections
server_socket.listen()
print(f"Server listening on {HOST}:{PORT}...")
try:
    while True:
        client_socket, addr = server_socket.accept()
        # daemon=True so ctrl-c kills the server even with clients still connected
        t = threading.Thread(target=handle_client, args=(client_socket, addr), daemon=True)
        t.start()
except KeyboardInterrupt:
    print("\nShutting down.")
finally:
    server_socket.close()

The setsockopt call with SO_REUSEADDR lets the program bind the port again right away after a restart, instead of waiting out the TIME_WAIT period, which is about 60 seconds. You will want that option the first time you stop and restart a server during development.

Approach 2: a few workers and an event loop

The second architecture runs one worker per processor core rather than one per connection, and each worker handles thousands of sockets. Instead of blocking in a recv on one socket, the worker asks the OS which of its sockets have data and services just those. The readiness call is epoll on Linux, kqueue on BSD and macOS, or select and poll generally. The sockets are non-blocking, so a recv with no data waiting returns at once rather than parking the worker. nginx is the best-known server of this kind.

The trade is the mirror image of approach 1. A few workers can serve tens of thousands of connections, which is the whole point. But the code is harder to write, because the worker must track the state of every connection explicitly rather than keeping it implicitly on a thread's stack, and one task that occupies the processor stalls every connection that worker is handling.

In Python, receive_tcp_polling.py. The setup registers the listening socket with a selector and names a callback: 

import socket
import selectors

# define host ip and port
HOST = '0.0.0.0'    # '127.0.0.1' is localhost
PORT = 9090

# the selector is the kernel's "tell me which sockets are ready" service.
# DefaultSelector picks epoll on linux, kqueue on mac, select on windows
sel = selectors.DefaultSelector()

# create TCP socket listening on ip address and port
server_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server_socket.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
server_socket.bind((HOST, PORT))

# listen for connections
server_socket.listen()
server_socket.setblocking(False)
sel.register(server_socket, selectors.EVENT_READ, lambda: on_acceptable(server_socket))
print(f"Server listening on {HOST}:{PORT}...")

# the event loop. select() blocks until at least one socket is ready, then hands
# back only those, and we run whatever callback we registered for each
try:
    while True:
        for key, mask in sel.select():
            key.data()   # key.data is the lambda we registered above
except KeyboardInterrupt:
    print("\nShutting down.")
finally:
    sel.close()
    server_socket.close()

And the two callbacks do the work: 

# the listening socket is readable: a new client is waiting in the accept queue
def on_acceptable(server_socket):
    client_socket, addr = server_socket.accept()
    print(f"Connected by {addr}")
    client_socket.setblocking(False)   # never block the one thread we have
    client = Client(client_socket, addr)
    sel.register(client_socket, selectors.EVENT_READ, lambda: on_readable(client))

# a client socket is readable: either data arrived or the client hung up
def on_readable(client):
    data = client.socket.recv(1024)
    if not data:   # empty bytes means the client sent FIN, not "no data yet"
        print(f"Disconnected: {client.addr}")
        sel.unregister(client.socket)   # stop watching before closing
        client.socket.close()
        return
    print(f"Received from {client.addr}: {data.decode()}")
    # could echo back to client here if we wanted

Follow the flow once and the pattern is clear. Set up a selector to watch sockets. Register the listening socket so that on_acceptable runs when a client connects, without blocking. When a client does connect, on_acceptable calls accept to get a socket for that connection, exactly as the multithreaded version does, makes it non-blocking, and registers it so that on_readable runs when that socket has data. on_readable then reads from the socket, but only when data is waiting, and unregisters the socket before closing it when the client disconnects.

Supplemental material

The sections below go beyond what we covered in class. The first develops reliable data transfer from first principles, which is worth reading because it shows that every TCP mechanism exists to solve a specific, identifiable failure. The second previews congestion control, which we take up properly in a later class.

Building a reliable protocol from nothing

Call the protocol rdt (reliable data transfer, Layer 4) and the unreliable service beneath it udt (unreliable data transfer, Layer 3). Four interface calls define the boundaries: rdt_send, called from the sender's Layer 7 with data intended for the receiver's Layer 7; udt_send, called by rdt to transfer a packet over the unreliable channel; rdt_rcv, called when a packet arrives on the receiver's side of the channel; and deliver_data, called by rdt to deliver data up to Layer 7.

Here is the central difficulty, and every mechanism that follows exists to address it: neither side knows the state of the other. It is easy for us, looking at a diagram of sender and receiver together, to say "ah, that packet was lost." From the sender's point of view, though, a curtain hangs between the two hosts. The sender cannot see whether its message arrived, and the only way it can learn anything about the receiver's state is for the receiver to send a message back. How the two sides do that is the protocol. Note the asymmetry: we want reliable one-way data transfer, and obtaining it requires two-way communication.

To specify the protocol we use finite state machines (FSMs), which you saw in CS 10. Prose specifications invite misinterpretation and quietly omit cases. An FSM makes the cases explicit: a state is a situation in which the next event uniquely determines the next state, and each transition carries the event that causes it and the actions taken.

rdt1.0 assumes a perfectly reliable channel: no bit errors, no loss, in order. The assumption is unrealistic, but under it the protocol is trivial. The sender has one state, waiting for a call from above; on rdt_send(data) it makes a packet and calls udt_send(packet). The receiver has one state, waiting for a call from below; on rdt_rcv(packet) it extracts the data and calls deliver_data. No acknowledgements, no timers, no sequence numbers, because nothing goes wrong. Everything that follows is the cost of dropping one assumption at a time.

rdt2.0 allows the channel to flip bits. A checksum detects a flipped bit, and recovery works the way humans recover from errors in conversation: we say "mm-hmm" to signal receipt and "say that again" when we did not hear. Those are the two messages we need, an ACK reporting that the packet arrived correctly and a NAK (negative acknowledgement) reporting that it had errors, on receipt of which the sender retransmits. The result is stop-and-wait: send one packet, then wait for the response before doing anything else.

rdt2.0 has a fatal flaw. What happens if the ACK or NAK is itself corrupted? Now the sender knows that something came back but not what, and the receiver may have received the data perfectly while the reply was garbled. Acknowledging the acknowledgement does not help, since the acknowledgement of the acknowledgement may also be lost, and that progression never terminates. Resending the packet does not help by itself either, because the receiver may then get two copies, and applications expect each byte, without errors, in order, exactly once. The fix is sequence numbers: the sender labels each packet and the receiver discards, rather than delivers, a packet whose number it has already seen. Stop-and-wait needs only two sequence numbers, since it never has more than one packet in flight, so one bit suffices.

rdt2.1 adds that one-bit sequence number, which doubles the states on both sides, because the sender's state must now remember which sequence number is in play and the receiver's must record which number it expects. One residual asymmetry is worth noticing: the receiver can never know whether its last ACK or NAK reached the sender. That gap is a permanent feature of distributed protocols, not a defect in the design.

rdt2.2 gets the same functionality with acknowledgements only, which matters because that is what TCP does. Instead of sending a NAK, the receiver acknowledges the last packet it received correctly, naming that packet's sequence number. A duplicate ACK at the sender then carries exactly the information a NAK carried. How does the sender come to see two acknowledgements bearing the same sequence number? Packet 0 goes out and is acknowledged. Packet 1 goes out and arrives garbled. The receiver, having nothing new to acknowledge, acknowledges packet 0 again. The sender sees the same sequence number twice and concludes that packet 1 did not arrive. Same information, one fewer message type.

rdt3.0 allows the channel to lose or delay packets as well. Checksums, sequence numbers, acknowledgements, and retransmissions all presuppose that something comes back, so a new mechanism is needed: the sender waits a reasonable interval for an acknowledgement and retransmits when none arrives, implemented with a countdown timer started when it sends a packet. If the packet or the acknowledgement was merely delayed, the retransmission creates a duplicate, which sequence numbers already handle. What counts as reasonable? At least the round-trip time (RTT) plus the receiver's processing time. Too short floods the network with unnecessary retransmissions, and too long stalls after every loss. Since RTT varies constantly, choosing the value is a real engineering problem, and TCP estimates it adaptively.

rdt3.0 is correct: it handles corruption, loss, and duplication, and delivers data in order, exactly once. It is also unusably slow, which brings us back to pipelining.

The cost of stop-and-wait, worked out

Define utilization as the fraction of time the sender is busy sending. Take a 1 gbps link with 15 ms propagation delay and 1,000-byte, which is 8,000-bit, packets. The time to transmit one packet into the channel is

Dtrans = L / R = 8,000 bits / 109 bits per second = 8 microseconds

The sender then waits for the packet to propagate (15 ms), for the receiver to respond, and for the acknowledgement to propagate back (15 ms). Assuming an instant response and a negligibly small acknowledgement, the sender can send again at t = RTT + L/R = 30.008 ms, so

Usender = (L/R) / (RTT + L/R) = 0.008 / 30.008 = 0.00027

The sender is busy 0.027% of the time, for an effective throughput of about 267 kbps on a 1 gbps link: one 1 KB packet every 30 ms. The protocol, not the hardware, is the bottleneck, and it wastes more than 99.9% of the capacity. Note what dominates the denominator, namely RTT, and recall from Day 1 that RTT has a hard floor set by the speed of light. The fix cannot be a shorter wait.

Principles of congestion control

Congestion, informally, is too many sources sending too much data too fast for the network to handle. It appears as long delays, from queueing in router buffers, and as packet loss, from buffer overflow at routers — the two phenomena from Day 1, now viewed as a control problem. Three scenarios show what congestion costs.

One router, infinite buffers, no retransmissions. Two flows share a router whose input and output links have capacity R. As the arrival rate approaches R/2 per connection, throughput approaches R/2 and stops there, because throughput can never exceed capacity, and delay grows sharply. Even in this idealized setting you cannot have both full utilization and low delay.

One router, finite buffers, sender retransmits lost packets. The transport-layer input now includes retransmissions, so it exceeds the application-layer input. Where the sender has perfect knowledge and retransmits only what was actually lost, throughput is degraded but the work is at least necessary. In the realistic version, timers expire prematurely, the sender transmits two copies, and both arrive, so that capacity is simply wasted.

Four senders, multi-hop paths, timeouts, and retransmission. Here the outcome is genuinely bad. As one flow's offered load increases, packets from another flow are dropped at a shared queue and that flow's throughput goes to zero. Note the additional cost: when a packet is dropped at a downstream router, all the upstream transmission capacity and buffering already spent carrying it there was wasted.

The insights, collected: throughput can never exceed capacity; delay increases as the network approaches capacity; loss and retransmission decrease effective throughput; unneeded duplicates decrease it further; and upstream capacity and buffering are wasted on packets dropped downstream.

Two broad approaches exist. End-to-end congestion control takes no explicit feedback from the network and infers congestion from observed loss and delay. TCP works this way, which is remarkable when you consider it: the sender diagnoses the state of a network it cannot see, using only the timing and the absence of acknowledgements. Network-assisted congestion control has routers give direct feedback to the hosts whose flows pass through them, possibly indicating the congestion level or even setting a rate explicitly. Explicit congestion notification (ECN) works this way.

TCP congestion control, in brief

TCP limits its rate with cwnd, the congestion window, constraining its unacknowledged data so that LastByteSent − LastByteAcked ≤ cwnd. Roughly, the sender sends cwnd bytes, waits one RTT for the acknowledgements, and then sends more, so rate ≈ cwnd / RTT, and adjusting cwnd adjusts the rate. The sender's real limit is the smaller of cwnd and rwnd, since congestion control and flow control both apply.

The algorithm is AIMD, additive increase and multiplicative decrease: raise the rate by one MSS every RTT until loss appears, then cut the rate in half. The result is the familiar sawtooth, a slow climb probing for available bandwidth and a sharp drop when the probe finds the limit. The decrease has a subtlety: on loss detected by triple duplicate ACKs the rate is halved, while on loss detected by timeout it falls all the way to 1 MSS, a judgment about severity, since a timeout means that no segment is getting through.

Slow start addresses the beginning of a connection, where adding 1 MSS per RTT from a start of 1 MSS would take far too long to reach a useful rate on a fast link. So cwnd starts at 1 MSS and doubles every RTT, implemented by adding one MSS for every acknowledgement received: one segment, then two, then four. The name misleads, since the initial rate is low but the ramp is fast. Growth turns linear when cwnd reaches ssthresh, the slow start threshold, which TCP sets to half of cwnd at each loss event. Above ssthresh TCP is in congestion avoidance and adds roughly one MSS per RTT. The whole cycle: ramp up quickly to near where trouble started last time, probe gently past it, and back off when loss confirms the limit.

Several refinements and alternatives are in wide use. CUBIC, the Linux default, exploits the observation that the bottleneck's congestion state has probably not changed much since the last loss, so after halving the window it ramps quickly back toward the old maximum and then approaches it slowly, increasing the window as a cubic function of the distance in time from the projected arrival at that maximum. Delay-based schemes such as BBR avoid inducing loss at all, comparing measured throughput against uncongested throughput to keep the pipe just full enough but no fuller. ECN spans two layers: a router marks two bits in the IP header's type-of-service field, and the destination echoes the signal to the sender using the C and E bits of the TCP header, so the sender learns of congestion without a loss occurring.

Is TCP fair? The goal is that K sessions sharing a bottleneck of capacity R each get R/K, and under idealized assumptions — equal RTTs, a fixed number of sessions all in congestion avoidance — TCP meets it. The argument is geometric: additive increase moves both connections' throughputs up along a slope of 1, and multiplicative decrease scales both down proportionally, so the pair converges toward the equal-share point. In practice the assumptions do not hold, and two routes around fairness break no rules at all. An application can open parallel connections: on a link with 9 existing connections, an application that asks for 1 gets R/10, while one that opens 11 gets R/2, and browsers do exactly this. Or an application can use UDP, as multimedia applications often do, precisely so that nothing throttles their rate. No Internet police enforce the use of congestion control. The Internet works as well as it does substantially because the dominant implementations choose to be polite.

Exercises

Complete these before or around the next class. Write down your prediction before you run anything, then run it and record what actually happened; a prediction that turns out wrong teaches more than one that turns out right, as long as you can explain why it was wrong.

  1. Watch the byte stream erase your message boundaries. Alter send_tcp.py to send five extra messages quickly after the "Hello, Server!" message; name them message0 through message4. Alter receive_tcp.py to sleep for three seconds after a client connects, which gives several segments from the client time to arrive, and then to call recv and print the bytes it received. Describe what happened.

    Then answer the design question: if bytes from multiple segments arrive concatenated in the stream, how can an application tell where one message ends and the next begins? Name two workable mechanisms. Compare your answer to the one you wrote down for the same question about UDP last class, and say why the two answers differ.

    Watch the whole exchange in Wireshark. Find the three-way handshake, the segments carrying your messages, and the connection teardown.

  2. Open vibrantcloud.pcapng in Wireshark and find the three-way handshake. Identify both initial sequence numbers and verify that each acknowledgement number is what the byte counts predict.
  3. Do the same with a capture of your own: start Wireshark, browse to vibrantcloud.org, and filter on the server's address. Compare your ports and sequence numbers to the walkthrough above. How many segments did your browser need, and how does that number compare to the seven in these notes?
  4. In tcp-wireshark-trace1-1.pcapng, look for retransmissions and duplicate acknowledgements. Where a retransmission occurred, can you tell whether a timeout or triple duplicate acknowledgements triggered it?
  5. Work out the selective repeat dilemma for yourself: with a four-value sequence space, what is the largest window size that is always safe, and why?

Terms

Not a comprehensive reference — the textbook has much more — but these are the terms from Day 6 that recur throughout the course.

listening socket
The socket a TCP server binds to a well-known port and marks with listen. It accepts connections but carries no data; accept returns a separate socket for each connection.
4-tuple
Source IP address, source port, destination IP address, and destination port: the four values that uniquely identify one TCP connection socket, and so let one server port serve many clients at once.
byte stream
TCP's data model: a reliable, in-order sequence of bytes with no message boundaries. One recv may return bytes from several segments, or part of one. Applications needing framing must supply it themselves.
full duplex
Data flowing in both directions over a single connection.
MSS (maximum segment size)
The largest payload in one TCP segment: the link MTU, 1500 bytes on Ethernet, minus the 20-byte TCP and 20-byte IP headers, typically 1460 bytes. Announced in a header option during the handshake.
sequence number
In TCP, the byte-stream number of a segment's first data byte. Each side picks a random starting value and increments by bytes sent, not segments sent.
acknowledgement number
The next byte the receiver expects, which equals the other side's starting sequence number plus one plus the bytes received so far.
offset (header length)
The TCP header length in 32-bit words; multiply by 4 for bytes. Options make a TCP header vary from 20 to 60 bytes, so the receiver needs this field to find where the Layer 7 message begins. UDP needs no equivalent, since its payload always starts at the ninth byte.
flags
Single header bits: C congestion, E ECN, U urgent, A acknowledgement, P push, R reset, S SYN, F FIN.
three-way handshake
SYN, SYN ACK, ACK: establishing a connection and exchanging random initial sequence numbers. Three messages are needed so that each side knows the other knows. Random starting numbers guard against stale packets from a prior connection.
SYN, FIN, RST
TCP header flag bits for opening a connection, closing one direction of one, and resetting one. A close takes four segments, a FIN and an ACK in each direction.
cumulative ACK
ACK(n) acknowledges every byte up to and including n, which means a later acknowledgement covers an earlier one that was lost.
duplicate ACK
A repeated acknowledgement for the same next-expected byte, sent when an out-of-order segment reveals a gap. It carries the information a NAK would.
fast retransmit
Resending the oldest unacknowledged segment after three duplicate acknowledgements rather than waiting for a timeout, since three later segments arriving implies the missing one was lost.
timeout and timer
The sender's mechanism for detecting loss: retransmit if no acknowledgement arrives within a reasonable interval, which must be at least an RTT plus the receiver's processing time.
flow control and rwnd
Preventing a sender from overflowing the receiver's buffer. The receiver advertises free buffer space in the header's receive window field and the sender caps its in-flight data accordingly. Distinct from congestion control.
pipelining
Allowing multiple transmitted but unacknowledged segments in flight, which requires a wider sequence space and buffering. Multiplies utilization by the number of packets in flight.
window
The set of sequence numbers a sender may have outstanding at once.
Go-Back-N (GBN)
Pipelined protocol with a single timer for the oldest unacknowledged packet; on timeout it retransmits that packet and all higher-numbered packets in the window. Simple receiver, but it retransmits packets that arrived intact.
selective repeat (SR)
Pipelined protocol in which the receiver acknowledges packets individually and buffers out-of-order ones, while the sender keeps a timer per packet and retransmits only what is missing. More state, less wasted capacity. The window must be at most half the sequence space to avoid ambiguity.
C10k problem
The difficulty of serving ten thousand concurrent connections on one machine. A thread per connection means a stack per connection, which is what the event-loop architecture avoids.
thread per connection
Server architecture in which accept hands each new socket to its own thread, which blocks in a recv loop. Simple to write; costs one stack per client. Apache works this way.
event loop
Server architecture in which a few non-blocking workers ask the OS which sockets are ready — through epoll, kqueue, or select — and service only those. Scales much further; requires tracking each connection's state explicitly. nginx works this way.
SO_REUSEADDR
A socket option letting a server bind its port again immediately after a restart instead of waiting out TIME_WAIT, roughly 60 seconds.
sendall versus send
sendall loops until it has sent every byte; send returns the number of bytes sent and leaves the remainder to the caller.
rdt and udt
Reliable data transfer, the Layer 4 service we build, and unreliable data transfer, the Layer 3 service beneath it. Interface calls: rdt_send, udt_send, rdt_rcv, deliver_data.
finite state machine (FSM)
A protocol specification technique: states in which the next event determines the next state, with transitions labeled by event and action.
ACK and NAK
Receiver messages reporting that a packet arrived correctly, or that it had errors. TCP is NAK-free, since a duplicate ACK carries the same information.
stop-and-wait
Sending one packet and waiting for a response before sending another. Correct but highly inefficient, with utilization (L/R)/(RTT + L/R), which is 0.00027 on a 1 gbps link with a 15 ms propagation delay.
utilization
The fraction of time the sender is busy sending.
congestion
Too many sources sending too fast for the network, appearing as queueing delay and buffer-overflow loss.
end-to-end versus network-assisted congestion control
Inferring congestion from observed loss and delay with no help from the network, which is TCP's approach, versus routers signaling congestion to hosts explicitly, as ECN does.
cwnd
The congestion window: the sender's self-imposed cap on unacknowledged data, so that rate ≈ cwnd/RTT. The effective limit is the smaller of cwnd and rwnd.
AIMD
Additive increase, multiplicative decrease: one MSS more per RTT until loss, then halve. Produces the sawtooth. Halve on triple duplicate ACKs; drop to 1 MSS on timeout.
slow start and ssthresh
At connection start, cwnd begins at 1 MSS and doubles every RTT until it reaches ssthresh, the slow start threshold, which TCP sets to half of cwnd at each loss event. Above ssthresh TCP is in congestion avoidance and grows linearly.
ECN (explicit congestion notification)
Routers mark two bits in the IP header to signal congestion; the destination echoes the signal in the TCP header's C and E bits, so the sender learns without a loss occurring.

Credit: Most information on this page is from Computer Networking: A Top-Down Approach, 9th edition by Kurose and Ross.
This page was generated by Claude from in-class slides.