Finite Capacity Tandem Queueing Network with Reneging

Table of Contents:


In the current age of IoT, cloud computing, industry 4.0, etc., modern computer networks process heavy workloads with random service demands. Hence, computer networks face challenges such as traffic control, time delay, data loss, or the blocking of a new connection. For the predictive analysis, various performance measures, including throughput, loss probability, blocking and delay, can be easily evaluated by using the queueing theoretic approach. The queueing models deal with waiting line problems that are surprisingly prevalent in all spheres of real-life problems, since waiting lines are ubiquitous. Jobs arrive at a node (router) in the computer network, wherein jobs have to processed and forwarded by the node. A node processes one job at a time and places the remaining jobs in the waiting line (buffer) of finite capacity. Queueing network is also used to study the quality of service at various stages of the computer network.

The Markov process is widely used for the performance analysis of various queueing problems that arise in any service system, including a computer network. A Markov process consists of a set of states and a labeled transition between the states. A state of the Markov process represents distinct conditions of interest in the computer network, namely various types of waiting jobs, the number of failed services, and so on.

In the tandem queueing network, several service facilities in a network are connected in a series to provide the requested service to the job sequentially. In the tandem queue, blocking or starving is a common phenomenon, and buffer size is an important decision criterion for optimal services in the network. Reneging, an unpredictable impatience behavior, is a vital aspect of a tandem queueing network. In the reneging process, the job leaves the waiting queue without being served. For example, in service call centers, jobs may hang up before completing their task.

Queueing theory is a mathematical tool that is commonly applied in the design and development of computer networks. Queueing modeling has been used effectively for evaluating the performance measures of computer networks, and many researchers in the past enrich literature. Some important works on the queueing network have been done by Perros [1994], Bolch et al. [1998], Altman [2000], Balsamo et al. [2003], Bylina and Bylina [2005], etc. Filipowicz and Kwiecien [2008] discussed different queueing networks for the modeling of complex network systems and presented formula that can be used to improve the flow of data or packets, throughput, delay time, etc. A lot of literature and textbooks concerning the queueing theory are available [Gross and Harris, 2008]. Petrovic et al. [2008] presented an application of the Markov theory to study the model of netw'orked transport system in the view of determining the system performance. Jain et al. [2009] developed a single and batch service finite capacity queueing model for the communication system, and presented the transient analysis of the average queue length, expected idle period, and expected busy period. Cominetti and Guzman [2013] presented a multipath routing network model that combines the tw'o network models, i.e., NUM (Network Utility Maximization) and MTE (Markovian Traffic Equilibrium), and explored the congestion control and multipath routing. Shekhar and Jain [2013] dealt with a Markovian queueing system having multitask service counters that provide complete service in three stages in tandem with the state-dependent rate and having a finite queue in front of each counter. Czachorski [2015] focused on three types of approaches, namely Markov models, fluid flow approximation, and diffusion approximation, to analyze transient states in queueing models. Baumann and Sandmann [2017] proposed a finite buffer multiserver tandem queue system with distributed stage-type service time and discussed various performance measures. Quality of service (QoS) enhances the performance of computer networks through proper management of available resources. Delay is a significant measure of QoS. Guan et al. [2006] developed a queueing model with delay constraints and presented an algorithm on queue with the moveable threshold that controls the delay. Ahmad et al. [2009] presented a comprehensive analysis of various congestion control schemes focused on certain performance measures such as throughput, mean queue length, probability of packet loss and end-to-end delay. Ammar [2017] discussed a Markovian model with impatient jobs and evaluated the performance of the system. Wang and Zhang [2018] developed a queueing model with impatient clients within the multiserver queueing system along with the threshold structure and discussed the various performance measures. Wang et al. [2019] introduced a two-station tandem queueing system with reneging and abandonment and described numerous performance metrics of a tandem.

This chapter considers the Markovian model that provides three types of service requests with two nodes. Both nodes with finite buffer are modeled as single-server finite capacity queues, and jobs make independent reneging decisions while waiting in the second node. Our study is applicable in the architectural process involved in routers where multitype jobs like data, packets, voice, etc. require processing at node(s) in sequence. The purpose of this chapter is threefold. First, we develop a mathematical model for the real-time, nodes-jobs computing network in tandem architect. Second, we derive the steady-state solution for the given model and obtain the different performance measures of the computing network. Third, we construct a relationship between the costs to determine the optimal size of the buffer in the rendering of the service. Numerical simulations have also been made for the direct benefit to the decision makers. The chapter is structured in the following manner. In section 3.2, we present a detailed model description of the tandem queueing network and formulate governing Chapman-Kolmogorov differential-difference equation. In section 3.3, we define performance measures to validate our governing model. In section 3.4, we develop the cost function of the computing network for optimal analysis of decision parameters. The results of the numerical experiment have been tabulated and depicted in section 3.5. Conclusions are drawn in section 3.6 along with future scopes.


We consider a tandem queue network with two nodes: Node 1 and Node 2, which are arranged in series with a dedicated buffer of finite size. Each node is assumed as a single-server queueing system. Three types of service requests are processed within the tandem network. In type 1 service requests, jobs require the processing only at the first node and leave the network after first node service completion. In type 2 service requests, jobs require processing at both nodes in sequence. In type 3 service requests, jobs require only the second node’s service. Jobs may make independent reneging decisions while waiting in the buffer space for the second node. The architectural layout is depicted in Figure 3.1. For the mathematical modeling purpose, we consider the following assumptions and notations.

The tandem queue network with reneging

FIGURE 3.1 The tandem queue network with reneging.

At Node 1, jobs arrive at the computing network following a Poisson process with a rate A.,. On arrival, if the server of Node 1 is available idly, the job enters for service without waiting. Otherwise, the job waits in Node l’s queue in the buffer of size St. The server at Node 1 renders the service whose service time follows an exponential distribution with mean rate |i,. After a job's processing request is satisfied at Node 1, the job may enter in Node 2 with probability q if it requires Node 2 service, otherwise it leaves the computing network. Those jobs that require Node 2’s service only enter in Node 2 directly with exponentially distributed interarrival time with rate X2. The server at Node 2 provides the service to both types of jobs, considering that they are waiting in one queue in the buffer of size S2. The service time at Node 2 follows the exponential distribution with mean rate |i2- Jobs may make independent reneging decisions while waiting at Node 2. Job reneging follows the Poisson process with the mean rate y.

Using the concept of the Markov process, the state transition diagram is illustrated in Figure 3.2. Let {/(f);f >0) and {J(t)U >0} be the number of jobs in the

State transition diagram

FIGURE 3.2 State transition diagram.

queue of Node 1 and Node 2, respectively, at the time t. Then, [I(t),J(ty,t >0} is a continuous Markov process on the state space S = {(i,j)-,0l,0< j2}. Let PKJ(t) = Prob{I(t) = i,J(t) = у;T > 0} be the probability that there are i jobs in the queue at Node 1, у jobs at Node 2 at the time t.

For the steady-state analysis, we define P,j = lim Then, the set of forward

Chapman-Kolmogorov difference equations for the above model is as follows:

For the computational convenience, Eqs. (3.1-3.9) can be represented in the matrix form, as:

where X is the coefficient matrix of order 5, x S2, P is the probability vector of state probabilities and 0 is the null vector of size S, x S2. Using the normalizing condition of probability

where e denotes the unit row vector of order 5, x S2. Eq. (3.10) can be expressed as

where XR is derived from the matrix X simply by replacing the last row with a row

vector with all unit elements and Y = [0,0,0..........0,1 ]r is a column vector of order

Si x S2. Non-homogenous system of equations Eq. (3.12) has been solved by a numerical technique that is based on SOR (Successive-Over-Relaxation) method, which is an extrapolation to the Gauss-Seidel method by taking the relaxation parameter w = 1.25 (1 < w < 2) to improve the convergence rate [Jain et al. 2011].

< Prev   CONTENTS   Source   Next >