Queue

  • QUEUING DISCIPLINES

1. DROP TAIL

It is a simple queue mechanism that is used by the routers that when packets should to be drop. In this mechanism each packet is treated identically and when queue filled to its maximum capacity the newly incoming packets are dropped until queue have sufficient space to accept incoming traffic.

When a queue is filled the router start to discard all extra packets thus dropping the tail of mechanism. The loss of packets (datagram’s) causes the sender to enter slow start which decreases the throughput and thus increases its congestion window.

2. FAIR QUEUING

It is a queuing mechanism that is used to allow multiple packets flow to comparatively share the link capacity. Routers have multiple queues for each output line for every user. When a line as available as idle routers scans the queues through round robin and takes first packet to next queue. FQ also ensure about the maximum throughput of the network. For more efficiency weighted queue mechanism is also used.

3. DEFICIT ROUND ROBIN

It is a modified weighted round robin scheduling mechanism. It can handle packets of different size without having knowledge of their mean size. Deficit Round Robin keeps track of credits for each flow. It derives ideas from Fair Queuing and Stochastic FQ. It uses hashing to determine the queue to which a flow has to be assigned and collisions automatically reduce the bandwidth guaranteed to the flow. Each queue is assigned a quantum and can send a packet of size that can fit in the available quantum. If not, the idle quantum gets added to this meticulous queue’s deficit and the packet can be sent in the next round. The quantum size is a very vital parameter in the DRR scheme, determining the upper bound on the latency as well as the throughput.

This queue mechanism used a well-designed idea to get better performance and can also be implemented in a cost effectiveness manner. It provides a generic framework to implement fair queuing efficiently.

Although DRR serves fine for throughput fairness, but when it comes to Latency bounds it performs rather poorly. Also it does not operate well for real time traffic. The queuing delays introduced by DRR can have exciting results on the congestion window sizes.

4. RANDOM EARLY DETECTION

Random Early Detection (RED) is a congestion avoidance queuing mechanism (as opposed to a congestion administration mechanism) that is potentially useful, particularly in high-speed transit networks. Sally Floyd and Van Jacobson projected it in various papers in the early 1990s.It is active queue management mechanism. It operates on the average queue size and drop packets on the basis of statistics information. If the buffer is empty all incoming packets are acknowledged. As the queue size increase the probability for discarding a packet also increase. When buffer is full probability becomes equal to 1 and all incoming packets are dropped.

RED is capable to evade global synchronization of TCP flows, preserve high throughput as well as a low delay and attains fairness over multiple TCP connections, etc. It is the most common mechanism to stop congestive collapses.

When the queue in the router starts to fill then a small percentage of packets are discarded. This is deliberate to start TCP sources to decrease their window sizes and hence suffocate back the data rate. This can cause low rates of packet loss in Voice over IP streams. There have been reported incidences in which a series of routers apply RED at the same time, resulting in bursts of packet loss.

5. STOCHASTIC FAIR QUEUING

This queuing mechanism is based on fair queuing algorithm and proposed by John Nagle in 1987. Because it is impractical to have one queue for each conversation SFQ uses a hashing algorithm which divides the traffic over a limited number of queues. It is not so efficient than other queues mechanisms but it also requires less calculation while being almost perfectly fair. It is called "Stochastic" due to the reason that it does not actually assign a queue for every session; it has an algorithm which divides traffic over a restricted number of queues using a hashing algorithm. SFQ assigns a pretty large number of FIFO queues.