Asymptotics and Bounds for Stochastic Networks in the Presence of Heavy Tails

Asymptotics and bounds for steady-state quantities of interest (such as delays, delivery dates, sojourn times, queue lengths and workload) in stochastic networks used in production, manufacturing, and telecommunications for example, are fairly well understood when component probability distributions are ``light-tailed' (e.g., have tails that decay like exponential tails). The basic result is that the asymptotics and bounds are exponential. Such results have led to some very good approximations in practice for quantities of interest. But data gathered from the Internet (and other areas) supports the existence of ``heavy-tailed' phenomena (e.g., tails decay slower than any exponential tail; they have infinite moment-generating functions). Here, it is proposed to derive asymptotics and bounds for complex models such as queuing networks with feedback (customers can return back to a node already visited) and general routing (non-Markovian) in which one or more of the component distributions (such as service times) is heavy-tailed (subexponential). The purpose is to obtain approximations and bounds that can be used in practice. It is also hoped that such an investigation will yield new insight/results concerning stability of networks with general (dependent, non-i.i.d.) input, and shed new light on connections between stochastic fluid models with long-range dependent input and queueing networks with heavy-tailed service.

Currently the Internet is witnessing explosive use and growth, and delays (waiting times) can be a considerable problem. For example, the waiting time for documents to download (or upload) between servers and desktop computers, or for links to become available to a user can become of considerable length when congestion is high. Evidence suggests that this kind of congestion is quite different from that found in classical telecommunication systems (phone congestion for example), in that it involves long random periods/times, known as 'heavy-tailed' times, that do not decay rapidly. Studying this congestion by use of mathematical modeling is a very helpful way of understanding such delays and how to control them. By creating and studying stochastic (probabilistic) models that exhibit such behavior (while capturing the relevant complexity of the real system), and also by simulating such models, the proposed research will lead to ways of more precisely measuring the congestion, help better understand how it occurs, and how to control it. The research will ultimately help future planning of various related technologies such as complex systems in manufacturing and production that increasingly involve components linked to Internet technologies (and hence are susceptible to heavy tails).