Queueing Theory 

• How to characterize a queueing system:
  1. the distribution of inter-arrival times 
  2. the distribution of service times
  3. the number of servers
  4. the buffer size 
  5. the population of customers 
  6. the service discipline (FIFO, LIFO, priority, random order, etc.)
• Performance measure:
  • transient and steady state analysis
  • distribution of delay, backlog
  • moments of delay, backlog (e.g., average, variance)
  • delay: queueing delay, sojourn time (time spent in a queueing system/node or a queueing network)
  • idle period, busy period: distribution, moments (e.g.,average)
• Classes of queues:
  • M/M/m
  • M/GI/m, GI/M/m, M/G/m, G/M/m
    • GI: renewal processes
    • G: arbitrary stochastic processes, e.g., Markov processes.  Typically assume G is a stationary and ergodic process.
  • GI/GI/m
  • G/G/m
    • In some papers/books, G/G/m means GI/GI/m.
• Delay and backlog are stochastic processes such as birth-death process, quasi-birth-death process, Markov chain.
• M/M/K/B/P denotes that 1) the distribution of inter-arrival times is exponential; 2) the distribution of service times is exponential; 3) there are K servers; 4) the buffer size is B; 5) the population of customers is P.
• Stability of queueing networks (queues do not go to infinity), stability of a network (control-theoretical perspective: Bounded input bounded output BIBO).   Prove TCP can achieve network stability.
• For a scheduler, performance analysis and resource allocation are dual problems.
  • The problem of performance analysis is following:    
    • Given a scheduler (e.g., GPS or EDF) and the allocated resource (e.g., bandwidth) for each flow, what is the QoS (e.g., loss probability or delay) experienced by each flow?    
    • The purpose of performance analysis is to map the allocated resource to the QoS, given a specific scheduler.
  • The problem of resource allocation is following:     
    • Given a scheduler and the QoS requirement of each flow, how much resource is required to be allocated?   
    • The purpose of resource allocation is to map the QoS requirements to the allocated resources.   It is an inverse problem of performance analysis.
• Applications
  • How to analyze a two-leaky-bucket system, characterized by three Usage Parameter Control (UPC) parameters, the sustainable rate $r_s$, the peak rate $r_p$, and the bucket size $b_T$ (or maximum burst size).  Maximum burst size (MBS) is defined as the maximum size of a burst that can be sent at the peak rate.   The relation between MBS and the bucket size is MBS = b_T/(r_p - r_s).  Note that $b_T$ is for the bucket with the token rate at $r_s$ and the bucket with the token rate at $r_p$ has a size of zero.

Self similarity

• Four related concepts:
  • Self-similar process (could be either continuous-time process or discrete-time process)
    • (Exact) second-order self-similarity
      • A process {X_n} is second-order self-similar if all the aggregated processes {X_n^{(m)} have the same autocorrelation function R^{(m)}(n) as that of the original process {X_n}.
    • Asymptotic second-order self-similarity
      • A process {X_n} is asymptotic second-order self-similar if the aggregated processes {X_n^{(m)} have autocorrelation functions R^{(m)}(n) that converge to that of the original process {X_n}, as m goes to infinity.
  • Heavy-tailed (long-tailed) distribution
    • A CDF F(x) is heavy-tailed if lim_{x goes to \infty} (1-F(x-y) )/(1-F(x)) = 1, for all $y \in R$.
    • The tail of a heavy-tailed distribution function decreases to zero more slowly than any exponential, i.e., for a heavy-tailed random variable X, \lim_{x goes to \infty} P(X>x) * exp(a*x) = \infty, for all $a>0$.
  • Subexponential distribution
    • A CDF F(x) is subexponential if \lim_{x goes to \infty} (1-F^{n*}(x) )/(1-F(x)) = n, for some (all) n>=2, where $F^{n*}(x)$ is the n-fold convolution of F.
  • Long-range dependence (LRD):
    • A process is long-range dependent if it has a non-summable autocorrelation, i.e., $\sum_{k=1}^{\infty} r(k) = \infty$.
    • A process is short-range dependent (SRD) if its autocorrelation is summable, i.e., $\sum_{k=1}^{\infty} r(k) < \infty$.
    • A self similar process must be LRD.

• Optimal smoothing:
  • The playout buffer at the receiver is like an equalizer, which makes the output have a constant delay w.r.t. the input (after the video encoder and before the shaper).   This is in contrast to the channel equalizer in communication theory, which makes the whole channel have a constant frequency response.
• What's the intuition of Burke's theorem?  
  • From information theory perspective, we know exponential distribution is the distribution that maximizes the entropy under the constraint of fixed mean.   In Burke's theorem, the input has maximal entropy (with fixed mean) and the departure (system) also has  maximal entropy (with fixed mean); therefore, the output should also has maximal entropy (with fixed mean), that is, the output is exponentially distributed.

Key Techniques: