Search

This study considers a multi-class single-server retrial queue with constant retrial rates in which service times are generally distributed with different service rates for each class. Avrachenkov (Queueing Systems 100:177–179, 2022) formulated the conjecture on the stability of this queueing system. We completely resolve the conjecture by using the fluid limit approach. [ABSTRACT FROM AUTHOR]

We consider a multi-class multi-server retrial queueing system. Customers of each class arrive from outside the system according to a Poisson process. The service times for each class of customers are assumed to be exponentially distributed with service rates depending on both the customers' class and the servers. We define the offered load and provide stability and instability conditions for this retrial queueing system. The stability result can be obtained by introducing artificial primitive processes and using the fluid limit approach. [ABSTRACT FROM AUTHOR]

We consider load balancing in service systems with affinity relations between jobs and servers. Specifically, an arriving job can be assigned to a fast, primary server from a particular selection associated with this job or to a secondary server to be processed at a slower rate. Such job–server affinity relations can model network topologies based on geographical proximity, or data locality in cloud scenarios. We introduce load balancing schemes that assign jobs to primary servers if available, and otherwise to secondary servers. A novel coupling construction is developed to obtain stability conditions and performance bounds. We also conduct a fluid limit analysis for symmetric model instances, which reveals a delicate interplay between the model parameters and load balancing performance. [ABSTRACT FROM AUTHOR]

We study a system where a random flow of customers is served by servers (called agents) invited on-demand. Each invited agent arrives into the system after a random time; after each service completion, an agent returns to the system or leaves it with some fixed probabilities. Customers and/or agents may be impatient, that is, while waiting in queue, they leave the system at a certain rate (which may be zero). We consider the queue-length-based feedback scheme, which controls the number of pending agent invitations, depending on the customer and agent queue lengths and their changes. The basic objective is to minimize both customer and agent waiting times. We establish the system process fluid limits in the asymptotic regime where the customer arrival rate goes to infinity. We use the machinery of switched linear systems and common quadratic Lyapunov functions to approach the stability of fluid limits at the desired equilibrium point and derive a variety of sufficient local stability conditions. For our model, we conjecture that local stability is in fact sufficient for global stability of fluid limits; the validity of this conjecture is supported by numerical and simulation experiments. When local stability conditions do hold, simulations show good overall performance of the scheme. [ABSTRACT FROM AUTHOR]

We study a mean-field approximation of the M/M/ $$\infty $$ queueing system. The problem we deal is quite different from standard games of congestion as we consider the case in which higher congestion results in smaller costs per user. This is motivated by a situation in which some TV show is broadcast so that the same cost is needed no matter how many users follow the show. Using a mean-field approximation, we show that this results in multiple equilibria of threshold type which we explicitly compute. We further derive the social optimal policy and compute the price of anarchy. We then study the game with partial information and show that by appropriate limitation of the queue-state information obtained by the players, we can obtain the same performance as when all the information is available to the players. We show that the mean-field approximation becomes tight as the workload increases, thus the results obtained for the mean-field model well approximate the discrete one. [ABSTRACT FROM AUTHOR]

We consider the stability of the longest-queue-first (LQF) scheduling policy in wireless networks with multihop traffic under the one-hop interference model. Although it is well known that the back-pressure algorithm achieves the maximal stability, its computational complexity is prohibitively high. In this paper, we consider LQF, a low-complexity scheduling algorithm, which has been shown to have near-optimal throughput performance in many networks with single-hop traffic flows. We are interested in the performance of LQF for multihop traffic flows. In this scenario, the coupling between queues due to multihop traffic flows makes the local-pooling-factor analysis difficult to perform. Using the fluid-limit techniques, we show that LQF achieves the maximal stability for linear networks with multihop traffic and a single destination on the boundary of the network under the one-hop interference model. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with threshold voter models on tori. Assuming that the initial distribution of the process is product measure with density $$p$$ , we obtain a fluid limit of the proportion of vertices in state 1 as the dimension of the torus grows to infinity. The fluid limit performs a phase transition phenomenon from $$p<1/2$$ to $$p>1/2$$ . [ABSTRACT FROM AUTHOR]

We consider a service system model primarily motivated by the problem of efficient assignment of virtual machines to physical host machines in a network cloud, so that the number of occupied hosts is minimized.There are multiple types of arriving customers, where a customer's mean service time depends on its type. There is an infinite number of servers. Multiple customers can be placed for service into one server, subject to general 'packing' constraints. Service times of different customers are independent, even if served simultaneously by the same server. Each new arriving customer is placed for service immediately, either into a server already serving other customers (as long as packing constraints are not violated) or into an idle server. After a service completion, each customer leaves its server and the system. We propose an extremely simple and easily implementable customer placement algorithm, called Greedy-Random (GRAND). It places each arriving customer uniformly at random into either one of the already occupied servers (subject to packing constraints) or one of the so-called zero-servers, which are empty servers designated to be available to new arrivals. One instance of GRAND, called GRAND( $$aZ$$ ), where $$a\ge 0$$ is a parameter, is such that the number of zero-servers at any given time $$t$$ is $$aZ(t)$$ , where $$Z(t)$$ is the current total number of customers in the system. We prove that GRAND( $$aZ$$ ) with $$a>0$$ is asymptotically optimal, as the customer arrival rates grow to infinity and $$a\rightarrow 0$$ , in the sense of minimizing the total number of occupied servers in steady state. In addition, we study by simulations various versions of GRAND and observe the dependence of convergence speed and steady-state performance on the number of zero-servers. [ABSTRACT FROM AUTHOR]

Consider a single server queueing system with several classes of customers, each having its own renewal input process and its own general service times distribution. Upon completing service, customers may leave, or re-enter the queue, possibly as customers of a different class. The server is operating under the egalitarian processor sharing discipline. Building on prior work by Gromoll et al. (Ann. Appl. Probab. 12:797-859, ) and Puha et al. (Math. Oper. Res. 31(2):316-350, ), we establish the convergence of a properly normalized state process to a fluid limit characterized by a system of algebraic and integral equations. We show the existence of a unique solution to this system of equations, both for a stable and an overloaded queue. We also describe the asymptotic behavior of the trajectories of the fluid limit. [ABSTRACT FROM AUTHOR]

We consider a single-server queue with renewal arrivals and i.i.d. service times, in which the server employs either the preemptive Shortest Remaining Processing Time (SRPT) policy, or its non-preemptive variant, Shortest Job First (SJF). We show that for given stochastic primitives (initial condition, arrival and service processes), the model has the same fluid limit under either policy. In particular, we conclude that the well-known queue length optimality of preemptive SRPT is also achieved, asymptotically on fluid scale, by the simpler-to-implement SJF policy. We also conclude that on fluid scale, SJF and SRPT achieve the same performance with respect to state-dependent response times. [ABSTRACT FROM AUTHOR]

We consider a class of controlled queue length processes, in which the control allocates each server's effort among the several classes of customers requiring its service. Served customers are routed through the network according to (prescribed) routing probabilities. In the fluid rescaling, $X^{n}(t)=\frac{1}{n} X(nt)$, we consider the optimal control problem of minimizing the integral of an undiscounted positive running cost until the first time that X=0. Our main result uses weak convergence ideas to show that the optimal value functions V of the stochastic control problems for X( t) converge (as n→∞) to the optimal value V of a control problem for the limiting fluid process. This requires certain equicontinuity and boundedness hypotheses on { V}. We observe that these are essentially the same hypotheses that would be needed for the Barles-Perthame approach in terms of semicontinuous viscosity solutions. Sufficient conditions for these equicontinuity and boundedness properties are briefly discussed. [ABSTRACT FROM AUTHOR]

We introduce a novel class of tandem queueing networks which arise in modeling the congestion behavior of wireless multi-hop networks with distributed medium access control. These models provide valuable insight in how the network performance in terms of throughput depends on the back-off mechanism that governs the competition among neighboring nodes for access to the medium. The models fall at the interface between classical queueing networks and interacting particle systems, and give rise to high-dimensional stochastic processes that challenge existing methodologies. We present various open problems and conjectures, which are supported by partial results for special cases and limit regimes as well as simulation experiments. [ABSTRACT FROM AUTHOR]

We introduce the concert (or cafeteria) queueing problem: A finite but large number of customers arrive into a queueing system that starts service at a specified opening time. Each customer is free to choose her arrival time (before or after opening time), and is interested in early service completion with minimal wait. These goals are captured by a cost function which is additive and linear in the waiting time and service completion time, with coefficients that may be class dependent. We consider a fluid model of this system, which is motivated as the fluid-scale limit of the stochastic system. In the fluid setting, we explicitly identify the unique Nash-equilibrium arrival profile for each class of customers. Our structural results imply that, in equilibrium, the arrival rate is increasing up until the closing time where all customers are served. Furthermore, the waiting queue is maximal at the opening time, and monotonically decreases thereafter. In the simple single class setting, we show that the price of anarchy (PoA, the efficiency loss relative to the socially optimal solution) is exactly two, while in the multi-class setting we develop tight upper and lower bounds on the PoA. In addition, we consider several mechanisms that may be used to reduce the PoA. The proposed model may explain queueing phenomena in diverse settings that involve a pre-assigned opening time. [ABSTRACT FROM AUTHOR]

Motivated by scheduling in cellular wireless networks and resource allocation in computer systems, we study a service facility with two classes of users having heterogeneous service requirement distributions. The aggregate service capacity is assumed to be largest when both classes are served in parallel, but giving preferential treatment to one of the classes may be advantageous when aiming at minimization of the number of users, or when classes have different economic values, for example. We set out to determine the allocation policies that minimize the total number of users in the system. For some particular cases we can determine the optimal policy exactly, but in general this is not analytically feasible. We then study the optimal policies in the fluid regime, which prove to be close to optimal in the original stochastic model. These policies can be characterized by either linear or exponential switching curves. We numerically compare our results with existing approximations based on optimization in the heavy-traffic regime. By simulations we show that, in general, our simple computable switching-curve strategies based on the fluid analysis perform well. [ABSTRACT FROM AUTHOR]

We analyze the behavior of Generalized Processor Sharing (GPS) queues with heavy-tailed service times. We compute the exact tail asymptotics of the stationary workload of an individual class and give new conditions for reduced-load equivalence and induced burstiness to hold. We also show that both phenomena can occur simultaneously. Our proofs rely on the single big event theorem and new fluid limits obtained for the GPS system that can be of interest by themselves. [ABSTRACT FROM AUTHOR]

In this paper we present a detailed analysis of queueing models with vacations and impatient customers, where the source of impatience is the absence of the server. Instead of the standard assumption that customers perform independent abandonments, we consider situations where customers abandon the system simultaneously. This is, for example, the case in remote systems where customers may decide to abandon the system, when a transport facility becomes available. [ABSTRACT FROM AUTHOR]

In this paper we study a partially ionized plasma that corresponds to an arc discharge at atmospheric pressure. We derive an inviscid hydrodynamic/diffusion limit, characterized by two temperatures, from a system of Boltzmann type transport equations modelling that plasma problem. The original property of this system is that impact ionization is a leading order collisional process. As a consequence, the density of electrons is given in terms of the density of the other species (and its temperature) via a Saha law. [ABSTRACT FROM AUTHOR]

We introduce a generalized criterion for the stability of Markovian queueing systems in terms of stochastic fluid limits. We consider an example in which this criterion may be applied: a polling system with two stations and two heterogeneous servers. [ABSTRACT FROM AUTHOR]

The subject of the paper is the stability analysis of some neural networks consisting of a finite number of interacting neurons. Following the approach of Dai [5] we use the fluid limit model of the network to derive a sufficient condition for positive Harris-recurrence of the associated Markov process. This improves the main result in Karpelevich et al. [11] and, at the same time, sheds some new light on it. We further derive two different conditions that are sufficient for transience of the state process and illustrate our results by classifying some examples according to positive recurrence or transience. [ABSTRACT FROM AUTHOR]

We consider a multi station queue with a multi class input process when any station is available for the service of only some (not all) customer classes. Upon arrival, any customer may choose one of its accessible stations according to some state dependent policy. We obtain simple stability criteria for this model in two particular cases when service rates are either station or class independent. Then, we study a two station queue under general assumptions on service rates. Our proofs are based on the fluid approximation approach. [ABSTRACT FROM AUTHOR]