Research in Large Deviations and Applications to Queueing Networks

大偏差及其在排队网络中的应用研究

• 批准号: 9700852
• 负责人: Richard Ellis
• 金额: $ 8.25万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-15 至 2000-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9700852&HistoricalAwards=false
• 关键词: Research; Large; Deviations; Applications; Queueing

9700852 Ellis This research will focus on two broad areas: (1) a weak convergence approach to the theory of large deviations and (2) large deviations for jump Markov processes and applications to queueing networks. In area (1) the research is based in part on a new book written jointly with Paul Dupuis. It consists of the following: (a) deriving representation formulas for new classes of processes, including jump Markov processes; (b) proving the Laplace principle for diffusions and other processes having discontinuous statistics with various geometries; (c) proving the Laplace principle for a random walk model with state- dependent noise; (d) proving the Laplace principle for empirical measures of Markov chains and related processes, including measure-valued processes with state dependencies; (e) generalizing a new formula on the Legendre-Fenchel transform of compositions of convex functions. Research in area (2) consists of the following: (a) using a new representation formula for large deviation probabilities together with weak convergence methods to obtain an explicit formula for the rate function for a number of queueing models of interest; (b) extending a recent paper on the large deviation analysis of general queueing systems to other queueing models, including state-dependent queues; (c) evaluating the exact large deviation rates and determining the overflow paths corresponding to certain overflow events in a number of queueing networks. This research program in large deviations is motivated by applications to queueing networks, which are of fundamental importance in communication and high performance computing. The work of the Principal Investigator over the past few years, which culminated in a number of important papers and a research-level book, develops a set of new and powerful techniques for studying the behavior of such networks. For example, a critical problem in the design of high speed networking technologies is to size the buffe rs at communications switches within these networks so that certain overflow probabilities are suitably small. Another critical problem in the design of very large multiprocessor systems is to estimate the probability that the system will fail in some time interval. This research will be adapted to studying these and related problems.

9700852 Ellis 这项研究将集中在两个广泛的领域：（1）大偏差理论的弱收敛方法和（2）跳跃马尔可夫过程的大偏差及其在排队网络中的应用。在领域 (1) 中，该研究部分基于与 Paul Dupuis 联合撰写的一本新书。它由以下部分组成： (a) 导出新类别过程的表示公式，包括跳跃马尔可夫过程； (b) 证明具有各种几何形状的不连续统计的扩散和其他过程的拉普拉斯原理； (c) 证明具有状态相关噪声的随机游走模型的拉普拉斯原理； (d) 证明马尔可夫链和相关过程的经验测度的拉普拉斯原理，包括具有状态依赖性的测值过程； (e) 推广凸函数组合的勒让德-芬切尔变换的新公式。 领域（2）的研究包括以下内容：（a）使用新的大偏差概率表示公式以及弱收敛方法来获得多个感兴趣的排队模型的速率函数的显式公式； (b) 将最近一篇关于一般排队系统大偏差分析的论文扩展到其他排队模型，包括状态相关队列； (c)评估精确的大偏差率并确定与多个排队网络中的某些溢出事件相对应的溢出路径。 这项大偏差研究计划的动机是排队网络的应用，排队网络在通信和高性能计算中至关重要。 首席研究员在过去几年的工作最终发表了许多重要论文和一本研究级书籍，开发了一套用于研究此类网络行为的强大的新技术。例如，高速网络技术设计中的一个关键问题是调整这些网络内通信交换机处的缓冲区大小，以使某些溢出概率适当小。超大型多处理器系统设计中的另一个关键问题是估计系统在某个时间间隔内发生故障的概率。本研究将适用于研究这些及相关问题。