Convexity properties of the overflow in an ordered-entry system with heterogeneous servers

The overflow probability in an Erlang loss system is known to be decreasing convex in the number of servers. Here we consider the GI/M/m loss system with ordered entry and heterogeneous servers. We show that adding a sequence of servers with non-increasing (non-decreasing) service rates will yield a decreasing convex (log-concave) sequence of overflow probabilities. An optimal server allocation problem is solved as a direct application of these results.     

A critically loaded multiclass Erlang loss system

We consider a generalization of the classical Erlang loss model to multiple classes of customers. Each of the J customer classes has an associated Poisson arrival process and an arbitrary holding time distribution. Classj customers requireM _j servers simultaneously. We determine the asymptotic form of the blocking probabilities for all customer classes in the regime known as critical loading, where both the number of servers and offered load are large and almost equal. Asymptotically, the blocking probability of classj customers is proportional toM _j . This asymptotic result provides an approximation for the blocking probabilities which is reasonably accurate. We also consider the behavior of the Erlang fixed point (reduced load approximation) for this model under critical loading. Although the blocking probability of classj customers given by the Erlang fixed point is again asymptotically proportional toM _j , the Erlang fixed point typically gives the wrong limit. Next we show that under critical loading the throughputs have a pleasingly simple form of monotonicity with respect to arrival rates: the throughput of classi is increasing in the arrival rate of classi and decreasing in the arrival rate of classj forji. Finally, we compare two simple control policies for this system under critical loading.     

Approximations for the delay probability in the M/G/s queue

This paper develops approximations for the delay probability in an M/G/s queue. For M/G/s queues, it has been well known that the delay probability in the M/M/s queue, i.e., the Erlang delay formula, is usually a good approximation for other service-time distributions. By using an excellent approximation for the mean waiting time in the M/G/s queue, we provide more accurate approximations of the delay probability for small values of s. To test the quality of our approximations, we compare them with the exact value and the Erlang delay formula for some particular cases.     

Second-order properties of the loss probability inM/M/s/s +c systems

The Erlang loss function, which gives the steady state loss probability in anM/M/s/s system, has been extensively studied in the literature. In this paper, we look at the similar loss probability inM/M/s/s + c systems and an extension of it to nonintegral number of servers and queue capacity. We study its monotonicity properties. We show that the loss probability is convex in the queue capacity, and that it is convex in the traffic intensity if is below some ^* and concave if is greater that ^*, for a broad range of number of servers and queue capacities. We prove that the one-server loss system is the onlyM/M/s/s +c system for which the loss probability is concave in the traffic intensity in all its range.Research supported by Grant BD/645/90-RM from Junta Nacional de Investigação Científica e Tecnológica.On leave from: Departamento de Matemática, Instituto Superior Técnico, Av. Rovisco Pais, 1096 Lisboa Codex, Portugal.     

On the speed of convergence to stationarity of the Erlang loss system

We consider the Erlang loss system, characterized by N servers, Poisson arrivals and exponential service times, and allow the arrival rate to be a function of N. We discuss representations and bounds for the rate of convergence to stationarity of the number of customers in the system, and display some bounds for the total variation distance between the time-dependent and stationary distributions. We also pay attention to time-dependent rates.     

Linear and convex aggregation of density estimators

We study the problem of finding the best linear and convex combination of M estimators of a density with respect to the mean squared risk. We suggest aggregation procedures and we prove sharp oracle inequalities for their risks, i.e., oracle inequalities with leading constant 1. We also obtain lower bounds showing that these procedures attain optimal rates of aggregation. As an example, we consider aggregation of multivariate kernel density estimators with different bandwidths. We show that linear and convex aggregates mimic the kernel oracles in asymptotically exact sense. We prove that, for Pinsker’s kernel, the proposed aggregates are sharp asymptotically minimax simultaneously over a large scale of Sobolev classes of densities. Finally, we provide simulations demonstrating performance of the convex aggregation procedure.      

Structural interpretation and derivation of necessary and sufficient conditions for delay moments in FIFO multiserver queues

Scheller-Wolf [12] established necessary and sufficient conditions for finite stationary delay moments in stable FIFO GI/GI/s queues that incorporate the interaction between service time distribution, traffic intensity (ρ) and the number of servers in the queue. These conditions can be used to show that when the service time has finite first but infinite αth moment, s slow servers can give lower delays than one fast server. In this paper, we derive an alternative derivation of these moment results: Both upper bounds, that serve as sufficient conditions, and lower bounds, that serve as necessary conditions are presented. In addition, we extend the class of service time distributions for which the necessary conditions are valid. Our new derivations provide a structural interpretation of the moment bounds, giving intuition into their origin: We show that FIFO GI/GI/s delay can be represented as the minimum of (s − k) i.i.d. GI/GI/1 delays, when ρ satisfies k < ρ < k+1. AMS Subject Classification 60K25     

Estimating Effective Capacity in Erlang Loss Systems under Competition

We consider an Erlang loss system (modem bank) with two streams of arriving customers, where arrival rates vary by time-of-day. We can observe one of the traffic streams (our customers), but we do not know how many servers the system has, or the characteristics of the other stream. Using detailed sample-path data, we construct a maximum likelihood estimator that makes good use of the data, but is slow to evaluate. As an alternative, we present an estimation system based on traffic data summarized by hour. This estimation system is much faster, and tends to produce good lower bounds on the size of the system and competing traffic.     

Heavy-traffic extreme value limits for Erlang delay models

We consider the maximum queue length and the maximum number of idle servers in the classical Erlang delay model and the generalization allowing customer abandonment—the M/M/n+M queue. We use strong approximations to show, under regularity conditions, that properly scaled versions of the maximum queue length and maximum number of idle servers over subintervals [0,t] in the delay models converge jointly to independent random variables with the Gumbel extreme value distribution in the quality-and-efficiency-driven (QED) and ED many-server heavy-traffic limiting regimes as n and t increase to infinity together appropriately; we require that t _n →∞ and t _n =o(n ^1/2?ε ) as n→∞ for some ε>0.     

Connection admission control for constant bit rate traffic at a multi‐buffer multiplexer using the oldest‐cell‐first discipline

Consider an ATM multiplexer where M input links contend for time slots on an output link which transmits C cells per second. Each input link has its own queue of size B cells. The traffic is delay sensitive so B is small (e.g., B=20). We assume that each of the M input links carries Constant Bit Rate (CBR) traffic from a large number of independent Virtual Connections (VCs) which are subject to jitter. The fluctuations of the aggregate traffic arriving at queue i, i=1,...,M, is modeled by a Poisson process with rate λ_i. The Quality of Service (QoS) of one connection is determined in part by the queueing delay across the multiplexer and the Cell Loss Ratio (CLR) or proportion of cells from this connection lost because the buffer is full. The Oldest‐Customer(Cell)‐First (OCF) discipline is a good compromise between competing protocols like round‐robin queueing or serving the longest queue. The OCF discipline minimizes the total cell delay among all cells arriving at the contending queues. Moreover, the CLR is similar to that obtained by serving the longest queue. We develop QoS formulae for this protocol that can be calculated on‐line for Connection Admission Control (CAC). These formulae follow from a simple new expression for the exact asymptotics of a M/D/1 queue. This revised version was published online in June 2006 with corrections to the Cover Date.     

Tail bounds for occupancy and the satisfiability threshold conjecture

The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well-known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3-SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c* ≈? 4.2. We provide a strong upper bound on the value of c*, showing that for c > 4.758 a random 3-SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds.     

New bounds for expected delay in FIFO M/G/c queues

Most bounds for expected delay, E[D], in GI/GI/c queues are modifications of bounds for the GI/GI/1 case. In this paper we exploit a new delay recursion for the GI/GI/c queue to produce bounds of a different sort when the traffic intensity p = λ/μ = E[S]/E[T] is less than the integer portion of the number of servers divided by two. (S AND T denote generic service and interarrival times, respectively.) We derive two different families of new bounds for expected delay, both in terms of moments of S AND T. Our first bound is applicable when E[S₂] < ∞. Our second bound for the first time does not require finite variance of S; it only involves terms of the form E[S^β], where 1 < β < 2. We conclude by comparing our bounds to the best known bound of this type, as well as values obtained from simulation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Reidemeister–Turaev torsion of 3-dimensional¶Euler structures with simple boundary tangency¶and pseudo-Legendrian knots

We generalize Turaev's definition of torsion invariants of pairs (M,&\xi;), where M is a 3-dimensional manifold and &\xi; is an Euler structure on M (a non-singular vector field up to homotopy relative to ∂M and modifications supported in a ball contained in Int(M)). Namely, we allow M to have arbitrary boundary and &\xi; to have simple (convex and/or concave) tangency circles to the boundary. We prove that Turaev's H ₁(M)-equivariance formula holds also in our generalized context. Using branched standard spines to encode vector fields we show how to explicitly invert Turaev's reconstruction map from combinatorial to smooth Euler structures, thus making the computation of torsions a more effective one. Euler structures of the sort we consider naturally arise in the study of pseudo-Legendrian knots (i.e.~knots transversal to a given vector field), and hence of Legendrian knots in contact 3-manifolds. We show that torsion, as an absolute invariant, contains a lifting to pseudo-Legendrian knots of the classical Alexander invariant. We also precisely analyze the information carried by torsion as a relative invariant of pseudo-Legendrian knots which are framed-isotopic. Received: 3 October 2000 / Revised version: 20 April 2001     

Some remarks on lengths of propositional proofs

We survey the best known lower bounds on symbols and lines in Frege and extended Frege proofs. We prove that in minimum length sequent calculus proofs, no formula is generated twice or used twice on any single branch of the proof. We prove that the number of distinct subformulas in a minimum length Frege proof is linearly bounded by the number of lines. Depthd Frege proofs ofm lines can be transformed into depthd proofs ofO(m ^d+1) symbols. We show that renaming Frege proof systems are p-equivalent to extended Frege systems. Some open problems in propositional proof length and in logical flow graphs are discussed. Supported in part by NSF grant DMS-9205181     

Overflow and losses in a network queue with a self-similar input

This paper considers a discrete time queuing system that models a communication network multiplexer which is fed by a self-similar packet traffic. The model has a finite buffer of size h, a number of servers with unit service time, and an input traffic which is an aggregation of independent source-active periods having Pareto-distributed lengths and arriving as Poisson batches. The new asymptotic upper and lower bounds to the buffer-overflow and packet-loss probabilities P are obtained. The bounds give an exact asymptotic of log P/log h when h → to ∞. These bounds decay algebraically slow with buffer-size growth and exponentially fast with excess of channel capacity over traffic rate. Such behavior of the probabilities shows that one can better combat traffic losses in communication networks by increasing channel capacity rather than buffer size. A comparison of the obtained bounds and the known upper and lower bounds is done. This revised version was published online in June 2006 with corrections to the Cover Date.     

Generating and Enumerating Digitally Convex Sets of Trees

A set S of vertices in a graph G with vertex set V is digitally convex if for every vertex \(v \in V\), \(N[v] \subseteq N[S]\) implies \(v \in S\). We show that a vertex belongs to at most half of the digitally convex sets of a graph. Moreover, a vertex belongs to exactly half of the digitally convex sets if and only if it is simplicial. An algorithm that generates all digitally convex sets of a tree is described and sharp upper and lower bounds for the number of digitally convex sets of a tree are obtained. A closed formula for the number of digitally convex sets of a path is derived. It is shown how a binary cotree of a cograph can be used to enumerate its digitally convex sets in linear time.     

On inner parallel bodies and quermassintegrals

Due to the “uncontrollable behavior“ of the inner parallel bodies of a convex body K ⊂ ℝ ⁿ regarding its boundary structure, it is not possible to get precise formulae for their volume/quermassintegrals, contrary to the case of the outer parallel bodies. In this paper we provide (sharp) bounds for the quermassintegrals of the inner parallel bodies, studying previously some particular properties of their boundary in terms of their outer normal vectors.     

Ricci Curvature and Bochner Formulas for Martingales

We generalize the classical Bochner formula for the heat flow on M to martingales on the path space PM and develop a formalism to compute evolution equations for martingales on path space. We see that our Bochner formula on PM is related to two‐sided bounds on Ricci curvature in much the same manner that the classical Bochner formula on M is related to lower bounds on Ricci curvature. Using this formalism, we obtain new characterizations of bounded Ricci curvature, new gradient estimates for martingales on path space, new Hessian estimates for martingales on path space, and streamlined proofs of the previous characterizations of bounded Ricci curvature.© 2018 Wiley Periodicals, Inc.     

Bounds for Analytical Functions of Matrices

If f is an analytic function bounded on a convex domain of the complex plane and A a square matrix whose spectrum is included in this domain, the function f(A) is well defined. In this paper we study bounds for ||f(A)|| uniform with respect to the functions f bounded by 1, and uniform with respect to the matrices A whose the numerical ranges are included in the domain. We show that these bounds are attained and give explicit formulae in some 2-dimensional cases.     

Lost customers in <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1/1 loss system

In this paper, we consider lost customers in the M/M/1/1 Erlang loss system. Here we present an explicit form of the probability that the M/M/1/1 system does not lose any customer in the time interval [0, t) and an iterative procedure to determine the distribution of the total number of losses in [0, t). All these probabilities solve the same second-order differential equation which was used to evaluate the corresponding generating probability function. Finally, the connection between the Erlang’s loss rate and the evaluated probabilities is showed.