B227 Lecture Overheads - Topic 5: Congestion Control

Congestion Control

Problem: what happens when there are more packets in a path than the routers can handle?

Some causes:

Routers receiving packets from multiple incoming lines, all meant for a the same outgoing line

Slow processors for the routers - in this case, the packets from the multiple incoming lines are coming in faster than the routers can process them and send them back out.

A different problem from flow control – which is between the sender and receiver.

In flow control, it is about not having a fast sender flood a slow receiver, when the slow receiver is not able to process the packets from the sender fast enough. This issue is detached from what happens on the network in between the sender and receiver. An example when we have a flow control problem but no congestion: a fast supercomputer sends packets to a slow workstation. The packets are not delayed at any of the routers, and so get to the workstation very quickly. Unfortunately, the workstation can’t process the packets fast enough. In this case, there is no congestion (in the network), but there is a flow problem (between the sender and receiver).

Some Guiding Principles for Congestion Control

Two categories of algorithms:

Open loop

Design the network properly in the first place

Depend less on adaptive changes

In open loop algorithms, we calculate the best configuration for the hosts and routers, and set them for the hosts and routers. Some issues of things to consider can be found in Fig. 5-23 on page 378 in the Tanenbaum textbook.

Closed loop

Have feedback on congestion in real-time, and respond.

Steps:

Monitor for congestion

Explicit monitors detects congestions by having the congested nodes send packets to notify others. Implicit monitors detects congestions by inferring from local data, such as how long acknowledgments takes to get back.

Pass info to appropriate places

Usually the best place to pass congestion information to is the source of the packets. The source is most able to adjust to congestion (by re-routing, slowing down, etc). Unfortunately, this can lead to further

Adjust operations

Two options on what we can adjust to alleviate congestion is 1) devote more resources (memory, processor time, etc) to handling the traffic, or 2) decrease the rate of sending packets.

An analogy for comparing between open vs closed loop algorithms is a city’s traffic light system. If we use an open loop algorithm, we would do a detailed analysis of the city’s traffic, come up with the best set of timing configurations for all the different traffic lights at different intersections, and then set the timings. Once the timing is set, it is not changed.
In a closed loop algorithm, however, we would start the traffic light with a default set of timings, install sensors on intersections to detect the passing traffic, devise a way for the sensors’ information to be relayed to other traffic lights, and then a method of changing the traffic light timings based on that information. Then as vehicles start to go through the different intersections, the traffic lights can adjust their timing to best optimise traffic flow.

Congestion Control Algorithms

Open loop:

Traffic shaping using

Leaky Bucket Algorithm

Token Bucket Algorithm

Closed loop:

Controlling VC set-up

Choke packets

Load Shedding

Traffic Shaping

Controlling congestion by controlling the rate of data transmission – mainly at the source of the packets.

Having host transmit at uniform rate usually cause less congestion – network less affected by bursts of packets.

Requires an agreement between all senders, receivers and subnet on how the network flow should be like - if for example, most hosts agrees to transmit at a slow rate, but one decides it will transmit at the fast rate, then the fast host will end up hogging the lines it uses.

Some algorithms:

Leaky Bucket

Token Bucket

Leaky Bucket Algorithm

Fig 5-24 p380

The leaky bucket algorithm is similar to how a leaky bucket behaves under a tap behaves: the drip from the leak is always constant regardless of how fast water coming from a tap is, and if the bucket is full, then water will overflow and be discarded.
In a network using the leaky bucket algorithm, data coming from a host goes through an interface. The interface stores up the packets from the source in memory and sends them out in a constant rate. If the memory fills up, the packets will be discarded (the host will re-transmit at a later time when it times out).

Token Bucket Algorithm

Fig 5-25 p383

We still use an interface (bucket) to regulate the flow, but we want to allow a slightly faster rate when the bucket is relatively full and slower when relatively empty. We do this by having the interface generate tokens. A packet being sent through the interface must consume a token. If there are no tokens, the packets must wait. By having the interface generate the tokens at a regular interval, we can have the tokens saved up at idle times, to be used for a burst when the packets come. And at busy times, the rate of transmission is still constant since the tokens are generated at a constant rate.

Controlling Virtual Circuit (VC) Set-up

Admission control: if there is congestion, routers will refuse any new request for new VCs to be set up through it.

Variants:

Set-up VCs to avoid congested areas.

Negotiate the resources (memory, processor time, etc) at the congested area so the VC use the full capacity available for the routers.

Choke Packets

Can be used in either VCs or Datagram subnets.

Every router maintains a variable for every outgoing line

The variable indicates how often the line is used – the router will obviously know how often a particular outgoing line is being used.

If the variable goes above a threshold value, the line goes into a warning state.

If a incoming packet requires an outgoing line which is in warning state, a choke packet is sent back to the source – the packet is till forwarded as normal.

Source receiving choke packets adjust their sending patterns – slow down, or re-route through somewhere else.

Load Shedding

Strategy: when routers can’t handle the load, just dump incoming packets!

But decision: which packets to dump?

New or old packets? Depends on what type the packets are.

In some applications, it is better than new packets get dumped. Eg. in interlaced image packets, packets sent out first (old packets) contain the coarse-grain image, then the later packets (new packets) fill in the details. So getting the coarse-grain image without the details may still be usable, but having the details without the coarse-grain image to work with is not.

On the other hand, in some applications, it is better than old packets get dumped. Eg. in file transfers, if any packets are to be discarded, we’d like it to be the one sent out earlier (old packets). This is so that the sender gets time out a lot sooner and re-transmit the file, rather than falsely believing that since the earlier packets are getting acknowledged, that everything is OK.

Can have source label the priority of the packets and put them in priority fields in the packet headers – routers can use these priority fields and dump the low priority packets first.

Jitter Control

In some audio and video transmission, speed for each packet is not as important as having a constant rate for all packet.

Routers can calculate if these packets are ahead or behind the scheduled rate, and during congestion hold off on processing packets currently ahead of schedule.

This involves the packets having a time-stamp, and the routers using this time-stamp to determine if the packet is ahead of schedule or not.

[Back to Lecture Notes page]