Papers Available on the Web

**
Internet Traffic Tends Toward Poisson and Independent as the
Load Increases
**

Jin Cao, William S. Cleveland, Dong Lin, and Don X. Sun

[compressed postscript] [pdf]

**
Internet Traffic: Statistical Multiplexing Gains
**
* DIMACS Workshop on Internet and WWW Measurement, Mapping and
Modeling, 2002 *

Jin Cao,
William S. Cleveland,
Dong Lin,
and Don X. Sun

** Abstract **
This note describes recent results on the effect
of statistical multiplexing on the long-range dependence (LRD) of Internet
packet traffic. Details and bibliographies may be found in
a series of papers at
http://cm.bell-labs.com/stat/InternetTraffic/webpapers.html.
Let a(j), for j = 1, 2, ... be the arrival times of packets on an
Internet link, let t(j) = a(j+1) - a(j) be the inter-arrival times, and let
q(j) be the packet sizes. Suppose we divide time up into equal-length,
consecutive intervals. Let p(i) be the packet counts in interval i.
The t(j) and q(j) are studied as time series in j, and the p(i) as
a time series in i.
The packet traffic on a link is the result of the
statistical multiplexing of packets from different active
connections. Let c be the mean number of active connections over
an interval of time during which link usage is stationary.
c serves as a measure of the magnitude of statistical multiplexing over the
interval. This note addresses the effect of an increasing
c on the LRD of the three traffic variables t(j), q(j), and p(i).
Results are based on the following: (1) the mathematical
theory of marked point processes; (2) empirical study of
live packet traces from 15 interfaces whose 5-min average traffic rates range
from about 2 kbps to 250 mbps; (3) empirical study of synthetic packet
traces from network simulation with NS;
(4) simple statistical models, FSD models and FSD-MA(1) models,
for the traffic variables.

[postscript]
[pdf]

**
S-Net: A Software System for Analyzing Packet Header Databases,
**
* Proc. Passive and Active Measurement, 34-44, 2002 *

Jin Cao,
William S. Cleveland,
and Don X. Sun

** Abstract **

S-Net is a software system designed for analyzing large databases of
Internet packet headers. S-Net runs on Unix, and analysis is carried out
using the S language for visualization and data analysis. There are three
goals in its design: (1) to allow, despite the large size of databases,
comprehensive analysis --- detailed analysis down to the level of
individual observations, together with analysis by summaries of behavior
that aggregate many observations; (2) to provide an extensible environment
so that analysts can readily tailor methods to the specific objectives
of their analyses; and (3) to provide an implementation based on public
domain software, making S-Net readily accessible to network researchers.
S-Net is available at http://cm.bell-labs.com/stat/InternetTraffic/S-Net.

[compressed postscript]
[pdf]

**
The Effect of Statistical Multiplexing on the
Long Range Dependence of Internet Packet Traffic,
**
* Bell Labs Tech Report, 2002 *

Jin Cao,
William S. Cleveland,
Dong Lin,
and Don X. Sun

** Abstract **
As the number of active connections (NAC) on an Internet link increases,
the long-range dependence of packet traffic changes due to increased
statistical multiplexing of packets from different connections.
Four packet traffic variables are studied as time series --- inter-arrival
times, sizes, packet counts in 100 ms intervals, and byte counts in
100 ms intervals.
Results are based on the following: (1) the mathematical
theory of marked point processes; (2) empirical study of 2526 packet traces,
5 min or 90 sec in duration, from 6 Internet monitors measuring
15 interfaces ranging from 100 mbps to 622 mbps;
(3) simple statistical models for the traffic variables;
and (4) network simulation with NS.
All variables have components of
long-range dependence at all levels of the NAC. But the variances of
the long-range dependent components of the sizes and of
the inter-arrivals decrease to zero as the NAC increases; the sizes tend
toward independent, and the inter-arrivals tend toward independent or
very short range dependent. These changes in the sizes and inter-arrivals
are not arrested by the increased upstream queueing that eventually
occurs as the NAC increases. The long-range dependence of the count variables
does not change with the NAC, but their standard deviations relative
to the means decrease like one over the square root of the NAC,
making the counts smooth relative to the mean.
Theory suggests that once the NAC is large enough,
increased upstream queueing should alter these properties of the counts,
but in the empirical study and in the simulation study the NAC was not large
enough to observe an alteration for 100 ms counts.
The change in the long-range dependence of the sizes and
inter-arrivals does not contradict the constancy of the long-range dependence
of the counts because the summation operations that
produce counts from the arrivals and sizes act on an increasing number of
packets as the NAC increases.

[compressed postscript]
[pdf]
[extended abstract: postscript]
[extended abstract: pdf]

**
A Poisson Limit for Buffer Overflow Probabilities
**
* Proc. INFOCOMM, 2002, to appear *

Jin Cao
and
Kavita Ramanan,

** Abstract **
A key criterion in the design of high-speed networks is the
probability that the buffer content exceeds a given threshold. We
consider n independent identical traffic sources modelled as point
processes, which are fed into a link with speed proportional to n.
Under fairly general assumptions on the input processes we show that
the steady state probability of the buffer content exceeding a
threshold b > 0 tends to the corresponding probability assuming
Poisson input processes. We verify the assumptions for a large class
of long-range dependent sources commonly used to model data traffic.
Our results show that with superposition, significant multiplexing
gains can be achieved for even smaller buffers than suggested by
previous results, which consider O(n) buffer size. Moreover,
simulations show that for realistic values of the exceedance
probability and moderate utilisations, convergence to the Poisson
limit takes place at reasonable values of the number of sources
superposed. This is particularly relevant for high-speed networks in
which the cost of high-speed memory is significant.

[postscript]
[pdf]

**
On the Nonstationarity of Internet Traffic,
**
* Proc. ACM SIGMETRICS `01, 102-112, 2001 *

Jin Cao,
William S. Cleveland,
Dong Lin,
and Don X. Sun

** Abstract **
Traffic variables on an uncongested Internet wire exhibit a pervasive
nonstationarity. As r, the TCP connection rate, changes, marginal
distributions and long range dependence change. As r increases (1)
packet and connection arrival processes tend toward Poisson; (2) time
series of packet sizes, round-trip times, and transferred file sizes
tend toward independence. Extensive empirical study of packet traces
demonstrates and elucidates the nonstationarity in two ways: (1) as r
changes, the parameters of comprehensive statistical models fitted to
traffic variables change; (2) as r changes, queueing characteristics
of the packet traces change. The cause of the nonstationarity is
superposition: the intermingling of sequences of connections between
different source-destination pairs, and the intermingling of sequences
of packets from different connections. Nonstationarity needs to be added
to long-range dependence and heavy-tailed marginal distributions as one
of the fundamental characteristics of Internet traffic.

[compressed postscript]
[pdf]

**
IP Packet Generation: Statistical Models for TCP
Start Times Based on Connection-Rate Superposition,
**
* Proc. ACM SIGMETRICS `00, 166-177, 2000*

William S. Cleveland,
Dong Lin,
and Don X. Sun

** Abstract **
TCP start times for HTTP are nonstationary. The nonstationarity occurs
because the start times on a link, a point process, are a superposition
of source traffic point processes, and the statistics of superposition
changes as the number of superposed processes changes. The start time
rate is a measure of the number of traffic sources. The univariate
distribution of the inter-arrival times is approximately Weibull,
and as the rate increases, the Weibull shape parameter goes to 1, an
exponential distribution. The autocorrelation of the log inter-arrival
times is described by a simple, two-parameter process: white noise plus a
long-range persistent time series. As the rate increases, the variance of
the persistent series tends to zero, so the log times tend to white noise.
A parsimonious statistical model for log inter-arrivals accounts for
the autocorrelation, the Weibull distribution, and the nonstationarity
in the two with the rate. The model, whose purpose is to provide
stochastic input to a network simulator, has the desirable property
that the superposition point process is generated as a single stream.
The parameters of the model are functions of the rate, so to generate
start times, only the rate is specified. As the rate increases, the model
tends to a Poisson process. These results arise from theoretical and
empirical study based on the concept of connection-rate superposition.
The theory is the mathematics of superposed point processes, and the
empiricism is an analysis of 23 million TCP connections organized into
10704 blocks of approximately 15 minutes each.

[compressed postscript]
[pdf]

**
Internet Traffic Data,
**
* Journal of the American Statistical Association, 95, 979-985, 2000.
Reprinted in Statistics in the 21st Century, edited by
A. E. Raftery, M. A. Tanner, and M. T. Wells, Chapman & Hall/CRC,
New York, 2002.*

William S. Cleveland
and Don X. Sun.

** Abstract **
Internet engineering and management depend on an understanding of the
characteristics of network traffic. Statistical models are needed
that can generate traffic that mimics closely the observed behavior on
live Internet wires. Models can be used on their own for some tasks
and combined with network simulators for others. But the challenge
of model development is immense. Internet traffic data are ferocious.
Their statistical properties are complex, databases are very large,
Internet network topology is vast, and the engineering mechanism
is intricate and introduces feedback into the traffic.
Packet header collection and organization of the headers into
connection flows yields data rich in information about
traffic characteristics and serves as
an excellent framework for modeling. Many existing statistical tools
and models --- especially those for time series, point processes,
and marked point process --- can be used to describe and model
the statistical characteristics, taking into account the structure
of the Internet, but new tools and models are needed.

[compressed postscript]
[pdf]

**
A Scalable Method for Estimating Network Traffic Matrices from Link Counts,
**
* Bell Labs Tech Report, 2001 *

Jin Cao,
D. Davis,
Scott Vander Wiel
Bin Yu, and Zhengyuan Zhu.

** Abstract **
Traffic matrices are extremely useful for network configuration,
management, engineering, and pricing. Direct measurement is, however,
expensive in general and impossible in some cases. This paper
proposes a scalable algorithm for statistically estimating a traffic
matrix from the readily available link counts. It relies on a
divide-and-conquer strategy to lower the computational cost without
losing estimation accuracy. The proposed algorithm is tested on a
real network with 18 nodes. The estimates are comparable to the
direct estimates but require dramatically less computation.

[postscript]

**
Time-Varying Network Tomography: Router Link Data,
**
* Journal of the American Statistical Association, 95,
1063-1075, 2000 *

Jin Cao,
D. Davis,
Scott Vander Wiel
and Bin Yu.

** Abstract **
The origin-destination (OD) traffic matrix of a computer network is
useful for solving problems in design, routing, configuration
debugging, monitoring, and pricing. Directly measuring this matrix is
not usually feasible but less informative link measurements are easy
to obtain.
This work studies the inference of OD byte counts from link byte
counts measured at router interfaces under a fixed routing scheme. A
basic model of the OD counts assumes that they are independent normal
over OD pairs and iid~over successive measurement periods. The normal
means and variances are functionally related through a power law. We
deal with the time-varying nature of the counts by fitting the basic
iid~model locally using a moving data window. Identifiability of the
model is proved for router link data and maximum likelihood is used
for parameter estimation. The OD counts are estimated by their
conditional expectations given the link counts and estimated
parameters. OD estimates are forced to be positive and to harmonize
with the link count measurements and the routing scheme. Finally, ML
estimation is improved by using an adaptive prior.
Proposed methods are applied to two simple networks at Lucent
Technologies and found to perform well. Furthermore, the estimates
are validated in a single-router network for which direct measurements
of origin-destination counts are available through special software.

[postscript]

**
Broadcast Audience Estimation,
**
* Proceedings of IEEE INFOCOM `00, 952-960, 2000 *

Chuanhai Liu,
and
Jorg Nonnenmacher

** Abstract **
We investigate the estimation of the size of a broadcast audience. We
give the Maximum Likelihood (ML) estimators for different scenarios. Using
Poisson approximation, we obtain upper and lower bounds for the audience
size. The ML estimators are obtained in closed-form, so are the bounds. We
treat the problem of a malfunctioning feedback flow control, where
the sender is overwhelmed by feedback messages. The ML estimate of
the audience size is obtained using the Expectation-Maximization (EM)
algorithm, even under such condition of censored values due to feedback
implosion. Quantifying the influence of feedback implosion the loss of
information for the audience estimation, we further investigated the
choice of the parameters in order to optimize estimation results. The
details are given the paper

[postscript]