15-441 Computer Networking ecture 17-TCP& Congestion Control
15-441 Computer Networking Lecture 17 – TCP & Congestion Control
Good Ideas so far Flow control Stop wait Parallel stop wait Sliding window Loss recovery · Timeouts Acknowledgement-driven recovery(selective repeat or cumulative acknowledgement Lecture 17: TCP Congestion Control
2 Lecture 17: TCP & Congestion Control Good Ideas So Far… • Flow control • Stop & wait • Parallel stop & wait • Sliding window • Loss recovery • Timeouts • Acknowledgement-driven recovery (selective repeat or cumulative acknowledgement)
Outline TCP flow control Congestion sources and collapse Congestion control basics Lecture 17: TCP Congestion Control
3 Lecture 17: TCP & Congestion Control Outline • TCP flow control • Congestion sources and collapse • Congestion control basics
Sequence Numbers (reminder How large do sequence numbers need to be? Must be able to detect wrap-around Depends on sender/receiver window size E.g Max seq=7, send win=recv win=7 If pkts 0. 6 are sent succesfully and all acks lost Receiver expects 7, 0.5, sender retransmits old 0.6! ! Max sequence must be s send window recv window Lecture 17: TCP Congestion Control
4 Lecture 17: TCP & Congestion Control Sequence Numbers (reminder) • How large do sequence numbers need to be? • Must be able to detect wrap-around • Depends on sender/receiver window size • E.g. • Max seq = 7, send win=recv win=7 • If pkts 0..6 are sent succesfully and all acks lost • Receiver expects 7,0..5, sender retransmits old 0..6!!! • Max sequence must be send window + recv window
Sequence Numbers 32 Bits, Unsigned> for bytes not packets! Circular Comparison b Max 0 Max 0 bSending Window +Receiving Window Also, want to guard against stray packets With IP, packets have maximum lifetime of 120s Sequence number would wrap around in this time at 286MB/s=- 2. 3Gbit/s ecture 17: TCP Congestion Control
5 Lecture 17: TCP & Congestion Control Sequence Numbers • 32 Bits, Unsigned → for bytes not packets! • Circular Comparison • Why So Big? • For sliding window, must have • |Sequence Space| > |Sending Window| + |Receiving Window| • No problem • Also, want to guard against stray packets • With IP, packets have maximum lifetime of 120s • Sequence number would wrap around in this time at 286MB/s =~ 2.3Gbit/s (hmm!) Max 0 a b a < b Max 0 b a b < a
TCP FloW Control TCP is a sliding window protocol For window size n, can send up to n bytes without receiving an acknowledgement When the data is acknowledged then the window slides forward Each packet advertises a window size Indicates number of bytes the receiver has space for Original tcp always sent entire window But receiver buffer space I= available net capacity! Congestion control now limits this window= min(receiver window, congestion window) Lecture 17: TCP Congestion Control
6 Lecture 17: TCP & Congestion Control TCP Flow Control • TCP is a sliding window protocol • For window size n, can send up to n bytes without receiving an acknowledgement • When the data is acknowledged then the window slides forward • Each packet advertises a window size • Indicates number of bytes the receiver has space for • Original TCP always sent entire window • But receiver buffer space != available net. capacity! • Congestion control now limits this • window = min(receiver window, congestion window)
Window flow control: send side window Sent and acked Sent but not acked Not yet sent Next to be sent Lecture 17: TCP Congestion Control 7
7 Lecture 17: TCP & Congestion Control Window Flow Control: Send Side Sent but not acked Not yet sent window Next to be sent Sent and acked
Window flow control: send side Packet Sent Packet Received Source Port Dest, Port Source Port Dest. port Sequence Number Sequence Number Acknowledgment Acknowledgment HL/Flags Window HL/Flags Window D Checksum Urgent pointer D Checksum Urgent Pointer Options Options App write acknowledged sent to be sent outside window ecture 17: TCP& Congestion Control
8 Lecture 17: TCP & Congestion Control acknowledged sent to be sent outside window Source Port Dest. Port Sequence Number Acknowledgment HL/Flags Window D. Checksum Urgent Pointer Options… Source Port Dest. Port Sequence Number Acknowledgment HL/Flags Window D. Checksum Urgent Pointer Options... Packet Sent Packet Received App write Window Flow Control: Send Side
Window flow control: receive side What should receiver do? New Receive buffer Acked but not Not yet delivered to user acked window ecture 17: TCP& Congestion Control
9 Lecture 17: TCP & Congestion Control Acked but not delivered to user Not yet acked Receive buffer window Window Flow Control: Receive Side New What should receiver do?
TCP Persist What happens if window is 0? Receiver updates window when application reads data What if this update is lost? TCP Persist state Sender periodically sends 1 byte packets Receiver responds with aCK even if it can 't store the packet Lecture 17: TCP Congestion Control
10 Lecture 17: TCP & Congestion Control TCP Persist • What happens if window is 0? • Receiver updates window when application reads data • What if this update is lost? • TCP Persist state • Sender periodically sends 1 byte packets • Receiver responds with ACK even if it can’t store the packet