Queueing theory Study Guide

📖 Core Concepts Queueing theory – the math of waiting lines; predicts queue lengths & waiting times. Stochastic operating characteristics – described with probabilities (e.g., “probability that exactly n customers are in the system”). Queueing node – a black‑box where jobs arrive, may wait in a buffer, receive service from one or more servers, then depart. Birth‑Death process – state k = number of jobs; birth = arrival (rate λ), death = departure (rate μ). Kendall’s notation A/S/c – A: inter‑arrival distribution, S: service‑time distribution, c: number of parallel servers. M = memoryless (exponential), D = deterministic, G = general. Service disciplines – FCFS (first‑come‑first‑served), single‑server vs. multiple parallel servers (single queue or separate queues). Queueing networks – several nodes linked by routing; state is the vector \((x{1},…,x{m})\). Jackson networks (open) and closed networks (Gordon–Newell) have product‑form steady‑state distributions. BCMP networks extend product‑form to multiple service disciplines and customer classes. --- 📌 Must Remember Steady‑state balance: \(\displaystyle \sum{n=0}^{\infty}\pi{n}=1\) → determines \(\pi{0}\). M/M/1 queue – Poisson arrivals (λ) + exponential service (μ) + one server. M/G/1 queue – Poisson arrivals (λ) + general service distribution, one server. Little’s‑type relation (Erlang’s modification): \(L =\) average queue length, \(\lambda\) = arrival rate, \(\sigma\) = dropout rate, \(\mu\) = service rate. Effective throughput = proportion of arrivals that receive service. Dropout – customers that leave without service (balking, reneging, or forced by a no‑buffer node). --- 🔄 Key Processes Model a node Identify λ (arrival rate) and μ (service rate). Choose the appropriate A/S/c notation. Write balance equations for each state n: Flow in = flow out → \(\lambda \pi{n-1} = \mu \pi{n}\) (for birth‑death). Normalize using \(\sum \pi{n}=1\) to solve for \(\pi{0}\) and all \(\pi{n}\). Compute performance measures (e.g., average number in system, average waiting time) by weighting each state with its probability. For networks Verify that each node satisfies the product‑form conditions (Jackson/BCMP). Compute node‑wise \(\pi{n}\) then multiply across nodes for the joint distribution. --- 🔍 Key Comparisons M/M/1 vs. M/G/1 Arrival: both Poisson (λ). Service: exponential (μ) vs. arbitrary distribution. Single queue + multiple servers vs. Separate queues per server Single queue → any idle server takes the next job → lower average waiting time. Separate queues → customers choose a line; can create uneven loads. Open (Jackson) vs. Closed (Gordon–Newell) networks Open: external Poisson arrivals, jobs leave the network. Closed: fixed number of jobs circulate; no external arrivals/departures. Jackson vs. BCMP Jackson: only exponential service (M) and FCFS discipline. BCMP: allows multiple service disciplines and class‑dependent routing. --- ⚠️ Common Misunderstandings λ = μ ⇒ stability – actually the system is unstable when λ ≥ μ; the outline assumes steady‑state exists only when λ < μ. “M” means deterministic – “M” denotes memoryless (exponential), not fixed. Buffers are infinite by default – a node may have a finite buffer n or none at all; this changes dropout behavior. Balking = reneging – balking occurs before joining; reneging occurs after joining and waiting. All networks have product‑form solutions – only Jackson, Gordon–Newell, and BCMP satisfy the required conditions. --- 🧠 Mental Models / Intuition Traffic intensity as “load” – think of λ as cars arriving on a road and μ as the road’s capacity; if cars arrive faster than the road can clear them, congestion grows indefinitely. Birth‑Death as a population ladder – each “birth” steps you up one rung, each “death” steps you down; steady‑state probabilities are the long‑run fraction of time spent on each rung. Product‑form = independent stations – imagine each node as a separate dice roll; the overall probability is the product of individual dice probabilities. --- 🚩 Exceptions & Edge Cases No‑buffer node – any arriving job finds all servers busy → immediate dropout (λ effective = 0 when servers busy). Finite buffer of size n – maximum queue length limited; dropouts occur once the buffer is full. Server failures – modeled as an additional Poisson process; effective service rate becomes μ × (1 − failure probability). λ > μ – system does not reach steady‑state; queues grow without bound. --- 📍 When to Use Which M/M/1 – use when both inter‑arrival and service times are well‑approximated by exponential distributions and there is a single server. M/G/1 – use when arrivals are Poisson but service times follow a known non‑exponential distribution (e.g., deterministic, hyper‑exponential). Jackson network – apply to open networks with Poisson external arrivals, exponential service at each node, and FCFS discipline. BCMP network – choose for networks with multiple customer classes, different service disciplines, or non‑exponential service (provided BCMP conditions hold). Erlang’s modification of Little’s law – use when dropout (abandonment) is present and exponential timing assumptions apply. --- 👀 Patterns to Recognize Poisson arrival ↔ exponential inter‑arrival → look for “M” in the A position of Kendall’s notation. Exponential service ↔ memoryless → “M” in the S position. Single queue feeding multiple servers → typically lower average waiting time; appears in “c > 1” with one shared line. Product‑form steady‑state → appears when each node’s arrival process is Poisson (or behaves like Poisson in a network) and service disciplines satisfy BCMP conditions. Dropout terms (σ) in formulas → signals that abandonment is being modeled; expect modified Little’s law. --- 🗂️ Exam Traps Mixing up the order of Kendall’s notation – remember it is A/S/c (arrival / service / servers), not c/A/S. Using M/M/1 formulas for M/D/1 or M/G/1 – the average waiting time and variance differ; only the arrival process is common. Assuming Little’s law holds without steady‑state – if λ ≥ μ the system never stabilizes, so \(L = λW\) is invalid. Treating separate queues as a single shared queue – performance (especially waiting time) can be worse with separate lines. Ignoring dropouts in effective throughput – the proportion of arrivals that receive service is less than 1 when balking/reneging or no‑buffer nodes exist. Believing every network is product‑form – only Jackson, Gordon–Newell, and BCMP networks guarantee that; other topologies may require simulation.