*Queuing Delay and Packet Loss*

The most complex and interesting element of nodal delay is the queuing delay, d_{queue}. In reality, queuing delay is so important and interesting in computer networking that thousands of papers and several books have been written about it [Bertsekas 1991; Daigle 1991; Kleinrock 1975, 1976; Ross 1995]. We give only a high-level, intuitive discussion of queuing delay here; the more interested reader may want to browse through some of the books (or even finally write a PhD thesis on the subject). Unlike the other three delays (namely, d_{proc}, d_{trans}, and d_{prop}), the queuing delay can fluctuate from packet to packet. For instance, if 10 packets arrive at an empty queue at the same time, the first packet transmitted will suffer no queuing delay, while the last packet transmitted will suffer a relatively large queuing delay (while it waits for the other nine packets to be transmitted). Therefore, when characterizing queuing delay, one normally uses statistical measures, such as average queuing delay, variance of queuing delay, and the possibility that the queuing delay exceeds some specified value.

When is the queuing delay large and when is it insignificant? The answer to this question depends on the rate at which traffic arrives at the queue, the transmission rate of the link, and the nature of the arriving traffic, that is, whether the traffic arrives occasionally or arrives in bursts. To get some insight here, let a denote the average rate at which packets arrive at the queue (a is in units of packets/sec). Recall that R is the transmission rate; that is, it is the rate (in bits/sec) at which bits are pushed out of the queue. Also suppose, for simplicity, that all packets consist of L bits. Then the average rate at which bits arrive at the queue is La bits/sec. Finally, suppose that the queue is very big, so that it can hold basically an infinite number of bits. The ratio La/R, called the traffic intensity, often plays an important role in estimating the extent of the queuing delay. If La/R > 1, then the average rate at which bits arrive at the queue exceeds the rate at which the bits can be transmitted from the queue. In this unfortunate situation, the queue will tend to increase without bound and the queuing delay will approach infinity. Therefore, one of the golden rules in traffic engineering is: Design your system so that the traffic intensity is no greater than 1.

Now think about the case La/R ≤ 1. Here, the nature of the arriving traffic impacts the queuing delay. For instance, if packets arrive periodically -that is, one packet arrives every L/R seconds - then every packet will arrive at an empty queue and there will be no queuing delay. On the other hand, if packets arrive in bursts but occasionally, there can be a considerable average queuing delay. For instance, suppose N packets arrive simultaneously every (L/R)N seconds. Then the first packet transmitted has no queuing delay; the second packet transmitted has a queuing delay of L/R seconds; and more commonly, the nth packet transmitted has a queuing delay of (n - 1)L/R seconds, We leave it as an exercise for you to calculate the average queuing delay in this example.

The two examples of periodic arrivals explained above are a bit academic. Normally, the arrival process to a queue is random; that is, the arrivals do not follow any pattern and the packets are spaced apart by random amounts of time. In this more realistic case, the quantity La/R is not generally enough to fully characterize the queuing delay statistics. However, it is useful in gaining an intuitive understanding of the extent of the queuing delay. Particularly, if the traffic intensity is close to zero, then packet arrivals are few and far between and it is unlikely that an arriving packet will find another packet in the queue. Thus the average queuing delay will be close to zero. On the other hand, when the traffic intensity is close to 1, there will be intervals of time when the arrival rate exceeds the transmission capacity (due to variations in packet arrival rate), and a queue will form during these periods of time; when the arrival rate is less than the transmission capacity, the length of the queue will shrink. However, as the traffic intensity approaches 1, the average queue length gets larger and larger. These qualitative dependence of average queuing delay on the traffic intensity is shown in the following figure.

One important feature of above figure is the fact that as the traffic intensity approaches 1, the average queuing delay increases quickly. A small percentage increase in the intensity will result in a much larger percentage-wise increase in delay. Maybe you have experienced this occurrence on the highway. If you frequently drive on a road that is normally congested, the fact that the road is normally congested means that its traffic intensity is close to 1. If some event causes an even a little larger-than-usual amount of traffic, the delays you experience can be massive.

### Packet Loss

In our discussions above, we have assumed that the queue is competent of holding an infinite number of packets. In fact a queue preceding a link has limited capacity, though the queuing capacity very much depends on the router design and cost. Because the queue capacity is limited, packet delays do not really approach infinity as the traffic intensity approaches 1. Instead, a packet can arrive to find a full queue. With no place to store such a packet, a router will drop that packet: that is, the packet will be lost.From an end-system viewpoint, a packet loss will look like a packet having been transmitted into the network core but never emerging from the network at the destination. The fraction of lost packets increases as the traffic intensity increases. For that reason, performance at a node is often measured not only in terms of delay, but also in terms of the possibility of packet loss. As we'll discuss in the following chapters, a lost packet may be retransmitted on an end-to-end basis in order to ensure that all data are finally transferred from source to destination