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.）输入，并揭示了新的光与长程相关输入的随机流体模型和重尾服务的网络之间的连接。目前，互联网正在见证爆炸性的使用和增长，延迟（等待时间）可能是一个相当大的问题。例如，当拥塞严重时，在服务器和台式计算机之间下载（或上载）文档的等待时间，或者链接对用户可用的等待时间可能会变得相当长。有证据表明，这种拥塞与经典电信系统（例如电话拥塞）中发现的拥塞有很大不同，因为它涉及长的随机周期/时间，称为“重尾”时间，不会迅速衰减。通过数学建模来研究这种拥塞是理解这种延迟以及如何控制它们的一种非常有用的方法。通过创造和研究随机表现出这种行为的（概率）模型（同时捕获真实的系统的相关复杂性），并且还通过模拟这样的模型，所提出的研究将导致更精确地测量拥塞的方法，帮助更好地理解它是如何发生的，以及如何控制它。这项研究最终将有助于未来规划各种相关技术，如制造业中的复杂系统，生产越来越多地涉及与互联网技术相关的组件（因此容易受到重尾影响）。