DOC PREVIEW
Stanford CS 144 - Congestion Control

This preview shows page 1-2-3-19-20-39-40-41 out of 41 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Lecture 6: Congestion ControlOverview• Internet is a network of networks• Narrow waist of IP: unreliable, best-effortdatagram delivery• Packet forwarding: input port to output port• Routing protocols: computing port mappings• Transport: end-to-end, reliability, flow control, andcongestion controlTransport• Provides end-to-end communication betweenapplications• UDP: unreliable datagram delivery (thin layer ontop of IP)• TCP: reliable stream deliveryTCP• Connection establishment• Connection teardown• Retransmission timeout (RTT and variance)• Flow control (receiver window)• Congestion control (transmit window)TCP• Connection establishment• Connection teardown• Retransmission timeout (RTT and variance)• Flow control (receiver window)• Congestion control (transmit window)A Bit of History• 1974: 3-way handshake• 1978: TCP and IP split into TCP/IP• 1983: January 1, ARPAnet switches to TCP/IP• 1986: Internet begins to suffer congestion collapses• 1987-8: Van Jacobson fixes TCP, publishes seminalpaper (Tahoe)• 1990: Fast recovery and fast retransmit added(Reno)Three questions• Goal: maintain TCP goodput at equilibrium• When does TCP retransmit packets?• When does TCP transmit packets?• When does TCP ack packets?Flow Control• Part of TCP specification (pre-1988)• Want to make sure we don’t send more than whatthe receiver can handle• Sliding window protocol as described in lastlecture• Use window header field to tell other side howmuch space you have• Rule: Sent and unacknowledged bytes ≤ windowTCP segmentpadding0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9 0 10 1 2 3source port destination portsequence numberacknowledgment numberreservedURdataGA P R S FCKSHSTYNINWindowdataoffsetchecksum urgent pointeroptionsSend Timing• Before Tahoe- On connection, nodes send full window of packets- Retransmit packet immediately after its timer expires• Result: window-sized bursts of packets in networkBursts of packetsRetransmission• TCP dynamically estimates round trip time• If segment goes unacknowledged, must retransmit• Use exponential backoff (in case loss fromcongestion)• After ∼10 minutes, give up and reset connectionRound Trip Time (RTT)• We want to estimate RTT so we can know a packetwas likely lost, not just delayed• The challenge is that RTTs for individual packetscan be highly variable, both on long-term andshort-term time scales• Can increase significantly with load!• Solution- Use exponentially weighted moving average (EWMA)- Estimate deviation as well as expected value- Assume packet is lost when time is well beyond reasonabledeviationRTT with EWMA• EstRTT= (1 − α) · EstRTT+ α · SampleRTT- Recommended α is 0.125• DevRTT= (1 − β) · DevRTT+ β · |SampleRTT− EstRTT|- Recommended β is 0.25• Timeout is EstRTT+ 4 · DevRTTOld RTT estimationTahoe RTT estimationSelf-Clocking• Goal is conservation of packets in steady state- A new packet isn’t put into the network until an old oneleaves• Solution: send a data packet for each ackSlow start• But how do you start?• Introduce a congestion window to connection state,cwnd• Rule: Sent and unacknowledged bytes ≤ cwnd• On start or loss, set cwnd to one packet (or... moreon this later)• On each data ack, increase cwnd by one packet• Prevents bursts of packetsWith Slow Start• Slow start allows connection to quickly reachequilibrium• How do we maintain it?Two States• TCP has two states: Slow Start (SS) andCongestion Avoidance (CA)• A window size threshold governs the statetransition- Window ≤ threshold: slow start- Window > threshold: collision avoidance• States differ in how they respond to new acks- Slow start: cwnd += MSS- Congestion avoidance: cwnd +=MSS2cwnd(MSS every RTT)Congestion Control• Two conflicting goals- Provider: high utilization- User: fairness among users• Want to converge to a state where everyone gets1N• Avoid congestion collapseTaming Congestion• The optimal congestion window is thebandwidth/delay product• Sender learns this by adapting window size• Senders must slow down when there is congestion• Absence of ACKs (timeout) implies seriouscongestion• Duplicate ACKs imply some congestionResponding to Loss• Set threshold tocwnd2• On timeout- Set cwnd to 1- Causes TCP to enter slow start• On triple duplicate ACK (Reno)- Set cwnd tocwnd2- Retransmit missing segment- Causes TCP to stay in congestion avoidanceAIMD• Additive increase, multiplicative decrease• Behavior in congestion avoidance mode• Why AIMD? Remember goals:- Link utilization- FairnessAIMD in action30AIMD in Action• Sender searches for correct window size• Figure thanks to Brad KarpChiu Jain Phase PlotsFlow A rate (bps)Flow B rate (bps)Chiu Jain Phase PlotsFlow A rate (bps)Flow B rate (bps)FairA=BChiu Jain Phase PlotsFlow A rate (bps)Flow B rate (bps)FairA=BEfficientA+B=CChiu Jain Phase PlotsFlow A rate (bps)Flow B rate (bps)FairA=BEfficientA+B=CoverloadunderloadChiu Jain Phase PlotsFlow A rate (bps)Flow B rate (bps)FairA=BEfficientA+B=CoverloadunderloadChiu Jain Phase PlotsFlow A rate (bps)Flow B rate (bps)FairA=BEfficientA+B=Coverloadunderloadt1t2t3t4t5t6Chiu Jain Phase PlotsFlow A rate (bps)Flow B rate (bps)FairA=BEfficientA+B=CoverloadunderloadαβThree questions, revisited• Goal: maintain TCP goodput at equilibrium• When does TCP retransmit packets?• When does TCP transmit packets?• When does TCP ack packets?Sending acknowledgements• An ACK must be sent for every other segment(RFC 2581)• An ACK must be sent within 500ms (RFC 2581)• Send duplicate acks aggressivelyAcknowledgement Issues• Savage et al., CCR 1999• ACKs are in terms of bytes• Congestion control is in terms of segments• What if you send multiple ACKs per segment?Multiplicative increase• Receiver can force multiplicative increase, for M ≤segment length• Can lead to 4GB cwnd in 4 RTTs!TCP Daytona!Other details• Persist timer- Sender can block because of 0-sized receive window- Receiver may open window, but ACK message lost- Sender keeps probing (sending one byte beyond window)• Keepalives- Detect dead connection even when no data to send- E.g., remote login server, and client rebooted- Solution: Send “illegal” segments with no data- Remote side will RST (if rebooted), or timeout (if crashed)TCP Extensions• Implemented as header options• Store timestamp in outgoing segments• Extend sequence


View Full Document

Stanford CS 144 - Congestion Control

Documents in this Course
IP Review

IP Review

22 pages

Load more
Download Congestion Control
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Congestion Control and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Congestion Control 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?