1 15-744: Computer Networking L-4 TCP 2 This Lecture: Congestion Control • Congestion Control • Assigned Reading • [Chiu & Jain] Analysis of Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks • [Jacobson and Karels] Congestion Avoidance and Control 3 Introduction to TCP • Communication abstraction: • Reliable • Ordered • Point-to-point • Byte-stream • Full duplex • Flow and congestion controlled • Protocol implemented entirely at the ends • Fate sharing • Sliding window with cumulative acks • Ack field contains last in-order packet received • Duplicate acks sent when out-of-order packet received Key Things You Should Know Already • Port numbers • TCP/UDP checksum • Sliding window flow control • Sequence numbers • TCP connection setup • TCP reliability • Timeout • Data-driven 42 5 Overview • Congestion sources and collapse • Congestion control basics • TCP congestion control • TCP modeling 6 Internet Pipes? • How should you control the faucet? 7 Internet Pipes? • How should you control the faucet? • Too fast – sink overflows! 8 Internet Pipes? • How should you control the faucet? • Too fast – sink overflows! • Too slow – what happens?3 9 Internet Pipes? • How should you control the faucet? • Too fast – sink overflows • Too slow – what happens? • Goals • Fill the bucket as quickly as possible • Avoid overflowing the sink • Solution – watch the sink 10 Plumbers Gone Wild! • How do we prevent water loss? • Know the size of the pipes? 11 Plumbers Gone Wild 2! • Now what? • Feedback from the bucket or the funnels? 12 Congestion • Different sources compete for resources inside network • Why is it a problem? • Sources are unaware of current state of resource • Sources are unaware of each other • In many situations will result in < 1.5 Mbps of throughput (congestion collapse) 10 Mbps 100 Mbps 1.5 Mbps4 13 Causes & Costs of Congestion • Four senders – multihop paths • Timeout/retransmit Q: What happens as rate increases? 14 Causes & Costs of Congestion • When packet dropped, any “upstream transmission capacity used for that packet was wasted! 15 Congestion Collapse • Definition: Increase in network load results in decrease of useful work done • Many possible causes • Spurious retransmissions of packets still in flight • Classical congestion collapse • How can this happen with packet conservation • Solution: better timers and TCP congestion control • Undelivered packets • Packets consume resources and are dropped elsewhere in network • Solution: congestion control for ALL traffic 16 Other Congestion Collapse Causes • Fragments • Mismatch of transmission and retransmission units • Solutions • Make network drop all fragments of a packet (early packet discard in ATM) • Do path MTU discovery • Control traffic • Large percentage of traffic is for control • Headers, routing messages, DNS, etc. • Stale or unwanted packets • Packets that are delayed on long queues • “Push” data that is never used5 17 Where to Prevent Collapse? • Can end hosts prevent problem? • Yes, but must trust end hosts to do right thing • E.g., sending host must adjust amount of data it puts in the network based on detected congestion • Can routers prevent collapse? • No, not all forms of collapse • Doesn’t mean they can’t help • Sending accurate congestion signals • Isolating well-behaved from ill-behaved sources 18 Congestion Control and Avoidance • A mechanism which: • Uses network resources efficiently • Preserves fair network resource allocation • Prevents or avoids collapse • Congestion collapse is not just a theory • Has been frequently observed in many networks Approaches Towards Congestion Control • End-end congestion control: • No explicit feedback from network • Congestion inferred from end-system observed loss, delay • Approach taken by TCP • Network-assisted congestion control: • Routers provide feedback to end systems • Single bit indicating congestion (SNA, DECbit, TCP/IP ECN, ATM) • Explicit rate sender should send at • Problem: makes routers complicated 19 • Two broad approaches towards congestion control: 20 Example: TCP Congestion Control • Very simple mechanisms in network • FIFO scheduling with shared buffer pool • Feedback through packet drops • TCP interprets packet drops as signs of congestion and slows down • This is an assumption: packet drops are not a sign of congestion in all networks • E.g. wireless networks • Periodically probes the network to check whether more bandwidth has become available.6 21 Overview • Congestion sources and collapse • Congestion control basics • TCP congestion control • TCP modeling 22 Objectives • Simple router behavior • Distributedness • Efficiency: Xknee = Σxi(t) • Fairness: (Σxi)2/n(Σxi2) • Power: (throughputα/delay) • Convergence: control system must be stable 23 Basic Control Model • Let’s assume window-based control • Reduce window when congestion is perceived • How is congestion signaled? • Either mark or drop packets • When is a router congested? • Drop tail queues – when queue is full • Average queue length – at some threshold • Increase window otherwise • Probe for available bandwidth – how? 24 Linear Control • Many different possibilities for reaction to congestion and probing • Examine simple linear controls • Window(t + 1) = a + b Window(t) • Different ai/bi for increase and ad/bd for decrease • Supports various reaction to signals • Increase/decrease additively • Increased/decrease multiplicatively • Which of the four combinations is optimal?7 25 Phase plots • Simple way to visualize behavior of competing connections over time Efficiency Line Fairness Line User 1’s Allocation x1 User 2’s Allocation x2 26 Phase plots • What are desirable properties? • What if flows are not equal? Efficiency Line Fairness Line User 1’s
View Full Document
Unlocking...