Monotone Queuing Networks and Time Parallel Simulation (Queueing Theory) (Analytical and Stochastic Modeling) Part 2

Monotone Networks of Queues

For the sake of readability we begin with a simple result to show how we can prove hv-monotonicity and then we generalise the results with more sophisticated routing strategies and more complex service time distributions. Finally we show with an example that G-networks of queues with positive and negative customers are not hv-monotone. We will use an event representation of the models. Events are associated with transitions. Let ev be an event and let x be a state, we denote by ev(x) the state obtained by application of event ev on state x. It is more convenient that some events do not have any effect (for instance, the end of service event will be a loop when it is applied on an empty queue). Monotonicity property has already be defined for events and their links with stochastic monotonicity are now understood [18].

Definition 4. An event ev is monotone if its probability does not depend on the state and for all states x and y,implies that

Finite Queues Jackson Networks

We consider a network of N queues with exponential service times and Poisson external arrivals. The queues have a finite capacity. Let Bi be the maximal size of queue i, ^ the service rate of its server and Xi the arrival rate of fresh customers. At the service completion at queue i, a customer leaves the network with probability di or joins queue j with probability Pij. As usual 1 for all queue j. When a customer arrives in a full queue, it is rejected. Let be the state of the network. xi will denote the size of queue i. Let B be (B1 ,B2,…, BN) and ei be the null vector except component i which is 1. The transitions of such a system are well known:

— Fresh Arrival at queue i: the rate is Xi and the transition is ev (x) = min (B, x + ei) where the min operator is applied component-wise.

— Departure from queue i to leave the network: the rate is ,idi and the transition is ev(x) = (x — ei)+ where as usual x+ = max(x, 0).

— Internal Routing from queue i to queue j: the rate is /j,iPij and the transition is ev(x) = min(B, (x — ei)+ + ej).

One now has to describe how to order the states and sequences.

— The ordering of the states <a is the product order: x <a y if for all i xi < yi.

— The ouput sequence of the model is the time tn and the state x at that time, n is the event index.

— The ordering of the output sequence is defined as follows:

— The input sequence is a time instant tn and a uniform random value un. Let us first consider a Poisson process with rate A = ^i(^i + t1i) to uniformize the system (we follow Poisson calculus methodology [4]). The time instants are given by this process and u is used to draw the event which is realised at time instant of the simulation. Typically this is done by an inverse transform method or an alias method (see an inverse method in the following).

—–Algorithm Draw from Inverse Transform—-

Note that steps 1 and 2 have to be performed only once. This algorithm is given here for the sake of readability and because it is used in the proof of the following property.

Property 2. The simulation model of a Jackson network with finite capacity is hv-monotone for ^a ordering on the states, ordering of the output sequences.

Proof: by induction on the time instants. Let O1 = M(x, I) and O2 = M(y, I). We prove by induction thatfor all t > 0. Note that as O1(0) = x and Note that as O2(0) = y, the property holds at time 0. Now consider a time instant t where the n-th transition occurs. Assume that holds and remember that the output is the state of the simulation. The input sequence is the same for both simulations even if the states are not equal. It is clear form the pseudo code of the algorithm that the event generated from the input is the same for both simulations because it is not state-dependent. Finally all events are monotone in such a network:

Thereforeand finally by induction□

We now present some numerical results to show the efficiency of the approach. We consider a toy example with three queues. The arrival rate are respectively 2.740, 3.540 and 2.170. The service rates are respectively 6.0, 6.0 and 3.0. The buffer size is 50 for all queues. The routing probabilities are given by matrix

. We assume that we have 100 processes and each part of the simulation generates 1000 events. We report in Figure 3 the time needed to build a consistent path for each LP. In these experiments, all the simulations processes have coupled after run 15 while we obtain an upper bound within 6 runs and a lower bounds after 7 runs. Clearly our approach is much more efficient than the initial one.

Index Based Routing, Poisson Arrivals and Exponential Services

We consider the same set of queues with the same capacity and the same rates but we generalises the routing policy as follows: we attach with the end of service event ev of a customer on queue i, a routing strategy which is defined as a function Rev on the state space and which gives the destination of the customer.

Fig. 3. Building a consistent sample-path vs. process number

We consider routing functions defined by index on queues. An index is a function IjV (xj) for event ev occuring at state xj at each queue j, and the routing function gives as a result the queue which minimises the index:

Intuitively, an index routing sends a customer to the queue with the minimal index value. This formalism supposes that argmin is well defined even when some index values are equal. The event monotonicity of some index based policy has already been used to design a perfect simulation algorithm [24,25]. Furthermore in [25], the following property is given:

Property 3. If the indices used by index routing are non decreasing functions of the states, then the routing strategies are event monotone.

In the following we denote these strategies as monotone index based routings. Many interesting routing strategies are monotone index based. For instance:

— Jump the shortest queue:

— Jump the shortest response time queue:

— Route to the first available queue in an ordered list. Let Li the rank of queue i in the list of priority for the customers. Indices are defined as follows:

— Blocking between i and j: a simplest version of the previous strategy using list of size 2 because queue i can always receive the customer again.

— Jump over blocking: it is a simplified version of the third item.

Property 4. The simulation model of a network with finite capacity queues, monotone index based routing, exponential services and Poisson arrivals is hv-monotone for <a ordering on the states and ordering of the output sequences.

Proof: The proof is similar to the proof of Property 2. We prove the monotonicity by induction on the event number we get the complete comparison of the sample-paths. Again the first step is based on two parts: first we prove that the input sequence provides the same event ev for states x and y and again it is true because the generation of the event does not change with the state description. Second we take into account that the events are monotone. Indeed, the arrivals are event monotone (see the proof of Property 2) and while the routings are event monotone according to Property 3. □

Monotone Phase Type Service Times, Exponential Arrivals

We first define the stochastic monotonicity of matrices and the strong stochastic comparison of distributions to introduce monotone Phase type distribution. We follow Stoyan [22] for both definitions.

Definition 5. Let X and Y be random variables taking values on a totally ordered and finite state space {1, 2,…,n} with p and q as probability distribution vectors. X is said to be less than Y in the strong stochastic sense (denoted by

For instance, one can easily check that:

Definition 6. Let M be a stochastic matrix on a totally ordered state space S, M is stochastically monotone if for all i

Property 5. Let M be a stochastic matrix, letbe the i-th row of M and may be seen as a probability distribution, M is stochastically monotone if

A service type is distributed as a continuous time Phase type if it is the absorbing time of a continuous time Markov chain. We define a monotone Phase type in continuous time as follows:

Definition 7. A continuous time monotone phase type distribution is defined by rate j and an absorbing discrete time Markov chain given by matrix M such that the absorbing state is the last state of the space and matrix M is stochastically monotone. More precisely, the CTMC describing the phase type distribution is P = j(M — Id), where Id is the identity matrix. Let n be the size of matrix M.

Consider now a network of queues with monotone Phase type services. For the sake of simplicity we still consider a routing of customers based on a Markovian routing matrix R but an index based routing is also possible. For the same reason, we assume that the fresh arrivals follow independent Poisson processes with rate Xi. We now need to change the state definition and the orderings. A state x of the network will be a vector of 2N integers: (x1 ,p1,x2,p2, …,xN,pN) where xi is the size of queue i, and pi is the phase of service at that queue. When pi = n, the service ends. Thus (xi,pi) is the state of queue i. It is assumed that if xi = 0, then pi = 1. Furthermore:

— The input sequence is again composed of time instants tn and uniform random values un. Again we uniformize the model with rate which is an upper bound of the total rate of transition in an arbitrary state. The time instants are still given a Poisson process with rate A and un is used to draw an event which is realised at time tn. Now the number of event is larger as we also consider the transitions of the service phases.

— The ouput sequence of the model is time tn and state x at that time.

— The state orderingis defined by

or ((xi = yi) and (pi > qi)). Intuitively the ordering is associated to the remaining time to empty the queue.

— The ordering of the output sequence is defined as follows:

Property 6. The simulation model of a network with finite capacity, monotone phase type services and Poisson arrivals is hv-monotone for ordering on the states and ordering of the output sequences.

Proof: The proof is slightly more complex as the generation of the event takes into account the state. We still proceed by induction. Let u be the random value provided by the input sequence at time t. We begin with steps 1 and 3 of the generation algorithm to obtain the queue number where the events occur (say i). Suppose at time t—1 we have by the induction assumption that where (xi,pi) and (yi, qi) are the states at that time. Now define v as in Step 4 of the generation algorithm. v is the same for both simulations because it is not dependent on the state. Now consider the value of v and the event generated:

— If v is smaller thanthe event is an arrival for any value of the state. In that case we conclude because the arrival is a monotone event.

— if v is larger thanthe event may be a service phase transition, an end of service followed by a routing from i to j or a departure. These events depend on the state because of the phase. We now have two cases:

1. Suppose thatbe the state after the event generated by u applied on (xi,pi). We define similarly

If the event on y is an end of service,. Due to the strict inequalityand the possible events which are service phase transition or service completion, we haveand . Thus the relation holds. If the event in y is not a departure, then we still haveAnd the proof for queue i is complete.

2. Suppose that xi = yi and pi > qi, then the monotonicity of matrix M implies that

Thus even if the events generated by u are not the same for the two states, the relation between the states still holds after execution of the event. By induction the model is hv-monotone.

Networks of G/G/1 Queues

Until now, all the models we have studied are Markovian. Here we consider a more general model in terms of distributions and independence assumptions. Assume that the inter-arrivals and services follow arbitrary distributions. We assume that the trace is composed of triples: the time instant tn, the queue in, and the description of the event. For the sake of simplicity we restrict ourselves to simple events: a symbol "a" describes a fresh arrival and an "e" is used for an end of service. At the end of its service at queue i, a customer may leave the network with probability di or it may route to queue j with probability Pi j.

The state is the number of customers at each queue and we use <a ordering. The output sequence is the state of the network. As the events are described in the input sequence, we just have to prove that the events (arrival, departure, routing from i to j) are monotone. This is already done in the proof of hv-monotonicity of Jackson networks (we just have to consider that Bi = to). For the sake of conciseness we just give the result without proof.

Property 7. The simulation model of a network of GI/GI/1 queue with the formerly defined input sequence is hv-monotone for <a ordering on the states, and dip ordering of the output sequence.

G-Networks of Queues with Positive and Negative Customers

G-networks with positive and negative customers were introduced by Gelenbe in [14]. A negative customer deletes a positive customer at its arrival at a back-logged queue. A negative customer is never queued. Positive customers are usual customers which are queued and receive service or are deleted by negative customers. Under typical assumptions (Poisson arrival for both types of customers, exponential service time for positive customers, Markovian routing of customers, open topology) Gelenbe proved that such a network has a product form solution for its steady-state behavior. As steady-state distribution have a closed form, simulation is not necessary. The results we give here is a trivial example of non monotone network to illustrate that all networks of queues are not monotone.

Property 8. The simulation model of a G-network with positive and negative customers, exponential services and Poisson arrivals of both types of fresh customers is not hv-monotone for <a ordering.

Proof: We give a very simple example with two queues. The states are the number of positive customers in each queue. Assume x = (1,0) and y = (1,1). We have: x da y. Let u a random value and suppose that the event ev generated by u is the end of service in queue 2 followed by routing as a negative customers into queue 1. Clearly ev(1,1) = (0,0) because the negative customer deletes the positive customer at queue 1. Now consider ev(1, 0). As queue 2 is empty this event is a loop: ev(1, 0) = (1,0). Thus, ev(y) da ev(x). The model is not hv-monotone.

Conclusions

We think that TPS and monotonicity of models may be the key for a better utilisation of cores for performance evaluation in the future. The traditional approaches in parallel simulation are based on distributed algorithms techniques to prove a correct sample-path but these approaches are not that efficient due to the cost of synchronisations between processes (clocks and future event list must be, in some sense, globally consistent, see [12]). TPS removes or simplifies the synchronisation problem if some stochastic properties hold. We propose to relax the assumptions of computing the exact sample-path as we only need a proof of quality of service. In the future we will develop a tool to simulate networks of queues using the TPS approach. The first problem is to find a simple characterisation of hv-monotone or inseq-monotone networks. While networks with ordinary customers are often monotone [16], the answer is much more complex for networks with customers and signals such as resets [15], or signal changing the class of a customer [6]. One possible direction is to describe the queueing network as a tensor decomposition of matrices following the approach used in [11] or [5] to prove product-form stationary distribution. Note that we already have a tool [7] to check the comparison and the monotonicity of matrices.