Quasi-reversible multiclass queues with order independent departure rates

This paper introduces a new class of queues which are quasi-reversible and therefore preserve product form distribution when connected in multinode networks. The essential feature leading to the quasi-reversibility of these queues is the fact that the total departure rate in any queue state is independent of the order of the customers in the queue. We call such queues order independent (OI) queues. The OI class includes a significant part of Kelly's class of symmetric queues, although it does not cover the whole class. A distinguishing feature of the OI class is that, among others, it includes the MSCCC and MSHCC queues but not the LCFS queue. This demonstrates a certain generality of the class of OI queues and shows that the quasi-reversibility of the OI queues derives from causes other than symmetry principles. Finally, we examine OI queues where arrivals to the queue are lost when the number of customers in the queue equals an upper bound. We obtain the stationary distribution for the OI loss queue by normalizing the stationary probabilities of the corresponding OI queue without losses. A teletraffic application for the OI loss queue is presented.     

Inclusion-exclusion: Exact and approximate

It is often required to find the probability of the union of givenn eventsA ₁ ,...,A _n . The answer is provided, of course, by the inclusion-exclusion formula: Pr(A _i )= _i – _i<j Pr(A _i A _j )±.... Unfortunately, this formula has exponentially many terms, and only rarely does one manage to carry out the exact calculation. From a computational point of view, finding the probability of the union is an intractable, #P-hard problem, even in very restricted cases. This state of affairs makes it reasonable to seek approximate solutions that are computationally feasible. Attempts to find such approximate solutions have a long history starting already with Boole [1]. A recent step in this direction was taken by Linial and Nisan [4] who sought approximations to the probability of the union, given the probabilities of allj-wise intersections of the events forj=1,...k. The developed a method to approximate Pr(A _i ), from the above data with an additive error of exp . In the present article we develop an expression that can be computed in polynomial time, that, given the sums _|S|=j Pr( _iS A _i ) forj=1,...k, approximates Pr(A _i ) with an additive error of exp . This error is optimal, up to the logarithmic factor implicit in the notation.The problem of enumerating satisfying assignments of a boolean formula in DNF formF=v _l ^m C _i is an instance of the general problem that had been extensively studied [7]. HereA _i is the set of assignments that satisfyC _i , and Pr( _iS A _i )=a _S /2ⁿ where _iS C _i is satisfied bya _S assignments. Judging from the general results, it is hard to expect a decent approximation ofF's number of satisfying assignments, without knowledge of the numbersa _S for, say, all cardinalities . Quite surprisingly, already the numbersa _S over |S|log(n+1)uniquely determine the number of satisfying assignments for F.We point out a connection between our work and the edge-reconstruction conjecture. Finally we discuss other special instances of the problem, e.g., computing permanents of 0,1 matrices, evaluating chromatic polynomials of graphs and for families of events whose VC dimension is bounded.Work supported in part by a grant of the Binational Israel-US Science Foundation.Work supported in part by a grant of the Binational Israel-US Science Foundation and by the Israel Science Foundation.     

Exact and approximate numerical solutions to steady-state single-server queues:M/G/1 — a unified approach

This paper presents a unified approach for the numerical solutions of anM/G/1 queue. On the assumption that the service-time distribution has a rational Laplace-Stieltjes transform (LST), explicit closed-form expressions have been obtained for moments, distributions of system length and waiting time (in queue) in terms of the roots of associated characteristic equations (c.e.'s). Approximate analyses for the tails of the distributions based on one or more roots are also discussed. Numerical aspects have been tested for a variety of complex service-time distributions including but not restricted to only mixed generalized Erlang and generalized hyperexponential. A sample of numerical computations is also included. It is hoped that the results obtained would prove to be beneficial to both practitioners and theorists dealing with bounds, inequalities, approximations, and other aspects.     

Queue-length balance equations in multiclass multiserver queues and their generalizations

A classical result for the steady-state queue-length distribution of single-class queueing systems is the following: The distribution of the queue length just before an arrival epoch equals the distribution of the queue length just after a departure epoch. The constraint for this result to be valid is that arrivals, and also service completions, with probability one occur individually, i.e., not in batches. We show that it is easy to write down somewhat similar balance equations for multidimensional queue-length processes for a quite general network of multiclass multiserver queues. We formally derive those balance equations under a general framework. They are called distributional relationships and are obtained for any external arrival process and state-dependent routing as long as certain stationarity conditions are satisfied and external arrivals and service completions do not simultaneously occur. We demonstrate the use of these balance equations, in combination with PASTA, by (1) providing very simple derivations of some known results for polling systems and (2) obtaining new results for some queueing systems with priorities. We also extend the distributional relationships for a nonstationary framework.     

Expulsion and scheduling control for multiclass queues with heterogeneous servers

We consider an M/M/2 system with nonidentical servers and multiple classes of customers. Each customer class has its own reward rate and holding cost. We may assign priorities so that high priority customers may preempt lower priority customers on the servers. We give two models for which the optimal admission and scheduling policy for maximizing expected discounted profit is determined by a threshold structure on the number of customers of each type in the system. Surprisingly, the optimal thresholds do not depend on the specific numerical values of the reward rates and holding costs, making them relatively easy to determine in practice. Our results also hold when there is a finite buffer and when customers have independent random deadlines for service completion.     

Interconnected networks of queues with randomized arrival and departure blocking

In this paper, we study two interconnected multiclass non-exponential queueing networks. Jobs can jump from one cluster to another, but subject to randomized blocking depending on the class occupancies. Such systems naturally arise in communication networks, like Metropolitan Area Networks. We present sufficient conditions for the existence of a product form equilibrium distribution under both the recirculate and the stop blocking protocol. A number of examples are given.     

On the departure process of a leaky bucket system with long-range dependent input traffic

Due to the strong experimental evidence that the traffic to be offered to future broadband networks will display long-range dependence, it is important to study the possible implications that such traffic may have for the design and performance of these networks. In particular, an important question is whether the offered traffic preserves its long-range dependent nature after passing through a policing mechanism at the interface of the network. One of the proposed solutions for flow control in the context of the emerging ATM standard is the so-called leaky bucket scheme. In this paper we consider a leaky bucket system with long-range dependent input traffic. We adopt the following popular model for long-range dependent traffic: Time is discrete. At each unit time a random number of sessions is initiated, having the distribution of a Poisson random variable with mean λ. Each of these sessions has a random duration τ, where the integer random variable τ has finite mean, infinite variance, and a regularly varying tail, i.e., P(τ >К) ~ К^-Lα L(К), where 1 < α < 2 L(·) is a slowly varying function. Once a session is initiated, it generates one cell at each unit of time until its termination. We examine the departure process of the leaky bucket policing mechanism driven by such an arrival process, and show that it too is long-range dependent for any token buffer size and any - finite or infinite - cell buffer size. Moreover, upper and lower bounds for the covariance sequence of the output process are established. The above results demonstrate that long-range dependence cannot be removed by the kinds of flow control schemes that are currently being envisioned for broadband networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

The quadratic three-dimensional assignment problem: Exact and approximate solution methods

This paper reports on algorithm development for solving the quadratic three-dimensional assignment problem (Q3AP). The Q3AP arises, for example, in the implementation of a hybrid ARQ (automatic repeat request) scheme for enriching diversity among multiple packet re-transmissions, by optimizing the mapping of data bits to modulation symbols. Typical practical problem sizes would be 8, 16, 32 and 64.     

The pricing problem. Part I: Exact and approximate algorithms

In the article we consider the pricing problem and show it to be NP-hard in the strong sense. Some exact and approximate algorithms are developed based on decomposition, genetic local search, and tabu search. The results of some computational experiments are provided.     

Exact and approximate solutions of time-fractional models arising from physics via Shehu transform

In this present investigation, we proposed a reliable and new algorithm for solving time-fractional differential models arising from physics and engineering. This algorithm employs the Shehu transform method, and then nonlinearity term is decomposed. We apply the algorithm to solve many models of practical importance and the outcomes show that the method is efficient, precise, and easy to use. Closed form solutions are obtained in many cases, and exact solutions are obtained in some special cases. Furthermore, solution profiles are presented to show the behavior of the obtained results in other to better understand the effect of the fractional order.     

Exact and approximate correctors for stochastic Hamiltonians: the 1-dimensional case

We perform a qualitative investigation of critical Hamilton–Jacobi equations, with stationary ergodic Hamiltonian, in dimension 1. We show the existence of approximate correctors, give characterizing conditions for the existence of correctors, provide Lax-type representation formulae and establish comparison principles. The results are applied to look into the corresponding effective Hamiltonian and to study a homogenization problem. In the analysis a crucial role is played by tools from stochastic geometry such as, for instance, closed random stationary sets.     

Exact and approximate pulsed beam solutions of Maxwell's equations

An exact solution of Maxwell's equations is constructed which represents a pulse of finite energy propagating along a given axis. To simplify the computation of such a pulse, an approximate solution is constructed as a superposition of solutions of the paraxial equation. This approximation is vectorial in nature and satisfies the divergence-free condition. The difference between the exact and approximate solutions is estimated relative to the total energy transfer of the exact solution.     

Burst reduction properties of rate-control throttles: departure process

In this paper we study the departure processes of two rate-control throttles: the token bank and the leaky bucket. Using sample path methods and the notion of majorization, we analyze the effect that parameters such as the token buffer capacity and token generation rate have on the vector of interdeparture times. In the transient case, we establish the monotonicity of the burst reduction in the sense of the majorization. In the case that the departure process converges in coupling to a stationary and ergodic process, the transient comparison results allow us to establish the monotonicity of the stationary interdeparture times in the sense of the convex ordering. Comparisons between the two flow control schemes are also established when appropriate.The work of this author was supported in part by the CEC DG XIII under the ESPRIT BRA grant QMIPS.The work of this author was supported in part by the National Science Foundation under grants ASC 88-8802764 and NCR-9116183.     

Exact and approximate solutions to the multisource weber problem

The problem considered is the choice of locations form sources so as to minimize the sum of weighted distances betweenn fixed sinks and the source closest to each sink. The weights represent the amounts to be shipped between the sinks and their respective sources; the allowable source locations are free of restriction. An algorithm for the approximate solution of the problem, and computational experience with it, are discussed first. A branch-and-bound algorithm for exact solution of the problem is then developed, and computational experience with it is described.For a more detailed discussion of the analyses contained in the present paper, the computational results, and for detailed program listings, the reader is referred to [8]. Tapes for the two programs discussed in the present paper are available at cost of reproduction from Program Analysis Division, Institute for Defense Analyses, Arlington, Virginia.     

The traveling purchaser problem with stochastic prices: Exact and approximate algorithms

The paper formulates an extension of the traveling purchaser problem where multiple types of commodities are sold at spatially distributed locations with stochastic prices (each following a known probability distribution). A purchaser’s goal is to find the optimal routing and purchasing strategies that minimize the expected total travel and purchasing costs needed to purchase one unit of each commodity. The purchaser reveals the actual commodity price at a seller upon arrival, and then either purchases the commodity at the offered price, or rejects the price and visits a next seller. In this paper, we propose an exact solution algorithm based on dynamic programming, an iterative approximate algorithm that yields bounds for the minimum total expected cost, and a greedy heuristic for fast solutions to large-scale applications. We analyze the characteristics of the problem and test the computational performance of the proposed algorithms. The numerical results show that the approximate and heuristic algorithms yield near-optimum strategies and very good estimates of the minimum total cost.     

On single-server closed queues with priorities and state dependent parameters

A wide class of closed single-channel queues is considered. The more general model involvesm +w + 1 “permanent” customers that occasionally require service. Them customers are of the first priority and the rest are of the second priority. The input rate and service of customers depend upon the total number of customers waiting for service. Such a system can also be described in terms of servicing machines processes with reserve replacement and multi-channel queues with finite waiting room. Two dual models, with and without idle periods, are treated. An explicit relation between the servicing processes of both models is derived. The semi-regenerative techniques originally developed in the author's earlier work [4] are extended and used to derive the probability distribution of the processes in equilibrium. Applications and examples are discussed. This paper is a part of work supported by the National Science Foundation under Grant No. DMS-8706186.     

Computation of the steady state distribution for multi-server retrial queues with phase type service process

We consider a multi-server retrial queueing system with the Batch Markovian Arrival Process and phase type service time distribution. Such a general queueing system suits for modeling and decision making in many real life objects including modern wireless communication networks. Behavior of such a system is described by the level dependent multi-dimensional Markov chain. Blocks of the generator of this chain, which is the block structured matrix of infinite size, can have large size if the number of servers is large and distribution of service time is not exponential. Due to this fact, the existing in literature algorithms allow to compute key performance measures of such a system only for a small number of servers. Here we describe the algorithm that allows to compute the stationary distribution of the system for larger number of servers and numerically illustrate its advantage. Importance of taking into account correlation in the arrival process is numerically demonstrated.     

Delay analysis of multiclass queues with correlated train arrivals and a hybrid priority/FIFO scheduling discipline

We analyze the delay experienced in a discrete-time priority queue with a train-arrival process. An infinite user population is considered. Each user occasionally sends packets in the form of trains: a variable number of fixed-length packets is generated and these packets arrive to the queue at the rate of one packet per slot. This is an adequate arrival process model for network traffic. Previous studies assumed two traffic classes, with one class getting priority over the other. We extend these studies to cope with a general number M of traffic classes that can be partitioned in an arbitrary number N of priority classes (1 ≤ N ≤ M). The lengths of the trains are traffic-class-dependent and generally distributed. To cope with the resulting general model, an (M × )∞-sized Markovian state vector is introduced. By using probability generating functions, moments and tail probabilities of the steady-state packet delays of all traffic classes are calculated. Since this study can be useful in deciding how to partition traffic classes in priority classes, we demonstrate the impact of this partitioning for some specific cases.