Search

A 2-queue system with a single-server operating according to the combined 'Join the Shortest Queue–Serve the Longest Queue' regime is analyzed. Both cases, with or without server's switch-over times, are investigated under the non-preemptive discipline. Instead of dealing with a state space comprised of two un-bounded dimensions, a non-conventional formulation is constructed, leading to an alternative two-dimensional state space, where only one dimension is infinite. As a result, the system is defined as a quasi birth and death process and is analyzed via both the probability generating functions method and the matrix geometric formulation. Consequently, the system's two-dimensional probability mass function is derived, from which the system's performance measures, such as mean queue sizes, mean sojourn times, fraction of time the server resides in each queue, correlation coefficient between the queue sizes, and the probability mass function of the difference between the queue sizes, are obtained. Extensive numerical results for various values of the system's parameters are presented, as well as a comparison between the current non-preemptive model and its twin system of preemptive service regime. One of the conclusions is that, depending on the variability of the various parameters, the preemptive regime is not necessarily more efficient than the non-preemptive one. Finally, economic issues are discussed and numerical comparisons are presented, showing the advantages and disadvantages of each regime. [ABSTRACT FROM AUTHOR]

In 1987, J.W. Cohen analyzed the so-called Serve the Longest Queue (SLQ) queueing system, where a single server attends two non-symmetric M / G / 1 -type queues, exercising a non-preemptive priority switching policy. Cohen further analyzed in 1998 a non-symmetric 2-queue Markovian system, where newly arriving customers follow the Join the Shortest Queue (JSQ) discipline. The current paper generalizes and extends Cohen's works by studying a combined JSQ–SLQ model, and by broadening the scope of analysis to a non-symmetric 3-queue system, where arriving customers follow the JSQ strategy and a single server exercises the preemptive priority SLQ discipline. The system states' multi-dimensional probability distribution function is derived while applying a non-conventional representation of the underlying process's state-space. The analysis combines both Probability Generating Functions and Matrix Geometric methodologies. It is shown that the joint JSQ–SLQ operating policy achieves extremely well the goal of balancing between queue sizes. This is emphasized when calculating the Gini Index associated with the differences between mean queue sizes: the value of the coefficient is close to zero. Extensive numerical results are presented. [ABSTRACT FROM AUTHOR]

We study a load balancing system in the many-server heavy-traffic regime. We consider a system with N servers, where jobs arrive to the system according to a Poisson process and have an exponentially distributed size with mean 1. We parametrize the arrival rate so that the arrival rate per server is 1 - N - α , where α > 0 is a parameter that represents how fast the load grows with respect to the number of servers. The many-server heavy-traffic regime corresponds to the limit as N → ∞ , and subsumes several regimes, such as the Halfin–Whitt regime ( α = 1 / 2 ), the NDS regime ( α = 1 ), as α ↓ 0 it approximates mean field and as α → ∞ it approximates the classical heavy-traffic regime. Most of the prior work focuses on regimes with α ∈ [ 0 , 1 ] . In this paper, we focus on the case when α > 1 and the routing algorithm is power-of-d choices with d = ⌈ c N β ⌉ for some constants c > 0 and β ≥ 0 . We prove that α + β > 3 is sufficient to observe that the average queue length scaled by N 1 - α converges to an exponential random variable. In other words, if α + β > 3 , the scaled average queue length behaves similarly to the classical heavy-traffic regime. In particular, this result implies that if d is constant, we require α > 3 and if routing occurs according to JSQ we require α > 2 . We provide two proofs to our result: one based on the Transform method introduced in Hurtado-Lange and Maguluri (Stoch Syst 10(4):275–309, 2020) and one based on Stein's method. In the second proof, we also compute the rate of convergence in Wasserstein's distance. In both cases, we additionally compute the rate of convergence in expected value. All of our proofs are powered by state space collapse. [ABSTRACT FROM AUTHOR]

We consider a system of N identical server pools and a single dispatcher in which tasks with unit-exponential service requirements arrive at rate λ (N) . In order to optimize the experienced performance, the dispatcher aims to evenly distribute the tasks across the various server pools. Specifically, when a task arrives, the dispatcher assigns it to the server pool with the minimum number of tasks among d(N) randomly selected server pools. We construct a stochastic coupling to bound the difference in the system occupancy processes between the join-the-shortest-queue (JSQ) policy and a scheme with an arbitrary value of d(N). We use the coupling to derive the fluid limit in case d (N) → ∞ and λ (Ν) / Ν → λ as N → ∞ along with the associated fixed point. The fluid limit turns out to be insensitive to the exact growth rate of d(N) and coincides with that for the JSQ policy. We further establish that the diffusion limit corresponds to that for the JSQ policy as well, as long as d (N) / N log (N) → ∞ , and characterize the common limiting diffusion process. These results indicate that the JSQ optimality can be preserved at the fluid and diffusion levels while reducing the overhead by nearly a factor O(N) and O( N / log (N) ), respectively. [ABSTRACT FROM AUTHOR]

The aim of this work concerns the performance analysis of systems with interacting queues under the join the shortest queue policy. The case of two interacting queues results in a two-dimensional random walk with bounded transitions to non-neighboring states, which in turn results in complicated boundary behavior. Although this system violates the conditions of the compensation approach due to the transitions to non-neighboring states, we show how to extend the framework of the approach and how to apply it to the system at hand. Moreover, as an additional level of theoretic validation, we have compared the results obtained with the compensation approach with those obtained using the power series algorithm and we have shown that the compensation approach outperforms the power series algorithm in terms of numerical efficiency. In addition to the fundamental contribution, the results obtained are also of practical value, since our analysis constitutes a first attempt toward gaining insight into the performance of such interacting queues under the join the shortest queue policy. To fully comprehend the benefits of such a protocol, we compare its performance to the Bernoulli routing scheme as well as to that of the single relay system. Extensive numerical results show interesting insights into the system's performance. [ABSTRACT FROM AUTHOR]

The degree to which delays or queue lengths equalize under load-balancing algorithms gives a good indication of their performance. Some of the most well-known results in this context are concerned with the asymptotic behavior of the delay or queue length at the diffusion scale under a critical load condition, where arrival and service rates do not vary with time. For example, under the join-the-shortest-queue policy, the queue length deviation process, defined as the difference between the greatest and smallest queue length as it varies over time, is at a smaller scale (subdiffusive) than that of queue lengths (diffusive). The goal of this paper is to argue that subdiffusivity of the deviation process (SDDP) is not limited to heavy traffic. To exhibit the breadth of this phenomenon, we establish SDDP in three load-balancing models: power of d choices, redundancy routing, and longest queue first. Our results accommodate server heterogeneity and time-varying arrival and service intensities. Load-balancing algorithms for systems that operate in heavy traffic are known to lead, under suitable conditions, to state space collapse (SSC). This term refers to the phenomenon whereby imbalance is negligible compared with queue lengths. Specifically, whereas queue lengths behave diffusively, the size of imbalance is at a subdiffusive scale: denoting by n the usual scaling parameter, the former and the latter are of order O (n 1/2) and o (n 1/2) , respectively. In this paper we consider load balancing for time-varying systems. SSC results and the standard techniques on which they are based do not apply to these systems, which (a) are not in heavy traffic, thus queue lengths may reach levels as high as O (n) , and (b) have time-varying traffic intensities that cause transitions between underloaded, critically loaded and overloaded regimes. Our results extend SSC far beyond the heavy traffic setting, by establishing subdiffusive [i.e., o (n 1/2) ] balance for time-varying systems. To exhibit the breadth of the described phenomenon, the results address three load-balancing models. The first is the power of d choices [SQ(d)], where arrivals from a single stream are routed to the shortest among d randomly chosen queues, where 1 < d ≤ N and N denotes the fixed number of queues in the system. The second is redundancy-d [R(d)], where jobs are replicated d times and simultaneously routed to d randomly chosen queues. All, but the first, replica to be admitted into service are canceled. The third model is the longest queue first (LQF), where a single resource is shared by N job classes, and the job that receives service is always selected from the queue that is longest. As an application of these results, asymptotic optimality of SQ(d) and R(d) is shown, with an optimality guarantee of order o (n 1/2) in the aforementioned framework, where, in particular, queue sizes may reach O (n). Moreover, in the special case of the standard heavy traffic setting, the results are shown to yield new, explicit sufficient conditions for SSC. [ABSTRACT FROM AUTHOR]

Consider a queueing network with a large number N nodes, in which each queue has a dedicated input stream, and, in addition, there is an extra input stream, balancing the network load by directing its arrivals to the shortest queue(s). A mean field interaction model is set up to study the performance of this network in terms of limiting results. One of our results shows that the stationary behavior of any of the queues is approximated by that of the M / M / 1 queue with a modified arrival rate when the queue length is around zero. [ABSTRACT FROM AUTHOR]

This paper introduces a load-balancing policy that interpolates between two well-known policies, namely join the shortest queue (JSQ) and join the least workload (JLW), and studies it in heavy traffic. This policy, which we call replicate to the shortest queues (RSQ(d)), routes jobs from a stream of arrivals into buffers attached to N servers by replicating each arrival into 1 ≤ d ≤ N tasks and sending the replicas to the d shortest queues. When the first of the tasks reaches a server, its d - 1 replicas are canceled. Clearly, RSQ(1) is equivalent to JSQ, and it has been shown that RSQ(N) is equivalent to JLW; intermediate values of d provide a trade-off between good performance measures of JSQ and those of JLW. In heavy traffic, a key property underlying asymptotic analysis of load-balancing policies is state space collapse (SSC). Unlike policies such as JSQ, where SSC is well understood, the treatment of SSC under RSQ(d) requires addressing the massive cancellations that highly complicate the queue length dynamics. Our first main result is that SSC holds under RSQ(d) for possibly heterogeneous servers. Based on this result, we obtain diffusion limits for the queue lengths in the form of one-dimensional reflected Brownian motion, asymptotic characterization of the short-time-averaged delay process and a version of Reiman's snapshot principle. We illustrate using simulations that as d increases the server workloads become more balanced, and the delay distribution's tail becomes lighter. We also discuss the implementation complexity of the policy as compared to that of the redundancy routing policy, to which it is closely related. [ABSTRACT FROM AUTHOR]

We investigate the impact of delay announcements on the coordination within hospital networks using a combination of empirical observations and numerical experiments. We offer empirical evidence that suggests that patients take delay information into account when choosing emergency service providers and that such information can help increase coordination in the network, leading to improvements in the performance of the network, as measured by emergency department wait times. Our numerical results indicate that the level of coordination that can be achieved is limited by the patients' sensitivity to waiting, the load of the system, the heterogeneity among hospitals, and, importantly, the method hospitals use to estimate delays. We show that delay estimators that are based on historical averages may cause oscillation in the system and lead to higher average wait times when patients are sensitive to delay. We provide empirical evidence that suggests that such oscillations occur in hospital networks in the United States. This paper was accepted by Gad Allon, operations management. [ABSTRACT FROM AUTHOR]

We experimentally explore the effects of time limitation on decision making. Under different time allowance conditions, subjects are presented with a queueing situation and asked to join one of the two given queues. The results can be grouped under two main categories. The first one concerns the factors driving decisions in a queueing system. Only some subjects behave consistently with rationality principles and use the relevant information efficiently. The rest of the subjects seem to adopt a simpler strategy that does not incorporate some information into their decision. The second category is related to the effects of time limitation on decision performance. A substantial proportion of the population is not affected by time limitations and shows consistent behavior throughout the treatments. On the other hand, some subjects’ performance is impaired by time limitations. More importantly, this impairment is not due to the stringency of the limitation but rather to being exposed to a time constraint.

We experimentally explore the effects of time limitation on decision making. Under different time allowance conditions, subjects are presented with a queueing situation and asked to join one of the two given queues. The results can be grouped under two main categories. The first one concerns the factors driving decisions in a queueing system. Only some subjects behave consistently with rationality principles and use the relevant information efficiently. The rest of the subjects seem to adopt a simpler strategy that does not incorporate some information into their decision. The second category is related to the effects of time limitation on decision performance. A substantial proportion of the population is not affected by time limitations and shows consistent behavior throughout the treatments. On the other hand, some subjects' performance is impaired by time limitations. More importantly, this impairment is not due to the stringency of the limitation but rather to being exposed to a time constraint. [ABSTRACT FROM AUTHOR]

While vacation processes are considered to be ordinary behavior for servers, the study of queueing networks with server vacations is limited, interesting, and challenging. In this paper, we provide a unified and effective method of functional analysis for the study of a supermarket model with server multiple vacations. Firstly, we analyze a supermarket model of N identical servers with server multiple vacations, and set up an infinite-dimensional system of differential (or mean-field) equations, which is satisfied by the expected fraction vector, in terms of a technique of tailed equations. Secondly, as N→ ∞ we use the operator semigroup to provide a mean-field limit for the sequence of Markov processes, which asymptotically approaches a single trajectory identified by the unique and global solution to the infinite-dimensional system of limiting differential equations. Thirdly, we provide an effective algorithm for computing the fixed point of the infinite-dimensional system of limiting differential equations, and use the fixed point to give performance analysis of this supermarket model, including the mean of stationary queue length in any server and the expected sojourn time that any arriving customer spends in this system. Finally, we use some numerical examples to analyze how the performance measures depend on some crucial factors of this supermarket model. Note that the method of this paper will be useful and effective for performance analysis of complicated supermarket models with respect to resource management in practical areas such as computer networks, manufacturing systems and transportation networks. [ABSTRACT FROM AUTHOR]

We are concerned with an $$M/M$$-type join the shortest queue ( $$M/M$$-JSQ for short) with $$k$$ parallel queues for an arbitrary positive integer $$k$$, where the servers may be heterogeneous. We are interested in the tail asymptotic of the stationary distribution of this queueing model, provided the system is stable. We prove that this asymptotic for the minimum queue length is exactly geometric, and its decay rate is the $$k$$th power of the traffic intensity of the corresponding $$k$$ server queues with a single waiting line. For this, we use two formulations, a quasi-birth-and-death (QBD for short) process and a reflecting random walk on the boundary of the $$k+1$$-dimensional orthant. The QBD process is typically used in the literature for studying the JSQ with two parallel queues, but the random walk also plays a key roll in our arguments, which enables us to use the existing results on tail asymptotics for the QBD process. [ABSTRACT FROM AUTHOR]

We consider a new idea for a storage model on n nodes, namely stability of shape. These nodes support K neighborhoods S ⊂ {1, ..., n} and items arrive at the S as independent Poisson streams with rates λ, i = 1, ... , K . Upon arrival at S an item is stored at node j ∈ S where j is determined by some policy. Under natural conditions on the λ we exhibit simple local policies such that the multidimensional process describing the evolution of the number of items at each node is positive recurrent (stable) in shape. [ABSTRACT FROM AUTHOR]

Randomized load balancing greatly improves the sharing of resources while being simple to implement. In one such model, jobs arrive according to a rate- αN Poisson process, with α<1, in a system of N rate-1 exponential server queues. In Vvedenskaya et al. (Probl. Inf. Transm. 32:15-29, ), it was shown that when each arriving job is assigned to the shortest of D, D≥2, randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as N→∞. This is a substantial improvement over the case D=1, where queue sizes decay exponentially. The reasoning in Vvedenskaya et al. (Probl. Inf. Transm. 32:15-29, ) does not easily generalize to jobs with nonexponential service time distributions. A modularized program for treating randomized load balancing problems with general service time distributions was introduced in Bramson et al. (Proc. ACM SIGMETRICS, pp. 275-286, ). The program relies on an ansatz that asserts that, for a randomized load balancing scheme in equilibrium, any fixed number of queues become independent of one another as N→∞. This allows computation of queue size distributions and other performance measures of interest. In this article, we demonstrate the ansatz in several settings. We consider the least loaded balancing problem, where an arriving job is assigned to the queue with the smallest workload. We also consider the more difficult problem, where an arriving job is assigned to the queue with the fewest jobs, and demonstrate the ansatz when the service discipline is FIFO and the service time distribution has a decreasing hazard rate. Last, we show the ansatz always holds for a sufficiently small arrival rate, as long as the service distribution has 2 moments. [ABSTRACT FROM AUTHOR]

We are concerned with the stationary distributions of reflecting processes on multidimensional nonnegative orthants and other related processes, provided they exist. Such stationary distributions arise in performance evaluation for various queueing systems and their networks. However, it is very hard to obtain them analytically, so our interest is directed to analytically tractable characteristics. For this, we consider tail asymptotics of the stationary distributions. The purpose of this paper is twofold. We first overview the current approaches to attack the problem from a unified viewpoint. We then take up two approaches, Markov additive and analytic function approaches, which are recently developed by the author and his colleagues. We discuss their possible extensions. We mainly consider the tail asymptotics for two-dimensional reflecting processes, but also discuss how we can approach the case of more than two dimensions. [ABSTRACT FROM AUTHOR]