Performance Analysis of Wavelength Division Multiplexing Asynchronous Internet Router Employing Space Priority Mechanism under Self-Similar Traffic Input—Multi-Server Queueing System with Markovian Input and Erlang-k Services ()
1. Introduction
It is evident from seminal studies that Internet protocol (IP) traffic of both Ethernet traffic and wide area network (WAN) traffic exhibits self-similarity [1] - [3] . Markov modulated Poisson process (MMPP) is employed to emulate the self-similar traffic over the different time scales [4] - [6] . Naturally, high demand in Internet traffic leads to congestion problems. Congestion problems can be dealt with some space priority mechanisms. Buffer Access Control (BAC) mechanism is one of the space priority mechanisms. There are several strategies to implement this mechanism and one of such strategies is partial buffer sharing (PBS) mechanism. In this scheme [7] - [11] , there is a limit (or threshold) in the buffer, and the part of buffer on or below the limit is shared by all arriving packets. When the buffer occupancy is above the limit, the arriving low priority packets will be dropped, and only high priority packets will be allowed. High priority packets will be lost only when buffer is full. If the limit is relatively low, then more low priority packets will be lost. If the limit is relatively high, then more high priority packets will be lost. The limit setting induces two time periods, namely, critical and non-critical periods. The critical period is the time period during which buffer occupancy of the queueing system is on or above limit level and the non-critical period is the time period during which buffer occupancy is below the limit level. This way, there is a trade-off relation between limit setting and packet loss. Hence, optimum level of limit is very important in dimensioning the network nodes such as switches or routers. Priority queue models are briefly discussed below. In paper [12] , the queueing analysis of infinite buffer priority system with MMPP input is investigated with an assumption that the delay sensitive cells and non-delay sensitive cells arrive at two separate queues. This scheme is not realistic as the buffers consist of limited number of fiber delay lines (FDLs) with fixed granularity. The loss behaviour of finite buffer space priority queues with discrete batch Markovian arrival process (D-BMAP) has been analyzed [7] which is not the case, since the router under consideration is handling self-similar traffic which is modelled by continuous-time Markov process.
Another issue of Internet traffic is to provide Quality of Service (QoS). Internet router with wavelength division multiplexing (WDM) technology is promising one to guarantee QoS. In WDM router, there are N input fiber lines, N output fiber lines, and each fiber line has C wavelength channels and a wavelength converter pool of size s,
dedicated to each output fiber line. Hence, each output port of the router is to be modelled as multi-server queueing system [13] [14] [11] . In general, there are two types of networks: synchronous (slotted) and asynchronous (unslotted) [15] . In the case of first one, all the packets are of constant size [7] [13] [9] [12] . In asynchronous networks, all the packets have variable lengths [8] [14] [16] [11] . Since IP packets are, in general, variable in length, the router is required to possess the ability to router the variable length packets. Therefore, performance analysis of the router by means of MMPP/D/1/C queueing system wherein service time (packet length) is deterministic may not be appropriate [17] . Router with variable length packet traffic is modelled as MMPP/M/1/C queueing system wherein service time is exponential distribution [18] - [20] . In the papers [8] [13] [14] [11] , the router is modelled as either single-server or multi-server priority based queueing system. However, the service times (packet lengths) distribution is assumed to be deterministic or exponential. It is appropriate that service time (packet length) follow more general distribution, namely, Erlang-k than the said distribution. There are many applications in a Broadband integrated services digital network (B-ISDN) communication services are to provide differentiated services (DiffServ) and QoS. To the best of our knowledge, priority based WDM router with self- similar traffic input is not yet modelled by MMPP/Ek/s/C queueing system with PBS mechanism.
The rest of the paper is organized as follows. In section 2, WDM asynchronous router―multi-server queueing model MMPP/Ek/s/C employing PBS mechanism with Erlang-k service times is discussed. Computational complexity is briefed in section 3. In section 4, numerical results are presented graphically. Finally, conclusion is given in section 5.
2. WDM Asynchronous Router―Multi-Server Queueing Model MMPP/Ek/s/C Employing Partial Buffer Sharing (PBS) Mechanism with Erlang-k Service Times
We consider the WDM asynchronous
router with each output fiber line consisting of C wavelength channels and a wavelength converter pool of size s. Buffer depth then is
. Such a router with self-similar traffic input can be modelled as MMPP/Ek/s/C queueing system. The operation and multi-server queueing model of the router employing PBS mechanism is shown in Figure 1. For the simplicity, two priority traffics are considered. The threshold is set at the level
, where b is a positive integer. The low priority packets can only access first
buffer spaces and the high priority packets are for the whole buffer space. The threshold setting induces two time periods, namely, non-critical period and critical period [7] [8] . Non-critical period is the time period during which buffer occupancy is below the threshold level and critical period is the time period during which buffer occupancy is on or above threshold. Each priority traffic is self-similar and is modelled by MMPP process [6] . Assume that high priority (class 1) packets and low priority (class 2) packets arrive at the system according to MMPPs of the states
and
, respectively, and are governed by the matrices
and
, respectively. Let the service time is generally and identically distributed with distribution function
. Let
be the matrices whose
element is the probability that given departure of class p at time 0, there is at least one packet left in the system and the
![]()
Figure 1. Operation and multi-server queueing model of a specific output port of the router employing partial buffer sharing mechanism with two different priority traffic input and Erlang-k service times.
process is in state i, the next departure of class p occurs no later than time t with the process in state j, during the service time there are m packets. We consider the Markov chain
at the departure epochs of the queueing system on the state space
where
denotes the buffer occupancy and
denotes the phase of superposed MMPP. For convenience, a queueing system is said to be at level d, if buffer occupancy is equal to d (excluding the ones in service). We ignore the time spent in a state and consider only the number of packets arrived during the sojourn time. Therefore, pertinent system is embedded Markov chain and has the following irreducible transition probability matrix P (with the dimension
):
, (1)
where
, (2)
. (3)
In Equations (2) and (3), the elements of row and column outside the matrices
and
are state spaces of the Markov chain and the elements of first (
) rows are identical.
and
are the matrices of high priority and low priority packets, respectively. The overall input traffic is the superposition of high priority and low priority packets, which is also an MMPP with
, and ![]()
, and
.
Sojourn time is ignores the matrices of counting functions become independent of time t. The matrices
satisfies the following equation [18] - [20] ,
. (4)
If the service time distribution
is Erlang with k phases in series of service and mean service time
, where
is the mean service rate. We have dropped the superscript “p” for convenience as the procedure holds good for both high priority and low priority packets. The matrices of counting function
’s can be computed following the procedure [18] - [21] . Then Equation (4) reduces to
(5)
where I is the unit matrix of appropriate dimension. For
in Equation (5), we have
. (6)
For
, let
be the coefficient of
in
, nth term of the series on right hand side of Equation (5). Then we have
,
,
,
,
...……,
, if
, and
![]()
Now, multiply on both sides of above equation by
, we obtain
![]()
In above equation, equating the coefficients of like powers of z, we obtain,
,
,
,
,
,
.
Equating the coefficients of
in the Equation (5), we get
. (7)
The fundamental arrival rate of class p packets is
, where
is the steady state probability vector of
. Then traffic intensity is
. Let
, where
, for
, when
is the conditional probability that there are v packets in the system given that embedded Markov chain is in the
state. Therefore, we have
, where e is the column vector consisting of all 1 [21] - [24] . Then, in the steady state, high priority packet loss probability
and low priority packet loss probability
, respectively, are derived as follows [13] [7] . Let
denote the number of high priority packets lost due to the fact that buffer is full. Then the expected value of
is
and is obtained by considering the last column of the
block transition probability matrix P as that column consists of matrices containing conditional probabilities that the buffer is full. Then high priority packet loss probability
is given by
(8)
where
is the number of packet arrivals during the mean service time. Let
denote the number of low priority packets lost due to the fact that buffer occupancy exceeds the threshold. Then expected value of
is
and is obtained by considering the last
columns of the
block transition probability matrix P as these columns consists of matrices containing conditional probabilities that the buffer occupancy is greater than or equal to threshold. The low priority packet loss probability
is given by
(9)
In the paper [7] , the alternate methods to compute
and
are proposed, but the input process is assumed to be discrete batch Markovian arrival process (D-BMAP) and the pertinent queueing system is of single-server. On the same lines we have extended it to multi-server queueing system with continuous input process. In view of threshold setting we decompose the state space U into two subsets:
, (10)
and
(11)
This partition of U makes the transition probability matrix P decomposed as follows:
. (12)
The sub-matrices
,
,
, and
are the left upper part, right upper part, left lower part, and right lower part of the matrix P with dimensions of
,
,
and
, respectively. These sub-matrices govern the transitions from
into itself, from
into
, from
into
and from
into itself, respectively. Next, we derive the mean length of non-critical and critical periods that occur alternately. For non-critical period, the transition probability matrix (TPM) of the absorbing Markov chain that has transient states
and absorbing state
is given by
. (13)
Similarly, in the case of critical period, the TPM of the absorbing Markov chain that has transient states
and absorbing states
is given by
, (14)
where
is the last
columns of the matrix
. This is followed from the fact that for a critical period it suffices to attain the buffer level
rather than all other below levels which is the starting point of non-critical period of each cycle except the first one. The absorbing probability vectors
and
of the Markovian chain
and
described in the paper [7] are given by,
(15)
and
, (16)
where
be the sub-matrix of
which consists of the last
rows in
. That is, absorbing probability vectors
and
are steady state probability vectors of
and
, respectively. The absorbing probability vectors are given by
and
, respectively, where V is the
stochastic matrix
in Equation (15) in which the last column is replaced by the column vector
and W is the
stochastic matrix
in Equation (16) in which the last column is replaced by the column vector
. Then the average length of non-critical and critical periods are
and
, respectively, given by
, (17)
and
. (18)
The average total number of high priority packets lost during a critical period is
,
. (19)
The average total number of low priority packets lost during a critical period is
,
, (20)
where
and
are the high priority packet loss during a critical period and
and
are the low priority packet loss during a critical period, and are given below, for
,
, (21)
, (22)
, (23)
and
. (24)
The high priority packet loss probability
and low priority packet loss probability
are
, (25)
and
. (26)
3. Computational Complexity
In this section, first we compute the computational complexity of the long-term performance measures, namely, high priority packet loss probability
and low priority packet loss probability
through the Equations (8)-(9). Next, we compute the short-term performance measures, namely, the mean length of non-critical periods
and critical periods
, and the long-term performance measures, namely, high priority packet loss probability
and low priority packet loss probability
through the Equations (15)-(26) and analyze their computational complexity [7] .
In order to find the computational complexity of long-term
and
through the Equations ((8)-(9)), the transition probability matrix P in Equation (1) is not of the canonical
type, using the Schur-Banachiewicz inversion formula, to compute the steady-state probability vector y of P (with dimension
) and we have
. Let
, where
is the matrix P in which the last column is replaced by the column vector
. Let the permutation matrix M with dimension
,
, (27)
where 0 and I are the zero and the identity matrices of dimension
. Now, multiplying M to
, we have
, (say). (28)
The sub-matrices E, F, G, and H are of the dimensions
,
,
, and
, respectively. Then the steady state probability vector y is the last row of the matrix,
. (29)
By the Schur-Banachiewicz inversion formula, where
is the Schur complement of E in
with dimension
. But E is not a Toeplitz matrix and can be further decomposed as
, (30)
where
and
are upper-triangular and Toeplitz matrices of dimensions
and
, respectively. Thus
. (31)
The sub-matrices
and
are also upper-triangular and Toeplitz matrices and the existence of
and
is due to the existence of the inverses of
,
and
. The complexity to obtain
is of the order
due to the matrix multiplication
, and the complexity to obtain the Schur complement X and the matrix R in (29) is of the order
. Thus the overall complexity to compute
and
by Equations ((8)-(9)) is of the order
. Note that as
,
becomes
, a complexity equal to the inversion of
by a direct Gaussian elimination.
Now, we place the algorithmic steps needed for computing the performance measures
,
,
, and
and analyze their computational complexity [7] .
Step 1. Compute
(the last (
) rows of
) and
.
Step 2. Compute
and
by using
and
respectively, where V is the
stochastic matrix
in Equation (15) in which the last column is replaced by the column vector
and W is the
stochastic matrix
in Equation (16) in which the last column is replaced by the column vector
.
Step 3. Compute
and
.
Step 4. Compute
,
,
and
.
Step 5. Compute
and
by using Equations ((17) and (18)), respectively.
Step 6. Compute
and
by Equations ((25) and (26)), respectively.
The computational complexity of the steps 5-6 in the above algorithm is of the order
due to the products of several pairs of row and column vectors. The computational complexity of the steps 3-4 is of the order
due to the size of the matrix
. The computational complexity of the 2nd step is of the order
due to the inversion of the
matrix
, and is also of the order
due to the multiplication of the two matrices
and
and the multiplication of the two matrices
and
.
We next show that the computational complexity of the first step is of the order
by subject to the existence of the inverses of
,
and
. Both
and
are not in canonical
type. Therefore, we will apply the Schur-Banachiewicz inversion formula for block matrices to obtain inverses. Now, multiplying M to
, we have
, (say). (32)
The sub-matrices
,
,
, and
are of the dimensions
,
,
, and
, respectively. The inverse of
is
and
is the last
rows of
and we have
, (33)
where
is the Schur complement of the matrix
in
, with dimension
. Since
is upper-triangular Toeplitz block matrix, the inverse is also upper-triangular Toeplitz block matrix. Thus the computation complexity of obtaining
in (33) is of the order
due to the computation of the inverse of
and the multiplication of the matrices
and
. Similarly, we have
![]()
, (say). (34)
The sub-matrices
,
,
, and
are of the dimensions
,
,
, and
, respectively. We have
, (35)
where
is the Schur complement of the matrix
in
, with dimension
. Since
is upper-triangular Toeplitz block matrix, the inverse is also upper-triangular Toeplitz block matrix. The computation complexity of obtaining the inverse of
in (35) is of the order
due to the multiplication of the matrices
and
. In conclusion, the overall complexity of the algorithm is above for the computation of the performance measures
,
,
, and
is of the order
.
4. Numerical Results
Using the Equations (15)-(26), the steady state packet loss probabilities and mean length of non-critical and critical periods are computed [7] . The generalized variance based Markovian fitting method proposed in [6] is employed to emulate the self-similar traffic for both priority packet traffics. The mean arrival rate (
) and variance (
) of the self-similar traffic is set to be 1 and 0.6, respectively [6] , the interested time-scale range to emulate self-similarity is over
[2] [3] . In the papers [5] [6] it is shown that in order to emulate self-similar traffic well, the minimum number of states of the resultant MMPPs must be
. That is, both
and
must be
. So each class is here characterized by
matrices. Such a high dimensional MMPP for both high priority and low priority traffic results in computational complexity. In order to reduce the computational complexity, we use approximate model [9] , which is based on the papers [25] [26] . The resultant 16-state MMPP of low priority packets is approximated by a 2-state Markovian arrival process (MAP). By applying this approximated model, the computational complexity is reduced by
times [16] . The number of servers (s) is set to be 3, the number of phases in series of each server (k) is set to be 5, and the system capacity (C) is set to be 20, buffer depth of the router then is 17. We consider two different self-similar traffic corresponding to the Hurst parameter values
and
, and the results are presented in Figures 2-8. Figure 2, depict the high priority packet loss probability decrease and the low priority packet loss probability increase as threshold (b) increases. In order to find out the optimal level of the threshold, we illustrate a plot of the high priority packet loss probability against the low priority packet loss probability ones at various b in Figure 3. We could find out that the optimal level of the threshold is the one located nearest to the left lower corner
![]()
Figure 2. Packet loss probabilities against threshold when C = 20, s = 3, k = 5, rho = 0.85, H = 0.7 and H = 0.8.
![]()
Figure 3. High priority packet loss probability vs low priority packet loss probability when C = 20, s = 3, k = 5, rho = 0.85, H = 0.7 and H = 0.8.
![]()
Figure 4. Packet loss probabilities against traffic intensity when b = 7, C = 20, s = 3, k = 5, H = 0.7 and H = 0.8.
![]()
Figure 5. Packet loss probabilities against buffer capacity when d = 7, s = 3, k = 5, rho = 0.85, H = 0.7 and H = 0.8.
of the plot, which is around
. Figure 4 & Figure 5 depict the variation of packet loss probability against traffic intensity (rho) and buffer capacity, respectively. It is clear that packet loss probability increase as traffic intensity increases (Figure 4). We observe that of high priority and low priority packet loss probabilities both decrease as buffer capacity increases (Figure 5). From Figure 6, we observe that the mean lengths of non-critical periods (ELNC) and critical periods (ELC) are decreases as threshold increases. Figure 7 & Figure 8 depict the variation of mean lengths at the optimum level of threshold against traffic intensity and buffer capacity, respectively. Figure 7 illustrates the mean lengths of non-critical periods decrease and critical periods increase
![]()
Figure 6. Mean lengths of non-critical and critical periods against threshold when C = 20, s = 3, k = 5, rho = 0.85, H = 0.7 and H = 0.8.
![]()
Figure 7. Mean lengths of non-critical and critical periods against traffic intensity when b = 7, C = 20, s = 3, k = 5, H = 0.7 and H = 0.8.
![]()
Figure 8. Mean lengths of non-critical and critical periods against buffer capacity when b = 7, rho = 0.85, s = 3, k = 5, H = 0.7 and H = 0.8.
as traffic intensity increases. Figure 8 depict the mean lengths of non-critical and critical periods both increase as buffer capacity increases.
5. Conclusion
In this paper, we have investigated the performance of asynchronous router employing PBS mechanism to provide differentiated services under Markovian modelled self-similar traffic input. To reduce the computational complexity, the original high dimensional MMPP of the low priority packets is approximated by 2-state MAP. The long-term performance measures, namely, the steady state high priority and low priority packet loss probabilities, and the short-term performance measures, namely, average length of non-critical and critical periods, are computed and presented graphically. With this analysis, we can locate the optimal limit (threshold) position of buffer to obtain the greatest performance.