Congestion Control
• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 seminar class Active In SP Posts: 5,361 Joined: Feb 2011 23-02-2011, 11:13 AM   05congestion.ppt (Size: 264 KB / Downloads: 206) Congestion Control Outline Queuing Discipline Reacting to Congestion Avoiding Congestion Quality of Service Issues • Two sides of the same coin – pre-allocate resources so at to avoid congestion – control congestion if (and when) is occurs • Two points of implementation – hosts at the edges of the network (transport protocol) – routers inside the network (queuing discipline) • Underlying service model – best-effort – multiple qualities of service (QoS) Framework • Connectionless flows – sequence of packets sent between source/destination pair – maintain soft state at the routers • Taxonomy – router-centric versus host-centric – reservation-based versus feedback-based – window-based versus rate-based Evaluation • Fairness • Power (ratio of throughput to delay) Queuing Discipline • First-In-First-Out (FIFO) – does not discriminate between traffic sources – drop policy (tail-drop, random early drop) • Fair Queuing (FQ) – explicitly segregates traffic based on flows – ensures no flow captures more than its share of capacity – variation: weighted fair queuing (WFQ) • Problem? FQ Algorithm • Suppose clock ticks each time a bit is transmitted • Let Pi denote the length of packet i • Let Si denote the time when start to transmit packet i • Let Fi denote the time when finish transmitting packet i • Fi = Si + Pi • When does router start transmitting packet i? – if before router finished packet i - 1 from this flow, then immediately after last bit of i - 1 (Fi-1) – if no current packets for this flow, then start transmitting when arrives (call this Ai) • Thus: Fi = MAX (Fi - 1, Ai) + Pi • For multiple flows – calculate Fi for each packet that arrives on each flow – treat all Fi’s as timestamps – next packet to transmit is one with lowest timestamp • Not perfect: can’t preempt current packet • Example TCP Congestion Control • Idea – assumes best-effort network (FIFO or FQ routers) each source determines network capacity for itself – uses implicit feedback – ACKs pace transmission (self-clocking) • Challenge – determining the available capacity in the first place – adjusting to changes in the available capacity Additive Increase/Multiplicative Decrease • Objective: adjust to changes in the available capacity • New state variable per connection: CongestionWindow – limits how much data source has in transit MaxWin = MIN(CongestionWindow, AdvertisedWindow) EffWin = MaxWin - (LastByteSent - LastByteAcked) • Idea: – increase CongestionWindow when congestion goes down – decrease CongestionWindow when congestion goes up • Question: how does the source determine whether or not the network is congested? • Answer: a timeout occurs – timeout signals that a packet was lost – packets are seldom lost due to transmission error – lost packet implies congestion