Network Model (CS4226)

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#

MetricDefinition
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#

Given:

  • 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.

Properties:

  • 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

Definitions#

  • 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

Resources#