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
Branching Program Lower Bounds
分支程序下界
- 批准号:
RGPIN-2019-06288 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Discovery Grants Program - Individual
Tighter error bounds for representation learning and lifelong learning
表征学习和终身学习的更严格的误差范围
- 批准号:
RGPIN-2018-03942 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Discovery Grants Program - Individual
AF: Small: New Techniques for Optimal Bounds on MCMC Algorithms
AF:小:MCMC 算法最优边界的新技术
- 批准号:
2147094 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Standard Grant
Lower bounds, meta-algorithms, and pseudorandomness
下界、元算法和伪随机性
- 批准号:
RGPIN-2019-05543 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Discovery Grants Program - Individual
Extremal Combinatorics Exact Bounds
极值组合精确界
- 批准号:
574168-2022 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
University Undergraduate Student Research Awards
Lower bounds on ranks of nontrivial toric vector bundles
非平凡环面向量丛的秩下界
- 批准号:
558713-2021 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Postgraduate Scholarships - Doctoral
Bringing upper and lower bounds closer in computational geometry
使计算几何中的上限和下限更加接近
- 批准号:
567959-2022 - 财政年份:2022
- 资助金额:
$ 30.34万 - 项目类别:
Postgraduate Scholarships - Doctoral