Queues with Equally Heavy Sojourn Time and Service Requirement Distributions

For the G/G/1 queue with First-Come First-Served, it is well known that the tail of the sojourn time distribution is heavier than the tail of the service requirement distribution when the latter has a regularly varying tail. In contrast, for the M/G/1 queue with Processor Sharing, Zwart and Boxma [26] showed that under the same assumptions on the service requirement distribution, the two tails are equally heavy. By means of a probabilistic analysis we provide a new insightful proof of this result, allowing for the slightly weaker assumption of service requirement distributions with a tail of intermediate regular variation. The new approach allows us to also establish the tail equivalence for two other service disciplines: Foreground–Background Processor Sharing and Shortest Remaining Processing Time. The method can also be applied to more complicated models, for which no explicit formulas exist for (transforms of) the sojourn time distribution. One such model is the M/G/1 Processor Sharing queue with service that is subject to random interruptions. The latter model is of particular interest for the performance analysis of communication networks.     

Characterization of Dirichlet Forms by their Excessive and Co–Excessive Elements

It is proved that if S, T are two elliptic Dirichlet operators on an ordered Hilbert space such that the excessive (resp. coexcessive) elements with respect to S and T are the same then there exists > 0 with T = S. Particularly if , are two elliptic Dirichlet forms on L² ( ) having the same domain of definition and the same -excessive (resp. -coexcessive) elements for any > 0 then = .     

Measures not charging semipolars and equations of schrödinger type

SupposeX is a Borel right process andm is a -finite excessive measure forX. Given a positive measure not chargingm-semipolars we associate an exact multiplicative functionalM(). No finiteness assumptions are made on . Given two such measures and ,M()=M() if and only if and agree on all finely open measurable sets. The equation (q–L)u+u=f whereL is the generator of (a subprocess of)X may be solved for appropriatef by means of the Feynman-Kac formula based onM(). Both uniqueness and existence are considered.Supported in part by NSF Grant DMS 92-24990.     

On strong summability of polynomial expansions

—.

---

---

Dedicated to Professor L. Leindler on his 50^th birthday     

Further delay moment results for FIFO multiserver queues

Using a new family of service disciplines, we provide weaker sufficient conditions for finite stationary delay moments in FIFO multiserver queues. This extends the work in Sigman and Scheller-Wolf [6] to GI/GI/s queues with = E[S]/E[T] s-1 are the familiar Kiefer and Wolfowitz conditions actually known to be necessary. For the case when < 1, we provide sufficient conditions for finite mean stationary delay, expressed as a function of the number of servers in the system. The limit of these conditions as s is the requirement that E[S] < , which is the condition for finite mean stationary delay in a FIFO GI/GI/ queue. Both of these results highlight the interplay between traffic intensity and service time distribution in determining the behavior of delay moments in multiserver queues.     

Optimal order for two servers in tandem

We consider two servers (serveri, i=1, 2) in tandem for which the order of servers can be changed. Server 1 has a general service time distribution and server 2 has either its shifted or truncated distribution. This permits that the service times at the two servers are overlapping. An unlimited queue is allowed in front of the first server. For the systems having zero buffer capacity between the servers, we show that the sojourn time of every customer is stochastically minimized under any arrival process if server 2 is first. For the systems with infinite buffer capacity and a Poisson arrivals, we show that this order of servers minimizes mean customer delay when traffic is light. Several numerical examples are presented to demonstrate that this optimal order is invariant under any arrival process (the interarrival times are i.i.d. r.v.'s) and mild traffic condition.Research funded by NEC Corporation C & C Laboratory.     

Reduced-Load Equivalence and Induced Burstiness in GPS Queues with Long-Tailed Traffic Flows

We analyze the queueing behavior of long-tailed traffic flows under the Generalized Processor Sharing (GPS) discipline. We show a sharp dichotomy in qualitative behavior, depending on the relative values of the weight parameters. For certain weight combinations, an individual flow with long-tailed traffic characteristics is effectively served at a constant rate. The effective service rate may be interpreted as the maximum average traffic rate for the flow to be stable, which is only influenced by the traffic characteristics of the other flows through their average rates. In particular, the flow is essentially immune from excessive activity of flows with heavier-tailed traffic characteristics. In many situations, the effective service rate is simply the link rate reduced by the aggregate average rate of the other flows. This confirms that GPS-based scheduling algorithms provide a potential mechanism for extracting significant multiplexing gains, while isolating individual flows. For other weight combinations however, a flow may be strongly affected by the activity of heavier-tailed flows, and may inherit their traffic characteristics, causing induced burstiness. The stark contrast in qualitative behavior illustrates the crucial importance of the weight parameters.     

Lattice point theory of irractional ellipsoids with an arbitrary center

We shall consider positive definite quadratic formsQ inr2 variables of the almost diagonal shape where 2, and for 1j,Q _j is a positive definite quadratic form with integral coefficients inr _j variables, _j is a positive real number,r _j1 andr ₁+...+r =r Letb ₁,...,b _r be a system of real numbers with 0b _j<1. For x>0 letA(x) be the number of lattice points in the ellipsoidQ(u+b)x, letV(x) be the volume of this ellipsoid and letP(x)=A(x)-V(x). Our purpose is to find the exact order ofP(x); i. e., the numberf for which for each >0P(x)=O(x^f+) andP(x)=(x ^f–).     

On a one-dimensional version of the dynamical Marguerre-Vlasov system

A one-dimensional version of the so-called Marguerre-Vlasov system of equations describing the vibrations of shallow shells is considered. The system depends on a parameter 0 in a singular way and undergoes the effect of damping mechanisms. We show that the system converges to a nonlinear beam equation while the energy decays exponentially uniformly (on 0) as time goes to infinity.     

Queues with nonstationary inputs

In this paper we study single server queues with independent and identically distributed service times and a general nonstationary input stream. We discuss several notions of being in equilibrium. For queues with a doubly stochastic Poisson input we survey continuity and bounds of moments of some performance characteristics. We also discuss conjectures posed by Ross [34] to the effect that for a more stationary input we have a better performance characteristics. Some results are reviewed to typify a problem and then it is followed by a discussion, questions and related bibliography.     

Controlled Ornstein-Uhlenbeck process with chance constraints

In Ref. 1, existence and optimality conditions were given for control systems whose dynamics are determined by a linear stochastic differential equation with linear feedback controls; moreover, the state variables satisfy probability constraints. Here, for the simplest case of such a model, the Ornstein-Uhlenbeck velocity process, we evaluate the necessary conditions derived in Ref. 1 and compute a time-optimal control such that a given threshold value > 0 is crossed with probability of at least 1 – .This work was supported by the Sonderforschungsbereiche 21 and 72, University of Bonn, Bonn, West Germany.     

On the number of lattice points between two enlarged and randomly shifted,copies of an oval

Summary Let A be an oval with a nice boundary in ²,R a large positive number,c>0 some fixed number and a uniformly distributed random vector in the unit square [0,1]². We are interested in the number of lattice points in the shifted annular region consisting of the difference of the sets {(R+c/R)A–} and {(R–c/R)A–}. We prove that whenR tends to infinity, the expectation and the variance of this random variable tend to 4c times the area of the set A, i.e. to the area of the domain where we are counting the number of lattice points. This is consistent with computer studies in the case of a circle or an ellipse which indicate that the distribution of this random variable tends to the Poisson law. We also make some comments about possible generalizations.     

Upper Bounds for Neumann–Schatten Norms

Let H and H _aux be Hilbert spaces, H a nonnegative self-adjoint operator in H,,s>0 and J a bounded linear transformation from the Hilbert space D(H ^s/2) (equipped with the graph scalar product of H ^s/2) to H _aux. It is shown that the operator J(H+)^–t belongs to the Neumann–Schatten class of order p=2+2(u–t)/(t–s/2) provided s/2<t<u,t–s/2<u–t and J(H+)^–u is Hilbert–Schmidt operator. An upper bound for the pth order Neumann–Schatten norm of J(H+)^–t is derived. If J is a closed operator from D(H ^1/2) to H _aux and D(J)D(H) then there exists a unique self-adjoint operator H ^J in H such that D(H ^J )D(J) and ( . Conditions which are sufficient in order that the operator (H ^J +)^–1–(H+)^–1 is compact and conditions which are sufficient in order that the wave operators W ^±(H ^J ,H) exist and are complete are derived. Instead of (Jf,Jg)_aux also certain other perturbation terms, not by necessity nonnegative, are considered. The special case when H equals the operator (–) ^r in L ²(R ^d ) for any strictly positive real number and H ^J equals (–) ^r + for some suitably chosen measure is discussed in detail. In particular, new results on existence and completeness of the wave operators W ^±(–+,–) are obtained.     

The A-Stability of Methods with Padé and Generalized Padé Stability Functions

This paper surveys some stability results and suggests the use of order arrows as an alternative to order stars in studying questions about the possible A-stability of a numerical method. A discussion of the so-called Butcher–Chipman conjecture includes a proof of a partial result.     

Combined free and forced laminar convection in internally finned square ducts

Analysis is presented for the heat transfer performance of square ducts with internal fins from each wall in the case of combined free and forced convection by fully developed laminar flow. Numerical results are obtained for the Nusselt number and the pressure drop parameter for various values of finlengths and heat source parameter. For various values of Rayleigh numbers, the Nusselt number increases with the increase in finlength and decreases with the increase in heat source parameter.

---

Zusammenfassung Es wird eine Analyse für den Wärmeaustausch von quadratischen Rohren mit inneren Rippen an jeder Wand im Falle einer Kombination von freier und erzwungener Konvektion bei voll entwickelter laminarer Strömung gegeben. Numerische Resultate für die Nusselt-Zahl und den Druckabfall-Koeffizienten für verschiedene Rippenbreiten und Parameter der Wärmequelle werden erhalten. Für einige Werte der Rayleighzahl wächst die Nusselt-Zahl mit der Rippenbreite und fällt mit wachsendem Parameter der Wärmequelle.

---

Nomenclature A cross sectional area of the duct - B _2k Bernoulli numbers - c _p specific heat at constant pressure - D _h hydraulic diameter of finless duct - E _n complex constants (20) - F heat source parameter,Q/c _p - F _n () defined by Equation (14) - G(, , , ) Green's function (15, 16) - g gravitational acceleration - H() Heaviside function - h() defined by Equation (22) - i imaginary unit,i ²=–1 - ImW imaginary part ofW - K(,t) kernel of the integral equation, defined by (25) - k thermal conductivity - L pressure drop parameter, –D _h ² (p/x+ _w )/ - l fin length of each fin, Figure (1) - N _u Nusselt number, Equation (32) - p pressure - Q heat generation rate - R() defined by Equation (26) - R _A Rayleigh number, _w gc _p D _h ⁴ /k - ReW real part ofW - T dimensionless temperature, (t–t _w )/(c _p D _h ² /k) - T _mx dimensionless mixed mean temperature, Equation (33) - t fluid temperature - t ₀ reference temperature atx=0 - u local axial velocity - mean axial velocity - V u/ - W complex function defined by Equation (6) - w suffix denoting wall conditions - W ₀ defined by Equation (9) - W ₁ W–W ₀, Equation (18) - x axial coordinate along the length of the duct - y, z cross-sectional coordinates - constant temperature gradient, t/x - coefficient of thermal expansion of the fluid - fluid density - _n - dynamic viscosity - () Dirac delta function - ² Laplacian operator, ²/y ²/²/z ² - , y/D _h ,z/D _h      

Round-off error analysis of iterations for large linear systems

Summary We deal with the rounding error analysis of successive approximation iterations for the solution of large linear systemsA _x =b. We prove that Jacobi, Richardson, Gauss-Seidel and SOR iterations arenumerically stable wheneverA=A ^*>0 andA has PropertyA. This means that the computed resultx _k approximates the exact solution with relative error of order A·A ^–1 where is the relative computer precision. However with the exception of Gauss-Seidel iteration the residual vector Ax _k –b is of order A² A ^–1 and hence the remaining three iterations arenot well-behaved.This work was partly done during the author's visit at Carnegie-Mellon University and it was supported in part by the Office of Naval Research under Contract N00014-76-C-0370; NR 044-422 and by the National Science Foundation under Grant MCS75-222-55     

An optimal design problem with perimeter penalization

We study the optimal design problem of finding the minimal energy configuration for a mixture of two conducting materials when a perimeter penalization of the unknown domain is added. We show that in this situation an optimal domain exists and that, under suitable assumptions on the data, it is an open set.This work is part of the project EURHomogenization, contract SC1-CT91-0732 of the program SCIENCE of the Commission of the European Communities.     

Maximal Effective Bandwidth of Constrained Traffic

We investigate the worst possible behavior of a stationary traffic source when the traffic emanating from it is required to meet certain constraints. Specifically, the peak rate of the source is required not to exceed a level and realizations must obey a leaky bucket constraint with bucket size and leak rate . The worst case source is considered to be the one with the largest effective bandwidth, a concept which arises in the large deviation theory of queueing networks and governs the asymptotic loss rate when a large number of sources send traffic to a single server queue. We conjecture the form of the worst case traffic in general and prove the conjecture for the special case when T, the time-scale parameter of the effective bandwidth, is less than both /(–) and /, the times taken respectively to fill and empty the leaky bucket.     

On Sets of Planes in Projective Spaces Intersecting Mutually in One Point

Let be a projective space. In this paper we consider sets of planes of such that any two planes of intersect in exactly one point. Our investigation will lead to a classification of these sets in most cases. There are the following two main results:- If is a set of planes of a projective space intersecting mutually in one point, then the set of intersection points spans a subspace of dimension 6. There are up to isomorphism only three sets where this dimension is 6. These sets are related to the Fano plane.- If is a set of planes of PG(d,q) intersecting mutually in one point, and if q3, 3(q²+q+1), then is either contained in a Klein quadric in PG(5,q), or is a dual partial spread in PG(4,q), or all elements of pass through a common point.     

Einschließungsaussagen für gewöhnliche Differentialoperatoren

Summary For differential operatorsM of second order (as defined in (1.1)) we describe a method to prove Range-Domain implications—Mu–u and an algorithm to construct these functions , , , . This method has been especially developed for application to non-inverse-positive differential operators. For example, for non-negativea ₂ and for given functions = we require =C ₀[0, 1] C ₂([0, 1]–T) whereT is some finite set), (M) (t)(t), (t[0, 1]–T) and certain additional conditions for eachtT. Such Range-Domain implications can be used to obtain a numerical error estimation for the solution of a boundary value problemMu=r; further, we use them to guarantee the existence of a solution of nonlinear boundary value problems between the bounds- and .