Fluid Approximations for Quantitative Analysis

Lead Research Organisation: Imperial College London
Department Name: Dept of Computing

Abstract

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.

Publications

10 25 50
 
Description This grant ended some 4 years ago and it is difficult to remember the key findings that are not readily available in the papers included with this submission. However, in general they are as follows:

1. The primary result was applied-mathematical, detailed in the paper coauthored with Tony Field, the co-investigator, "BUSY PERIODS IN FLUID QUEUES WITH MULTIPLE EMPTYING INPUT STATES". This paper was a combined analytical-numerical method that enabled, for the first time, first-order fluid queues to be solved for their equilibrium behaviour (distribution of fluid level, response time distribution) when any number of its modulating states could have an output rate greater than its input rate. Such problems had previously been restricted to a single such state. The method facilitated the tractable numerical solution of significantly sized problems.

2. The rest of the project was mainly concerned with applying the new result in networks of interconnected fluid queues, representing various types of contention system, where the fluid represents large numbers of discrete items like packets or continuous quantities like battery charge or real fluid such as water. These results are also reported in the associated papers.

3. A particularly novel application that has led to significant new research and collaboration with, for example, Andrew Rice's team at the University of Cambridge, has been in the modelling and analysis of mobile device battery charging strategies. In fact our 2011 Mascots paper was the second-highest ranked at that conference. This result demonstrated when the use of a low-power mode can be useful in extending battery-life between charges.

4. Towards the end of the project, we obtained numerical results on power-saving by storing electrical power when there is an excess, for example using existing schemes whereby water is pumped uphill and used hydroelectrically at times of high demand.
Exploitation Route The results we obtained are applicable in modelling continuous resources like electricity or water as well as approximations to moderate-heavy loaded discrete systems. As noted above, we are already collaborating regarding mobile devices and have new work on mobile phone optimisation with respect to performance (e.g. user response time) and energy (mainly battery charge). This work will likely combine fluid methods with DPS (discriminatory processor sharing) queueing models.
Sectors Digital/Communication/Information Technologies (including Software),Education,Electronics,Energy,Environment

 
Description This grant finished many years ago, and I previously submitted my findings. Your website does not make it easy to view previous input, certainly not from the page where you say this should be done. I can therefore only refer you to the previous findings, trusting that they will be more accessible to you.
First Year Of Impact 2011
Sector Education
Impact Types Societal,Economic