1 of 25

CS118 Dis 1EF, Week 4

Xinyu Ma

2 of 25

Contents

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

2

3 of 25

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

4 of 25

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 |

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

5 of 25

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

6 of 25

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

7 of 25

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

8 of 25

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

9 of 25

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

10 of 25

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

11 of 25

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

12 of 25

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

13 of 25

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

14 of 25

Connection Setup

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

14

FYI

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

15 of 25

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

16 of 25

Simultaneous Close (FYI)

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

16

FIN

FIN

FIN-ACK

FIN-ACK

wait

wait

17 of 25

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

18 of 25

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

19 of 25

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

20 of 25

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

21 of 25

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

22 of 25

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

23 of 25

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

24 of 25

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

25 of 25

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