In this paper consideration is given to the // 1 FCFS system in which the service time distribution is not fully known. There is an unknown “theoretical distribution” of the actual service times. But those service times which are known, follow a diferent distribution, obtained by adding theoretical services times with the error term drawn from a left-truncated normal distribution. The goal is to derive bounds on the response time in the // 1 FCFS queue with the unknown “theoretical distribution” that are better than simply using the known service time distribution. In [1] it is shown that in the case when theoretical service times are multiplied by a log-normally distributed error the // 1 LCFS queue with resampling gives better upper bounds on the mean response time in the // 1 FCFS queue with the “theoretical distribution” of the service times. Here we present some numerical results, which show that once the error becomes additive the result of [1] is not valid any more. In the calculations it was assumed that the unknown “theoretical distribution” is left-truncated Weibull. The new modification of the LCFS resampling policy is suggested, which leads to the lower bounds for the unknown first and second moments of the response time in the // 1 FCFS system with the “theoretical distribution” of the service times. Behaviour of mean response times under other service policies is briefly discussed.
Copyright © 2018 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. In: K. E. Samouylov, L. A. Sevastianov, D. S. Kulyabov (eds.): Selected Papers of the 1st Workshop (Summer Session) in the framework of the Conference “Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems”, Tampere, Finland, 20–23 August, 2018, published at http://ceur-ws.org
In this paper a step forward is made in the problem of analyzing the queues with the inaccurate job size information. We understand the inaccurate job size information as described in [2]. Assume that at a top-level some technical system (e.g. a data-intensive execution engine) may be modelled by a //
Upon arrival its (future) service time, say ˆ, is sampled from the known distribution, say ˆ( ), and the value of ˆ is used for scheduling the job. After the job has received service, it turned out that its service time was ̸ happens with the next job etc. It means that the (true) service time is sampled from
another distribution, say ( ), which is unknown to the scheduler. Thus the system’s performance characteristics based on ˆ( ) are biased and may difer significantly from those which are based on ( ).
The general question is: is it possible to tune the
mathematical model so as to reduce the bias? In [
ˆ is possible in // long-tailed,
1 PS queue with service times drawn from ( ). Since it is more
common in the mathematical models of various phenomena that an error term
(usually
normally distributed) enters the model in the additive (not multiplicative) way, we
ifnd it important to understand whether the results of [
The major drawback of the additive model is that in its basic form i.e. when the inaccurate job size ˆ is modelled by ˆ = + , where inaccurate job size ˆ are independent random variables > constants > 0 and < 0, and ˆ = + . We also assume that and >
, for some has the left-truncated Weibull distribution with parameters and and its probability density ( ) has the is ˆ ( ) =
(︁ )︁ −1 −( ) +( ) , > , > 0, > 0.
(1) 1It is always good if is exponentially distributed. 2It is worth noticing here that, on the contrary, for the multiplicative model there are statistical evidences from practice. See [2]. left-truncated normal distribution is The mean E and the variance
can be derived in a straightforward manner (for the details one can refer, for example, to [5]). The probability density ( ) of the For example, for = −2, = 1 the value of is −0.0627. But it can be shown that this 2.
Let us consider two queueing systems operating independently in parallel. The first (denote it system I) is the // 1 FCFS queue with the arrival rate and the service times distributed as
with the probability density (1). Denote the mean sojourn time in this system by . The second (denote it system II) is the // 1 FCFS queue with the same arrival rate but with the service times distributed as ˆ = + , where the density of is given by (2) and the parameters , and are such that E = 0.
Denote the mean sojourn time in this system by ^. For any > 0 it holds that E ˆ = E + E = E,
E ˆ2 = E 2 + E 2.
From the Pollaczek-Khintchine formula it follows that that 0 < <
(E )−1. One of the questions we are interested in is the following: is it possible to tune the mathematical model of system II in such a way that it gives the < ^ for any value of such value of the mean sojourn time, say *, satisfying < * < ^?
In [7– 9] there was introduced the service policy — LCFS with resampling — which, when applied to system II, may give such value of *. But only if the error is multiplicative and the service time distribution is long-tailed.
With the additive error, as it is shown by the numerical examples in the next section, this result does not hold any more3 . Yet the LCFS policy with resampling may be useful for finding the lower bound for we alter it in such a way that the resampling customer occupies a place in the queue with a certain probability4 , say , then by making the value of dependent on the service time distribution ˆ( ) (or only its moments), the mean sojourn time *( ) in . If examples in the next section give the first impressions about this efect. the //
1 LCFS with -resampling may provide a lower bound for . The numerical 4Note that if = 1 then -resampling policy is the simple resampling policy. 3And we don’t have any suggestion for a modification which leads to an upper bound better than ^.
Even though some analytic analysis of the interplay between , ^ and *( ) is possible under the assumptions made above, we will restrict ourselves here only to some observations made from the numerical experiments.
Let us assume that the distributions of rest the values of the parameters were chosen arbitrarily5 . by (1) and (2). Then the numerical computation of , ^ and *( ) is possible. We consider the following three cases for the distribution of : (i) has a constant hazard rate, (ii) has a decreasing hazard rate, (iii) has an increasing hazard rate. The basic data for the distributions of Basic data of the distributions of , and ^. three graphs for *( ) corresponding to the following values of : 1 = 1, 2 = 0.5,
The most important observation, which follows from the Figure 1, is the following.
Irrespective of the tail of the distribution of ˆ, the simple resampling policy (the curve of
*( 1)) does not provide better than ^ estimate of
load. This empirical fact is in the sharp contrast with the results for the multiplicative
model: as shown in [
was chosen for simplicity. 6For the resampling queue the stability condition is diferent: ( ) > (1 + )−1. 200 180 160 140 120 100 80 60 40 20 0 200 180 160 140 120 100 80 60 40 20 0 200 180 160 140 120 100 80 60 40 20 0 vS vŜ v*, θ1 v*, θ2 v*, θ3 vS vŜ v*, θ1 v*, θ2 v*, θ3 vS vŜ v*, θ1 v*, θ2 v*, θ3 the value of . As can be seen from the Figure 1, the lower bound may be quite tight and may hold across the whole (or at least meaningful) range of load. 0 0,005 0,01 0,015 0,02 0,025 0,03 0,035 143,6 61,0 λ 56,0 41,1
It is worth also mentioning that if we switch from the FCFS policy to the other policy (like Shortest-Job-First or SRPT) under which the mean sojourn time depends not only on E ˆ but on some other characteristics of the service time distribution, the situation becomes more complicated and requires a special, delicate treatment7 .
Coming back to the FCFS case, just for the illustrations purposes, let us briefly consider one real-life scenario. Specifically let us estimate the values of the parameters , , , , and based on one of the workloads generated by the tool SWIM (see [10]), which is said to be used (see [11, 12]) to test MapReduce systems. Specifically we use the trace FB09-1 from Facebook8 , which contains a bunch of data on 6638 jobs. Since we are interested in the job’s processing times only we used the methodology from [3, Section 2.2] to combine the available data to obtain the processing times (further denoted by ). The basic statistics for this trace are: the minimal processing time is = 1.3738 × 10−8, the sample mean processing time is ≈ 11.8, the sample second moment is . . ≈ 13574.8.
The direct way to obtain the values of , , , , and would be to equate the ifrst four theoretical moments E ˆ, E ˆ2, E ˆ3 and E ˆ4 to the sample moments and solve the system under the natural constraints > 0, − < < 0, > 0, > 0, < 0 and > 0. Since there are 6 unknowns, the other two equations are: + = , E = 0. The problem is that this system may not have a solution and it is so with the trace9 FB09-1. Thus in order to obtain some estimates we artificially limit the number of unknowns. Firstly we fix the value of = −2 which immediately gives us also the value of = 2 + = 2 + 1.3738 × 10−8. Next we fix the value of = 5 and from the equation E = 0 we find the value of = −10.89427. Finally by solving (numerically) the system of two equation E ˆ = , E ˆ2 = . . , we find the values of ≈ 0.07639 and ≈ 8.1147477 × 10−15. So the probability density functions of the true service time and the error have the form: ( ) = 262511.47 −0.92361 −11.92313 0.07639 , > 2.000000014,
Numerical computations show that for these and the picture is qualitatively the same as in the Figure 1, case (ii).
The empirical observations show that in a case of inaccurate job size information, when the error is additive the simple resampling policy (i.e. when = 1) does not lead to better estimates of the unknown mean sojourn time . Yet there is a modification √ of the simple resampling policy (for example, with = 3 = 1 − − E ^2 ) which may lead to quite tight lower bounds for the . The usefulness of this empirical fact can be seen from the following example. According to the Figure 1 in the // 1 FCFS queue with the arrival rate and the service time ˆ = + (where and are independent, given by (1) and (2); is the true service time, is the error) the true sojourn time satisfies the inequality *( 3) < for all 0 < < ( )−1. Thus 7It may happen, for example, that ^ < even though E ^ = E and E ^2 > E 2. 8The trace can be downloaded from https://raw.github.com/SWIMProjectUCB/SWIM/master/workloadSuite/ FB-2009_samples_24_times_1hr_1.tsv. 9Indeed, due to the given values of and the value ≈ 0 and for > 1 we have that / ≈ 0. Thus, by disregarding the term / and by introducing the new variable = / , the equation E = 0 can be rewritten as + (− )(1 − Φ(− ))−1 = 0. It does not have a solution in (−∞, 0). (unknown!) second moment of : from the Pollaczek-Khintchine formula for we get the following lower bound for the E 2 ≥ max 0, ︂( 2(1 − E ) ( *( 3) − E ) .
︂) Finding conditions when this bound is trivial as well as the proofs of the presented empirical are yet to be done.
The publication has been prepared with the support of the “RUDN University Program 5-100”. The work of L.A. Meykhanadzhyan and R.V. Razumchik (specifically, the idea to consider the inaccuracy model with the additive noise, the results and the analysis of the numerical experiments) was funded by RFBR according to the research project No. 18-37-00283. Stationary Performance Characteristics In Single Server Queues With Inaccurate Job Size Information. Proceedings 30th European Conference on Modelling and
Pastorelli,
Barbuzzi, 2013, arXiv:1306.6023. mean sojourn time in the processor sharing //
1 queue with inaccurate job size information Proceedings of the International Scientific Conference Analytical And Computational Methods in a queueing system
with inverse service order and generalized probabilistic priority, 8. L.A. Meykhanadzhyan. Stationary characteristics of the finite capacity queueing system
with inverse service order and generalized probabilistic priority, Inform. ary distribution in a queueing system with inverse service order and generalized probinjector for MapReduce, https://github.com/SWIMProjectUCB/SWIM.
Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling. Proceedings of the 5th European conference on Computer systems, 265–278, 2010. doi:10.1145/1755913.1755940 performance using workload suites. MASCOTS 2011, IEEE, Singapore, 390–399,