Queueing theory - Network Structures

Queueing Networks Introduction Queueing networks represent systems where customers flow through multiple interconnected service nodes rather than a single queue. Understanding these networks is essential because many real-world systems—from computer networks to manufacturing lines to healthcare facilities—process customers through multiple sequential or parallel stages. This section builds on single-queue theory by showing how to analyze these more complex, interconnected systems. Definition and State Representation A queueing network consists of multiple service nodes connected by customer routing paths. Customers arrive at the network, receive service at one or more nodes, and eventually depart. The key insight is that a queueing network can be analyzed using methods analogous to single-queue systems, but with appropriate modifications. For a network with $m$ nodes, we represent the system state as a vector: $$\mathbf{x} = (x1, x2, \ldots, xm)$$ where $xi$ denotes the number of customers currently at node $i$. This state representation is crucial because it allows us to describe the entire network's configuration at any moment. Unlike a single queue where the state is just a number, a network state must track customers across all nodes simultaneously. Simple Network Structures Tandem Queues The simplest queueing network is a tandem queue (also called a series network), where customers pass through nodes in a fixed, sequential order. For example, consider a manufacturing process where items must be processed at Station A, then Station B, then Station C in that exact order. Each station has its own queue and server(s). A customer completing service at node $i$ immediately joins the queue at node $i+1$ with certainty. Tandem queues are important because they represent processes with strict sequential requirements, and they serve as a building block for understanding more complex network structures. Product-Form Networks: The Power of Analytical Solutions One of the most important discoveries in queueing theory is that certain network structures have product-form stationary distributions. This means the joint stationary distribution of customers across all nodes can be expressed as a product of individual node distributions, making computation tractable. Jackson Networks (Open Networks) A Jackson network is an open queueing network (external arrivals and departures) with the following properties: Arrivals from outside the network follow Poisson processes Service times at each node are exponentially distributed Customers route between nodes according to fixed, probabilistic routing probabilities Nodes have arbitrary (but independent) numbers of servers The remarkable result is that the stationary state distribution of a Jackson network has product form: $$\pi(\mathbf{x}) = \prod{i=1}^{m} \pii(xi)$$ where each $\pii(xi)$ is determined by the traffic intensity at node $i$. Why does this matter? Without this product form, analyzing networks would require solving enormous systems of balance equations. Instead, each node can be analyzed almost as if it were independent—we only need to account for the effective arrival rate that each node receives from the rest of the network. Gordon-Newell Networks (Closed Networks) While Jackson networks have external arrivals, closed queueing networks contain a fixed population of customers that circulate endlessly through the nodes with no external arrivals or departures. The Gordon-Newell theorem proves that closed networks also have product-form stationary distributions: $$\pi(\mathbf{x}) = \frac{1}{G(N)} \prod{i=1}^{m} \rhoi^{xi}$$ where $N$ is the fixed number of customers in the system, $\rhoi$ represents the relative utilization of node $i$, and $G(N)$ is a normalizing constant. Closed networks model systems like: manufacturing facilities where parts continuously cycle, computer systems where a fixed number of jobs are always present, or telecommunications networks with a fixed set of users. Since there's no queue building up indefinitely (customer population is bounded), these systems never become unstable. Extensions: More General Networks BCMP Networks BCMP networks (named after Baskett, Chandy, Kuntz, and Poisson) generalize Jackson and Gordon-Newell networks to allow: Multiple customer classes: Different types of customers with different characteristics General service disciplines: Not just FCFS (First-Come-First-Served), but also priority queues, LCFS (Last-Come-First-Served), or processor sharing Class-dependent routing: Different customer classes can follow different paths through the network Remarkably, BCMP networks retain the product-form property, meaning the computational advantages of product-form networks extend to these much more realistic scenarios. This generality makes BCMP networks widely applicable to real systems with heterogeneous customer types and non-standard service policies. Buzen's Algorithm Computing the normalizing constant for closed product-form networks requires summing over many states, which can be computationally expensive. Buzen's algorithm provides an efficient recursive method to compute this normalizing constant without enumerating all possible states. While you should understand that efficient computational methods exist for product-form networks, the specific implementation of Buzen's algorithm is less critical than understanding its purpose: it makes closed network analysis computationally feasible even for moderately large systems. <extrainfo> Specialized Network Models Kelly Networks Kelly networks extend product-form results to networks where customers belong to distinct classes and each class receives different priority levels at service nodes. Despite the priority-based service discipline, Kelly networks maintain product-form stationary distributions. This elegance—that priority-based routing still yields product-form solutions—demonstrates the power of queueing theory's analytical framework. </extrainfo>