\documentclass[12pt]{article}
\renewcommand{\today}{}
\setlength{\textwidth}{6.3in}
\setlength{\oddsidemargin}{.20in}
\begin{document}
\begin{center}
\noindent{\bf \Huge 
Empirical Modeling and Data Mining Network Traffic Data
}\\
~\\
\Large March 16, 2004\\
\vspace{.5in}
{\it \bf \Large \underline {\sf Principle Investigators}}\\
Charles Hagwood (hagwood@nist.gov)\\
Hung-kung Liu (liu@nist.gov)
\\ Les Cottrell (cottrell@SLAC.Stanford.EDU)
\end{center}
\underline{\hspace{6.2in}}
\section*{Abstract}

Massive amounts of data exist to provide feedback on traffic 
performance in high performance networks.  Feedback for traffic 
networks consists of transmission statistics such as roundtrip delay, 
traceroute data, packet losses, connectivity, reachability and throughput, all collected at various 
time scales.  Many organizations collect data and monitor network performance.  Two prominent projects 
are PingER and NLANR. PingER,  partially funded by DOE and NLANR by NSF began collecting data in 1995. 
They have been successful in providing both visual and analytic tools to monitor  network traffic.  
One shortcoming of  previous analysis  is that  performance measures are analyzed one variable at a 
time, e.g. roundtrip delay, packet losses. Many hidden correlations and patterns will not be found 
taking one variable at a time.  In this proposal PingER data  will be analyzed.  First,  with the 
help of SLAC, the PingER data is organized into a  matrix format from which data mining algorithms 
can be applied. With the data in the correct format, data mining algorithms will be applied to search 
for hidden patterns and correlations in the data.   Second,  a more elaborate model for network 
traffic will be built.  Based on historical/training data, an empirical model to characterize 
the ``normal" network behavior is planned. We might form $n$ vectors where each vector contains 
weekly roundtrip delay data from a fixed host to a destination. Then we will use principle 
component analysis to determine if these vectors can be explained by a smaller number, say $k$, 
of these weekly events or linearly combinations of them. We take these $k$ vectors as our empirical 
model. We will then fit future observations to this constructed empirical model to detect any 
``abnormal" network behavior.

\section*{Statement of the work plan}

NIST principle investigators propose to analyze historical data collected by the  PingER project. 
We are interested in detecting hidden patterns and correlations in network traffic data.  
Our idea is to build, based on historical data, an empirical model to characterize  ``normal" 
network behavior.  For example, we might form $n$ vectors where each vector contains weekly 
round trip delay data from a fixed host to a destination. Then we will use principal component 
analysis to see whether these vectors can be explained by a smaller number, say $k$, of these 
weekly vectors or linearly combinations of them. We take these $k$ vectors as our empirical 
model. We will then fit future (whole week or partial week) observations to this constructed 
empirical model to detect any ``abnormal" network behavior.

In addition to the data mining work of the previous paragraph, NIST intends to apply data 
mining to a conditioned subset of the PingER traffic data. Technically, data mining is 
the process of finding correlations or patterns among dozens of fields in large 
relational databases. In essence, network traffic data is not much different from 
say, Walmart customer sales traffic data.  For each customer transaction, Wal-mart 
records the date/time of sale,  amount of transaction, product id, store id, quantity 
id, etc.  Walmart has used data mining to understand its customer base.  Similarly, we 
plan to organize the eight years or so of PingER data into a database so that data mining 
can be performed. We plan to use principal component analysis, also known as singular 
value decomposition as our data mining technique, as well as other data mining algorithms.   

SLAC will work with NIST to provide access to data and information about the data to 
enable the analysis. SLAC will help organize the data into a format favorable for 
data mining.  SLAC will continue to provide long term archival storage for the data. 
SLAC will document and provide detailed information on the PingER measurements. This 
will include auxiliary information relating to the quality of the measurements including 
filters, idiosyncracies, effects of aggregations and sampling, information on 
distributions and the effects on medians and averages etc.

SLAC will provide navigateable anontated indexes of the available data. The annotation 
will include information on when collected, where stored, access policies, formats, 
compression and known features and problems.

SLAC will, on demand, disemminate data as selected by the requester. Based on these 
demands SLAC will develop tools to make multi-faceted subsets of the data available 
in machine readable form in common formats without human intervention. SLAC will provide 
mapping of data to tools that read and write the data.

Finally, SLAC will integrate the NIST techniques into the PingER analysis and reporting.

\section*{Technical details}
There are many well developed commerical tools for data mining.  S-plus has a data 
mining tool kit, that we plan to use, that is more than adequate for our data mining needs.

Principal component analysis (PCA) is a mathematical procedure that 
transforms a number of (possibly) correlated variables into a (smaller) 
number of uncorrelated variables called principal components. The first 
principal component accounts for as much of the variability in the data 
as possible, and each succeeding component accounts for as much of the 
remaining variability as possible.
If a large data set can be represented as physically meaningful vectors,
PCA is a useful tool for finding structures  large data
sets.

For a given week, let $y$ denote the weekly round trip delay data, i.e.,
the $m-$dimensional vector ($m=7\times 48$ ) whose components are the
average round trip delays from a fixed host to a destination.
The behavior of the weekly round trip delays often depends only on a small 
number ($\ll m$) of independent variables. By using a Taylor expansion, we assume the model
\begin{equation}\label{1.1}
y= \mu + \chi \beta+ X \gamma+ \varepsilon.
\end{equation}
Here $\beta$ and $\gamma$ are, respectively,  $k$ and $\ell$ dimensional
unknown column vectors.  Also the $m\times l$ matrix $\chi$ represents the part
of the design that is unknown,
and the $m\times l$ matrix $X$ represents the part of the
design that is known.  If the design is totally unknown, we have $l = 0$.
Model (\ref{1.1}) is therefore called the 
{\em empirical} linear model since part
of the design matrix $\chi$ can only be determined empirically.
To make $\chi$ and $\beta$ identifiable, we first write $\chi$ as
\begin{equation} 
\chi=(S, S_0) \left( \begin{array}{c}
D \\ 0   
\end{array} \right)
V=SDV   \label{lab21}
\end{equation}
by the singular value decomposition. Here $(S,S_0)$ and $V$ are
orthogonal square matrices of sizes $m$ and $k$ respectively. It is
assumed that $S$ has size $m\times k$ and $k<m$. The matrix $D$ is a
diagonal matrix with positive diagonal elements
$d_i$ which decrease in $i$.  Since we shall assume that the
$d_i$'s are different, take  $d_1 >d_2 \cdots > d_k$.  
The quantity 0 represents the zero matrix of size $(m-k)\times k$.
Also we shall follow the rule that in doing a singular value
decomposition:
\begin{equation} \label{lab22}
\mbox{the first non-zero element of each column in $(S,S_0)$ is positive.}
\end{equation}
This, together with the assumptions that the $d_i$'s are distinct, implies
that the columns of $S$ are uniquely determined.
Model (\ref{1.1}), after
substituting $\chi$ by (\ref{lab21}) and replacing $DV\beta$ by $\eta$, becomes
\begin{equation}
y= \mu+S\eta +X\gamma +\varepsilon, \label{lab28}.
\end{equation}

An empirical linear model provides a useful structure in modeling
network traffic data.
The question we want to address in this proposal is:
can ``abnormal" network behavior
be determined by a $t$--dimensional subvector $y_1$ of $y$?

If $S$ were known,
applying a traditional multivariate linear model, one can incorporate $y_1$
with the known design matrix to predict the rest of the elements.
Since $S$ is
unknown, it will be estimated by using a set of $y^i$'s, called the
historical/training data.
We can express the training data from the ``normal" network traffic as
\begin{equation}\label{1.3}
y^i= \mu + S \eta^i+ X \gamma^i+ \varepsilon^i, \quad i = 1,\ldots,n.
\end{equation}
Then the estimated model, together with
a $t$--dimensional subvector $y_1$ of $y$, may be used to estimate
the rest of the components $y_2$ of $y$.
% ELP vs HELP
 
What are the reasonable point predictors which allow us to do so?
How does one assess the prediction error?  
How does one determine that the observed network behavior is ``abnormal?
These are the central
questions that we will address in this proposal.  We tackle the problems
by constructing prediction sets,
confidence sets and Scheff\'e type (1959) simultaneous intervals.  

This is a
challenging problem involving several interesting and difficult
areas such
as estimation of dimensionality, variable selection, calibration and
prediction.  Another striking feature is that the model
could involve a design matrix that is totally unknown.
In fact, the special case of (\ref{lab28}) and (\ref{1.3}),
\begin{equation}
y = S\eta + \varepsilon,\mbox{ and}
     \label{1.2}
\end{equation}
\begin{equation}
y^i = S\eta^i + \varepsilon^i,
     \label{1.4}
\end{equation}
i.e., $\mu=0$ and $l=0$,
corresponds to the case when the design matrix is totally unknown.

\begin{thebibliography}{99}

\bibitem{}  Anderson, T. W. (1984), {\em An introduction to
   multivariate statistical analysis}, Second ed., Wiley
   Series in Probability and Mathematical Statistics.

    
\bibitem{} Stenbakken, G. N., Liu, H. K., and Hwang, J. T. (2004), 
    {\em Empirical modeling methods using partail data},
    IEEE Instrumentation and Measurement Society April 2004 issue of the
        I\&M Transactions.
 
\bibitem{} Hwang, J. T. and Liu, H. K. (1995), {\em Asymptotic
    theory for prediction through empirical linear models}, Spring
    Research Conference: 1994 Proceedings, 207--216.
 
\bibitem{} Scheff\'e, H. (1959), {\em The analysis of variance},
  John Wiley \& Sons, Inc., New York.
 
\end{thebibliography}


\section*{Business and Financial Information}
For the past several years the Statistical Engineering Division  has committed resources 
to study internet traffic modeling.  The Statistical Engineering Division and the 
Advanced Network Technologies Division at NIST have collaborated in support of  
an industrial consortia to  develop metrics and tools to measure the performance of 
Internet services.  The consortia include Cross Industry Working Team (XIWT) and 
the Internet Performance Metrics Working Group (IPPM-WG) of the Internet Engineering 
Task Force (IETF).  Through this proposal, we are seeking funding to support continued 
work in internet modeling using PingER data.  The estimated funding requirements are:\\

\begin{tabular}{ll}
 FY2004-2005: & Request 100K (NIST)\\
              & Request (75K) (SLAC)
\end{tabular}

\section*{About the investigators}

Charles Hagwood received his Ph.D in mathematics from the University of 
Michigan in 1979 under the direction of Michael Woodroofe in nonlinear 
renewal theory. After leaving Michigan he taught at Dartmouth College 
(1979-1981) and at the University of Virginia (1981-1987).  He spent 
the school year 1983-1984 in the Statistics Department at Stanford 
University.  Since 1987, he has been a member of the Statistical 
Engineering Division at the National Institute of Standards and Technology.\\


Dr.\ Hung-kung Liu is a statistician with 15 years experience consulting
on a wide variety of problems including
engineering, physical and biological sciences.
He is knowledgeable in various approaches
to statistical inference, design of experiments, and computer intensive methods
with experience in developing statistical methodology for special problems.
Dr.\ Liu joined the National Institute of Standards and Technology in 1991.
Before that he was a faculty member of the State University of New York
at Stony Brook since 1984 when he received his Ph.D. in statistics from
Cornell University.
\noindent Grant related publications and talks:\\

\noindent Hagwood, C., Carson, M.,  Estimating Delay Along the Internet Backbone-manuscript to be submitted.\\

\noindent Hagwood, C. Estimating Delay Along the Internet Backbone (talk)-Joint Statistical Meetings, August 3-7, 2003, San Franscico, CA.\\


\noindent Stenbakken, G. N., Liu, H. K., and Hwang, J. T. (2004),
    {\em Empirical modeling methods using partail data},
    IEEE Instrumentation and Measurement Society April 2004 issue of the
        I\&M Transactions.\\

\noindent Hwang, J. T. and Liu, H. K. (1995), {\em Asymptotic
    theory for prediction through empirical linear models}, Spring
    Research Conference: 1994 Proceedings, 207--216.





\end{document}
