\documentclass[10pt, journal]{IEEEtran}
\usepackage{times}
\usepackage{mathptm}
\usepackage{epsfig}
\usepackage{amssymb}
\usepackage{amsfonts}
% Define the Laplace Transform Pair Symbol
\def\LapTpairSyb#1{
\mathop{\ \Longleftrightarrow \ }\limits^{#1}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\DeclareSymbolFont{slanted}{OT1}{cmr}{m}{sl}
\DeclareSymbolFontAlphabet\mathsl{slanted}
\begin{document}
%
\title{Variance-Time Curve for Packet Streams Generated by Exponentially
Distributed ON/OFF Sources}
\author{Georgios Y. Lazarou and Victor S. Frost
\thanks{Dr. Lazarou is with the New York City Transit
(Email: glaz@ieee.org).}
\thanks{Dr. Frost is with the University of Kansas
(Email: frost@ittc.ku.edu).}}
\maketitle
%************************************************************************************
\begin{abstract}
In this letter we provide a solution to an open problem in network traffic
characterization. Specifically we present a closed-form expression of the
variance-time curve for a packet stream generated by exponentially
distributed ON/OFF sources. So far, the variance-time curve for such processes
was obtained by numerical analysis at the desired time scales.
We also show that under low and medium loads, the variance-time curve
obtained by approximating the ON/OFF/Exponential source as a stationary
fluid source is over-estimated. Lastly, as a by-product of our analysis, we
present a new mathematical identity based on the incomplete Gamma function.
\end{abstract}
%------------------------------------------------------------------------------------
\section{Introduction}
Traffic is the driving force behind all telecommunication activities, and
models are of crucial importance for evaluating network performance.
In this letter we consider a traditional model, namely the
ON/OFF Exponential traffic source model. This traffic model became
popular when it was used in \cite{Sriram} to characterize the aggregate
packet arrival process generated by the superposition of separate voice
streams. For computing the index of dispersion for counts (IDC) for
an aggregated voice-packet stream, the variance-time curve was obtained
in \cite{Heffes} by numerical analysis at the desired time scales.
Our main goal in this letter is to derive a closed-form expression
of the variance-time curve for the packet streams generated by such
traffic sources. This closed-form expression of the variance-time is
very useful for better characterizing the variability of packet streams
that are generated by such traffic sources, i.e., VoIP packet traffic
sources. This exact expression of the variance-time curve is then compared
with an approximated expression derived when considering the
ON/OFF/Exponential sources as a stationary fluid source.
%==============================================================================================
\section{ON/OFF Exponential Source Model}
We consider a packet stream (Fig. \ref{singleONOFF}) generated
by a single ON/OFF traffic source with strictly alternating ON- and
OFF-periods. The OFF-periods are exponentially distributed with mean
$\frac{1}{\beta}$, and
during the ON-periods, the source transmits a packetized message
whose size is also exponentially distributed. Hence, the number of packets
($W$)
transmitted during ON times is geometrically distributed, and thus
\begin{figure}[bht]
\centering
\includegraphics[width=2.4in]{figures/onoff.eps}
\caption{Packet Stream Generated by a Single ON/OFF Source}
\label{singleONOFF}
\end{figure}
the packet stream due to a single source is a renewal process.
Assuming that the size of all packets transmitted is fixed, the probability
density function (pdf) for the packet interarrival times is given by
\cite{Sriram}
\begin{equation}
f(x) = p\delta (x-T) + (1-p)\beta e^{-\beta (x-T)} u(x-T)
\label{fx}
\end{equation}
where $u(t)$ is the unit step function, $T$ the packet transmission time, and
$p$ ($0 < p < 1$) the probability that the next interarrival time\footnote{
We assume that packets from the same message are transmitted back to back
without any inter-idle time.}
is $T$. The interarrival time is measured from the last arrival bit of the
$(n-1)^{st}$ packet to the last arrival bit of the $n^{th}$ packet.
Define $E[W]$ as the mean number of packets transmitted during the ON periods,
then
\[ p = \frac{E[W]-1}{E[W]}.\]
That is, the interarrival times $X_1, X_2, \dots, X_n$ are of length $T$
with probability $p$ and of length $I + T$ with probability $1-p$, where
$I$ is the exponentially distributed random length of the OFF periods.
The mean packet arrival rate is therefore
\begin{eqnarray}
\lambda = \frac{1}{E[X]} = \frac{1}{\int_0^{\infty} x f(x) \,dx}
= \frac{\beta}{(1-p) + \beta T}
\label{lambda}
\end{eqnarray}
Let $\alpha^{-1}$ to be the mean ON time. Then $\alpha^{-1} = E[W] T$, and
since $E[W] = \frac{1}{1-p}$, we have that $\alpha T = 1 - p$.
%\begin{equation}
%\alpha T = 1 - p.
%\label{aT}
%\end{equation}
%==============================================================================================
\section{Deriving the Variance-Time Curve}
Assuming an arbitrary origin, the renewal process $\{N(t), t \ge 0\}$ is
stationary \cite{Lewis}, where $N(t)$ denotes the number of packet arrivals
in an interval of length $t$. The variance of arrival counts over a time
interval of length $t$, or variance-time curve, is
\begin{eqnarray}
Var[N(t)] & = & E[N^2(t)] - (E[N(t)])^2 \nonumber \\
& = & E[N(t)\{N(t)+1\}] - E[N(t)] - (E[N(t)])^2 \nonumber \\
& = & \Psi(t) - \lambda t - (\lambda t)^2
\label{VNt}
\end{eqnarray}
where the challenge here is to obtain
\begin{equation}
\Psi(t) = E[N(t)\{N(t)+1\}].
\label{Psi}
\end{equation}
It is known from \cite{Renewal} that on taking the Laplace transform
of $\Psi(t)$ we get
\begin{equation}
{\mit\Psi}^{*}(s) = {\cal L}[\Psi(t)]
= \frac{2\lambda}{s^2 \{1 - {\mathsl{f}}^{*}(s)\}} \qquad for \ Re[s] > 0,
\label{LPsi}
\end{equation}
where
\begin{eqnarray}
{\mathsl{f}}^{*}(s) & = & {\cal L}[f(x)] = \int_0^{\infty} f(x) e^{-sx} \,dx
\nonumber\\
& = & \left[ p + (1 - p) \frac{\beta}{s + \beta}\right] e^{-sT}
\label{Lfx}
\end{eqnarray}
is the Laplace transform of $f(x)$.
Hence,
\begin{equation}
{\mit\Psi}^{*}(s)
= \frac{2\lambda}{s^2 \left\{ 1 -
\left[ p + (1 - p)\frac{\beta}{s + \beta}\right] e^{-sT}\right\} } \nonumber\\
= \frac{{\varphi}^{*}(s)}{s^2}
\label{LLPsi}
\end{equation}
by letting
\begin{equation}
{\varphi}^{*}(s) = \frac{2\lambda}{1 -
\left[ p + (1 - p)\frac{\beta}{s + \beta}\right] e^{-sT}}.
\label{Lphi}
\end{equation}
The next step in getting $\Psi(t)$ is to compute the inverse Laplace
transform of ${\mit\Psi}^{*}(s)$
\begin{equation}
\Psi(t) = {\cal L}^{-1}[{\mit\Psi}^{*}(s)] =
\int_{c - j\infty}^{c + j\infty}{\mit\Psi}^{*}(s) e^{st}\,ds
\label{ILT}
\end{equation}
where $Re[s] = c > 0$ being chosen so that all singularities of
${\mit\Psi}^{*}(s)$ lie to the left of the line of integration.
Now, let $s = a + j b$ where $a = Re[s]$ and $b = Im[s]$. Then
\begin{eqnarray}
\left|{\mathsl{f}}^{*}(s)\right|
& = & \left| \left[ p + (1 - p) \frac{\beta}{s + \beta}\right] e^{-sT} \right|
\nonumber \\
& = & \left| \left[ p + (1 - p) \frac{\beta}{a + j b + \beta}\right]
e^{-(a + j b) T} \right| \nonumber \\
& = & \left| p + (1 - p) \frac{\beta}{a + \beta + j b}\right|
\left| e^{-(a + j b) T} \right| \nonumber \\
& = & \left| \frac{pa + p\beta + j pb + \beta - p\beta}{
a + \beta + j b}\right| e^{-aT} \nonumber \\
& = & \left| \frac{pa + \beta + j pb}{a + \beta + j b}\right| e^{-aT}.\nonumber
\label{ALfx}
\end{eqnarray}
Clearly,
$e^{-aT} < 1 \ \ \forall\, a = Re[s] > 0$
and
\[ \left| \frac{pa + \beta + j pb}{a + \beta + j b}\right|
= \sqrt{\frac{(pa + \beta)^2 + (pb)^2}{(a + \beta)^2 + b^2}} < 1\]
for
\[\begin{array}{l}
\forall\, 0 < p < 1, \ \beta > 0,\\
\forall\, a = Re[s] > 0, \ and\\
\forall\, b = Im[s],
\end{array}\]
making
\begin{equation}
\left| {\mathsl{f}}^{*}(s) \right| < 1 \qquad for \ Re[s] > 0.
\label{ALTfx}
\end{equation}
Thus, for $Re[s] > 0$
\[ {\varphi}^{*}(s) = \frac{2\lambda}{1 - {\mathsl{f}}^{*}(s)} \]
is a geometric series\footnote{Geometric Series:
$\sum_{n = 0}^{\infty} \alpha x^n = \frac{\alpha}{1 - x} \ \ for\
\left| x \right| < 1.$}.
Therefore, on the line of integration $Re[s] = c > 0$ in (\ref{ILT})
$|{\mathsl{f}}^{*}(s)| < 1$ and the function ${\varphi}^{*}(s)$
is equal to
\begin{equation}
\sum_{n = 0}^{\infty} 2\lambda \left[{\mathsl{f}}^{*}(s)\right]^n
= 2\lambda \sum_{n = 0}^{\infty}
\left[p + (1 - p) \frac{\beta}{s + \beta}\right]^n e^{-snT}.
\label{gvarphis}
\end{equation}
Upon using the Binomial Theorem\footnote{Binomial Theorem:
$\left(a + x \right)^n = \sum_{z = 0}^{n} {n \choose z} a^{n-z} x^{z}
= a^n + {n \choose 1} a^{n-1} x + {n \choose 2} x^2 + \cdots + x^n.$}
in (\ref{gvarphis}) we get
%-----------------------------------------------------------------------------
\begin{eqnarray}
{\varphi}^{*}(s) & = & 2\lambda\sum_{n = 0}^{\infty}\sum_{z = 0}^{n}
{n \choose z} p^{n-z}\left[ (1-p)\frac{\beta}{s + \beta}\right]^{z}e^{-snT}
\nonumber\\
& = & 2\lambda \sum_{n = 0}^{\infty} p^{n}e^{-snT} + \nonumber\\
& & 2\lambda
\sum_{n = 1}^{\infty}\sum_{z = 1}^{n}{n \choose z}
p^{n-z}(1-p)^{z}{\beta}^{z}\frac{e^{-snT}}{(s + \beta)^z}.
\label{afterBinomial}
\end{eqnarray}
%-----------------------------------------------------------------------------
Letting
\[ {\varphi}_{1}^{*}(s) = 2\lambda \sum_{n = 0}^{\infty} p^{n}e^{-snT} \]
and
\[ {\varphi}_{2}^{*}(s) = 2\lambda \sum_{n = 1}^{\infty}
\sum_{z = 1}^{n}{n \choose z}p^{n-z}(1-p)^{z}{\beta}^{z}
\frac{e^{-snT}}{(s + \beta)^z}, \]
then
${\varphi}^{*}(s) = {\varphi}_{1}^{*}(s) + {\varphi}_{2}^{*}(s)$
and
\[{\mit\Psi}^{*}(s) = \frac{{\varphi}^{*}(s)}{s^2} =
\frac{{\varphi}_{1}^{*}(s)}{s^2} + \frac{{\varphi}_{2}^{*}(s)}{s^2} =
{\mit\Psi}_{1}^{*}(s) + {\mit\Psi}_{2}^{*}(s). \]
Obviously,
$\Psi(t) = \Psi_{1}(t) + \Psi_{2}(t).$
Using the Laplace transform pair \cite{LPtables}
\[ \frac{e^{-as}}{s^2} \LapTpairSyb{{\cal L}} (t - a) u(t-a)
\qquad a \ge 0 \]
we easily obtain
\begin{equation}
\Psi_{1}(t) = 2\lambda \sum_{n = 0}^{\infty} p^{n} (t - nT) u(t - nT).
\label{Psi1}
\end{equation}
Similarly, by using the Laplace transform pair
\begin{eqnarray}
\frac{e^{-snT}}{s^2 (s + a)^{z}} & \LapTpairSyb{{\cal L}} &
\frac{1}{a^{z+1}}\left\{ a(t-nT)G\left[ a(t - nT), z\right]\right. -
\nonumber \\
& & \left. z G\left[ a(t - nT), z+1\right]\right\} u(t-nT)\nonumber
%\qquad \begin{array}{l}a,nT \ge 0\\ z=1,2,\dots \end{array}\nonumber
\end{eqnarray}
for $a,nT \ge 0$ and $z=1,2,\dots$, where
\[ G(x,y) = \frac{1}{\Gamma(y)} \int_{0}^{x} t^{y-1} e^{-t}\,dt
\qquad y > 0, \ \ x > 0 \]
is the incomplete Gamma\footnote{Gamma Function:
$\Gamma(y) = \int_{0}^{\infty} t^{y-1}e^{-t}\,dt \qquad y > 0.$] } function,
we get
%=============================================================================
\begin{eqnarray}
\Psi_{2}(t) & = & 2\lambda \sum_{n = 1}^{\infty}\sum_{z = 1}^{n}{n \choose z}
\frac{p^{n-z}(1-p)^{z}}{\beta}\{ \beta(t - nT)\times\\
& & G\left[\beta(t - nT),z\right] - z G\left[\beta(t - nT),z+1\right]\}
u(t - nT).\nonumber
\label{Psi2}
\end{eqnarray}
A slightly different form of $\Psi_{2}(t)$ is presented in the Appendix,
as well as a new mathematical identity based on the incomplete Gamma
function derived by comparing the two forms of $\Psi_{2}(t)$.
Putting everything together, we then obtain the variance-time curve as:
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\begin{eqnarray}
Var[N(t)] & = & \Psi_{1}(t) + \Psi_{2}(t) - \lambda t - (\lambda t)^2\nonumber\\
& = & 2\lambda \sum_{n = 0}^{\infty} p^{n} (t - nT)u(t - nT) +
2\lambda \sum_{n = 1}^{\infty}\sum_{z = 1}^{n}{n \choose z}\times\nonumber\\
& & \frac{p^{n-z}(1-p)^{z}}{\beta}\{ \beta(t - nT)G\left[\beta(t - nT),z\right] -
\nonumber\\
& & z G\left[\beta(t - nT),z+1\right]\} u(t - nT)
- \lambda t - (\lambda t)^2.\nonumber\\
\label{VARNt}
\end{eqnarray}
Suppose now an aggregated packet stream is generated by the superposition of $M$
independent but not necessarily identical ON/OFF/Exponential sources.
Assuming again stationarity, then the index of dispersion for counts is
given by
\begin{displaymath}
IDC(t) = \frac{\sum_{i=1}^{M} Var[N_i(t)]}{\sum_{i=1}^{M} \lambda_i t}
\label{superposeIDC}
\end{displaymath}
where $\lambda_i$ is the mean packet arrival rate and $N_i (t)$ is the
number of packet arrivals in the interval $(0,t]$ from the $i^{th}$
source. In case that the sources are also identical, then the
IDC for the aggregated packet stream is identical to that of a
single source.
%====================================================================================================
\section{Comparison with the Fluid Source Model}
\label{Fluid}
Considering the ON/OFF/Exponential traffic source as a stationary fluid source
with a constant transmission rate $\nu = \frac{1}{T}$ during the ON-periods,
it can be described by a two-state Markov process. Letting
$\rho = \alpha + \beta$, we then have from
\cite{Chou, cost242} the approximate\footnote{During the ON-periods the
burst of consecutive packets generated by the source is considered as
a continuous fluid. Denote $I(t) = 1_{\{source\ is\ ON\ at\ time\ t\}}$, then
the cumulative number of packets generated by the source in time interval
$(0, t]$ is approximately $\tilde{N}(t) = \int_{0}^{t} \nu I(t)\,ds$.}
variance-time curve as
\begin{equation}
\tilde{V}ar[N(t)] = \frac{2(1 - p) \lambda^3}{\beta^2}
\left[ t - \frac{1}{\rho} \left( 1 - e^{- \rho t}\right)
\right].
\label{fVNt}
\end{equation}
One way to see that $\tilde{V}ar[N(t)]$ is an
approximate of $Var[N(t)]$ given by (\ref{VARNt}) is by checking whether
in the limit the index of dispersion for counts is equal with the
squared coefficient of variation of the interarrival times\footnote{
Since $N(t)$ is a renewal process, then
$\lim_{t \to \infty} IDC(t) = \lim_{t \to \infty}(Var[N(t)]/E[N(t)])
= {\cal C}^{2}(X) = Var[X] / (E[X])^2 =
\lambda^2 (1-p^2)/\beta^2$.},
${\cal C}^{2}(X)$:
$\lim_{t \to \infty} \tilde{IDC}(t) = \frac{2}{1 + p}{\cal C}^{2}(X)$.
From this, the following is easily obtained:
\begin{equation}
\lim_{t \to \infty}\frac{\tilde{V}ar[N(t)]}{Var[N(t)]} = \frac{2}{1 + p}.
\label{compVV}
\end{equation}
Clearly, as the mean number of packets transmitted during the ON periods ($E[W]$)
increases, and thus $p \to 1$, $\tilde{V}ar[N(t)] \to Var[N(t)]$ for
large enough $t$. But as $E[W]$ decreases and thus $p \to 0$,
$\tilde{V}ar[N(t)] \to 2 Var[N(t)]$ for large enough $t$. This shows
that under low and medium loads, network performance obtained
by using fluid analysis is over-estimated.
%************************************************************************************
\section{Conclusion}
\label{conclusion}
We derived an exact expression of the variance-time curve using point
processes analysis for packet streams generated by exponentially
distributed ON/OFF network traffic sources. In addition, we showed that the fluid analysis
over-estimates the variance-time curve under low or medium load conditions.
Finally, our analysis generated a new mathematical identity based on
the incomplete Gamma function.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%BIBILIOGRAPHY%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{12}
\bibitem{Sriram}
K. Sriram and W. Whitt, ``Characterizing Superposition Arrival Processes in
Packet Multiplexers for Voice and Data,'' IEEE J. Select. Areas Commun.,
Vol. SAC-4, No. 6, pp. 833-846, Sept.1986.
\bibitem{Heffes}
H. Heffes and D.M. Lucantoni, ``A Markov Modulated Characterization of
Packetized Voice and Data Traffic and Related Statistical Multiplexer
Performance,'' IEEE Journal on Selected Areas in Communications, Vol. SAC-4,
No. 6, pp. 856-868, Sept. 1986.
\bibitem{Lewis}
D. R. Cox and P. A. Lewis, \textit{The Statistical Analysis of Series
of Events}, London: Methuen, New York: J. Wiley \& Sons, 1966.
\bibitem{Renewal}
D. R. Cox, \textit{Renewal Theory}, London: Methuen,
New York: J. Wiley \& Sons, 1962.
\bibitem{LPtables}
Paul A. McCollum and Buck F. Brown, \textit{Laplace Transform Tables And
Theorems}, Holt, Rinehart and Winston, New York, 1965.
\bibitem{Chou}
L.-S. Chou and C.-S. Chang, ``Experiments of the Theory of Effective
Bandwidth for Markov Sources and Video Traces,'' \textit{in Proc. of IEEE INFOCOM,} 1996, pp. 497-504.
\bibitem{cost242}
James Roberts, Ugo Mocci, Jorma Virtamo, \textit{\textbf{
Broadband Network Teletraffic}: Performance Evaluation and Design
of Broadband Multiservice Networks; Final Report of Action COST 242},
Springer, 1996.
\end{thebibliography}
%=========================================================================
\appendix
\section{Mathematical Identity}
Let ${\mit\xi}_{2}^{*}(s) = \frac{{\varphi}_{2}^{*}(s)}{s}$, so that
${\mit\Psi}_{2}^{*}(s) = \frac{{\varphi}_{2}^{*}(s)}{s^2}
= \frac{{\mit\xi}_{2}^{*}(s)}{s}$
and
\[ {\mit\xi}_{2}^{*}(s) = 2\lambda \sum_{n = 1}^{\infty}
\sum_{z = 1}^{n}{n \choose z}p^{n-z}(1-p)^{z}{\beta}^{z}
\frac{e^{-snT}}{s (s + \beta)^z}. \]
Applying the following Laplace transform pair \cite{LPtables}
\[
\frac{e^{-snT}}{s (s + a)^{z}} \LapTpairSyb{{\cal L}}
\frac{1}{a^{z}}\left\{1 - e^{-a(t-nT)}\sum_{m=0}^{z-1}\right.
\left. \frac{[a(t-nT)]^{m}}{m!}\right\}u(t-nT)
\]
for $a,nT \ge 0$ and $z=1,2,\dots$, we get
\begin{eqnarray}
\xi(t) & = & 2\lambda \sum_{n = 1}^{\infty}\sum_{z = 1}^{n}{n \choose z}
p^{n-z}(1-p)^{z} \times \nonumber\\
& & \left\{1 - e^{-\beta(t-nT)}
\sum_{m=0}^{z-1}\frac{[\beta(t-nT)]^m}{m!}\right\}u(t-nT).\nonumber
\end{eqnarray}
From this, an alternative form of $\Psi_{2}(t)$ is obtained as follows,
%-----------------------------------------------------------------------------
\begin{eqnarray}
\Psi_{2}(t) & = & \int_{0}^{t} \xi(x)\,dx
= 2\lambda \sum_{n = 1}^{\infty}\sum_{z = 1}^{n}{n \choose z}
\frac{p^{n-z}(1-p)^{z}}{\beta} \times \nonumber\\
& & \left\{\beta(t-nT) - \sum_{m=0}^{z-1}G[\beta(t-nT),m]\right\}
u(t-nT).\nonumber\\
\label{Psi2FormB}
\end{eqnarray}
Comparing the two different forms of $\Psi_{2}(t)$ shown in (\ref{Psi2})
and (\ref{Psi2FormB}) we easily obtain the following identity
\begin{equation}
\sum_{m=1}^{z} G(x,m) = x\left[1-G(x,z)\right] + z G(x,z+1) \qquad z = 1, 2,
3, \dots.
\label{identity}
\end{equation}
To the best of authors' knowledge the above identity has never been
published before.
\end{document}