1 Congestion Control Overview When number of packets sent is within subnet carrying capacity, all are delivered
As traffic increases, packet loss happens
At very high traffic, performance collapses
Both transport and network layers share responsibility of handling congestion
Network layer is directly affected. Therefore network congestion control should
protect the network from congestion collapse
2 How Congestions Happens Incoming packets from multiple inputs need to go to same output line; queue builds up If insufficient memory, packets lost Adding memory helps to some point Even with ∞ memory, congestion gets worse delayed packets timeout, retransmitted duplicates increase load When load exceeds capacity: Congestion collapse Slow processors CPU slow in doing bookkeeping tasks queues build up Low bandwidth lines can’t forward packets same as arriving speeds Mismatch between system parts 3 upgrading some parts only shifts bottleneck Congestion Control Congestion control refers to techniques and mechanisms that can either prevent congestion, before it happens, or remove congestion, after it has happened.
Congestion control mechanisms are divided into two broad categories: open- loop congestion control (prevention) and closed-loop congestion control (removal)
Open-Loop Congestion Control: policies are applied to prevent congestion
before it happens. In these mechanisms, congestion control is handled by either the source or the destination (Examples: retransmission policy, Window policy, Discarding policy, Acknowledgment policy, Admission Policy)
Closed-Loop Congestion Control: mechanisms try to alleviate congestion
after it happens. Several mechanisms have been used by different protocols. Examples: Back Pressure, Choke Packet, Implicit and Explicit signaling) Congestion Control Methods
5 Congestion Control Methods (Open Loop) Retransmission Policy: To prevent congestion, retransmission timers must be designed to prevent congestion and also able to optimize efficiency.
Window Policy: Selective repeat window should be adopted as it sends the
specific packet that may have been lost.
Discarding Policy: A good discarding policy adopted by the routers is that
the routers may prevent congestion and at the same time partially discard the corrupted or less sensitive packages.
Acknowledgment Policy: The receiver should send acknowledgement for
N packets rather than sending acknowledgement for a single packet. Receiver can send acknowledgment only if it has to send a packet or a timer expires.
Admission Policy: Switches in a flow should first check the resource
requirement of a network flow before transmitting it further. If there is a chance of a congestion or there is a congestion in the network, router should 6 deny establishing a virtual network connection to prevent further congestion. Congestion Control Methods (Closed Loop) Backpressure: Where a congested node stops receiving packets from upstream node. It is a node-to-node congestion control technique that propagate in the opposite direction of data flow. It can be applied only to virtual circuit where each node has information of its above upstream node.
7 Congestion Control Methods (Closed Loop) Choke Packet: A choke packet is a packet sent by a node to the source to inform it of congestion. It is applicable to both virtual networks as well as datagram subnets. Each router monitors its resources and the utilization at each of its output lines. Whenever the resource utilization exceeds the threshold value (set by the administrator), the router directly sends a choke packet to the source giving it a feedback to reduce the traffic. The intermediate nodes through which the packets has traveled are not warned about congestion.
8 Congestion Control Methods (Closed Loop) Implicit Signaling: Where there is no communication between the congested nodes and the source. The source guesses that there is congestion in a network. For example when sender sends several packets and there is no acknowledgment for a while, one assumption is that there is a congestion. Explicit Signaling: If a node experiences congestion it can explicitly sends a packet to the source or destination to inform about congestion. Here the signal is included in the packets that carry data rather than creating a different packet like choke packet technique. Explicit signaling can occur in either forward or backward direction. Forward Signaling: In forward signaling, a signal is sent in the direction of the congestion. The destination is warned about congestion. The receiver in this case adopt policies to prevent further congestion. Backward Signaling: In backward signaling, a signal is sent in the opposite direction of the congestion. The source is warned about congestion and it needs to slow down. Quality of Service Four issues must be addressed to ensure quality of service:
1. What applications need from the network.
2. How to regulate the traffic that enters the network.
3. How to reserve resources at routers to guarantee performance.
4. Whether the network can safely accept more traffic.
No single technique deals efficiently with all these issues. Instead, a variety of techniques have been developed for use at the network (and transport) layer.
10 QoS To accommodate a variety of applications, networks may support different categories of QoS. They support:
1. Constant bit rate (e.g., telephony).
2. Real-time variable bit rate (e.g., videoconferencing).
3. Non-real-time variable bit rate (e.g., watching a movie on demand).
4. Available bit rate (e.g., file transfer).
11 Traffic policing and Traffic shaping Traffic Policing : It is a mechanism which monitors the traffic in any network by using an action to packets that conform to a specified rate.
The policies in the network keeps a check on the number of tokens
in the bucket.
In traffic policing one token usually represents one byte of traffic.
It can be used to control inbound and outbound traffic.
It also maintains control over the excess traffic.
12 Traffic policing and Traffic shaping Traffic Shaping : It reduces congestion and regulates the rate of data transmission.
It is a congestion control mechanism that delays some packets to
bring them at par with other traffic components.
It increases the latency and the bandwidth of packets.
It makes traffic conform to a certain rate by giving the packets some
delay.
Traffic shaping can be used to control outbound traffic only.
It also does queuing of packets.
13 Leaky Bucket
The leaky bucket is used to implement traffic policing and traffic shaping in Ethernet and cellular data networks.
Leaky Bucket technique can be used to shape the traffic
Suppose we have a bucket in which we are pouring water in a random order
but we have to get out water in a fixed rate , for this we will make a hole at the bottom of the bucket. It will ensure that water coming out is in a some fixed rate. And also if bucket will full we will stop pouring in it.
The input rate can vary, but the output rate remains constant.
Similarly, in networking, a technique called leaky bucket can smooth out
bursty traffic.
Bursty chunks are stored in the bucket and sent out at an average rate Leaky Bucket Algorithm Example Consider a frame relay network having a capacity of 1Mb and data is input at the rate of 25mbps.Calculate 1. What is the time needed to fill the bucket. 2. If the output rate is 2 mbps , the time needed to empty the bucket.
Ans. Here , C is Capacity of bucket = 1Mb Data input rate = 25 mbps Output rate = 2mbps.
1. T = C/input rate = 1/25 = 40 msec
2. T = C/output rate = ½ = 500 msec
15 Leaky Bucket Each network interface contains a leaky bucket and the following steps are involved in leaky bucket algorithm: When host wants to send packet, packet is thrown into the bucket. The bucket leaks at a constant rate, meaning the network interface transmits packets at a constant rate. Bursty traffic is converted to a uniform traffic by the leaky bucket. In practice the bucket is a finite queue (FIFO) that outputs at a finite rate.
16 Token Bucket The leaky bucket algorithm enforces output pattern at the average rate, no matter how bursty the traffic is.
So in order to deal with the bursty traffic we need a flexible algorithm so that the data is not lost. One such algorithm is token bucket algorithm.
It is used in packet-switched and telecommunications networks
It is an algorithm used in packet-switched computer networks to ensure that
data transmission in the form of packets does not cross its bandwidth.
Steps of this algorithm are:
1. In regular intervals tokens are thrown into the bucket.
2. The bucket has a maximum capacity.
3. If there is a ready packet, a token is removed from the bucket, and the packet is sent.
4. If there is no token in the bucket, the packet cannot be sent.
Token Bucket In figure (a) we see a bucket holding three tokens, with five packets waiting to be transmitted. For a packet to be transmitted, it must capture and destroy one token. In figure (b) We see that three of the five packets have gotten through, but the other two are stuck waiting for more tokens to be generated.
18 Token Bucket Algorithm Algorithm
Step – 1 : A token is added at every ∆t time.
Step – 2 : The bucket can hold at most b-tokens. If a token arrive when bucket is full it is discarded.
Step - 3 : When a packet of m bytes arrived m tokens are removed from the bucket and the packet is sent to the network.
Step – 4 : If less than n tokens are available no tokens are removed from the buckets and the packet is considered to be non conformant. The non conformant packet may be enqueued for subsequent transmission when sufficient token have been accumulated in the bucket.
If C is the maximum capacity of bucket and ρ is the arrival rate and M is the maximum output rate then Burst Length S can be calculated as
19 C + ρS = MS or S = C / (M – ρ) Token Bucket Algorithm Example Consider a frame relay network having a capacity of 1Mb of data is arriving at the rate of 25mbps for 40msec.The Token arrival rate is 2mbps and the capacity of bucket is 500 kb with maximum output rate 25mbps. Calculate 1. The Burst Length. 2. Total output time. Ans. Here, C is Capacity of bucket = 500kb M is max. output rate = 25 mbps ρ is token arrival rate = 2mbps. 1. S = C / (M - ρ) = 500 / (25 - 2) = 21.73msec ~= 22msec 2. For 22msec the output rate is 25mbps after that the output rate becomes 2mbps i.e. token arrival rate. Therefore, for another 500 kb the time taken will be: 500 / 2 = 250 msec Therefore, total output time = 22 + 250 = 272 msec. 20 Leaky bucket v/s Token bucket
Some advantage of token Bucket over leaky bucket
If bucket is full in token Bucket , tokens are discard not packets. While in leaky bucket, packets are discarded.
Token Bucket can send Large bursts at a faster rate while leaky bucket always sends packets at constant rate.
