Search

Aim. The paper primarily aims to simulate the operation of railway transportation systems using the queueing theory with the case study of marshalling yards. The goals also include the development of the methods and tools of mathematical simulation and queueing theory. Methods. One of the pressing matters of modern science is the development of methods of mathematical simulation of transportation systems for the purpose of analyzing the efficiency, stability and dependability of their operation while taking into account random factors. Research has shown that the use of the most mature class of such models, the singlephase Markovian queueing systems, does not enable an adequate description of transportation facilities and systems, particularly in railway transportation. For that reason, this paper suggests more complex mathematical models in the form of queueing networks, i.e., multiple interconnected queueing systems, where arrivals are serviced. The graph of a queueing network does not have to be connected and circuit-free (a tree), which allows simulating transportation systems with random structures that are specified in table form as a so-called “routing matrix”. We suggest using the BMAP model for the purpose of describing incoming traffic flows. The Branch Markovian Arrival Process is a Poisson process with batch arrivals. It allows combining several different arrivals into a single structure, which, in turn, significantly increases the simulation adequacy. The complex structure of the designed model does not allow studying it analytically. Therefore, based on the mathematical description, a simulation model was developed and implemented in the form of software. Results. The developed models and algorithms were evaluated using the case study of the largest Russian marshalling yard. A computational experiment was performed and produced substantial recommendations. Another important result of the research is that significant progress was made in the development of a single method of mathematical and computer simulation of transportation hubs based on the queueing theory. That is the strategic goal of the conducted research that aims to improve the accuracy and adequacy of simulation compared to the known methods, as well as should allow extending the capabilities and applicability of the model-based approach. Conclusions. The proposed model-based approach proved to be a rather efficient tool that allows studying the operation of railway marshalling yards under various parameters of arrivals and different capacity of the yards. It is unlikely to completely replace the conventional methods of researching the operation of railway stations based on detailed descriptions. However, the study shows that it is quite usable as a primary analysis tool that does not require significant efforts and detailed statistics.

Discrete-time queueing models find a large number of applications as they are used in modeling queueing systems arising in digital platforms like telecommunication systems and computer networks. In this paper, we analyze an infinite-buffer queueing model with discrete Markovian arrival process. The units on arrival are served in batches by a single server according to the general bulk-service rule, and the service time follows general distribution with service rate depending on the size of the batch being served. We mathematically formulate the model using the supplementary variable technique and obtain the vector generating function at the departure epoch. The generating function is in turn used to extract the joint distribution of queue and server content in terms of the roots of the characteristic equation. Further, we develop the relationship between the distribution at the departure epoch and the distribution at arbitrary, pre-arrival and outside observer’s epochs, where the first is used to obtain the latter ones. We evaluate some essential performance measures of the system and also discuss the computing process extensively which is demonstrated by some numerical examples.

We investigate the effects of autonomous vehicles (AVs) on highway congestion. AVs have the potential to significantly reduce highway congestion, since these vehicles are able to maintain smaller inter-vehicle gaps and travel together in larger platoons (or batches) than human-driven vehicles (HVs). Various policies have been proposed to regulate AVs on highways, yet no in-depth comparison of these policies exists. To address this shortcoming, we develop a queueing model for a multi-lane highway, and analyze two policies for a mixed fleet of HVs and AVs: the designated-lane policy (“D policy”) under which one lane is designated to AVs, and the integrated policy (“I policy”) under which AVs travel together with HVs in all lanes. Our analysis connects the service rate of the queueing system to congestion on the highway, as well as inter-vehicle gaps using a Markovian arrival process (MAP). We measure the performance of these policies using mean travel time and throughput as metrics. We show that although the I policy performs at least as well as a benchmark case with no AVs, the D policy outperforms the benchmark only when the highway is heavily congested and AVs constitute the majority of vehicles; in such a case this policy may outperform the I policy as well. These findings caution against recent industry and government proposals that the D policy should be employed at the beginning of the mass appearance of AVs. Finally, we calibrate our model to data; our numerical analysis shows that for highly congested highways, a moderate number of AVs can make substantial improvement (e.g., 22% AVs can improve throughput by 30%), and when all vehicles are AVs, throughput can be increased over 400%.

This paper analyzes a finite-buffer queueing system, where customers arrive in batches and the accepted customers are served in batches by a single server. The service is assumed to be dependent on the batch-size and follows a general bulk service rule. The inter-arrival times of batches are assumed to be correlated and they are represented through the batch Markovian arrival process (BMAP). Computation procedure of the queue-length distributions at the post-batch-service completion, an arbitrary, and the pre-batch-arrival epochs are discussed. Various performance measures along with the consecutive customer loss probabilities are studied considering batch-size-dependent renewal service time distributions. Further, the above finite-buffer bulk-service queueing model is also investigated considering correlated batch-service times which are presented through the Markovian service process (MSP). The phase-dependent consecutive loss probabilities for the correlated batch-service times are determined. In the form of tables and graphs, a variety of numerical results for different batch-service time distributions are presented in this paper.

Queueing inventory models are extensively analysed since 1992. Very few among these discuss multi-commodity system. In this paper, we present a multi-commodity queueing inventory problem involving one essential and a set of m optional item(s). Immediately after the service of an essential item, the customer either leaves the system with probability p or with probability 1-p he goes for optional item(s). However, in the absence of an essential item, service will not be provided. More than one optional item can be demanded by the customer. The i th optional item or i th and j th optional items or i th, j th and k th and so on or all the optional items together, could be demanded by a customer, with probabilities $$p_{i}$$ , $$p_{ij}$$ , $$p_{ijk}$$ $$\ldots $$ $$p_{12\ldots m}$$ respectively. If the demanded optional item(s) is(are) not available, the customer leaves the system after purchasing the essential item. With the arrival of customers forming Markovian Arrival Process (MAP), service time of essential item Phase type distributed and that for optional items exponentially distributed( depending on the type(s) of item(s)), all given by the same (single) server, we analyse the system. Then we obtain the system state probability distribution. In-order to get a picture of how the system performs, we derive several characteristics of the system. With control policies for essential and optional items determined respectively, by (s, S) and ( $$s_{i}$$ , $$S_{i}$$ ), $$i=1,2,3,$$ ..., m, we investigate the optimal values of $$s,S,s_{i}$$ and $$S_{i}$$ s’. To this end, we set up a cost function, involving these control variables.

We consider a tandem queue consisting of two stations. We demonstrate that customer numbers and waiting times at both stations are independent of each other in the steady-state. As an optimal design, in the second station, We consider that there is a single channel that has the total service capacity of two parallel channels instead of two identical channels. Then, we indicate that the optimal system works faster than the tandem queue system with parallel channels at the second station. Also, when the total service capacity is limited, the mean waiting time in the system has been minimized in the optimal system obtained the mean waiting time lower limit. We compared it to those found through a numerical example.

The current investigation of our paper is concentrated on an infinite-buffer single-server queueing model with discrete-time batch Markovian arrival process and Markovian service process. The stead...

In this paper we consider a single server queueing model with under general bulk service rule with infinite upper bound on the batch size which we call group clearance. The arrivals occur according to a batch Markovian point process and the services are generally distributed. The customers arriving after the service initiation cannot enter the ongoing service. The service time is independent on the batch size. First, we employ the classical embedded Markov renewal process approach to study the model. Secondly, under the assumption that the services are of phase type, we study the model as a continuous-time Markov chain whose generator has a very special structure. Using matrix-analytic methods we study the model in steady-state and discuss some special cases of the model as well as representative numerical examples covering a wide range of service time distributions such as constant, uniform, Weibull, and phase type.

Queueing systems with batch Markovian arrival process (BMAP) have paramount applications in the domain of wireless communication. The BMAP has been used to model the superposition of video sources ...

In this paper, we study a double-sided queueing model with marked Markovian arrival processes and finite discrete abandonment times. We apply the theory of multi-layer Markov modulated fluid flow (...

In this paper we consider two single server queueing models with non-preemptive priority and working vacation under two distinct N-policies. High priority (type I) customers are served even in vacation mode whereas low priority (type II) customers are served only when the server comes to normal mode of service. Type I customers have only a limited waiting space L whereas type II customers have unlimited capacity. The two distinct N-policies are as described below: In model I, while service of type I customers are in progress in vacation mode (working vacation), if the number of such customers present in the system hits N ($$\le L$$) or the vacation timer (clock) expires, whichever occurs first, the server is switched on to normal mode. In model II, switching the server to normal mode from vacation mode occurs as soon as the accumulated number (those served out plus those present in the system) of type I customers during that working vacation hits N or the vacation timer expires, whichever occurs first. Type I customers arrive according to a Poisson process whereas type II customer’s arrival is governed by Markovian Arrival Process. Service time of type I and type II customers follow distinct phase type distributions. At a service completion epoch, finding the system empty, server takes an exponentially distributed working vacation. During working vacation, type I customers are served at a reduced rate. On vacation expiration, the service of the type I customer already in service, will start from the beginning in the normal mode of service. We analyze these models in steady state to compute the distribution of duration of service time continuously in slow mode, expected number of returns to 0 type I customer state, starting from 0 type I customer state during vacation mode of service before the arrival of a type II customer, the distribution of a p-cycle in normal mode, LSTs of busy cycle, busy period of type I customers generated during the service time of a type II customer and LSTs of waiting time distributions of type I and type II customers. We compare these models in steady state by numerical experiments to identify the superior model.

In this paper, we consider two single server queueing systems to which customers of two distinct priorities (P1 and P2) arrive according to a Marked Markovian arrival process (MMAP). They are served according to two distinct phase type distributions. The probability of a P1 customer to feedback is θ on completion of his service. The feedback (P1) customers, as well as P2 customers, join the low priority queue. Low priority (P2) customers are taken for service from the head of the line whenever the P1 queue is found to be empty at the service completion epoch. We assume a finite waiting space for P1 customers and infinite waiting space for P2 customers. Two models are discussed in this paper. In model I, we assume that the service of P2 customers is according to a non-preemptive service discipline and in model II, the P2 customers service follow a preemptive policy. No feedback is permitted to customers in the P2 line. In the steady state these two models are compared through numerical experiments which reveal their respective performance characteristics.

This paper approximates the Markovian model to study the router's loss behaviour employing the PBS mechanism under self-similar variable length input traffic by considering voids using the queueing system . As we know that the Broadband integrated digital service network (B-ISDN) is expected to support various kinds of services such as voice, data, video, and possible combinations of these. Because of this integration and demand, there may be congestion problem in networking. Congestion problem in the network can be dealt with some priority handling queueing mechanisms. One of such mechanisms is buffer access control (B.A.C.), also called space priority. There are strategies by which one can implement this space priority mechanism. One of such strategies is the partial buffer sharing (PBS) scheme. A limit (or threshold) is imposed on both low and high priority packets in this scheme. All arriving packets share the part of Buffer on or below the threshold. When the buffer occupancy is above the threshold, the queueing system's arriving low priority packets will be rejected. The high priority packets are lost only when the Buffer is full. Determination of an appropriate threshold is the significant design issue for a space priority queueing system. If the threshold is relatively high, then high priority packets will be lost more than expectedly. If the threshold is relatively low, low priority packets will be lost excessively. Either way, qualities of service (QoS) requirements are not guaranteed. Hence the threshold setting is a trade-off between the queue utilization and the guaranteed QoS. On the other hand, when the packet length is variable, voids will occur in the router buffer, and the performance of the router degrades as voids will incur excess loads. We assume that voids length follows uniform distribution and packet length follows an exponential distribution. Here, in this paper, the input traffic is self-similar and modelled as the Markovian arrival process (M.A.P.). Suppose the packet lengths follow an exponential distribution, and voids follow a uniform distribution. In that case, the sum of them need not be exponential and presents difficulties in the computation of performance measures. Hence, we assume that sum of packet length distribution and void length distribution are exponential, but with modified parameters that involve both the parameters of exponential distribution and uniform distribution. We compute the performance measures such as packet loss probability against the threshold, buffer capacity, traffic intensity, and optimal threshold using matrix analytic methods. One could utilize the analysis of mean lengths of the critical and non-critical period to initialize the related call admission control schemes in the router to improve performance further.

Despite that cloud virtual reality (VR) is the most promising service in 5G networks, a reasonable traffic model for it is still unknown. Based on statistics of real cloud VR traces, we justify that the Markovian arrival process (MAP) can well characterize the inter-arrival times (IATs) among packets. Moreover, we discuss possible methods to efficiently estimate parameters for flow aggregation. Since MAPs are analytically tractable, we quantify the performance of delivering cloud VR traffic from a queueing theory perspective. Aiming at supporting quantile metrics, we provide distributions of queue-length and latency for an arbitrary packet. The accuracy of estimated latency is validated by comparing with measured latency on an industrial 5G platform. The MAP-based traffic model will potentially serve as an input for performance evaluation and network planning for assuring high requirements of user experience.

We analyse the evolution of a system designed for reservation of some items in advance (for example, seats in aircrafts or trains or bus) by customers arriving at random moments. The reservation has to be done by the server in one of the K time frames. At the beginning of the pth time frame, the inventoried items in it (as well as those sold from it earlier) have life time distribution which is a p-fold convolution of a phase-type distribution with itself, for $$1 \le p \le K.$$ Cancellation of reserved items is possible before the expiry of their life. Distributions characterizing the service and inter-cancellation times are assumed to be independent exponential random variables and the customer arrivals are according to a Markovian arrival process. The number of items for reservation, available at the beginning of each time frame, is finite. If, at the commencement of service of a customer, the item in the required time frame is not available, the reservation may still be possible, through overbooking. Overbooking up to a maximum fixed level is permitted for each time frame. If, for the required day, the overbooked item is available, the customer is served the same. If this too is not available, he is asked to give alternatives. If none of his alternatives can be met, he is provided with a reservation for the time frame (day) for which one is available. If that too is not available, then he will have to wait until the expiry of one time frame; in the last case all remaining customers will have to wait. On expiry of one phase distribution, the time frames are renumbered and a new time frame with a K-fold convolution of the phase-type distribution is added $$(0 \leftarrow 1 \leftarrow 2 \leftarrow \cdots \leftarrow K-1 \leftarrow K \leftarrow K+1).$$ All overbooked customers present in the recently expired time frame are provided with a reservation in the newly added time frame (which has, at that epoch, a life time of a K-fold convolution of the phase-type distribution). This system is analysed and illustrated through numerical experiments. The special case of Poisson arrival, coupled with blocking of arrivals when all time frames $$1, 2, \ldots , K$$ are overbooked, is shown to yield a product form solution. For this case, an appropriate cost function is constructed and its properties investigated numerically.

A semi-open queueing network is considered. The network of an arbitrary topology consists of a finite number of nodes operation of which is modeled by single-server queueing systems with a buffer and an exponential service time distribution. Customers arrive at the network according to a Markovian arrival process. The total number of customers, which can be processed simultaneously, is restricted by a fixed in advance threshold. If the number of customers in the network at a new customer arrival moment is less than the threshold, this customer is admitted for service. Otherwise, the customer temporarily leaves the system (it is said that the customer joins the orbit) and retries to get access to the network after the random time intervals duration of which has an exponential distribution. The capacity of the orbit is infinite. After the admission to the network, the customer starts sequential service in a random number of nodes. The choice of the first and the subsequent nodes for service is made stochastically according to a fixed stochastic vector and a transition probability matrix. The behavior of the network is described by the continuous-time Markov chain that belongs to the class of asymptotically quasi-Toeplitz Markov chains. This allows to derive a transparent condition for the ergodicity of the chain and compute its steady-state distribution. Expressions for computation of various performance measures of the network are derived. Numerical results are presented. The model can be applied, e.g., for analysis and optimization of the operation of logistics and manufacturing systems, and the wireless telecommunication networks.

This paper analyzes the finite-buffer single server queue with vacation(s). It is assumed that the arrivals follow a batch Markovian arrival process (BMAP) and the server serves customers according to a non-exhaustive type gated-limited service discipline. It has been also considered that the service and vacation distributions possess rational Laplace-Stieltjes transformation (LST) as these types of distributions may approximate many other distributions appeared in queueing literature. Among several batch acceptance/rejection strategies, the partial batch acceptance strategy is discussed in this paper. The service limit L (1 ≤ L ≤ N) is considered to be fixed, where N is the buffer-capacity excluding the one in service. It is assumed that in each busy period the server continues to serve until either L customers out of those that were waiting at the start of the busy period are served or the queue empties, whichever occurs first. The queue-length distribution at vacation termination/service completion epochs is determined by solving a set of linear simultaneous equations. The successive substitution method is used in the steady-state equations embedded at vacation termination/service completion epochs. The distribution of the queue-length at an arbitrary epoch has been obtained using the supplementary variable technique. The queue-length distributions at pre-arrival and post-departure epoch are also obtained. The results of the corresponding infinite-buffer queueing model have been analyzed briefly and matched with the previous model. Net profit function per unit of time is derived and an optimal service limit and buffer-capacity are obtained from a maximal expected profit. Some numerical results are presented in tabular and graphical forms.

We consider a queueing-inventory problem with Markovian arrival process, phase type distributed service time. The life time of items is exponentially distributed; all items perish together which means they have a common life time. Reservation (purchase) and cancellation of purchased items is permitted as long as the common life time is not realized. In addition overbooking of items upto a certain maximum is also permitted. When system is fully overbooked waiting customers tend to leave the system. On realization of common life time, instantly S items are procured resulting in the commencement of next cycle. In the particular case of Poisson process and exponentially distributed service time we show that the system admits asymptotic product form solution. System state characteristics are computed which are then numerically illustrated for different sets of values for the input parameters.

We consider a single-server queueing system with server vacations as the important component of the polling queueing model of a real-world system. Period of continuous operation of the server (the maximum server attendance time) is restricted, but the service of a customer cannot be interrupted when this period expires. Such features are inherent for many real-world systems with resource sharing. We assume that the customers arrival is described by the Markovian Arrival Process and service, vacation and maximum server attendance times have a phase-type distribution. We derive the stationary distributions of the system states and waiting time. Taking in mind the necessity of further application of the results to modeling the polling queueing systems, the distribution of the server visiting time is derived. Extensive numerical results are presented. They highlight that an account of the coefficient of variation of vacation and maximum attendance time is very important for exact evaluation of the key performance measures of the system, while only the results for the coefficient of variation equal to zero or one are known in the literature. Impact of the possible customers impatience, which is intuitively important because the time-limited service is considered, is confirmed by the results of the numerical experiments. Optimization problem of matching the durations of vacation and maximum attendance time is considered.

A simple bound in GI/G/1 queues was obtained by Kingman using a discrete martingale transform. We extend this technique to 1) multiclass Σ\textrmGI/G/1 $ queues and 2) Markov Additive Processes (MAPs) whose background processes can be time-inhomogeneous or have an uncountable state-space. Both extensions are facilitated by a necessary and sufficient ordinary differential equation (ODE) condition for MAPs to admit continuous martingale transforms. Simulations show that the bounds on waiting time distributions are almost exact in heavy-traffic, including the cases of 1) heterogeneous input, e.g., mixing Weibull and Erlang-k classes and 2) Generalized Markovian Arrival Processes, a new class extending the Batch Markovian Arrival Processes to continuous batch sizes.

Combining the study of queuing with inventory is very common and such systems are referred to as queuing-inventory systems in the literature. These systems occur naturally in practice and have been studied extensively in the literature. The inventory systems considered in the literature generally include (s,S)-type. However, in this paper we look at opportunistic-type inventory replenishment in which there is an independent point process that is used to model events that are called opportunistic for replenishing inventory. When an opportunity (to replenish) occurs, a probabilistic rule that depends on the inventory level is used to determine whether to avail it or not. Assuming that the customers arrive according to a Markovian arrival process, the demands for inventory occur in batches of varying size, the demands require random service times that are modeled using a continuous-time phase-type distribution, and the point process for the opportunistic replenishment is a Poisson process, we apply matrix-analytic methods to study two of such models. In one of the models, the customers are lost when at arrivals there is no inventory and in the other model, the customers can enter into the system even if the inventory is zero but the server has to be busy at that moment. However, the customers are lost at arrivals when the server is idle with zero inventory or at service completion epochs that leave the inventory to be zero. Illustrative numerical examples are presented, and some possible future work is highlighted.

The unpredictable variability of Data Stream Processing (DSP) application workloads calls for advanced mechanisms and policies for elastically scaling the processing capacity of DSP operators. Whilst many different approaches have been used to devise policies, most of the solutions have focused on data arrival rate and operator resource utilization as key metrics for auto-scaling. We here show that, under burstiness in the data flows, overly simple characterizations of the input stream can yet lead to very inaccurate performance estimations that affect such policies, resulting in sub-optimal resource allocation.We then present MEAD, a vertical auto-scaling solution that relies on online state-based representation of burstiness to drive resource allocation. We use in particular Markovian Arrival Processes (MAPs), which are composable with analytical queueing models, allowing us to efficiently predict performance at run-time under burstiness. We integrate MEAD in Apache Flink, and evaluate its benefits over simpler yet popular auto-scaling solutions, using both synthetic and real-world workloads. Differently from existing approaches, MEAD satisfies response time requirements under burstiness, while saving up to 50% CPU resources with respect to a static allocation.

In most of the service systems considered so far in queuing theory, no fresh customer is admitted to a batch undergoing service when the number in the batch is less than a threshold. However, a few researchers considered the case of customers accessing ongoing service batch, irrespective of how long service was provided to that batch. A queuing system with a different kind of accessibility that relates to a real situation is studied in the paper. Consider a single server queuing system in which the service process comprises of k stages. Customers can enter the system for service from a node at the beginning of any of these stages (provided the pre-determined maximum service batch size is not reached) but cannot leave the system after completion of service in any of the intermediate stages. The customer arrivals to the first node occur according to a Markovian Arrival Process (MAP). An infinite waiting room is provided at this node. At all other nodes, with finite waiting rooms (waiting capacity cj,2≤j≤k), customer arrivals occur according to distinct Poisson processes with rates λj,2≤j≤k. The service is provided according to a general bulk service rule, i.e., the service process is initiated only if at least a customers are present in the queue at node 1 and the maximum service batch size is b. Customers can join for service from any of the subsequent nodes, provided the number undergoing service is less than b. The service time distribution in each phase is exponential with service rate μjm, which depends on the service stage j,1≤j≤k, and the size of the batch m,a≤m≤b. The behavior of the system in steady-state is analyzed and some important system characteristics are derived. A numerical example is presented to illustrate the applicability of the results obtained.

We consider a single server queueing inventory model. The customers arrive according to Markovian arrival Process (MAP). The service is assumed to follow Phase type(PH) distribution. An inventory of commodities is attached to the service station. The common life time (CLT) for inventoried items is assumed to follow Phase type(PH) distribution. The inventoried items perish all together. In this case, the supply of items is immediately in local purchase to bring the inventory level to maximum inventory level S. The inventory is not allowed to go down to zero because of local purchase. Each service requires a unit of commodity for service. This unit is instantaneously taken at the beginning of the service. The replenishment of inventory follows (s, S) policy with lead time positive. The lead time follows exponential distribution. In the case of local purchase, the outstanding order of the normal purchase (wait until replenishment) is cancelled. Service of a customer begins only when the server is free. Otherwise, the arriving customer joins the buffer. Steady state analysis of the queueing inventory model is performed. Some performance measures are computed under steady state. A numerical example is presented.

Building performance models for microservices applications in DevOps is costly and error-prone. Accurate service demand distribution estimation is critical to performance model parameterization. However, traditional service demand estimation methods focus on capturing the mean service demand, disregarding higher-order moments of the distribution. To address this limitation, we propose to estimate higher moments of the service demand distribution for a microservice from monitoring traces. We first generate a closed queueing model to abstract a microservice and model the departure process at the queue node as a Markovian arrival process. This allows formulating the estimation of service demand as an optimization problem, which aims to find the optimal parameters of the first multiple moments of the service demand distribution based on the inter-departure times. We then estimate the service demand distribution with a novel maximum likelihood algorithm, and heuristics to mitigate the computational cost of the optimization process for scalability. We apply our method to real traces from a microservice-based application and demonstrate that its estimations lead to greater prediction accuracy than exponential distributions assumed in traditional service demand estimation approaches.

We consider the sleep mode with multimedia applications in WiMAX 2 networks, where the real-time traffic includes the real-time and the Best Effort (BE) traffic mixed. In this chapter, we build a queueing model with multiple heterogeneous vacations to capture the system probability behavior in the networks with multimedia applications. Taking into account the correlation of the real-time traffic, we assume the arrival process to be a Discrete Time Markovian Arrival Process (D-MAP), and analyze the queueing model by using the method of an embedded Markov chain. Then, we give the steady-state distribution for the number of data packets. Accordingly, we derive performance measures of the system in terms of the average response time of data packets, the energy saving rate of the system, and the standard deviation for the number of data packets. We also construct a system cost function to determine the optimal length of the sleep cycle in order to maximize the energy saving rate of the system while satisfying the Quality of Service (QoS) constraint on the average response time of data packets. Finally, we present numerical results to investigate the influence of the system parameters on the system performance.

In this paper, we analyze a multi-server queueing system with heterogeneous customers that arrive according to a marked Markovian arrival process. Customers of two types differ in priorities and parameters of phase type distribution of their service time. The queue under consideration can be used to model the processes of information transmission in telecommunication networks in which often the flow of information is the superposition of several types of flows with correlation of inter-arrival times within each flow and cross-correlation. We define the process of information transmission as the multi-dimensional Markov chain, derive the generator of this chain and compute its stationary distribution. Expressions for computation of various performance measures of the system, including the probabilities of loss of customers of different types, are presented. Output flow from the system is characterized. The presented numerical results confirm the high importance of account of correlation in the arrival process. The values of important performance measures for the systems with the correlated arrival process are essentially different from the corresponding values for the systems with the stationary Poisson arrival process. Measurements in many real world systems show poor approximation of real flows by such an arrival process. However, this process is still popular among the telecommunication engineers due to the evident existing gap between the needs of adequately modeling the real life systems and the current state of the theory of algorithmic methods of queueing theory.

Broadband integrated service digital network (B-ISDN) is expected to support various kinds of services such as voice, data, video, and possible combinations of these. Because of this integration and demand there may be congestion problem in networking. Congestion problem in network can be dealt with some priority handling queueing mechanisms. One of such mechanisms is buffer access control (BAC) also called space priority. There are strategies by which one can implement this space priority mechanism, one of such strategies is partial buffer sharing (PBS) scheme. In this scheme, a limit (or threshold) is imposed on both low and high priority packets. The part of buffer on or below the threshold is shared by all arriving packets. When the buffer occupancy is above the threshold, the arriving low priority packets will be rejected by queueing system. The high priority packets are lost only when the buffer is full. Determination of an appropriate threshold is the significant design issue for a space priority queueing system. If the threshold is relatively high, then high priority packets will be lost more than expectedly. If the threshold is relatively low, low priority packets will be lost excessively. Either way, qualities of service (QoS) requirements are not guaranteed. Hence the threshold setting is a trade-off between the queue utilization and the guaranteed QoS. On the other hand, when the packet length is variable, voids will occur in the router buffer and performance of router degrades as voids will incur excess loads. We assume that voids length follows uniform distribution and packet length follows exponential distribution. In this paper, loss behavior of the router employing PBS mechanism under Markovian modeled self-similar variable length input traffic by taking voids into consideration is investigated using queueing system. Here the input traffic is self-similar in nature and modeled as Markovian arrival process (MAP). If the packet lengths follow exponential distribution, and voids follow uniform distribution, then sum of them need not be exponential and presents difficulties in the computation of performance measures. Hence, we assume that sum of packet length distribution and void length distribution is exponential, but with modified parameter which involves both the parameters of exponential distribution and uniform distribution. We compute the performance measures such as packet loss probability against threshold, buffer capacity and traffic intensity and optimal threshold using matrix analytic methods.

This paper deals with the finite-buffer single server vacation queues with batch Markovian arrival process (BMAP). The server follows gated-limited service discipline, i.e., the server can serve a maximum of L customers out of those that are waiting at the start of the busy period or all the waiting customers, whichever is minimum. It has been assumed that the server can take only one vacation, i.e., if no customers are found at the end of a vacation, the server remains idle until a batch of customers arrives. The service time and vacation time distributions are considered to possess rational Laplace–Stieltjes transform. The queue-length distribution at post-departure, arbitrary, and pre-arrival epochs has been obtained. Various performance measures like mean queue-length, mean waiting time of an arbitrary customer, and mean length of busy and idle periods have been derived for this model. Numerical results have been presented based on the analysis done.

This paper presents a study of applying open queueing networks with MAP∕PH∕1∕N nodes for estimation of performance characteristics of wireless networks with linear topology using either relay, or DCF channels. Basic properties of such queueing networks are outlined along with Markovian arrival processes (MAPs) and phase-type (PH) distributions fitting methods. Due to exponential growth of the system state space in MAP∕PH∕1∕N →⋯ →•∕PH∕1∕N queueing networks, the exact calculation of its characteristics is practically impossible for an arbitrary large number of nodes, and we propose an algorithm which finds approximated results by iterative estimations of node parameters using departure processes approximations with MAPs of smaller order. We use this approach to get numerical results, which are further compared with the data obtained by Monte-Carlo method. The comparison shows that the results obtained by both methods are very close to each other, while the iterative approach requires significantly less time. The paper provides results of fitting transmission delays using PH distributions and end-to-end delays estimations for wireless networks with simple relay and IEEE 802.11 DCF channels. All numerical results are validated using a simulation model.

This article gives closed-form analytic expressions as well as a computational analysis of the stationary system-length distribution for the renewal-input, bulk-arrival, and multi-server continuous-time queueing model. The service times are equal to the constant D for any customer. The queueing model may be denoted as G I X / D / c queue. Using the steady-state equations, the system-length probability generating function is derived. Subsequently, by inverting this probability generating function the stationary system-length distribution is obtained using the roots of a characteristic equation. Next, a similar analysis for the corresponding multi-server queueing model with batch Markovian arrival process ( B M A P ) is carried out using the roots of a characteristic equation associated with the vector generating function of the system-length distribution. The distribution function of the stationary actual waiting-time for the first customer of an arrival batch in a B M A P / D / c queue is also derived. Some numerical implementation of the procedure for the G I X / D / c and B M A P / D / c queues is performed. Numerical values for the expected system length and waiting time are also obtained.

We study the \begin{document}$ MAP/M/s+G $\end{document} queueing model that arises in various multi-server engineering problems including telephone call centers, under the assumption of MAP (Markovian Arrival Process) arrivals, exponentially distributed service times, infinite waiting room, and generally distributed patience times. Using sample-path arguments, we propose to obtain the steady-state distribution of the virtual waiting time and subsequently the other relevant performance metrics of interest via the steady-state solution of a certain Continuous Feedback Fluid Queue (CFFQ). The proposed method is exact when the patience time is a discrete random variable and is asymptotically exact when it is continuous/hybrid, for which case discretization of the patience time distribution is required giving rise to a computational complexity depending linearly on the number of discretization levels. Additionally, a novel method is proposed to accurately obtain the first passage time distributions for the virtual and actual waiting times again using CFFQs while approximating the deterministic time horizons by Erlang distributions or more efficient Concentrated Matrix Exponential (CME) distributions. Numerical results are presented to validate the effectiveness of the proposed numerical method.

Markovian arrival process (MAP) is a popular tool for modeling arrival processes of stochastic systems such as queueing systems, reliability systems and telecommunications networks. In this paper we show how properties of Markovian Arrival Processes can be derived from the general theory of Markov processes with a homogeneous second component. We also present a series of results on queueing systems with MAP arrivals which were published in RUDN University before 1990.

A popular model of correlated arrival processes is the Batch Markovian Arrival Process. In this chapter, we define this process and consider its basic properties, particular cases and some its generalizations. Analysis of performance characteristics of queuing systems with this arrival process requires consideration of multidimensional (at least two-dimensional) Markov processes. Therefore, for the use in the following chapters here we briefly present the known in the literature results for multidimensional Markov chains with several kinds of special structure of the generator or transition probability matrix. Some of these results were originally obtained in the papers of authors of this book.

We develop an analytical framework for queueing and delay analysis in the case of a number of distinct flows arriving at a network node, where asynchronous partial network coding is applied for an efficient packet transmission. In order to perfectly model and analyze the practical communication networks, the arriving flows are assumed to be general Markovian arrival processes. As a key example, we apply the proposed model to the problem of coded caching in single bottleneck caching networks. In addition, we verify the accuracy of the proposed model through simulations and real trace-driven experiments.

In this paper, a novel queueing analytical framework is proposed to evaluate the performance of IEEE 802.15.6-based carrier-sense multiple access with collision avoidance (CSMA/CA) scheduling in wireless body area networks with joint consideration of instantaneous delay constraints and body shadowing effects. Specifically, we develop an absorbing Markov chain to model the medium access process with error controls that is defined by the IEEE standard and design a random time-limited single vacation to describe the potential body shadowing interruption process. To guarantee the timeliness of received packets and avoid energy waste for transmitting valueless packets, an instantaneous delay constraint is carefully considered, which is then characterized by an overdeadline packet dropping process with a predefined waiting deadline. In our analysis, a Markovian arrival process is also adopted to capture the correlation of arrival traffic, and all other random processes are modeled by phase-type distributions, which make our framework more general and comprehensive. To address the inherent complexity of the original model, based on the transient queueing analysis, we develop a buffer-overflowing queueing principle to approximate the overdeadline packet dropping principle by solving a buffer length optimization problem. After that, we construct a multidimensional discrete-time Markov chain to analyze the stationary distribution through the matrix-geometric method. Performance measures, including the average delay, waiting time distribution, and packet transmission failure probability, are derived. The accuracy of our proposed analytical framework is validated by extensive simulations.

We consider a novel multi-server queueing system that is potentially useful for optimizing real-world systems, in which the objectives of high performance and low power consumption are conflicting. The queueing model is formulated and investigated under the assumption that an arrival flow is defined by a batch Markovian arrival process and random values characterizing customer processing have the phase-type distribution. If the service time of some customer by a server exceeds a certain random bound, this server receives help from a so-called backup server from a finite pool of backup servers. The behavior of the system is described by a quite complicated multi-dimensional continuous-time Markov chain that is successfully analyzed in this paper. Examples of the potential use of the obtained results in managerial decisions are presented.

A semi-open queueing network having a finite number of nodes is considered. The nodes are modeled by single-server queueing systems with a finite buffer and an exponential service time distribution. Customers arrive to the network according to a Markovian arrival process. The number of customers, which can be processed in the network simultaneously, is restricted by a threshold. If the number of customers in the network is less than this threshold, when a new customer arrives, the customer is processed in the network. Choice of the first and the subsequent nodes for service is performed randomly according to a fixed stochastic vector and a transition probability matrix. If the number of customers in the network at the customer arrival epoch is equal to the threshold, the customer is queued into an input buffer with an infinite capacity. Customers in the input buffer are impatient. The stationary behavior of network states is analyzed. The Laplace–Stieltjes transform of the distribution of the customer’s waiting time in the input buffer is obtained. Expressions for computing performance measures of the network are derived. Numerical results are presented. The model is suitable, e.g., for analysis and optimization of wireless telecommunication networks and manufacturing systems with a finite number of machines and workers.

The batch Markov-modulated Poisson process (BMMPP) is a subclass of the versatile batch Markovian arrival process (BMAP), which has been widely used for the modeling of dependent and correlated simultaneous events (as arrivals, failures, or risk events). Both theoretical and applied aspects are examined in this paper. On one hand, the identifiability of the stationary BMMPP m (K) is proven, where K is the maximum batch size and m is the number of states of the underlying Markov chain. This is a powerful result for inferential issues. On the other hand, some novelties related to the correlation and autocorrelation structures are provided.

Cloud computing is continuing to prove its flexibility and versatility in helping industries and businesses as well as academia as a way of providing needed computing capacity. As an important alternative to cloud computing, desktop grids allow to utilize the idle computer resources of an enterprise/community by means of distributed computing system, providing a more secure and controllable environment with lower operational expenses. Further, both cloud computing and desktop grids are meant to optimize limited resources and at the same time to decrease the expected latency for users. The crucial parameter for optimization both in cloud computing and in desktop grids is the level of redundancy (replication) for service requests/workunits. In this paper we study the optimal replication policies by considering three variations of Fork-Join systems in the context of a multi-server queueing system with a versatile point process for the arrivals. For services we consider phase type distributions as well as shifted exponential and Weibull. We use both analytical and simulation approach in our analysis and report some interesting qualitative results.

The joint arrival process of multiple independent batch Markovian arrival processes (BMAP) is analyzed. First, the parameter matrices of the joint arrival process are constructed, and their relations with the parameter matrices of the component BMAPs are also obtained. Second, it is proved that the parameter matrices of the joint arrival process have the same properties as the BMAP; and based on these properties, in analyzing the queueing models, some relations for the joint arrival process either can inherit from the existing literature on the BMAP and the multiple-BMAP, or can be derived with the same complexity as the case for the BMAP.

Unreliability of components is the inherent feature of many real world systems and its account is vital for correct prediction of performance measures of the system. Multi-server queueing model considered in this paper allows to evaluate characteristics of the systems under much more general assumptions about the probabilistic distributions describing behavior of the system than models known in existing literature. We analyse the multi-server queue with infinite buffer and the Batch Markovian Arrival Process (BMAP) of customers. The servers are identical and independent of each other. Service time of a customer has phase-type (PH) distribution. Servers are subject to breakdowns and repairs. Breakdowns occurrence moments are defined by the Markovian Arrival Process (MAP). The breakdown causes a failure of any server, which is not under repair. When a server fails the repair period starts immediately. The duration of this period has PH distribution. A customer whose service is interrupted occupies an idle server, if any, and continues his/her service. If he/she does not see an idle server, the customer goes to the buffer with some probability and permanently leaves the system with the complementary probability. We derive the constructive ergodicity condition and calculate the stationary distribution and the main performance characteristics of the system. Illustrative numerical examples are presented.

This article discusses the queueing-inventory model with a cancellation policy and two classes of customers. The two classes of customers are named ordinary and impulse customers. A customer who does not plan to buy the product when entering the system is called an impulse customer. Suppose the customer enters into the system to buy the product with a plan is called ordinary customer. The system consists of a pool of finite waiting areas of size N and maximum S items in the inventory. The ordinary customer can move to the pooled place if they find that the inventory is empty under the Bernoulli schedule. In such a situation, impulse customers are not allowed to enter into the pooled place. Additionally, the pooled customers buy the product whenever they find positive inventory. If the inventory level falls to s, the replenishment of Q items is to be replaced immediately under the (s, Q) ordering principle. Both arrival streams occur according to the independent Markovian arrival process (MAP), and lead time follows an exponential distribution. In addition, the system allows the cancellation of the purchased item only when there exist fewer than S items in the inventory. Here, the time between two successive cancellations of the purchased item is assumed to be exponentially distributed. The Gaver algorithm is used to obtain the stationary probability vector of the system in the steady-state. Further, the necessary numerical interpretations are investigated to enhance the proposed model.

We give a brief survey of literature devoted to studying queueing systems with Markovian and batch Markovian arrival processes and their application to modeling telecommunication networks.

A queueing model with catastrophes and delayed action is studied in this paper. This delayed action could be in the form of protecting or removing all the customers that are in the system based on the outcome of two random clocks which are simultaneously activated upon the occurrence of a catastrophic event. Assuming the customers to arrive according to a versatile Markovian point process to a single server system, the service times to be of phase type, and all other underlying random variables to be exponentially distributed, we use matrix-analytic methods to study the delayed catastrophic model in steady-state. Needed expressions for the number in the system as well as the waiting time distributions are derived along with a discussion on some special cases of this model. Detailed illustrative examples are presented.

In this paper, we prove strong approximations for the (MAPt/Pht/)N queueing network. These strong approximations allow us to derive fluid and diffusion limits for the queue length processes of the network. This extends recent work that provides fluid and diffusion limits in the single station setting.

This paper deals with the analysis of the BMAP/MSP/1 generalized processor-sharing queue. The analysis is based on RG-factorization technique applied to the Markov chain of the associated quasi-birth and death process. The stationary system-length distribution of the number of customers in the system and the LaplaceStieltjes transform (LST) of the sojourn time distribution of a tagged customer in the system is obtained in this paper. The mean sojourn time of a tagged customer is derived using the previous LST. The corresponding finite-buffer queueing model is also analyzed and system-length distribution is derived using the same technique as stated above. Further, the blocking probabilities for customers with different positions, such as the first-, an arbitrary- and the last-customer of a batch are obtained. The detail computational procedure for these models is discussed. Various numerical results are presented to show the applicability of the results obtained in the study. HighlightsAn infinite-buffer single server queue with batch Markovian arrival is considered.The service process is non-renewal as well under generalized processor sharing.Stationary system-length distribution is obtained using RG-factorization approach.The mean sojourn time of a tagged customer is analyzed in detail.Performance indices and blocking probability for finite-buffer are also obtained.

In this paper, we consider a queue where the inter-arrival times are correlated and, additionally, service times are also correlated with inter-arrival times. We show that the resulting model can be interpreted as an MMAP[K]/PH[K]/1 queue for which matrix geometric solution algorithms are available. The major result of this paper is the presentation of approaches to fit the parameters of the model, namely the MMAP, the PH distribution and the parameters introducing correlation between inter-arrival and service times, according to some trace of inter-arrival and corresponding service times. Two different algorithms are presented. The first algorithm is based on available methods to compute a MAP from the inter-arrival times and a PH distribution from the service times. Afterward, the correlation between inter-arrival and service times is integrated by solving a quadratic programming problem over some joint moments. The second algorithm is of the expectation maximization type and computes all parameters of the MAP and the PH distribution in an iterative way. It is shown that both algorithms yield sufficiently accurate results with an acceptable effort.

Given only the traffic correlations of counts and intervals, a Batch Renewal Arrival Process (BRAP) is completely determined, as the least biased choice and thus, it provides the analytic means to construct suitable traffic models for the study of queueing systems independently of any other traffic characteristics. In this context, the BRAP and the Batch Markovian Arrival Process (BMAP) are employed in the continuous time domain towards the analysis of the stable BRAP/GE/1 and BMAP/GE/1 queues with infinite capacity, single servers and generalized exponential (GE) service times. Novel closed form expressions for the steady state probabilities of these queues are obtained, based on the embedded Markov chains (EMCs) technique and the matrix-geometric (M-G) method, respectively. Moreover, the stable GE sGGeo /GE/1 queue with GE-type service times and a GE sGGeo BRAP consisting of bursty GE-type batch interarrival times and a shifted generalized geometric (sGGeo) batch size distribution is adopted to assess analytically the combined adverse effects of varying degrees of correlation of intervals between individual arrivals and the burstiness of service times upon the typical quality of service (QoS) measure of the mean queue length (MQL). Moreover, a comprehensive experimental study is carried out to investigate numerically the relative impact of count and interval traffic correlations as well as other traffic characteristics upon the performance of stable BRAP/GE/1 and BMAP/GE/1 queues. It is suggested via a conjecture that the BRAP/GE/1 queue is likely to yield pessimistic performance metrics in comparison to those of the stable BMAP/GE/1 queues under the worst case scenario (i.e., a worst case scenario) of the same positive count and interval traffic correlations arising from long sojourn in each phase. HighlightsConstruction of a unique continuous-time BRAP from count and interval correlations.Analysis of the stable BRAP/GE/1 and BMAP/GE/1 queues via the EMCs and M-G techniques.Investigation into the performance impact of traffic correlation on queues with BRAP.Conjecture on BRAP pessimistic queue metrics over those of BMAP with same correlations.

We consider multi-server tandem queues where both stations have a finite buffer and all services times are phase-type distributed. Arriving customers enter the first queueing station if buffer space is available or get lost otherwise. After completing service in the first station customers proceed to the second station if buffer space is available, otherwise a server at the first station is blocked until buffer space becomes available at the second station. We provide an exact computational analysis of various steady-state performance measures such as loss and blocking probabilities, expectations and higher moments of numbers of customers in the queues and in the whole system by modeling the tandem queue as a level-dependent quasi-birth-and-death process and applying suitable matrix-analytic methods. Numerical results are presented for selected representative examples.