CS118 Dis 1EF, Week 4

Xinyu Ma

Contents

• TCP
• Protocol
• Congestion Control
• Some old problems
• Midterm

2

TCP

• TCP provides
• End-to-end “pipe” connection
• Bit stream
• Reliability
• TCP is built on IP
• A graph of nodes identified by IP address
• Packet
• What TCP needs to do
• Port number -> identify process
• Connection -> Setup, shutdown
• Pack bits into packets
• Buffer -> flow control
• Checksum -> Integrity
• ACK, SEQ -> In order delivery, retransmission
• Congestion control

3

Client

Server

TCP Model

A pipeline of bits

IP Model

A graph, that packets go through

Packet format

• Window is recv window size
• SYN,RST,FIN for connection mgmt

4

0 1 2 3

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Source Port | Destination Port |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Sequence Number |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Acknowledgment Number |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Data | |U|A|P|R|S|F| |

| Offset| Reserved |R|C|S|S|Y|I| Window |

| | |G|K|H|T|N|N| |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Checksum | Urgent Pointer |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Options | Padding |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| data |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Minimum Size

• The smallest TCP segment size is 20B

5

0 1 2 3

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Source Port | Destination Port |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Sequence Number |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Acknowledgment Number |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Data | |U|A|P|R|S|F| |

| Offset| Reserved |R|C|S|S|Y|I| Window |

| | |G|K|H|T|N|N| |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Checksum | Urgent Pointer |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Options | Padding |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| data |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

4x5

Old Quiz

• Please mark all the correct statement(s) below.
• UDP header has a fixed size.
• 8B (2 ports + length + checksum)
• TCP header has a fixed size.
• Has options
• UDP establishes an unreliable connection between the two ends.
• UDP is connectionless
• TCP establishes a reliable connection between the two ends.
• ​

6

TCP

• Process identification
• (Src IP, Src Port, Dst IP, Dst Port) tuple decides a connection
• OS allocates buffer and file descriptor (socket) for each connection
• Flow control
• (send) Nagle’s algorithm combines bytes into packets
• (recv) Take out bytes from OS buffer
• The same buffer used for both flow control and congestion control
• But different windows
• Sender can send min(rwnd,cwnd)

7

(FYI) Nagle’s Algorithm

A segment is sent when any of:

1. Data to be sent > MSS (Maximum Segment Size)
2. No data to be ACKed
3. Received an ACK
4. Time out

Retransmission

• ACK
• SEQ of the first desired byte (recved SEQ + data size)
• Add 1 after SYN / FIN without data
• Retransmission timer (RTO)
• Too early -> Unnecessary traffic
• Too late -> Wait longer
• Adjusted based on estimated RTT
• Typically set to a long value
• Fast retransmission
• Upon 3rd duplicate ACK
• NOT including the original one

8

Congestion Control (slow start w/ cong. avoidance)

• AIMD (cwnd >= ssthresh)
• cwnd += 1MSS when all data in last RTT are ACKed
• cwnd += 1/cwnd ( (1MSS)^2/cwnd in Byte)
• ​
• Retransmission timer (RTO)
• ssthresh = cwnd / 2
• cwnd = 1MSS
• Go back to Slow Start
• ​
• Fast retransmission & recovery (3 dup ack)
• ssthresh = cwnd / 2
• cwnd = cwnd / 2
• Stay in Congestion Avoidance

​

• Slow Start (cwnd < ssthresh)
• cwnd += 1 for every ACK
• This doubles the cwnd per RTT
• The rest of Fast Recovery is FYI

​

​

​

• Throughput = 0.75 W/RTT

9

Old Homework

• The time periods of Slow Start?
• The time periods of AIMD?
• Which losses were detected by RTO?
• Which losses were detected by Fast Ret.?
• For each loss, identify the ssthresh

10

Old Homework

• The time periods of Slow Start?
• 1-6, 22-25
• The time periods of AIMD?
• 6-22
• Which losses were detected by RTO?
• Which losses were detected by Fast Ret.?
• For each loss, identify the ssthresh
• ​

11

Old Homework

• The time periods of Slow Start?
• 1-6, 22-25
• The time periods of AIMD?
• 6-22
• Which losses were detected by RTO?
• 0, 21
• Which losses were detected by Fast Ret.?
• 12, 18
• For each loss, identify the ssthresh
• ​

12

Old Homework

• The time periods of Slow Start?
• 1-6, 22-25
• The time periods of AIMD?
• 6-22
• Which losses were detected by RTO?
• 0, 21
• Which losses were detected by Fast Ret.?
• 12, 18
• For each loss, identify the ssthresh
• t=0, ssthresh=40/2=20
• t=12, ssthresh=70/2=35
• t=18, ssthresh=40/2=20
• t=21, ssthresh=22/2=11

13

Connection Setup

• Client: SYN
• SYN
• SEQ = random number r_c
• No data
• Server: SYN-ACK/SYN
• SYN, ACK = r_c + 1
• SEQ = random number r_s
• No data
• Client: SYN-ACK
• ACK = r_s + 1
• SEQ = r_c + 1
• May carry data

14

FYI

Every packet that needs to be ACKed will take a SEQ.

Connection Close

• Does not distinguish client & server
• Inform the other side “no more data”
• A sends FIN
• FIN (may have ACK)
• SEQ = a
• B sends FIN-ACK
• ACK = a+1 (may have FIN)
• SEQ = ? (maybe b, maybe not)
• May carry data
• B sends FIN
• FIN (may be combined with FIN-ACK)
• SEQ = b
• A sends FIN-ACK
• ACK = b+1
• SEQ = a+1

15

Simultaneous Close (FYI)

If two sides both send FIN, both sides need to wait

16

FIN

FIN

FIN-ACK

FIN-ACK

wait

wait

Old Quiz

• Assume that node A (client) sets up a TCP connection with node B (server)
• The sequence number N carried in A’s TCP SYN segment informs B that N will be used to number the first byte A sends to B.
• The sequence number N carried in A’s TCP SYN segment informs B that (N+1) will be used to number the first byte A sends to B.
• The sequence number N carried in A’s TCP FIN segment informs B that N is the last byte A sends to B.
• The sequence number N carried in A’s TCP FIN segment informs B that (N-1) is the last byte A sends to B.

17

Old Homework

True or False?

• A is sending B a large file over a TCP connection. B has no data to send A. B will not send ACKs to A because B cannot piggyback the ACK on data.
• The size of rwnd never changes throughout the duration of connection
• A is sending B a large file over a TCP connection. UnACKed bytes A sends cannot exceed the size of the recv buffer.

​

​

​

18

Old Homework

True or False?

• A is sending B a large file over a TCP connection. B has no data to send A. B will not send ACKs to A because B cannot piggyback the ACK on data.
• The size of rwnd never changes throughout the duration of connection
• A is sending B a large file over a TCP connection. UnACKed bytes A sends cannot exceed the size of the recv buffer.

• False
• B always need to acknowledge

​

​

• False

​

• True

19

Old Homework

True or False?

• A is sending B a large file over a TCP connection. If SEQ=m for one segment, then the next segment’s SEQ will be m+1.
• TCP header has a field for rwnd
• Suppose last SampleRTT=1ms, then the current RTO will necessarily be >= 1ms
• A sends segment of 4B with SEQ=38. Then B’s ACK for the same segment will necessarily be 42.

​

• ​

​

20

Old Homework

True or False?

• A is sending B a large file over a TCP connection. If SEQ=m for one segment, then the next segment’s SEQ will be m+1.
• TCP header has a field for rwnd
• Suppose last SampleRTT=1ms, then the current RTO will necessarily be >= 1ms
• A sends segment of 4B with SEQ=38. Then B’s ACK for the same segment will necessarily be 42.

• False
• m + size of this segment

​

• True
• False
• SRTT != SampleRTT

​

• False
• There may be unacked segments before

21

Old Homework

• Client A (port: 34679) sends data to server B (port: 2000)
• A picks SYN SEQ 1234, B 5678
• Host A then sends 3 segments: 500B & 500B & 500B.
• No packet loss
• (SrcPort, DstPort) of B’s ACK?
• ​
• SEQ and ACK of the 2nd data segment
• ​
• SEQ and ACK in B’s FIN?
• ​

• ​

22

Old Homework

• Client A (port: 34679) sends data to server B (port: 2000)
• A picks SYN SEQ 1234, B 5678
• Host A then sends 3 segments: 500B & 500B & 500B.
• No packet loss
• (SrcPort, DstPort) of B’s ACK?
• (2000, 34679)
• SEQ and ACK of the 2nd data segment
• (1735, 5679)
• SEQ and ACK in B’s FIN?
• (5679, 2736)

23

A

B

34679

2000

S, seq=1234

SA, seq=5678, ack=1235

A, seq=1235, ack=5679

A, seq=1735, ack=5679

A, seq=2235, ack=5679

A, seq=5679, ack=2735

FA, seq=2735, ack=5679

A, seq=5679, ack=2736

FA, seq=5679, ack=2736

A, seq=2736, ack=5680

Old Homework

• Client A (port: 34679) sends data to server B (port: 2000)
• A picks SYN SEQ 1234, B 5678
• Host A then sends 3 segments: 500B & 500B & 500B.
• B’s FIN segment gets lost, there is only this lost packet. What happens next?
• B will resend its FIN segment.

24

A

B

34679

2000

S, seq=1234

SA, seq=5678, ack=1235

A, seq=1235, ack=5679

A, seq=1735, ack=5679

A, seq=2235, ack=5679

A, seq=5679, ack=2735

FA, seq=2735, ack=5679

A, seq=5679, ack=2736

FA, seq=5679, ack=2736

X

Two stages of congestion

• An extra scenario to the “How network congestion happens” slide
• A packet sends at t=0 will be ACKed by B at t=8ms
• A received this ACK at t=14ms
• 14ms / (1000bits / 1Mbps) = 14
• cwnd = 14 is the best option
• R1-R2 is always full
• If cwnd < 14, throughput < 1Mbps
• If cwnd >= 14, throughput = 1Mbps (max)
• If cwnd <= 14, RTT = 14ms
• If cwnd > 14, RTT > 14ms (congestion@R1)

25

A

B

R1

R2

2Mbps 2ms

1Mbps 2ms

2Mbps 2ms

1000b

1000b

1000b

1000b