4005-741-01 Advanced Computer Networks
Module 1B. Theory -- Queuing Theory
Lecture Notes

Questions

• Given:
  • A network topology (graph)
  • Capacity of each link (bits/sec)
  • Route from each source to each destination
  • Traffic level (packets/sec) from each source to each destination
  • Packet size distribution (bits/packet)

• Questions:
  1. How long does it take the average packet to travel from source to destination?
  2. What is the probability that a packet will be dropped due to buffer overflow?

Queuing Theory

• For mathematical derivations, see:
  • "Queuing Theory" (PDF -- 144,633 bytes)
  • "Delay Analysis" (PDF -- 494,336 bytes)

Unbounded M/M/1 Queue

• Exponential distribution of interarrival times, λ = mean arrival rate

• Exponential distribution of service times, μ = mean service rate

• One server

• Traffic intensity ρ = λ / μ

• Mean queue length N = ρ / (1 − ρ)

• Little's Theorem; applies to any unbounded queue: Mean waiting time T = N / λ

• Mean waiting time T = ρ / (λ(1 − ρ)) = 1 / (μ − λ)

Unbounded M/G/1 Queue

• Exponential distribution of interarrival times, λ = mean arrival rate

• General (any) distribution of service times
  • μ = mean service rate
  • σ = standard deviation of service rate

• One server

• Traffic intensity ρ = λ / μ

• Mean queue length N = ρ + ρ² (1 + σ²/μ²) / (2 (1 − ρ))

• Mean waiting time T = N / λ

Unbounded M/C/1 Queue

• Exponential distribution of interarrival times, λ = mean arrival rate

• Constant service time, μ = mean service rate, σ = 0

• One server

• Traffic intensity ρ = λ / μ

• Mean queue length N = (1 − ρ/2) ρ / (1 − ρ)

• Mean waiting time T = (1 − ρ/2) / (μ − λ)

Bounded M/M/1 Queue

• Exponential distribution of interarrival times, λ = mean arrival rate

• Exponential distribution of service times, μ = mean service rate

• One server

• Traffic intensity ρ = λ / μ

• Maximum queue length = n

• If ρ ≠ 1:

  • Mean queue length N = (nρⁿ⁺² − (n + 1)ρⁿ⁺¹ + ρ) / ((ρⁿ⁺¹ − 1)(ρ − 1))

  • Mean waiting time T = (nρⁿ⁺¹ − (n + 1)ρⁿ + 1) / (μ(ρⁿ − 1)(ρ − 1))

  • Dropped fraction D = ρⁿ(ρ − 1) / (ρⁿ⁺¹ − 1)

• If ρ = 1:

  • Mean queue length N = n / 2

  • Mean waiting time T = (n + 1) / (2μ)

  • Dropped fraction D = 1 / (n + 1)

Advanced Computer Networks • 4005-741-01 • Fall Quarter 2009

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2009 Alan Kaminsky. All rights reserved. Last updated 11-Sep-2009. Please send comments to ark­@­cs.rit.edu.