Blocking Probabilities in Mobile Communications Networks with Time-Varying Rates and Redialing Subscribers

Call-blocking probabilities are among the key performance measures in mobile communications networks. For their analysis, mobile networks can be modelled as networks of Erlang loss queues with common capacity restrictions dictated by the allocation of frequencies to the cells of the network. However, due to the time-varying load offered to the cells of such networks, blocking probabilities usually cannot be obtained in closed form. The relation between networks of Erlang loss queues and networks of infinite server queues, for which the time-dependent occupancy distribution is multidimensional Poisson, suggests to use that distribution as approximate distribution for the network of Erlang loss queues. This paper extends this so-called Modified Offered Load (MOL) approximation to networks of Erlang loss queues, and also allows subscribers that find their call blocked to redial to continue their call. For GSM networks operating under Fixed Channel Allocation, it is shown that blocking probabilities are increasing in the redial rates so that the MOL approximation that is most accurate for maximal redial rates turns out to be fairly accurate for the resulting upper bound for blocking probabilities. The accuracy is explicitly evaluated in an application of the results towards blocking probabilities in a hot spot travelling along a road through a GSM network.     

On the blocking process in queue networks

The blocking process in some particular exponential open queue networks is studied. The networks are in the form of two-stage and three-stage queue networks with finite intermediate waitingroom. FIFO scheduling is assumed. Blocking occurs when the flow of units through one queue is momentarily stopped owing to a capacity limitation of another queue have been reached. Exact and approximate bounds for the mean blocking time in these networks are obtained. The condition for stability in the two-stage networks is also derived. Finally the applicability of the results obtained is demonstrated through a case study.     

A survey of product form queueing networks with blocking and their equivalences

Queueing network models have been extensively used to represent and analyze resource sharing systems, such as production, communication and information systems. Queueing networks with blocking are used to represent systems with finite capacity resources and with resource constraints. Different blocking mechanisms have been defined and analyzed in the literature to represent distinct behaviors of real systems with limited resources. Exact product form solutions of queueing networks with blocking have been derived, under special constraints, for different blocking mechanisms. In this paper we present a survey of product form solutions of queueing networks with blocking and equivalence properties among different blocking network models. By using such equivalences we can extend product form solutions to queueing network models with different blocking mechanisms. The equivalence properties include relationships between open and closed product form queueing networks with different blocking mechanisms.This work has been partially supported by CNR Project Research Funds Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo and by MURST Project Research Funds Performability hw/sw di sistemi distribuiti e paralleli.     

The blocking probability of spider-web networks

We determine the limiting behavior of the blocking probability for spider-web networks, a class of crossbar switching networks proposed by Ikeno. We use a probabilistic model proposed by the author, in which the busy links always form disjoint routes through the network. We show that if the occupancy probability is below the threshold 2 - √2 = 0.5857…, then the blocking probability tends to zero, whereas above this threshold it tends to one. This provides a theoretical explanation for results observed empirically in simulations by Bassalygo, Neiman, and Vvedenskaya.     

Approximate analysis of arbitrary configurations of open queueing networks with blocking

An algorithm for analyzing approximately open exponential queueing networks with blocking is presented. The algorithm decomposes a queueing network with blocking into individual queues with revised capacity, and revised arrival and service processes. These individual queues are then analyzed in isolation. Numerical experience with this algorithm is reported for three-node and four-node queueing networks. The approximate results obtained were compared against exact numerical data, and they seem to have an acceptable error level.Supported in part by a grant from CAIP Center, Rutgers University.Supported in part by the National Science Foundation under Grant DCR-85-02540.     

Insensitive versus efficient dynamic load balancing in networks without blocking

So-called Whittle networks have recently been shown to give tight approximations for the performance of non-locally balanced networks with blocking, including practical routing policies such as joining the shortest queue. In the present paper, we turn the attention to networks without blocking. To this end, we consider a set of “insensitive” dynamic load balancing schemes preserving the structure of Whittle networks in the case of infinite buffers and examine their efficiency. Using Hausdorff’s theorem, we prove that the optimal insensitive schemes are static in this case, i.e., routing decisions do not depend on the current state of the queues. On the other hand, simulations show that the performance of static policies is generally much worse than that of “non balanced” sensitive dynamic policies. This demonstrates that strict insensitivity and efficiency may be incompatible objectives for networks with dynamic load balancing in case of infinite buffers. AMS Subject Classifications 60K25 · 68M20     

A decomposition-related throughput property of tandem queueing networks with blocking

A general throughput property of tandem queueing networks with blocking that relates existing decomposition methods to throughput bounds is discussed using the sample path approach.     

A heuristic for blocking flow algorithms

This note presents a simple heuristic to speed up algorithms for the maximum flow problem that works by repeatedly finding blocking flows in layered (acyclic) networks. The heuristic assigns a capacity to each vertex of the layered network, which will be an upper bound on the amount of flow that can be transported through that vertex to the sink. This information can be utilized when constructing a blocking flow, since no vertex can ever accommodate more flow than its capacity. The static heuristic computes capacities in a layered network once, while a dynamic variant readjusts capacities during construction of the blocking flow.The effects of both static and dynamic heuristics are evaluated by a series of experiments with the wave algorithm of Tarjan. Although neither give theoretical improvement to the efficiency of the algorithm, the practical effects are in most cases worthwhile, and for certain types of networks quite dramatic.     

On Jackson's product form with ‘jump-over’ blocking

It is shown that Jackson's product form is retained for queueing networks with capacity constraints under the assumption of a ‘jump-over’ blocking protocol.     

生产流水线中的排队问题

本文讨论产品以Poisson过程到达,有K道加工工序,每加工点是有限容量且服务服从指数分布带受阻的排队网络,并给出了平稳条件和在平稳条件下以三节点组合逼近方法得到平均队长．     

On evaluation of the blocking probability in multiwave time division multiplexing networks

A new technique of estimating the blocking probability in multiwave time division multiplexing networks is proposed. The technique is based on solution of combinatorial problems of calculating the number of compositions with bounded parts.     

Bounding blocking probabilities and throughput in queueing networks with buffer capacity constraints

We propose a new technique for upper and lower bounding of the throughput and blocking probabilities in queueing networks with buffer capacity constraints, i.e., some buffers in the network have finite capacity. By studying the evolution of multinomials of the state of the system in its assumed steady state, we obtain constraints on the possible behavior of the system. Using these constraints, we obtain linear programs whose values upper and lower bound the performance measures of interest, namely throughputs or blocking probabilities. The main advantages of this new technique are that the computational complexity does not increase with the size of the finite buffers and that the technique is applicable to systems in which some buffers have infinite capacity. The technique is demonstrated on examples taken from both manufacturing systems and communication networks. As a special case, for the M/M/s/s queue, we establish the asymptotic exactness of the bounds, i.e., that the bounds on the blocking probability asymptotically approach the exact value as the degree of the multinomials considered is increased to infinity. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal network configuration and capacity expansion of railroads

Railroads ship individual cars according to blocking plans that route the cars in groups (blocks) that share common intermediate stops. An individual shipment is regrouped (reclassified) two to three times along the way from its origin to destination. Yards are crucial facilities of the rail network where cars are reclassified according to such blocking plans. Therefore, yard locations and the blocking plan impose the detour and classification of cars over the physical network. Yards are capacitated with respect to number of blocks made and number of cars classified; rail lines between major stations are capacitated with respect to number of cars that pass through. These restrictions are accounted for in designing the blocking plans. Changing the yard locations and expanding associated capacities may result in dramatic changes in blocking plans saving tens of millions of dollars in railroad transportation costs. We develop a mathematical programming formulation and propose solution methods for the yard location problem and the capacity expansion problems. We demonstrate that the railroads can save significantly by reconfiguring their networks.     

Symmetry property of the throughput in closed tandem queueing networks with finite buffers

In this paper we consider closed tandem queueing networks with finite buffers and blocking before service. With this type of blocking, a server is allowed to start processing a job only if there is an empty space in the next buffer. It was recently conjectured that the throughput of such networks is symmetrical with respect to the population of the network. That is, the throughput of the network with population N is the same as that with population C − N, where C is the total number of buffer spaces in the network. The main purpose of this paper is to prove this result in the case where the service time distributions are of phase type (PH-distribution). The proof is based on the comparison of the sample paths of the network with populations N and C − N. Finally, we also show that this symmetry property is related to a reversibility property of this class of networks.     

Deadlock free buffer allocation in closed queueing networks

Blocking queueing networks are of much interest in performance analysis due to their realistic modeling capability. One important feature of such networks is that they may have deadlocks which can occur if the node capacities are not sufficiently large. A necessary and sufficient condition for the node capacities is presented such that the network is deadlock free. An algorithm is given for buffer allocation in blocking queueing networks such that no deadlocks will occur assuming that the network has the special structure called cacti-graph. Additional algorithm which takes linear time in the number of nodes, is presented to find cycles in cacti networks.Akyildiz's work was supported in part by School of Information and Computer Science, ICS, of Georgia Tech and by the Air Force Office of the Scientific Research (AFOSR) under Grant AFOSR-88-0028.     

Fast simulation of blocking probabilities in loss networks

This paper is concerned with the determination of blocking probabilities in loss networks. In fact, our study consists of two parts. Primarily, we scale both arrival rates and link capacities, in order to derive rough asymptotical expressions. These expressions arise as the result of mathematical programming problems. Secondly, we develop a fast simulation technique to estimate the blocking probabilities. This technique is based on importance sampling, where the choice of the alternative probability model is closely related to the optimizing arguments of the above mentioned mathematical programming problem. Some examples show that huge gain of simulation effort can be achieved.     

Virtual Path Design in Service-Specific ATM Networks

This paper addresses the problem of virtual path management in ATM networks, which is the problem of jointly selecting efficient virtual trunk routes and sizing them to meet end-to-end grade-of-service requirements. The problem is posed over capacitated networks and is formulated as a two-level multi-commodity network flow problem with linear side-constraints (physical layer capacity) and non-linear side constraints (end-to-end/link blocking). Through a variety of examples we show the method (i) generates solutions that agree with engineering judgement, (ii) can solve VP layout management for realistic size networks (of up to 200 nodes) in reasonable time and (iii) provides upper bounds on how far the solution strays from the mathematically optimal design.     

Local balance in queueing networks with positive and negative customers

This paper investigates to what extent a recently developed new product form result for queueing networks with positive and negative customers fits into the class of product form queueing networks that satisfy a notion of partial or local balance. As such, this paper investigates whether this new product form is still a consequence of an appropriate notion of local balance. To this end, a new and non-standard type of local balance is introduced as an extension of standard local balance. This new type of local balance appears more restrictive and is no longer directly sufficient for global balance. Nevertheless, based on this new type of local balance, some extensions such as blocking phenomena for queueing networks with positive and negative customers can be concluded.     

ATM Routing Algorithms for Multimedia Traffic in Private ATM Networks

The goal of this paper is to recommend a good Private Network-to-Network Interface (PNNI) routing algorithm for private ATM networks. A good routing algorithm has to work well with multimedia traffic with several quality of service (QoS) requirements (such as cell loss ratio, cell delay and its variation etc.) in different networks under various traffic conditions. The multiplicity of QoS requirements makes the routing problem NP-complete, so our approach to the problem is based on large scale simulations involving several empirical algorithms (compliant with the PNNI routing specification) which have been tested for different network topologies and traffic scenarios. Based on analysis of tradeoffs involving performance metrics (such as blocking rate, complexity, load distribution) we recommend a consistently good routing algorithm for single domain ATM networks.