 Congestion is an important

issue that can arise in packet

switched network. Congestion Causing of Congestion:
is a situation in Communication The various causes of congestion in a
Networks in which too many subnet are:
packets are present in a part of • The input traffic rate exceeds the
the subnet, performance capacity of the output lines. If
degrades. Congestion in a suddenly, a stream of packet start
network may occur when the arriving on three or four input lines and
load on the network (i.e. the all need the same output line. In this
number of packets sent to the case, a queue will be built up. If there
network) is greater than the is insufficient memory to hold all the
capacity of the network (i.e. the packets, the packet will be lost.
Increasing the memory to unlimited
number of packets a network
size does not solve the problem. This
can handle.). Network is because, by the time packets reach
congestion occurs in case of front of the queue, they have already
traffic overloading. timed out (as they waited the queue).
 In other words when too much When timer goes off source transmits
traffic is offered, congestion duplicate packet that are also added to
sets in and performance the queue. Thus same packets are
degrades sharply added again and again, increasing the
load all the way to the
destination.
The routers are too slow to perform mechanisms are divided into two
bookkeeping tasks (queuing buffers, categories, one category prevents the
updating tables, etc.). congestion from happening and the
• The routers' buffer is too limited. other category removes congestion
• Congestion in a subnet can occur if after it has taken place.
the processors are slow. Slow speed
CPU at routers will perform the routine
tasks such as queuing buffers, updating
table etc slowly. As a result of this,
queues are built up even though there
is excess line capacity.
• Congestion is also caused by slow
links. This problem will be solved
when high speed links are used. But it
is not always the case. Sometimes
increase in link bandwidth can further
deteriorate the congestion problem as
higher speed links may make the
network more unbalanced.Congestion
can make itself worse. If a route!" does
not have free buffers, it start
ignoring/discarding the newly arriving
packets. When these packets are
discarded, the sender may retransmit
them after the timer goes off. Such
packets are transmitted by the sender These two categories are:
again and again until the source gets 1. Open loop
the acknowledgement of these packets.
Therefore multiple transmissions of 2. Closed loop
packets will force the congestion to Open Loop Congestion Control
take place at the sending end.
• In this method, policies are used to
How to correct the Congestion prevent the congestion before it
Problem: happens.
Congestion Control refers to • Congestion control is handled either
techniques and mechanisms that can by the source or by the destination.
either prevent congestion, before it • The various methods used for open
happens, or remove congestion, after it loop congestion control are:
has happened. Congestion control
Retransmission Policy • Acknowledgments also add to the
• The sender retransmits a packet, if it traffic load on the network. Thus, by
feels that the packet it has sent is lost sending fewer acknowledgements we
or corrupted. can reduce load on the network.

• However retransmission in general • To implement it, several approaches

may increase the congestion in the can be used:
network. But we need to implement 1. A receiver may send an
good retransmission policy to prevent acknowledgement only if it has a
congestion. packet to be sent.
• The retransmission policy and the 2. A receiver may send an
retransmission timers need to be acknowledgement when a timer
designed to optimize efficiency and at expires.
the same time prevent the congestion. 3. A receiver may also decide to
Window Policy acknowledge only N packets at a time.
• To implement window policy, Discarding Policy
selective reject window method is used • A router may discard less sensitive
for congestion control. packets when congestion is likely to
• Selective Reject method is preferred happen.
over Go-back-n window as in Go- • Such a discarding policy may prevent
back-n method, when timer for a congestion and at the same time may
packet times out, several packets are not harm the integrity of the
resent, although some may have transmission.
arrived safely at the receiver. Thus,
this duplication may make congestion Admission Policy
worse. • An admission policy, which is a
• Selective reject method sends only quality-of-service mechanism, can
the specific lost or damaged packets. also prevent congestion in virtual
circuit networks.
Acknowledgement Policy
• Switches in a flow first check the
• The acknowledgement policy resource requirement of a flow before
imposed by the receiver may also admitting it to the network.
affect congestion.
• A router can deny establishing a
• If the receiver does not acknowledge virtual circuit connection if there is
every packet it receives it may slow congestion in the "network or if there
down the sender and help prevent is a possibility of future congestion.
congestion.
Closed Loop Congestion Control
• Closed loop congestion control in turn, reject data from their upstream
mechanisms try to remove the node or nodes.
congestion after it happens. As shown in fig node 3 is congested
• The various methods used for closed and it stops receiving packets and
loop congestion control are: informs its upstream node 2 to slow
Backpressure down. Node 2 in turns may be
congested and informs node 1 to slow
• Backpressure is a node-to-node down. Now node 1 may create
congestion control that starts with a congestion and informs the source
node and propagates, in the opposite node to slow down. In this way the
direction of data flow. congestion is alleviated. Thus, the
pressure on node 3 is moved backward
to the source to remove the congestion.
Choke Packet
• In this method of congestion control,
congested router or node sends a
special type of packet called choke
packet to the source to inform it about
the congestion.
• Here, congested node does not
inform its upstream node about the
congestion as in backpressure method.
• In choke packet method, congested
node sends a warning directly to the
source station i.e. the intermediate
The backpressure technique can be nodes through which the packet has
applied only to virtual circuit traveled are not warned.
networks. In such virtual circuit each
node knows the upstream node from
which a data flow is coming.
• In this method of congestion control,
the congested node stops receiving
data from the immediate upstream
node or nodes.
• This may cause the upstream node on
nodes to become congested, and they,
implicit Signaling • In forward signaling, a bit is set in a
• In implicit signaling, there is no packet moving in the direction of
communication between the congested congestion. This bit warns the
node or nodes and the source. destination about the congestion. The
receiver in this case uses policies such
• The source guesses that there is as slowing down the
congestion somewhere in the network acknowledgements to remove the
when it does not receive any congestion.
acknowledgment. Therefore the delay
in receiving an acknowledgment is Congestion control algorithms
interpreted as congestion in the
Leaky Bucket Algorithm
network.
• It is a traffic shaping mechanism that
• On sensing this congestion, the
controls the amount and the rate of the
source slows down.
traffic sent to the network.
• This type of congestion control
• A leaky bucket algorithm shapes
policy is used by TCP.
bursty traffic into fixed rate traffic by
Explicit Signaling averaging the data rate.
• In this method, the congested nodes • Imagine a bucket with a small hole at
explicitly send a signal to the source or the bottom.
destination to inform about the
• The rate at which the water is poured
congestion.
into the bucket is not fixed and can
• Explicit signaling is different from vary but it leaks from the bucket at a
the choke packet method. In choke constant rate. Thus (as long as water is
packed method, a separate packet is present in bucket), the rate at which the
used for this purpose whereas in water leaks does not depend on the rate
explicit signaling method, the signal is at which the water is input to the
included in the packets that carry data. bucket.

Explicit signaling can occur in either

the forward direction or the backward
direction .
• In backward signaling, a bit is set in
a packet moving in the direction
opposite to the congestion. This bit
warns the source about the congestion
and informs the source to slow down.
Also, when the bucket is full, any
additional water that enters into the
bucket spills over the sides and is lost.
• The same concept can be applied to
packets in the network. Consider that
data is coming from the source at Token bucket Algorithm
variable speeds. Suppose that a source • The leaky bucket algorithm allows
sends data at 12 Mbps for 4 seconds. only an average (constant) rate of data
Then there is no data for 3 seconds. flow. Its major problem is that it
The source again transmits data at a cannot deal with bursty data.
rate of 10 Mbps for 2 seconds. Thus, in
a time span of 9 seconds, 68 Mb data • A leaky bucket algorithm does not
has been transmitted. consider the idle time of the host. For
example, if the host was idle for 10
If a leaky bucket algorithm is used, the seconds and now it is willing to sent
data flow will be 8 Mbps for 9 seconds. data at a very high speed for another 10
Thus constant flow is maintained. seconds, the total data transmission
will be divided into 20 seconds and
average data rate will be maintained.
The host is having no advantage of
sitting idle for 10 seconds.
• To overcome this problem, a token
bucket algorithm is used. A token
bucket algorithm allows bursty data
transfers.
• A token bucket algorithm is a
modification of leaky bucket in which
leaky bucket contains tokens.
• In this algorithm, a token(s) are
generated at every clock tick. For a
packet to be transmitted, system must
remove token(s) from the bucket.
• Thus, a token bucket algorithm
allows idle hosts to accumulate credit
for the future in form of tokens.
• For example, if a system generates
100 tokens in one clock tick and the
host is idle for 100 ticks. The bucket
will contain 10,000 tokens.
Now, if the host wants to send bursty
data, it can consume all 10,000 tokens
at once for sending 10,000 cells or
bytes.
Thus a host can send bursty data as
long as bucket is not empty.