Queue

queue theory

• performance evaluation

  • $\lambda$ average arrival rate, packets per second
  • $\mu$ average service rate, packets servered per second
  • $c$ number of servers
  • $\rho = \lambda/c\mu$ traffic congestion in servers
    • if >1 averge exceeds service capability
    • if = 1 randomness prevents queue from emptying
  • $p_n$ is probability of a particular number n customers in the system
  • expected number in system: $L = \sum(n p_n)$
  • expected number in queue: $L = \sum_{n=c+1}((n-c) p_n)$
  • time : $T = T_q + S$ time in queue + service time
  • little law
    • $W = E[T] W_q = E[T_q]$ mean waiting time in system
    • $L = \lambda W$
    • $E[T] = E[T_q] + E[S]$ to get $W = W_q + 1/\mu$
    • expected servered people: $E[N_s] = L-L_q = \lambda(W-W_q) = \lambda(1/\mu) = \lambda/\mu$
    • $c = 1, r = \rho , L-L_q = \sum_{n=1} np- \sum_{n=1} (n-1)p = \sum_{n=1} p_n = 1-p_0=\rho$
  • busy probability
    • for G/G/c system, $E[N_s] = r$
    • $P_b = \rho$ one server being busy brobability
    • ...

• rate transition diagrams

  • a type of continuous-time Markov chain
  • $(\lambda_n+\mu_n)p_n =(\lambda_{n-1}+\mu_{n-1})p_{n-1}+(\lambda_{n+1}+\mu_{n+1})p_{n+1}$
  • $p_3 = \frac{\lambda_2 \lambda_1 \lambda_0}{\mu_3 \mu_2 \mu_1} p_0 $
  • $p_n = \prod_{i=1}^n\frac{\lambda_{i-1}}{\mu_i}$

• M/M/1 system

  • Exponentially distributed
    • interarrival time $TI(t)=\lambda e^{-\lambda t}$
    • service time $TI(t)=\mu e^{-\mu t}$
  • if all $\mu$ and $\lambda$ equal get $p_n = p_0 (\frac{\lambda}{\mu})^n$
  • $p_0 = 1-\rho$ - > $p_n = (1-\rho)\rho^n$