Modern Probabilistic Methods for Analysis of Telecommunication Networks

Frontmatter

Analysis of Queueing System with Constant Service Time for SIP Server Hop-by-Hop Overload Control

Abstract

Consideration is given to the analysis of queueing system M ₂|D|1|R with bi-level hysteretic input load control that can model signalling hop-by-hop overload control mechanism for SIP servers described in RFC 6357. Bi-level hysteretic input load control implies that system may be in three states (normal, overloaded, blocking), depending on the total number of customers present in it, and upon each state change input flow rate is adjusted. New approach that allows fast computation of joint stationary probability distribution is proposed, expressions for important performance characteristics are given.

Pavel Abaev, Alexander Pechinkin, Rostislav Razumchik

On Mean Return Time in Queueing System with Constant Service Time and Bi-level Hysteric Policy

Abstract

Single server queueing system with two Poisson input flows of rate λ ₁ and λ ₂, finite queue of size R − 1 < ∞ and bi-level hysteretic policy is considered. Customers of λ ₁ flow are served with relative priority. Customers of both flows are served with the same constant service time. Bi-level hysteretic policy implies that system may be in three states (normal, overload, blocking), depending on the total number of customers present in it. New method for calculation of mean return time to normal operation state is proposed.

Pavel Abaev, Alexander Pechinkin, Rostislav Razumchik

Discrete-Time Queueing System with Expulsions

Abstract

In this paper we analyze a discrete-time queueing system in which an arriving customer can decide, with a certain probability, to go directly to the server expelling out of the system the customer that is currently in service or to join the queue in the last place. The arrivals are assumed to be geometrical and the service times are arbitrarily distributed. We present some numerical examples in order to illustrate the effect of the parameters on several performance characteristics.

Iván Atencia, Inmaculada Fortes, Sixto Sánchez

Stationary Distribution Invariance of an Open Queueing Network with Temporarily Non-active Customers

Abstract

This paper considers stationary functioning of an open queueing network with temporarily non-active customers. Non-active customers are in a system queue and do not get service. Customers can pass from non-active state into state, when they can get their service and vice versa. Stationary distribution invariance with reference to service time distribution functional form is obtained.

Julia Bojarovich, Yury Malinkovsky

An Open Queueing Network with Temporarily Non-active Customers and Rounds

Abstract

An open queueing network with partly non-active customers is considered. Non-active customers are in a system queue and do not get service. Customers can pass from non-active state into state, when they can get their service and vice versa. The form of stationary distribution and conditions of stationary distribution existence are obtained.

Julia Bojarovich, Larisa Marchenko

Analysis of MAP/PH/c Retrial Queue with Phase Type Retrials – Simulation Approach

Abstract

In this paper we study a multi-server retrial queueing model in which customers arrive according to a Markovian arrival process (MAP) and the service times are assumed to be of phase type (PH-type). An arriving customer finding all servers busy will enter into a (retrial) orbit of infinite size. The customers in orbit will try to capture a free server after a random amount of time which is assumed to be of PH-type. Thus, every customer in the orbit has his/her own phase type distribution before attempting to get into service. Due to the complexity of the model and lack of attention to such models in the literature, we study this via simulation. After validating our simulated results against known results (both exact and approximation) for some special cases, we illustrate how one can underestimate or overestimate some key system performance measures by incorrectly assuming the retrial times to be exponential.

Srinivas R. Chakravarthy

Fluid Flow Analysis of RED Algorithm with Modified Weighted Moving Average

Abstract

We study with the use of fluid flow approximation the impact of a modified weighted moving average on the performance of RED mechanism. A model of TCP/UDP connection with RED implemented in an intermediate IP router is used, the weighted moving average is determined on the basis of a difference (recursive) equation. The fluid flow approximation technique is applied to model the interactions between the set of TCP/UDP flows and RED mechanism.

Joanna Domańska, Adam Domański, Tadeusz Czachórski

A Tandem Queueing System with Batch Session Arrivals

Abstract

We consider a tandem queueing system with session arrivals. Session means a group of customers which should be sequentially processed in the system. In contrast to the standard batch arrival when a whole group of customers arrives into the system at one epoch, we assume that the customers of an accepted session arrive one by one in exponentially distributed times. Generation of sessions at the first stage is described by a Batch Markov Arrival Process (BMAP). At the first stage of tandem, it is determined whether a session has the access to the second stage. After the first stage the session moves to the second stage or leaves the system. At the second stage having a finite buffer the customers from sessions are serviced. A session consists of a random number of customers. This number is geometrically distributed and is not known at a session arrival epoch. The number of sessions, which can be admitted into the second stage simultaneously, is subject to control. An accepted session can be lost, with a given probability, in the case of any customer from this session rejection.

Sergey Dudin, Olga Dudina

Socio-behavioral Scheduling of Time-Frequency Resources for Modern Mobile Operators

Abstract

This article presents a mathematical foundation for scheduling of batch data produced by mobile end users over the time-frequency resources provided by modern mobile operators. We model the mobile user behavior by Batch Markovian Arrival Process, where a state corresponds to a specific user data activity (i.e. sending a photo, writing a blog message, answering an e-mail etc). The state transition is marked by issuing a batch of data of the size typical to the activity. To model the changes of user behavior caused by the environment, we introduce a random environment which affects the intensities of transitions between states (i.e., the probabilities of the user data activities). The model can be used for calculating probability of packet loss and probability of exceeding the arbitrarily fixed value by the sojourn time of a packet in the system conditional that the packet arrives to the system at moments when the random environment has a given state. This allows to compute the realistic values of these probabilities and can help to properly fix their values that can be guaranteed, depending on the state of the random environment, by a service provider.

Alexander Dudin, Evgeny Osipov, Sergey Dudin, Olov Schelén

Queueing System MAP/M/N/N + K Operating in Random Environment as a Model of Call Center

Abstract

A multi-server queueing system with a Markovian Arrival Process (MAP), a finite buffer and impatient customers operating in random environment as a model of a call center is investigated. The service time of a customer by a server has an exponential distribution. If all servers are busy at a customer arrival epoch, the customer may leave the system forever or move to the buffer with probability that depends on the number of customers in the buffer. During a waiting period, a customer can be impatient and can leave the system without the service. System parameters depend on the state of the random environment. An efficient algorithm for calculating the stationary probabilities of system states is proposed. Some key performance measures are calculated. The Laplace-Stieltjes transforms of the sojourn and waiting time distributions are derived.

Olga Dudina, Sergey Dudin

Optimal Choice of the Capacities of Telecommunication Networks to Provide QoS-Routing

Abstract

The problems of telecommunication networks designing could be presented into three aspects: 1) choice of the capacity for each telecommunication link with total minimum network cost; 2) QoS-routing of multicommodity flows in the synthesized network for all forecasting demands and 3) providing a necessary level of survivability. We consider QoS-routing, taking into account various performance requirements: delay, variation of the delay (jitter), bandwidth, packet loss probability. In this article we consider QoS-routing adding to consideration new constraints which provide the delay requirements as the important part of QoS.

E. Girlich, M. M. Kovalev, N. I. Listopad

A Retrial Tandem Queue with Two Types of Customers and Reservation of Channels

Abstract

We consider a retrial tandem queue with two multi-server stations which can be considered as a mathematical model of a call center with two types of customers classified by their ability to wait for the connection to the agent. Customers arrive at Station 1 according the stationary Poisson flow. If an arriving customer meets all servers busy he/she goes to the infinite size orbit and retries after a random time. The type of a customer is randomly determined upon completion of the service at Station 1. If all servers of Station 2 are busy type 1 (priority) customer leaves the system forever while type 2 (non-priority) customer is queued in the buffer of limited size. If the buffer is full this customer leaves the system. The customers staying in the queue are impatient. This means that they might decide to leave the system before their service at Station 2 begins. It is assumed that a number of servers of Station 2 can be reserved to serve priority customers only. We calculate the stationary distribution and the main performance measures of the system. The cost function evaluating quality of service under different number of reserved server is constructed. Illustrative numerical example is presented.

Valentina Klimenok, Roman Savko

Some Aspects of Waiting Time in Cyclic-Waiting Systems

Abstract

We consider a queueing system with Poisson arrivals and exponentially distributed service time and FCFS service discipline. The service of a customer is started at the moment of arrival (in case of free system) or at moments differing from it by the multiples of a given cycle time T (in case of occupied server or waiting queue). The waiting time is always the multiple of cycle time T, one finds its generating function and mean value. The characteristics of service are illustrated by numerical examples. If we measure the waiting time by means of number of cycles, we can optimize the cycle time T.

Laszlo Lakatos, Dmitry Efroshinin

Gaussian Approximation of Multi-channel Networks in Heavy Traffic

Abstract

In the paper the multichannel stochastic networks are considered. From the outside on each node of the network a Poisson input flow of calls arrives. An approximate method of studying of the service process at heavy traffic regime is developed. The limit process is represented as a multidimensional diffusion.

Eugene Lebedev, Ganna Livinska

Performance Evaluation of Finite Buffer Queues through Regenerative Simulation

Abstract

In this paper we discuss the estimation of the loss probability in a queueing system with finite buffer fed by Brownian traffic, the Gaussian counterpart of the well-known Poisson process. The independence among arrivals in consecutive time slots allows the application of regenerative simulation technique, combined with the so-called Delta-method to construct confidence intervals for the stationary loss probability. Numerical simulation are carried out to verify the efficiency of the regenerative approach for different values of the queue parameters (buffer size and utilization) as well as simulation settings (digitization step and generalizations of the regeneration cycle).

Oleg Lukashenko, Evsey Morozov, Ruslana Nekrasova, Michele Pagano

Finite Source Retrial Queues with State-Dependent Service Rate

Abstract

This paper deals with the research of finitesource retrial queues whose service rate depends on queue length. Two- and three-dimensional models that describe threshold and hysteresis control policies are taken into account. Explicit vector-matrix representations of stationary distributions are main results in both cases.

Vadym Ponomarov, Eugene Lebedev

Multidimensional Alternative Processes Reliability Models

Abstract

Multidimensional alternative processes are introduced, their stationary and quasi-stationary probabilities are investigated, and their applications in reliability models are considered.

Vladimir Rykov

BMAP/G/1 Cyclic Polling Model with Binomial Disciplines

Abstract

The paper deals with the analysis of BMAP/G/1 cyclic polling model with binomial-gated and binomial-exhaustive disciplines. The analysis relies on formerly applied methodology, in which the service discipline independent and service discipline dependent parts of the analysis are treated separately. In this work we complete the service discipline dependent part of the analysis for the binomial disciplines. This leads to a governing equation of the system in terms of the steady-state number of customers at the server arrival and departure epochs. A numerical procedure can be established based on the newly derived results together with formerly obtained service discipline independent results to determine the steady-state factorial moments of the number of customers in the system.

Zsolt Saffer

Analysis of Fluid Queues in Saturation with Additive Decomposition

Abstract

Fluid queueing models with finite capacity buffers are applied to analyze a wide range of real life systems. There are well established numerical procedures for the analysis of these queueing models when the load is lower or higher than the system capacity, but these numerical methods become unstable as the load gets close to the system capacity. One of the available numerical procedures is the additive decomposition method proposed by Nail Akar and his colleagues.

The additive decomposition method is based on a separation of the eigenvalues of the characterizing matrix into the zero eigenvalue, the eigenvalues with positive real part and the eigenvalues with negative real part. The major problem of the method is that the number of zero eigenvalues increases by one at saturation. In this paper we present an extension of the additive decomposition method which remain numerically stable at saturation as well.

Miklós Telek, Miklós Vécsei

Queue-Size Distribution in M/G/1-Type System with Bounded Capacity and Packet Dropping

Abstract

A single-server queueing system of M/G/1-type with boun- ded total volume is considered. It is assumed that volumes of arriving packets are generally distributed random variables. The AQM-type mechanism is used to control the actual buffer state: each of arriving packets is dropped with probability depending on its volume and the occupied volume of the system at the pre-arrival epoch. The explicit formulae for the stationary queue-size distribution and loss probability are found.

Oleg Tikhonenko, Wojciech M. Kempa

Use of Time-Scale for Analysis of Data Source Traffic

Abstract

In this paper, we consider the model of server traffic when the traffic is separated into several streams. The amount of transferred data differs for different streams. Based on real traffic measurements we proposed the server traffic model where traffic of every stream is described by the same independent processes, but each process has its own time scale. We show that for traffic analysis as well as for developing of the most effective methods of control of this traffic, it is necessary to correctly identify the time scale for each stream, as well as the time scale of traffic fluctuations those have a significant effect to QoS.

Ivan Titov, Ivan Tsitovich, Stoyan Poryazov

On a Queueing Model with Group Services

Abstract

An analogue of M _t /M _t /S/S Erlang loss system for a queue with group services is introduced and considered. Weak ergodicity of the model is studied. We obtain the bounds on the rate of convergence to the limiting characteristics and consider two concrete queueing models with finding of their main limiting characteristics.

Alexander Zeifman, Anna Korotysheva, Yakov Satin, Galina Shilova, Tatyana Panfilova

Study of Queues’ Sizes in Tandem Intersections under Cyclic Control in Random Environment

Abstract

Tandem queueing systems under cyclic control with readjustments are investigated. Conflict input flows are formed in a random synchronious environment. Transition of customers from the first system to the second system occurs with random speeds. Two communicating intersections give an example of such a tandem. The blocks of the systems are described nonlocally. A mathematical model is constructed in form of a multidimensional denumerable discrete-time Markov chain. Limit behaviour of queues’ sizes is studied.

Andrei Zorine

Backmatter