Share

Congestion Control Algorithm

This article covers the algorithm of congestion control. The key strategy lies in maintaining the congestion level under optimal load conditions. Refer to congestion control basics for an introduction to the subject.

Basic Algorithm

The following figure describes the basic algorithm for congestion control.

Figure showing congestion control algorithm for managing congestion level

  1. The congestion control task will receive a congestion trigger if the any of the resources being monitored crosses a congestion threshold, i.e. congestion has either risen above a threshold or fallen below a threshold.
  2. On the basis of the reported congestion condition, the congestion control task applies a congestion level.
    • Resource Overloaded: If the monitored resource is overloaded, the traffic in the system needs to be reduced. Thus, the congestion control task increases the throttling of traffic by increasing the congestion level by one.
    • Resource Optimally Loaded: If the monitored resource is loaded just right, i.e. to its optimum usage, the congestion level needs to maintained. So no change is made to the congestion control level. Hence, no congestion control action is taken.
    • Resource Under Loaded: If the monitored resource is under loaded, the system can handle more traffic than is being currently offered. Thus, the congestion control task decreases the throttling of traffic by decreasing the congestion level by one.
  3. If the congestion level has changed in the previous step, the task needs to implement the level change by asking the front-end processors to increase or decrease traffic blocking.
  4. The front-end processors take appropriate action. This action will result in change in traffic load.
  5. Changes in load handled by the system will finally result in further congestion triggers, thus bringing us back to point 1.

The above algorithm presents a simplistic handling of congestion control. We will discuss other aspects of congestion control in the following sections.

Congestion Threshold Management

To avoid oscillations of resource usage between overload region and optimum load region or between the optimum load region and under load region on application of congestion control action, the abatement threshold is kept different from the onset threshold.

The following figure shows the threshold settings for CPU utilization trigger reporting in a typical system.

Setting of onset and abatement thresholds for congestion monitoring

If the CPU utilization increases beyond 50%, the system moves from under load region to optimum load region. The system can only move back to under load region if the CPU utilization falls below 45%. This difference in onset and abatement thresholds ensures that no oscillations would take place when the load is close to 50%. In absence of this difference, the system would have probably alternated between reporting under load and optimum load regions. Similar reasoning applies to the difference in the overload onset and overload abatement thresholds. This differential threshold setting is also referred to as hysteresis (The name comes from BH hysteresis curves.).

The tuning of onset and abatement thresholds is more of an art rather than a science. It involves a lot of hit and trial. It is generally based on simulation and real life traffic statistics.

Congestion Action Hangover

It should be noted that noticeable difference in system performance happens only after the congestion control action has been in effect for sometime. Thus there is a requirement that the congestion control task ignores the congestion triggers received immediately after the congestion control action has been applied. This duration is again tuned on the basis of traffic statistics.

Taking our central bank example, when the central bank raises or lowers the key lending rates, the economy takes some time to react to the changes.