Periodic problems and problems with discontinuities for nonlinear parabolic equations

In this paper we study nonlinear parabolic equations using the method of upper and lower solutions. Using truncation and penalization techniques and results from the theory of operators of monotone type, we prove the existence of a periodic solution between an upper and a lower solution. Then with some monotonicity conditions we prove the existence of extremal solutions in the order interval defined by an upper and a lower solution. Finally we consider problems with discontinuities and we show that their solution set is a compact R -set in (CT, L ²(Z)).     

Diffusion Approximation in Overloaded Switching Queueing Models

The asymptotic behavior of a queueing process in overloaded state-dependent queueing models (systems and networks) of a switching structure is investigated. A new approach to study fluid and diffusion approximation type theorems (without reflection) in transient and quasi-stationary regimes is suggested. The approach is based on functional limit theorems of averaging principle and diffusion approximation types for so-called Switching processes. Some classes of state-dependent Markov and non-Markov overloaded queueing systems and networks with different types of calls, batch arrival and service, unreliable servers, networks (M _SM,Q /M _SM,Q /1/) ^r switched by a semi-Markov environment and state-dependent polling systems are considered.     

Queueing systems fed by many exponential on-off sources: an infinite-intersection approach

In queueing theory, an important class of events can be written as ‘infinite intersections’. For instance, in a queue with constant service rate c, busy periods starting at 0 and exceeding L > 0 are determined by the intersection of the events , i.e., queue Q _t is empty at 0 and for all t∊ [0, L] the amount of traffic A _t arriving in [0,t) exceeds the server capacity. Also the event of exceeding some predefined threshold in a tandem queue, or a priority queue, can be written in terms of this kind of infinite intersections. This paper studies the probability of such infinite intersections in queueing systems fed by a large number n of i.i.d. traffic sources (the so-called ‘many-sources regime’). If the sources are of the exponential on-off type, and the queueing resources are scaled proportional to n, the probabilities under consideration decay exponentially; we explicitly characterize the corresponding decay rate. The techniques used stem from large deviations theory (particularly sample-path large deviations). M. Mandjes is also with Korteweg-de Vries Institute, University of Amsterdam, Amsterdam, the Netherlands, and EURANDOM, Eindhoven, the Netherlands. Work done while P. Mannersalo was on leave at CWI. MSC 2000: 60F10 (Large deviations), 60K25 (Queueing theory)     

Switching stochastic models and applications in retrial queues

Some special classes of Switching Processes such as Recurrent Processes of a Semi-Markov type and Processes with Semi-Markov Switches are introduced. Limit theorems of Averaging Principle and Diffusion Approximation types are given. Applications to the asymptotic analysis of overloading state-dependent Markov and semi-Markov queueing modelsM _SM,Q /M _SM,Q /1/∞ and retrial queueing systemsM/G/1/w.r in transient conditions are studied. The paper was supported by INTAS Project 96-0828     

Jitter analysis of an MMPP-2 tagged stream in the presence of an MMPP-2 background stream

We first consider a single-server queue that serves a tagged MMPP-2 stream and a background MMPP-2 stream in a FIFO manner. The service time is exponentially distributed. For this queueing system, we obtain the CDF of the tagged inter-departure time, from which we can calculate the jitter, defined as a percentile of the inter-departure time. The formulation is exact, but the solution is obtained numerically, which introduces an error that has been found to be negligible. Subsequently, we consider a tandem queueing network consisting of N tandem queues, which is traversed by the MMPP-2 tagged stream, and where each queue also serves a local MMPP-2 background stream. For this queueing network, we obtain an upper bound on the CDF of the inter-departure time from the Nth queue using a heavy traffic approximation, and we verify it by simulation.     

Rounding Error Analysis in Solving M-Matrix Linear Systems of Block Hessenberg Form

The problem of solving large M-matrix linear systems with sparse coefficient matrix in block Hessenberg form is here addressed. In previous work of the authors a divide-and-conquer strategy was proposed and a backward error analysis of the resulting algorithm was presented showing its effectiveness for the solution of computational problems of queueing theory and Markov chains. In particular, it was shown that for block Hessenberg M-matrices the algorithm is weakly backward stable in the sense that the computed solution is the exact solution of a nearby linear system, where the norm of the perturbation is proportional to the condition number of the coefficient matrix. In this note a better error estimate is given by showing that for block Hessenberg M-matrices the algorithm is even backward stable.     

Analysis of queueing policies in QoS switches

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the “best effort” approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst-case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.     

Traffic processes in a class of finite Markovian queues

This paper exposes the stochastic structure of traffic processes in a class of finite state queueing systems which are modeled in continuous time as Markov processes. The theory is presented for theM/E _k /φ/L class under a wide range of queue disciplines. Particular traffic processes of interest include the arrival, input, output, departure and overflow processes. Several examples are given which demonstrate that the theory unifies many earlier works, as well as providing some new results. Several extensions to the model are discussed.     

Limit theorems for finite dams

Limit distributions are given for both the dam content at time n and the limiting dam content in the n^th dam, as n tends to infinity, for a sequence of finite dams in discrete time, under assumptions which correspond to the various cases of heavy traffic in queueing theory. The proof employed is an application of the theory of weak convergence of probability measures.     

Weak Convergence of a Sequence of Semimartingales to a Diffusion with Discontinuous Drift and Diffusion Coefficients

This paper presents a set of sufficient conditions for a sequence of semimartingales to converge weakly to a solution of a stochastic differential equation (SDE) with discontinuous drift and diffusion coefficients. This result is closely related to a well-known weak-convergence theorem due to Liptser and Shiryayev (see [27]) which proves the weak convergence to a solution of a SDE with continuous drift and diffusion coefficients in the Skorokhod–Lindvall J ₁-topology.The goal of this paper is to obtain a stronger result in order to solve outstanding problems in the area of large-scale queueing networks – in which the weak convergence of normalized queueing length is a solution of a SDE with discontinuous coefficients. To do this we need to make the stronger assumptions: (1) replacing the convergence in probability of the triplets of a sequence of semimartingales in the original Liptser and Shiryayev's theorem by stronger convergence in L ₂, (2) assuming the diffusion coefficient is coercive, and (3) assuming the discontinuity sets of the coefficients of the limit diffusion processs are of Lebesgue measure zero.     

Markov Decision Processes with Variance Minimization: A New Condition and Approach

Abstract

This article deals with the limiting average variance criterion for discrete-time Markov decision processes in Borel spaces. The costs may have neither upper nor lower bounds. We propose another set of conditions under which we prove the existence of a variance minimal policy in the class of average expected cost optimal stationary policies. Our conditions are weaker than those in the previous literature. Moreover, some sufficient conditions for the existence of a variance minimal policy are imposed on the primitive data of the model. In particular, the stochastic monotonicity condition in this paper has been first used to study the limiting average variance criterion. Also, the optimality inequality approach provided here is different from the “optimality equation approach” widely used in the previous literature. Finally, we use a controlled queueing system to illustrate our results.     

Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed G/G/1 queue

We develop a strongly efficient rare-event simulation algorithm for computing the tail of the steady-state waiting time in a single server queue with regularly varying service times. Our algorithm is based on a state-dependent importance sampling strategy that is constructed so as to be straightforward to implement. The construction of the algorithm and its asymptotic optimality rely on a Lyapunov-type inequality that is used to bound the second moment of the estimator. The solution to the Lyapunov inequality is constructed using fluid heuristics. Our approach takes advantage of the regenerative ratio formula for the steady-state distribution—and does not use the first passage time representation that is particular to the delay in the G/G/1 queue. Hence, the strategy has the potential to be applied in more general queueing models.      

Optimal boundary control of the wave equation with pointwise control constraints

In optimal control problems frequently pointwise control constraints appear. We consider a finite string that is fixed at one end and controlled via Dirichlet conditions at the other end with a given upper bound M for the L ^∞-norm of the control. The problem is to control the string to the zero state in a given finite time. If M is too small, no feasible control exists. If M is large enough, the optimal control problem to find an admissible control with minimal L ²-norm has a solution that we present in this paper.     

<Emphasis Type="Italic">V</Emphasis>-uniform ergodicity for state-dependent single class queueing networks

We consider single class queueing networks with state-dependent arrival and service rates. Under the uniform (in state) stability condition, it is shown that the queue length process is V-uniformly ergodic; that is, it has a transition probability kernel which converges to its limit geometrically quickly in the V-norm sense. Among several asymptotic properties of V-uniformly ergodic processes, we present a Strassen-type functional law of the iterated logarithm result.     

Proof of Monotone Loss Rate of Fluid Priority-Queue with Finite Buffer

This paper studies a fluid queueing system that has a single server, a single finite buffer, and which applies a strict priority discipline to multiple arriving streams of different classes. The arriving streams are modeled by statistically independent, identically distributed random processes. A proof is presented for the highly intuitive result that, in such a queueing system, a higher priority class stream has a lower average fluid loss rate than a lower priority class stream. The proof exploits the fact that for a work-conserving queue, the fluid loss rate for a given class is invariant of what queueing discipline is applied to all arriving fluid of this particular class. AMS subject classification: 60K25, 68M20     

On the mean square of standard L-functions attached to Ikeda lifts

By using estimates on the frequency of large values of the Riemann zeta-function and modular L-functions attached to the full modular group SL(2, ℤ), we prove sharp upper and lower estimates of the mean square of standard L-functions attached to Siegel cusp forms which are Ikeda lifts, on boundaries and the central line of the critical strip. The mean square of spinor L-functions attached to Saito-Kurokawa lifts is also studied.     

Generalized Stokes resolvent equations in an infinite layer with mixed boundary conditions

In this paper we prove unique solvability of the generalized Stokes resolvent equations in an infinite layer Ω₀ = ℝ^{n –1} × (–1, 1), n ≥ 2, in L^q ‐Sobolev spaces, 1 < q < ∞, with slip boundary condition of on the “upper boundary” ∂Ω⁺₀ = ℝ^{n –1} × {1} and non‐slip boundary condition on the “lower boundary” ∂Ω^–₀ = ℝ^{n –1} × {–1}. The solution operator to the Stokes system will be expressed with the aid of the solution operators of the Laplace resolvent equation and a Mikhlin multiplier operator acting on the boundary. The present result is the first step to establish an L^q ‐theory for the free boundary value problem studied by Beale [9] and Sylvester [22] in L ²‐spaces. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Application of C 0 -semigroup Theory to Dynamic Queueing Systems

In this paper, we consider the dynamic M/G ^k,B /1 queueing system. By means of the C ₀ -semigroup theory of bounded linear operators in functional analysis we prove that this system has a unique nonnegative solution. January 15, 1999     

Truncated Erlangian queueing system with fuzzy arrival rate,balking and reneging

In this paper, we derive the performance measures of the truncated Erlangian service queueing system with state-dependent rate, balking and reneging with fuzzy arrival rate _n\tilde \lambda _n so for the (M/E _r /1/N(α, β)), we have obtained P _n,s the steady state probabilities in the system with the unit in the service being at stage s (s=1, 2, …, r); k is the boundary state for the number of customer more than the one that the rate of service increases. We treat this queueing system for general values of r, k and N and derive the Fuzzy effective measures for the operation of the system at any time.