Fluid Approximations for 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.