[attachment=9001]
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