Perfect Sampling of Phase-Type Servers Using Bounding Envelopes (Queueing Theory) (Analytical and Stochastic Modeling) Part 2

Coupling of Phase-Type Systems Envelopes

This section is dedicated to the analysis of the coupling time of the envelopes for networks of phase type servers The main features can actually be seen in the simplest network: two queues in tandem with a phase-type server on the first queue. This case is considered first. The general case is considered in the second subsection.

The Tandem Case

Theorem 3. The envelopes of any phase-type tandem couple almost surely. Proof. To prove that the upper and lower envelopes meet almost surely, one needs to show that there exists at least one sequence of events e … en, called a synchronizing word, such thatfor all initial couple

We denote by a an arrival in queue q, by d an end of service in queue q’ and by tij a phase transition from phase i to phase j with or without a service. Letbe the phase-type server graph, with E the set of transitions.

Letbe the set of re-numbered phases according to <p, that isThen, the following event sequence is a synchronizing word:

is a phase such that where

is a phase such that

In fact, it is clear that, by a sequence of C arrivals in the input queue and C’ services in the output queue, any couple (M, m) will reach a state where the input queue is full and the output queue is empty.

In the sequence of phase transitionseach transition tiji may either increase mv by one or have no effect on mv. For eachmay also increase taking the valueor stay unchanged. Once Mv would reach phase g, it will never change anymore and mv will also join this state by the remaining events. So, whilemay couple before reaching phase g, coupling will be done in this phase, in the worst case. Sequences of events ad has been added to compensate the effect of possible services associated to transitions tij.

To prove that such synchronizing word exists, we have to show that the event sequenceis possible. It relies on the existence of a phase transition tij, within all phase i except in the maximal phase g. This is true by construction of the orderbuilt on the covering in-tree with the maximum as root. Indeed, each phase i is connected by a forward transition to a greater phase, whatever the choseen linear extension. A suitable order can always be constructed if G is strongly connected, and a Phase-type server graph is strongly connected by definition.

The previous discussion concerns the Multiple Rest State (MRS) model. If the Single Rest State (SRS) model was used instead, then the envelopes would not be as efficient. Indeed, letdenote the envelopes of the SRS model after the occurrence of eventswhile are the envelopes of the MRS model, as described earlier.

It is direct to show by induction that the sets all possible states (with positive queue size) inside the envelopes satisfy

for all n. This means that the computations of the envelopes is not as tight as in the MRS case.

This phenomenon is particularly accute when m is the empty set (when mq = 0) and when the phases are equal in the MRS case. In that case, mS =

while. In the SRS case, one can show that the envelopes will eventually couple, as in the MRS case. However, coupling will be much longer than in the MRS case. In particular, if the eventdoes not exist (i.e. a service event in the minimal phase according tothen the envelopes for SRS cannot meet in state (0,.) so that coupling will be exponentially slower than in the MRS case for lightly loaded queues, making the envelope method inapplicable in practice for the SRS model. This shows the importance of the model construction for simulation purposes. Here, both SRS and MRS models have the same stochastic behavior, however their simulations by envelopes have widely different efficiencies.

Extension to Networks of Queues

If phase-type servers are connected by an arbitrary network, the approach presented in the previous section can be extended in a rather straightforward manner.

Let us consider a network N of queues Q1,…,Qk, of capacities C1 ,…,Ck each of them with a phase-type server with graphs of phase transitions G1 ,…,Gk. The queues are connected through a routing matrix R of size (0,1,…,k) x (0,1,…,k) where queue Q0 is a dummy queue representing the outside world. The matrix R is such that the network has no sinkand no starvation (for allThe state of system X is included inIn words, Xj is the

number of packets in queue i and yi is the phase of the server of queue i.

The space X is ordered using the same approach as in the two queue case: Each phase-type graph Gi is ordered along a spanning tree and if for all‘ The network N with routing matrix R is a Markov chain on X.

The definition of the envelopes is the same as in the two-queue case: The envelopes are defined on each component xi and on each phase yi using Formulas from (1) to (10).

As for the perfect simulation algorithm, the fact that the coupling time is almost surely finite, with a finite expectation is a direct consequence of the two queue case proved in Theorem 3.

Theorem 4. Under the foregoing assumptions on the network N, The envelope perfect simulation algorithm terminates almost surely and the expected coupling time of the envelopes is finite.

Proof. The proof is based on the construction of a synchronizing sequence for the envelopes. The existence of such a sequence implies the fact that envelopes couple almost surely and that the expected coupling time is finite, using the Lemma of Borel-Cantelli.

Let us call ui the sequence of events that make queue i couple (in isolation). This sequence is given in Theorem 3. Here is the way to construct a global coupling sequence from the sequences ui. Since R has no starvation and no sink, it is possible to extract from R an acyclic connection graph A of N starting in input queues Qi (queues with exogenous arrivals, i.e. such that R0i > 0) and ending in output queues Qj (i.e. such that Rj0 > 0).

The queues are now consider along the topological order induced by A. The input queues Qi are considered first. The sequence of events ui is used so that the components (ui, yi) of both envelopes couple (using the proof of Theorem 3). From that point on, those components will remain coupled. Once the envelopes have coupled in the input queues, we consider one queue following them in A, say Qj. The individual coupling sequence uj is used to couple the envelopes on (xj, yj) by replacing each arrival in Qj by an arrival and a service in one input queue of Qj. By doing this until all queues have been considered, all the components in the envelopes have coupled.

Experimental Results

In this section, we have gathered several experimental results providing evidence of the efficiency of the envelope perfect sampling as well as some insight on the parameters that most influence the simulation time of such systems.

Figure 4 displays the average coupling time of one queue with capacity 20. This is done for several phase-type distributions of service in the queue: exponential service time (Fig. 5(a)), hyper-exponential service time with three phases (Fig. 5(d)), Erlang service with three phases (Fig. 5(b)), cox distribution with three phases (Fig. 5(c)), self designed phase time service as given in the Figure 5(e). For all distributions, the mean service rate is set to 1.

The average is taken over a large number of simulations in order for the confidence interval to be smaller than 5 % on the reported values.

The average coupling time is given as a function of A/(A + /), where A is the arrival rate in the queue and j is the service rate in the queue. The parameters in all 5 cases have been chosen so that j is always equal to 1. We let A vary from 0 to 20 so that x = A/(A + /) ranges from 0 to « 0.95.

When x is small, the first queue is lightly loaded and coupling in the queue happens at point 0 (empty queue) with a very high probability.

When x is around 1/2, then the arrival rate and the service rate are almost the same in the queue so that coupling can happen equally likely with an empty queue or with a full queue. Finally, when x approaches 1, the load gets larger and larger, going to infinity. In this case, coupling happens with a full first queue with high probability.

The first comment that can be made concerning Figure 4 is that the coupling time remains rather low in all cases, never exceeding 3000 time steps which means that sampling time (for 1000 independent samples) is never above one second.

The second comment concerns the qualitative behavior of the coupling time as a function of the load. In all cases, the shape is almost symmetrical w.r.t. 1/2. This can be explained by the fact that empty or occupied seats in the queue play almost identical roles so that full and empty queues behave the same when A and j are exchanged in a single queue.

Fig. 4. Coupling time of EPSA in tandem queues, under several distributions of the service in the first queue, when the input rate A varies

(a) M/M/1 server

(b) Erlangian server with 3 phases

(c) Coxian server with 3 phases

(d) hyper-exponential server with 3 phases

(e) Self-designed server example

Fig. 5. Five phase-type service distributions

The fact that the symmetry is not perfect comes from the difference between Poisson arrivals and phase type services (a way to see this is to notice that coupling time is perfectly symmetrical in the exponential case).

Another easy conclusion is that the coupling time increases sharply around A = j is almost all cases. This can be proved exactly in the exponential case (see [3]). This is due to the fact that when A = / the average drift in the queue is null so that the number of customers in the queue hardly reaches the extreme values C or 0 where coupling takes place.

Let us focus on the lightly loaded case (A/(A + /) close to 0), that is the most usual case in practise. One can see that the coupling time compare in the same way as that the average number of events needed for a customer to leave the system. Since coupling happens at 0 with high probability here, such a correlation is be expected.

The shift to the left of the pick for the hyper-exponential case can be explained by the following fact. Even if reaching a state with a full or with an empty queue are equally likely when A = /, coupling is not symmetrical: Coupling is easier when the queue is full than when the queue is empty because of the phase changes due to arrivals. Therefore, coupling is actually slightly longer when the empty queue is easier to reach (i.e. with A smaller than /). To further illustrate this behavior, Figure 6 displays the coupling time of an hyper-exponential queue with the following service distribution: service has rate 3/2 with probability 1/2 and rate 3/4 with probability 1/2 (so that the overall average service time is equal to 1). This service is modeled with 2 (resp 3 and 4) phases in the figure. The more phases, the more difficult coupling is at state 0 so that the pick further moves to the left.

Fig. 6. Shift of the coupling time pick with a fixed hyper-exponential service, when the number of phases increases

Conclusion

In this paper, we have shown that perfect sampling can be efficient to obtain samples of the stationary distribution of queuing networks with arbitrary phase-type servers.

This efficiency comes from two ingredients: The construction of tight envelopes that can be computed in linear time and a modeling trick that makes the server change phases even when idle without changing the probabilistic law of the system.

On the other hand, the sampling time is very sensitive to the number of phases per service, as shown in the experimental part. One possible direction for future work would be to design new events for phase type service to fight this phenomenon.