Multiscale queuing analysis, sampling theory, and network probing

Files in this item

Files Size Format View
3168133.PDF 46.07Mb application/pdf Thumbnail

Show full item record

Item Metadata

Title: Multiscale queuing analysis, sampling theory, and network probing
Author: Ribeiro, Vinay
Advisor: Baraniuk, Richard G.
Degree: Doctor of Philosophy thesis
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.
Citation: Ribeiro, Vinay. (2005) "Multiscale queuing analysis, sampling theory, and network probing." Doctoral Thesis, Rice University.
Date: 2005

This item appears in the following Collection(s)