Fluid Approximations for Quantitative Analysis

用于定量分析的流体近似

• 批准号: EP/F048726/1
• 负责人: Peter Harrison
• 金额: $ 53.54万
• 依托单位: Imperial College London
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2009
• 资助国家: 英国
• 起止时间: 2009 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FF048726%2F1
• 关键词: Fluid; Approximations; Quantitative; Analysis

Quantitative models are vital for the design of efficient systems in ICT, communication networks, sensor networks and other logistical areas such as business processes, biochemical systems and healthcare resource allocation or scheduling. However, models specified at a high level of description are often inefficient in terms of their mathematical solutions. Conversely, models which can be solved efficiently are often small, contrived and/or very problem specific. In many systems with very large numbers of components, it is often preferable to aggregate many entities of the same type into a single quantity, leading to a mathematically more tractable, continuous (real number) state model, cf. large numbers of gas molecules represented by a volume. The resulting so-called 'fluid methods' have been studied for many years, for example in physics, biology, chemistry and financial modelling.More recently, similar fluid methods have been used in stochastic models of performance. For example, fluid approximations exist for conventional queueing networks where the (integer) queue populations are replaced by a continuous fluid level and where discrete 'customer' movements are approximated by a continuous fluid flow. Similar fluid approximations have also been introduced in other stochastic modelling formalisms, for example Stochastic Petri Nets (SPNs) and Stochastic Process Algebras (SPAs). The difficulty with fluid models in general is finding exact, or good approximate, analytical solutions for useful model specifications. In the absence of analytical solutions, or efficient numerical solutions, one has to resort to simulation, which is notoriously inefficient for large problems, even when a fluid is used to approximate large numbers of otherwise discrete customers.Current fluid SPA models lead to deterministic systems of coupled differential equations in the time variable that are solveable by conventional numerical solution methods. However, the equations are defined solely by deterministic parameters (e.g. constant arrival and processing rates) and so their relevance lies in transient properties, equilibrium solutions (when they exist) also being deterministic. Their generalisation to probabilistically varying inputs and service times requires much more complex analysis, involving first- or second-order partial differential equations, which only rarely can be solved exactly. In the context of fluid queueing networks, the single fluid queue with Markovian on/off processes has been studied in some depth and results exist under quite general assumptions about the input processes. However, even very simple networks of queues have intractably complex solutions, and non-trivial networks are usually analysed by some form of fluid flow simulation. In traditional discrete-state models, solution methods for large systems have exploited compositional, usually approximate, approaches as they constitute the only way to find numerically tractable solutions. This typically involves making simplifying assumptions or using a hierarchical methodology such as the layered queueing network (LQN) paradigm.The central idea that underpins this proposal is to seek hierarchical approaches in the analysis of fluid systems, analogous to those that are well developed in traditional discrete-state models. The aim is to develop efficient solution methods, both exact and approximate, for a much broader range of fluid models than can be handled at present. The proposed work has significant theoretical value in its own right, but also has enormous practical potential as it opens up the possibility of solving large-scale fluid models, without having to resort to much less efficient solution methods based on simulation. Potential applications range from the analysis and optimisation of internet communication systems and storage area networks (SANs) to the study of systems involving 'real' fluids such as pumping systems and river networks.

定量模型对于ICT、通信网络、传感器网络和其他物流领域（如业务流程、生化系统和医疗资源分配或调度）的高效系统设计至关重要。然而，在高层次的描述指定的模型往往是低效的，在他们的数学解决方案。相反，可以有效解决的模型通常很小，人为的和/或非常具体的问题。在许多具有非常大数量的组件的系统中，通常优选的是将相同类型的许多实体聚合成单个量，从而导致数学上更易处理的连续（真实的数）状态模型，参见。用体积表示的大量气体分子。由此产生的所谓的“流体方法”已经被研究了很多年，例如在物理学，生物学，化学和金融建模中。最近，类似的流体方法已被用于随机性能模型。例如，流体近似存在于传统的排队网络中，其中（整数）队列人口被连续的流体水平所取代，并且其中离散的“客户”移动被连续的流体流所近似。类似的流体近似也被引入到其他随机建模形式主义中，例如随机Petri网（SPN）和随机过程代数（SPA）。一般来说，流体模型的困难在于为有用的模型规范找到精确的或良好的近似的分析解。在没有解析解或有效的数值解的情况下，人们不得不求助于模拟，这对于大型问题是出了名的低效，即使当流体被用来近似大量的其他离散customers.Current流体SPA模型导致在时间变量中的耦合微分方程的确定性系统可通过常规数值解方法求解。然而，方程仅由确定性参数（例如恒定到达和处理速率）定义，因此它们的相关性在于瞬态特性，平衡解（当它们存在时）也是确定性的。他们的概括概率不同的输入和服务时间需要更复杂的分析，涉及一阶或二阶偏微分方程，很少可以精确求解。在流体排队网络的背景下，对具有马尔可夫开/关过程的单流体排队系统进行了深入的研究，并在对输入过程的一般假设下得到了相应的结果.然而，即使是非常简单的排队网络也有非常复杂的解决方案，并且通常通过某种形式的流体流动模拟来分析非平凡网络。在传统的离散状态模型中，大型系统的求解方法利用了组合方法，通常是近似方法，因为它们是找到数值上易于处理的解决方案的唯一途径。这通常涉及简化假设或使用分层方法，如分层嵌套网络（LQN）paradigament.The中心思想，支持这一建议是寻求分层的方法在流体系统的分析，类似于那些在传统的离散状态模型中得到很好的发展。我们的目的是开发有效的解决方案的方法，精确和近似，更广泛的流体模型比目前可以处理。所提出的工作本身具有重要的理论价值，但也具有巨大的实际潜力，因为它开辟了解决大规模流体模型的可能性，而不必求助于基于模拟的效率低得多的求解方法。潜在的应用范围从互联网通信系统和存储区域网络（SAN）的分析和优化到涉及“真实的”流体的系统（如泵送系统和河流网络）的研究。

项目成果

Busy periods in fluid queues with multiple emptying input states

具有多个清空输入状态的流体队列的繁忙期

• DOI: 10.1239/jap/1276784904
• 发表时间: 2016
• 期刊: Journal of Applied Probability
• 影响因子: 1
• 作者: Field A

Response time distribution of flash memory accesses

闪存访问的响应时间分布

• DOI: 10.1016/j.peva.2009.10.003
• 发表时间: 2010
• 期刊: Performance Evaluation
• 影响因子: 2.2
• 作者: Harrison P

Fluid Queue Models of Battery Life

• DOI: 10.1109/mascots.2011.61
• 发表时间: 2011-07
• 期刊: 2011 IEEE 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems
• 作者: Gareth L. Jones;P. Harrison;U. Harder;T. Field

Blending randomness in closed queueing network models

在封闭排队网络模型中混合随机性

• DOI: 10.1016/j.peva.2014.09.001
• 发表时间: 2014
• 期刊: Performance Evaluation
• 影响因子: 2.2
• 作者: Casale G

Storage workload modelling by hidden Markov models: Application to Flash memory

通过隐马尔可夫模型进行存储工作负载建模：在闪存中的应用

• DOI: 10.1016/j.peva.2011.07.022
• 发表时间: 2012
• 期刊: Performance Evaluation
• 影响因子: 2.2
• 作者: Harrison P