We consider a tandem queue with coupled processors, which is subject to global breakdowns. When the network is in the operating mode and both queues are non empty, the total service capacity is shared among the stations according to fixed proportions. When one of the stations becomes empty, the total service capacity is given to the non-empty station. Moreover, arrival rates depend on the state of the network. The system is described by a Markov modulated random walk in the quarter plane representing the number of jobs in the two stations and the state of the network. By applying the generating function approach, we first apply the power series approximation method to obtain power series expansions of the generating function of the stationary queue lengths for both network states. Then, we also provide a way to derive the generating function of the stationary queue lengths for both network states in terms of the solution of a Riemann-Hilbert boundary value problem. Numerical results are obtained to show insights in the system performance.
Queues with coupled processors were initially studied in @cite_35 . To gain quantitative insights about the queueing process, they derived a solution for the generating function of the stationary joint queue-length distribution using the theory of Riemann-Hilbert boundary value problems. Later, in @cite_5 a systematic and detailed study of the technique of reducing a two dimensional functional equation of a random walk or queueing model to a boundary value problem was presented, while several numerical issues were discussed. Important generalizations were given in @cite_9 @cite_7 @cite_4 @cite_15 @cite_27 @cite_36 @cite_16 @cite_3 @cite_33 @cite_38 @cite_14 (not exhaustive list) where various two-dimensional queueing models with the aid of the theory of Riemann (-Hilbert) boundary value problems.
@cite_35 @cite_38 @cite_14 @cite_4 @cite_33 @cite_7 @cite_36 @cite_9 @cite_3 @cite_27 @cite_5 @cite_15 @cite_16
2171734367 2142006463 2102860267 2110840677 2032312967 2256216618 2836117655 1995626820 2013566131 1510598052 1993949882 2061823767 2059060883 2073121338 2156168464 2132210216 2006267017 2614091483 1495091143 2015774390
We consider a tandem queue with coupled processors and analyze the two-dimensional Markov process representing the numbers of jobs in the two stations. A functional equation for the generating function of the stationary distribution of this two-dimensional process is derived and solved through the theory of Riemann-Hilbert boundary value problems. In Resing and Ormeci [16] it is shown that the two-stage tandem queue with coupled processors can be solved using the theory of boundary value problems. In this paper we consider the issues that arise when calculating performance measures like the mean queue length and the fraction of time a station is empty. It is assumed that jobs arrive at the first station according to a Poisson process and require service at both stations before leaving the system. The amount of work that a job requires at each of the stations is an independent, exponentially distributed random variable. When both stations are nonempty, the total service capacity is shared among the stations according to fixed proportions. When one of the stations becomes empty, the total service capacity is given to the nonempty station. We study the two-dimensional Markov process representing the numbers of jobs at the two stations. The problem of finding the generating function of the stationary distribution can be reduced to two different Riemann-Hilbert boundary value problems, where both problems yield a complete analytical solution. We discuss the similarities and differences between the two problems, and relate them to the computational aspects of obtaining performance measures. We develop power series approximations for a discrete-time queueing system with two parallel queues and one processor. If both queues are nonempty, a customer of queue 1 is served with probability β, and a customer of queue 2 is served with probability 1?β. If one of the queues is empty, a customer of the other queue is served with probability 1. We first describe the generating function U(z 1,z 2) of the stationary queue lengths in terms of a functional equation, and show how to solve this using the theory of boundary value problems. Then, we propose to use the same functional equation to obtain a power series for U(z 1,z 2) in β. The first coefficient of this power series corresponds to the priority case β=0, which allows for an explicit solution. All higher coefficients are expressed in terms of the priority case. Accurate approximations for the mean stationary queue lengths are obtained from combining truncated power series and Pade approximation. This paper presents a novel technique for deriving asymptotic expressions for the occurrence of rare events for a random walk in the quarter plane. In particular, we study a tandem queue with Poisson arrivals, exponential service times and coupled processors. The service rate for one queue is only a fraction of the global service rate when the other queue is non-empty; when one queue is empty, the other queue has full service rate. The bivariate generating function of the queue lengths gives rise to a functional equation. In order to derive asymptotic expressions for large queue lengths, we combine the kernel method for functional equations with boundary value problems and singularity analysis. We derive in this paper closed formulae for the joint probability generating function of the number of customers in the two FIFO queues of a generalized processor-sharing (GPS) system with two classes of customers arriving according to Poisson processes and requiring exponential service times. In contrast to previous studies published on the GPS system, we show that it is possible to establish explicit expressions for the generating functions of the number of customers in each queue without calling for the formulation of a Riemann-Hilbert problem. We specifically prove that the problem of determining the unknown functions due to the reflecting conditions on the boundaries of the positive quarter plane can be reduced to a Poisson equation. The explicit formulae are then used to derive some characteristics of the GPS system (in particular the tails of the probability distributions of the numbers of customers in each queue). Renyi’s parking problem (or 1D sequential interval packing problem) dates back to 1958, when Renyi studied the following random process: Consider an interval I of length x, and sequentially and randomly pack disjoint unit intervals in I until the remaining space prevents placing any new segment. The expected value of the measure of the covered part of I is M(x), so that the ratio M(x) x is the expected filling density of the random process. Following recent work by [4], we studied the discretized version of the above process by considering the packing of the 1D discrete lattice interval 1, 2,…,n + 2k − 1 with disjoint blocks of (k + 1) integers but, as opposed to the mentioned [4] result, our exclusion process is symmetric, hence more natural. Furthermore, we were able to obtain useful recursion formulas for the expected number of r-gaps (0 ≤ r ≤ k) between neighboring blocks. We also provided very fast converging series and extensive computer simulations for these expected numbers, so that the limiting filling density of the long line segment (as n →∞) is Renyi’s famous parking constant, 0.7475979203…. Several queueing processes may be modeled as random walks on a multidimensional grid. In this paper the equilibrium distribution for the case of a two-dimensional grid is considered. In previous research it has been shown that for some two-dimensional random walks the equilibrium distribution has the form of an infinite series of products of powers which can be constructed with a compensation procedure. The object of the present paper is to investigate under which conditions such an elegant solution exists and may be found with a compensation approach. The conditions can be easily formulated in terms of the random behaviour in the inner area and the drift on the boundaries. An important class of queueing networks is characterized by the following feature: in contrast with ordinary units, a disaster may remove all work from the network. Applications of such networks include computer networks with virus infection, migration processes with mass exodus and serial production lines with catastrophes. In this paper, we deal with a two-stage tandem queue with blocking operating under die presence of a secondary flow of disasters. The arrival flows of units and disasters are general Markovian arrival processes. Using spectral analysis, we determine the stationary distribution at departure epochs. That distribution enables us to derive the distribution of the number of units which leave the network at a disaster epoch, We calculate the stationary distribution at an arbitrary time and, finally, we give numerical results and graphs for certain probabilistic descriptors of the network. This paper is a survey of certain known results concerning networks of queues. The choice of the topics presented has been made with special emphasis on mathematical results which can be applied to the analysis and synthesis of mathematical or simulation models of complex computer systems in which an ensemble of resources is shared among a set of user programs. The subjects covered include the Jackson, and Gordon and Newell theorems; the work-rate theorems of Chang, Lavenberg and Traiger; the Baskett, Chandy, Muntz, Palacios results. We also discuss in a unified manner problems related to Poisson processes in queueing networks. Companion papers (Parts II, III) will present results concerning approximations to queueing networks and some of their applications to computer system performance evaluation. We study a processing system comprised of parallel queues, whose individual service rates are specified by a global service mode (configuration). The issue is how to switch the system between various possible service modes, so as to maximize its throughput and maintain stability under the most workload-intensive input traffic traces (arrival processes). Stability preserves the job inflow–outflow balance at each queue on the traffic traces. Two key families of service policies are shown to maximize throughput, under the mild condition that traffic traces have long-term average workload rates. In the first family of cone policies, the service mode is chosen based on the system backlog state belonging to a corresponding cone. Two distinct policy classes of that nature are investigated, MaxProduct and FastEmpty. In the second family of batch policies (BatchAdapt), jobs are collectively scheduled over adaptively chosen horizons, according to an asymptotically optimal, robust schedule. The issues of nonpreemptive job processing and non-negligible switching times between service modes are addressed. The analysis is extended to cover feed-forward networks of such processing systems nodes. The approach taken unifies and generalizes prior studies, by developing a general trace-based modeling framework (sample-path approach) for addressing the queueing stability problem. It treats the queueing structure as a deterministic dynamical system and analyzes directly its evolution trajectories. It does not require any probabilistic superstructure, which is typically used in previous approaches. Probability can be superposed later to address finer performance questions (e.g., delay). The throughput maximization problem is seen to be primarily of structural nature. The developed methodology appears to have broader applicability to other queueing systems. Two independent Poisson streams of jobs flow into a single-server service system having a limited common buffer that can hold at most one job. If a type-i job (i = 1,2) finds the server busy, it is blocked and routed to a separate type-i retrial (orbit) queue that attempts to re-dispatch its jobs at its specific Poisson rate. This creates a system with three dependent queues. Such a queueing system serves as a model for two competing job streams in a carrier sensing multiple access system. We study the queueing system using multi-dimensional probability generating functions, and derive its necessary and sufficient stability conditions while solving a Riemann- Hilbert boundary value problem. Various performance measures are calculated and numerical results are presented. In particular, numerical results demonstrate that the proposed multiple access system with two types of jobs and constant retrial rates provides incentives for the users to respect their contracts. Most existing discussions regarding the time-dependent distribution of queue length was undertaken in the context of isolated intersections. However, computing queue length distributions for a signalized network with generic topology is very challenging because such process involves convolution and nonlinear transformation of random variables, which is analytically intractable. To address such issue, this study proposes a stochastic queue model considering the strong interdependence relations between adjacent intersections using the probability generating function as a mathematical tool. Various traffic flow phenomena, including queue formation and dissipation, platoon dispersion, flow merging and diverging, queue spillover, and downstream blockage, are formulated as stochastic events, and their distributions are iteratively computed through a stochastic network loading procedure. Both theoretical derivation and numerical investigations are presented to demonstrate the effectiveness of the proposed approach in analyzing the delay and queues of signalized networks under different congestion levels. .We consider a class of stochastic processing networks. Assume that the networks satisfy a complete resource pooling condition. We prove that each maximum pressure policy asymptotically minimizes the workload process in a stochastic processing network in heavy traffic. We also show that, under each quadratic holding cost structure, there is a maximum pressure policy that asymptotically minimizes the holding cost. A key to the optimality proofs is to prove a state space collapse result and a heavy traffic limit theorem for the network processes under a maximum pressure policy. We extend a framework of Bramson [Queueing Systems Theory Appl. 30 (1998) 89–148] and Williams [Queueing Systems Theory Appl. 30 (1998b) 5–25] from the multiclass queueing network setting to the stochastic processing network setting to prove the state space collapse result and the heavy traffic limit theorem. The extension can be adapted to other studies of stochastic processing networks. 1. Introduction. This paper is a continuation of Dai and Lin (2005), in which maximum pressure policies are shown to be throughput optimal for a class of stochastic processing networks. Throughput optimality is an important, first-order objective for many networks, but it ignores some key secondary performance measures like queueing delays experienced by jobs in these networks. In this paper we show that maximum pressure policies enjoy additional optimality properties; they are asymptotically optimal in minimizing a certain workload or holding cost of a stochastic processing network. Stochastic processing networks have been introduced in a series of three papers by Harrison (2000, 2002, 2003). In Dai and Lin (2005) and this paper we consider a special class of Harrison’s model. This class of stochastic processing networks is much more general than multiclass queueing networks that have been a subject of intensive study in the last 20 years; see, for example, Harrison (1988), Williams We consider the double queue that arises when arriving customers simultaneously place two demands handled independently by two servers. It is assumed that the customer arrivals form a Poisson process with mean 1, the servers have exponential service times with rate @math , and @math , which insures stability of the queue. Let @math be the respective lengths of the @math - and @math -queues, and @math at equilibrium. In a previous paper with the same title we obtained a formula for the generating function @math . We use this to derive the asymptotic behavior of @math as @math . The asymptotic results are employed to study the interdependence of @math . We derive limit laws for the expectation and distribution for either of these random variables conditioned on the other. The authors develop a theory characterizing optimal stopping times for discrete-time ergodic Markov processes with discounted rewards. The theory differs from prior work by its view of per-stage and terminal reward functions as elements of a certain Hilbert space. In addition to a streamlined analysis establishing existence and uniqueness of a solution to Bellman's equation, this approach provides an elegant framework for the study of approximate solutions. In particular, the authors propose a stochastic approximation algorithm that tunes weights of a linear combination of basis functions in order to approximate a value function. They prove that this algorithm converges (almost surely) and that the limit of convergence has some desirable properties. The utility of the approximation method is illustrated via a computational case study involving the pricing of a path dependent financial derivative security that gives rise to an optimal stopping problem with a 100-dimensional state space. We study communication networks that employ drop-tail queueing and Additive-Increase Multiplicative-Decrease (AIMD) congestion control algorithms. It is shown that the theory of nonnegative matrices may be employed to model such networks. In particular, important network properties, such as: 1) fairness; 2) rate of convergence; and 3) throughput, can be characterized by certain nonnegative matrices. We demonstrate that these results can be used to develop tools for analyzing the behavior of AIMD communication networks. The accuracy of the models is demonstrated by several NS studies. We investigate performance limits of a multiple access communication system with energy harvesting nodes where the utility function is taken to be the long-term average sum-throughput. We assume a causal structure for energy arrivals and study the problem in the continuous time regime. For this setting, we first characterize a storage dam model that captures the dynamics of a battery with energy harvesting and variable transmission power. Using this model, we next establish an upper bound on the throughput problem as a function of battery capacity. We also formulate a nonlinear optimization problem to determine optimal achievable power policies for transmitters. Applying a calculus of variations technique, we then derive Euler-Lagrange equations as necessary conditions for optimum power policies in terms of a system of coupled partial integro-differential equations. Based on a Gauss-Seidel algorithm, we devise an iterative algorithm to solve these equations. We also propose a fixed-point algorithm for the symmetric multiple access setting in which the statistical descriptions of energy harvesters are identical. To further support our iterative algorithms, along with the analysis, comprehensive numerical results are also obtained. We consider the problem of computing the convolution of two long vectors using parallel processing units in the presence of "stragglers". Stragglers refer to the small fraction of faulty or slow processors that delays the entire computation in time-critical distributed systems. We first show that splitting the vectors into smaller pieces and using a linear code to encode these pieces provides better resilience against stragglers than replication-based schemes under a simple, worst-case straggler analysis. We then demonstrate that under commonly used models of computation time, coding can dramatically improve the probability of finishing the computation within a target "deadline" time. As opposed to the more commonly used technique of expected computation time analysis, we quantify the exponents of the probability of failure in the limit of large deadlines. Our exponent metric captures the probability of failing to finish before a specified deadline time, i.e. , the behavior of the "tail". Moreover, our technique also allows for simple closed form expressions for more general models of computation time, e.g. shifted Weibull models instead of only shifted exponentials. Thus, through this problem of coded convolution, we establish the utility of a novel asymptotic failure exponent analysis for distributed systems. Consider a critical branching random walk on the real line. In a recent paper, Aidekon (2011) developed a powerful method to obtain the convergence in law of its minimum after a log-factor translation. By an adaptation of this method, we show that the point process formed by the branching random walk seen from the minimum converges in law to a decorated Poisson point process. This result, confirming a conjecture of Brunet and Derrida (J Stat Phys 143:420–446, 2011), can be viewed as a discrete analog of the corresponding results for the branching Brownian motion, previously established by (2010, 2011) and (2011). In a Fork-Join (FJ) queueing system an upstream fork station splits incoming jobs into N tasks to be further processed by N parallel servers, each with its own queue; the response time of one job is determined, at a downstream join station, by the maximum of the corresponding tasks' response times. This queueing system is useful to the modelling of multi-service systems subject to synchronization constraints, such as MapReduce clusters or multipath routing. Despite their apparent simplicity, FJ systems are hard to analyze. This paper provides the first computable stochastic bounds on the waiting and response time distributions in FJ systems. We consider four practical scenarios by combining 1a) renewal and 1b) non-renewal arrivals, and 2a) non-blocking and 2b) blocking servers. In the case of non blocking servers we prove that delays scale as O(logN), a law which is known for first moments under renewal input only. In the case of blocking servers, we prove that the same factor of log N dictates the stability region of the system. Simulation results indicate that our bounds are tight, especially at high utilizations, in all four scenarios. A remarkable insight gained from our results is that, at moderate to high utilizations, multipath routing 'makes sense' from a queueing perspective for two paths only, i.e., response times drop the most when N = 2; the technical explanation is that the resequencing (delay) price starts to quickly dominate the tempting gain due to multipath transmissions.