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

存在重尾的情况下随机网络的渐近和界限

• 批准号: 0115034
• 负责人: Karl Sigman
• 金额: $ 30.34万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-15 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0115034&HistoricalAwards=false
• 关键词: Asymptotics; Bounds; Stochastic; Networks; Presence

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).

例如，在生产、制造和电信中使用的随机网络中，对于感兴趣的稳态量（如延迟、交货日期、停留时间、队列长度和工作量）的渐近性和界限，当组成概率分布是“轻尾”（例如，具有像指数尾一样衰减的尾巴）时，就可以很好地理解。基本的结果是渐近和界是指数的。这样的结果在实践中对感兴趣的量产生了一些非常好的近似。但从互联网（和其他领域）收集的数据支持“重尾”现象的存在（例如，尾比任何指数尾衰减得都慢；它们具有无限的矩生成函数）。在这里，我们提出了对复杂模型的渐近性和界的推导，例如具有反馈的排队网络（客户可以返回到已经访问过的节点）和一般路由（非马尔可夫），其中一个或多个组件分布（如服务时间）是重尾的（次指数的）。目的是得到可以在实践中使用的近似值和界限。我们也希望这样的研究能够对具有一般（依赖的，非i.i.d）输入的网络的稳定性产生新的见解/结果，并揭示具有远程依赖输入的随机流体模型与具有重尾服务的排队网络之间的联系。目前，互联网正在经历爆炸式的使用和增长，延迟（等待时间）可能是一个相当大的问题。例如，当拥塞严重时，服务器和桌面计算机之间下载（或上传）文档的等待时间，或者用户可以使用链接的等待时间可能会变得相当长。有证据表明，这种拥塞与传统电信系统（例如电话拥塞）中发现的拥塞完全不同，因为它涉及长随机周期/时间，称为“重尾”时间，不会迅速衰减。通过数学建模来研究这种拥塞是理解这种延迟以及如何控制它们的一个非常有用的方法。通过创建和研究表现出这种行为的随机（概率）模型（同时捕捉真实系统的相关复杂性），并通过模拟这些模型，提出的研究将导致更精确地测量拥塞的方法，帮助更好地理解它是如何发生的，以及如何控制它。这项研究最终将有助于各种相关技术的未来规划，例如制造和生产中的复杂系统，这些系统越来越多地涉及与互联网技术相关的组件（因此容易受到重尾的影响）。