📊 Queueing Theory & Packet Routing

An Interactive Tutorial for Understanding Network Performance

🎯 Introduction: What is Queueing Theory? ▼

Real-World Analogy

Think of a post office or bank:

  • Customers arrive randomly (like data packets)
  • They wait in line (the queue/buffer)
  • Servers help them (transmission lines)
  • Then they leave (packet transmitted)
💡 Key Idea: Queueing theory helps us calculate:
  • How long customers wait (delay)
  • How many customers are waiting (queue length)
  • How busy the servers are (utilization)
  • How many customers get served per hour (throughput)

Basic Queue System

Arrivals (λ)
→
Buffer/Queue
→
Server (μ)
→
Departures

Important Notation:

  • λ (lambda) = arrival rate (packets per second)
  • μ (mu) = service rate (packets per second per server)
  • ρ (rho) = utilization = λ/μ (how busy the system is)
  • n = number of customers/packets in the system
  • Pn = probability of being in state n
🔄 State-Dependent Queues (Birth-and-Death Process) ▼

What Makes a Queue "State-Dependent"?

In a regular M/M/1 queue, λ and μ are always the same. But in state-dependent queues, they change based on how many customers are in the system!

⚠️ Key Difference:
Regular Queue: λ and μ are constant
State-Dependent: λn and μn depend on state n

Why "Birth and Death"?

  • Birth = A new customer arrives (packet enters)
  • Death = A customer leaves (packet transmitted)
Probability of arrival in time Δt: λnΔt
Probability of departure in time Δt: μnΔt
Probability of no arrival: 1 - λnΔt
Probability of no departure: 1 - μnΔt

Balance Equations

The core principle: Rate IN = Rate OUT

(λn + μn) · Pn = λn-1 · Pn-1 + μn+1 · Pn+1

This means: ways to leave state n = ways to enter state n

🎓 Example: State Transitions

From state 2 to state 3: Need an arrival → rate = λ2

From state 3 to state 2: Need a departure → rate = μ3

🖥️ M/M/2 Queue: Two-Server System ▼

What is M/M/2?

A queueing system with TWO servers (like a router with 2 transmission lines)

M/M/2 System Diagram

Arrivals
(λ)
→
Buffer
→
Server 1 (μ)
Server 2 (μ)
→
Out

How Service Rates Work (This is the KEY!):

State Customers in System Service Rate (μn) Explanation
0 0 0 Empty - no service
1 1 μ Only 1 server is busy
2 2 2μ BOTH servers are busy!
3 3 2μ Still both busy (1 waiting)
4+ 4+ 2μ Both busy (multiple waiting)
💡 The Big Insight:
When n ≥ 2, both servers work simultaneously, so the service rate doubles to 2μ!
You can only serve 2 packets at once (you only have 2 servers).

State Diagram:

    λ          λ          λ          λ
0 ----→ 1 ----→ 2 ----→ 3 ----→ 4 ...
    ←----  ←----  ←----  ←----
      μ        2μ       2μ       2μ

🎓 Real-World Example: Two Checkout Lines

Imagine a store with 2 cashiers:

  • If 1 customer arrives → 1 cashier helps them (rate = μ)
  • If 2 customers are there → both cashiers work (rate = 2μ)
  • If 5 customers are there → still only 2 cashiers working (rate = 2μ), 3 wait in line
📐 Key Formulas for M/M/2 ▼

Important Formulas (Don't panic - we'll explain!)

1. Utilization (ρ)

ρ = λ / (2μ)

What it means: How busy each server is (must be < 1 for stability)

⚠️ Note: For M/M/1, ρ = λ/μ, but for M/M/2, we divide by 2μ because we have 2 servers!

2. General Formula for Pn

Pn = (λ0 · λ1 · ... · λn-1) / (μ1 · μ2 · ... · μn) · P0

For M/M/2 specifically:

Pn = 2ρn · P0

3. Probability of Empty System (P0)

P0 = (1 - ρ) / (1 + ρ)

What it means: Probability that the system is empty (no customers)

4. Average Number of Customers (E[n])

E[n] = 2ρ / (1 - ρ²)

What it means: Expected number of packets in the system (waiting + being served)

5. Average Delay (E[W])

E[W] = 1 / (μ · (1 - ρ²))

What it means: How long a packet waits on average

Derived using Little's Law: E[n] = λ · E[W]

💡 Why M/M/2 is Better than M/M/1:
Since ρ = λ/(2μ) for M/M/2 vs ρ = λ/μ for M/M/1, the utilization is HALF as much!
Lower ρ means lower delay and better performance! 🎉

🎓 Numerical Example

Given: λ = 8 packets/sec, μ = 5 packets/sec

Calculate:

  • ρ = 8/(2×5) = 8/10 = 0.8
  • P0 = (1-0.8)/(1+0.8) = 0.2/1.8 ≈ 0.111
  • E[n] = 2(0.8)/(1-0.64) = 1.6/0.36 ≈ 4.44 packets
  • E[W] = 1/(5×0.36) = 1/1.8 ≈ 0.556 seconds
⚡ System Throughput ▼

What is Throughput?

Throughput = The actual rate at which packets are served (leaving the system)

For M/M/2 System:

Throughput = μ · P1 + 2μ · (1 - P0 - P1)

Breaking it Down:

System State Service Rate Probability Contribution
State 1 (1 packet) μ P1 μ · P1
State 2+ (2+ packets) 2μ P2 + P3 + ... = 1 - P0 - P1 2μ · (1 - P0 - P1)
💡 Key Insight:
When both servers are busy (state ≥ 2), throughput is doubled!
In state 0, throughput is 0 (nobody to serve).

For M/M/c (c servers):

The pattern extends:

M/M/3: μ·P1 + 2μ·P2 + 3μ·(1 - P0 - P1 - P2)
M/M/4: μ·P1 + 2μ·P2 + 3μ·P3 + 4μ·(1 - P0 - P1 - P2 - P3)
🌐 Packet Routing Algorithms ▼

Three Approaches to Route Packets

Algorithm 1: Cost-Based (Shortest Path First)

Goal: Find the cheapest path from source to destination

How it works:

  • Each link has a "cost" (could be distance, time, or money)
  • Calculate total cost for each possible path
  • Choose the path with minimum cost
  • Drop packets sent on inefficient paths

🎓 Example: The "$90 Budget" Problem

Scenario: You have $90 to get from point A to point F

Path 1: A → B → E → F (costs: $30 + $20 + $30 = $80)

Path 2: A → C → D → F (costs: $25 + $15 + $20 = $60) ✓

Result: Choose Path 2 (cheaper). Packets on Path 1 get dropped!

Metaphor: It's like choosing the cheapest flight - you book that one and ignore the expensive options.

Algorithm 2: Flooding

Goal: Make sure the packet reaches the destination (reliability over efficiency)

How it works:

  • Send packets on ALL possible paths
  • Avoid creating loops (no infinite cycles)
  • Create a spanning tree (tree structure with no loops)
  • Many duplicate packets, but guaranteed delivery

🎓 Example: Emergency Broadcast

Like sending a group text: Everyone gets the message through multiple routes!

  • A sends to B and C
  • B sends to D and E (but not back to A - that would be a loop)
  • C sends to F and G (but not back to A)

Rule: Never send back to where you came from (prevents loops)

⚠️ Trade-off:
Pro: Guaranteed delivery, works even if some links fail
Con: Creates many duplicate packets, wastes bandwidth

Algorithm 3: Shortest Path Tree

Goal: Combine the best of both - efficient AND organized

How it works:

  • Use cost information from Algorithm 1
  • Use tree structure from Algorithm 2
  • Create a diagram showing ONLY the optimal paths
  • Visualize the "winning" routes as a tree

🎓 Example: GPS Navigation Map

Think of Google Maps:

  • Calculates shortest path to each destination
  • Shows you ONE best route (not all possible routes)
  • Creates a "tree" of optimal paths from your location

This is the easiest algorithm to visualize - just draw the winning paths!

Calculating Duplicate Packets

In routing algorithms, you can calculate duplicate packets using:

Duplicate Packets ≈ (Number of paths tried) - (Optimal paths used)

Or use the DVR (Distance Vector Routing) tables to count entries.

💡 Quick Comparison:
Algorithm 1: Cheapest route, fewest packets ✓
Algorithm 2: Most reliable, most packets ✗
Algorithm 3: Best visualization, practical use ✓✓
📝 Practice Problems & Tips for Teaching ▼

Teaching Tips

🎓 How to Explain This to Your Class:
  1. Start with real-world examples (post office, bank, store checkout)
  2. Use visuals (show the queue diagrams on this website!)
  3. Build intuition first (explain WHY before showing formulas)
  4. Work through numbers (use simple examples with real values)
  5. Compare systems (why is M/M/2 better than M/M/1?)

Common Questions Students Ask:

Q: "Why do we need all these formulas?"

A: Network engineers use these to:

  • Decide how many transmission lines a router needs
  • Calculate if users will experience lag
  • Know when to upgrade equipment
  • Optimize network performance and save money

Q: "What's the most important concept?"

A: Understanding that ρ must be < 1 for stability!

If λ ≥ service capacity, the queue grows infinitely (system crashes).

Q: "How do I remember all these formulas?"

A: Focus on the pattern:

  1. Set up balance equations (Rate IN = Rate OUT)
  2. Solve for Pn in terms of P0
  3. Use normalization (all probabilities sum to 1) to find P0
  4. Calculate E[n] using Σ(n · Pn)
  5. Use Little's Law to get delay: E[W] = E[n]/λ

Quick Reference Card:

System ρ (utilization) Key Feature
M/M/1 λ/μ 1 server, simple
M/M/2 λ/(2μ) 2 servers, μ₁=μ, μₙ=2μ (n≥2)
M/M/c λ/(cμ) c servers, μₙ=min(n,c)·μ

Study Recommendations:

  • ✓ Master the M/M/1 queue first (foundation for everything)
  • ✓ Understand why μₙ changes in M/M/c systems
  • ✓ Practice calculating P₀ for different systems
  • ✓ Work through the series derivations (important for exams)
  • ✓ Draw state diagrams for each problem
✨ Quick Summary Cheat Sheet ▼

The Essential Concepts (TL;DR)

State-Dependent Queues

  • Arrival rate (λₙ) and service rate (μₙ) depend on system state n
  • Birth = arrival, Death = departure
  • Balance equations: Rate IN = Rate OUT

M/M/2 Queue (Two Servers)

  • μ₁ = μ (only 1 server busy)
  • μₙ = 2μ for n ≥ 2 (both servers busy)
  • ρ = λ/(2μ) (note the 2!)
  • Lower delay than M/M/1 due to lower ρ

Key Formulas

  • P₀ = (1-ρ)/(1+ρ)
  • Pₙ = 2ρⁿ · P₀
  • E[n] = 2ρ/(1-ρ²)
  • E[W] = 1/(μ(1-ρ²))
  • Throughput = μ·P₁ + 2μ·(1-P₀-P₁)

Routing Algorithms

  • Cost-Based: Choose cheapest path, drop others
  • Flooding: Send everywhere, avoid loops
  • Shortest Path Tree: Visualize optimal routes

⚠️ Critical Rules for Stability

  • ρ must be < 1 (arrival rate < total service capacity)
  • For M/M/c: λ < c·μ
  • If ρ ≥ 1, queue grows infinitely → system fails!