This thesis examines, both analytically and through numerical experiments, the performance of queuing models with a 'working holiday' policy that occurs naturally in communication systems, particularly in wavelength division multiplexed networks (WDM). A working holiday model with different customer priority classes is studied because priority-based traffic can increase network performance and ensure quality of service (QoS).
Introduction
Queueing theory
1.1. QUEUEING THEORY
The next MAP/G/1/K queue analysis with limited service discipline is performed by Gupta et al. Finch [62] analyzed the GI/M/1+D queue with continuous constraints on the queuing time and found the distribution of the queuing time.
1.2. QUEUES IN COMMUNICATION SYSTEMS
Queues in communication systems
The probability of packet loss depends on the type of network, as this determines the number of paths that can be established simultaneously to reduce the amount of buffer occupancy. In OBS, incoming traffic from clients at the edge of the network is aggregated and further transmitted through WDM links [131, 171].
1.3. WDM NETWORKS AND WORKING VACATION QUEUES
WDM networks and working vacation queues
They obtained the transformation formulas for the distribution of the number of customers in the system and the steady state residence time. Baba [22] considered the GI/M/1/WV system with a general independent arrival process where the distribution of vacation duration and duty times is exponential.
Phase-type distribution
Let Z = inf{t≥0, Xt =m+ 1} be the random variable indicating the time until absorption in state m + 1 of the Markov chain χ. This means that the renewal times of the new Markov chain with generator Q∗ follow the PH distribution.
1.5. MARKOVIAN ARRIVAL PROCESS
Markovian arrival process
The arrival rate is given by λ=πD11. The MAP representation of PH renewal process is D0 =T andD1 =T0α. A two-state MMBP arrival process is characterized by the transition probability matrix Pb and the arrival rate matrix Λ defined as.
Quasi-Birth-Death process
A noncontinuous time-irreducible QBD process is positively recurrent if and only if there is a minimal nonnegative solution R of the matrix equation. The matrix R is also interpreted as recording the rate of residence time in states l(n+ 1) per unit of local time l(n).
1.7. SOLUTION METHODS OF QUEUEING MODELS
Solution methods of queueing models
- Transform methods
- Matrix-Geometric Method
We can determine interesting quantities such as the mean and variance of the random variable from the PGF itself. For a discrete random variable f∗(s) = GX(e−s), i.e., the LST of a random variable differs from its PGF only by replacing z with e−s.
1.8. OUTLINE OF THE THESIS
Outline of the thesis
In this chapter, we provide a detailed analysis of the discrete-time WV model and also outline its continuous-time analog. As for the traffic model, here we have chosen the MAP process for the following reasons: MAP is one of the most powerful traffic models in terms of its ability to mimic complex statistical properties of the network traffic, e.g. the long-range dependent behavior [42].
The discrete-time MAP/PH/1/WV model
- Stability condition
- The rate matrix R
- Stationary distribution
A10 is the probability of the event that the system remains in the non-holiday period and at the same level. A03 gives the probability of the event that the system remains in WV but changes its level from n ton+ 1. A20 is the probability of the event that the system remains in non-holiday and changes its level franton−1.
2.2. WAITING TIME DISTRIBUTION
Waiting time distribution
The second term gives the probability that an arriving customer finds the system empty due to the completion of the service of the only customer in WV. The first term gives the probability of the event that the system is not on holiday with i customers while an incoming customer enters and the ongoing service continues. The second term gives the probability of a service termination event when the system has i+ 1 customers in a non-holiday period such that an incoming customer finds i customers.
2.3. REGULAR BUSY PERIOD AND BUSY CYCLE
Regular busy period and busy cycle
Equation (2.11) is the probability of the event that the service of j customers lasts i unit of time. Or a service ends within the first unit of time and the service of the rest of customers j−1 duration−1 time unit;. The second term in the RHS is the probability that the customers' service time lasts i−l time units.
2.4. NUMERICAL EXAMPLES
Numerical examples
- Comparison of MMBP and DPH arrival models
- Autocorrelation and DMAP/Geo/1/WV(Geo) model
The change in the value of c2 also provides a difference in the queue lengths for the MMBP and the corresponding PH model. We have seen that for c2=1 the average queue lengths of the MMBP model and the PH model come very close in Figure 2.5. We can also have a situation like in Figure 2.7 where the queue lengths of the MMBP model become smaller than those of the PH model.
The continuous-time MAP/PH/1/WV model
A11 = D0 ⊕S because, the system remains in non-rest without any service completion and no arrival, but only internal phase transitions. The stationary vector xi is the joint probability of the number of customers, the arrival phase, the holiday duration phase, the service phase during the non-holiday period, or the service phase during the WV period, within the customers in the system. Let yi be the marginal probability of finding i customers in the system at time t, then.
3.1. MODEL DESCRIPTION
Model description
- Stationary distribution at arbitrary epochs
- Stationary distribution at pre-arrival epochs
The system remains in non-holiday with an internal phase change without any service completion. The vector xi is the joint probability of the number of customers, arrival phase, holiday time phase, service phase during non-holiday or service phase during WV period, with customers in the system. Let zi be the stationary probability vector of finding i customers in the system by an arriving customer and, for 1≤i≤K, we get.
3.2. PERFORMANCE MEASURES
Performance measures
MMPP arrival process model: A special case
To get a better insight into this model, we have taken the special case, the MMPP/M/1/K model with exponential WV durations and analyzed the system performance using some numerical examples. ½ 0 if the system in WV period and 1 if the system in non-holiday period, Jt = arrival phase. The first set says that when there are no cells in the system, the system will always be on vacation.
3.4. NUMERICAL EXAMPLES
Numerical examples
- Effect of buffer size
- Effect of burstiness
- Effect of correlation
Typically, the characteristics of the traffic source are given - the mean λ1 and the squared coefficient of variationc2 of the distribution between arrivals. When the buffer size is large, it is intuitive that the probability of system loss approaches zero. To see the effect on the average queue length for different MMPP arrival processes, we plotted the average queue length against holiday service level µv for three different arrival rates in Figure 3.4.
4.1. MODEL DESCRIPTION
Model description
This impatient timer X follows an Exp(ξ) distribution and is independent of the number of customers in the queue at that time. If no server returns to its non-holiday period when X expires, the client leaves the system and never returns. Otherwise, if either server returns from its vacation before time X expires, the client stops the timer and remains in the system until its service is complete.
4.2. STATIONARY DISTRIBUTION
Stationary distribution
Artalejo [13] compared the finite truncation method with the generalized truncation by studying the stationary distribution of a multi-server model. The dominant process is constructed in the same state-space of the process under study. Chakravarthy [37] analyzed multi-server retry queuing using this method and provided efficient algorithms to calculate various steady-state performances.
4.3. THE FINITE TRUNCATION METHOD
The finite truncation method
As the dimensions of the matrices increase in each iteration, the computations to compute the above matrices involve the multiplication and inversion of increasingly large matrices. Taking advantage of the matrix structure in the above equations, we notice that the sparse blocks B01(K−1) and C0(K−1) simplify the calculations. The complete method of computing the stationary distribution using the finite-truncation method is summarized in the following algorithm.
4.4. PERFORMANCE MEASURES
Performance measures
4.5. NUMERICAL EXAMPLES
Numerical examples
- Effect on cut-off value K f
- Effect on mean queue length
A hyperexponential model always has the highest average queue length compared to the corresponding Erlang and exponential models, regardless of the number of servers. When the impatient frequency is small, the average queue length of the Erlang model becomes the minimum. But the impatient frequency does not have much effect on queue lengths when the arrival process is Erlang, whereas the average queue length for hyperexponential model decreases significantly with the increase of impatient frequency.
4.5. NUMERICAL EXAMPLES highly impatient customers ³
Effect on blocking probability
Average number of servers busy in non-vacation
Average customer loss
As discussed in the previous chapter, multiple services are provided by an efficient network for better Quality of Service (QoS) support. In a packet-switched computer network via WDM technology, priority-based wavelength allocation is a necessary task. Dutta and Chaubey [55] studied the prioritization of incoming call connection requests for WDM optical networks by modeling the system.
5.1. MODEL DESCRIPTION
Model description
Either the duration of residual leave, from the arrival epoch, is longer than the service time of the customer in question, i.e. V > U, or the remaining holiday is no longer than the service time in the WV period, V ≤U. For the case V > U, let ci(k), i= 1.2, be the probability of arrival of class-1 customers during the service of a class customer in the WV period.
5.2. LENGTH OF BUSY PERIOD
Length of busy period
5.3. BUSY CYCLE
Busy cycle
Therefore, the busy cycle can be seen as a busy period initiated by exceptional service to the first customer. The busy cycle LST of the M/PH/1/WV model with outstanding service time for the first customer is given by. Let Θc be the length of a loaded period with exceptional service time X0 for the first customer, then, using equation (5.24), we have.
5.4. QUEUE LENGTH
Queue length
For Xn = 0 with class 2 customers in the system and Xn+1 =k ≥0, we have that while servicing a class 2 customer who is not on vacation, class 1 customers arrive. Let Np(z) be the PGF of the number of class 1 customers in to the system just before Class 1 customer service begins. The average number of Class 1 customers present in the system during the initial period of Class 1 customer service is.
5.5. WAITING TIME
Waiting time
5.6. RESPONSE TIME
Response time
5.7. NUMERICAL EXAMPLES
Numerical examples
Therefore, the waiting times of class-1 customers are reduced up to 40% by having WV model instead of a classic holiday one. In Figure 5.5 we compare the waiting times of class-1 customers for three different service distributions—. Hyperexponential service time distribution appears to significantly increase the waiting times of class-1 customers.
6.1. MODEL DESCRIPTION
Model description
The server receives a WV once the system (both orbit and server) is empty, i.e. if all clients have been served, no new clients arrive and the orbit is empty. If no client appears in the system in the end-of-holiday epoch, the server restarts for another WV. This continues until the server returns from a break to find at least one client in the system.
6.2. STATIONARY DISTRIBUTION
Stationary distribution
S0(t,0) is the probability of the event that the system is in WV with an empty orbit at service completion epoch t. Sn(t,0) is the probability of the event that the system is in WV and orbits exactly n clients at the time of service termination. W0(t,0) is the probability of the event that the system is not on holiday with an empty orbit at service completion epoch t.
6.3. SYSTEM EFFICIENCY
System efficiency
- The availability of the server
- The blocking probability
- The distribution of number of customers in the orbit
- The distribution of number of customers in the system
If N0(t) is the random variable for the number of customers in the circuit at time t, with stationary probability distribution given as un=P{N0 =n}. Differentiating the above equation with respect to z and evaluating it at z = 1 gives the average number of customers in circuit as. Let N(t) be a random variable of the number of customers in the circuit including the one in service at time t with stationary probability distribution qn = P{N =n}.
6.4. STOCHASTIC DECOMPOSITION
Stochastic decomposition
6.5. NUMERICAL RESULTS
Numerical results
For θ= 8, the system availability remains almost stable in terms of the retry rates, as we can see in the graph (Figure 6.3). So the retry rate affects system availability if the holiday duration is less than 8 ie. for shorter durations of holidays. To see the effect of service distribution on the model, in figure 6.7 we have plotted the system availability for an exponentially distributed service time distribution and for an Erlang-2 distributed service times with the same mean.
7.1. MULTIPLE WORKING VACATION MODEL
Multiple working vacation model
- Stationary distribution
- Performance measures
- Stochastic decomposition in MWV model
To have complete information about the system at any time, the number of clients in the system at that time and the holiday status of the server are sufficient. Thus, to describe the state of the system, we define a continuous-time Markov chain, ∆ = {(Nt, Jt), t ≥0}, where Nt denotes the total number of customers in the system and Jt denotes the holiday status of the server, i.e. Another important performance measure is the total wait time of a customer completing their service before leaving the system.
