**Rice University Student Theses supported by DARPA NMS Program **

- Alireza Keshavarz-Haddad
- Michael Rabbat
- Vinay Ribeiro
- Shriram Sarvotham
- Yolanda Tsang

**Alireza Keshavarz-Haddad **

- The Effect of traffic bursts in the network queue
(pdf), Master Thesis, April 2003

__Abstract:__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 estimation.

**Vinay Ribeiro (Homepage) **

- Multiscale queuing, sampling theory, and network probing (pdf), Phd Thesis, May 2005

__Abstract:__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 network traffic. 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. Although 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