Modelling Transient States in Queueing Models of Computer Networks: A Few Practical Issues

Abstract

The article summarises author’s experience in two problems related to the use of queueing models in performance evaluation of computer networks: modelling transient states of queues and computations for queueing network models having large number of nodes. Both issues are not well represented in classical queueing theory, yet important to applications, because the observed traffic is time dependant and network topologies that should be considered become larger and larger. The article discusses two approaches: diffusion approximation and fluid-flow approximation that can cope with much larger models that are attainable with the use of Markov chains.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Queueing models are frequently used in modelling and evaluation of computer networks. Queueing theory, introduced a century ago to model telephone exchanges was successfully adapted to the needs of computer science but new problems arise following the constant development of computer networks. The problems are mainly related to computational aspects of queueing models and more precisely to the need of taking into account very large topologies, corresponding to real ones encountered in computer networks and the necessity to analyse transient behaviour of queues, as the intensity of traffic flows generated by users, e.g. internet applications is permanently changing. The quality of transmission services depends on current load of links and not on its average value. Also modelling and understanding the performance of traffic control mechanisms, control stability and its impact on quality of service needs transient state analysis, e.g. [27].

The use of analytical models known in classical queueing theory is limited to single M/M/1 and M/M/1/N stations and even there the transient state solutions are quite complex. Moreover, the results refer to transient states but it is assumed that the model parameters, the input rate in particular, are constant. Therefore, they do not fit well the problem of modelling IP routers, where the incoming streams of packets are not Poisson and the size of packets is not exponentially distributed. We need models describing constantly changing non-Poisson flows and considering general distributions of service times. We need also the possibility to include in these models the description of self-similarity of flows. The models should also be scalable to meet very large topologies characteristic to the Internet.

In sections that follow we describe our experience and present simple numerical examples referring diffusion approximation, and fluid-flow approximation – the approaches we think are most suitable to this purposes.

2 Diffusion Approximation of a Single Queue

This approach is merging states of the considered queueing system and thus needs much less computations than the Markov models. We present here the principles of the method following [9] where steady-state solution of a single G/G/1/N model was given and then extended to the network of queues in [10]. We supplemented these results with semi-analytical, semi-numerical transient state solution [3] given for constant model parameters but it could be applied also in case of time-dependent parameters if we only make them constant within small intervals.

Let $A(x)$, $B(x)$ denote the interarrival and service time distributions at a service station and $a(x)$ and $b(x)$ be their density functions. The distributions are general but not specified, the method requires only the knowledge of their two first moments. The means are denoted as $E[A]=1/\lambda$, $E[B]=1/\mu$ and variances are $\text {Var}[A] = \sigma _{A}^2$, $\text {Var}[B]= \sigma _B^2$. Denote also squared coefficients of variation $C_A^2=\sigma _{A}^2 \lambda ^2$, $C_B^2=\sigma _{B}^2 \mu ^2$. $N(t)$ represents the number of customers present in the system at time $t$.

Diffusion approximation, replaces the process $N(t)$ by a continuous diffusion process $X(t)$, the incremental changes $dX(t) = X(t + dt) - X(t)$ of which are normally distributed with the mean $\beta dt$ and variance $\alpha dt$, where $\beta$, $\alpha$ are coefficients of the diffusion equation

$$\begin{aligned} \frac{\partial f(x,t;x_0)}{\partial t} = \frac{\alpha }{2} \frac{\partial ^2 f(x,t;x_0)}{\partial x ^2} - \beta \frac{\partial f(x,t;x_0)}{\partial x}\,. \end{aligned}$$

(1)

This equation defines the conditional pdf of $X(t)$:

$$ f(x,t;x_0) dx =P [x \le X(t) < x + dx \,\, |\,\, X(0) = x_{0} ]. $$

The both processes $X(t)$ and $N(t)$ have normally distributed changes; the choice $\beta = \lambda - \mu$, $\alpha = \sigma _{A}^{2} \lambda ^{3} + \sigma _{B}^{2} \mu ^{3}= C_{A}^{2} \lambda + C_{B}^{2} \mu$ ensures that the parameters of these distributions increase at the same rate with the length of the observation period. In the case of G/G/1/N station, the process evolves between barriers placed at $x=0$ and $x=N$ where barriers with instantaneous jumps are placed, [9]. When the diffusion process comes to $x=0$, it remains there for a time exponentially distributed with a parameter $\lambda _0$ and then it returns to $x=1$. The time when the process is at $x=0$ corresponds to the idle time of the system. When the process comes to the barrier at $x=N$, it stays there for a time which is exponentially distributed with a parameter $\mu _0$ which corresponds to the time when the system is full and do not accept new customers (the completion time of current service from the moment when the queue becomes full). The assumption on exponential sojourn times in barriers will be dropped below where transient model is presented. Diffusion equation becomes and is supplemented by balance equations for probabilities $p_0(t)$ and $p_N(t)$ of being at the barriers

$$\begin{aligned} \frac{\partial f(x,t;x_0)}{\partial t}&= \frac{\alpha }{2} \frac{\partial ^2 f(x,t;x_0)}{\partial x ^2} - \beta \frac{\partial f(x,t;x_0)}{\partial x}+ \nonumber \\&\quad \;\; + \lambda _0 p_0(t) \delta (x-1) + \lambda _N p_N(t) \delta (x-N+1)\;, \nonumber \\ \frac{dp_0(t)}{dt}&= \lim _{x \rightarrow 0} \;[\frac{\alpha }{2} \frac{\partial f(x,t;x_0)}{\partial x} - \beta f(x,t;x_0)] - \lambda _0 p_0(t)\;, \nonumber \\ \frac{dp_N(t)}{dt}&= \lim _{x \rightarrow N} \;[- \frac{\alpha }{2} \frac{\partial f(x,t;x_0)}{\partial x} + \beta f(x,t;x_0)] - \lambda _N p_N(t)\;, \end{aligned}$$

(2)

where $\delta (x)$ is Dirac delta function.

Our solution of these equations is based on the representation of the density function $f(x,t;x_0)$ of the diffusion process with barriers with jumps by a superposition of the density functions $\phi (x,t;x_0)$ of diffusion processes with absorbing barriers at $x=0$ and $x=N$, which has the following form

$$\begin{aligned} \phi (x,t;x_0)=\left\{ \begin{array}{lll} \delta (x-x_0) &{}\text {for} &{} t=0 \\ \frac{1}{\sqrt{2 { \Pi } \alpha t}} \sum _{n=-\infty }^{\infty } \Bigl \{ \exp \left[ \frac{\beta x_n '}{\alpha } - \frac{(x-x_0-x_n'-\beta t)^2}{2 \alpha t} \right] &{} &{} \\ \qquad \quad \qquad - \exp \left[ \frac{\beta x_n ''}{\alpha } - \frac{(x-x_0-x_n''-\beta t)^2}{2 \alpha t} \right] \Bigr \} &{}\text {for} &{} t>0\,, \\ \end{array} \right. \end{aligned}$$

(3)

where $x_n ' = 2nN$, $x_n '' =- 2x_0 - x_n '\;.$ If the initial condition is defined by a function $\psi (x)$, $x \in (0,N)$, $\lim _{x \rightarrow 0}\psi (x) =\lim _{x \rightarrow N}\psi (x)=0$, then the pdf of the process has the form $\phi (x,t;\psi )= \int _0 ^N \phi (x,t;\xi )\psi (\xi ) d \xi$.

The probability density function $f(x,t;\psi )$ of the diffusion process with elementary returns is composed of the function $\phi (x,t;\psi )$ which represents the influence of the initial conditions and of a spectrum of functions $\phi (x,t-\tau ;1)$, $\phi (x,t-\tau ;N-1)$ which are pd functions of diffusion processes with absorbing barriers at $x=0$ and $x=N$, started at time $\tau <t$ at points $x=1$ and $x=N-1$ with densities $g_1(\tau )$ and $g_{N-1}(\tau )$:

$$\begin{aligned} f(x,t;\psi )= \phi (x,t;\psi ) + \int _0 ^{t} g_1(\tau )\phi (x,t-\tau ;1) d\tau +\int _0 ^{t} g_{N-1}(\tau )\phi (x,t-\tau ;N-1) d\tau \;. \end{aligned}$$

(4)

Densities $\gamma _{0}(t)$, $\gamma _N (t)$ of probability that at time $t$ the process enters to $x=0$ or $x=N$ are

$$\begin{aligned} \gamma _0(t)&= p_0(0)\delta (t) + [1-p_0 (0)-p_N(0)]\gamma _ {\psi ,0}(t) + \int _0 ^{t} g_1(\tau )\gamma _{1,0}(t-\tau ) d \tau \nonumber \\&\quad +\int _0 ^{t} g_{N-1}(\tau )\gamma _{N-1,0}(t-\tau ) d \tau \;, \nonumber \\ \gamma _N(t)&= p_N(0)\delta (t) + [1-p_0(0)-p_N(0)] \gamma _ {\psi ,N}(t) + \int _0 ^{t} g_1(\tau )\gamma _{1,N}(t-\tau ) d \tau \nonumber \\&\quad +\int _0 ^{t} g_{N-1}(\tau )\gamma _{N-1,N}(t-\tau ) d \tau \;, \end{aligned}$$

(5)

where $\gamma _{1,0}(t)$, $\gamma _{1,N}(t)$, $\gamma _{N-1,0}(t)$, $\gamma _{N-1,N}(t)$ are densities of the first passage time between corresponding points, e.g.

$$\begin{aligned} \gamma _{1,0}(t)=\lim _{x \rightarrow 0}[ \frac{\alpha }{2} \frac{\partial \phi (x,t;1)}{\partial x} -\beta \phi (x,t;1)]\;. \end{aligned}$$

(6)

For absorbing barriers

$$\lim _{x \rightarrow 0} \phi (x,t;x_0) = \lim _{x \rightarrow N} \phi (x,t;x_0) = 0\,, $$

hence $\gamma _{1,0}(t)= \lim _{x \rightarrow 0} \frac{\alpha }{2} \frac{\partial \phi (x,t;1)}{\partial x}.$ The functions $\gamma _{\psi ,0}(t)$, $\gamma _{\psi ,N}(t)$ denote densities of probabilities that the initial process, started at $t=0$ at the point $\xi$ with density $\psi (\xi )$ will end at time $t$ by entering respectively $x=0$ or $x=N$.

Finally, we may express $g_1(t)$ and $g_{N}(t)$ with the use of functions $\gamma _0(t)$ and $\gamma _N(t)$:

$$\begin{aligned} g_1(\tau )= \int _0 ^{\tau } \gamma _0 (t)l_0 (\tau -t) dt \;, \qquad g_{N-1}(\tau )= \int _0 ^{\tau } \gamma _N (t)l_N (\tau -t) dt \;, \end{aligned}$$

(7)

where $l_0(x)$, $l_N(x)$ are the densities of sojourn times in $x=0$ and $x=N$; the distributions of these times are not restricted to exponential ones as it is in Eq. (2).

The above equations are transformed by the Laplace transform, and the transform of $f(x,t, x_0)$ is obtained analytically and then its original is computed numerically using e.g. Stehfest algorithm [22].

In case of unlimited queue of G/G/1 type we just remove the barrier at $x=N$ and related to it terms and equations.

3 Open Network of G/G/1, G/G/1/N Queues, One Class, Steady State and Transient Solution

The steady-state open networks models of $G/{}G/{}1$ queues were studied in [10]. Let $M$ be the number of stations and suppose at the beginning that there is one class of customers. The throughput of station $i$ is, as usual, obtained from traffic equations

$$\begin{aligned} \lambda _i = \lambda _{0i} + \sum _{j=1}^M \lambda _{j} r_{ji}\,, \qquad i=1, \ldots , M, \end{aligned}$$

(8)

where $r_{ji}$ is routing probability between station $j$ and station $i$; $\lambda _{0i}$ is external flow of customers coming from outside of network.

Second moment of interarrival time distribution is obtained from two systems of equations; the first defines $C_{Di}^2$ as a function of $C_{Ai}^2$ and $C_{Bi}^2$; the second defines $C_{Aj}^2$ as another function of $C_{D1}^2$, ..., $C_{DM}^2$:

(1) The formula (9) is exact for $M/G/1$, $M/G/1/N$ stations and is approximate in the case of non-Poisson input [1]

$$\begin{aligned} d_{i}(t) = \varrho _{i} b_{i}(t) + (1-\varrho _{i}) a_{i}(t) * b_{i}(t)\;, \qquad i=1, \ldots ,M, \end{aligned}$$

(9)

where * denotes the convolution operation. From (9) we get

$$\begin{aligned} C_{Di}^{2} = \varrho _{i}^{2}C_{Bi}^{2} + C_{Ai}^{2}(1-\varrho _{i}) + \varrho _{i} (1-\varrho _{i})\,. \end{aligned}$$

(10)

(2) Customers leaving station $i$ according to the distribution $D_i(x)$ choose station $j$ with probability $r_{ij}$: intervals between customers passing this way has pdf $d_{ij}(x)$

$$\begin{aligned} d_{ij}(x)=d_i(x) r_{ij} + d_i(x) *d_i(x) (1-r_{ij})r_{ij} + d_i(x) *d_i(x)*d_i(x) (1-r_{ij})^2 r_{ij} + \cdots \end{aligned}$$

(11)

hence

$$\begin{aligned} E[D_{ij}] = \frac{1}{\lambda _i r_{ij} }\,, \qquad C_{Dij}^{2} = r_{ij}(C_{Di}^2 -1) +1 \,. \end{aligned}$$

(12)

$E[D_{ij}]$, $C_{Dij}^{2}$ refer to interdeparture times; the number of customers passing from station $i$ to $j$ in a time interval $t$ has approximately normal distribution with mean $\lambda _i r_{ij} t$ and variation $C_{Dij}^{2} \lambda _i r_{ij} t$. The sum of streams entering station $j$ has normal distribution with mean

$$ \lambda _j t = [\sum _{i=1}^M \lambda _i r_{ij} + \lambda _{0j}]\, t \qquad \text {and variance} \qquad \sigma _{Aj} ^2 t = \{ \sum _{i=1}^M C_{Dij}^{2} \lambda _i r_{ij} + C_{0j}^2 \lambda _{0j} \} t\,, $$

hence

$$\begin{aligned} C_{Aj}^{2} = \frac{1}{\lambda _{j}}\sum _{i=1}^{M}r_{ij}\lambda _{i} [(C_{Di}^{2}-1)r_{ij}+1] + \frac{C_{0j}^{2}\lambda _{0j}}{\lambda _{j}}\;. \end{aligned}$$

(13)

Parameters $\lambda _{0j}$, $C_{0j}^{2}$ represent the external stream of customers. For $K$ classes od customers with routing probabilities $r_{ij}^{(k)}$ (let us assume for simplicity that the customers do not change their classes) we have

$$\begin{aligned} \lambda _i^{(k)} = \lambda _{0i}^{(k)} + \sum _{j=1}^M \lambda _{j}^{(k)} r_{ji}^{(k)} \,, \qquad \quad i=1,\ldots ,M; \;\;k=1, \ldots , K , \end{aligned}$$

(14)

and

$$\begin{aligned} C_{Di}^{2} = \lambda _{i}\sum _{k=1}^{K} \frac{\lambda _{i}^{(k)}}{{\mu _{i}^{(k)}}^{2}} [{C_{Bi}^{(k)}}^{2}+1] + 2\varrho _{i} (1-\varrho _{i}) + (C_{Ai}^{2}+1)(1-\varrho _{i}) - 1\,. \end{aligned}$$

(15)

A customer in the stream leaving station $i$ belongs to class $k$ with probability $\lambda _i^{(k)} /\lambda _i$ and we can determine ${C_{Di}^{(k)}}^{2}$ in the similar way as it has been done in Eqs. (11–12), replacing $r_{ij}$ by $\lambda _i^{(k)} / \lambda _i$:

$$\begin{aligned} {C_{Di}^{(k)}}^{2}=\frac{\lambda _i^{(k)}}{\lambda _i} (C_{Di}^2 -1) +1 \,; \end{aligned}$$

(16)

then

$$\begin{aligned} C_{Aj}^{2}=\frac{1}{\lambda _{j}} \sum _{l=1}^{K} \sum _{k=1}^{K} r_{ij}^{(k)} \lambda _{i} \left[ \left( \frac{\lambda _i^{(k)}}{\lambda _i} (C_{Di}^2 -1) \right) r_{ij}^{(k)} + 1\right] + \sum _{k=1}^{K} \frac{{C_{0j}^{(k)}}^{2} \lambda _{0j}^{(k)}}{\lambda _{j}}\;. \end{aligned}$$

(17)

Equations (10), (13) or (15), (17) form a linear system of equations and allow us to determine $C_{Ai}^{2}$ and, in consequence, parameters $\beta _{i}$, $\alpha _{i}$ for each station.

In our approach to transient analysis, the time axis is divided into small intervals (equal e.g. to the smallest mean service time) and at the beginning of each interval the Eqs. (8), (10), (13) are used to determine the input parameters of each station based on the values of $\varrho _i(t)$ obtained at the end of the precedent interval. As the values of parameters are changed at each interval, also external flows $\lambda _{0j}^{(k)}(t)$ may be modelled following any, possibly self-similar process.

Fig. 1.

Topology of the network considered in numerical examples.

Numerical example 1. The considered exemplary network topology is presented in Fig. 1. It was generated by aSHIIP generator [29] allowing generation of hierarchical networks, typical for Internet - this sample network consists of 6 levels. The same topology was used in an example referring to the fluid flow approximation presented in the next section. We do not compare the results, as diffusion model does not incorporate the TCP congestion window mechanism (although it is possible) and the loads of networks are different in both examples. The examples demonstrate rather the possibilities of both approaches. Here, flows are generated by nodes 8, 9, 19 and their intensity is piecewise, given in Table 1, the routing of flows is indicated in the figure. All nodes have the same service intensity $\mu = 3$, the queue capacity is $N = 20$, and the squared coefficient of variation for all flaws and stations are: $C_A ^2= C_B^2 = 1$. The propagation time between nodes is null (it is easy to compute knowing the length o the links and the speed of light in nodes).

Table 1. Generated flows $\lambda _i$, $i=8,9,19,$ as a function of time

In Figs. 2, 3 the time evolution of mean queues in a few chosen nodes, predicted by diffusion approximation and simulation (we treat simulation results as almost exact) are compared, giving the idea of the errors of the approach. The model naturally gives not only these mean values but also the distributions of queues. Figure 4 compares the time-dependant flow intensities at certain nodes obtained via diffusion approximation and simulation. With our software we may we may generate and solve numerically much larger models, having hundreds of thousands or millions nodes and flows. It seems that our solver concerning transient diffusion models is the unique existing one.

Fig. 2.

Mean queue lengths at nodes 9 and 10, diffusion approximation and simulation results

Fig. 3.

Mean queue lengths at nodes 9 and 10, diffusion approximation and simulation results

Fig. 4.

Flow intensities at nodes 8, 9, and 19, diffusion approximation and simulation results

4 Fluid-Flow Approximation

Fluid-flow approximation is a well-known approach of modelling transient behaviour where only mean values of traffic intensity and service times are considered. Compared to the diffusion approximation, mathematical side of the model is simple: instead of partial differential equations of second order, the first-order ordinary linear differential equations are used. Due to its simplicity, it gained much interest in the analysis of transient states in Internet and in investigation of TCP-IP connections stability [4, 31]. Some solvers already exist [6, 7] but we have developed our own to have a better inside to its functionalities and to optimise its performance.

Fluid approximation gives larger methodological errors than the diffusion approximation which is a second-order approximation and considers not only the mean values but also the variance of flow changes. We have also observed it our tests [5].

Here we present the method in a form proposed in [11, 14], already adapted to TCP congestion window mechanism and RED algorithm in routers, hence in an easy way incorporating some essential details of Internet transmissions.

Let the modelled network $V$ be composed of routers. The fluid approximation computes the average values of the queues at the routers while the implemented RED mechanism requires the instantaneous values of them to estimate discard probability. Hence, the instantaneous and average queue lengths in the network are noted by the vectors $\mathbf {q}$ and $\mathbf {x}$. The values of the routers’ discard probabilities depend on the instantaneous queue length and are recorded in vector $\mathbf {p}(\mathbf {x})$ which depends for the router $v \in V$ only on $x_v$. The network structure is represented by binary matrix $\mathbf {A}$. Its rows correspond to TCP flows and the columns represent network nodes. If a flow $i$ traverses a node $k$, the value of the element $a_{ik}$ is determined as “one”, otherwise the element is set to “zero”. The matrix $\mathbf {A}$ and vector $\mathbf {p}(\mathbf {x})$ are used to define a new matrix $\mathbf {B}$: the rows of the matrix $\mathbf {B}$ are formed by multiplying the corresponding element of $\mathbf {p}$ and a row of $\mathbf {A}$, such that ${B_{ij}} = {A_{ij}} \cdot p_j(x_j)$. The $\mathbf {B}$ matrix is used to calculate the total packet loss probability on the path of the entire flow. Each row of the matrix stores the probabilities for routers on the route. To determine the total loss probability, it is necessary to calculate all possible combinations of packet drop probabilities on the path from source to destination. The way to do it is to calculate the success probability (the successful packet arrival traverse through all nodes on the path). The dynamics of the congestion window $W_{i}(t)$ at a connection $i$ is:

$$\begin{aligned} \frac{ dW _{i}(t)}{ dt } = \frac{1}{R_{i}(\varvec{q}(t))}&- \frac{W_{i}(t)}{2}\;\cdot \;\frac{W_{i}(t - \tau )}{R_{i}(\varvec{q}(t - \tau ))}\;\cdot \nonumber \\&\; \cdot \left( 1- \prod _{j\in V}(1- {B}_{ij})\right) \,. \end{aligned}$$

(18)

The other equations concern the mean queue length $q_v$ of router $v$ at this instant, the average queue $x_v$ and delays $R_{i}$.

The router’s AQM packet discard probability $p(x(t))$, Eq. 20, included in the above formula is determined with the use of the weighted average queue length:

$$\begin{aligned} x_{v}(k\delta )\ =\ (1-\gamma _{v})\;\cdot \;x_{v}((k-1)\delta )\ +\ \gamma _{v}q_{v}(k\delta ) \end{aligned}$$

(19)

where:

$\delta$ – queue sampling parameter,

$\gamma$ – weight parameter, specifying the percentage of current queue $q$ taken in the moving average,

$k$ – iteration step,

$$\begin{aligned} p_{v}(x_{v})\ =\ \left\{ \begin{array}{ll} 0,&{}0 \leqslant x_{v}<t_{ min _{v}}\\ \frac{x_{v}\;-\;t_{ min _{v}}}{t_{ max _{v}}-t_{ min _{v}}}p_{ max _{v}}, &{}t_{ min _{v}}\leqslant x_{v}<t_{ max _{v}}\\ 1,&{}t_{ max _{v}}\leqslant x_{v}\leqslant B_{v} \end{array}\right. \end{aligned}$$

(20)

$x_v(t)$, $q_v(t)$ are respectively the average and instantaneous queue lengths in router $v$. With the transmission capacity $C_{v}$ the time change of $q_v$ is

$$\begin{aligned} \frac{ dq _{v}(t)}{ dt }\ =\ \sum _{i=1}^{K}\;\frac{W_{i}(t)}{R_{i}(\varvec{q}(t))}\ -\ \varvec{1}(q_{v}(t)>0)\;\cdot \;C_{v}\,, \end{aligned}$$

(21)

$C_v$ is transmission capacity of the router $v$. A router allows reception of traffic from $K$ TCP flows ($K \leqslant N$). Each flow $i (i = 1, ..., N)$ is determined by time varying congestion window size $W_i$, measured in packets and constant propagation delay $Tp_i$ throughout flow route. Total packet delay for flow $i$ (Round Trip Time) consists of queue delay and propagation delay.

$$\begin{aligned} R_{i}(\varvec{q}(t))\ =\sum _{j=1}^{M} \frac{q_{j}(t)}{C_{j}}\;+\; Tp _{i}\,. \end{aligned}$$

(22)

Numerical example 2. The topology of the considered network is the same as in Example 1 and generated by aSHIIP. The flows, propagation times, and buffer sizes at routers were also generated randomly. Table 2 illustrates the network parameters: $B$ - maximum buffer capacity; $C$ - service intensity; $Q_0$ - initial queue length; $\gamma$, $t_{min}$, $t_{max}$, $p_{max}$ - weight, thresholds and maximum probability for RED algorithm. On the whole structure, we ran our algorithm for selecting the pair of border routers as a flow endpoints and searched for the shortest paths from the sender to the receiver using the Dijkstra algorithm. Table 3 shows the flow parameters: $W_0$ - starting window size; $Tp$ - total propagation delay that is the sum of the link delays on the route.

Table 2. Router parameters

Table 3. Flow parameters

Few results are displayed, e.g. the RTT as a function of time for flow classes, Fig. 5. The value of RTT specifies the time needed to propagate an information through the network after which a sender may react on losses. The first overload occurs roughly at $t= 300$ time units (t.u.) and the RTT time of classes 3–5 at that moment ranges between [260, 325], therefore the expected moment when the sender reduces the transmitted traffic is after about 300 t.u. It is visible in Fig. 6 – the window sizes of class 3–5 are reduced at a time close to $t = 600$ t.u. For other classes the losses are so small that the continuous increase of window sizes is observed.

Fig. 5.

The RTT time $R_i$ in each flow class

Fig. 6.

The congestion window sizes $W_i$ in each flow class

The reduction of window sizes contributed to an immediate decrease of queue length of congested nodes (Fig. 7). The queue in 17th and 18th node started to empty after 600th time unit because of exceeding the RED maximum threshold by average queue around 300th t.u. and rejecting new packets since then. However, the queues did not reach the maximum buffer sizes that were set respectively on 18 and 17 packets.

Fig. 7.

The queue lengths $Q_i$ in each node

Figure 8 displays the throughputs of flow classes. Each class has different characteristic, however the classes with a shared overloaded part of the route had similar behaviour. The flows that traversed through shared non-congested network fragments have different throughputs – as it is seen for class 1 and 2.

Fig. 8.

The throughputs $T_i$ in each flow class

5 Conclusions

We believe that diffusion and fluid approximations are useful approaches that are complementary to Markov models. The size and complexity of models which may be analysed by diffusion and fluid flow approximations are much larger than in case of traditional Markovian models. We have developed our own tools for the both methods and we are testing their possibilities. They are able to treat very large (up to millions of nodes) networks giving a software test bed to consider modifications of protocols or the choice of network topologies. The models based on Markov chains are still essential in performance evaluation and supporting the design of new communication protocols, mechanisms for regulation of the intensity of Internet transmissions and mechanisms to ensure the quality of transmission services. Their principal constraint is the number of states growing very rapidly with the complexity of an object being modelled; as each state of the Markov chain corresponds to one state of the system, it is necessary to construct and solve very large systems of equations linking the states probabilities. The existing solvers as e.g. XMARCA [28], PEPS [20], or PRISM [21] consider only steady state Markov chains.

We are developing our own Markovian package Olymp [19]. It is a library for generating transition matrices of continuous time Markov chains, and solve the resulting model. Olymp uses Java language to define network nodes and their interactions - that gives a lot of flexibility in defining a network structure and functions.

At the moment we are able to generate and solve Markov chains of the 150 million of states. The main method of solution is one of projection methods based on Krylov subspace with Arnoldi process, e.g. [23, 26, 28]. We plan to increase the size of tractable Markov chains by several orders through the use of a GPU-CPU (graphical processing unit) and a better design of computational algorithms for parallel computing and optimization of memory usage, [17].

An alternative to analytical models is discrete event simulation – also used here to evaluate diffusion approximation results. We have developed an extension of OMNET++ (a popular simulation tool written in C++, [18]) allowing simulation of transient state models. In this case a simulation run should be repeated a sufficient number of times (e.g. 500 thousands in our examples) and the results for a fixed time should be averaged. That makes transient simulation models time-consuming.