Asymptotics and Bounds for Stochastic Networks in the Presence of Heavy Tails
存在重尾的情况下随机网络的渐近和界限
基本信息
- 批准号:0115034
- 负责人:
- 金额:$ 30.34万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Continuing Grant
- 财政年份:2001
- 资助国家:美国
- 起止时间:2001-08-15 至 2005-07-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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)输入的网络的稳定性产生新的见解/结果,并揭示具有远程依赖输入的随机流体模型与具有重尾服务的排队网络之间的联系。目前,互联网正在经历爆炸式的使用和增长,延迟(等待时间)可能是一个相当大的问题。例如,当拥塞严重时,服务器和桌面计算机之间下载(或上传)文档的等待时间,或者用户可以使用链接的等待时间可能会变得相当长。有证据表明,这种拥塞与传统电信系统(例如电话拥塞)中发现的拥塞完全不同,因为它涉及长随机周期/时间,称为“重尾”时间,不会迅速衰减。通过数学建模来研究这种拥塞是理解这种延迟以及如何控制它们的一个非常有用的方法。通过创建和研究表现出这种行为的随机(概率)模型(同时捕捉真实系统的相关复杂性),并通过模拟这些模型,提出的研究将导致更精确地测量拥塞的方法,帮助更好地理解它是如何发生的,以及如何控制它。这项研究最终将有助于各种相关技术的未来规划,例如制造和生产中的复杂系统,这些系统越来越多地涉及与互联网技术相关的组件(因此容易受到重尾的影响)。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Karl Sigman其他文献
Comparing backwards and forwards random walk maxima
- DOI:
10.1007/s11134-022-09815-1 - 发表时间:
2022-04-28 - 期刊:
- 影响因子:0.700
- 作者:
Karl Sigman - 通讯作者:
Karl Sigman
Stochastic Networks: Admission and Routing Using Penalty Functions
- DOI:
10.1023/b:ques.0000046578.47761.4c - 发表时间:
2004-11-01 - 期刊:
- 影响因子:0.700
- 作者:
Jan Cosyn;Karl Sigman - 通讯作者:
Karl Sigman
Exact simulation of the stationary distribution of the FIFO M/G/c queue: the general case for ρ<c
- DOI:
10.1007/s11134-011-9266-6 - 发表时间:
2011-11-09 - 期刊:
- 影响因子:0.700
- 作者:
Karl Sigman - 通讯作者:
Karl Sigman
Queues as Harris recurrent Markov chains
- DOI:
10.1007/bf01189048 - 发表时间:
1988-06-01 - 期刊:
- 影响因子:0.700
- 作者:
Karl Sigman - 通讯作者:
Karl Sigman
Light traffic for workload in queues
- DOI:
10.1007/bf01163865 - 发表时间:
1992-12-01 - 期刊:
- 影响因子:0.700
- 作者:
Karl Sigman - 通讯作者:
Karl Sigman
Karl Sigman的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Karl Sigman', 18)}}的其他基金
Risk and Duality in Multidimensional Stochastic Recursions
多维随机递归中的风险和对偶性
- 批准号:
9622657 - 财政年份:1996
- 资助金额:
$ 30.34万 - 项目类别:
Continuing Grant
NSF-CGP Science Fellowship Program: Fluid Flow Approximation in Open Networks
NSF-CGP 科学奖学金计划:开放网络中的流体流动近似
- 批准号:
9402505 - 财政年份:1994
- 资助金额:
$ 30.34万 - 项目类别:
Standard Grant
Japan (JSPS) Postdoctoral Program: Polling Models in Telecommunications and Manufacturing
日本(JSPS)博士后项目:电信和制造业中的民意调查模型
- 批准号:
9001558 - 财政年份:1990
- 资助金额:
$ 30.34万 - 项目类别:
Standard Grant
Presidential Young Investigator Award: Stability, Moments and Regenerative Simulation of Queueing Networks
总统青年研究员奖:排队网络的稳定性、矩和再生模拟
- 批准号:
8957825 - 财政年份:1989
- 资助金额:
$ 30.34万 - 项目类别:
Continuing Grant
相似海外基金
CAREER: Lower Bounds for Shallow Circuits
职业生涯:浅层电路的下限
- 批准号:
2338730 - 财政年份:2024
- 资助金额:
$ 30.34万 - 项目类别:
Continuing Grant
Complexity Lower Bounds from Expansion
扩展带来的复杂性下限
- 批准号:
23K16837 - 财政年份:2023
- 资助金额:
$ 30.34万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
Non-parametric estimation under covariate shift: From fundamental bounds to efficient algorithms
协变量平移下的非参数估计:从基本界限到高效算法
- 批准号:
2311072 - 财政年份:2023
- 资助金额:
$ 30.34万 - 项目类别:
Standard Grant
Tighter error bounds for representation learning and lifelong learning
表征学习和终身学习的更严格的误差范围
- 批准号:
RGPIN-2018-03942 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Discovery Grants Program - Individual
Branching Program Lower Bounds
分支程序下界
- 批准号:
RGPIN-2019-06288 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Discovery Grants Program - Individual
Lower bounds, meta-algorithms, and pseudorandomness
下界、元算法和伪随机性
- 批准号:
RGPIN-2019-05543 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Discovery Grants Program - Individual
Bringing upper and lower bounds closer in computational geometry
使计算几何中的上限和下限更加接近
- 批准号:
567959-2022 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Postgraduate Scholarships - Doctoral
Lower bounds on ranks of nontrivial toric vector bundles
非平凡环面向量丛的秩下界
- 批准号:
558713-2021 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Postgraduate Scholarships - Doctoral
Extremal Combinatorics Exact Bounds
极值组合精确界
- 批准号:
574168-2022 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
University Undergraduate Student Research Awards
AF: Small: New Techniques for Optimal Bounds on MCMC Algorithms
AF:小:MCMC 算法最优边界的新技术
- 批准号:
2147094 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Standard Grant