We present and discuss three types of regeneration that are based on classical regeneration for steady-state simulation and output analysis of multiserver systems. First method is arti cial regeneration based on exponential splitting property of some distributions. Regenerative envelopes allow to construct upper and lower bound for QoS characteristic of the system. Resampling of New Better than Used interarrivals or New Worse than Used service times accelerates simulation. All this techniques are reduced to classical regeneration and allow to receive shorter regeneration cycles.
Modern computer systems, as a rule, have a multiserver or multicore architecture, which is caused both by the physical features of the modern technological process of microchip production and by the need to create high-performance computers suitable for solving computationally complex problems. Data transfer to the users in modern networks also requires coordinated performance of several devices, as well as work with several servers, for solving problems of reducing delays and optimizing throughput. By this reason, reliable estimation of Quality of Service (QoS) parameters of multiserver systems is an important problem to study.
Regeneration of stochastic process is one of the powerful and e cient
methods of steady-state simulation and output analysis of complex queueing
systems [
Standard classical regeneration method uses visits of the process (describing the systems behavior) to a xed return state as regeneration points. The trajectory between such points can be divided into independent (for classical regeneration) and identically distributed groups (in general, they can be weakly dependent for wide-sense regeneration). It allows to apply well-developed classical statistical methods based on the special form of the Central Limit Theorem (CLT) for con dence estimation of QoS parameters.
However, in multiserver systems standard regeneration is not guaranteed by stability condition of the system and regeneration points may be too rare to be useful in practice or even they might not exist. We study an alternative constructive method of obtaining the regeneration points.
The so-called arti cial regeneration uses the splitting property [
The regenerative envelopes method is reduced to replacing the original system
based on the coupling method [
We discuss the possibility of accelerating the simulation for multiserver systems in which service times and iterarrival times have New Worse than Used distribution or New Better than Used distribution. If service times have New Worse than Used distribution we resample service time each time when the remaining service time exceeds a xed constant a. If interarrival times has New Better than Used distribution we resample input each time when the remaining interarrival time is less than a xed constant b. In both cases we obtain more frequent classical regeneration that allows to accelerate simulation. 2
Arti cial regeneration based on splitting property in multiserver systems The density f of continuous random variable (r.v.) T can be split if there exists some 0 < p < 1 and density f0, such that:
f > pf0: We de ne a new Bernoulli random variable I called splitting indicator such that P(I = 1) = p. We construct a new splitted r.v. T 0 (stochastically equivalent to the r.v. T ) as follows:
T 0 = IT0 + (1
I)T1; (1) where T0 has density f0, and T1 has density
Now we describe the application of exponential splitting technique to discrete event simulation of multiserver systems.
Consider a stochastic process = fX(t); T(t)gt>0, with discrete (vector) component X = (X1; : : : ; Xn) and continuous component T = (T1; : : : ; Tm) > 0 (hereafter we denote vector-valued variables in bold and assume the dimension is clear from context, if not sub-indexed explicitly). Moreover, we assume that T decreases linearly with time, that is, T(t + ) = T(t) 1; for > 0, and de ne an event as a time epoch ti such that Tj (ti) = 0 for some j 2 f1; : : : ; mg (in this case we say that the ith event occurring at ti is of j th type). We assume that the discrete component X is changed only at event epochs, e.g. by some recurrent relation
X(ti+) = Gj (X(ti )) ; (5) where Gj is the recursion related to type j event, or, in general, assume the change is governed by some Markovian probability
Pj (x; x0) = Pj fX(ti+) = x0jX(ti ) = xg: The component X(t) does not change if T(t) > 0, that formally means
X(t) = X(ti+); i = maxfk : tk < tg: We also assume that in the vector T the zeroed at ti component Tj is initialized at ti+ from some distribution with density fj , that is, fj (u; x; x0) = P(Tj (ti+) 2 dujX(ti ) = x; X(ti+) = x0): (6) Now we assume, that if X(t) = x for some speci c x , then the process allows to perform exponential splitting of the continuous component T, that is for each continuous component Tj there exist constants 0(j); (j); p(j) such that (4) holds for the density fj (u; x; x ), with corresponding density f0;j (u) = j e j(u 0(j)) and f1;j de ned appropriately. At that, we introduce a split process 0 = fX(t); T0(t); Z(t)gt>0 enhanced with auxiliary phase variable Z 2 f0; 1; 2gm denoting the phases of components of T de ned componentwise in a recursive manner as follows (7) (8) (9) Zj (ti+) = Zk(ti+) = Zk(ti ); k 6= j ; 1; 2; otherwise;
if X(ti+) = x and Ij (ti+) = 1; where ti is the epoch of type j event, and Ij is the splitting indicator corresponding to the component T 0 with success probability p(j ). However, starting j from Zj (ti+) = 1 at time ti, the component Zj makes a step between the events:
Zj (t) = 1; ti < t < ti + 0(j ) 0; t > ti + 0(j ); that is, the phase Zj is changed from one to zero when not less than 0(j ) time passes since the epoch ti corresponding to the last event of j th type (we call this time epoch a pseudo-event). In case Zj 6= 1, the component Zj does not change during inter-event time.
We de ne the arti cial regeneration epochs as the (increasing) sequence of pseudo-event epochs f kgk>1 k+1 = min ft > k : X(t+) = x ; Z(t+) = 0g : (10)
This method of arti cial regeneration could be applied to performance estimation of m-server system with energy e ciency control and single waiting room. The discrete and continuous components of the simulated process we de ne in the following way. The discrete components 0(t) is the queue size at time t, and Xi(t) is the mode of ith server, i = 1; : : : ; m, X1(t) = 1 if the server is active, and X1(t) = 0 if the server is in the sleep mode. Continuous components: T0(t) is the time before the next arrival epoch, and Ti(t) is the remaining times of current activity (service/sleep) of ith server, i = 1; : : : ; m. For the regeneration epoch, we set x = fk; 1; : : : ; 1g for some k > 0 and recall that arti cial regeneration occurs at such pseudo-event epoch t that X(t+) = x and all the exponentially split components T0; : : : ; Tm are in exponential phases, that is, Z(t+) = 0.
The second approach of de ning the regeneration times is to construct stochastically equivalent system with the same input, but sampling from either f0 or f1 at every random variable initialization time epoch. Then the original r.v. T is replaced by a stochastically equivalent splitting representation T 0 = IT0+(1 I)T1. Coupling method allows to construct new arti cial system, which is equivalent to the original system, and by this reason has equivalent QoS parameters.
To construct the arti cial regeneration points we suggest the following method. Sample the sequence of splitting indicators Ii; i > 1 as a Bernoulli 0-1 r.v. with success probability p. Sample service times T~j either from density f0, or from f1, using relation (2). Fix integer 0 ( xed number of customers in system) and de ne n+1 = infnk > n : k = 0 6 m;
o Ii = 1; i 2 Mk; M n \ Mk = ; ; n > 0; (11) where Mn = fi : ti 6 tn < tidg is the set of the customers presented in new system at arrival instant tn and tid is the departure instant of the ith customer. Note that at the constructed regeneration epoch, the remaining work possesses memoryless property, since all the tasks being served have exponentially distributed service times. It is easy to see that n := f n; Ij ; j 2 M n g; n > 1 is a Markov process, and that distribution of n is independent of n > 1 and pre-history f k; k < ng. 3
Regenerative envelopes for multiserver systems simulation Now we consider an in nite bu er FCFS m-server GI=G=m queueing system , with the renewal input with instants tn, the iid interarrival times Ln = tn+1 tn and the iid service times Sn; n > 1. Denote n the number of customers at instant tn , Qn the number of customers waiting in the queue at instant tn , so Qn = max(0; n m).
The main idea of the regenerative envelopes method is the construction of two new systems: a majorant system and a minorant system with the same input as in the original system , but (stochastically) smaller (in minorant system) or larger (in majorant system) service times.
We describe the construction of m-server majorant system ~. The corresponding variables in the system ~ we endow with tildes. Assume that the service time distributions in both systems are ordered as FS (x) 6 FS~(x); x > 0, that is S >st S~ (stochastically). Moreover, by construction, L =st L~. Then the coupling method allows to take t~n = tn and Sn > S~n w.p.1.
De ne the set Mn = fi : ti 6 tn < zig of the customers, which are being served in the system at instant tn, Si(n) { the remaining service time of customer i at instant tn in .
Fix arbitrary integer 0 > 0 (number of customers in the system), constants 0 6 a 6 b < 1 and de ne n+1 = infnk > n : k = 0; Si(k) 2 (a; b); M n \ Mk = ?; i 2 Mko: (12)
Then, at the (discrete) instant k = n+1, we replace all the non-zero remaining times Si(k); i 2 Mk, by the upper bound b.
It is easy to see that cess and the distribution of n := f n; Si(n); i 2 Mng; n > 1, is a Markov pro
n is independent of n and pre-history f k; k < ng; n > 1.
The process f n; n > 1g classically regenerates at the instants f kg and has the i.i.d regeneration cycles f k; n 6 k < n+1g with i.i.d cycle lengths n = n+1 n; n > 1.
In a minorant system we de ne the regenerative moments n; n > 0 in a similar way (with possibly other values a; b; 0). At each such instant n we replace the remaining times Si(k); i 2 Mk, by the lower bound a.
The systems ; ; have zero initial state, and moreover (in an evident notation) Ln = Ln = Ln; Sn > Sn > Sn; n > 1. Then it follows from coupling property that n > n > n; Qn > Qn > Qn; n > 1; (13) and it allows us to use regenerative simulation of and to obtain an upper and lower bounds of the mean stationary queue size (number of customers) in original system.
EQ 6 EQ 6 EQ: 4
Accelerated simulation of multiserver networks with New Better than Used distributions In this section we will discuss how the properties of New Better (Worse) than Used distributions of input or service times could be applied to accelerate regeneration simulation.
We say that the distribution F of r.v. T has increasing (decreasing) failure rate IFR (DFR) if
Ft(x) = P (T 6 t + xjT > t) = P (T 6 x) = F (t + x)
F (t)
F (t) is increasing (decreasing) in t. Remark, that lim x!0
Ft(x) x = f (t) F (t) = r(t): t R r(x)dx
Function r(t) is called failure rate and it is easy to see that F (t) = e o . Weibull and Gamma distributions with shape parameter > 1 are IFR, with < 1 are DFR.
It is known [
t F (t) > (6) e 1 ; t < Then we construct new system ~ with the same input, but each time when St > a = const we resample S with d.f. B. Using classical regeneration approach for new system ~ we obtain lower (upper) bound for QoS parameter of the original system (for example, queue size).
If L has NBU (NWU) distribution, then At 6 (>) A or
P (Lt > x) 6 (>) P (L > x): Then we construct new system ~ with the same service times, but each time when Lt 6 a = const we resample L with d.f. A. In this case we can use classical regeneration approach for new system ~ to obtain lower (upper) bound for QoS parameter of the original system .
In the case of NWU service times or NBU interarrival times we obtain more frequent classical regenerations that allows to accelerate simulation. 5
Conclusion We present three techniques which allow to construct and speed-up classic regenerations in multiserver systems: arti cial regeneration based on splitting property, regenerative envelopes and accelerated simulation for systems with NWU service times of NBU input Our future work will focus on the comparison of the simulation results e ciency.
ACKNOWLEDGEMENTS The publication was carried out under state order to the Karelian Research Centre of the Russian Academy of Sciences (Institute of Applied Mathematical Research KRC RAS). This research is partially supported by RFBR project 1807-00147 and by the Ministry of Education and Science of Russian Federation (project no. 14.580.21.0009, unique identi er RFMEFI58017X0009).