An Open Queueing Network with a Correlated Input Arrival Process for Broadband Wireless Network Performance Evaluation

Abstract

In the paper characteristics of an open queueing network with correlated input Markovian arrival processes and phase type distribution of service time in the nodes are studied. The developed methodology is used for the performance evaluation of broadband wireless networks with linear topology. A comparison study of numeric results of analytic modelling and simulation is carried out. To study open queueing networks with MAP input a pyQuMo library has been developed using Python 3 language. The library provides a means for model description, model properties computations by taking advantage of an analytical approach, and simulation as well as results visualisation.

1 Introduction

The designing of a backbone network is a topical task for the systems which are as follows: intellectual transport systems (ITS), road safety systems, pico- and femtocells access systems, as well as for the development of telecommunications infrastructure along railways and pipelines. For the performance evaluation and optimal design of networks of this rank there is a need for new mathematical models describing the functionality of wireless networks. In this paper we propose a model of open homogeneous queueing networks with a correlated input arrival process (MAP), PH-distribution of service time in the network nodes and a routing matrix $\Vert t_{ij} \Vert$, where $t_{ij}$ is the probability of packet arrival at the j-th node after its serving at the i-th node is completed.

The state space and transmission intensities of the Markovian process are described. The results of numerical computation of the queues length, packet loss probabilities and other network parameters are presented. Such results are achieved by making use of a precise analytical approach as well as simulation modelling.

2 The Model of an Open Homogeneous Network with Correlated Input Arrivals and PH-Distribution of Service Time

It is not enough to make use of traditional approaches, which are based on the models of BCMP-networks [1, 2] being used extensively for the performance evaluation and optimization of computer networks characteristics, and for taking into account a number of significant features of functioning of wireless network considered. Such features are as follows:

• correlated nature of input arrival process of packets;

• limited buffer memory of base stations and respective packet loss;

• the ability to transmit packets repeatedly when the packet losses occurred as a result of, for instance, interference or strong signal attenuation;

• the service and transmission time of packets being produced by different applications can vary significantly and have various distributions.

To take account of the correlated nature of the traffic let us consider MAP (Markovian Arrival Process) and BMAP (Batch MAP) to arrive into an open homogeneous queueing network [3, 4]. Let us denote MAP $A \sim MAP(D_{0},D_{1})$, where $D=D_{0}+D_{1}$ is an infinitesimal generator of an appropriate Markovian chain, i.e.

$$\begin{aligned} \forall i: \sum \limits _{j=1} d_{ij} = 0, \quad \forall i \ne j: d_{ij} \ge 0, \quad \forall i: d_{ii} \le 0. \end{aligned}$$

$D_{0}$ and $D_{1}$ are constrained matrices:

$$\begin{aligned} \forall i, j: \{D_{1}\}_{ij} \ge 0,\quad \forall i \ne j: \{D_{0}\}_{ij} \ge 0, \quad \forall i: \{D_{0}\}_{ii} \le 0. \end{aligned}$$

The aim of such partitioning is to divide invisible transitions leading only to a change of state and determined by matrix $D_{0}$ and visible ones determined by matrix $D_{1}$ that cause packet generation. In the case of BMAP a sequence of matrices $\{D_{i}:i \ge 1\}$ is set up instead of a single $D_{1}$ matrix. Each matrix from this sequence defines transition intensities resulting to packet generating. Applications of MAP and BMAP to telecommunication traffic modelling are well studied and available in the literature. It has been shown that one can simulate real traffic with sufficient precision using these arrivals [5, 6]. Batch MAP allows us to describe the simultaneous arrival of an arbitrary amount of packets while MAP does not. To simplify the formulas of the suggested model, MAP is made use of, but all this reasoning is also valid for BMAP.

To take into account the errors and losses arising during transitions let us associate the error probability $p_{e_{i}}$ with each station, thus a packet being served returns into the queue or leaves it irretrievably with that probability.

Service time can be modelled by PH-distribution [7]. Phase type distribution is made extensive use of and allows us to describe the service process as part of a Markovian model. Let us denote B PH-distributed random value, $B \sim PH(S, \mathbf {\tau }), S \in \mathbb {R}^{W \times W}, \mathbf {\tau } \in \mathbb {R}^W$, that depicts the time elapsed until arrival to the accepting state. Let us define the generator of the chain as

$$\begin{aligned} \begin{bmatrix} S&-S\mathbf {1} \\ \mathbf {0}&0 \end{bmatrix}. \end{aligned}$$

It has $W+1$ states, the last state is accepting. Vector $\mathbf {\tau }$ specifies the initial distribution of probabilities of the modulating chain.

To make allowance for the limited station memory the queue of each station is supposed to have a capacity of $M_{i}$ packets and each station can contain up to $K_{i}=M_{i}+1$ packets.

Let us consider each station as associated with a user which contributes to the network with the arrival process $A_{i} \sim MAP(D_{0}^{(i)}, D_{1}^{(i)})$ and can be treated as the traffic sink as well: each packet accepted by the station with the probability $r_{i}$ is transmitted to the user and leaves the network or it arrives to the queue with complementary probability $1-r_{i}$. If the queue is full, the packet is lost irretrievably. The service time is PH-distributed: $B \sim PH(S^{i}, \mathbf {\tau }^{i})$.

Fig. 1.

The queueing network modelling wireless network with linear topology.

Finally, the packet routing is carried out according to the stochastic matrix $T \in \mathbb {R}^{N \times N}$, where N is the number of stations. Element $t_{ij}$ of the matrix equals the conditional probability of packet transmission to the j-th station after serving at the i-th station on condition of successful transmission. Since the ability to transmit the packet back to the queue having been considered, it is reasonable to suppose $t_{ii}=0$ for all i.

Unconditional probabilities of packet transmission from the i-th to the j-th station, to its user as well as packet loss and packet retransmission probabilities are shown in Fig. 1.

The functioning of the whole network is described by a Markovian process $\mathcal {C} \sim Markov(Q)$, that is defined by a Markovian process modulating MAP and PH-distributions. Having the infinitesimal generator Q of such a process one can compute the stationary probability distribution of its states and then the distribution of queue lengths, busy coefficients of stations and other characteristics. Moreover, it is easy to build matrices $\hat{D}_{0}^{(i)}$, $\hat{D}_{1}^{(i)}$ of the MAP of packets served by the i-th station and also $\check{D}_{0}^{(i)}$, $\check{D}_{1}^{(i)}$ of overall MAP incoming at the i-th station. Knowing these matrices allows us to compute the probability that the next packet is lost due to memory overflow.

So, the space of states and transition intensities between the states are required to be defined to describe the process $\mathcal {C}$. It is possible to completely define any state of the chain given the following values:

• the number of packets $k_{i}$ at the i-th station, $k_{i}=0..K_{i}$;

• the state $a_{i}$ of a user input MAP $A_{i}, a_{i} \in 1..V_{t}$;

• the state $b_{i}$ of a server (of its PH-distribution modulating chain), $b_{i} \in 1..W_{i}$.

It is not difficult to see that the state space of the process has size $Z=\prod _{i=1}^{N}(V_{i} + K_{i}V_{i}W_{i})$ and grows exponentially with the growth of N. It is not feasible to express the generator matrix in explicit form due to its size. Instead of this let us take advantage of the notion of transition classes (e.g., see [8]) and describe them. Each class defines the set of transitions of the same type in which some subset of states changes equally while other states remain immutable.

The change of the state of the chain $\mathcal {C}$ can be caused by both the state change of a user MAP or PH-distribution of a server. If the transition does not cause either packet arrival or service completion, then the change is localized in the corresponding process. Otherwise, both the state of the corresponding process and the number of packets in one or two nodes can be changed.

Let triplet $\langle k_{i}, v_{i}, w_{i} \rangle$ describe the state of the i-th node, where $k_{i}$ is the number of packets in the node, $v_{i}$ — the state of a user input MAP, $w_{i}$ — the state of a server. For the reason that the last component is meaningless when $k_{i}=0$, we can omit it from time to time: $\langle 0, v_{i} \rangle$. The transition class is depicted by the expression of the form:

$$\begin{aligned} \langle k_{i}, v_{i}, w_{i} \rangle , \langle k_{j}, v_{j}, w_{j} \rangle \xrightarrow {\lambda } \langle \acute{k}_{i}, \acute{v}_{i}, \acute{w}_{i} \rangle , \langle \acute{k}_{j}, \acute{v}_{j}, \acute{w}_{j} \rangle \end{aligned}$$

where the left side of the expression describes the states of the nodes before transition and the right side — the states after transition (the state with a dash sign is modified); the transition intensity is above the arrow. Other states not mentioned in the expression remain unmodified.

The transitions appearing due to the change of the state of modulating chain of input MAP-flow of the i-th node $A_{i} \sim MAP(D_{0}^{(i)}, D_{1}^{(i)})$:

$$\begin{aligned} \langle k_{i}, v_{i}, w_{i} \rangle , \xrightarrow { \{ D_{1}^{(i)} \}_{ v_{i}\acute{v}_{i} } } \langle \min (k_{i}+1, K_{i}), \acute{v}_{i}, w_{i} \rangle \end{aligned}$$

(1)

$$\begin{aligned} \langle 0, v_{i} \rangle , \xrightarrow { \tau _{w_{i}}^{(i)} \{ D_{1}^{(i)} \}_{ v_{i} \acute{v}_{i} } } \langle 1, \acute{v}_{i}, w_{i} \rangle \end{aligned}$$

(2)

$$\begin{aligned} \langle k_{i}, v_{i}, w_{i} \rangle , \xrightarrow { \{ D_{0}^{(i)} \}_{ v_{i} \acute{v}_{i} } } \langle k_{i}, \acute{v}_{i}, w_{i} \rangle \end{aligned}$$

(3)

$$\begin{aligned} \langle 0, v_{i} \rangle , \xrightarrow { \{ D_{0}^{(i)} \}_{ v_{i} \acute{v}_{i} } } \langle 0, \acute{v}_{i} \rangle \end{aligned}$$

(4)

The transition appearing due to the change of the state of the modulating chain of PH-distribution of a server $B_{i} \sim PH(S^{(i)},\mathbf {\tau }^{(i)})$:

$$\begin{aligned} {\begin{matrix} \langle k_{i}, v_{i}, w_{i} \rangle , \langle k_{j}, v_{j}, w_{j} \rangle \xrightarrow { t_{ij} (1-r_{j}) (1-p_{e_{i}}) \tau _{w_{i}}^{(i)} \{ -S^{(i)}\mathbf {1} \}_{w_{i}} } \\ \langle k_{i}-1, v_{i}, \acute{w}_{i} \rangle , \langle \min (k_{j}+1, K_{j}), v_{j}, w_{j} \rangle \end{matrix}} \end{aligned}$$

(5)

$$\begin{aligned} \langle k_{i}, v_{i}, w_{i} \rangle , \langle 0, v_{j} \rangle \xrightarrow { t_{ij} (1-r_{j}) (1-p_{e_{i}}) \tau _{\acute{w}_{i}}^{(i)} \tau _{w_{j}}^{(j)} \{ -S^{(i)}\mathbf {1} \}_{w_{i}} } \langle k_{i}-1, v_{i}, \acute{w}_{i} \rangle , \langle 1, v_{j}, w_{j} \rangle \end{aligned}$$

(6)

$$\begin{aligned} {\begin{matrix} \langle 1, v_{i}, w_{i} \rangle , \langle k_{j}, v_{j}, w_{j} \rangle \xrightarrow { t_{ij} (1-r_{j}) (1-p_{e_{i}}) \{ -S^{(i)}\mathbf {1} \}_{w_{i}} } \\ \langle 0, v_{i} \rangle , \langle \min (k_{j}+1, K_{j}), v_{j}, w_{j} \rangle \end{matrix}} \end{aligned}$$

(7)

$$\begin{aligned} \langle 1, v_{i}, w_{i} \rangle , \langle 0, v_{j} \rangle \xrightarrow { t_{ij} (1-r_{j}) (1-p_{e_{i}}) \tau _{w_{j}}^{(j)} \{ -S^{(i)}\mathbf {1} \}_{w_{i}} } \langle 0, v_{i} \rangle , \langle 1, v_{j}, w_{j} \rangle \end{aligned}$$

(8)

$$\begin{aligned} \langle k_{i}, v_{i}, w_{i} \rangle , \xrightarrow { \tau _{\acute{w}_{i}}^{(i)} ( t_{ij}r_{j} (1-p_{e_{i}}) + p_{e_{i}}p_{l_{i}} ) \{ -S^{(i)}\mathbf {1} \}_{w_{i}} } \langle k_{i}-1, v_{i}, \acute{w}_{i} \rangle , \end{aligned}$$

(9)

$$\begin{aligned} \langle 1, v_{i}, w_{i} \rangle , \xrightarrow { ( t_{ij}r_{j} (1-p_{e_{i}}) + p_{e_{i}}p_{l_{i}} ) \{ -S^{(i)}\mathbf {1} \}_{w_{i}} } \langle 0, v_{i} \rangle , \end{aligned}$$

(10)

$$\begin{aligned} \langle k_{i}, v_{i}, w_{i} \rangle , \xrightarrow { \tau _{\acute{w}_{i}}^{(i)} p_{e_{i}} (1-p_{l_{i}}) \{ -S^{(i)}\mathbf {1} \}_{w_{i}} + S^{(i)}_{w_{i} \acute{w}_{i}}} \langle k_{i}, v_{i}, \acute{w}_{i} \rangle , \end{aligned}$$

(11)

The classes (1) and (2) correspond to the appearing of a packet in MAP, (3) and (4) — transition of the chain of MAP-flow without packet generating. The classes (5)–(8) correspond to transition of the chain of PH-distribution of the i-th device into an accepting state and transmission of the packet to the j-th node. The classes (9) and (10) correspond to the transition of the chain of PH-distribution into the accepting state with the error of transmission or transmission of the packet to the user of the i-th node – anyway, the packet leaves the network irretrievably. Finally, the class (11) corresponds to the transitions of the chain of PH-distribution which leads the chain into the accepting state, but the packet is retransmitted (the first summand) or the transition of the chain is carried out into a non-accepting state (the second summand) and service is continued - the amount of packets in the node is not changed.

Let $\mathbf {x} = (\mathbf {x}_{1}, \cdots , \mathbf {x}_{i}, \cdots , \mathbf {x}_{N})$ be the state of the chain $\mathcal {C}$, where

$$\begin{aligned} \mathbf {x}_{i} = {\left\{ \begin{array}{ll} \langle k_{i}, v_{i}, w_{i} \rangle &{} \text{ if } k_{i}=1 \cdots K_{i} \\ \langle 0, v_{i} \rangle &{} \text{ if } k_{i}=0 \end{array}\right. } \end{aligned}$$

— the state of the i-th node, X the set of all states of the chain, $\Vert X\Vert = \prod _{i=1}^{N} (V_{i} + K_{i}V_{i}W_{i})$. The stationary distribution of the chain $\mathcal {C}$ can be found as the solution of the system:

$$\begin{aligned} \varvec{\pi } Q = 0, \varvec{\pi } \mathbf {1} = 1, \end{aligned}$$

where $\varvec{\pi } \in [0,1]^{|X|}$. Let $q_{l}^{(i)} = \mathbb {P}\{ k_{i}=l \} = \sum _{\mathbf {x}:k_{i}=l} \pi _{\mathbf {x}}$ — the stationary probability that the i-th node has l packets. In particular, $q_{0}^{(i)}$ — the probability of the fact that the node is vacant and $q_{K_{i}}^{(i)}$ — the probability that the queue is full. Knowing the probabilities $\{q_{K}^{(i)}\}$ allows us to compute the mean number of packets $l_{i} = \sum _{k=0}^{K_{i}} kq_{k}^{(i)}$ in the i-th station, from which the loss probability of the arrival packet can be achieved:

$$\begin{aligned} p_{ql}^{(i)} = \mathbf {v}^{(i)} \frac{\check{D}_{1}^{(i)}}{\lambda ^{(i)}}\mathbf {1}, \end{aligned}$$

where $\mathbf {v}^{(i)}$ is a projection of the vector $\varvec{\pi }$ in which $k_{i} = K_{i}$, $\check{D}_{1}^{(i)}$ is the matrix of visible transitions of input MAP, and $\lambda ^{(i)} = \varvec{\phi }^{(i)}\check{D}_{1}^{(i)}$ is a mean arrival intensity of this process, $\varvec{\phi }^{(i)}$ is its stationary probability distribution. The probability $\varvec{\phi }^{(i)}$ and $\mathbf {v}^{(i)}$ can be achieved from $\varvec{\pi }$ by summing up over the states from which the input arrival process is independent.

Knowing the mean intensity of packet arrival $\lambda ^{(i)}$ and the mean number of packets in the system makes it possible to compute the mean packet delay in the station by Little’s formula: $T_{i} = l_{i}/[(1-p_{ql}^{(i)})\lambda ^{(i)}]$ . Here an additional factor in the denominator appears due to the fact that the input process turns out to be filtered with the probability being equal complementary loss probability resulting from the queue overflow.

To study other characteristics of the model the expression of MAP incoming to the station (both from the user and from other stations) as well as of MAP departure may be required. Due to the existence of feedback in the general case the modulating chains will depend on the states of all network nodes. Therefore let us consider the modulating chain of the arrival process that is to be found, to have the same space of the state X as the process operating the system does. Obviously, chain $\mathcal {C}$ performs control over MAP as well, however from different points of observation the transitions being in an intensity matrix of packet generating $D_{i}$ will differ. So, to determine a MAP $A^{(i,j)} \sim MAP(D_{0}^{(i,j)},D_{1}^{(i,j)})$ describing the arriving of the packets at the j-th node after being served at the i-th node, the intensities defined by expressions (5)–(8) for the given pair (i, j) should be placed into matrix $D_{1}^{(i,j)}$ and the other intensities — into matrix $D_{0}$. If the MAP $\check{A}^j \sim MAP(\check{D}_{0}^{(j)},\check{D}_{1}^{(j)})$ arriving at the station j from all other stations (excluding packet retransmission as it actually does not affect the amount of packets in the network) is in a region of interest, then all intensities (5)–(8) for all $i \ne j$ should be placed into matrix $D_{1}$. An other arrival process can be achieved similarly.

It should be noted that the matrices of the arrival process have an enormous size, which makes it difficult or even impossible to use them for analytical computations. However, it is possible to achieve more simple expressions for the arrival process matrices in some special cases. In particular, it is possible to build MAP for a tandem network that is described below as an example, with the help of the following theorems [4, 9, 10]:

Theorem 1

The result of sifting of MAP $A \sim MAP(D_{0},D_{1})$ with probability p is MAP $A_{p} \sim MAP(D_{0}+(1-p)D_{1},pD_{1})$ (further we will denote it as pA).

Theorem 2

The composition of a MAP $A_{1} \sim MAP(D_{0}^{(1)},D_{1}^{(1)})$ and a MAP $A_{2} \sim MAP(D_{0}^{(2)},D_{1}^{(2)})$ is a MAP $B = A_{1} \oplus A_{2} \sim MAP(D_{0}^{(1)} \oplus D_{0}^{(2)},D_{1}^{(1)} \oplus D_{1}^{(2)})$, where $\oplus$ is a Kronecker sum.

Theorem 3

A MAP of served packets in the system $MAP{\slash }PH{\slash }1{\slash }M$, where the interval between arrivals is distributed by $A \sim MAP(D_{0},D_{1})$, service time - $B \sim PH(S, \varvec{\tau })$, M is the capacity of the queue, V is an order of matrix S, W is a number of input MAP states, service discipline is FIFO, is $B \sim MAP(\hat{D}_{0},\hat{D}_{1})$ and its matrices are defined as:

$$\begin{aligned} \hat{D}_{0} = \begin{bmatrix} D_{0} \otimes I_{V}&R_{0}&0&\cdots&0&0\\ 0&D_{0} \otimes S&D_{1} \otimes I_{V}&\cdots&0&0\\ 0&0&D_{0} \otimes S&\cdots&0&0 \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0&0&\cdots&D_{0} \otimes S&D_{1} \otimes I_{V}\\ 0&0&0&\cdots&0&R_{A} \end{bmatrix}, \end{aligned}$$

$$\begin{aligned} \hat{D}_{1} = \begin{bmatrix} 0&\cdots&0&0&0 \\ I_{W} \otimes C_{t}&\cdots&0&0&0 \\ \vdots&\ddots&\vdots&\vdots&\vdots \\ 0&\cdots&I_{W} \otimes C_{t}&0&0\\ 0&\cdots&0&I_{W} \otimes C_{t}&0 \end{bmatrix}, \end{aligned}$$

where

$$\begin{aligned} R_{0} = D_{1}\otimes (\varvec{\tau } \otimes \mathbf {1}_{V}), \end{aligned}$$

$$\begin{aligned} R_{A} = (D_{0}+D_{1}) \otimes S, \end{aligned}$$

$$\begin{aligned} C_{t} = (-S \mathbf {1}_{V}) \otimes \varvec{\tau } \end{aligned}$$

There are no state components corresponding to the number of packets in the i-th and further stations of the input MAP in construction of MAP as consistent with the given theorems. At the expense of this fact the computation is significantly simplified, in particular the computation of vectors $\varvec{\phi }^{(i)}$ and $\mathbf {v^{(i)}}$: the first one turns out to be a projection of the stationary distribution of generators states of the i-th station that corresponds to a full queue and the second one — the stationary distribution of the states of an input MAP generator.

Due to the exponential growth and enormously large dimension of the state space it is extremely difficult to find precise analytical expressions even for small dimensions. For practical applications of the suggested model approximation methods can be exploited. Such methods approximate both MAP and PH-distributions by the arrival process and distributions of lower dimensions and replace the large fragments of the network by much more simple chains that approximate such fragments [11]. The method of iterative search can be applied for an approximate solution by using multiplicative representation according to paper [8]. The other way to explore such systems is to apply the method of iterative modelling presented in the current work as well to simulate the networks of enormous dimensions.

3 Simulation of a Wireless Network with Linear Topology and Hot Standby Links

Wireless networks with linear topology are often used to organize connections along long-length objects (highways, railways, pipeline) when the optical fibre is not available. Up-to-date wireless communication systems allows us to build networks consisting of a large amount of retransmitters being placed from 100 m to tens of kilometres from each other and providing transmission rate from 150 Mbps (e.g. IEEE 802.11) to 1 Gbps (e.g. mmwave relay link).

The network suffers from packet losses as it is wireless. In the case of outage of one of the stations its neighbours can connect with each other if visibility conditions and the strength of the signal allow to do it. Such connections are acceptable in the case of the station working correctly as well. An example of such a network is shown in Fig. 2.

Fig. 2.

The queueing network modelling wireless network with linear topology.

A special case of a wireless network with linear topology is an uplink aggregation network where the traffic is generated by the users (e.g. video cameras) and being transmitted to a control centre. In particular, such networks are applied in road safety systems. We have studied this network in the model mentioned above as an example. The analytical computations have been performed for a simple network where the transmissions occur between neighbouring stations only, and the same network to calibrate the results as well as a network where transmissions escaping neighbouring stations are allowed is computed with the help of simulation.

As was mentioned above the construction of a chain generator faces the problem of exponential growth of the state space. In the case of an open queueing system without routing loops the scheme of chain construction can be simplified. To achieve the analytical solution of the problem the scheme of iterative construction of served packets MAP was employed [10]. This scheme is similar to the one being used to explore a more simple open network with linear topology that takes advantage of consecutive transmission without transmission losses and losses due to transmission errors. According to this scheme, starting from the first station, MAP matrices are build, that describe the intervals between the outage of served packets of each station. Output arrival processes are computed as a composition of input MAP. The iterative procedure using Theorems 1–3 mentioned above is made use of.

One of the most important characteristics of the network functioning is an end-to-end delay being equal to the time passed from the packet arrival into the network until it leaves the network in a destination node. As all packets of a data aggregation network are transmitted into the center connected with the N-th station the delay of packet transmission in the network from the i-th station can be computed as the sum of delays $\sum _{j=i}^{N}T_{j}$, where $T_{j}$ is a delay in the j-th station, the computation of it having been described above. Let us note that in case of a computation of the mean residence time the loss probabilities must be taken into account. At the same time keeping computation of end-to-end delays we actually consider only the packets arriving successfully and take advantage of conditional probabilities of successful arrival. In the studied models the same cross-traffic arrived into all stations. Therefore a mean delay throughout the whole network is supposed to be equal to the arithmetic average of delay from each station.

The characteristics of a network with linear topology without the ability to transmit over the neighbour (i.e. all traffic is directed to the next station) have been studied with the help of an analytical model. The computation has been performed iteratively according to the scheme mentioned above. A more general case has been studied with the help of simulation. In that case the routing matrix of a data aggregation network with linear topology has an upper triangular form with zero main diagonal:

$$\begin{aligned} T = \begin{bmatrix} 0&t_{12}&\cdots&t_{1N} \\ 0&0&\cdots&t_{2N} \\ \vdots&\vdots&\ddots&\vdots \\ 0&0&\cdots&0 \end{bmatrix} \end{aligned}$$

Fig. 3.

A graphic representation of input MAP being used (transitions corresponding to the $D_{0}$ matrix marked by dashed lines and transitions corresponding to the $D_{1}$ matrix marked by solid lines)

To simplify the computation we make a natural assumption that the station can transmit data to its neighbour or the station next to the neighbour only (that is nonzero elements of matrix T are $t_{i,i+1}$ and $t_{i,i+2}$) and these probabilities are equal for all stations excluding two border stations: $p = t_{i,i+1} \forall i < N-1$. The input MAP $A_{0} \sim MAP(D_{0},D_{1})$ are as follows:

$$\begin{aligned} D_{0} = \begin{bmatrix} -1.724&0&0 \\ 0.172&-1.552&1.293 \\ 0.086&1.724&-1.811 \end{bmatrix} \quad D_{1} = \begin{bmatrix} 0.862&0.862&0 \\ 0&0&0.086 \\ 0&0&0 \end{bmatrix} \end{aligned}$$

The graph depicting this MAP is shown in Fig. 3. Such MAP arrives at each station as a cross-traffic. In different experiments MAP is scaled using the mean.

To simplify the computation the serving is performed according to the exponential distribution with rate $\mu = 5$ in all experiments. The number of stations in the network is supposed to be equal to $N = 5$ and the capacity of all queues is supposed to be $K = 2$.

Fig. 4.

Mean time of end-to-end delay depending on the mean rate of input cross-traffic. The value of the p parameter is a fraction of traffic transmitted to direct neighbour after service completion

Fig. 5.

The delivery and loss probabilities as well as the mean queueing lengths (left). The mean intensities of input and served arrivals over stations (right).

In Fig. 4 end-to-end delays for different arrived rates of input MAP and different value of the probability p of packet transmission to the direct neighbour (the less p, the greater a fraction of the traffic transmitted escaping the direct neighbour) are shown. As we can see in the figure the delay decreases when the fraction of the traffic transmitted into direct neighbour drops. The result is expected and related to reduction of the mean path length that packet is transmitted over to the last station.

Let us note that the delay tendency to an asymptote when the intensity growths (instead of an unbound increase in the case of systems with an infinite queue) related to memory limitation — starting from some moment the stations are in a high-loaded state, all the extra packets are discarded and the delay of served packets stops increasing. The result is also confirmed by the change of delivery and loss probabilities over different stations and the change in the mean number of packets in stations as well (see Fig. 5).

As in the case of delays the losses drops when parameter p reduces, which is also related to the reduction of route lengths and, as a consequence, the reduction of input arrivals rates (see Fig. 5). At the same time starting from some moment the stations accumulate at input the maximum arrivals that they can serve whereupon the studied parameters change slightly; but if the p is small this moment comes later.

The dependence of delivery probability on the mean intensity of input outer traffic and parameter p is illustrated in the form of a heatmap in Fig. 6. Here the brighter the colour, the lower the successful delivery probability.

Fig. 6.

The dependence of delivery probability on cross-traffic mean arrival rate (ordinate, rises from bottom to top) and the fraction of traffic transmitted to its direct neighbour (abscissa, rises from left to right).

To carry out the calculations, analysis of results and their visualisation a pyQuMo library allowing us to work effectively with Markovian queueing models of large dimensions was developed. It is implemented in Python 3 languages and based on SciPy, NumPy and Pandas libraries. One of the advantages of pyQuMo is the storing and handling of chain generators in the form of sparse matrices which allows the handling of models having up to several million states using an ordinary laptop. As simulation requires the handling of a large amount of events the OMNeT++ system is used. The work with a simulation model is performed by pyQuMo, making it possible to compare the results of analytical modelling and simulation using a single program. A vast bulk of statistics is collected during the program work and to meet this problem SQLite is made use of.

4 Conclusion

In this paper a model of an open queueing network with correlated input Markovian arrival processes and phase type distribution of service time is presented. A network with linear topology that adequately describes wireless long-distance networks with the ability to transmit data over several stations is studied specially. A comparison study of numeric results of analytic modelling and simulation has been carried out. It is shown that to drop transmission delays as well as the fraction of packet losses it is rational to divide traffic and transmit as small a fraction as possible to the direct neighbour. We developed a pyQuMo library in Python 3 language to compute queueing systems with correlated input arrivals.