Rice University Student Theses supported by DARPA NMS Program
- Alireza Keshavarz-Haddad
- Michael Rabbat
- Vinay Ribeiro
- Shriram Sarvotham
- Yolanda Tsang
- The Effect of traffic bursts in the network queue
(pdf), Master Thesis, April 2003
This thesis studies the effect of the traffic bursts in the queue.
Knowledge of the queueing behavior provides opportunity for
additional control and improved performance. Most existing work on
queueing today is based on Long-Range-Dependence (LRD) and
Self-similarity, two well-known properties of network traffic at
large scales. However, network traffic shows bursty behavior on
small scales which are not captured by traditional self-similar
models. We leverage a decomposition of traffic into two
components. The alpha component is the bursty part of the traffic
consisting of only few high bandwidth connections. The beta
component collects the residual traffic and is a Gaussian LRD
process. The alpha component is highly non-Gaussian and bursty. We
propose two models for the alpha component, a heavy-tailed
self-similar process and a high rate ON/OFF source. Our results
explain how size and type of bursts affect the queueing behavior.
Michael Rabbat (Homepage)
- Multiple Source Network Tomography (pdf), Master Thesis, May 2003
Abstract: Assessing and predicting internal network performance is of fundamental importance in problems ranging from routing optimization to anomaly
detection. The problem of estimating internal network structure and
link-level performance from end-to-end measurements is called network
tomography. This thesis investigates the general network tomography
problem involving multiple sources and receivers, building on existing
single source techniques. Using multiple sources potentially provides a
more accurate and refined characterization of the internal network. The
general network tomography problem is decomposed into a set of smaller
components, each involving just two sources and two receivers. A novel
measurement procedure is proposed which utilizes a packet arrival order
metric to classify two-source, two-receiver topologies according to their
associated model-order. Then a decision-theoretic framework is developed,
enabling the joint characterization of topology and internal performance.
A statistical test is designed which provides a quantification of the
tradeoff between network topology complexity and network performance
Vinay Ribeiro (Homepage)
- Multiscale queuing, sampling theory, and network probing (pdf), Phd Thesis, May 2005
Multiscale techniques model and analyze phenomena at multiple scales
in space or time. This thesis develops novel multiscale solutions for
problems in queuing theory, sampling theory, and network inference.
First, we study the tail probability of an infinite-buffer queue fed
with an arbitrary traffic source. The tail probability is a critical
quantity for the design of computer networks. We propose a multiscale
framework that uses traffic statistics at only a fixed finite set of
time scales and derive three approximations for the tail
probability. Theory and simulations strongly support the use of our
approximations in different networking applications. Second, we
design strategies to optimally sample a process in order to estimate
its global average. Our results have implications for Internet
measurement, sensor network design, environmental monitoring, etc. We
restrict our analysis to linear estimation of certain multiscale
stochastic processes --- independent innovations trees and covariance
trees. Our results demonstrate that the optimal solution depends
strongly on the correlation structure of the tree. We also present an
efficient water-filling solution for arbitrary independent
innovations trees. Third, we present two probing tools that estimate
the available bandwidth of network paths and locate links with scarce
bandwidth. These tools aid network operations and network-aware
applications such as grid computing. We use novel packet trains called
chirps that simultaneously probe the network at multiple bit-rates
which improves the efficiency of the tools. We validate the tools
through simulations and Internet experiments.
Shriram Sarvotham (Homepage)
- Analysis and Modeling of Bursty Long-Range-Dependent Network Traffic (pdf), Master Thesis, May 2001
Abstract: In this thesis, we study the cause and impact of burstiness in computer
A connection-level analysis of traffic at coarse time scales
(time scales greater than a round-trip-time)
reveals that a single connection dominates during the period of the burst.
The number of dominating connections that cause bursts is found to be
a small fraction of the total number of connections.
Removing the burst causing connections from the traffic
yields a trace whose marginal is close to a Gaussian.
This observation motivates a network traffic model
comprised of two components, namely the Gaussian part and the bursty part.
The Gaussian part of the traffic models the aggregate of majority of the
connections, whereas the bursty part models the behavior of
few dominant connections that transmit data at unusually high rates.
The Gaussian component imparts long-range-dependence (LRD) to the
traffic, whereas the bursty component gives rise to spikiness.
We argue that
heterogeneity in bottleneck link speeds gives rise to
burstiness, and heavy tailed connection
durations results in LRD.
We perform simulations in ns to validate the proposed model
and synthesize realistic traffic that is both non-Gaussian and LRD.
We demonstrate the impact of the bursty component in queueing behavior.
the bursty component constitutes a small fraction of the total traffic,
it significantly affects the queueing behavior, in particular at
large queue sizes.
Yolanda Tsang (Homepage)
- Loss Inference in Unicast Network Tomography (pdf), Master Thesis, May 2001
Abstract: Network tomography is a promising technique for characterizing the internal behavior of large-scale networks based solely on end-to-end measurements. Despite the efficiency of active probing in most network loss tomography methods, these measurements impose an additional burden on the network in terms of bandwidth and network resources. They can therefore cause the estimated performance parameters to differ substantially from losses suffered by existing TCP traffic flows. In this thesis, we propose a promising passive measurement framework based on the sampling of existing TCP flows. We demonstrate its performance using extensive ns-2 simulations. We observe accurate estimates of link losses (with 2% mean absolute error). We also describe the Expectation-Maximization (EM) algorithm in solving the Maximum Likelihood (ML) Estimates in terms of individual link loss rates as an incomplete data problem. Finally, we present a new method for simultaneously visualizing the network connectivity and the network performance parameters.
- Network Tomography, Phd expected, May 2005