% title slide								1
\begin{slide}{}
\begin{center}
Closure Approximations for\\
Computer Networks
\end{center}
\vspace{.75 truein}
\begin{center}
Todd W.\ Mummert
\end{center}
\vspace{.75 truein}
\begin{center}
Texas A\&M University\\
July 24, 1992
\end{center}
\end{slide}

% Overview                                                              2
\begin{slide}{}
\begin{center}
Overview
\end{center}
\begin{itemize}
\item Motivation, solution methods
\item $M/M/1$ queue, equations for the mean and variance, closure
        approximations
\item Monte Carlo simulator for Jackson \\ 
        networks
\item Performance of closure approximations on Jackson networks
\item Reducing the computation time \\
         Associated errors
\item Conclusions
\end{itemize}
\end{slide}

% motivation,                                                           3
\begin{slide}{}
\begin{center} 
Applications of Queueing Models
\end{center}
\begin{itemize}
\item Assembly line management
\item Airport congestion control
\item Telephone switching centers
\item Data networks
\begin{enumerate}
\item Model each node as a queue
\item Determine average number of packets, variance, idle probability
\item Testing of routing algorithms, network protocols prior to
        actual physical implementation
\end{enumerate}
\end{itemize}
\end{slide}

% solution methods                                                      4
\begin{slide}{}
\begin{center}
Solution Methods
\end{center}
\begin{enumerate}
\item Analytic solution known for $M/M/1$ and $M/M/1/k$ queues.
\item Kolmogorov forward equations -- \\
        $(k+1)^n$ for $M/M/1/k$
\item Independent Kolmogorov equations -- \\ 
        $(k+1)n$ for $M/M/1/k$
\item Monte Carlo simulation -- statistical \\
        approach
\item Randomization, fluid-flow, diffusion.
\item Closure approximations
\end{enumerate}
\end{slide}

% Chapter 2 slide 1                                                     5
\begin{slide}{}
\begin{center}
Single $M/M/1$ Queue 
\end{center}
\begin{itemize}
\item Poisson arrival and service rates.
\item Exact transient solution is known.
\item Differential equations for the mean and variance
\end{itemize}
\jot=0.25truein
\begin{eqnarray}
{dM(t)\over dt} & = & \lambda(t)-\mu(t)\bigl(1-P_0(t)\bigr), \nonumber \\
{dV(t)\over dt} & = & \lambda(t)+\mu(t)-\mu(t)P_0(t)\bigl(2M(t)+1\bigr).
\nonumber
\end{eqnarray}
\end{slide}

% Chapter 2 slide 2                                                     6
\begin{slide}{}
\begin{itemize}
\item Rothkopf and Oren's Approximation
\begin{enumerate}
\item Negative binomial distribution 
\begin{displaymath}
P_n={r+n-1\choose n}p^r(1-p)^n,\quad n=0,1,2,\ldots
\end{displaymath}
\item Fully specified by its mean, $r(1-p)/p$, and variance $r(1-p)/p^2$
\item Estimate of the idle probability is given by
\begin{displaymath}
\hat P_0(t)=\left({M(t)\over V(t)}\right)^{M^2(t)/
                                          \left(V(t)-M(t)\right)}.
\end{displaymath}
\end{enumerate}
\item Chang and Wang's Approximation
\begin{enumerate}
\item Empirically derived
\item Expression for the idle probability is
\begin{displaymath}
\hat P_0(t)={1\over1+M(t)}e^{0.55
        \left(1-M(t)\left(1+M(t)\right)/V(t)\right).}
\end{displaymath}
\end{enumerate}
\end{itemize}
\end{slide}

% Chapter 2 slide 3                                                     7
\begin{slide}{}
\begin{itemize}
\item Clark's Closure Approximation
\begin{enumerate}
\item Polya-Eggenberger distribution 
\item Four equations are necessary
\end{enumerate}
\item Results for the Single $M/M/1$ Queue
\begin{enumerate}
\item Variety of initial conditions
\item Exact results using generalized Q-functions
\item Rothkopf/Oren $<$ Chang/Wang $<$ Clark
\end{enumerate}
\end{itemize}
\end{slide}

% Chapter 3 slide 1                                                     8
\begin{slide}{}
\begin{center}
Monte Carlo Simulator for Jackson Networks
\end{center}
\begin{itemize}
\item Definition of Jackson network
\begin{enumerate}
\item External arrivals follow a Poisson distribution ($\lambda$)
\item Service times exponentially distributed ($1/\mu$)
\item Routing paramaters ($\theta_{ij}$)
\item Total arrival rate ($\gamma_i$)
\end{enumerate}
\end{itemize}
\end{slide}

% Chapter 3 slide 2                                                     9
\begin{slide}{}
\begin{center}
Monte Carlo Simulator for Jackson Networks
\end{center}
\begin{itemize}
\item Requirements
\begin{enumerate}
\item Easy specification of network -- arrivals, services, initial
        number in each queue
\item Dynamically scalable
\item Configurable runtime parameters -- number of simulation runs,
        start/stop times, observation points
\end{enumerate}
\end{itemize}
\end{slide}

% Chapter 3 slide 3                                                     10
\begin{slide}{}
\begin{itemize}
\item Initialization
\item Establishment of an agenda
\item Event handler
\begin{enumerate}
\item Choose item off the agenda
\item Service completion -- decrement, route, conditional service
\item External arrival -- increment, conditional service, schedule next
\item Observation event -- update the accounting variables
\end{enumerate}
\end{itemize}
\end{slide}

% Chapter 3 slide 4                                                     11
\begin{slide}{}
\begin{itemize}
\item Handling non-stationary arrivals
\item Measuring the accuracy
\begin{enumerate}
\item Results are not exact
\item Generation of confidence intervals
\end{enumerate}
\item Performance
\begin{enumerate}
\item Considerably faster than SIMAN (12x)
\item More limited in scope
\end{enumerate}
\end{itemize}
\end{slide}

% Chapter 4 slide 1                                                     12
\begin{slide}{}
\begin{center}
Closure Approximations for Jackson Networks
\end{center}
\jot=0.25truein
\begin{eqnarray}
\lefteqn{{d \over dt} E\left[n_i(t)\right] =} \nonumber \\
 & &    \lambda_i(t) + \sum_{j\not=i}\theta_{ji}(t)\mu_j(t)\left(1-p_{j0}(t)
        \right) \nonumber \\
& & -\left(1-\theta_{ii}(t)\right)\mu_i(t)\left(1-p_{i0}(t)\right) \nonumber \\
\lefteqn{{d \over dt} {\rm Var}\left[n_i(t)\right] =} \nonumber \\
 & &    \lambda_i(t)+\sum_{j\not=i}\theta_{ji}(t)\mu_j(t)\left(1-p_{j0}(t)
        \right) \nonumber \\
& & +2\sum_{j\not=i}(\theta_{ji}(t)\mu_j(t)p_{j0}(t) \nonumber \\
& & \quad\cdot\left\{E\left[n_i(t)\right]-E\left[n_i(t)|n_j(t)=0\right]\right\}) \nonumber \\
& & +\left(1-\theta_{ii}(t)\right)\mu_i(t)\left(1-p_{i0}(t)\right)
        \nonumber \\
& & -2\mu_i(t)p_{i0}(t)E\left[n_i(t)\right]. \nonumber
\end{eqnarray}
\end{slide}

% Chapter 4 slide 2                                                     13
\begin{slide}{}
Assuming nodes are independent, $\theta_{ii} = 0$, and defining
\begin{displaymath}
\gamma_i(t) = \lambda_i(t)+\sum_j\theta_{ji}\mu_j\left(1-p_{j0}(t)\right),
\end{displaymath}
        the equations for the mean and variance become
\jot=0.25truein
\begin{eqnarray}
{d \over dt}E\left[n_i(t)\right] & = & \gamma_i(t)-\mu_i(t)
        \left(1-p_{i0}(t)\right) \nonumber \\
{d \over dt}{\rm Var}\left[n_i(t)\right] & = & \gamma_i(t)+\mu_i(t)\nonumber \\
    & &    -\mu_i(t)p_{i0}(t)\left(2E\left[n_i(t)\right]+1\right). \nonumber
\end{eqnarray}

Same as $M/M/1$
\end{slide}

% Chapter 4 slide 3                                                     14
\begin{slide}{}
Baker -- 2 node tandem results
\begin{enumerate}
\item Clark's and Chang/Wang's vs truncated Kolmogorov
\item Mean $e_{ave} < 15\%,$ variance $e_{ave} < 40\%$
\item Worst case -- low utilization, initially loaded 
\end{enumerate}
Andrewartha -- larger networks
\begin{enumerate}
\item 4 to 61 node networks
\item Approximations vs Monte Carlo results
\item Mean $e_{ave} < 16\%,$ variance $e_{ave} < 17\%$
\end{enumerate}
\end{slide}

% Chapter 5 slide 1                                                     15
\begin{slide}{}
\begin{center}
Computation Time Requirements
\end{center}
\begin{enumerate}
\item Chang/Wang's approximation performed poorly at low utilization;
        much better under loaded conditions
\item Clark better (25\%) at low utilization, but considerably slower
        when $\rho > 0.8$
\item Running time indeterminate {\it a priori}
\item 4th/5th order Runge-Kutta
\end{enumerate}
\end{slide}

% Chapter 5 slide 2                                                     16
\begin{slide}{}
\begin{center}
Simpler Runge-Kutta Algorithm
\end{center}
\begin{itemize}
\item 4th order 
\item Fixed step size over the interval of interest
\item Measure changes in accuracy
\item Computational savings
\end{itemize}
\end{slide}

% Chapter 5 slide 3                                                     17
\begin{slide}{}
\begin{itemize}
\item Stationary Results
\begin{enumerate}
\item 4 tandems and a 3 node fan network
\item $0.1 \leq \rho \leq 2.0$
\item Tandems \\
   $\quad$ mean $e_{ave} < 15\%$ \\
   $\quad$ variance $e_{ave} < 42\%$
\item Fan \\
   $\quad$ mean $e_{ave} < 14\%$ \\
   $\quad$ variance $e_{ave} < 300\%$
\end{enumerate}
\end{itemize}
\end{slide}

% Chapter 5 slide 4                                                     18
\begin{slide}{}
\begin{itemize}
\item Nonstationary Results
\begin{enumerate}
\item Arrival pattern
\begin{displaymath}
\rho = {\lambda \over \mu}\left(1+a\sin{2\pi t \over T} \right)
\end{displaymath}
\item Tandems \\
  $\quad$ mean $e_{ave} < 16\%$ \\
  $\quad$ variance $e_{ave} < 25\%$
\item Fan \\
  $\quad$ mean $e_{ave} < 17\%$ \\
  $\quad$ variance $e_{ave} < 315\%$
\end{enumerate}
\end{itemize}
\end{slide}

% Chapter 5 slide 5                                                     19
\begin{slide}{}
\begin{itemize}
\item Time Savings
\begin{enumerate}
\item Chang/Wang's approximation -- 100x improvement
\item Rothkopf/Oren's -- 30-50x improvement
\item Clark's approximation -- \\
        small $\rho$, 25x improvement\\
        large $\rho$, 5x improvement
\item Extremely predictable with regard to runtime.
\end{enumerate}
\end{itemize}
\end{slide}

% Chapter 6 slide 1                                                     20
\begin{slide}{}
\begin{itemize}
\item Conclusions
\begin{enumerate}
\item Useful for modeling Jackson networks.
\item Simplified approach to Runge-Kutta \\
        applicable
\end{enumerate}
\item Improvements
\begin{enumerate}
\item Automatically choose step size
\item Graphical interface -- Monte Carlo simulator and
        closure methods
\end{enumerate}
\end{itemize}
\end{slide}