Skip to main content

Network Model (CS4226)

Published on November 30, 2020

In this document, you will find my summary for the Network Performance Model and Queueing Model content covered under CS4226: Internet Architecture course taught by Dr. Richard Ma. I compiled this document with the help of notes written by my good friend Matthew over here.

Performance metrics

Link Rate / BandwidthTheoretical maximum capacity; indirectly related to speed
Throughput / Effective bandwidthActual data transfer rate between source and destination; directly related to speed; with end-to-end delay factored in

End-to-end delay

For a given packet being sent over a link, end-to-end delay is made up of:

  • Transmission delay: dependent on packet size L (bits)L\ (bits) and link rate R (bits/s)R\ (bits/s): dT=LRd_{T} = \frac{L}{R}
  • Propagation delay: dependent on distance and propagation speed
  • Processing delay: dependent on LL
  • Queueing delay: dependent on queue size and dTd_{T}

Queueing delay

Little's Law

The long-term average number LL of customers in a stationary system is equal to the long-term average effective arrival rate λ\lambda multiplied by the average time WW that a customer spends in the system.

In the context of Internet Architecture:

L=λWL = \lambda W

  • LL: Average number of packets in the system
    • L=limt1t0tL(s)dsL = \lim_{t \to \infty} \frac{1}{t} \int^{t}_{0} L(s) ds
  • λ\lambda: Average packet arrival rate for the system
    • λ=limtN(t)t\lambda = \lim_{t \to \infty} \frac{N(t)}{t} where N(t)N(t) is the number of packets which arrived up to time tt
  • WW: Average sojourn time
    • W=limn1ni=1nWiW = \lim_{n \to \infty} \frac{1}{n} \sum^{n}_{i = 1} W_{i} where n is the number of packets and WiW_{i} is the waiting/sojourn time for the iith packet

Modelling arrival time


  • tit_{i}: Arrival time of iith packet
  • TiT_{i}: Inter-arrival time where Titi+1tiT_{i} \triangleq t_{i + 1} - t_{i}

Model TiT_{i}s using independent and identically distributed (i.i.d.) random variable TT which is exponentially distributed, with λ0\lambda \geq 0 condition. Exponential distribution was chosen because of its memoryless property.


  • P(T>t)=eλtP(T > t) = e^{-\lambda t}
  • P(Tt)=1eλtP(T \leq t) = 1-e^{-\lambda t}
  • E[T]=1λE[T] = \frac{1}{\lambda}
  • Memoryless property: P{T>s+t  T>s}=P{T>t}P\{T > s + t\ |\ T > s \} = P\{T > t\}

Merging Poisson processes

TiT_{i}s are i.i.d. random variables distributed as TT with rate λ\lambda. This arrival pattern is called a Poisson process, in which starting time does not matter (memoryless property). Therefore, two Poisson proccesses can be merged to create a new Poisson process:

  • λ=λ1+λ2\lambda = \lambda_{1} + \lambda_{2}
  • T=min{T1,T2}T = min\{T_{1}, T_{2}\}
  • P(T>t)=P(T1>tT2>t)=eλ1teλ2t=e(λ1+λ2)tP(T > t) = P(T_{1} > t \wedge T_{2} > t) = e^{-\lambda_{1} t} e^{-\lambda_{2} t} = e^{-(\lambda_{1} + \lambda_{2}) t}
  • E[T]=1λ1+λ2E[T] = \frac{1}{\lambda_1 + \lambda_2}

M/M/1 queueing model

  • Single server with a queue of infinite length
  • Exponential i.i.d. service time with rate μ\mu


  • Utilization: ρ=λμ\rho = \frac{\lambda}{\mu}
    • Percentage of time whereby the server is busy (1 item in server)
      • Alternatively, mean number of packets in the server
    • Derived from E[L]=λE[Ws]E[L] = \lambda E[W_{s}] where average service time = E[Ws]=1μE[W_{s}] = \frac{1}{\mu}
    • For server to be stable, ρ=λμ<1λ<μ\rho = \frac{\lambda}{\mu} < 1 \Rightarrow \lambda < \mu
  • πi\pi_{i}: Percentage of time or probability that there are exactly ii packets in the system
    • πi=P{L=i}=ρi(1ρ)\pi_{i} = P\{L = i\} = \rho^{i}(1 - \rho)
    • Follows a Geometric distribution

M/M/1 Formulas

  • E[L]=E[packets in queue + server]=ρ1ρ=λμλE[L] = E[\text{packets in queue + server}] = \frac{\rho}{1 - \rho} = \frac{\lambda}{\mu - \lambda}
  • E[packets in queue]=E[L]ρ=ρ21ρE[\text{packets in queue}] = E[L] - \rho = \frac{\rho^{2}}{1-\rho}
  • E[W]=1μλE[W] = \frac{1}{\mu - \lambda}
    • Derived from L=λW1=(μλ)×E[W]E[W]=1μλL = \lambda W \Rightarrow 1 = (\mu - \lambda) \times E[W] \Rightarrow E[W] = \frac{1}{\mu - \lambda}
  • μ=λ+1E[W]\mu = \lambda + \frac{1}{E[W]}
  • λ=μ1E[W]\lambda = \mu - \frac{1}{E[W]}
  • E[Wq]=E[W]E[Ws]=1μλ1μE[W_q] = E[W] - E[W_{s}] = \frac{1}{\mu - \lambda} - \frac{1}{\mu}
    • Derived from E[W]=E[Wq]+E[Ws]E[Wq]=E[W]E[Ws]E[W] = E[W_{q}] + E[W_{s}] \Rightarrow E[W_{q}] = E[W] - E[W_{s}]

Burke's Theorem

Burke's theorem asserts that for a M/M/1 queue in the steady state with arrivals, a Poisson process with rate parameter λ\lambda:

  1. The departure process is a Poisson process with rate parameter λ\lambda.
  2. At time tt the number of packets in the queue is independent of the departure process prior to time tt.

Tandem queues

Given ii consecutive servers with queues in tandem:

  • ρi=λμi\rho_{i} = \frac{\lambda}{\mu_{i}}

Given 2 consecutive servers, s1s_{1} and s2s_{2}:

  • P{L1=j,L2=k}=P{L1=j}×P{L2=k}=ρ1j(1ρ1)×ρ2k(1ρ2)P\{L_{1} = j, L_{2} = k\} = P\{L_{1} = j\} \times P\{L_{2} = k\} = \rho^{j}_{1} (1 - \rho_{1}) \times \rho^{k}_{2} (1 - \rho_{2})

Jackson network

Jackson networks have multiple sources and feedback loops. By Burke's Theorem, merging and splitting of Poisson still apply to these networks.

To do so:

  1. Determine the utilization ρi\rho_{i} for each server ii
  2. Create product form solutions as in #tandem-queues