Join-the-Shortest-Queue (JSQ) is the scheduling policy of choice for many network providers, cloud servers, and traffic management systems, where individual queues are served under the processor sharing (PS) queueing discipline. A numerical solution for the response time distribution in two parallel PS queues with JSQ scheduling is derived for the first time. Using the generating function method, two partial differential equations (PDEs) are obtained corresponding to conditional response times, where the conditioning is on a particular traced task joining the first or the second queue. These PDEs are functional equations that contain partial generating functions and their partial derivatives, and therefore cannot be solved by commonly used techniques. We are able to solve these PDEs numerically with good accuracy and perform the deconditioning with respect to the queue-length probabilities by evaluating a certain complex integral. Numerical results for the density and the first four moments compare well against regenerative simulation.

Join-the-Shortest-Queue (JSQ) is the scheduling policy of choice for many network providers, cloud servers, and traffic management systems, where individual queues are served under processor sharing (PS) queueing discipline. A numerical solution for the response time distribution in two parallel PS queues with JSQ scheduling is derived for the first time. Using the generating function method, two partial differential equations (PDEs) are obtained corresponding to conditional response times, where the conditioning is on a particular traced task joining the first or the second queue. These PDEs are functional equations that contain partial generating functions and their partial derivatives, and therefore cannot be solved by commonly used techniques. We are able to solve these PDEs numerically with good accuracy and perform the deconditioning with respect to the queue-length probabilities by evaluating a certain complex integral. Numerical results for the density and the first four moments compare well against regenerative simulation with 500,000 regeneration cycles.

Response time density is obtained in a tandem pair of Markovian queues with both batch arrivals and batch departures. The method uses conditional forward and reversed node sojourn times and derives the Laplace transform of the response time probability density function in the case that batch sizes are finite. The result is derived by a generating function method that takes into account that the path is not overtake-free in the sense that the tagged task being tracked is affected by later arrivals at the second queue. A novel aspect of the method is that a vector of generating functions is solved for, rather than a single scalar-valued function, which requires investigation of the singularities of a certain matrix. A recurrence formula is derived to obtain arbitrary moments of response time by differentiation of the Laplace transform at the origin, and these can be computed rapidly by iteration. Numerical results for the first four moments of response time are displayed for some sample networks that have product-form solutions for their equilibrium queue length probabilities, along with the densities themselves by numerical inversion of the Laplace transform. Corresponding approximations are also obtained for (non-product-form) pairs of “raw” batch-queues—with no special arrivals—and validated against regenerative simulation, which indicates good accuracy. The methods are appropriate for modeling bursty internet and cloud traffic and a possible role in energy-saving is considered.

Power modes can be used to save energy in electronic devices but a low power level typically degrades performance. This trade-off is addressed in the so-called EP-queue model, which is a queue depth dependent M/GI/1 queue augmented with power-down and power-up phases of operation. The ability to change service times by power settings allows us to leverage a Markov Decision Process (MDP), which approach we illustrate using a simple fully solar-powered case study with finite states representing levels of battery charge and solar intensity.

Cryptocurrency mining can be said to be the modern alchemy, involving as it does the transmutation of electricity into digital gold. The goal of mining is to guess the solution to a cryptographic puzzle, the difficulty of which is determined by the network, and thence to win the block reward and transaction fees. Because the return on solo mining has a very high variance, miners band together to create so-called mining pools. These aggregate the power of several individual miners, and, by distributing the accumulated rewards according to some scheme, ensure a more predictable return for participants.In this paper we formulate a model of the dynamics of a queue-based reward distribution scheme in a popular Ethereum mining pool and develop a corresponding simulation. We show that the underlying mechanism disadvantages miners with above-average hash rates. We then consider two-miner scenarios and show how large miners may perform attacks to increase their profits at the expense of other participants of the mining pool. The outcomes of our analysis show the queue-based reward scheme is vulnerable to manipulation in its current implementation.

Response time variability in software applications can severely degrade the quality of the user experience. To reduce this variability, request replication emerges as an effective solution by spawning multiple copies of each request and using the result of the first one to complete. Most previous studies have mainly focused on the mean latency for systems implementing replica cancellation, i.e., all replicas of a request are canceled once the first one finishes. Instead, we develop models to obtain the response-time distribution for systems where replica cancellation may be too expensive or infeasible to implement, as in “fast” systems, such as web services, or in legacy systems. Furthermore, we introduce a novel service model to explicitly consider correlation in the processing times of the request replicas, and design an efficient algorithm to parameterize the model from real data. Extensive evaluations on a MATLAB benchmark and a three-tier web application (MediaWiki) show remarkable accuracy, e.g., 7 (4 percent) average error on the 99th percentile response time for the benchmark (respectively, MediaWiki), the requests of which execute in the order of seconds (respectively, milliseconds). Insights into optimal replication levels are thereby gained from this precise quantitative analysis, under a wide variety of system scenarios.

Processing time variability is commonplace in distributed systems, where resources display disparate performance due to, e.g., different workload levels, background processes, and contention in virtualized environments. However, it is paramount for service providers to keep variability in response time under control in order to offer responsive services. We investigate how request replication can be used to exploit processing time variability to reduce response times, considering not only mean values but also the tail of the response time distribution. We focus on the distributed setup, where replication is achieved by running copies of requests on multiple servers that otherwise evolve independently, and waiting for the first replica to complete service. We construct models that capture the evolution of a system with replicated requests using approximate methods and observe that highly variable service times offer the best opportunities for replication - reducing the response time tail in particular. Further, the effect of replication is non-uniform over the response time distribution: gains in one metric, e.g., the mean, can be at the cost of another, e.g., the tail percentiles. This is demonstrated in wide range of numerical virtual experiments. It can be seen that capturing service time variability is key to the evaluation of latency tolerance strategies and in their design.

In the literature, numerous works have modeled user activity on smartphones and the effects on battery life. Power-saving modes prolong battery life by saving energy, but application performance is limited as a result. We investigate performance-energy trade-offs of smartphone applications by investigating three strategies: first, we propose an M/M/1 discriminatory processor sharing queue to act as a smartphone server and measure delays of Android applications; secondly, we form a performance-energy trade-off that takes into account cellular radio transfers using an objective cost function incorporating mean delay and power consumption; and thirdly, we build an online HMM to act as a power consumption model that predicts battery life given recent data transfers. For all three strategies, we obtain logged smartphone activity of over 750 users via an open-source smartphone data-collection application. Hence, we obtain three hypotheses from our strategies: first, delay of applications is approximated well using the beta prime distribution; secondly, power consumption increases as mean delay decreases with battery life prolonged if adjustments are made to cellular radio usage; and thirdly, burstiness is captured by HMMs in both data transfers and rates of power consumption.

Consistently high reliability and low latency are twin requirements common to many forms of distributed processing; for example, server farms and mirrored storage access. To address them, we consider replication of requests with canceling - i.e. initiate multiple concurrent replicas of a request and use the first successful result returned, canceling all outstanding replicas. This scheme has been studied recently, but mostly for systems with a single central queue, while server farms exploit distributed resources for scalability and robustness. We develop an approximate stochastic model to determine the response-time distribution in a system with distributed queues, and compare its performance against its centralized counterpart. Validation against simulation indicates that our model is accurate for not only the mean response time but also its percentiles, which are particularly relevant for deadline-driven applications. Further, we show that in the distributed set-up, replication with canceling has the potential to reduce response times, even at relatively high utilization. We also find that it offers response times close to those of the centralized system, especially at medium-to-high request reliability. These findings support the use of replication with canceling as an effective mechanism for both fault- and delay-tolerance.

Computing paradigms have shifted towards highly parallel processing and massive replication of data. This entails the efficient distribution of requests and the synchronization of results provided to users. Guaranteeing SLAs requires the ability to evaluate the performance of such systems while taking the effect of non-parallel workloads into consideration. This can be achieved with performance models that are able to represent both parallel and sequential workloads. This paper presents a product-form stochastic Petri-net approximation of fork-join queueing networks with interfering requests. We derive the necessary conditions that guarantee the accuracy of the approximations and verify this through examples in comparison to simulation. We apply these approximate models to the performance evaluation of replication in NoSQL cloud datastores and illustrate the composition of large models from smaller models, thus facilitating the ability to model a range of deployment scenarios. We show the efficiency of our solution method, which finds the product-form solution of the models without the representation of the state-space of the underlying CTMC.

Fork-join queues are natural models for various computer and communications systems that involve parallel multitasking and the splitting and resynchronizing of data, such as parallel computing, query processing in distributed databases, and parallel disk access. Job response time in a fork-join queue is a critical performance indicator but its exact analysis is challenging. We introduce a stochastic model for K -node homogeneous fork-join queues ( K ≥ 2 ) that focuses on the difference in length between any node-queue and the shortest one, truncating the state space such that the maximum difference is at most a constant C . Whilst most previous methods focus on the mean response time, our model is also able to evaluate the response time distribution , as well as accommodating phase-type processing times and Markovian arrival processes. In order to tackle scenarios with high loads, which require a large value of C to provide sufficient accuracy, we develop an efficient algorithm using matrix-analytic methods. Tests against simulation show that the proposed model yields accurate results for 2-node fork-join queues. As the model becomes numerically intractable for large values of K , we further propose an approximate approach, based on properties of order statistics and extreme values. The approximation gives a high degree of accuracy on response time tails, and has the advantage of being efficient and scalable, requiring only the analytical results for a single-node and 2-node fork-join queues, which we obtain with the aforementioned matrix-analytic model. Comparison with simulation results shows that our approximation yields good fits for the tails, even in very large cases with general processing and inter-arrival times.

Social networks, and the behaviour of groups of online users, are popular topics in modeling and classifying Internet traffic data. There is a need to analyze online network performance metrics through suitable workload benchmarks. We address this issue with a Multi-dimensional Hidden Markov Model (MultiHMM) to act as a Multi-User workload classifier. The MultiHMM is an adaptation of the original HMM, using clustering methods and multiple trace-training for the Baum-Welch algorithm. The goals of the MultiHMM are to classify multiple online user streams with minimal processing needs, represent burstiness and correlation among groups of users and to improve security measures in the social network. Experiments are carried out using multiple traces from Twitter data, where original traces are analysed and compared with the MultiHMM-generated traces. The metrics involved in validating our model include means, standard deviations, skew ness and autocorrelation, and we discuss applications and extensions of our model.

As the computing industry enters the Cloud era, multicore architectures and virtualisation technologies are replacing traditional IT infrastructures. However, the complex relationship between applications and system resources in multicore virtualised environments is not well understood. Workloads such as web services and on-line financial applications have the requirement of high performance but benchmark analysis suggests that these applications do not optimally benefit from a higher number of cores.

A new algorithm is given to find product-form solutions for the joint equilibrium probabilities in a class of synchronized Markov processes. This is based on, and proved by, multiple applications of the Reversed Compound Agent Theorem (RCAT) and can describe multi-way synchronizations (seen as chains of pairwise synchronizations) that occur in a prescribed order. The length of the sequence is unbounded but finite with probability 1. Several applications are given to illustrate the methodology, which include various modes of resets in queueing networks with negative customers. In particular, it is shown that there is a type of reset that can propagate further transitions in a chain actively. Furthermore, a number of completely new product-form models, for example, where the transitions in a chain are non-homogeneous, are given.

Run-time resource allocation requires the availability of system performance models that are both accurate and inexpensive to solve. We here propose a new methodology for run-time performance evaluation based on a class of closed queueing networks. Compared to exponential product-form models, the proposed queueing networks also support the inclusion of resources having first-come first-served scheduling under non-exponential service times. Motivated by the lack of an exact solution for these networks, we propose a fixed-point algorithm that approximates performance indexes in linear time and linear space with respect to the number of requests considered in the model. Numerical evaluation shows that, compared to simulation, the proposed models solved by fixed-point iteration have errors of about 1%-6%, while, on the same test cases, exponential product-form models suffer errors even in excess of 100%. Execution times on commodity hardware are of the order of a few seconds or less, making the proposed methodology practical for run-time decision-making.

We investigate how a power-save mode affects the battery life of a device subject to stochastically determined charging and discharging periods. We use a multi-regime fluid queue, imposing a threshold at some value. When the power level falls below the threshold, (for example, 20% of charge remaining) a power-save mode is entered and the rate of discharge decreased. An expression for the Laplace transform of the battery life's probability density function is found and inverted numerically in particular instances. We show the life of battery can be significantly improved by the introduction of the power-saving threshold.

Performance model interchange formats (PMIFs) support the portability of models and sharing of solutions amongst different tools. XML-based interchange formats have been defined for the interchange of queueing network and Petri net models, amongst others, but there is still scope to extend their application to multiple formalisms, in particular beyond queueing networks. We extend an existing PMIF to hybrid models by including a new type of node, called a 'building block', defined as a certain class of Petri nets. The synchronisation primitives of these building blocks can be used to specify fork-join systems whilst, under certain conditions, retaining product-form solutions when embedded in queueing (or other) networks possessing this property already. When a product-form does not exist, the whole network is translated into a Petri net and solved either by simulation or direct solution of the underlying Markov chain by an existing analyser. Finally, we apply the extended PMIF to model a computer system with RAID storage.

In queueing networks with blocking, stations wishing to transmit customers to a full queue are blocked and need to take alternative action on completing a service. In general, product-forms, i.e. separable solutions for such a network's equilibrium state probabilities, do not exist but some product-forms have been obtained over the years in special cases, using a variety of techniques. We show that the Reversed Compound Agent Theorem (RCAT) can obtain these diverse results in a uniform way by its direct application, so unifying product-forms in networks with and without blocking. New product-forms are also constructed for a type of blocking we call `skipping', where a blocked station sends its output-customers to the queue after the one causing the blocking in that customer's path. Finally, we investigate a novel congestion management scheme for networks of finite-capacity queues in which a station with a full queue transmits signals that delete customers from upstream queues in order to reduce incoming traffic.

Consistent with the divide-and-conquer approach to problem solving, a recursive result is presented in the domain of stochastic modelling that derives product-form solutions for the steady state probabilities of certain networks composed from interacting Markov chains. Practical applications include multi-tasking operating systems, communication channels and multi-tiered storage systems. The approach is also applied to the computation of response time quantiles, which are vital in transaction processing, computer communication service level agreements and other operational systems. The joint probability distribution of the sojourn times of a tagged task at each node in a network is determined by noting that this is the same in both the forward and reversed processes. In this way, existing results for response time probability densities in tandem, tree-like, and overtake-free Markovian queueing networks are quickly and systematically obtained. We further show how to apply the method in more general networks.

Department of Computing, Imperial College London, London, UK. Email: [email protected] A resurgence in product-forms Interest in the stochastic behaviour of queueing networks began in the 1960s with the work by Jackson, Gordon, Newell and others [1–3]. These authors derived the so-called product-form solutions for the equilibrium probabilities of the joint state in such a continuous time Markov chain (CTMC). From the preceding lecture, of course, these networks are special cases of G-networks, where there are no negative customers, triggers, signals, etc. After a number of generalizations of Jackson networks in the 1970s and 1980s, it was thought by many that a product-form for a stochastic network would only exist if that network satisfied a condition called partial or local balance [4, 5]. Essentially, this specifies a specific way by which the global balance equations of probability fluxes into, and out of, a given state (the steady-state theorem for CTMCs) are constructed from balanced subsets of these equations, each subset relating to a component of the network. Gelenbe's G-network model [6–14], and the related RNN model [15], with its non-linear traffic equations in particular, provided counter-examples to this widely held view. In turn, this sparked a resurgence of interest in the quest for product-forms, which continues today.

Strict priority queueing and weighted round robin are two common scheduling schemes for differentiation of services in telecommunication networks. A combination of these is the priority weighted round robin (PWRR) scheme, which serves three classes of traffic with distinct quality requirements, namely expedited forwarding (EF), assured forwarding (AF) and best effort forwarding (BF). The response time of the AF class is analysed under a worst case scenario and an expression for its mean value is obtained using a queueing model. Numerical results are validated by simulation and implications on service level agreements are discussed.

A new queuing model is proposed for the performance evaluation of the High Speed Downlink Packet Access (HSDPA) protocol, with respect to a specified user, in UMTS networks. The model is based on the recently evolved MM ΣΚκ= CPPκGEcLG-queue1, in which the number of servers allocated to a specified user is subjected to vary according to the physical channel allocation policy. This queue is, essentially, an important variant of the so-called Sigma queuing model, and it is able to capture most of the features of HSDPA wireless communications, such as traffic-burstiness, channel fading, channel allocation policy, etc., in an integrated way. Numerical results for the performance of HSDPA with respect to a specified user are obtained, and different HSDPA user equipment categories are compared with respect to their computed model throughputs.

The quantitative behaviour of stochastic tandem networks is considered, in which two buffers hold fluid rather than discrete tokens at each server-node. The end-to-end performance of a simple wireless router network is then optimized using such a stochastic fluid model. The optimization minimizes both the mean and variance of the transmission delay (or 'response time'), subject to an upper limit on the rate of losses and finite capacity queueing and recovery buffers. The trade-off between mean and variance of response time is assessed and the optimal ratio of arrival-buffer size to recovery-buffer size is determined, which is a critical quantity, affecting both loss rate and transmission time.

In this paper we consider an M/G/1 queue-based analytical model. The end-to-end performance of a tandem wireless router network with batch arrivals is optimized. The mean of the transmission delay (or 'response time') is minimized subject to an upper limit on the rate of losses and finite capacity queueing and recovery buffers. The optimal ratio of arrival-buffer size to recovery-buffer size is determined, which is a critical quantity, affecting both loss rate and transmission time. The impact of the retransmission probability is investigated: too high a value leads to congestion and so higher response times, too low and packets are lost forever, yielding a different penalty

Differentiated services and other scheduling strategies are now widespread in the traditional, "best effort" Internet. These offer quality of service guarantees for important customers at the same time as supporting less critical applications of lower priority. Since response time, or delay, is a crucial performance metric for delay-sensitive applications, time delays in priority queues have been studied extensively in recent years. We consider a DiffServ node which is modelled as a non-preemptive priority queue with modulated arrivals and derive an expression for the probability distribution of the response time using the generating function method. We consider two service classes: expedited traffic forms the high priority class and is modelled as a Poisson process whereas best effort traffic is in the low priority class and modelled as a Markov modulated Poisson process. The distribution of service time is general. This queue has many real-world applications; in the example considered here, it could model a DiffServ router which provides service differentiation for signalling or management traffic together with standard data streams. Mean delays are derived as explicit expressions and show very close agreement with simulation. Higher moments can be computed in the same way with more routine algebra.

Probability distributions of response times are important in the design and analysis of transaction processing systems and computer-communication systems. We present a general technique for deriving such distributions from high-level modelling formalisms whose state spaces can be mapped onto finite Markov chains. We use a load-balanced, distributed implementation to find the Laplace transform of the first passage time density and its derivatives at arbitrary values of the transform parameter s. Setting s = 0 yields moments while the full passage time distribution is obtained using a novel distributed Laplace transform inverter based on the Laguerre method. We validate our method against a variety of simple densities, cycle time densities in certain overtake-free (tree-like) queueing networks and a simulated Petri net model. Our implementation is thereby rigorously validated and has already been applied to substantial Markov chains with over 1 million states. Corresponding theoretical results for semi-Markov chains are also presented.

We present a process algebra, SPADES, based on Milner's CCS, which may be used to describe discrete event simulations with parallelism. It is able to describe the passing of time and probabilistic choice, either discrete, between a countable number of processes, or continuous, to choose a random amount of time to wait. Its operational semantics is presented as a labelled transition system and we discuss equivalences over this operational semantics that imply axioms that can be used to compare and transform processes formally. We discuss notions of equivalence over simulations and the meaning of non-determinism in the context of the specification of a simulation. The algebra is applied to describe quantitatively a range of communicating systems.

This Hot-Topics Session on G-Networks aims at bringing these relatively new models which we introduced for the first time in 1989 and 1990, to the attention of the performance evaluation and modeling community. The session includes presentations by Peter Harrison, Onno Boxma, Jean-Michel Fourneau and myself. We will cover the basic concepts, some examples of potential applications, as well as recent research efforts in this area.

Efficient product form solution is one of the major attractions of queueing networks for performance modelling purposes. These models rely on a form of interaction between nodes in a network which allows them to be solved in isolation, since they behave as if independent up to normalisation. Markovian process algebras (MPA) extend classical process algebras with information about the duration of actions but retain their compositional structure: a system is modelled as an interaction of components. The advantages of this compositional structure for model construction and model simplification have already been demonstrated. In this paper we exploit results from queueing networks to identify a restricted form of interaction between suitable MPA components which leads to a product form solution. Each component of the model may be solved separately and the compositional structure of an MPA consequently facilitates efficient solution for successively more complex models. This work uses the notion of quasi-reversibility in a Markov process setting to define the type of interaction between MPA components. This leads to a substantial class of MPA definitions that have product-form solutions which is more general than the usual queueing network-based class of Markov processes.

In this paper we consider the distribution of message transmission times in buffered full cross bar interconnection networks with cyclic arbitration in which the input buffers are serviced in a 'round robin' fashion. The system is modelled as an open queue ing network in which the queues appear at the net work outputs and with the cyclic arbiter being mod elled by queue jumping. We obtain the Laplace Trans form of the transmission time by deriving a condi tional Laplace Transform and solving by the use of a generating function. The density function is then enumerated by numerical inversion and compared with similar results from a simulation model. The analysis is then extended to general service times by modelling each output as a LCFS queue with a suitably modified arrival rate. In the special case of exponential service times, this model is less versatile than the previous one since it only works in the case where the jump probability is fixed. In this case, however, it is shown to produce the same result as the original.

Dynamic, parallel algorithms of the divide-and-conquer type are mapped onto static parallel computer architectures where the set of processors and their interconnections are fixed throughout the execution of a program. The approach taken is to transform a class of algorithms, expressed as functional programs, into a form that corresponds to a pipeline. The pipeline itself is then generated and the technique is illustrated by two sorting and one numeric list processing examples.

A unified approach to the development of algorithms tailored to various classes of parallel computer architecture is presented. The central theme is to identify a small set of higher-order functions that can be implemented efficiently on the target architecture and which can be used to express parallel algorithms – in general via mechanised program transformation from some higher-level specification. Such higher-order functions enable generic programs to be written in which much parallelism may be explicit. Although the analysis uses purely functional languages, it is the functional paradigm that is important and not the particular syntax. The proposed methodology is illustrated with a numerical problem which is solved directly by a non-recursive program. We also describe schemes that map programs onto both static and dynamic MIMD architectures which have communication links which are fixed and changeable at run-time respectively.

The efficient implementation of abstract data types and all functions that manipulate them would permit application-oriented solutions to be developed without having to take undue account of executional properties. The synthesis of efficient concrete types and functions forms the basis of the present paper, which appeals to a theory of inverse functions for additional axioms to augment those of a first-order functional algebra. These axioms are then applied in the simplification of the combinator-expressions arising in the synthesis of the functions between the concrete types. We also show how the abstraction function itself may be deduced in certain situations where it is required to optimise particular operations on an abstract type. In addition to possessing rigorous mathematical foundations, the function-level axioms are more generally applicable than previous approaches to this problem, and induce a more mechanisable rewrite-based transformation system.

A major component of a parallel machine is its interconnection network (IN), which provides concurrent communication between the processing elements. It is common to use a multistage interconnection network (MIN) that is constructed using crossbar switches and introduces contention not only for destination addresses but also for internal links. Both types of contention are increased when nonlocal communication across a MIN becomes concentrated on a certain destination address, the hot-spot . This paper considers analytical models of asynchronous, circuit-switched INs in which partial paths are held during path building, beginning with a single crossbar and extending recursively to MINs. Since a path must be held between source and destination processors before data can be transmitted, switching networks are passive resources and queuing networks that include them do not therefore have product-form solutions. Using decomposition techniques, the flow-equivalent server (FES) that represents a bank of devices transmitting through a switching network is determined, under mild approximating assumptions. In the case of a full crossbar, the FES can be solved directly and the result can be applied recursively to model the MIN. Two cases are considered: one in which there is uniform routing and the other where there is a hot-spot at one of the output pins. Validation with respect to simulation for MINs with up to six stages (64-way switching) indicated a high degree of accuracy in the models.

The often conflicting needs to make software both efficient and correct have made a large contribution to the present so-called software crisis, and transformation-based support environments for functional languages offer a major step towards solving this conflict in requirements. In such an environment programs are initially developed by concentrating only on the understandability, correctness, clarity, reliability and maintenance aspects. This initial specification is then transformed through a series of meaning-preserving transformations to achieve an efficient implementation. We argue that the abstraction level of the majority of commonly used functional languages is too low-level for the results of the analysis to be automatically implemented or very generally applicable. However, by compiling such programs into a higher-level, more structured, variable-free representation, we show how the analysis can achieve more powerful, mechanised, and generally applicable transformations. This is due in part to the elimination of the concern for the domain of objects, since function definitions are now expressed purely in terms of functions and so become simpler. Many recursive functions are linear in the sense that the number of recursive function calls they generate is bounded by a number which is proportional to the magnitude of their argument. The performance of functional languages can therefore be improved by a more efficient implementation of linear functions, and we derive equivalent imperative language loops for a large class of linear recursive functions. Moreover, such linear functions can be detected automatically in the parsing phase of a compiler and their loop implementations generated. Other recursive functions are non-linear, generating a number of function calls that grows in a non-linear manner with respect to the magnitude of the arguments to which they are applied, for example quadratically or exponentially. Although non-linear functions tend to be fewer, their run-time performance tends to be relatively much poorer, and so their efficient implementation too is of considerable importance to functional languages. We illustrate how certain non-linear function definitions can be transformed into linear ones, and how they can therefore subsequently be implemented as loops. An alternative, more automatic approach for the treatment of non-linear functions uses memo-functions, which are functions that ‘remember’ all the arguments to which they have been applied, together with the corresponding results computed from them. We define a class of non-linear functions for which memorisation linearises the time-cost of calls of a non-linear function to itself whilst executing in bounded space. The technique for generating such memo-functions is widely applicable, easily mechanised and achieves improvements in efficiency that are comparable with existing program transformation schemes. Furthermore, the sizes of the tables for these memo-functions are guaranteed not to exceed a compile-time constant found by a simple static analysis of the definition of the non-linear function.

In this paper we describe two types of complex server aggregations which can be used to model collections of components in certain types of parallel computer systems and give a case study showing how the aggregations may be applied in practice. Analytical models of such systems are becoming increasingly important as a means of guiding the often complex design processes, particularly since recent developments in VLSI technology now make it possible to fabricate many paper-designs hitherto impractical for reasons of cost. We argue that aggregations of the type described are essential in the modelling of parallel systems; using the proposed techniques, large numbers of components can be modelled as queue-length-dependent servers within a queueing network in which the number of servers is the same as the number of distinct types of processing element in the system being modelled. Because the number of severs in the model is fixed i.e. is independent of the number of processors, very large multiprocessor systems can be modelled efficiently with no explosion in the size of the state space.

An approximation for the distribution of time delays experienced by a customer in a network of queues is presented. Approximate analytical models are necessary since exact solutions are only available for a very restricted class of networks, and are too complex computationally to be viable in practice. Approximations have so far often proved inadequate, particularly for closed networks with first come first served queueing disciplines. We also prove that the correlation between the sojourn times at successive servers on a customer's path in a closed queueing network with exponential servers is negative.

The time delays experienced by tasks in computer systems are a prime interest for both the user community and installation management. Thus their prediction becomes an important objective for the computer performance analyst. Cycle time in scheduling systems and response time, an aggregation of cycle times, in interactive systems are typical examples. The statistical characteristics of time delays have been represented predominantly by simulation models. In analytical models, based on queueing network analysis, normally only their mean values have been derived using Little's law. An exact derivation is presented for the distribution of cycle times in so-called tree-like queueing networks. The analysis is performed for a choice of network structure which avoids the need for explicit tagging of some test customer. Thus expansion of the state space is not necessary. Cycle time distribution is derived in the form of its Laplace transform, from which its moments follow. Further, a recurrence relation for a uniformly convergent discrete representation of the distribution may be determined in a similar manner. Numerical examples show how the distribution of cycle time and its standard deviation vary as the population of a network increases, and how the exact formulae may be used to validate other types of model, such as approximate analytic or simulation.

A Markov model is developed for a message processing node with batch arrivals and various flow control schemes. In particular, a credit allocation pacing control mechanism, previously modeled only by simulation, is represented analytically. The primary application is the network-independent flow control of messages between networks which may have quite different characteristics, via a gateway, but the approach is sufficiently general for modeling many servers or whole subnetworks in any queueing system. A closed form solution to the model's balance equations cannot be found, and direct solution is impracticable due to their number. However, by identifying invariants and making physically realistic approximations, the size of the state space is reduced to such an extent that direct numerical solution does become viable. In particular, the credit allocation scheme is shown to be equivalent to the node's operation in different modes, each with its own buffer capacity, so that credit control need not be modeled explicitly, and no approximation is incurred. Accuracy is assessed by comparison with the results of explicit simulations of a selection of nodes of this type with various parameterizations. Finally, we suggest applications for the model in the assessment and comparison of performance under various congestion control schemes and propose some new stabilizing mechanisms.

Prediction of detailed characteristics of the time delays experienced by customers in queueing networks is of great importance in various modelling and performance evaluation activities: operations research, computer systems and communication networks. Their statistical properties have been investigated predominantly by simulation techniques with the exception of mean value analyses for which Little's Law is applied. Theoretical studies of the probability distributions of time delays tend to be based on their Laplace transforms, which are of limited use, can be inverted analytically only in very simple cases and present substantial computation problems for numerical inversion. An exact derivation is presented for the distribution of cycle times in so called tree-like queueing networks. The analysis is performed for a network structure which is such that it is not necessary to mark a special customer, so avoiding expansion of the state space. Cycle time distribution is derived initially in the form of its Laplace Transform, from which its moments follow. A recurrence relation for a uniformly convergent discrete representation of the distribution then follows by a similar argument. Finally, the numerical results obtained for some simple test networks are presented and compared with those corresponding to an approximate method, hence indicating the accuracy of the latter.

Non-procedural, functional of applicative, languages are well accepted as an excellent means for problem solving, but conventional implementations invite criticism of their performance and constrained notation, which may involve long, clumsy and repeated expressions. Such deficiencies are overcome to a large extent by the (destructive) assignment statement in algorithmic languages and we propose incorporation of the desirable properties of assignment into functional languages, whilst preserving non-procedural semantics. Performance is then addressed via stack storage management for block structured functional languages. Stack storage economics are achieved by efficient handling of the display vector and by early erasure of unwanted links and arguments from the stack. Execution time is optimized by retaining in an appropriate outer function's stack frame, values which would otherwise be recomputed via repeating identical function calls or argument evaluation. This also results in further savings in stack storage in many cases.