Abstract: This work deals with the stationary analysis of two-dimensional partially homogeneous nearest-neighbour random walks. Such random walks are characterized by the fact that the one-step transition probabilities are functions of the state-space. We show that stationary behaviour is investigated by solving a finite system of linear equations, two matrix functional equations, and a functional equation with the aid of the theory of Riemann (–Hilbert) boundary value problems. This work is strongly motivated by emerging applications in flow level performance of wireless networks that give rise in queueing models with scalable service capacity, as well as in queue-based random access protocols, where the network’s parameters are functions of the queue lengths. A simple numerical illustration, along with some details on the numerical implementation are also presented. PubDate: 2021-04-27

Abstract: In this paper, we consider a \(\text {Cox}/G_t/\infty \) infinite server queueing model in a random environment. More specifically, the arrival rate in our server is modeled as a highly fluctuating stochastic process, which arguably takes into account some small timescale variations often observed in practice. We prove a homogenization property for this system, which yields an approximation by an \(M_t/G_t/\infty \) queue with some effective parameters. Our limiting results include the description of the number of active servers, the total accumulated input and the solution of the storage equation. Hence, in the fast oscillatory context under consideration, we show how the queuing system in a random environment can be approximated by a more classical Markovian system. PubDate: 2021-04-20

Abstract: The proliferation of smart devices, computational and storage resources is predicted to continue aggressively in the near future. Such “networked” devices and resources which are distributed in a physical space and provide services are collectively referred to as a distributed service network. Assigning users or applications to available resources is important to sustain high performance of the distributed service network. In this work, we consider a one-dimensional service network where both users and resources are located on a line, and analyze a unidirectional assignment policy Move To Right (MTR), which sequentially assigns users to resources available to their right. We express the communication cost for a user-resource assignment as an increasing function of the distance traveled by the user request (request distance) and analyze the expected communication cost for the service network when locations of users and resources are modeled by different spatial point processes. We use results from the literature that map the request distance of an assigned user in a one-dimensional service network to the sojourn time of a customer in an exceptional service accessible batch queueing system. We compute the Laplace–Stieltjes transform of the sojourn time distribution for this queueing system for Poisson distributed users with general inter-resource distance distributions and in the process also generate new results for batch service queues. Unlike previous work (Panigrahy et al. in Perform Eval 142:102, 2020), our framework not only captures the first-order moment of the request distance, but also the request distance distribution itself, thus allowing us to compute the expected communication cost under different cost models. PubDate: 2021-04-17

Abstract: Order-independent (OI) queues, introduced by Berezner et al. (Queueing Syst 19(4):345–359, 1995), expanded the family of multi-class queues that are known to have a product-form stationary distribution by allowing for intricate class-dependent service rates. This paper further broadens this family by introducing pass-and-swap (P&S) queues, an extension of OI queues where, upon a service completion, the customer that completes service is not necessarily the one that leaves the system. More precisely, we supplement the OI queue model with an undirected graph on the customer classes, which we call a swapping graph, such that there is an edge between two classes if customers of these classes can be swapped with one another. When a customer completes service, it passes over customers in the remainder of the queue until it finds a customer it can swap positions with, that is, a customer whose class is a neighbor in the graph. In its turn, the customer that is ejected from its position takes the position of the next customer it can be swapped with, and so on. This is repeated until a customer can no longer find another customer to be swapped with; this customer is the one that leaves the queue. After proving that P&S queues have a product-form stationary distribution, we derive a necessary and sufficient stability condition for (open networks of) P&S queues that also applies to OI queues. We then study irreducibility properties of closed networks of P&S queues and derive the corresponding product-form stationary distribution. Lastly, we demonstrate that closed networks of P&S queues can be applied to describe the dynamics of new and existing load-distribution and scheduling protocols in clusters of machines in which jobs have assignment constraints. PubDate: 2021-04-12

Abstract: In this article, a special case of two coupled M/G/1-queues is considered, where two servers are exposed to two types of jobs that are distributed among the servers via a random switch. In this model, the asymptotic behavior of the workload buffer exceedance probabilities for the two single servers/both servers together/one (unspecified) server is determined. Hereby, one has to distinguish between jobs that are either heavy-tailed or light-tailed. The results are derived via the dual risk model of the studied coupled M/G/1-queues for which the asymptotic behavior of different ruin probabilities is determined. PubDate: 2021-04-05

Abstract: We investigate the behavior of equilibria in an M/M/1 feedback queue where price- and time-sensitive customers are homogeneous with respect to service valuation and cost per unit time of waiting. Upon arrival, customers can observe the number of customers in the system and then decide to join or to balk. Customers are served in order of arrival. After being served, each customer either successfully completes the service and departs the system with probability q, or the service fails and the customer immediately joins the end of the queue to wait to be served again until she successfully completes it. We analyze this decision problem as a noncooperative game among the customers. We show that there exists a unique symmetric Nash equilibrium threshold strategy. We then prove that the symmetric Nash equilibrium threshold strategy is evolutionarily stable. Moreover, if we relax the strategy restrictions by allowing customers to renege, in the new Nash equilibrium, customers have a greater incentive to join. However, this does not necessarily increase the equilibrium expected payoff, and for some parameter values, it decreases it. PubDate: 2021-04-01

Abstract: Motivated by the trade-off issue between delay performance and energy consumption in modern computer and communication systems, we consider a single-server queue with phase-type service requirements and with the following two special features: Firstly, the service speed is a piecewise constant function of the workload. Secondly, the server switches off when the system becomes empty, only to be activated again when the workload reaches a certain threshold. For this system, we obtain the steady-state workload distribution and its moments of any order. We use this result to choose the activation threshold such that a certain cost function, involving processing costs, activation costs and mean workload, is minimized. PubDate: 2021-03-25

Abstract: This paper presents an analysis of the stochastic recursion \(W_{i+1} = [V_iW_i+Y_i]^+\) that can be interpreted as an autoregressive process of order 1, reflected at 0. We start our exposition by a discussion of the model’s stability condition. Writing \(Y_i=B_i-A_i\) , for independent sequences of nonnegative i.i.d. random variables \(\{A_i\}_{i\in {\mathbb N}_0}\) and \(\{B_i\}_{i\in {\mathbb N}_0}\) , and assuming \(\{V_i\}_{i\in {\mathbb N}_0}\) is an i.i.d. sequence as well (independent of \(\{A_i\}_{i\in {\mathbb N}_0}\) and \(\{B_i\}_{i\in {\mathbb N}_0}\) ), we then consider three special cases (i) \(V_i\) equals a positive value a with certain probability \(p\in (0,1)\) and is negative otherwise, and both \(A_i\) and \(B_i\) have a rational LST, (ii) \(V_i\) attains negative values only and \(B_i\) has a rational LST, (iii) \(V_i\) is uniformly distributed on [0, 1], and \(A_i\) is exponentially distributed. In all three cases, we derive transient and stationary results, where the transient results are in terms of the transform at a geometrically distributed epoch. PubDate: 2021-03-13

Abstract: We provide a novel expression of the scale function for a Lévy process with negative phase-type jumps. It is in terms of a certain transition rate matrix which is explicit up to a single positive number. A monotone iterative scheme for the calculation of the latter is presented and it is shown that the error decays exponentially fast. Our numerical examples suggest that this algorithm allows us to employ phase-type distributions with hundreds of phases, which is problematic when using the known formula for the scale function in terms of roots. Extensions to other distributions, such as matrix-exponential and infinite-dimensional phase-type, can be anticipated. PubDate: 2021-03-08 DOI: 10.1007/s11134-021-09696-w

Abstract: The Adaptive MaxWeight policy achieves optimal throughput for switches with nonzero reconfiguration delay and has been shown to have good delay performance in simulation. In this paper, we analyze the queue length behavior of a switch with nonzero reconfiguration delay operating under the Adaptive MaxWeight. We first show that the Adaptive MaxWeight policy exhibits a weak state space collapse behavior in steady state, which can be viewed as an inheritance of a similar property of the MaxWeight policy in a switch with zero reconfiguration delay. The weak state space collapse result is then utilized to obtain an asymptotically tight bound on an expression involving the steady-state queue length and the probability of reconfiguration for the Adaptive MaxWeight policy in the heavy traffic regime. We then derive the relation between the expected schedule duration and the steady-state queue length through Lyapunov drift analysis and characterize bounds for the expected steady-state queue length. While the resulting queue length bounds are not asymptotically tight, they suggest an approximate queue length scaling behavior, which approaches the optimal scaling with respect to the traffic load and the reconfiguration delay when the hysteresis function of the Adaptive MaxWeight policy approaches a linear function. PubDate: 2021-03-05 DOI: 10.1007/s11134-021-09695-x

Abstract: Pay-for-priority is a common practice in congestion-prone service systems. The extant literature on this topic restricts attention to the case where the only epoch for customers to purchase priority is upon arrival, and if customers choose not to upgrade when they arrive, they cannot do so later during their wait. A natural alternative is to let customers pay and upgrade to priority at any time during their stay in the queue, even if they choose not to do so initially. This paper builds a queueing-game-theoretic model that explicitly captures self-interested customers’ dynamic in-queue priority-purchasing behavior. When all customers (who have not upgraded yet) simultaneously decide whether to upgrade, we find in our model that pure-strategy equilibria do not exist under some intuitive criteria, contrasting the findings in classical models where customers can only purchase priority upon arrival. However, when customers sequentially decide whether to upgrade, threshold-type pure-strategy equilibria may exist. In particular, under sufficiently light traffic, if the number of ordinary customers accumulates to a certain threshold, then it is always the second last customer who upgrades, but in general, it could be a customer from another position, and the queue-length threshold that triggers an upgrade can also vary with the traffic intensity. Finally, we find that in-queue priority purchase subject to the sequential rule yields less revenue than upon-arrival priority purchase in systems with small buffers. PubDate: 2021-03-05 DOI: 10.1007/s11134-021-09694-y

Abstract: The traditional approach when looking for a symmetric equilibrium behavior in queueing models with strategic customers who arrive according to some stationary arrival process is to look for a strategy which, if used by all, is also a best response of an individual customer under the resulting stochastic steady-state conditions. This description lacks a key component: a proper definition of the set of players. Hence, many of these models cannot be defined as proper noncooperative games. This limitation raises two main concerns. First, it is hard to formulate these models in a canonical way, and hence, results are typically limited to a specific model or to a narrow class of models. Second, game theoretic results cannot be applied directly in the analysis of such models and call for ad hoc adaptations. We suggest a different approach, one that is based on the stationarity of the underlying stochastic processes. In particular, instead of considering a system that is functioning from time immemorial and has already reached stochastic steady-state conditions, we look at the process as a series of isolated, a priori identical, and independent strategic situations with a random, yet finite, set of players. Each of the isolated games can be analyzed using existing tools from the classical game theoretic literature. Moreover, this approach suggests a canonic definition of strategic queueing models as properly defined mathematical objects. A significant advantage of our approach is its compatibility with models in the existing literature. This is exemplified in detail for the famous model of the unobservable “to queue or not to queue” problem and other related models. PubDate: 2021-02-20 DOI: 10.1007/s11134-021-09692-0

Abstract: We consider an acyclic network of single-server queues with heterogeneous processing rates. It is assumed that each queue is fed by the superposition of a large number of i.i.d. Gaussian processes with stationary increments and positive drifts, which can be correlated across different queues. The flow of work departing from each server is split deterministically and routed to its neighbors according to a fixed routing matrix, with a fraction of it leaving the network altogether. We study the exponential decay rate of the probability that the steady-state queue length at any given node in the network is above any fixed threshold, also referred to as the ‘overflow probability’. In particular, we first leverage Schilder’s sample-path large deviations theorem to obtain a general lower bound for the limit of this exponential decay rate, as the number of Gaussian processes goes to infinity. Then, we show that this lower bound is tight under additional technical conditions. Finally, we show that if the input processes to the different queues are nonnegatively correlated, non-short-range dependent fractional Brownian motions, and if the processing rates are large enough, then the asymptotic exponential decay rates of the queues coincide with the ones of isolated queues with appropriate Gaussian inputs. PubDate: 2021-02-18 DOI: 10.1007/s11134-021-09689-9

Abstract: We present a broad literature survey of parameter and state estimation for queueing systems. Our approach is based on various inference activities, queueing models, observations schemes, and statistical methods. We categorize these into branches of research that we call estimation paradigms. These include: the classical sampling approach, inverse problems, inference for non-interacting systems, inference with discrete sampling, inference with queueing fundamentals, queue inference engine problems, Bayesian approaches, online prediction, implicit models, and control, design, and uncertainty quantification. For each of these estimation paradigms, we outline the principles and ideas, while surveying key references. We also present various simple numerical experiments. In addition to some key references mentioned here, a periodically updated comprehensive list of references dealing with parameter and state estimation of queues will be kept in an accompanying annotated bibliography. PubDate: 2021-02-17 DOI: 10.1007/s11134-021-09688-w

Abstract: A broad class of parallel server systems is considered, for which we prove the steady-state asymptotic independence of server workloads, as the number of servers goes to infinity, while the system load remains sub-critical. Arriving jobs consist of multiple components. There are multiple job classes, and each class may be of one of two types, which determines the rule according to which the job components add workloads to the servers. The model is broad enough to include as special cases some popular queueing models with redundancy, such as cancel-on-start and cancel-on-completion redundancy. Our analysis uses mean-field process representation and the corresponding mean-field limits. In essence, our approach relies almost exclusively on three fundamental properties of the model: (a) monotonicity, (b) work conservation and (c) the property that, on average, “new arriving workload prefers to go to servers with lower workloads.” PubDate: 2021-02-17 DOI: 10.1007/s11134-021-09686-y

Abstract: We study the problem of strategic choice of arrival time to a single-server queue with opening and closing times when there is uncertainty regarding service speed. A Poisson population of customers choose their arrival time with the goal of minimizing their expected waiting times and are served on a first-come first-served basis. There are two types of customers that differ in their beliefs regarding the service-time distribution. The inconsistent beliefs may arise from randomness in the server state along with noisy signals that customers observe. Customers are aware of the two types of populations with differing beliefs. We characterize the Nash equilibrium dynamics for exponentially distributed service times and show how they substantially differ from the model with homogeneous customers. We further provide an explicit solution for a fluid approximation of the game. For general service-time distributions we provide an algorithm for computing the equilibrium in a discrete-time setting. We find that in equilibrium customers with different beliefs arrive during different (and often disjoint) time intervals. Numerical analysis further shows that the mean waiting time increases with the coefficient of variation of the service time. Furthermore, we present a learning agent-based model (ABM) in which customers make joining decisions based solely on their signals and past experience. We numerically compare the long-term average outcome of the ABM with that of the equilibrium and find that the arrival distributions are quite close if we assume (for the equilibrium solution) that customers are fully rational and have knowledge of the system parameters, while they may greatly differ if customers have limited information or computing abilities. PubDate: 2021-01-28 DOI: 10.1007/s11134-020-09683-7

Abstract: This paper introduces non-cooperative games on a network of single server queues with fixed routes. A player has a set of routes available and has to decide which route(s) to use for its customers. Each player’s goal is to minimize the expected sojourn time of its customers. We consider two cases: a continuous strategy space, where each player is allowed to divide its customers over multiple routes, and a discrete strategy space, where each player selects a single route for all its customers. For the continuous strategy space, we show that a unique pure-strategy Nash equilibrium exists that can be found using a best-response algorithm. For the discrete strategy space, we show that the game has a Nash equilibrium in mixed strategies, but need not have a pure-strategy Nash equilibrium. We show the existence of pure-strategy Nash equilibria for four subclasses: (i) N-player games with equal arrival rates for the players, (ii) 2-player games with identical service rates for all nodes, (iii) 2-player games on a \(2\times 2\) -grid, and (iv) 2-player games on an \(A\times B\) -grid with small differences in the service rates. PubDate: 2021-01-25 DOI: 10.1007/s11134-020-09681-9