Chapter 11. Packet Queues and Delay Analysis

Queueing models offer qualitative insights into the performance of communication networks and quantitative estimations of average packet delay. In many networking instances, a single buffer forms a queue of packets. A single queue of packets is a notion of packet accumulation at a certain router or even at an entire network. In the context of data communication, a queuing buffer is a physical system that stores incoming packets, and a server can be viewed as a switch or a similar mechanism to process and route packets to the desired ports or destinations. A queueing system generally consists of a queueing buffer of various sizes and one or more identical servers. this chapter focuses on delay analysis of single queueing units and queueing networks, including feedback. The following topics are covered:

• Little's theorem

• Birth-and-death process

• Queueing disciplines

• Markovian FIFO queueing systems

• Non-Markovian and self-similar models

• Network of queues and delay models

The chapter starts by analyzing two basic theorems: Little's theorem and birth-and-death processes. Next, various scenarios of queueing disciplines are presented: finite versus infinite queueing capacity, one server versus several servers, and Markovian versus non-Markovian systems. Non-Markovian models are essential, as many network applications such as Ethernet, WWW, and multimedia traffic, cannot be modeled by Markovian patterns.

Networks of queues rely on two important and fundamental theorems: Burke's theorem and Jackson's theorem . Burke's theorem presents solutions to a network of several queues. Jackson's theorem is used when a packet visits a particular queue more than once. In such conditions, the network typically contains loops or feedback .