Rice University Student Theses supported by DOE SciDAC INCITE Project

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

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, probing, and sampling of network traffic, Phd Thesis, expected May 2005
  Proposal Abstract: The growth of computer networks has far outstripped that of network measurement and modeling tools crucial for achieving good performance. We propose research for developing such tools that have a wide range of applicability addressing single router, aggregate path, and per-hop path performance issues.
  The four main research thrust areas are traffic analysis and modeling, queuing theory, active probing for available bandwidth, and active probing to identify performance degrading ``hotspots'' in the network. The traffic analysis reveals the burstiness of traffic which the queuing theory translates into performance metrics like router queuing delays. These aid the engineer in making informed provisioning decisions. The active probing schemes for available bandwidth give network-aware applications vital information for making efficient use of resources. The edge-based hotspot detection algorithms give the scientific community a deeper insight into the working of the Internet and suggest remedial measures for improving performance. Most of the tools are set in a multiscale framework which is intimately related to the multi-layer network protocol hierarchy and is ideal for modeling and studying the burstiness of traffic. We have obtained encouraging experimental results that confirm the utility of the queuing and available bandwidth tools and are confident of the success of the hotspot detection tools.

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
  

Aleksandar Kuzmanovic (Homepage) 

• Edge-Based Inference, Control, and DoS Resilience for the Internet, Phd Thesis, August 2004
  Abstract: Realizing new services on the Internet ultimately requires edge-based solutions for both deployability and scalability. Each such solution has two fundamental aspects. The first is the ability to accurately infer critical network parameters and processes such as Quality of Service (QoS) mechanisms, end-to-end available bandwidth, or the existence of a Denial of Service (DoS) activity; and the second is the ability to effectively utilize this knowledge to build endpoint services. This thesis presents the design, implementation, and evaluation of a series of edge-based algorithms and protocols for efficient inference, control, and DoS resilience of the Internet from its endpoints. The proposed solutions together form a new foundation for a robust quality-of-service communication via a scalable edge-based architecture where the novel functionality is added strictly at either edge routers or end hosts. In particular, this thesis develops techniques for multi-class service inference, active probing for available bandwidth, and end-point-based protection against DoS attacks.