Congestion Control Algorithms
Congestion is a state of excessive accumulation or overfilling or overcrowding.
Maximum carrying capacity of subnet Perfect
Packets Delivered
Desirable
Congested
Packets Sent
2/8/2013 Congestion Control Algorithms 1
Factors responsible for congestion
Packet arrival rate exceeds the outgoing link capacity. Insufficient memory to store arriving packets Bursty traffic Slow processor
Congestion tends to feed upon itself & become worse.
2/8/2013 Congestion Control Algorithms 2
Difference between Congestion Control & Flow Control
Congestion control has to make sure that subnet is able to carry the offered load. Flow control relates to point-to-point traffic between a given sender & a receiver.
2/8/2013
Congestion Control Algorithms
Principles Of Congestion Control
Control Theory
Open Loop Control
Closed Loop Control
2/8/2013
Congestion Control Algorithms
Open Loop Control
Open loop control attempts to solve the problem by making sure it doesnt occur in the first place. Tools: When to accept a new packet. Deciding when to discard packets & which ones. Making scheduling decisions at various points in the network.
2/8/2013 Congestion Control Algorithms 5
Closed Loop Control
Its based on the concept of feedback loop. When applied to congestion control: 1. Monitors the system to detect when & where congestion occurs. 2. Pass this information to the places where action can be taken. 3. Adjust system operation to correct the problem.
2/8/2013 Congestion Control Algorithms 6
Techniques
Several techniques can be employed. These include: Choke packets Load shedding Traffic shaping The first 2 deal with congestion detection and recovery. The last one deals with congestion avoidance.
2/8/2013 Congestion Control Algorithms 7
Traffic Shaping
Forcing the packets to be transmitted in a more predictable rate. Traffic policing: Monitoring the traffic flow.
2/8/2013
Congestion Control Algorithms
The Leaky Bucket Algorithm
2/8/2013
Congestion Control Algorithms
The Token Bucket Algorithm
2/8/2013
Congestion Control Algorithms
10
Leaky Bucket vs Token Bucket
LB discards packets; TB does not. TB discards tokens. With TB, a packet can only be transmitted if there are enough tokens to cover its length in bytes. LB sends packets at an average rate. TB allows for large bursts to be sent faster by speeding up the output. TB allows saving up tokens (permissions) to send large bursts. LB does not allow saving.
2/8/2013
Congestion Control Algorithms
11
Choke Packets
A more direct way of telling the source to slow down. A choke packet is a control packet generated at a congested node and transmitted to restrict traffic flow. The source, on receiving the choke packet must reduce its transmission rate by a certain percentage.
2/8/2013 Congestion Control Algorithms 12
unew = auold
( 1-a ) f
U Utilization of its output lines. A a constant, how fast the router forgets the recent history. F instantaneous line utilization
2/8/2013
Congestion Control Algorithms
13
Weighted Fair Queuing
Packet Finishing time
A B C D
11
15
19
20
C 8
12
16
B 16
O
13 17
17
18
10
14
18
20
A router with 5 packets queued for line O
2/8/2013 Congestion Control Algorithms
Finishing times for 5 packets
14
Choke Packets that affects only the source
B
A E B A E B A
Choke
C D F C A
C D A
C D
Choke
E B F C
Flow is still at maximum rate
B
Choke
C
D Flow is reduced
A Reduced Flow E F
D A
F C D
E
2/8/2013
F
Congestion Control Algorithms 15
Hop-by-hop Choke Packet
B B C D E a) B A C D F b)
2/8/2013
C D
A
F
A Heavy Flow Choke E F
Reduced Flow B C D E F
c)
B
A
C D F d)
Choke E
Choke E
e)
Congestion Control Algorithms
16
Load Shedding
Load Shedding is a way in which the routers when flooded with packets that it cannot handle, just throws them away.
2/8/2013
Congestion Control Algorithms
17
Jitter Control
In this technique, the packets which are ahead of schedule get slowed down & packets that are behind schedule get speeded up.
2/8/2013
Congestion Control Algorithms
18
Congestion Control For Multicasting
RSVP--- Resource reSerVation Protocol
1 Sender s 2
Receivers 2/8/2013
Congestion Control Algorithms
19
