Where Can Queuing Occur In a Router
If we consider input and output port functionality and the configuration shown in the figure below , it’s clear that packet query may form at both the input ports and the output ports, just as we identified cases where cars may wait at the inputs and outputs of the traffic intersection in our roundabout analogy.
The location and extent of queuing (either at the input port queues or the output port queues) will depend on the traffic load, the relative speed of the switching fabric, and the line speed. Let’s now consider these queues in a bit more detail, since as these queues grow large, the router’s memory can eventually be exhausted and packet loss will occur when no memory is available to store arriving packets. Recall in earlier tutorials, we said that packets were “lost within network” or “dropped at a router”. It is here, at these queues within a router, where such packets are actually dropped and lost.
Suppose that the input and output line speeds (transmission rates) all have an identical transmission rate of Rline packets per second, and that there are N input ports and N output ports. To further simplify the discussion, let’s assume that all packets have the same fixed length, and the packets arrive to input ports in a synchronous manner. That is, the time to send a packet on any link is equal to the time to receive a packet on any link, and during such an interval of time, either zero or one packet can arrive on an input link.
Define the switching fabric transfer rate Rswitch as the rate at which packets can be moved from input port to output port. If Rswitch is N times faster than Rline, then only negligible queuing will occur at the input ports. This is because even in the worst case, where all N input lines are receiving packets, and all packets are to be forwarded to the same output port, each batch of N packets (one packet per input port) can be cleared through the switch fabric before the next batch arrives.
But what can happen at the output ports? Let’s suppose that Rswitch is still N times faster than Rline . Once again, packets arriving at each of the N input ports are destined to the same output port. In this case, in the time it takes to send a single packet onto the outgoing link, N new packets will arrive at this output port. Since the output port can transmit only a single packet in a unit of time (the packet transmission time), the N arriving packets will have to queue (wait) for transmission over the outgoing link. Then N more packets can possibly arrive in the time it takes to transmit just one of the N packets that had just previously been queued. And so on. Eventually, the number of queued packets can grow large enough to exhaust available memory at the output port, in which case packets are dropped.
Output port queuing is illustrated in the figure below .
At time t, a packet has arrived at each of the incoming input ports, each destined for the uppermost outgoing port. Assuming identical line speeds and a switch operating at three times the line speed, one time unit later (that is, in the time needed to receive or send a packet), all three original packets have been transferred to the outpoint port and are queued awaiting transmission. In the next time unit, one of these three packets will have been transmitted over the outgoing link. In our example, two new packets have arrived at the incoming side of the switch; one of these packets is destined for this uppermost output port.
Given that router buffers are needed to absorb the fluctuations in traffic load, the natural question to ask is how much buffering is required. For many years, the rule of thumb [RFC 3439] for buffering sizing was that the amount of buffering (B) should be equal to an average round-trip time (RTT, say 250 msec) times the link capacity (C). This result is based on an analysis of the queueing dynamics of a relatively small number of TCP flows. Thus a 10 Gbps link with an RTT of 250 msec would need an amount of buffering equal to B=RTT x C = 2.5 Gbps of buffers.
Recent theoretical and experimental efforts, however, suggest that when there are large number of TCP flows (N) passing through a link , the amount of buffering needed is B = RTT x (C/sq. root of N). With a large number of flows typically passing through large backbone router links, the value of N can be large, with the decrease in needed buffer size becoming quite significant.
A consequence of output port queuing is that a packet scheduler at the output port must choose one packet among those queued for transmission. This selection might be done on a simple basis, such as first-come-first-served (FCFS) scheduling, or a more sophisticated scheduling discipline such as weighted fair queuing (WFQ), which shares the outgoing link fairly among the different end-to-end connections that have packets queued for transmission. Packet scheduling plays a crucial role in providing quality-of-service guarantees.
Similarly, if there is not enough memory to buffer an incoming packet, a decision must be made to either drop the arriving packet (a policy known as drop-tail) or remove one or more already queued packets to make room for the newly arrived packet. In some cases, it may be advantageous to drop (or mark the header of ) a packet before the buffer is full in order to provide a congestion signal to the sender. A number of packet-dropping and –marking policies (which collectively have become known as active queue management (AQM) algorithms) have been proposed and analysed . One of the most widely studied and implemented AQM algorithms is the Random Early Detection (RED) algorithm. Under RED, a weighted average is maintained for the length of the output queue. If the average queue length is less than a minimum threshold, minth , when a packet arrives, the packet is admitted to the queue.
Conversely, if the queue is full or the average queue length is greater than a maximum threshold maxth , when a packet arrives, the packet is marked or dropped.
Finally, if the packet arrives to find an average queue length in the interval [minth, maxth], the packet is marked or dropped with a probability that is typically some function of the average queue length minth, and maxth. A number of probabilistic marking/dropping functions have been proposed, and various version of RED have been analytically modelled, simulated , and/or implemented.
If the switch fabric is not fast enough (relative to the input line speeds) to transfer all arriving packets through the fabric without delay, then packet queuing can also occur at the input ports, as packets must join input port queues to wait their turn to be transferred through the switching fabric to the output port.
To illustrate an important consequence of this queuing, consider a crossbar switching fabric and suppose that:
- All link speeds are identical
- That one packet can be transferred from any one input port to a given output port in the same amount of time it takes for a packet to be received on a input link , &
- Packets are moved from a given input queue to their desired output queue in an FCFS manner.
Multiple packets can be transferred in parallel, as long as their output ports are different. However, if two packets at the front of two input queues are destined for the same output queue, the one of the packets will be blocked and must wait at the input queue – the switching fabric can transfer only one packet to a given output port at a time.
The figure below shows an example, in which two packets (darkly shaded) at the front of their input queues are destined for the same upper-right output port. Suppose that the switch fabric chooses to transfer the packet from the front of the upper-left queue. In this case, the darkly shaded packet in the lower-left queue must wait.
But not only must this darkly shaded packet wait, so too must the lightly shaded packet that is queued behind the packet in the lower-left queue, even though there is no contention for the middle-right output port (the destination for the lightly shaded packet). This phenomenon is known as head-of-the-line (HOL) blocking in an input-queued switch – a queued packet in an input queue must wait for transfer through the fabric (even though its output port is free) because it is blocked by another packet at the head of the line.
It has been shown that due to HOL blocking , the input queue will grow to unbounded length (informally, this is equivalent to saying that significant packet loss will occur) under certain assumptions as soon as the packet arrival rate on the input link reaches only 58 percent of their capacity.