§labChapter 3 Labs, the rdt Assignment and Interview

The lab’s questions, answered from this trace

What are the port numbers, and the initial sequence numbers? The client uses ephemeral port 52310 and the server the well-known port 80. The client’s initial sequence number is 1,798,242,560 and the server’s is 2,753,396,224. They are unrelated, and each side chose its own — section 3.5.6 explains why they must be hard to guess. Wireshark renumbers both to start at 0, which is why packet 1 reads Seq=0.

What is the maximum segment size? 1,460 bytes, announced by both sides as an option on their SYN (synchronize) synchronize The TCP flag bit that marks a connection-establishment segment. Set in the first two segments of the three-way handshake (§3.5.6). introduced in ch. 3 . It is 1,500 − 20 − 20: an Ethernet frame’s payload, less the IP (Internet Protocol) Internet Protocol The network-layer protocol that defines the datagram format and addressing every Internet device must use. introduced in ch. 1 header and the TCP header.

What is the estimated round-trip time? Read it off any pair. Packet 4 goes out at 0.0603 and its acknowledgement, packet 5, arrives at 0.1205. The difference is 60.2 ms, and it is the same for every other pair in the trace.

Where is congestion control? In the shape of the sending. One segment (packet 4), then two (packets 6 and 7), then four (packets 10 to 13). That is slow start slow start Simple The opening phase, where the window doubles every round trip — anything but slow. Precise The state a TCP connection begins in. cwnd starts at a small value and grows by one MSS for every segment first acknowledged, which doubles the sending rate every round-trip time. It ends when cwnd reaches ssthresh, when a timeout occurs (cwnd returns to 1 MSS and slow start restarts), or when three duplicate acknowledgements arrive (TCP moves to fast recovery). The name refers to starting from 1 MSS, not to the growth rate. introduced in ch. 3 — open in glossary doubling the congestion window each round trip, exactly as in section 3.7.1. Nothing in any header says so — the congestion window is never transmitted. You are inferring it from the timing, which is what the lab is training you to do.

Where is flow control? In the receive-window field. It sits at 64,240 bytes until packet 16, then falls to 62,780, 61,320 and 59,860 — down exactly 1,460 each time — and returns to 64,240 at packet 20. Section 3.5.5 says the receive window is the free space in the receive buffer, and here you can watch it being consumed.

Where is retransmission? Packet 19, and the four packets before it explain why.

The recovery, packet by packet

Two things are worth sitting with.

Packet 19 follows packet 18 immediately. No timer expired. The sender acted on the third duplicate, which is the entire point of the mechanism.

Packet 20 jumps 5,840 bytes. The receiver had bytes 7301 through 11680 the whole time and could not say so, because a cumulative acknowledgement cannot name anything past a gap. The moment the hole was plugged, all four segments became deliverable at once — and the receive window snapped back to 64,240 because those bytes finally left the buffer.

That is section 3.5.4 and section 3.5.5 in the same two numbers.

The four fields, and nothing else

Eight bytes of header in total, against TCP’s twenty. There is no sequence number, no acknowledgement number, no receive window and no flags, because UDP does none of the things those fields exist for.

Two details that catch people out.

The length includes the header. 26, not 18. So the payload is always length − 8.

The source port is optional. UDP allows it to be zero when no reply is wanted. Here it is filled in, because the client wants the shouted sentence back.

The checksum, computed

Section 3.3.2 says the checksum covers the UDP header, the data, and a pseudo-header borrowed from the IP header. Here is the whole sum for packet 1, word by word.

The pseudo-header — source address, destination address, a zero byte, the protocol number and the UDP length:

0xc0a8  192.168 — source address, high half
0x0118  .1.24   — source address, low half
0xc633  198.51  — destination address, high half
0x6407  .100.7  — destination address, low half
0x0011  zero byte, then protocol 17 (UDP)
0x001a  UDP length, 26

The UDP header — with the checksum field taken as zero while computing:

0xcaa1  source port 51873
0x2ee0  destination port 12000
0x001a  length 26

The data — “hello from bangkok”, two characters per word:

0x6865 "he"   0x6c6c "ll"   0x6f20 "o "
0x6672 "fr"   0x6f6d "om"   0x2062 " b"
0x616e "an"   0x676b "gk"   0x6f6b "ok"

Add all of those with end-around carry — every carry out of the top bit is added back at the bottom — and the total is

0x583c

Invert every bit:

~0x583c = 0xa7c3

which is exactly what the checksum field contains.

Now check it the way the receiver does. Add the same words again, this time including the checksum:

0x583c + 0xa7c3 = 0xffff

All ones. That single test is why the sender inverts the sum instead of sending it directly — the receiver looks for one fixed pattern rather than comparing two numbers. Problem P3 asks you to prove that, and problem P4(c) asks you to break it.

The four lines that matter

if A['waiting']: return — stop-and-wait, enforced. The layer above is told nothing; the simulator simply retries later. This is the rdt_unable_to_send of problem P17.

if corrupt(pkt) or pkt['ack'] != A['seq']: return — the sender ignores anything unexpected. It does not retransmit. Problem P12 shows what happens if you retransmit here instead: the protocol stays correct and its cost grows without bound.

tolayer3('A', A['last']) — a timeout resends the stored packet, byte for byte. Rebuilding it would be a bug: the sequence number must not change.

The else branch in B_input — a duplicate or corrupted packet still gets an acknowledgement, naming the previous sequence number. Staying silent would deadlock the sender, which is exactly the failure problem P6 asks you to construct.

Three traps in the Go-Back-N version

One timer, not N. Go-Back-N has a single timer, and it belongs to the oldest unacknowledged packet. Start it when base == nextseq before sending; restart it whenever base moves and packets remain. Giving each packet its own timer turns this into Selective Repeat, which is a different assignment.

Compare sequence numbers modulo the space, never with <. A['nextseq'] - A['base'] < N is wrong the moment the numbers wrap. Every comparison here is written (x - y) % SEQSPACE, and that is not fussiness — it is the bug that makes this lab take an extra evening.

The receiver still discards out-of-order packets, and still replies. The if has no else that skips the acknowledgement. Every arriving packet gets one, and a discarded packet gets a repeat of the last good one. That repeat is what lets the sender’s window advance when an acknowledgement was lost — review question R12(b) is exactly this case.

Voices from the field

Van Jacobson works at Google and was previously a Research Fellow at PARC (Palo Alto Research Center) Palo Alto Research Center Xerox's research centre, where Metcalfe and Boggs invented Ethernet in the mid-1970s. introduced in ch. 6 . Before that he was co-founder and Chief Scientist of Packet Design, and Chief Scientist at Cisco. Earlier still he headed the Network Research Group at Lawrence Berkeley National Laboratory and taught at UC Berkeley and Stanford.

He received the ACM SIGCOMM Award in 2001 for outstanding lifetime contribution to the field. He received the IEEE (Institute of Electrical and Electronics Engineers) Institute of Electrical and Electronics Engineers The body whose 802 committee standardises Ethernet and WiFi. introduced in ch. 1 Kobayashi Award in 2002 for “contributing to the understanding of network congestion and developing congestion control mechanisms that enabled the successful scaling of the Internet”. He was elected to the U.S. National Academy of Engineering in 2004.

Please describe one or two of the most exciting projects you have worked on during your career. What were the biggest challenges?

School teaches us lots of ways to find answers. In every interesting problem I’ve worked on, the challenge has been finding the right question. When Mike Karels and I started looking at TCP congestion, we spent months staring at protocol and packet traces asking “Why is it failing?”. One day in Mike’s office, one of us said “The reason I can’t figure out why it fails is because I don’t understand how it ever worked to begin with.” That turned out to be the right question and it forced us to figure out the “ack clocking” that makes TCP work. After that, the rest was easy.

More generally, where do you see the future of networking and the Internet?

For most people, the Web is the Internet. Networking geeks smile politely since we know the Web is an application running over the Internet but what if they’re right? The Internet is about enabling conversations between pairs of hosts. The Web is about distributed information production and consumption. “Information propagation” is a very general view of communication of which “pairwise conversation” is a tiny subset. We need to move into the larger tent. Networking today deals with broadcast media (radios, PONs, etc.) by pretending it’s a point-to-point wire. That’s massively inefficient. Terabits-per-second of data are being exchanged all over the World via thumb drives or smart phones but we don’t know how to treat that as “networking”. ISPs are busily setting up caches and CDNs to scalably distribute video and audio. Caching is a necessary part of the solution but there’s no part of today’s networking — from Information, Queuing or Traffic Theory down to the Internet protocol specs — that tells us how to engineer and deploy it. I think and hope that over the next few years, networking will evolve to embrace the much larger vision of communication that underlies the Web.

What people inspired you professionally?

When I was in grad school, Richard Feynman visited and gave a colloquium. He talked about a piece of Quantum theory that I’d been struggling with all semester and his explanation was so simple and lucid that what had been incomprehensible gibberish to me became obvious and inevitable. That ability to see and convey the simplicity that underlies our complex world seems to me a rare and wonderful gift.

What are your recommendations for students who want careers in computer science and networking?

It’s a wonderful field — computers and networking have probably had more impact on society than any invention since the book. Networking is fundamentally about connecting stuff, and studying it helps you make intellectual connections: Ant foraging & Bee dances demonstrate protocol design better than RFCs, traffic jams or people leaving a packed stadium are the essence of congestion, and students finding flights back to school in a post-Thanksgiving blizzard are the core of dynamic routing. If you’re interested in lots of stuff and want to have an impact, it’s hard to imagine a better field.