Discussion 6

1

CS 168, Spring 2026 @ UC Berkeley

Slides credit: Sylvia Ratnasamy, Rob Shakir, Peyrin Kao, Iuniana Oprescu

Reliable Delivery, TCP 📆

Logistics

• Midterm on March 20th, 7-9pm (put it in your calendar)!
• Exam Logistics
• Accommodations form
• Can still submit late but no guarantees

​

TCP

• TCP Header
• Connection Establishment
• Teardown
• Reliability

Reliability

• Best-effort network
• Need to handle packet loss, corruption, reordering, delays, duplications, etc.
• Building blocks
• Checksums: detect corruption
• Feedback: positive/negative feedback from receiver
• Retransmissions: sender re-sends packets
• Timeouts: when to resend a packet
• Sequence numbers: indicate which packets have been received
• Design considerations
• Window size, nature of feedback, detection of loss, response to loss

Go-Back-N

• Simple (though not advisable algorithm)
• “Sliding window” protocol: sender keeps a window of up to W transmitted but unACKed packets

​

​

​

​

• Timer for oldest in-flight packet
• On timeout, resend all W packets (starting with the lost one)
• Receiver discards out-of-order packets

Kurose Ross, Computer Networking: A Top-down Approach, Chapter 3

Not what TCP does, but useful as a starting point to figure out something better.

Go-Back-N w/o Errors

Window

S=1

S=2

S=3

S=4

A=1

A=2

A=3

A=4

Go-Back-N w/o Errors

Window

S=1

S=2

S=3

S=4

A=1

A=2

A=3

A=4

S=5

Go-Back-N w/o Errors

Window

S=1

S=2

S=3

S=4

A=1

A=2

A=3

A=4

S=5

S=6

Go-Back-N w/o Errors

Window

S=1

S=2

S=3

S=4

A=1

A=2

A=3

A=4

S=5

S=6

S=7

A=5

Go-Back-N w/o Errors

Window

S=1

S=2

S=3

S=4

A=1

A=2

A=3

A=4

S=5

S=6

S=7

S=8

A=5

A=7

A=8

A=6

…

Go-Back-N w/ Errors

S=1

S=2

S=3

S=4

A=1

A=2

A=3

A=4

S=5

S=6

S=7

S=8

A=5

A=5

A=5

Packet 6 timeout

S=9

S=6

S=7

S=8

S=9

A=6

A=7

A=8

A=9

Window: {1 2 3 4}

{1 2 3 4}

{1 2 3 4}

{1 2 3 4}

{2 3 4 5}

{3 4 5 6}

{4 5 6 7}

{5 6 7 8}

{6 7 8 9}

Review

TCP

• L4 Protocol (Transport)
• Byte Stream
• Bi-directional
• Reliable
• In-order

Source port

TCP Header

• Host port numbers
• Multiplexing and demultiplexing
• 16 bits

​

• But wait - why no address?!
• IP header has address.

​

TCP Header

• Byte offset
• Of first payload byte
• Initialized randomly

​

• Byte Stream Protocol
• Seq # refers to bytes

​

TCP Header

• Header length
• 4 bits
• In 4-byte words
• Minimum 5 words (20B)
• Maximum 15 words
• Why?
• Only 4 bits, so max is 2^4 – 1 = 15 words

TCP Header

• SYN
• SYNchronize initial state
• ACK
• ACKnowledgement
• FIN
• No more data
• RST
• Connection ReSeT

TCP Header

• Receive Window Size
• Maximum receiver buffer
• Limits sending rate
• Don’t send faster than receiver can process

TCP Header

• Checksum
• Includes header and payload
• Options common
• Unlike IP
• Not covered
• Assume no options unless specified

TCP Segments

TCP/IP packet: IP packet with TCP header and TCP data inside.

Size limits:

• IP packet: Maximum transmission unit (MTU).
• TCP segment: Maximum segment size (MSS).
• MSS = MTU – (IP header) – (TCP header).

TCP Header

TCP Payload (Segment)

IP Header

TCP

• TCP Header
• Connection Establishment
• Teardown
• Reliability

Three Way Handshake

• Client sends server a SYN
• A TCP packet with the SYN flag set
• SYN packet carries initial state
• Receive window
• Source port number
• Initial sequence number

Three Way Handshake

• Server responds with a SYN-ACK
• Acknowledge the client’s SYN
• Respond with the server’s own SYN
• Carries server’s initial state
• Receive window
• Source port number
• Initial sequence number

Three Way Handshake

• Client responds with an ACK
• Now the connection is established!
• Client and server can freely communicate

Connection Establishment

• Sequence number and acknowledgement number don’t start from zero
• Instead client and server choose a random initial seq #
• Why?
• Must be communicated between client and server

Connection Establishment

• Client/Server exchange state
• Initial Sequence numbers
• Port number
• TCP Options

TCP

• TCP Header
• Connection Establishment
• Teardown
• Reliability

Two Teardown Methods

• Four way handshake
• Graceful/normal teardown
• Reset
• Exceptional Teardown

Normal Teardown

• One side closes their connection
• Indicates they will send no more data
• Sends a FIN
• Receives an ACK
• Other side may continue transmitting
• Eventually it closes as well
• Sends a FIN
• Receives an ACK
• Connection is closed

TCP Reset

• Reset the connection
• Most commonly, attempt to SYN on a closed port
• Send RST packet(s) only (no ACK)

TCP

• TCP Header
• Connection Establishment
• Teardown
• Reliability

Reliability

• Cumulative ACKs
• Allow detection of dropped packets
• How do we know a packet was lost?
• Timeout
• Duplicate ACKs

Timeout

• Retransmission Time Out (RTO)
• Timeout after which packets are retransmitted
• Based on a constantly updated RTT estimate (and variance)
• Single timer (not per-packet)
• Each received ACK of new data resets RTO
• If RTO times out
• Retransmit packet containing “next byte”

Timeout

• What if RTO is too large?
• Packet is dropped . . .
• Wait
• Keep waiting
• … Keep waiting
• Timer goes off
• Finally retransmit
• Can we do better?

Duplicate ACKs

• Transmit
• Seq 1000
• Seq 2000
• Seq 3000 Dropped in flight
• Seq 4000
• Seq 5000
• Seq 6000
• What ACKs do we receive?
• ACK 2000
• ACK 3000
• ACK 3000
• ACK 3000
• ACK 3000
• Duplicate ACKs indicate packet loss/reorder

Worksheet

• TCP in Action
• TCP Calculations
• Reliable Transport

Question 1: TCP in Action

Question 1: TCP in Action

Question 1: TCP in Action

​

D100

D200

D300

X

A200

Timer start (A200)

A200

D400

A200

.

.

.

TO

D200

A500

Time-out! Retransmit

1 RTT

1 RTT

Note: The question assumes each batch is sent/received at the same time, but they are shown separately for readability

Question 1: TCP in Action

​

1 RTT

A600

D500

A700

D600

D700

X

Timer start (A700)

A700

D800

A700

D900

D700

A1000

Time-out! Retransmit

TO

1 RTT

.

.

.

Note: The question assumes each batch is sent/received at the same time, but they are shown separately for readability

Question 1: TCP in Action

1 RTT

A1100

D1000

Total Time = RTT + TO + RTT + RTT + TO + RTT + RTT

= 5 * RTT + 2 * TO

= 6.05 seconds

Worksheet

• TCP in Action
• TCP Calculations
• Reliable Transport

Question 2: TCP Calculations

Question 2: TCP Calculations

Question 2: TCP Calculations

Worksheet

• TCP in Action
• TCP Calculations
• Reliable Transport

Question 3: Reliable Transport

Question 3: Reliable Transport

Question 3: Reliable Transport

Question 3: Reliable Transport

Questions?

Feedback Form: https://tinyurl.com/cs168-su25-disc-feedback