The Asymmetric Inclusion Process (ASIP) tandem queue is a model of stations in series with a gate after each station. At a gate opening, all customers in that station instantaneously move to the next station unidirectionally. In our study, we enhance the ASIP model by introducing the capability for individual customers to independently move from one station to the next, and by allowing both individual customers and batches of customers from any station to exit the system. The model is inspired by the process by which macromolecules are transported within cells. We present a comprehensive analysis of various aspects of the queue length in the ASIP tandem model. Specifically, we provide an exact analysis of queue length moments and correlations and, under certain circumstances, of the queue length distribution. Furthermore, we propose an approximation for the joint queue length distribution. This approximation is derived using three different approaches, one of which employs the concept of the replica mean-field limit. Among other results, our analysis offers insight into the extent to which nutrients can support the survival of a cell.

We consider a system with several job types and two parallel server pools. Within the pools the servers are homogeneous, but across pools possibly not in the sense that the service speed of a job may depend on its type as well as the server pool. Immediately upon arrival, jobs are assigned to a server pool, possibly based on (partial) knowledge of their type. In case such knowledge is not available upon arrival, it can however be obtained while the job is in service; as the service progresses, the likelihood that the service speed of this job type is low increases, creating an incentive to execute the job on different, possibly faster, server(s). Two policies are considered: reroute the job to the other server pool, or replicate it there.We determine the effective load per server under both the rerouting and replication policy for completely unknown as well as partly known job types. We also examine the impact of these policies on the stability bound, which is defined as the maximum arrival rate of jobs for which the effective load per server is smaller than one. We demonstrate that the uncertainty in job types may significantly reduce the stability bound, and that for (highly) unbalanced service speeds full replication achieves the largest stability bound. Finally, we discuss how the use of threshold-based policies can help improve the expected latency for completely or partly unknown job types.

We consider a general class of closed product-form queueing networks, consisting of single-server queues and infinite-server queues. Even if a network is of product-form type, performance evaluation tends to be difficult due to the potentially large state space and the dependence between the individual queues. To remedy this, we analyze the model in a Halfin–Whitt inspired scaling regime, where we jointly blow up the traffic loads of all queues and the number of customers in the network. This leads to a closed-form limiting stationary distribution, which provides intuition on the impact of the dependence between the queues on the network’s behavior. We assess the practical applicability of our results through a series of numerical experiments, which illustrate the convergence and show how the scaling parameters can be chosen to obtain accurate approximations.

We investigate the stability condition for redundancy-d systems where each of the servers follows a processor-sharing (PS) discipline. We allow for generally distributed job sizes, with possible dependence among the d replica sizes being governed by an arbitrary joint distribution. We establish that for homogeneous servers the stability condition for the associated fluid-limit model is characterized by the expectation of the minimum of d replica sizes being less than the mean interarrival time per server. In the special case of identical replicas, the stability condition is insensitive to the job size distribution given its mean, and the stability threshold is inversely proportional to the number of replicas. In the special case of i.i.d. replicas, the stability threshold decreases (increases) in the number of replicas for job size distributions that are NBU (NWU). We also discuss the extension to heterogeneous servers. For heavy-tailed job sizes we characterize the tail behavior of the response time distribution. In particular, for regularly varying job sizes with tail index −ν it is shown that the tail index of the response time equals −ν and −dν for identical and i.i.d. replicas, respectively.

As the use of wireless sensor networks increases, the need for (energy-)efficient and reliable broadcasting algorithms grows. Ideally, a broadcasting algorithm should have the ability to quickly disseminate data, while keeping the number of transmissions low. In this paper we develop a model describing the message count in large-scale wireless sensor networks. We focus our attention on the popular Trickle algorithm, which has been proposed as a suitable communication protocol for code maintenance and propagation in wireless sensor networks. Besides providing a mathematical analysis of the algorithm, we propose a generalized version of Trickle, with an additional parameter defining the length of a listen-only period. This generalization proves to be useful for optimizing the design and usage of the algorithm. For single-cell networks we show how the message count increases with the size of the network and how this depends on the Trickle parameters. Furthermore, we derive distributions of inter-broadcasting times and investigate their asymptotic behavior. Our results prove conjectures made in the literature concerning the effect of a listen-only period. Additionally, we develop an approximation for the expected number of transmissions in multi-cell networks. All results are validated by simulations.

Consider two M/G/1 queues that are coupled in the following way. Whenever both queues are non-empty, each server serves its own queue at unit speed. However, if server 2 has no work in its own queue, then it assists server 1, resulting in an increased service speed r/sub 1//sup *//spl ges/1 in the first queue. This kind of coupling is related to generalized processor sharing. We assume that the service request distributions at both queues are regularly varying at infinity of index -v/sub 1/ and -v/sub 2/, namely, they are heavy-tailed. Under this assumption, we present a detailed analysis of the tail behaviour of the workload distribution at each queue. If the guaranteed unit speed of server 1 is already sufficient to handle its offered traffic, then the workload distribution at the first queue is shown to be regularly varying at infinity of index 1-v/sub 1/. But if it is not sufficient, then the workload distribution at the first queue is shown to be regularly varying at infinity of index 1-min(v/sub 1/,v/sub 2/). In particular, traffic at server 1 is then no longer protected from worse-behaved (heavier-tailed) traffic at server 2.

We analyze the asymptotic behavior of long-tailed traffic sources under the generalized processor sharing (GPS) discipline. GPS-based scheduling algorithms, such as weighted fair queueing, have emerged as an important mechanism for achieving differentiated quality-of-service in integrated-services networks. Under certain conditions, we prove that in an asymptotic sense an individual source with long-tailed traffic characteristics is effectively served at a constant rate, which may be interpreted as the maximum feasible average rate for that source to be stable. Thus, asymptotically, the source is only affected by the traffic characteristics of the other sources through their average rate. In particular, the source is essentially immune from excessive activity of sources with 'heavier'-tailed traffic characteristics. This suggests that GPS-based scheduling algorithms provide an effective mechanism for extracting high multiplexing gains, while protecting individual connections.

Consider a fluid queue fed by N on/off sources. It is assumed that the silence periods of the sources are exponentially distributed, whereas the activity periods are generally distributed. The inflow rate of each source, when active, is at least as large as the outflow rate of the buffer. We make two contributions to the performance analysis of this model. Firstly, we determine the Laplace-Stieltjes transforms of the distributions of the busy periods that start with an active period of source i, i = 1; : : : ; N , as the unique solution in [0; 1] N of a set of N equations. Thus we also find the Laplace-Stieltjes transform of the distribution of an arbitrary busy period. Secondly, we relate the tail behaviour of the busy period distributions to the tail behaviour of the activity period distributions. We show that the tails of all busy period distributions are regularly varying of index \\Gamma iff the heaviest of the tails of the activity period distributions are regularly varying of i...

In modern teletraffic applications of queueing theory, service time distributions B(t) with a heavy tail occur, i.e., 1-B(t)/spl sim/Ct/sup -v/ for t/spl rarr//spl infin/ with v>1. For such service time distributions, not much explicit information is available concerning the tail probabilities of the corresponding waiting time distribution W(t). In the present study, which is devoted to the M/G/1 queue, a class of heavy-tailed service time distributions is introduced that does allow a rather detailed analysis of the tail behavior of the waiting time distribution. For v=1 1/2 , an explicit expression for W(t) is derived. For rational v with 1<v<2, an asymptotic series for the tail probabilities of W(t) is derived. In addition, we present an approximation for W(t), which is based on a heavy-traffic limit theorem for the M/G/1 queue with heavy-tailed service time distribution (with infinite variance); this approximation is shown to yield excellent results for values of t which are not too small, even when the load is not heavy.

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.

Time limits are the major mechanisms used for controlling a large variety of multistation single-medium computer-communication systems like the FDDI network and the IEEE 802.4 Token Bus. The proper use of these mechanisms is still not understood and rules for efficient system operation are not available. The authors' objective is the derivation of such rules. They use a cyclic polling model with different service limits (k-limited service) at the different queues, thus emulating time limits. They are interested in determining these k-limit values so as to minimize the mean waiting cost of messages in the system. A simple approximative approach is proposed for two major problems: one in which a limit is set on the token rotation time and one in which no limits are imposed. The approach is tested for a variety of cases and is shown to be very effective.>

This paper analyses a variant of the ikl/G/l queue in which the service times of arriving customers depend on the length of the interval between their arrival and the previous arrival.The dependence structure corresponds to the case of customers arriving according to an ordinary Poisson arrival process, and customer collectors being sent out according to a Poisson process to collect the customers and to bring them to the service facility.In this case collected numbers of customers, and hence total collected service requests, are positively correlated with the corresponding collect intervals.Viewing a batch of collected customers as one (super) customer gives rise to an itf/G/l queue with a positive correlation between service times of such customers and their interarrival times.Both for individual customers and for batches of collected customers we derive the transforms of the sojourn time and waiting time distributions.We also compare our results with those for the ordinary M/G/l queue without dependence.

The authors examine an M/G/1 FCFS (first come, first served) queue with two types of customers: ordinary customers, who arrive according to a Poisson process, and permanent customers, who immediately return to the end of the queue after having received a service. The influence of the permanent customers on queue length and sojourn times of the Poisson customers is studied using results from queuing theory and from the theory of branching processes. In particular, it is shown that, when the service time distributions of the Poisson customers and all K permanent customers are negative exponential with identical means, the queue length and sojourn time distributions of the Poisson customers are the (K+1)-fold convolution of those for the case without permanent customers.>

The analysis of waiting times in polling systems in which the stations are polled according to a general service-order table is discussed. Such systems can be used to represent token-bus local area networks in which the routing of the token is fixed. Stations are given higher priority by being listed more frequently in the table, or by receiving service according to the exhaustive service discipline. The polling system is modeled by a single-server multiqueue system in discrete time. Nonzero switchover times between the queues are assumed. An extension of the principle of work conservation to systems with nonzero switchover times leads to an exact expression for a weighted sum of the mean waiting times at the various queues. By using a limiting procedure, the discrete-time results are translated to continuous-time results. The special case of polling in a star network is discussed and compared to polling in a corresponding network with strictly cyclic service order.>

Single-served, multiqueue systems with cyclic service in discrete time are considered. Nonzero switchover times between consecutive queues are assumed; the service strategies at the various queues may differ. A decomposition for the amount of work in such systems is obtained, leading to an exact expression for a weighted sum of the mean waiting times at the various queues.>

Mean waiting-time approximations are derived for a single-server multi-queue system with nonexhaustive cyclic service. Non-zero switch-over times of the server between consecutive queues are assumed. The main tool used in the derivation is a pseudo-conservation law recently found by Watson. The approximation is simpler and, as extensive simulations show, more accurate than existing approximations. Moreover, it gives very good insight into the qualitative behavior of cyclic-service queueing systems.

Consider a closed cyclic queuing system consisting of M exponential queues.The Laplace-Stieltjes transform of the joint d~stribution of the consecutive sojourn times of a customer at the M queues is determined and shown to have a product form.The proof is based on a reverslbdity argument.