Announcements Project 3 should be out tonight Can do individual or in a team of 2 people First phase due November 16 no slip days Exercise good better time management TCP Congestion Control EE 122 Intro to Communication Networks Fall 2006 MW 4 5 30 in Donner 155 Vern Paxson TAs Dilip Antony Joseph and Sukun Kim http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley 1 2 Goals of Today s Lecture State Diagrams For complicated protocols operation depends critically on current mode of operation State diagrams Tool for understanding complex protocols Important tool for capture this state diagram Principles of congestion control Learning that congestion is occurring Adapting to alleviate the congestion At any given time protocol endpoint is in a particular state Dictates its current behavior TCP congestion control Endpoint transitions to other states on events Additive increase multiplicative decrease NACK fast retransmission and timeout based detection Slow start and slow start restart Interaction with lower layer Reception of certain types of packets Interaction with upper layer New data arrives to send or received data is consumed Timers 3 4 5 6 TCP State Diagram 1 How Fast Should TCP Send Flow Control 8 7 Sliding Window TCP Header for Receiver Buffering Allow a larger amount of data in flight Allow sender to get ahead of the receiver though not too far ahead Sending process TCP Destination port Sequence number Advertised window informs sender of receiver s buffer space Receiving process TCP Last byte written Source port Last byte read Acknowledgment HdrLen 0 Flags Advertised window Checksum Urgent pointer Options variable Data Last byte ACKed Sender Window Last byte sent Next byte expected Receiver Window Last byte received 9 10 Advertised Window Limits Rate If the window is W then sender can send no faster than W RTT bytes sec Receiver implicitly limits sender to rate that receiver can sustain If sender is going to fast window advertisements get smaller smaller Termed Flow Control How Fast Should TCP Send In original TCP design that was it sole protocol mechanism controlling sender s rate What s missing Congestion Control 11 12 2 It s Not Just The Sender Receiver Congestion is Unavoidable Flow control keeps one fast sender from overwhelming a slow receiver Two packets arrive at the same time The node can only transmit one and either buffers or drops the other Congestion control keeps a set of senders from overloading the network If many packets arrive in a short period of time The node cannot keep up with the arriving traffic and the buffer may eventually overflow Three congestion control problems Adjusting to bottleneck bandwidth Without any a priori knowledge Could be a Gbps link could be a modem Adjusting to variations in bandwidth Sharing bandwidth between flows 13 Load Delay and Power Typical behavior of queuing systems with bursty arrivals Congestion Collapse Definition Increase in network load results in a decrease of useful work done A simple metric of how well the network is performing Power Average Packet delay 14 Load Delay Due to Undelivered packets Packets consume resources and are dropped later in network Power Spurious retransmissions of packets still in flight Load optimal load Unnecessary retransmissions lead to more load Pouring gasoline on a fire Load Mid 1980s Internet grinds to a halt Goal maximize power 15 Knee point after which Throughput increases very slowly Delay increases quickly Throughput View from a Single Flow knee Until Jacobson Karels devise TCP congestion control 16 General Approaches packet loss cliff congestion collapse Send without care Many packet drops Disaster leads to congestion collapse Cliff point after which Throughput starts to decrease very fast to zero congestion collapse Delay approaches infinity Delay 1 Reservations Pre arrange bandwidth allocations Requires negotiation before sending packets Potentially low utilization difficult to stat mux Load 2 Pricing Load Don t drop packets for the highest bidders Requires payment model 17 18 3 General Approaches cont d Idea of TCP Congestion Control 3 Dynamic Adjustment Probe network to test level of congestion Speed up when no congestion Slow down when congestion Drawbacks Each source determines the available capacity so it knows how many packets to have in flight Congestion window CWND Suboptimal Messy dynamics Seems complicated to implement But clever algorithms actually pretty simple Jacobson Karels 88 All three techniques have their place But for generic Internet usage dynamic adjustment is the most appropriate due to pricing structure traffic characteristics and good citizenship 19 Maximum of unacknowledged bytes to have in flight Congestion control equivalent of receiver window MaxWindow min congestion window receiver window Send at the rate of the slowest component Adapting the congestion window Decrease upon detecting congestion Increase upon lack of congestion optimistic exploration 20 Detecting Congestion How can a TCP sender determine that network is under stress Network could tell it ICMP Source Quench 5 Minute Break Risky because during times of overload the signal itself could be dropped Packet delays go up knee of load delay curve Tricky because a noisy signal delay often varies considerably Questions Before We Proceed Packet loss Fail safe signal that TCP already has to detect Complication non congestive loss checksum errors 22 21 Leads to the TCP Sawtooth Additive Increase Multiplicative Decrease How much to increase and decrease Increase linearly decrease multiplicatively AIMD Necessary condition for stability of TCP Consequences of over sized window much worse than having an under sized window Window Loss Over sized window packets dropped and retransmitted Under sized window somewhat lower throughput Additive increase halved On success for last window of data increase linearly One packet MSS per RTT t Multiplicative decrease On loss of packet divide congestion window in half 23 24 4 Managing the Congestion Window Getting Started Increasing CWND Need to start with a small CWND to avoid overloading the network Increase by MSS on success no loss for last window of data One approach track first packet in flight new window starts when it s ack d at which point CWND MSS Another increase a fraction of MSS per received ACK Window packets and thus ACKs per window CWND MSS Increment per ACK CWND MSS MSS
View Full Document
Unlocking...