Monotonicity and error bounds for networks of Erlang loss queues

Networks of Erlang loss queues naturally arise when modelling finite communication systems without delays, among which, most notably are

1. classical circuit switch telephone networks (loss networks) and
2. present-day wireless mobile networks.

Performance measures of interest such as loss probabilities or throughputs can be obtained from the steady state distribution. However, while this steady state distribution has a closed product form expression in the first case (loss networks), it does not have one in the second case due to blocked (and lost) handovers. Product form approximations are therefore suggested. These approximations are obtained by a combined modification of both the state space (by a hypercubic expansion) and the transition rates (by extra redial rates). It will be shown that these product form approximations lead to

• upper bounds for loss probabilities and
• analytic error bounds for the accuracy of the approximation for various performance measures.

The proofs of these results rely upon both monotonicity results and an analytic error bound method as based on Markov reward theory. This combination and its technicalities are of interest by themselves. The technical conditions are worked out and verified for two specific applications:

• pure loss networks as under (i)
• GSM networks with fixed channel allocation as under (ii).

The results are of practical interest for computational simplifications and, particularly, to guarantee that blocking probabilities do not exceed a given threshold such as for network dimensioning.     

Compactness and the axiom of choice

In the absence of the axiom of choice four versions of compactness (A-, B-, C-, and D-compactness) are investigated. Typical results:

1. C-compact spaces form the epireflective hull in Haus of A-compact completely regular spaces.
2. Equivalent are:
3. the axiom of choice,
4. A-compactness = D-compactness,
5. B-compactness = D-compactness,
6. C-compactness = D-compactness and complete regularity,
7. products of spaces with finite topologies are A-compact,
8. products of A-compact spaces are A-compact,
9. products of D-compact spaces are D-compact,
10. powers X ^k of 2-point discrete spaces are D-compact,
11. finite products of D-compact spaces are D-compact,
12. finite coproducts of D-compact spaces are D-compact,
13. D-compact Hausdorff spaces form an epireflective subcategory of Haus,
14. spaces with finite topologies are D-compact.

1. Equivalent are:
2. the Boolean prime ideal theorem,
3. A-compactness = B-compactness,
4. A-compactness and complete regularity = C-compactness,
5. products of spaces with finite underlying sets are A-compact,
6. products of A-compact Hausdorff spaces are A-compact,
7. powers X ^k of 2-point discrete spaces are A-compact,
8. A-compact Hausdorff spaces form an epireflective subcategory of Haus.

1. Equivalent are:
2. either the axiom of choice holds or every ultrafilter is fixed,
3. products of B-compact spaces are B-compact.

1. Equivalent are:
2. Dedekind-finite sets are finite,
3. every set carries some D-compact Hausdorff topology,
4. every T ₁-space has a T ₁-D-compactification,
5. Alexandroff-compactifications of discrete spaces and D-compact.

     

Flow of a weakly ionized gas between parallel cold walls with parabolic velocity profile

Ambipolar diffusion between flat cold insulating walls of a weakly ionized gas which flows in the direction parallel to the walls with parabolic velocity profile is investigated theoretically. It has been found that:

1. the patched velocity of linear and nonlinear regions tends to 1/√2 of the thermal velocity;
2. the thickness of the nonlinear region with parabolic velocity profile is found to be less than that of Shioda who considered uniform streaming (J. Phys. Soc. Japan, 1969,29, 197); and
3. the number density and the electric potential approximations in the sheath edge do not depend uponx, the coordinate in the streaming direction.

     

Order stars and stability theorems

This paper clears up to the following three conjectures:

1. The conjecture of Ehle [1] on theA-acceptability of Padé approximations toe ^z , which is true;
2. The conjecture of Nørsett [5] on the zeros of the “E-polynomial”, which is false;
3. The conjecture of Daniel and Moore [2] on the highest attainable order of certainA-stable multistep methods, which is true, generalizing the well-known Theorem of Dahlquist.

We further give necessary as well as sufficient conditions forA-stable (acceptable) rational approximations, bounds for the highest order of “restricted” Padé approximations and prove the non-existence ofA-acceptable restricted Padé approximations of order greater than 6. The method of proof, just looking at “order stars” and counting their “fingers”, is very natural and geometric and never uses very complicated formulas.     

Multidimensional symmetric stable processes

This paper surveys recent remarkable progress in the study of potential theory for symmetric stable processes. It also contains new results on the two-sided estimates for Green functions, Poisson kernels and Martin kernels of discontinuous symmetric α-stable process in boundedC ^1,1 open sets. The new results give explicit information on how the comparing constants depend on parameter α and consequently recover the Green function and Poisson kernel estimates for Brownian motion by passing α ↑ 2. In addition to these new estimates, this paper surveys recent progress in the study of notions of harmonicity, integral representation of harmonic functions, boundary Harnack inequality, conditional gauge and intrinsic ultracontractivity for symmetric stable processes. Here is a table of contents.

1. Introduction
2. Green function and Poisson kernel estimates

1. Estimates on balls
2. Estimates on boundedC ^1,1 domains
3. Estimates on boundedC ^1,1 open sets

1. Harmonic functions and integral representation
2. Two notions of harmonicity
3. Martin kernel and Martin boundary
4. Integral representation and uniqueness
5. Boundary Harnack principle
6. Conditional process and its limiting behavior
7. Conditional gauge and intrinsic ultracontractivity

     

Queueing networks with dependent nodes and concurrent movements

Classical queueing network processes are useful for modeling the movement of discrete units in a network in which the nodes operate independently, the routing of units is independent of the congestion, only one unit moves at a time and its equilibrium distribution is a well-understood product form. Actual networks, however, typically have dependent nodes and concurrent movement of units. Imagine the dependencies associated with the network movements of telephone calls, manufacturing material, computer data packets, messages in a parallel-processing simulation, etc. A second generation of queueing network processes is beginning to evolve for modeling such “intelligent” networks with dependent nodes and concurrent movements. This paper describes the following fundamental processes that have been developed in this regard:

? A basic queueing network process for dependent nodes and single-unit movements. Examples include the classical Jackson, BCMP, Kelly and Kelly-Whittle networks and networks with interacting subpopulations.

? Reversible queueing network processes for dependent nodes and concurrent movements. An example is a multivariate, compound birth-death process.

? Miscellaneous partially balanced queueing networks. Examples include extensions of the basic network processes and weakly coupled and quasi-reversible networks.

     

Generalized conic curves and their applications in curve approximation

The appriximation properties of generalized conic curves are studied in this paper. A generalized conic curve is defined as one of the following curves or their affine and translation equivalent curves:

1. conic curves, including parabolas, hyperbolas and ellipses;
2. generalized monomial curves, including curves of the form x=y^γ, γ∈R, γ≠0,1, in the x?y Cartesian coordinate system;
3. exponential spiral curves of the form ρ(?)=Ae^γ?, A>0, γ≠0, in the ρ-? polar coordinate system.

This type of curves has many important properties such as convexity, approximation property, effective numerical computation property and the subdivision property etc. Applications of these curves in both interpolation and approximations using piecewise generalized conic segment are also developed. It is shown that these generalized conic splines are very similar to the cubic polynomial splines and the best error of approximation isO(h ⁵) or at leastO(h ⁴) in general provided appropriate procedures are used. Finally some numerical examples of interpolation and approximations with generalized conic splines are given.     

States on bounded commutative residuated lattices

We define states on bounded commutative residuated lattices and consider their property. We show that, for a bounded commutative residuated lattice X,

1. If s is a state, then X/ker(s) is an MV-algebra.
2. If s is a state-morphism, then X/ker(s) is a linearly ordered locally finite MV-algebra.

Moreover we show that for a state s on X, the following statements are equivalent:

1. s is a state-morphism on X.
2. ker(s) is a maximal filter of X.
3. s is extremal on X.

     

E-free objects inE-varieties of inverse rings

We show that for any regular ring (R, +, -), the following conditions are equivalent:

1. (R, -) is inverse.
2. (R, -) isE-solid.
3. (R, -) is locally inverse.
4. (R, -) is locallyE-solid.

We also show that there is ane-free object in eache-variety of inverse rings.     

Convex rearrangements of stable processes

The asymptotic behavior of convex rearrangements for smooth approximations of random processes is considered. The main results are.

- the relations between the convergence of convex rearrangements of absolutely continuous on [0, 1] functions and the weak convergence of its derivatives considered as random variables on the probability space {[0, 1], ß_{[0, 1]}, λ} are established:

- a strong law of large numbers for convex rearrangements of polygonal approximations of stable processes with the exponent α, 1<α≦2, is proved:

- the relations with the results by M. Wshebor (see references) on oscillations of the Wiener process and with the results by Yu. Davydov and A. M. Vershik (see references) on convex rearrangements of random walks are discussed.

     

A generalization of Norton's theorem for queueing networks

A general framework for aggregation and decomposition of product form queueing networks with state dependent routing and servicing is presented. By analogy with electrical circuit theory, the stations are grouped into clusters of subnetworks such that the process decomposes into a global process and a local process. Moreover, the local process factorizes into the subnetworks. The global process and the local processes can be analyzed separately as if they were independent. The global process describes the behaviour of the queuing network in which each cluster is aggregated into a single station, whereas the local process describes the behaviour of the subnetworks as if they are not part of the queueing network. The decomposition and aggregation method formalized in this paper allows us to first analyze the global behaviour of the queueing network and subsequently analyze the local behaviour of the subnetworks of interest or to aggregate clusters into single stations without affecting the behaviour of the rest of the queueing network. Conditions are provided such that:

- the global equilibrium distribution for aggregated clusters has a product form;

- this form can be obtained by merely monitoring the global behaviour;

- the computation of a detailed distribution, including its normalizing constant, can be decomposed into the computation of a global and a local distribution;

- the marginal distribution for the number of jobs at the stations of a cluster can be obtained by merely solving local behaviour.

As a special application, Norton's theorem for queueing networks is extended to queueing networks with state dependent routing such as due to capacity constraints at stations or at clusters of stations and state dependent servicing such as due to service delays for clusters of stations.     

On the geometry of the characteristic vector of an lcQS-manifold

We study conditions under which the characteristic vector of a normal lcQS-manifold is a torsion-forming or even a concircular vector field. We prove that the following assertions are equivalent:

• An lcQS-structure is normal, and its characteristic vector is a torsion-forming vector field.
• An lcQS-structure is normal, and its characteristic vector is a concircular vector field.
• An lcQS-structure is locally conformally cosymplectic and has a closed contact form.

     

Call Centers with Impatient Customers: Many-Server Asymptotics of the M/M/n + G Queue

The subject of the present research is the M/M/n + G queue. This queue is characterized by Poisson arrivals at rate λ, exponential service times at rate μ, n service agents and generally distributed patience times of customers. The model is applied in the call center environment, as it captures the tradeoff between operational efficiency (staffing cost) and service quality (accessibility of agents). In our research, three asymptotic operational regimes for medium to large call centers are studied. These regimes correspond to the following three staffing rules, as λ and n increase indefinitely and μ held fixed:

Efficiency-Driven (ED): $n\ \approx \ (\lambda / \mu)\cdot (1 - \gamma),\gamma > 0,$

Quality-Driven (QD): $n \ \approx \ ( \lambda / \mu)\cdot (1 + \gamma),\gamma > 0$ , and

Quality and Efficiency Driven (QED): $ n \ \approx \ \lambda/ \mu+\beta \sqrt{\lambda/\mu},-\infty < \beta < \infty $ .

In the ED regime, the probability to abandon and average wait converge to constants. In the QD regime, we observe a very high service level at the cost of possible overstaffing. Finally, the QED regime carefully balances quality and efficiency: agents are highly utilized, but the probability to abandon and the average wait are small (converge to zero at rate 1/ $\sqrt{n}$ ). Numerical experiments demonstrate that, for a wide set of system parameters, the QED formulae provide excellent approximation for exact M/M/n + G performance measures. The much simpler ED approximations are still very useful for overloaded queueing systems. Finally, empirical findings have demonstrated a robust linear relation between the fraction abandoning and average wait. We validate this relation, asymptotically, in the QED and QD regimes.     

Characterizations of Strength Extremal Graphs

With graphs considered as natural models for many network design problems, edge connectivity κ′(G) and maximum number of edge-disjoint spanning trees τ(G) of a graph G have been used as measures for reliability and strength in communication networks modeled as graph G (see Cunningham, in J ACM 32:549–561, 1985; Matula, in Proceedings of 28th Symposium Foundations of Computer Science, pp 249–251, 1987, among others). Mader (Math Ann 191:21–28, 1971) and Matula (J Appl Math 22:459–480, 1972) introduced the maximum subgraph edge connectivity \({\overline{\kappa'}(G) = {\rm max} \{\kappa'(H) : H {\rm is} \, {\rm a} \, {\rm subgraph} \, {\rm of} G \}}\) . Motivated by their applications in network design and by the established inequalities $$\overline{\kappa'}(G) \ge \kappa'(G) \ge \tau(G),$$ we present the following in this paper:

1. For each integer k > 0, a characterization for graphs G with the property that \({\overline{\kappa'}(G) \le k}\) but for any edge e not in G, \({\overline{\kappa'}(G + e) \ge k+1}\) .
2. For any integer n > 0, a characterization for graphs G with |V(G)| = n such that κ′(G) = τ(G) with |E(G)| minimized.

     

Complex Banach spaces whose duals areL 1-spaces

We prove that for a complex Banach spaceA the following properties are equivalent:

1. A ^* is isometric to anL ₁(μ)-space;
2. every family of 4 balls inA with the weak intersection property has a non-empty intersection;
3. every family of 4 balls inA such that any 3 of them have a non-empty intersection, has a non-empty intersection.

     

Some results on entire functions of finite lower order

Letf(z) be an entire function of order λ and of finite lower order μ. If the zeros off(z) accumulate in the vicinity of a finite number of rays, then

1. λ is finite;
2. for every arbitrary numberk ₁>1, there existsk ₂>1 such thatT(k ₁ r,f)≤k ₂ T(r,f) for allr≥r ₀. Applying the above results, we prove that iff(z) is extremal for Yang's inequalityp=g/2, then
3. every deficient values off(z) is also its asymptotic value;
4. every asymptotic value off(z) is also its deficient value;
5. λ=μ;
6. $\sum\limits_{a \ne \infty } {\delta (a,f) \leqslant 1 - k(\mu ).} $

     

Diffraction of light by superposed parallel supersonic waves,one being then-th harmonic of the other. Solution of the system of difference-differential equations for the amplitudes by a series expansion method

In the problem of the diffraction of light by two parallel supersonic waves, consisting of a fundamental tone and itsn-th harmonic, the solution of the system of difference-differential equations for the amplitudes has been reduced to the integration of a partial differential equation. The expressions for the amplitudes of the diffracted light waves are obtained as the coefficients of the Laurent expansion of the solution of this partial differential equation. The latter has been integrated for two approximations:

1. Forρ = 0, the results of Murty’s elementary theory are reestablished.
2. Forρ ≤ 1, a power series inρ, the terms of which are calculated as far as the third one, leads to a new expression for the intensities of the diffracted light waves, verifying the general symmetry properties obtained by Mertens.

     

On HCO spaces. An uncountable compactT 2 space,different from ℵ1+1, which is homeomorphic to each of its uncountable closed subspaces,which is homeomorphic to each of its uncountable closed subspaces

LetX be an Hausdorff space. We say thatX is a CO space, ifX is compact and every closed subspace ofX is homeomorphic to a clopen subspace ofX, andX is a hereditarily CO space (HCO space), if every closed subspace is a CO space. It is well-known that every well-ordered chain with a last element, endowed with the interval topology, is an HCO space, and every HCO space is scattered. In this paper, we show the following theorems: Theorem (R. Bonnet):

1. Every HCO space which is a continuous image of a compact totally disconnected interval space is homeomorphic to β+1 for some ordinal β.
2. Every HCO space of countable Cantor-Bendixson rank is homeomorphic to α+1 for some countable ordinal α.

Theorem (S. Shelah):Assume \(\diamondsuit _{\aleph _1 } \) . Then there is a HCO compact space X of Cantor-Bendixson rankω ₁} and of cardinality ?₁ such that:

1. X has only countably many isolated points,
2. Every closed subset of X is countable or co-countable,
3. Every countable closed subspace of X is homeomorphic to a clopen subspace, and every uncountable closed subspace of X is homeomorphic to X, and
4. X is retractive.

In particularX is a thin-tall compact space of countable spread, and is not a continuous image of a compact totally disconnected interval space. The question whether it is consistent with ZFC, that every HCO space is homeomorphic to an ordinal, is open.     

On lines missing polyhedral sets in 3-space

We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include:

1. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of the set of lines that can be translated to infinity without intersecting a given finite set ofn lines, wherec is a suitable constant. This bound is almost tight.
2. AnO(n ^1.5+ε) randomized expected time algorithm that tests whether a directionv exists along which a set ofn red lines can be translated away from a set ofn blue lines without collisions. ε>0 is an arbitrary small but fixed constant.
3. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of theenvelope of lines above a terrain withn edges, wherec is a suitable constant.
4. An algorithm for computing the intersection of two polyhedral terrains in 3-space withn total edges in timeO(n ^4/3+ε+k ^1/3 n ^1+ε+klog² n), wherek is the size of the output, and ε>0 is an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelleet al. [5].

The tools used to obtain these results include Plücker coordinates of lines, random sampling, and polarity transformations in 3-space.     

On an Ulam's problem

The existence and the uniqueness (with respect to a filtration-equivalence) of a vector flowX on ? ⁿ ,n≥3, such that:

1. X has not any stationary points on ? ⁿ ;
2. all orbits ofX are bounded;
3. there exists a filtration forX are proved in the present note.