Multiscale queuing analysis, sampling theory, and network probing

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.