Computer Networking Lecture Notes

2014 October 13 • Network Congestion Control

---

Outline

• Review and definitions.
• The congestion-control continuum.
  • Prevention: network provisioning.
  • Avoidance: admission control, throttling.
  • Reaction: load shedding

The Territory

Network Resources

• Attached subnetworks treat the network (links + routers) as a resource.
  • Bandwidth, routing, and so on.
• Network resources are finite and relatively static.
• Subnetwork resource demands are practically unbounded and dynamic.
• How can subnetwork demands be matched to network capabilities?

Resource Management

• Resource management can be proactive or reactive.
• Proactive management tries to manage demand to fit the resources.
• Reactive management tries to manage resources to fit the demand.
  • Although it also tries to influence demand too.
• Congestion control is reactive management.
• Quality of service (QoS) is proactive management (next lecture).

Network Resources

• Routers and links are the network resource of interest.
  • Time resources include router CPU and link bandwidth.
  • Space resources include buffer space and routing table size.
• A simplified view, but a useful one.

Congestion

• Congestion occurs when demand (traffic) outstrips supply (resources).

  The router can handle M bits/sec maximum. Congestion occurs when \(\Sigma\)j ij bits/sec > M

• This is a first-cut definition.

More Congestion

• Link 4 can handle M₄ bits/sec maximum.

  

• Congestion occurs when \(\Sigma\)_j i_{j, 4} bits/sec > M₄.
  • Even though \(\Sigma\)_j i_{j, 4} bits/sec ≤ M.

Congestion Pictured

Controlling Congestion

• Network congestion control should
  • Avoid congestion collapse in the network
  • run the network as close to limits as possible.
    • Higher utilization makes better economic sense.
• A continuum of network congestion control.
  • From slower preventative techniques to faster reactive techniques.

Network Provisioning

• Network provisioning adds and upgrades resources to handle traffic.
  • Prevents congestion, but is slow to react.
• Expected traffic demands can be forecast, but not easily.
  • Particularly in dynamic environments.
  • Technologically-driven over-provisioning is helpful here.
    • But Parkinson’s law.

Congestion Costs

• Congestion is a cost to the network and to its users.
• Routing algorithms are good at handling, and optimizing, costs.
• Condition edge and vertex weights (costs) on congestion.
  • And use them in routing algorithms.
• The result is congestion-aware routing algorithms.

Example

• Congestion-aware routing algorithms
  • have poor convergence properties, and
  • can cause wild instabilities.

Evaluation

• Possible fixes for congestion-aware problems include
  • multi-path routing
  • dampened reaction to congestion changes.
• Congestion-aware routing algorithms used to be used in the Internet.
  • Not a solution in itself, but helpful elsewhere.

An Analogy

• What do you do when you have more people than seats?

  

Admission Control

• Only admit traffic when the network can handle it without congestion.
  • Easier for circuit-based networks than it is for datagram networks.
  • But still not easy.
• Example: no dial tone on overloaded phone networks.
• The big questions in the Internet now are related to admission control.

Describing Traffic

• Traffic can be described by its average rate in bits/sec.
• But much traffic is bursty, or on-off variable.
  • Think Web traffic over persistent connections.
• Traffic also has a shape, or instantaneous burst size in bits/sec.
  • The maximum rate.

Admission Decisions

• Fitting advertised rate + shape into the network can be tricky.
• Given applications with
  • 100 kbit/sec average rate, and
  • 1 mbit/sec burst rate
• how many applications fit in a 100 mbit/sec network?

Deciding Admissions

• (100 mbit/sec)/(100 kbit/app-sec) = 1000 applications.
• (100 mbit/sec)/(1 mbit/app-sec) = 100 applications.
• Deciding on average rates overcommits the network.
• Deciding on burst rates under-utilizes the network.
• And all this assumes the traffic parameters are accurate.

Example

• Order of magnitude differences (approximately) between average and maximum rates.

Congestion Awareness

• Congestion-aware routing is unstable for whole networks.
• But works well for routing specific circuits.
• Congestion is also more manageable, smaller and better behaved.
• Congestion-aware routes can more finely partition the network into congested and uncongested regions.

Recovering From Mistakes

• Admission control can err on the wrong side.
  • And datagram services are harder to manage in the network.
  • And networks are (should be) run close to congestion.
• What happens when congestion results?
  • The network has failed, in some sense.
  • It’s up to the senders to respond.

Traffic Throttling

• When too much traffic causes congestion, cut back (or throttle) the traffic.
  • A move from prevention and avoidance to reaction and mitigation.
• Any traffic-throttling scheme has two problems:
  • Recognizing or anticipating congestion.
  • Signaling congestion to the senders.

Recognizing Congestion

• Routers monitor network conditions and draw conclusions.
• Observable conditions include
  • output link utilization,
  • buffer or queue length, or
  • resource exhaustion.
• Average utilization misses burstiness; resource exhaustion is too late.
• Average queue length works well.

Congestion Signaling

• A sender receiving congestion signals should throttle back transmissions.
  • By some amount for some time.
• Further signals, or their absence, determine future behavior.
  • More signals, more throttling.
  • Fewer or no signals, try for more capacity.
• How should these signals be conveyed?

Choke Packets

• A router nearing or in congestion sends choke packets back to senders.

  

• Which sender does the router choke?

Sender Choice

• Choking the last-in packet sender may not help.
  • That sender may not be a high-rate sender.
• Randomly pick a queued packet and choke its sender.

  

  • High-rate senders queue many packets.
  • Not perfect, but low overhead.

Aiding and Abeting

• Sending choke packets adds congestion.
• Congested routers flag packets encountering congestion anyway.
• Let the destination relay the congestion flag back to the sender in an ack.
• This is Explicit Congestion Notification (ECN).
  • Implemented in DECNet (1980s), used in the Internet.

ECN Example

Long Fast Networks

• Seattle is using a fast network to send to Boston via Toronto.
• Toronto is getting congested, and uses choke packets or ECN.
• What happens?
  • The Seattle-Toronto segment is filled with packets.
  • The segment dumps all its packets into Toronto after Seattle is notified.

Network Action

• If the sender can’t help, the network has to.
• Each router forwarding a choke packet devotes extra buffer space to the exuberant flow.
• Congestion relief flows backwards to the sender, which then stems the flow.
  • Up-stream routers recover as the sender throttles.
• This is hop-by-hop backpressure.

Backpressure Example

• 

The Last Resort

What do you do with more stuff than you can handle?

Load Shedding

• Last-resort congestion control throws packets on the floor.
  • Dropping or shedding packets.
  • Electric power distribution does something similar.
• The important decision: what packets to drop?
  • There are non-trivial decisions to be made.
• Random choice works, but are there better choices?

Dropping Knowledge

• Choice based on application-type can improve matters.
  • Drop later (newer) packets in a file transfer.
  • Drop earlier (older) packets in media streams.
  • Wine vs milk.
  • MPEG-encoded video packets.
• Chose based on packet-type too.

Sender Assistance

• The sender can mark packets as droppable or precious.
• There should be incentives for accurate marking.
  • Too many precious packets can be penalized (by high cost, for example).
  • A predominance of droppable packets can be rewarded (by improved priority, for example).
• This didn’t work in the Internet.

Definitive Signaling

• Sending signals in heterogeneous environments is tricky.
  • Signals can be misinterpreted, misunderstood, or ignored.
• Dropped packets are a definitive congestion signal.
  • But dropping packets in congestion is too late.
• Drop packets in near-congested conditions.
  • An obvious and possibly timely signal.

Random Early Detection

• Random Early Detection (or Drop, RED):

  Drop packets at random in near-congestion conditions.

• This is a TCP-specific solution.
  • Datagram based.
  • TCP throttles on packet loss.
• Tuning RED parameters improves results.
• The Internet uses ECN with RED fall-back.

RED Illustrated

• 

  Min > Avg		Do nothing.
  Max ≥ Avg ≥ Min		Drop or mark with probability p.
  Avg > Max		Drop.

• Avg = (1 - α)Avg + αQLen.
• p directly proportional to average queue size.

Summary

• Network congestion control drives the network up to but not into congestion.
• There is a continuum of congestion-control measures.
  • From slow avoidance to fast recovery.
  • Networks use several points in the continuum.
• Congestion problems and solutions are constantly shifting in response to technological and operational events.

References

• Parkinson's Law by C. Northcode Parkinson from Houghton Mifflin, 1957.

Credits

• Admission (Found Object) by Tom Fassbender under a Creative Commons BY NC ND license.
• bandwidth blowout by Matt Haughey under a Creative Commons BY NC SA license.
• Overflowing trash bin by Matti Mattila under a Creative Commons BY NC SA license.

---

This page last modified on 2014 October 12.