6-3-Queueing-Performance.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Queueing Theory: Section 3 - Performance Metrics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In sections 1 and 2, we considered a single-server queue with Poisson arrivals (with rate $\\lambda$) and exponential service times (with rate $\\mu$).  The headcount process, $\\{X(t),\\ t \\geq 0\\}$, tracks the number of customers in the system, and is an irreducible continuous-time Markov chain on state space $\\mathcal{S} = \\{0, 1, 2, \\dots\\}$:\n",
    "\n",
    "$$\\begin{aligned}\n",
    "    \\text{state $0$:}&& p_{01} &= 1 & v_0 &= \\lambda \\\\\n",
    "    \\ \\\\\n",
    "    \\text{state $i \\geq 1$:}&& p_{ij} &= \\begin{cases} \\displaystyle\\frac{\\lambda}{\\lambda+\\mu} & j = i+1 \\\\ \\displaystyle\\frac{\\mu}{\\lambda+\\mu} & j = i-1 \\\\ 0 & \\text{otherwise} \\end{cases} & v_i &= (\\lambda+\\mu)\n",
    "  \\end{aligned}$$\n",
    "\n",
    "We saw in section 2 that, if $\\lambda < \\mu$, the CTMC is positive recurrent has a geometric stationary distribution:\n",
    "$$\\pi_i = \\left(\\frac{\\lambda}{\\mu}\\right)^i \\left(1 - \\frac{\\lambda}{\\mu}\\right) \\qquad i \\in \\mathcal{S}$$\n",
    "\n",
    "Although we solved the balance equations to get the stationary distribution, Exercise 2.1 showed that the embedded DTMC of the uniformized CTMC was the exactly same as the reflected random walk (with $p = \\frac{\\lambda}{\\lambda + \\mu}$).  Therefore, we can immediately use our results from the reflected random walk to analyze this queue."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stability Condition\n",
    "\n",
    "What if $\\lambda > \\mu$?  This corresponds to the reflected random walk with $p > \\frac{1}{2}$ – the Markov chain is transient.  (Remember that transience and recurrence of states in a CTMC are the same as the embedded DTMC.)\n",
    "\n",
    "Intuitively, $\\lambda$ is rate at which customers arrive into the system while $\\mu$ can be considered to be the rate at which customers can be processed.  When $\\lambda > \\mu$, the system will not be able to keep up with the flow up customers into the system and the number of customers waiting will build up over time.  Of course, this happens stochastically – the actual number of customers in the system will fluctuate.\n",
    "\n",
    "We will generally assume that the system is **stable**: the CTMC is positive recurrent and a stationary distribution exists.  In the case of this particular system, the **stability condition** is $\\lambda < \\mu$ (later, we will look at different systems that have different stability conditions).  This is often also expressed as a ratio:\n",
    "$$ \\rho \\overset{\\mathsf{def}}{=} \\frac{\\lambda}{\\mu} < 1$$\n",
    "(Here $\\rho$ is the Greek letter “rho” and the definition of $\\rho$ may be different for different queueing systems.)\n",
    "\n",
    "In terms of $\\rho$, the stationary distribution is $\\text{Geometric}(1 - \\rho)$ or, $\\pi_i = \\rho^i (1 - \\rho)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.1\n",
    "\n",
    "Change the parameters in Section 1 so that $\\lambda > \\mu$ and simulate a sample path.  What do you notice about the headcount process $\\{X(t),\\, t \\geq 0\\}$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Steady-State Performance Metrics\n",
    "\n",
    "Recall that, for a positive recurrent CTMC, as $t \\to \\infty$, $p_{ij}(t) \\to \\pi_j$ for any $i \\in \\mathcal{S}$.  This means that eventually, the system reaches a “steady-state” distribution, no matter initial state $i$ and the steady-state distribution is equal to the stationary distribution.\n",
    "\n",
    "With some abuse of notation, we can think of $X(\\infty)$ as the number of customers in the system in steady-state – after the system has been running for a long time.  The distribution of $X(\\infty)$ is the stationary distribution: $\\mathsf{P}(X(\\infty) = i) = \\pi_i$.\n",
    "\n",
    "Examples of steady-state performance metrics:\n",
    "* Probability that the system is empty: $\\pi_0 = 1 - \\rho$\n",
    "* Probability that the server is busy: $1 - \\pi_0 = \\rho$\n",
    "* Expected number of customers in the system: $\\displaystyle\\frac{\\rho}{1 - \\rho}$\n",
    "* Expected queue length: $\\displaystyle\\frac{\\rho^2}{1 - \\rho}$\n",
    "* Expected wait time: $\\displaystyle\\frac{\\rho}{\\mu - \\lambda}$\n",
    "* Expected sojourn time: $\\displaystyle\\frac{1}{\\mu - \\lambda}$\n",
    "\n",
    "The **wait time** of a customer is the amount of time spent waiting in line.  Since the queue operates under a first-come first-served policy, this is equal to the amount of time it takes for all customers that are already in the system to be processed.  That is, if there are $k$ customers in the system, a new arrival will have a wait time that follows an $\\text{Erlang}(k, \\mu)$ distribution (the sum of the $k$ service requirements of those already in the system, including the remaining service time of the customer currently in service).\n",
    "\n",
    "The **sojourn time** of a customer is the total amount of time spent in the system: waiting in line plus time in service (equivalently, the customer's departure time minus her arrival time).\n",
    "\n",
    "### Example: Steady-State Expected Queue Length\n",
    "\n",
    "Recall that $X(t)$ represents the number in system at time $t$, including the customer in service (if the system is not empty).  What if we simply wanted the number waiting in line (the queue length)?\n",
    "$$\\text{queue length at time } t = \\max\\{0, X(t) - 1\\}$$\n",
    "Therefore\n",
    "$$\\begin{aligned}\n",
    "    \\mathsf{E}[\\text{steady-state queue length}] &= \\mathsf{E}[\\max\\{0, X(\\infty) - 1\\}] \\\\\n",
    "    &= \\sum_{k=0}^\\infty \\max\\{0, k - 1\\} \\pi_k \\\\\n",
    "    &= \\sum_{k=1}^\\infty (k - 1) \\pi_k \\\\\n",
    "    &= \\sum_{k=1}^\\infty k \\pi_k - \\sum_{k=1}^\\infty \\pi_k \\\\\n",
    "    &= \\frac{\\rho}{1 - \\rho} - (1 - \\pi_0) \\\\\n",
    "    &= \\frac{\\rho}{1 - \\rho} - \\rho \\\\\n",
    "    &= \\frac{\\rho^2}{1 - \\rho}\n",
    "  \\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3.2\n",
    "\n",
    "Calculate the steady-state expected headcount, wait time, and sojourn time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Poisson Arrivals See Time Averages (PASTA)\n",
    "\n",
    "Another useful application of the stationary distribution is that it also describes, in some sense, the experience of a typical customer.  More specifically:\n",
    "\n",
    "Let $N(t)$ be a Poisson process and let $S_n$ be the time of the $n$th arrival.  Let $\\{X(t),\\, t \\geq 0\\}$ be the headcount process.\n",
    "\n",
    "We will denote by $X(S_n-)$ as the state of the headcount process *immediately prior* to the $n$th arrival.  Think of this as taking a “snapshot” of the system immediately prior to time $S_n$.  $X(S_n-)$ is the number of customers that the $n$th arrival sees in the system upon arrival (not including herself).  \n",
    "\n",
    "Let $f(x)$ be a function (e.g., some performance metric).  Then\n",
    "$$ \\lim_{n \\to \\infty} \\frac{1}{n} \\sum_{k=1}^n f(X(S_n-)) = \\lim_{t \\to \\infty} \\frac{1}{t} \\int_0^t f(X(s)) \\,ds $$\n",
    "In other words, averaging the performance over these snapshots at Poisson arrivals is the same as averaging over all time (in the long-run).  Rather than sampling continuously over time, we only need to sample at Poisson arrivals.\n",
    "\n",
    "Therefore, the long-run probability that an arrival sees $i$ customers in the system is $\\pi_i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Little's Law\n",
    "\n",
    "An easier way to calculate steady-state performance metrics is using Little's Law.\n",
    "$$\\text{number in system} = \\text{rate into system} \\times \\text{time spent in system}$$\n",
    "where these quantities are long-run averages.\n",
    "\n",
    "Let:\n",
    "* $A(t)$ be the arrival counting process\n",
    "* $T_k$ be the sojourn time of the $k$th customer\n",
    "* $X(t)$ be the number of customers in the system at time $t$\n",
    "\n",
    "If the following long-run averages exist and are finite:\n",
    "$$ \\lambda = \\lim_{t \\to \\infty} \\frac{A(t)}{t} \\qquad W = \\lim_{n \\to \\infty} \\frac{1}{n} \\sum_{k=1}^n T_k$$\n",
    "then the following long-run average exists and is finite:\n",
    "$$L = \\lim_{t \\to \\infty} \\frac{1}{t} \\int_0^t X(s)\\, ds $$\n",
    "and\n",
    "$$L = \\lambda W$$\n",
    "\n",
    "The power of Little's Law is that it applies quite broadly and we have flexibility in defining the “system.”\n",
    "\n",
    "If we consider the “system” to include the queue and the server, then:\n",
    "* $L = \\displaystyle\\frac{\\rho}{1 - \\rho}$\n",
    "* $\\lambda = \\lambda$\n",
    "* $W = \\displaystyle\\frac{1}{\\mu - \\lambda}$\n",
    "\n",
    "If we consider the “system” to be just the server, then:\n",
    "* $L = \\rho$\n",
    "* $\\lambda = \\lambda$\n",
    "* $W = \\displaystyle\\frac{1}{\\mu}$\n",
    "\n",
    "If we consider the “system” to be just the queue, then:\n",
    "* $L = \\displaystyle{\\rho^2}{1  - \\rho}$\n",
    "* $\\lambda = \\lambda$\n",
    "* $W = \\displaystyle\\frac{\\rho}{\\mu - \\lambda}$\n",
    "\n",
    "**Note:** Little's Law does not depend on a first-come first-served (FCFS) policy (and neither did the CTMC formulation).  Therefore, the steady-state performance metrics above are the same for a broad range of policys, not necessarily FCFS.  For example, if instead it were a *last*-come first-served policy, the expected wait time would be the same.  Also, if the next customer to be served was chosen randomly from all customers waiting in line, the expected wait time would be exactly the same.  Of course, the particular experience of an individual customer for a particular sample path will be different under these different policies, but the stochastic dynamics of the number of customers in the system are unchanged and, by Little's Law, many of the performance metrics of the system remain the same."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}