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.     

From here to infinity: sparse finite versus Dirichlet process mixtures in model-based clustering

In model-based clustering mixture models are used to group data points into clusters. A useful concept introduced for Gaussian mixtures by Malsiner Walli et al. (Stat Comput 26:303–324, 2016) are sparse finite mixtures, where the prior distribution on the weight distribution of a mixture with K components is chosen in such a way that a priori the number of clusters in the data is random and is allowed to be smaller than K with high probability. The number of clusters is then inferred a posteriori from the data. The present paper makes the following contributions in the context of sparse finite mixture modelling. First, it is illustrated that the concept of sparse finite mixture is very generic and easily extended to cluster various types of non-Gaussian data, in particular discrete data and continuous multivariate data arising from non-Gaussian clusters. Second, sparse finite mixtures are compared to Dirichlet process mixtures with respect to their ability to identify the number of clusters. For both model classes, a random hyper prior is considered for the parameters determining the weight distribution. By suitable matching of these priors, it is shown that the choice of this hyper prior is far more influential on the cluster solution than whether a sparse finite mixture or a Dirichlet process mixture is taken into consideration.

     

State-dependent Coupling of Quasireversible Nodes

The seminal paper of Jackson began a chain of research on queueing networks with product-form stationary distributions which continues strongly to this day. Hard on the heels of the early results on queueing networks followed a series of papers which discussed the relationship between product-form stationary distributions and the quasireversibility of network nodes. More recently, the definition of quasireversibility and the coupling mechanism between nodes have been extended so that they apply to some of the later product-form queueing networks incorporating negative customers, signals, and batch movements.In parallel with this research, it has been shown that some special queueing networks can have arrival and service parameters which depend upon the network state, rather than just the node state, and still retain a generalised product-form stationary distribution.In this paper we begin by offering an alternative proof of a product-form result of Chao and Miyazawa and then build on this proof by postulating a state-dependent coupling mechanism for a quasireversible network. Our main theorem is that the resultant network has a generalised product form stationary distribution. We conclude the paper with some examples.     

Simple bounds and monotonicity results for finite multi-server exponential tandem queues

Simple and computationally attractive lower and upper bounds are presented for the call congestion such as those representing multi-server loss or delay stations. Numerical computations indicate a potential usefulness of the bounds for quick engineering purposes. The bounds correspond to product-form modifications and are intuitively appealing. A formal proof of the bounds and related monotonicity results will be presented. The technique of this proof, which is based on Markov reward theory, is of interest in itself and seems promising for further application. The extension to the non-exponential case is discussed. For multiserver loss stations the bounds are argued to be insensitive.     

Multistability of neural networks with discontinuous activation function

In this paper, the multistability is studied for two-dimensional neural networks with multilevel activation functions. And it is showed that the system has n² isolated equilibrium points which are locally exponentially stable, where the activation function has n segments. Furthermore, evoked by periodic external input, n² periodic orbits which are locally exponentially attractive, can be found. And these results are extended to k-neuron networks, which is really enlarge the capacity of the associative memories. Examples and simulation results are used to illustrate the theory.     

Minimal interatomic distance in Morse clusters

In this paper we derive a lower bound, independent from the number of atoms N, for the minimal interatomic distances between atoms in a cluster whose total energy is modelled by means of the so called Morse potential. A similar result was previously proven for Lennard–Jones clusters but the proof can not be extended to Morse clusters. Besides the theoretical interest, the derivation of this lower bound is important for the definition of efficient procedures for the computation of the total energy of clusters with a large number of atoms.     

Adaptive cluster synchronization in directed networks with nonidentical nonlinear dynamics

In this article, the problem of cluster synchronization in the complex networks with nonidentical nonlinear dynamics is considered. By Lyapunov functional and M‐matrix theory, some sufficient conditions for cluster synchronization are obtained. Moreover, the least number of nodes which should be pinned is given. It is shown that when the root nodes of all the clusters are pinning‐controlled, cluster synchronization with adaptive coupling strength can be achieved. Different from the constraints of many literatures, the assumption is that each row sum for all diagonal submatrices of the Laplacian matrix is equal to zero. Finally, a numerical simulation in the network with three scale‐free subnetwork is provided to demonstrate the effectiveness of the theoretical results. © 2016 Wiley Periodicals, Inc. Complexity 21: 380–387, 2016     

Bottleneck analysis in multiclass closed queueing networks and its application

Asymptotic behavior of queues is studied for large closed multi-class queueing networks consisting of one infinite server station with K classes and M processor sharing (PS) stations. A simple numerical procedure is derived that allows us to identify all bottleneck PS stations. The bottleneck station is defined asymptotically as the station where the number of customers grows proportionally to the total number of customers in the network, as the latter increases simultaneously with service rates at PS stations. For the case when K=M=2, the set of network parameters is identified that corresponds to each of the three possible types of behavior in heavy traffic: both PS stations are bottlenecks, only one PS station is a bottleneck, and a group of two PS stations is a bottleneck while neither PS station forms a bottleneck by itself. In the last case both PS stations are equally loaded by each customer class and their individual queue lengths, normalized by the large parameter, converge to uniformly distributed random variables. These results are directly generalized for arbitrary K=M. Generalizations for K≠M are also indicated. The case of two bottlenecks is illustrated by its application to the problem of dimensioning bandwidth for different data sources in packet-switched communication networks. An engineering rule is provided for determining the link rates such that a service objective on a per-class throughput is satisfied. This revised version was published online in June 2006 with corrections to the Cover Date.     

A new perspective on the normalization of invariant measures for loss networks and other product form systems

Loss networks have proved to be a vital tool in the study of telecommunication networks, computer performance, and resource allocation problems. For a large subset of these models, the invariant measure is of a product form. The existence of efficient procedures to normalize a product-form invariant measure is essential for analysis of the underlying system.Choudhury et al. [1—4] have recently presented a number of algorithms based upon Fourier analysis for the normalization of product-form invariant measures for specific systems. Bean and Stewart [5] discussed related work for the normalization of product-form invariant measures for closed queueing networks. In this paper, we present a simple unifying framework within which to study these algorithms. This framework is significant as it suggests a number of extensions to these algorithms and simplifies their derivation.     

Asymptotic analysis for closed multiclass queueing networks in critical usage

We consider a class of closed multiclass queueing networks containing First-Come-First-Serve (FCFS) and Infinite Server (IS) stations. These networks have a productform solution for their equilibrium probabilities. We study these networks in an asymptotic regime for which the number of customers and the service rates at the FCFS stations go to infinity with the same order. We assume that the regime is in critical usage, whereby the utilizations of the FCFS servers slowly approach one. The asymptotic distribution of the normalized queue lengths is shown to be in many cases a truncated multivariate normal distribution. Traffic conditions for which the normalized queue lengths arealmost asymptotically independent are determined. Asymptotic expansions of utilizations and expected queue lengths are presented. We show through an example how to obtain asymptotic expansions of performance measures when the networks are in mixed usage and how to apply the results to networks with finite data.Supported partially by NSF grant NCR93-04601.     

Large Closed Queueing Networks in Semi-Markov Environment and Their Application

The paper studies closed queueing networks containing a server station and k client stations. The server station is an infinite server queueing system, and client stations are single-server queueing systems with autonomous service, i.e. every client station serves customers (units) only at random instants generated by a strictly stationary and ergodic sequence of random variables. The total number of units in the network is N. The expected times between departures in client stations are (N μ _j )⁻¹. After a service completion in the server station, a unit is transmitted to the jth client station with probability p _j (j=1,2,…,k), and being processed in the jth client station, the unit returns to the server station. The network is assumed to be in a semi-Markov environment. A semi-Markov environment is defined by a finite or countable infinite Markov chain and by sequences of independent and identically distributed random variables. Then the routing probabilities p _j (j=1,2,…,k) and transmission rates (which are expressed via parameters of the network) depend on a Markov state of the environment. The paper studies the queue-length processes in client stations of this network and is aimed to the analysis of performance measures associated with this network. The questions risen in this paper have immediate relation to quality control of complex telecommunication networks, and the obtained results are expected to lead to the solutions to many practical problems of this area of research.      

Random permutations of countable sets

Summary The main objective of this paper is a study of random decompositions of random point configurations onR ^d into finite clusters. This is achieved by constructing for each configurationZ a random permutation ofZ with finite cycles; these cycles then form the cluster decomposition ofZ. It is argued that a good candidate for a random permutation ofZ is a Gibbs measure for a certain specification, and conditions are given for the existence and uniqueness of such a Gibbs measure. These conditions are then verified for certain random configurationsZ.     

GMRES and the minimal polynomial

We present a qualitative model for the convergence behaviour of the Generalised Minimal Residual (GMRES) method for solving nonsingular systems of linear equationsAx =b in finite and infinite dimensional spaces. One application of our methods is the solution of discretised infinite dimensional problems, such as integral equations, where the constants in the asymptotic bounds are independent of the mesh size.Our model provides simple, general bounds that explain the convergence of GMRES as follows: If the eigenvalues ofA consist of a single cluster plus outliers then the convergence factor is bounded by the cluster radius, while the asymptotic error constant reflects the non-normality ofA and the distance of the outliers from the cluster. If the eigenvalues ofA consist of several close clusters, then GMRES treats the clusters as a single big cluster, and the convergence factor is the radius of this big cluster. We exhibit matrices for which these bounds are tight.Our bounds also lead to a simpler proof of existing r-superlinear convergence results in Hilbert space.This research was partially supported by National Science Foundation grants DMS-9122745, DMS-9423705, CCR-9102853, CCR-9400921, DMS-9321938, DMS-9020915, and DMS-9403224.     

Comparing Theories of Infinite Resistive 1-Networks

Flanders' Hilbert space or finite power theory of infinite networks was extended to 1-networks by Zemanian. A new approach uses approximation by finite networks, a-priori bounds from no-gain properties, and Arzela–Ascoli, in a continuous function space. This paper compares, contrasts and reconciles these existence and uniqueness theories.     

An approximation method for general closed queuing networks with Fork/Join mechanisms

Queuing networks with Fork/Join mechanisms are encountered in modelling and analysis of parallel computer systems and computer/communication networks. Exact analytical solutions of such networks are not available. In particular, due to the Fork/Join mechanisms, these networks do not have a product-form solution. As a result, approximation methods that can provide accurate estimates of the performance parameters are of high interest. The purpose of this paper is to propose such an approximation method that applies to a fairly general class of closed queuing networks with Fork/Join mechanisms. The method is based on the use of a product-form approximation technique. Numerical results are provided that show that the accuracy of the method is fairly good.     

On a class of approximations for closed queueing networks

This paper presents some analytical results concerning an approximation procedure for closed queueing networks. The procedure is well-known and has been found useful for product-form networks where large numbers of queues, jobs or job classes prohibit an exact analysis, as well as for networks which do not possess product-form. The procedure represents the mean sojourn time at a queue as a function of the throughput of the queue, and derives a set of fixed point equations for the throughputs of the various job classes. We begin by showing that under a mild regularity condition the fixed point equations have a unique solution. Then we show that derivatives of performance measures can be readily calculated, and that their simple form provides an interesting insight into capacity allocation in closed queueing networks.This work was supported in part by the Nuffield Foundation     

Applications of BGP-reflection functors: isomorphisms of cluster algebras

Given a symmetrizable generalized Cartan matrix A, for any index k, one can define an automorphism associated with A, of the field Q(u1,…, un) of rational functions of n independent indeterminates u1,…,un.It is an isomorphism between two cluster algebras associated to the matrix A (see sec. 4 for the precise meaning). When A is of finite type, these isomorphisms behave nicely; they are compatible with the BGP-reflection functors of cluster categories defined in a previous work if we identify the indecomposable objects in the categories with cluster variables of the corresponding cluster algebras, and they are also compatible with the "truncated simple reflections" defined by Fomin-Zelevinsky. Using the construction of preprojective or preinjective modules of hereditary algebras by DIab-Ringel and the Coxeter automorphisms (i.e. a product of these isomorphisms), we construct infinitely many cluster variables for cluster algebras of infinite type and all cluster variables for finite types.     

Quasi-reversibility of a discrete-time queue and related models

We consider a discrete-time queueing system and its application to related models. The model is defined byX _n+1=X_n+A_n-D_n+1 with discrete states, whereX _n is the queue-length at the nth time epoch,A _n is the number of arrivals at the start of the nth slot andD _n+1 is the number of outputs at the end of the nth slot. In this model, the arrival process {A _n} is described as a sequence of independently and identically distributed random variables. The departureD _n+1 depends only on the system sizeX _n+A_n at the beginning of the time slot.We study the reversibility for the model. The departure discipline in which the system has quasi-reversibility is determined. Models with special arrival processes were studied by Walrand [8] and sawa [7]. In this paper, we generalize their results. Moreover, we consider discrete-time queueing networks with some reversible nodes. We then obtain the product-form solution for these networks.     

Existence and characterization of product-form invariant distributions for state-dependent stochastic networks in the heavy-traffic diffusion limit

We consider state-dependent stochastic networks in the heavy-traffic diffusion limit represented by reflected jump-diffusions in the orthant ℝ₊ ⁿ with state-dependent reflection directions upon hitting boundary faces. Jumps are allowed in each coordinate by means of independent Poisson random measures with jump amplitudes depending on the state of the process immediately before each jump. For this class of reflected jump-diffusion processes sufficient conditions for the existence of a product-form stationary density and an ergodic characterization of the stationary distribution are provided. Moreover, such stationary density is characterized in terms of semi-martingale local times at the boundaries and it is shown to be continuous and bounded. A central role is played by a previously established semi-martingale local time representation of the regulator processes. F.J. Piera’s research supported in part by CONICYT, Chile, FONDECYT Project 1070797. R.R. Mazumdar’s research supported in part by NSF, USA, Grant 0087404 through Networking Research Program, and a Discovery Grant from NSERC, Canada.     

A second-order space–time accurate scheme for nonlinear diffusion equation with general capacity term

A fully implicit finite difference (FIFD) scheme with second-order space–time accuracy is studied for a nonlinear diffusion equation with general capacity term. A new reasoning procedure is introduced to overcome difficulties caused by the nonlinearity of the capacity term and the diffusion operator in the theoretical analysis. The existence of the FIFD solution is investigated at first which plays an important role in the analysis. It is established by choosing a new test function to bound the solution and its temporal and spatial difference quotients in suitable norms in the fixed point arguments, which is different from the traditional way. Based on these bounds, other fundamental properties of the scheme are rigorously analyzed consequently. It shows that the scheme is uniquely solvable, unconditionally stable, and convergent with second-order space–time accuracy in L^∞(L²) and L^∞(H¹) norms. The theoretical analysis adapts to both one- and multidimensional problems, and can be extended to schemes with first-order time accuracy. Numerical tests are provided to verify the theoretical results and highlight the high accuracy of the second-order space–time accurate scheme. The reasoning techniques can be extended to a broad family of discrete schemes for nonlinear problems with capacity terms.