% Author: Georgios Y. Lazarou
% Revision based on reviews
% Date: 09/19/2008
\documentclass[11pt, journal]{IEEEtran}
\usepackage{times}
\usepackage{mathptm}
\usepackage{epsfig}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{color, soul}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\DeclareSymbolFont{slanted}{OT1}{cmr}{m}{sl}
\DeclareSymbolFontAlphabet\mathsl{slanted}
\begin{document}
\title{Describing Network Traffic Using the Index of Variability}
\author{Georgios Y. Lazarou, Julie Baca, Victor S. Frost and Joseph B. Evans
\thanks{Part of this paper was presented at MSO'03~\cite{iasted},
\copyright IASTED 2003.}
\thanks{G.Y. Lazarou and J. Baca are with the Mississippi State University
glaz@ece.msstate.edu, baca@cavs.msstate.edu.}
\thanks{V.S. Frost and J.B. Evans are with the University of Kansas,
\{frost,evans\}@eecs.ku.edu.}}
\maketitle
%===============================================================================
\begin{abstract}
Commonly used measures of traffic burstiness do not capture the fluctuation of
traffic variability over the entire range of time scales.
In this paper, we present a measure of variability, called
the \textit{Index of Variability} ($H_v(\tau)$), that depicts the degree
of variability (burstiness) of a typical network traffic
process at each time scale and is analytically tractable for many traffic
models. As an illustration, we derive the closed-form expressions of
$H_v(\tau)$ for two traditional traffic models and generate a variety of
2D and 3D Index of Variability curves. These curves demonstrate that the
Index of Variability can help in determining the complexities
of the network traffic variability over the network performance
relevant time scales.
We then introduce a practical method for estimating the Index of Variability
curve from a given traffic trace. Using this method, we estimate the
Index of Variability curves for 12 long NLANR network traffic traces.
The results indicate that the variability of real network traffic
varies with time scales and that the Index of Variability has the
ability to discern qualitative differences between traffic traces obtained from
different networks. Thus, the Index of Variability offers the potential
to gain insights into the dynamics of network traffic that existing tools
do not offer.
\end{abstract}
%\begin{keywords}
%Internet QoS, Proportional Differentiated Services, Packet Scheduling
%\end{keywords}
%===============================================================================
\section{Introduction}
Many empirical studies have shown that Internet traffic exhibits
high variability\footnote{Fluctuation of traffic as a function of time.}
\cite{Duffy, Fowler, Leland, Paxson}, i.e.,
traffic is bursty (variable) over a wide range of time scales in sharp
contrast to the assumption that traffic burstiness exists only at short
time scales while traffic is smooth at large time scales \cite{Leland}.
High variability in traffic has been shown to have a significant impact
on network performance \cite{Leland, Erramilli}.
The results from \cite{Erramilli, Grossgluser, Krishnan2, Neidhardt}
show that knowledge of the traffic characteristics on multiple time scales helps
to improve the efficiency of traffic control mechanisms. More importantly, the
design and provision of quality-of-service-guarantees over the Internet requires
the understanding of traffic characteristics, such as variability.
Since the publication of \cite{Leland}, the popular belief has been that the
high variability in traffic is due to the \textit{long-range dependence}(LRD)
property of the traffic processes. In general, a (weakly) stationary
discrete-time real-valued stochastic process
$Y = \{ Y_n, n = 0, 1, 2, \dots \}$ with mean $\mu = E[ Y_{n} ]$
and variance $\sigma^2 = E[ {( Y_{n} - \mu )}^2] < \infty$ is long-range dependent
if $\sum_{k=1}^{\infty} r(k) = \infty$, where $r(k)$ measures the correlation between
samples of $Y$ separated by $k$ units of time. If $\sum_{k=1}^{\infty} r(k) < \infty$, then
$Y$ is said to exhibit \textit{short-range dependence} (SRD).
Many common traffic models with LRD are based on self-similar processes.
\hl{It is important to note however that not all common traffic models
with LRD are based on self-similar processes}.
In traffic modeling, the term self-similarity usually refers to
the \textit{asymptotically second order self-similar} or
\textit{mono-fractal} processes \cite{ParkBook}.
The definition of asymptotically second order self-similarity is as follow \cite{Leland}:
assume that $Y$ has an autocorrelation function of the form
$r(k) \sim k^{-\beta} L(k)$ as $k \to \infty$, where
$0 < \beta < 1$ and the function $L$ is slowly varying at infinity, i.e.,
$\lim_{k \to \infty} \frac{L(kx)}{L(k)} = 1$ $\forall x > 0$.
For each $m = 1, 2, 3, \dots$, let $Y^{(m)} = \{Y^{(m)}_{n}, n = 1, 2, 3,\dots\}$ denote a
new aggregated time series obtained by averaging the original series $Y$ over non-overlapping
blocks of size $m$, replacing each block by its sample mean. That is, for each
$m = 1, 2, 3, \dots$, $Y^{(m)}$ is given by
\begin{equation}
Y^{(m)}_{n} = \frac{Y_{nm-m+1} + \cdots + Y_{nm}}{m}
\qquad n \ge 1.
\label{apym}
\end{equation}
The new aggregated discrete-time stochastic process $Y^{(m)}$ is also (weakly) stationary
with an autocorrelation function $r^{(m)}(k)$; then, $Y$ is called
asymptotically second order self-similar with self-similar parameter $H = 1 - \frac{\beta}{2}$
if for all $k$ large enough, $r^{(m)}(k) \to r(k)$ as $m \to \infty$,
that is, $Y$ is asymptotically second-order self-similar if the
corresponding aggregated processes $Y^{(m)}$ become indistinguishable from $Y$ at least
with respect to their autocorrelation functions. By definition,
asymptotically second order self-similarity implies LRD \cite{ParkBook}.
The parameter $H$ is called the \textit{Hurst parameter}. For general self-similar
processes, it measures the degree of ``self-similarity''. For random processes suitable for
modeling network traffic, the Hurst parameter is basically a measure of the speed
of decay of the tail of the autocorrelation function.
If $0.5 < H < 1$, then the process is LRD, and if $0 < H < 0.5$,
then it is SRD. If $H=0.5$ then the process can be either SRD or LRD. However,
most processes relevant to traffic modeling with $H=0.5$ are SRD, eg., Markov
processes. Hence, $H$ is widely used to capture the intensity of long-range
dependence of a traffic process: the closer $H$ is to 1 the more long-range
dependent the traffic is, and vice versa \cite{ParkBook}.
Several methods exist for estimating $H$ from a traffic trace. One of the
most widely used is the \textit{Aggregated Variance} method:
for successive values of $m$ that are equidistant on a log scale, the sample
variance of $Y^{(m)}$ is plotted versus $m$ on a log-log plot \cite{beran}\cite{estimators}.
By fitting a least-square line to the points of the plot and then
calculating its slope, an estimate of the Hurst parameter is obtained
as $\hat{H} = 1 - \frac{\left| slope \right| }{2}$.
Another very popular method is based on wavelets \cite{DarryVeitch}. Given a traffic
trace $Y_n$, the Hurst parameter can be estimated as follows:
for each scale $j$, the wavelet energy $\mu_j={{1} \over {N_j}}{\sum_{k=1}^{n_j}}d^2(j,k)$
is plotted versus $j$ on a semi-log plot (i.e., $\log_2(\mu_j)$ vs. $j$).
By fitting a least-square line to the points of the curve region that
\textit{looks} linear and then computing its slope $\alpha$, $H$ is estimated as
$\hat{H} = \frac{\alpha+1}{2}$.
%-------------------------------------------------------------------------------
\subsection{Need for a New Measure of Variability}
Commonly used measures of traffic burstiness, such as the
peak-to-mean ratio, the coefficient of variation of interarrival times, the
indices of dispersion for intervals and counts, and the Hurst parameter,
do not capture the fluctuation of variability over different time scales.
It is claimed in \cite{Leland} that the Hurst parameter is a good measure of
variability, and the higher the value of $H$, the burstier the traffic.
The popular belief from early studies
\cite{Erramilli, Baiocchi, Norros, leland, duffield, Duffield}
on the impact of LRD on network performance is that high values of the Hurst
parameter are associated with poor queueing performance. However, later studies
\cite{Krishnan2, Krishnan1} show examples in which larger values of $H$
are associated with better queueing performance compared to smaller values
of $H$. In addition, the results in \cite{Neidhardt} indicate that
the queueing performance depends mostly on the variability over certain
time scales rather than on the value of $H$.
Moreover, it is known \cite{Grossgluser} that different long-range dependent
processes with the same value of the Hurst parameter can generate vastly
different queueing behavior. Clearly, the single value Hurst parameter does not
capture the fluctuation of the degree of traffic burstiness across time scales,
regardless of whether the traffic process exhibits LRD or SRD.
From the definition presented in the previous section, the Hurst parameter
is defined asymptotically (i.e., for large time scales) and hence conveys
nothing about the variability of measured traffic over small or medium time
scales; unless the traffic is exactly self-similar with known variances.
Therefore, the Hurst parameter is an incomplete descriptor of traffic variability.
For many network traffic processes, the wavelet energy-scale or variance-time
plots usually do not tend to straight lines, i.e., see Fig. \ref{waveletplot}.
\begin{figure}
\centering
\includegraphics[width=2.8in]{figures/20010301-0310-0jy.eps}
\caption{$\log_2(\mu_j)$ versus scale $j$ for the Auckland-IV traffic trace 20010301-310-0
(For information about the trace, see Section \ref{EIVEMTT}).}
\label{waveletplot}
\end{figure}
Usually many of these processes have piecewise fractal behavior with varying
Hurst parameter over some small ranges of time scales \cite{QiongLi}.
\hl{When a traffic process is described by a collection of scaling exponents $H(\tau)$
is usually referred to as \textit{multi-scaling}} \cite{idc-veitch}.
\hl{If the moments of these processes behave as power laws of the scales, then
are usually referred to as multi-fractal with \textit{multi-fractal scaling}}
\cite{Ribeiro, abry}. \hl{In the cases that the moments do not behave as
power laws of the scales, the \textit{Infinitely Divisible Cascades}
models can be used to characterize network traffic processes.}
Queueing performance greatly depends on traffic irregularities at small time
scales which are typically attributed to the complex dynamics of data networks
\cite{Grossgluser, Kant, Melo}. Multifractal analysis based on the Legendre spectrum is
often used to study the multiscaling behavior of traffic at small time scales
\cite{QiongLi, Riedi, Vehel, Gilbert}.
The process of estimating the Legendre spectrum involves higher order sample moments
and negative values of moments. It is known \cite{MSTaqqu} that higher order sample moments
are not well-behaved and negative values of moments tend to be erratic. In addition,
the Legendre spectrum is difficult to interpret \cite{Horvath}.
The infinitely divisible cascade analysis represents an improvement over
the multifractal analysis \cite{idc-veitch}. It relaxes the questionable
assumption that moments behave as power-laws of scales \cite{abry}.
Hence, there is a need for an intuitively appealing, conceptually simple, and
mathematically rigorous measure which can capture the various scaling phenomena
that are observed in data networks on both small and large
scales \cite{Willinger-Paxson}. In this paper, we present an alternative
measure of variability, called the \textit{Index of Variability} ($H_v(\tau)$),
that captures the degree of variability of a typical network traffic process
at each \hl{\textit{critical time scale}} \cite{Grossgluser, Neidhardt, Kant}
and is analytically tractable for many traffic models.
The remainder of this paper is organized as follows: Section II presents the
definition of the \textit{Index of Variability}.
Section III presents the derivation of the closed-form expressions
of $H_v(\tau)$ for two traditional traffic models.
A variety of 2D and 3D Index of Variability curves are also presented for
illustration.
Section IV presents a practical method for estimating the Index of
Variability curve from a given traffic trace and
experimental results. The paper concludes in Section V.
%===============================================================================
\section{Index of Variability for Packet Traffic Sequences}
\label{variability}
Let $N(t)$ denote the number of events (packet arrivals) of a stationary point
process in the interval $(0,t]$. For each fixed time interval $\tau > 0$, an
event count sequence $Y = \{ Y_n(\tau), \tau > 0, n = 1,2,\dots \}$ can be
constructed from each point process, where
\begin{equation}
Y_n(\tau) = N[n\tau] - N[(n-1)\tau]
\label{Yn}
\end{equation}
denotes the number of events that have occurred during the $n^{th}$ time
interval of duration $\tau$. Clearly, $Y$ is also (weakly) stationary for all
$\tau > 0$. In this study, $Y$ represents a network traffic trace where
$Y_n(\tau)$ denotes the number of packets observed from an arbitrary point in
the network during the $n^{th}$ time interval of duration $\tau$. We refer to
$\tau$ as the \textit{time scale} of the traffic trace, and it represents the
length (i.e., 10ms, 1s, 10s, e.t.c.) of one sample of $Y$.
The expected number of events that have occurred during the interval $(0,t]$ is
always: $E[N(t)] = \frac{t}{E[X]} = \lambda t$ where $E[X]$ is the expected
interarrival time and $\lambda$ is the mean event (packet) arrival rate. The
index of dispersion for counts (IDC) is defined as:
%\begin{equation}
$IDC(t) \equiv \frac{Var[N(t)]}{E[N(t)]} = \frac{Var[N(t)]}{\lambda t}$.
%\label{idc}
%\end{equation}
The IDC was defined such that it provides some comparison with the
Poisson process, for which $IDC(t) = 1$ $\forall t$. Note that since the point
process is stationary, IDC has the same value over any interval of length
$t$; thus, $t$ can be viewed as the time scale $\tau$ of the traffic process
$Y$ defined in (\ref{Yn}). Henceforth $t$ will be used to denote
generality and $\tau$ to denote time scales, i.e., the time length of
each sample of the packet-count sequence $Y$.
An important feature of IDC is that it is mathematically equivalent to the
Aggregated Variance method for estimating the Hurst parameter $H$ of a
self-similar process. For a self-similar process, plotting $\log(IDC(m\tau))$
against $\log(m)$ results in an asymptotic straight line with slope $2H - 1$.
When $Y$ is a long-range dependent process, the slowly decaying variance
property of LRD processes \cite{Leland} with parameter $0 < \beta < 1$ is
equivalent to an IDC curve\footnote{In log-log coordinates.} with an
asymptotic straight line with slope $1-\beta$, implying $0 < slope < 1$. When
the IDC curve converges to an asymptotic straight line with $slope = 0$ for
some $\tau < \infty$, then this is suggestive of $Y$ been a short-range
dependent process. Based on the above property of IDC, we define the
following new measure of variability:
\begin{definition} \label{IOV}
For a general stationary traffic process $Y$ as defined by (\ref{Yn})
whose $IDC(\tau)$ is continuous and differentiable over $(0, \infty)$,
we refer to:
\begin{equation}
H_v(\tau) \equiv \frac{\frac{d(\log(IDC(\tau)))}{d(\log(\tau))} + 1}{2}
\label{HvD}
\end{equation}
as the \textit{Index of Variability} of $Y$ for the time scale $\tau$, where
$\frac{d(\log(IDC(\tau)))}{d(\log(\tau))}$ is the local slope of the IDC
curve at each $\tau$ when plotted in log-log coordinates.
\end{definition}
Note that the index of variability is so defined in order for an
asymptotically or second-order self-similar process
$H_v(\tau) \to H \in (0.5, 1)$ as $\tau \to \infty$. If the process is exactly
self-similar, then $H_v(\tau) = H \in (0.5, 1)$ for all $\tau > 0$, that is, if
$\log(IDC(\tau))$ is linear with respect to $\log(\tau))$, then $H_v(\tau)$
reduces to $H$. The Index of Variability can be viewed as the Hurst
parameter defined at each time scale.
In general\footnote{The generality here is confined for those processes that
are suitable in modeling network packet traffic.}, the process $Y$ exhibits
significant variability for those time scales $\tau$ such that
$0.5 < H_v(\tau) < 1$. When $\frac{d(\log(IDC(\tau)))}{d(\log(\tau))} \to 1$,
then $H_v(\tau) \to 1$, implying very high variability. A plot of $H_v(\tau)$
versus $\tau$ would depict the behavior of the traffic process $Y$ in terms
of variability (burstiness) at each time scale
$\tau$ ($= 10ms,\ 100ms,\ 1s, \ \dots$).
Expanding the local slope of the IDC curve at each time scale, we obtain:
\begin{eqnarray}
\frac{d(\log(IDC(\tau)))}{d(\log(\tau))} & = &
\frac{\tau}{IDC(\tau)}\frac{d(IDC(\tau))}{d\tau}\nonumber\\
& = & \frac{\tau}{Var[N(\tau)]} \frac{d(Var[N(\tau)])}{d\tau} - 1.
\label{dlog}
\end{eqnarray}
Using the above in (\ref{HvD}), we obtain a more convenient form of the
Index of Variability:
\begin{eqnarray}
H_v(\tau) & = & 0.5\tau\left(\frac{\frac{dVar[N(\tau)]}{d\tau}}{Var[N(\tau)]}\right)\label{varhv}\\
& = & \frac{1}{2}\left\{1 + \tau \left(\frac{
\frac{d(IDC(\tau))}{d\tau}}{IDC(\tau)}\right)\right\}
\label{varidchv}
\end{eqnarray}
Suppose now $Y$ is an aggregate sequence of packet counts resulting from the
superposition of $M$ independent packet-traffic sources, not necessarily
identical. Then $N(t) = N_1(t) + \cdots + N_M(t)$, where $N_i(t)$
denotes the number of packet arrivals in the interval $(0,t]$ from
the $i^{th}$ traffic source. Assuming again stationarity, then:
\begin{equation}
IDC(t) = \frac{\sum_{i=1}^{M} Var[N_i(t)]}{\sum_{i=1}^{M} \lambda_i t}
= \sum_{i=1}^{M} \left(\frac{IDC_{i}(t)}{\Lambda_{i}}\right)
\label{superposeIDC}
\end{equation}
where $\lambda_i$ is the mean packet arrival rate from the $i^{th}$ source,
and $\Lambda_{i} = \frac{\sum_{j=1}^{M} \lambda_j}{\lambda_i}.$
In addition,
$\frac{\log(IDC(t))}{\log(t)} = \frac{\log(\sum_{i=1}^{M} Var[N_i(t)])}{\log(t)}
- \frac{\log(\sum_{i=1}^{M} \lambda_i t)}{\log(t)},$
and upon taking the derivative in respect to $\log(t)$
the Index of Variability for the aggregate traffic stream is computed to be:
\begin{eqnarray}
H_v(\tau) & = & 0.5\tau\left(
\frac{\sum_{i=1}^{M} \frac{dVar[N_i(\tau)]}{d\tau}}
{\sum_{i=1}^{M} Var[N_i(\tau)]}
\right)\nonumber\\
& = & \frac{1}{2}\left\{1 + \tau \left(\frac{\sum_{i=1}^{M}
\frac{d(IDC_{i}(\tau))}{d\tau}\left(
\frac{1}{\Lambda_{i}}\right)}{\sum_{i=1}^{M}
\left(\frac{IDC_{i}(\tau)}{\Lambda_{i}}\right)}\right)\right\}.
\label{AHvD}
\end{eqnarray}
As can be observed from (\ref{AHvD}), the variances or the indices of
dispersion for counts of the $M$ independent
point-processes completely characterize the variability function of the
aggregate packet-count sequence $Y$.
If
\makebox{$\lim_{\tau \to \infty} IDC(\tau) = \lim_{\tau \to \infty}
\left( \sum_{i=1}^{M}\left(\frac{IDC_{i}(\tau)}{\Lambda_{i}}\right)\right)
= c < \infty$}, then
\makebox{$\lim_{\tau \to \infty} H_v(\tau) = 0.5$}.
In the case that all $M$ underlying point processes of making up $Y$ are also
identical, then (\ref{AHvD}) reduces to (\ref{varidchv}).
If all $M$ underlying point processes are Poisson, then
$\frac{d(IDC_{i}(\tau))}{d\tau} = 0$ for all $\tau$ and $i$ and hence
$H_v(\tau) = 0.5$ for all $\tau$.
\hl{An interesting point is that the Index of Variability estimates the
difference of the second and the first Infinitely Divisible Cascade
scaling exponent}.
%===============================================================================
\section{Analysis of Traffic Models in Terms of the Index of Variability}
In this section, we derive the Index of Variability functions for two
traditional traffic models: two-state Markov Modulated Poisson
Process (MMPP) and renewal process with hyperexponential interarrival time
distributions of order two (RPH2). Two-state MMPP models have become popular for
modeling the superposition of packet voice streams \cite{Heffes}.
The work in \cite{Feldman} shows that long-tail distributions can be
approximated by hyperexponentional distributions. Thus, renewal processes with
hyperexponential interarrival time distributions can be used for capturing the
high variability of traffic over any range of (short or long) \hl{critical time scales}.
A major advantage of these models is their relative ease of analytically
obtaining queueing performance predictions.
\subsection{Two-state MMPP}
Consider that the underlying point process of $Y$ is an MMPP with
two-state Markov chain where the mean sojourn times in state 1 and 2
are $\alpha^{-1}$ and $\beta^{-1}$, respectively. When the chain is in
state $i$ ($ i = 1,2$) the point process is Poisson with rate $\lambda_i$.
Letting
$\eta = \alpha + \beta$ and $\upsilon = \lambda_{1}\beta + \lambda_{2}\alpha$,
we have from \cite{Heffes} that $E[N(t)] = \frac{\upsilon t}{\eta}$
and
\makebox{$IDC(t) = 1 + \eta A - A\left(\frac{1-e^{-\eta t}}{t}\right)$},
where
\makebox{$A = \frac{2\alpha\beta(\lambda_1 - \lambda_2)^2}{\eta^{3}\upsilon}$}.
Clearly the $\lim_{t \to \infty} IDC(t) = 1 + \eta A$.
Upon taking the derivative of IDC(t), the Index of Variability
of $Y$ can be obtained:
\[ H_v(\tau) = 0.5\left\{ 1 + \frac{A\left[ 1 - \left(1 + \eta\tau\right)
e^{-\eta\tau}\right]}{(1+\eta A)\tau - A \left( 1 - e^{-\eta\tau}\right)}
\right\}. \]
\subsubsection{Numerical Example}
%\textbf{Numerical Example:}
Assume $\alpha^{-1} = \beta^{-1} = 100$ seconds, $\lambda_1 = 4$
packets/second and $\lambda_2$ to vary from 1 to 1000 packets/second.
Fig. \ref{MMPPHv} shows the resulting index of variability curves as
a function of time scale ($\tau$) and state rates ($\lambda_i$).
Notice that when $\lambda_2 = \lambda_1$, we have a pure Poisson
process, and therefore zero variability; however, as the difference between
$\lambda_1$ and $\lambda_2$ increases, so does the Index of Variability.
From Fig. \ref{MMPPHv} it can be observed that the Index of
Variability increases with $\lambda_2$ up to its maximum value, and any further
increase in $\lambda_2$ does not have any affect on variability. It can be also
observed that the Index of Variability increases with $\tau$ up to its
maximum value and then decays exponentially.
In addition, notice for values of $\lambda_2$ further from $\lambda_1$,
the packet-count process $Y$ has
substantial variability over a wide range of time scales that spans
about 200 seconds.
\begin{figure}%[htb]
\centering
\includegraphics[width=2.5in]{figures/mmppHv1.eps}
\includegraphics[width=2.5in]{figures/mmppHv3.eps}
\caption{Index of Variability for The Two-State MMPP:
$\alpha^{-1} = \beta^{-1} = 100$ Seconds, $\lambda_1 = 4$ Packets/Second.}
\label{MMPPHv}
\end{figure}
%-------------------------------------------------------------------------------
\subsection{RPH2} \label{RPHITDEX}
\label{hyperexponetial}
Assume here that the underlying point process of $Y$ is a stationary
renewal process with interarrival times hyperexponentially distributed.
We call this model as the \textit{hyperexponential model}.
A hyperexponential distribution of order $K$, ($= 1, 2, 3, \dots$), is the
weighted sum of $K$ exponential distributions:
\begin{equation}
F_K(x) = Pr[X \le x] = \sum_{i=1}^{K} w_i (1 - e^{-\alpha_i x})
\label{hypexpdistr}
\end{equation}
where $w_i > 0$ are the weights satisfying $\sum_{i=1}^{K} w_i = 1$,
and $\alpha_i > 0$ are the rates of the exponential distributions
\cite{Gusella}. It is shown in \cite{Greiner} that if $w_i = w^i$ and
$\alpha_i = \frac{\mu}{\eta^i}$ for $0 < w < 1$, $\eta > 1$, and
$\mu > 0$, then the tail of the hyperexponential distribution gets
longer and longer with $K$. The major advantages of the hyperexponential
distributions over heavy-tailed distributions, such as Pareto are two-fold:
their Laplace transform exists, therefore they can be utilized in analytic
models, and they have finite variance for all $K$.
In this paper, we only consider the case of $K=2$ (i.e., the \textbf{RPH2}
process). Letting $a = \alpha_1$ and $b = \alpha_2$, we get the pdf
of the interarrival times to be:
\begin{equation}
f_2(x) = w_1 a e^{-a x} + w_2 b e^{-b x}.
\label{pdfh2}
\end{equation}
The mean packet arrival rate is $\lambda = \frac{a b}{a w_2 + b w_1}$,
and the squared coefficient of variation of the interarrival times is
${\cal C}^{2}(X) = 2\left[\frac{a^{2}w_2 + b^{2}w_1}{(a w_2 + b w_1)^2}\right]
- 1$. Note that if $a = b$, then $\lambda = a = b$ and
${\cal C}^{2}(X) = 1$ for all the values of $w_1$ and $w_2$, and hence it is
a Poisson process. In addition, $\lim_{w_2 \to 0} {\cal C}^{2}(X) = 1$
and $\lim_{b \to 0} {\cal C}^{2}(X) = \frac{2}{w_2} - 1$.
\begin{figure}%[htb] %[p]
\centering
%\includegraphics[width=2.8in]{/home/glaz/work/research/ku/thesis/dissertation/papers/ieeetransnet/figures/C2Xa100b10mpps.eps}
\includegraphics[width=2.8in]{figures/C2Xa100b1upps.eps}
\caption{Squared Coefficient of Variation of the Interarrival Time vs. $w_2$
for the Case of Hyperexponential Distribution of Order Two: $a = 100$,
and $b = 0.0001$.}
\label{C2Xh2plots}
\end{figure}
As shown in Fig. \ref{C2Xh2plots}, for constant values of
$a$ and $b$, ${\cal C}^{2}(X)$ increases exponentially up to its maximum
value and then decreases to one very abruptly. This indicates that
the hyperexponential distribution can be used to model the interarrival times
distribution of highly bursty traffic.
From \cite{Renewal} we have that
\begin{equation}
Var[N(t)] = 2\lambda \int_{0}^{t} \Phi(u)\,du + \lambda t - \lambda^2 t^2
\label{vnth2}
\end{equation}
where
\begin{equation}
\Phi(t) = {\cal L}^{-1}\left[{\mit\Phi}^{*}(s)\right] = {\cal L}^{-1}\left[
\frac{{\mathsl{f}}_{2}^{*}(s)}{s\left\{1 - {\mathsl{f}}_{2}^{*}(s)\right\}}
\right].
\label{orfh2}
\end{equation}
Note that the symbol ${\cal L}^{-1}$ denotes the inverse Laplace transform
and
\[
{\mathsl{f}}_{2}^{*}(s) = {\cal L}\left[f_2(x)\right] =
w_1 \left(\frac{a}{s + a}\right) + w_2\left(\frac{b}{s + b}\right)
\]
is the Laplace transform of $f_2(x)$. Noting that:
\begin{eqnarray}
\varphi(t) & = &{\cal L}^{-1}\left[
\frac{{\mathsl{f}}_{2}^{*}(s)}{1 - {\mathsl{f}}_{2}^{*}(s)}\right]\nonumber\\
& = & \lambda - \frac{[(aw_1 + bw_2)^2 - (a^2w_1 + b^2w_2)]
e^{-[aw_2 + bw_1]t}}{aw_2 + bw_1}\nonumber\\
\end{eqnarray}
$\Phi(t)$ is obtained:
\begin{eqnarray}
\Phi(t) & = & \int_{0}^{t}\varphi(u)\,du\nonumber\\
& = & \lambda t - \frac{[(aw_1 + bw_2)^2 - (a^2w_1 + b^2w_2)]}{(aw_2 + bw_1)^2}\nonumber\\
&\ & \left(1 - e^{-[aw_2 + bw_1]t}\right).
\label{Phith2}
\end{eqnarray}
Performing the integration in (\ref{vnth2}) results:
\begin{eqnarray}
Var[N(t)] & = & \frac{2\lambda[(aw_1 + bw_2)^2 - (a^2w_1 + b^2w_2)]}
{(aw_2 + bw_1)^3}\nonumber\\
& & \left(1 - e^{-[aw_2 + bw_1]t}\right) + \lambda {\cal C}^{2}(X)t,
\label{VNth2}
\end{eqnarray}
and hence
\begin{eqnarray}
\frac{d}{dt}\left(Var[N(t)]\right) & = &
\frac{2\lambda[(aw_1 + bw_2)^2 - (a^2w_1 + b^2w_2)]}
{(aw_2 + bw_1)^2}\nonumber\\
&\ & e^{-[aw_2 + bw_1]t} + \lambda {\cal C}^{2}(X),
\label{dVNth2}
\end{eqnarray}
and
\begin{eqnarray}
IDC(t) & = & \frac{2[(aw_1 + bw_2)^2 - (a^2w_1 + b^2w_2)]}
{(aw_2 + bw_1)^3}\nonumber\\
& & \left(\frac{1 - e^{-[aw_2 + bw_1]t}}{t}\right) + {\cal C}^{2}(X).
\label{IDCh2}
\end{eqnarray}
Observe that $\lim_{t \to \infty} IDC(t) = {\cal C}^{2}(X)$,
and if $a = b$ then $[(aw_1 + bw_2)^2 - (a^2w_1 + b^2w_2)] = 0$ and
${\cal C}^{2}(X) = 1$ making $Var[N(t)] = \lambda t$ and $IDC(t) = 1$,
i.e., we get a Poisson process.
(\ref{VNth2}) or (\ref{IDCh2}) can then be used in (\ref{varhv}) or
(\ref{varidchv}) to obtain the Index of Variability. It is obvious to see that
$\lim_{\tau \to \infty} H_v(\tau) = 0.5$.
Deriving the symbolic expression of $Var[N(t)]$ for $K > 2$ is a
difficult problem, mainly due to the difficulty in deriving $\phi (t)$,
i.e., performing the following inverse Laplace transform:
\begin{displaymath}
{\cal L}^{-1}\left[
\frac{{\mathsl{f}}_{K}^{*}(s)}{1 - {\mathsl{f}}_{K}^{*}(s)}\right]
\end{displaymath}
where ${\mathsl{f}}_{K}^{*}(s)$ is the Laplace transform of the the $K$-order
hyperexponential pdf of the interarrival times. However, it becomes trivial
when the model parameters (e.g., $w_i$ and $\alpha_i$) are set to
numerical values.
\subsubsection{Numerical Example}
%\textbf{Numerical Example:}
\begin{table}%[htb]
\footnotesize
\begin{center}
\caption{Values of Mean Packet Rate ($\lambda$) and Squared Coefficient
of Variation of Interarrival Times (${\cal C}^{2}(X)$) for the Numerical
Example of the Case of Hyperexponential Distribution of Order Two:
$a = 100$.}
\begin{tabular}{|l | c c | c r |} \hline
& $\lambda$ & (packets/sec) & ${\cal C}^{2}(X)$ & \\
$w_2$ & $b = 0.01$ & $b = 0.0001$ & $b = 0.01$ & $b = 0.0001$\\ \hline \hline
$10^{-3}$ & 9.1000 & 0.0999 & 1.6522x$10^{3}$ & 1.9950x$10^{3}$\\ \hline
$10^{-4}$ & 50.0000 & 0.9901 & 5.0000x$10^{3}$ & 1.9605x$10^{4}$\\ \hline
$10^{-5}$ & 90.9000 & 9.0909 & 1.6536x$10^{3}$ & 1.6529x$10^{5}$\\ \hline
$10^{-6}$ & 99.0000 & 50.0000 & 197.0202 & 5.0000x$10^{5}$\\ \hline
$10^{-7}$ & 99.9000 & 90.9091 & 20.9561 & 1.6529x$10^{5}$\\ \hline
$10^{-8}$ & 99.9900 & 99.0099 & 2.9992 & 1.9607x$10^{4}$\\ \hline
$10^{-9}$ & 99.9990 & 99.9001 & 1.2000 & 1.9970x$10^{3}$\\ \hline
$10^{-10}$ & 99.9999 & 99.9900 & 1.0200 & 200.9596 \\ \hline
$10^{-11}$ & 100.0000& 99.9990 & 1.0020 & 20.9996 \\ \hline
$10^{-12}$ & 100.0000& 99.9999 & 1.0002 & 2.9999 \\ \hline
$10^{-13}$ & 100.0000& 100.0000& 1.0000 & 1.2001 \\ \hline
\end{tabular}
\label{NElC2Xh2}
\end{center}
\normalsize
\end{table}
Let $a = 100$. Table \ref{NElC2Xh2} lists the values of the mean packet
rate ($\lambda$) and the squared coefficient of variation of
the interarrival times (${\cal C}^{2}(X)$) for $b = 0.01$ and $b = 0.0001$ for
different values of $w_2$. Note that $w_1 + w_2 = 1$.
Fig. \ref{Hvh2plots} shows the resulted Index of Variability curves
for different values of $w_2$, and thus for different values of $\lambda$,
and for $b = 0.0001$. Clearly, the value of $w_2$ has a direct inpact on the
variability of the resulting packet traffic. By observation, these curves
can be divided into two groups, the ones shown at the left of Fig.
\ref{Hvh2plots} (group A) and the ones shown at the right (group B).
\begin{figure}%[htb]
\centering
%\includegraphics[width=4in]{../../chap3/figures/Hv100b10mppsSt39s.eps}
\includegraphics[width=3.4in]{figures/Hva100b1uw23to6.eps}
\includegraphics[width=3.4in]{figures/Hva100b1uw26to12.eps}
\caption{Index of Variability vs. Time Scale
for the Case of Hyperexponential Distribution of Order Two, $a = 100$,
$b = 0.0001$: \hl{\textbf{(top)}} $w_2\ =\ $ (i) $10^{-3}$ (ii) $10^{-4}$ (iii) $10^{-5}$
(iv) $10^{-6}$ \hl{\textbf{(bottom)}} $w_2\ =\ $ (i) $10^{-6}$ (ii) $10^{-7}$ (iii) $10^{-8}$
(iv) $10^{-9}$ (v) $10^{-10}$ (vi) $10^{-11}$ (vii) $10^{-12}$.}
\label{Hvh2plots}
\end{figure}
In group A, the curves have approximately the same \hl{increasing} behaviors but
their \hl{decreasing} behaviors, although having similar shapes, occur on
different time scales. As $\lambda \to \frac{a}{2}$ (i.e., $w_2 \to 10^{-6}$),
the range of time scales of high variability behavior and the maximum value
of variability increases. On the other hand, in group B the curves have similar
\hl{decreasing} behaviors but different \hl{increasing} behaviors. In this case,
the maximum value of variability as well as the range of time scales of
substantial variability become smaller as $\lambda \to a$.
If we let
\small
\begin{displaymath}
\tau_{\rm on} = \inf\{range\ of\ time\ scales\ of\ substantial\ variability\}
\end{displaymath}
\normalsize
and
\small
\begin{displaymath}
\tau_{\rm off} = \sup\{range\ of\ time\ scales\ of\ substantial\ variability\},
\end{displaymath}
\normalsize
then we can say that the process behaves like Poisson for all
$\tau\notin [\tau_{\rm on}, \tau_{\rm off}]$.
As it can be observed in Fig. \ref{Hvh2plots}, the $w_2 = 10^{-6}$-curve
(left plot curve (iv) or right plot curve (i))
is the boundary curve between the two groups. At this value of $w_2$,
$\lambda = \frac{a}{2}$, the process attains the widest range of time scales
(that spans $7$ order of magnitude) of high variability, and in this range the
index of variability reaches its maximum value (max$H_v = 0.9988$).
Interestingly, the maximum value of ${\cal C}^{2}(X)$ occurs also at
$\lambda = \frac{a}{2}$. Note that this widest range of time scales of
high variability most likely covers all time scales that impact network
performance evaluation \cite{Grossgluser}.
Assuming an RPH2/M/1 queueing system\footnote{RPH2/M/1 can be considered
as special case of G/M/1 queue with RPH2 as the arrival process. See
\cite{Kleinrock} for details about the G/M/1 queue.}, we get the mean
number of packets in the queue to be $E[N] = \rho / (1 - \sigma)$ where
$\rho = \lambda / \mu$ is the load, $\mu$ the mean packet service rate, and
\begin{displaymath}
\sigma = \frac{(\mu+a+b-\sqrt{\mu^2 -2(a+b)\mu+\frac{4ab}{\rho}+(a-b)^2}}{2\mu}.
\end{displaymath}
\begin{figure}%[htb]
\centering
\includegraphics[width=3.4in]{figures/normalizedENa100b0001.eps}
\caption{Normalized mean number of packets (E[N]) versus $w_2$ for various
values of system load ($\rho$) assuming an $RPH2/M/1$ queueing system. The
normalization is in terms of the $M/M/1$ queueing system.}
\label{gm1EN}
\end{figure}
Fig. \ref{gm1EN} depicts the normalized\footnote{
Normalized $E[N]$ = $E[N]_{\rm RPH2/M/1}$ / $E[N]_{\rm M/M/1}$.}
$E[N]$ as a function of $w_2$ and $\rho$ (load).
By studing these queueing performance curves, several interesting observations
can be made: (1) even at very low loads, the mean number of packets in the
queue (or the mean queueing delay) can get very large (see the curve for
$\rho = 0.3$); (2) as the load increases, the normalized $E[N]$
peak increases (as expected); (3) as $\rho \to 1$, $w_2^{\rm peak} \to 10^{-6}$,
(i.e., $\lambda = \frac{a}{2}$) where $w_2^{\rm peak}$ is the value of
$w_2$ where $E[N]$ attains it maximum value; (4) as $w_2$ decreases,
E[N] increases exponentially reaching its maximum value and then \hl{decreases}
sharply to 1. Clearly, for those values of $w_2$ such that the
normalized $E[N] \approx 1$, the queueing system behaves like M/M/1.
In addition, by careful examination of Figures \ref{Hvh2plots} and \ref{gm1EN},
it can be determined that the performance of the RPH2/M/1 queue is
correlated to the behavior of the Index of Variability curve at early time
scales. For example, consider first the
$w_2 = 10^{-5}$-Index-of-Variability-curve. Although at $\tau \approx 10^4$
the value of $H_v$ has \hl{decreased} close to 0.5, $E[N]$ is relatively high, as
shown in Fig. \ref{gm1EN}, even at a very low load. Next consider the
$w_2 = 10^{-8}$-Index-of-Variability-curve. The Index of Variability curve
starts from close to 0.5 at low values of $\tau$ and reaches its maximum
value around 100 seconds. Clearly, for $\tau < 1$ seconds, $H_v$ is
relatively low. Although $H_v$ attains high variability at relatively
high time scales for a wide range of time scales, the normalized $E[N]$
has values close to 1 for any load. It appears that high variability of the
arrival process beyond a certain time scale does not affect the performance
of the RPH2/M/1 queueing system, in agreement with \cite{Grossgluser}.
Figure \ref{Hvh3Dplots} depicts 3D Index of Variability curves generated using
the \textit{hyperexponential} model with $K=2$. Clearly, both Figures
\ref{Hvh2plots} and \ref{Hvh3Dplots} demonstrate that the
hyperexponential model can yield a variety of Index of Variability
curves. Hence, hyperexponential models can be used to model a wide
range of network traffic types. Although hyperexponential models
of order two (i.e., $K=2$) are capable of generating
a variety of Index of Variability curves, capturing the characteristics of
traffic with multimodal Index of Variability curves would require using
higher order ($K > 2$) hyperexponential models.
\begin{figure*}%[t]
\centering
\includegraphics[width=2.6in]{figures/rph2_b0_0001_w2_10_6.eps}
\includegraphics[width=2.6in]{figures/rph2_tau1000_b0_001.eps}
\includegraphics[width=2.6in]{figures/rph2_a1000_b0_0001.eps}
\includegraphics[width=2.6in]{figures/rph2_tau1_w2_10_7.eps}
\caption{Illustrations of 3D Index of Variability curves generated using the
\textit{hyperexponential} model with the following model parameter values:
(top left) $b = 0.0001$, $w_2 = 10^{-6}$ (top right) $\tau = 1000$, $b = 0.001$
(bottom left) $a = 1000$, $b = 0.0001$ (bottom right) $\tau = 1$,
$w_2 = 10^{-7}$.}
\label{Hvh3Dplots}
\end{figure*}
%===============================================================================
\section{Estimating $H_v(\tau)$ from Traffic Traces}
\label{EIVEMTT}
The estimation of the Index of Variability curve from a given traffic trace
requires the estimation of the first derivative of $Var[N(\tau)]$ from
discrete samples ($Var[N(\tau_i)],\ i=1,\cdots,n$). To do this, we must first
find an analytic function that best fits the discrete variance data.
This in turn requires the use of an interpolation method such as
polynomial-based interpolation, cubic spline and
smoothing spline \cite{NumericalAnalysis}-\cite{Shahraray}.
Since we use the sample variances as the estimates of
$Var[N(\tau_i)],\ i=1,\cdots,n$, we consider these estimates of the variances to
be noisy samples. The smoothing spline interpolation methods are known to have
optimal properties for estimating continuous functions and their derivatives
from a finite number of noisy samples \cite{Reinsch, Fox, Shahraray}. Note that
nonsmoothing interpolation methods such as cubic spline have the
characteristic that the estimated curve passes through all the given points.
Hence, in case of noisy data, nonsmoothing interpolation methods yield
rough curves, and therefore erroneously high first derivatives.
\subsection{Smoothing Spline Interpolation Method}
For a given data series $(x_i, y_i)$, $i=1,2,\cdots,n$, the smooth function
$f(x)$ is the solution of the minimization problem
\begin{equation}
\frac{1}{n}\sum_{i=1}^{n} (y_i - f(x_i))^2 +
\xi \int_{x_1}^{x_n} (f^{(k)})^2\,du,
\label{spdef}
\end{equation}
where $\xi$ is the smoothing parameter and $f^{(k)}$ is the $k^{th}$
derivative of $f$. If $k=2$, then $f$ is a cubic smoothing spline.
The first term in (\ref{spdef}) is the residual sum of squares, an indicator
of the goodness-of-fit of the spline curve to the data. In other words, it
measures the degree of fidelity of the smoothing spline function to the data.
The second term measures the roughness of the resulting smoothing spline
curve. The roughness of a function can be characterized by its curvature.
For example, if a function is a straight line, then its second derivative
(and therefore, roughness) is zero, that is, the second term is a penalty
term measuring how close the function is to a straight line.
The smoothing parameter $\xi$ plays an important role. It weights two aspects:
smoothness and fit. Large values of $\xi$ give a smoother curve, while small
values of $\xi$ result in a closer fit.
\subsection{Steps for Estimating $H_v(\tau)$ from Traffic Traces}
\label{stepshv}
We now present a practical method for estimating the Index of Variability
from traffic traces. Assuming that a given traffic trace is a realization
of a second-order ergodic point process whose variance curve is continuous
and differentiable. We can estimate $H_v(\tau)$ of the process as follows:
\begin{itemize}
\item
Using the \textit{Aggregated Variance} method \cite{beran} estimate the
variance-time sequence: $\widehat{Var}[N(\tau_i)],\ i=1,\cdots,n$.
\item
Using an appropriate smoothing spline implementation estimate the
smoothing spline $\widetilde{Var}[N(\tau)]$ from
$\widehat{Var}[N(\tau_i)],\ i=1,\cdots,n$.
\item
Using (\ref{varhv}) estimate the Index of Variability $\widehat{H_v}(\tau)$.
\end{itemize}
Prior to experimentation, the accuracy and robustness of this
procedure was
validated by estimating and matching the Index of Variability curves shown in
Fig. \ref{Hvh2plots} from synthetically generated data using
the \textit{hyperexponential} traffic model.
\subsection{Experimental Results}
\label{expresults}
\begin{table}%[htb]
\begin{center}
\caption{Dates and durations of the NLANR network traffic traces.
D:H:M $->$ Days:Hours:Minutes}
\begin{tabular}{|l | c | c | c |} \hline
Trace & Data Set & Date & Duration\\
& & Collected & (D:H:M)\\ \hline \hline
19991129-134258-0 & Auckland-II & 9/29/1999 & 1:14:29\\ \hline
19991129-134258-1 & Auckland-II & 9/29/1999 & 1:14:29\\ \hline
19991201-192548-0 & Auckland-II & 12/1/1999 & 1:0:2\\ \hline
20010220-226-0 & Auckland-IV & 2/20/2001 & 6:4:58\\ \hline
20010220-226-1 & Auckland-IV & 2/20/2001 & 6:4:58\\ \hline
20010301-0310-0 & Auckland-IV & 3/1/2001 & 9:14:49\\ \hline
20010301-0310-1 & Auckland-IV & 3/1/2001 & 9:14:49\\ \hline
20010609-0613-0 & Auckland-VI & 6/9/2001 & 4:6:0\\ \hline
20010609-0613-1 & Auckland-VI & 6/9/2001 & 4:6:0\\ \hline
20010609-0613-e0 & Auckland-VI & 6/9/2001 & 4:6:0\\ \hline
20010609-0613-e1 & Auckland-VI & 6/9/2001 & 4:6:0\\ \hline
20020519-525 & Bell-Lab-I & 5/19/2002 & 7:0:0\\ \hline
\end{tabular}
\label{TracesInfo}
\end{center}
\end{table}
Using the steps outlined in the previous section, we estimated the
Index of Variability curve ($H_v(\tau)$) from 12 NLANR network
traffic long traces \cite{Traces}. The dates at which each trace was collected
and their durations are listed in Table \ref{TracesInfo}. For more information
about these traffic traces, see \cite{Traces}.
Figures \ref{EstimatedHvTracesAIIandIV} and \ref{EstimatedHvTracesAVI} show the
estimated Index of Variability curves from the 12 long packet traces.
We used Matlab's spline toolbox to estimate all the smoothing splines. Its
smoothing spline implementation is based on Reinsch's approach
\cite{Reinsch, Eubank}. Based on the input data, the algorithm computes
the optimal smoothing parameter $\xi$ such that the penalized residual sum of
squares is less than a tolerance value $\epsilon > 0$. In all cases we used the
default value of $k$ ($=2$) and $\epsilon = 0.0001$.
\hl{Note that prior to estimating the Index of Variability of these
empirical traces, we did not perform any test of differentiability. Rather
we made the \textbf{restrictive assumption} that their variance curves are
differentiable}.
\begin{figure*}[p] %[htb] %[p]
\centering
\includegraphics[width=2.7in]{figures/19991129-134258-0-hvplots.eps}
\includegraphics[width=2.7in]{figures/19991129-134258-1-hvplots.eps}
\includegraphics[width=2.7in]{figures/19991201-192548-0-hvplots.eps}
\includegraphics[width=2.7in]{figures/20010220-226-0-hvplots.eps}
\includegraphics[width=2.7in]{figures/20010220-226-1-hvplots.eps}
\includegraphics[width=2.7in]{figures/20010301-0310-0-hvplots.eps}
\includegraphics[width=2.7in]{figures/20010301-0310-1-hvplots.eps}
\includegraphics[width=2.7in]{figures/bell-1-hvplots.eps}
\caption{Estimated Index of Variability Curves for Auckland II
(top first three), Aucland IV (next four), and Bell-Lab-I (last) traces}
\label{EstimatedHvTracesAIIandIV}
\end{figure*}
\begin{figure*}%[htb] %[p]
\centering
\includegraphics[width=3in]{figures/auck6-20010609-0613-0-hvplots.eps}
\includegraphics[width=3in]{figures/auck6-20010609-0613-1-hvplots.eps}
\includegraphics[width=3in]{figures/auck6-20010609-0613-e0-hvplots.eps}
\includegraphics[width=3in]{figures/auck6-20010609-0613-e1-hvplots.eps}
\caption{Estimated Index of Variability Curves for Auckland VI traces}
\label{EstimatedHvTracesAVI}
\end{figure*}
%-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=
\section{Discussion} \label{sdiscussion}
As expected, the results displayed in Figures \ref{EstimatedHvTracesAIIandIV} and
\ref{EstimatedHvTracesAVI} show that the variability of real network
traffic varies with time scales. An interesting observation is that the
Index of Variability curves derived from the Auckland traffic traces exhibit
similar monomodal behavior, while the Bell-Lab Index of Variability curve is
multimodal. Hence, \textit{hyperexponential} models of order two can be used
to well approximate the Auckland traffic processes (see Figures \ref{Hvh2plots}
and \ref{Hvh3Dplots}), but they are not appropriate to be used to capture the
characteristics of the Bell Lab traffic. Hence, the Index of Variability
can be used to reveal significant differences between traffic traces.
We believe that the characteristics exhibited by the Bell Lab traffic
can be captured either by \textit{hyperexponential} models of order higher
than two or by \textit{mixprocess} models, that is the superposition of
heterogeneous traffic processes. As an illustration, consider that an
aggregated network traffic (packet) process is the result of the
superposition of 10 renewal processes with hyperexponential interarrival
time distribution of order two (RPH2), 20 two-state Markov Modulated Poisson
processes (MMPP), 16 packetized voice streams, and 40 packet streams
generated by ON/OFF traffic sources whose ON and OFF periods
are both exponentially distributed\footnote{See \cite{Dissertation} for
more details.}.
\begin{figure*}%[htb] %[p]
\centering
\includegraphics[width=3.4in]{figures/mixHvandRPH2.eps}
\caption{Analytically derived Index of Variability curve for the case of
\textit{mixprocess} traffic model example.}
\label{mixprocess}
\end{figure*}
The resulting Index of Variability curve for this \textit{mixprocess}
traffic model is shown in Fig. \ref{mixprocess}. Note that the dash-line
curve is the $H_v$ curve for the case of aggregating only 10 identical
RPH2 processes. Comparing the Index of Variability curves of Figures
\ref{EstimatedHvTracesAIIandIV} and \ref{mixprocess}, it can be inferred that
the Bell-Lab traffic can be well modeled using such a \textit{mixprocess}
traffic model.
Evidently, the Index of Variability is a valuable tool that can provide
new insights and understanding of the dynamics of network traffic.
$H_v$ curves can be used to identify the characteristics of networks
or applications that generate the various types of traffic patterns.
An $H_v$ curve can be regarded as a "signature" of a particular network
or application. To further understand the difference between the Auckland and
Bell-Lab Index of Variability curves, these two networks must be
compared in terms of their architecture, protocols employed at each layer,
physical links, applications, and other network specific characteristics.
%===============================================================================
\section{Conclusion}
Knowledge of the traffic characteristics on multiple time scales can help
to improve the efficiency of traffic control mechanisms. In addition, the
design and provision of quality-of-service-guarantees over the Internet requires
the understanding of traffic characteristics, such as variability.
This paper presented an alternative measure of traffic burstiness
called the \textit{Index of Variability} ($H_v(\tau)$),
that describes the degree of variability of a typical
network traffic process at each \hl{critical time scale} and is analytically tractable for
many traffic models. Analytical derivations of $H_v(\tau)$ were given
for two conventional traffic models. Several generated 2D and 3D
Index of Variability curves predicate that the Index of Variability
can help in determining the complexities of the network traffic variability
over time scales that are relevant to network performance.
This paper also presented a practical method for estimating the Index of
Variability curves from traffic traces. Using this method, the
Index of Variability curves for 12 NLANR network traffic long traces were
estimated. The results indicate that the variability of real network traffic
varies with time scales.
In summary, the Index of Variability offers the potential to gain insights
into the dynamics of network traffic that existing tools do not offer.
Future work involves developing methods of fitting analytically obtained
Index of Variability functions to empirically obtained Index of Variability
curves. To accomplish this, nonlinear optimization techniques will be utilized.
In addition, studies to find relations that associate $H_v(\tau)$ with
\hl{H\"{o}lder exponent $h(t)$} \cite{abry} and queuing performance metrics such as
packet loss rate and delay will be performed.
%===============================================================================
%\section*{Acknowledgments}
%The authors would like to acknowledge the suggestions of many people.
\nocite{*}
\bibliographystyle{IEEE}
%%%%%\bibliography{bib-file} % commented if *.bbl file included, as seen below
%%%%%%%%%%%%%%%%% BIBLIOGRAPHY IN THE LaTeX file !!!!! %%%%%%%%%%%%%%%%%%%%%%%%
%% This is nothing else than the IEEEsample.bbl file that you would %%
%% obtain with BibTeX: you do not need to send around the *.bbl file %%
%%---------------------------------------------------------------------------%%
%===============================================================================
\begin{thebibliography}{1}
\bibitem{iasted}
G. Y. Lazarou, X. Xiangdong and V. S. Frost,
"Internet traffic modeling using the index of variability,"
in \textit{Proc. IASTED International Conference on Modeling and
Simulation,} 2003, pp. 31--37.
\bibitem{Duffy}
D. Duffy, A. McIntosh, M. Rosenstein and D. Wilson,
"Statistical analysis of CCSN/SS7 traffic data from working CCS
subnetworks," \textit{IEEE JSAC}, vol. 12, no. 3, pp. 544--551, Apr. 1994.
\bibitem{Fowler}
H. J. Fowler and W. Leland, "Local area network traffic
characteristics, with implication for network congestion management,"
\textit{IEEE JSAC,} vol. 9, no. 7, pp. 1139--1149, Sept. 1991.
\bibitem{Leland}
W. Leland, M. Taqqu, W. Willinger and D. Wilson,
"On the self-similar nature of ethernet traffic (extended version),"
\textit{IEEE/ACM Trans. on Networking,} vol. 2, no. 1, pp. 1--15, Feb. 1994.
\bibitem{Paxson}
V. Paxson and S. Floyd, "Wide-area traffic: The failure of Poisson
modeling," \textit{IEEE/ACM Trans. on Networking,} vol. 3, no. 3,
pp. 226--244, Jun. 1995.
\bibitem{Erramilli}
A. Erramilli, O. Narayan and W. Willinger,
"Experimental queueing analysis with long-range dependent packet traffic,"
\textit{IEEE/ACM Trans. on Networking,} vol. 4, no. 2, pp. 209--223, Apr. 1996.
\bibitem{Grossgluser}
M. Grossglauser and J.-C. Bolot,
"On the relevance of long-range dependence in network traffic,"
\textit{IEEE/ACM Trans. on Networking,} vol. 7, no. 5, pp. 629--640, Oct. 1999.
\bibitem{Krishnan2}
K. R. Krishnan, A. L. Neidhardt and A. Erramilli,
"Scaling analysis in traffic management of self-similar processes,"
in \textit{Proc. 15th ITC,} 1997, pp. 1087--1096.
\bibitem{Neidhardt}
A. L. Neidhardt and J. L. Wang, "The concept of relevant time
scales and its application to queueing analysis of self-similar traffic
(or is Hurst naughty or nice?)," in \textit{Proc. ACM SIGMETRICS,} 1998,
pp. 222--232.
\bibitem{ParkBook}
K. Park and W. Willinger, Editors, \textit{Self-Similar Network
Traffic And Performance Evaluation,} New York: John Wiley \& Sons, 2000.
\bibitem{beran}
J. Beran, \textit{Statistics for Long-Memory Processes. Monographs
on Statistics and Applied Probability}, New York: Chapman and Hall, 1994.
\bibitem{estimators}
M. Taqqu, V. Teverovsky and W. Willinger, "Estimators for
long-range dependence: An emperical study," \textit{Fractals,}
vol. 3, no. 4, pp. 785--798, 1995.
\bibitem{DarryVeitch}
D. Veitch and P. Abry, "A wavelet based joint estimator for the parameters of
LRD," Special issue on Multiscale Statistical Signal Analysis and
its Applications, \textit{IEEE Trans. Information Theory,} vol. 45, no. 3,
Apr. 1999.
\bibitem{Baiocchi}
A. Baiocchi, N. Melazzi, M. Listanti, A. Roveri and R. Winkler,
"Modeling isssues on an ATM multiplexer within a bursty traffic
environment," in \textit{Proc. IEEE INFOCOM,} 1991, pp. 83--91.
\bibitem{Norros}
I. Norros, "A storage model with self-similar input,"
\textit{Queueing Systems,} vol. 16, pp. 387--396, 1994.
\bibitem{leland}
W. Leland and D. Wilson, "High time-resolution measurement
and analysis of LAN traffic: Implication for LAN interconnection,"
in \textit{Proc. IEEE INFOCOM,} 1991, pp. 1360--1366.
\bibitem{duffield}
N. G. Duffield, J. T. Lewis, N. O'Connel, R. Russell and F. Toomey,
"Statistical issues raised by the Bellcore data," in \textit{Proc. of the
$11^{th}$ Teletraffic Symposium on Performance Engineering in
Telecommunications Networks,} 1994, pp. 1--8.
\bibitem{Duffield}
N. G. Duffield, J. T. Lewis, N. O'Connel, R. Russell and F. Toomey,
"Predicting quality of service for traffic with long-range fluctuations,"
in \textit{Proc. IEEE ICC,} 1995, pp. 473--477.
\bibitem{Krishnan1}
K. R. Krishnan, "A new class of performance results for a
fractional brownian traffic model," Queueing Systems, vol. 22,
pp. 277--285, 1996.
\bibitem{QiongLi}
Q. Li and D. Mills, "Investigating the scaling behavior, crossover and
anti-persistence of Internet packet delay dynamics," in \textit{Proc. IEEE
Globecom,} 1999, pp. 1843--1852.
\bibitem{Ribeiro}
V. J. Ribeiro, R. Riedi and R. G. Baraniuk, "Wavelets and multifractals for
network traffic modeling and inference," in \textit{Proc. IEEE ICASSP,} 2001,
pp. 3429--3432.
\bibitem{abry}
P. Abry, R. Baraniuk, P. Flandrin, R. Riedi and D. Veitch,
"Multiscale nature of network traffic," \textit{IEEE Signal Processing
Magazine,} vol. 19, no. 3, pp. 28--46, May 2002.
\bibitem{Kant}
K. Kant, "On aggregate traffic generation with multifractal properties,"
in \textit{Proc. IEEE Globecom,} 1999, pp. 801--804.
\bibitem{Melo}
\hl{C. A. V. Melo and N. L. S. da Fonseca, "Envelope Process and Computation
of the Equivalent Bandwidth of Multifractal Flow," vol. 48, no. 3, pp. 351--375, 2005.}
\bibitem{Riedi}
R. Riedi, M. S. Crouse, V. J. Ribeiro and R. G. Baraniuk, "A multifractal
wavelet model with application to network traffic," \textit{IEEE Trans. on
Information Theory,} vol. 45, no. 3, pp. 992--1018, Apr. 1999.
\bibitem{Vehel}
J. L. Vehel and B. Sikdar, "A multiplicative multifractal for TCP traffic,"
in \textit{Proc. of the 6th IEEE Symposium on Computers and Communications,}
2001, pp. 714-719.
\bibitem{Gilbert}
A. C. Gilbert, W. Willinger and A. Feldmann, "Scaling analysis of conservative
cascades, with applications to network traffic," \textit{IEEE Trans. on
Information Theory,} vol. 45, no. 3, pp. 971--991, Apr. 1999.
\bibitem{MSTaqqu}
M. Taqqu, V. Teverovsky and W. Willinger, "Is network traffic self-similar
or multifractal?" \textit{Fractals}, vol. 5, pp. 63--73, 1997.
\bibitem{Horvath}
A. Horvath and M. Telek, "A \hl{Markovian} point process exhibiting multifractal
behaviour and its application to traffic modeling," in \textit{Proc. 4th
International Conference Matrix Analytic Methods in Stochastic Models,} 2002.
\bibitem{idc-veitch}
D. Veitch, P. Abry, P. Flandrin and P. Chainais, "Infinitely divisible
cascade analysis of network traffic data," in \textit{Proc. IEEE ICASSP,} 2000,
pp. 245--248.
\bibitem{Willinger-Paxson}
W. Willinger, V. Paxson, R. Riedi and M. Taqqu, "Long-range dependence and data
network traffic," in \textit{Long-range Dependence: Theory and Applications},
P. Doukhan, G. Oppenheim, M. Taqqu, Eds., Birkhauser, 2002.
\bibitem{Heffes}
H. Heffes and D. M. Lucantoni, "A \hl{Markov} modulated characterization of
packetized voice and data traffic and related statistical multiplexer
performance," \textit{IEEE JSAC,} vol. SAC-4, no. 6, pp. 856--868,
Sept. 1986.
\bibitem{Feldman}
A. Feldman and W. Whitt, "Fitting mixtures of exponentials to long-tail
distributions to analyze network performance models,"
\textit{Performance Evaluation,} vol. 31, no. 8, pp. 963--976, Aug. 1998.
\bibitem{Gusella}
R. Gusella, "Characterizing the variability of arrival processes
with indexes of dispersion," \textit{IEEE JSAC,} vol. 9, no. 2, pp. 203--211,
Feb. 1991.
\bibitem{Greiner}
M. Greiner, M. Jobmann and L. Lipsky, "The importance
of power-tail distributions for telecommunications traffic modeling,"
Institute f\"{u}r Informatik, Technische Universit\"{a}t
M\"{u}nchen, M\"{u}nchen, Germany, Tech. Rep., 1995.
\bibitem{Renewal}
D. R. Cox, \textit{Renewal Theory}, London: J. Wiley \& Sons, 1962.
\bibitem{Dissertation}
G. Y. Lazarou, \textit{On the Variability of Internet Traffic,}
Ph.D. Dissertation, Electrical Engineering and Computer Science,
University of Kansas, 2000.
\bibitem{Kleinrock}
L. Kleinrock, \textit{Queueing Systems, Volume I: Theory,}
New York: J. Wiley \& Sons, 1975.
\bibitem{Traces}
J. Micheel, NLANR PMA: Special Traces Archive,
[Online]. Available: http://pma.nlanr.net/Traces/long/
\bibitem{NumericalAnalysis}
R. L. Burden and J. D. Faires, \textit{Numerical Analysis} $7^{th}$ ed.,
Brooks/Cole, 2001.
\bibitem{Reinsch}
C. M. Reinsch, "Smoothing by spline functions," \textit{Numerische Mathematik},
vol. 10, pp. 177--183, 1967.
\bibitem{Eubank}
R. L. Eubank, \textit{Spline Smoothing and Nonparametric Regression,}
New York:Marcel Dekker, 1988.
\bibitem{Fox}
J. Fox, \textit{Nonparametric Simple Regression: Smoothing Scatterplots,}
Californian:Sage Publications, Thousand Oaks, 2000.
\bibitem{Shahraray}
B. Shahraray and D. J. Anderson, "Optimal estimation of contour properties by
cross-Validated regularization," \textit{IEEE Trans. on Pattern Analysis and
Machine Intelligense,} vol. 11, no. 6, pp. 600--610, Jun. 1989.
\end{thebibliography}
%\section*{Appendix}
%\appendix
%===============================================================================
\begin{biography}[{\includegraphics{bios/lazarou.eps}}]{Georgios Y. Lazarou}
is currently an Assistant Professor in the Electrical and Computer
Engineering Department at Mississippi State University. He is a founding
member of the Telecommunication and Information Technology Laboratory (TITL)
at Mississippi State University. Currently, his is member of the
Intelligent Electronic Systems (IES) program at CAVS. His current research
interests lie in the area of next generation smart networking technologies,
wireless networking for intelligent transportation systems, and energy efficient
protocols for wireless sensor networks. He has been involved in research
projects concerning the design of adaptive and reconfigurable networks,
modeling and evaluating the performance of high-speed wide-area
asynchronous transfer mode (ATM) networks and Internet, and characterization
of network traffic. Results from his work have been published in numerous
journal and conference articles, and in technical reports.
\end{biography}
\begin{biography}[{\includegraphics{bios/baca.eps}}]{Julie Baca}
is currently a Research Assistant Professor at the Center for Advanced Vehicular
Systems at the Mississippi State University. Prior to this, Dr. Baca was a
member of the computer science research group of the Information Technology
Laboratory at U.S. Army Corps of Engineers. Currently, Dr. Baca directs the
mobile computing usability and the in-vehicle dialogue interface projects with
an emphasis on voice over IP. She has over a decade of experience in designing
complex software system interfaces for voice and multimedia applications over
the Internet. Her research interests include mobile computing, wireless
networking, operating systems, and user interface design in mobile environments.
Dr. Baca received her Ph.D. degree from Mississippi State University in 1998,
and is a member of ACM.
\end{biography}
\begin{biography}[{\includegraphics{bios/frost.eps}}]{Victor S. Frost}
is currently the Dan F. Servey Distinguished Professor of Electrical
Engineering and Computer Science and Director of the University of Kansas
Telecommunications and Information Technology Center (ITTC). He is a Fellow
of the IEEE and received a Presidential Young Investigator Award from the
National Science Foundation in 1984. His current research interest is in the
areas of internet quality of service, traffic management, and integrated
broadband communication networks. He has been involved in research on several
national scale high speed wide area testbeds. Government agencies, including,
NSF, DARPA, Rome Labs, and NASA have sponsored his research. Professor
Frost has been involved in research for numerous corporations, including
Harris, Sprint, NCR, BNR, Telesat Canada, AT\&T, McDonnell Douglas, DEC, and
COMDISCO Systems. He has published over 100 journal articles and
conference papers. Dr. Frost received the BS, MS, and Ph.D. degrees from
the University of Kansas, Lawrence in 1977, 1978, and 1982, respectively.
In 1982 he joined the faculty of the University of Kansas
\end{biography}
\begin{biography}[{\includegraphics{bios/evans.eps}}]{Joseph B. Evans}
is the Deane E. Ackers Distinguished Professor of
Electrical Engineering \& Computer Science and Director of Research
Information Technology at the University of Kansas. He recently
served as a Program Director in the Division of Computer \& Network
Systems in the Directorate for Computer \& Information Science \&
Engineering at the National Science Foundation.
His research interests include mobile and wireless networking, pervasive
computing systems, high speed networks, and adaptive computing systems.
He has been involved in major national high performance networking
testbeds and broadband wireless mobile networking efforts, and has
published over 100 journal and conference works. Dr. Evans received his
PhD degree from Princeton University in 1989, is a senior member of the
IEEE, and a member of the ACM.
\end{biography}
\end{document}