PERTURBATION ANALYSIS OF A VARIABLE M/M/1 QUEUE: A PROBABILISTIC APPROACH NELSONANTUNES,CHRISTINEFRICKER,FABRICEGUILLEMIN,ANDPHILIPPE ROBERT 6 0 0 Abstract. Motivatedbytheproblemofthecoexistenceontransmissionlinks 2 oftelecommunicationnetworksofelasticandunresponsivetraffic,westudyin n thispapertheimpactonthebusyperiodofanM/M/1queueofasmallper- a turbation intheserverrate. Theperturbation depends upon anindependent J stationary process (X(t)) and is quantified by means of a parameter ε ≪ 1. We specifically compute the two first terms of the power series expansion in 6 ε ofthe meanvalue ofthe busyperiodduration. Thisallows usto study the validityoftheReduced ServiceRate(RSR)approximation, whichconsists in ] I comparing the perturbed M/M/1 queue with the M/M/1 queue where the N servicerateisconstant andequal tothemeanvalueofthe perturbation. For . thefirsttermoftheexpansion,thetwosystemsareequivalent. Forthesecond s term, the situation is more complex and it is shown that the correlations of c theenvironmentprocess(X(t)) playakeyrole. [ 1 Contents v 5 1. Introduction 1 1 2. Model 3 0 1 3. Busy period analysis: First order term 5 0 4. Busy Period: Second order term 9 6 5. Applications 15 0 6. Appendix: Some useful quantities for the M/M/1 queue 19 / s References 21 c : v i 1. Introduction X We considerinthis paperanM/M/1queuewithatime varyingserverrate. We r a specificallyassumethattheserverratedependsuponarandomenvironmentrepre- sentedbymeansofaprocess(X(t)),takingvaluesinsome(discreteorcontinuous) state space and assumed to be stationary. The study of this queueing system is motivated by the following engineering problem: Consider a transmission link of a telecommunicationnetwork carryingelastic traffic, able to adapt to the congestion level of the network, and a small proportion of traffic, which is unresponsive to congestion. The problem addressed in this paper is to derive quantitative results for estimating the influence of unresponsive traffic on elastic traffic. In real implementations, elastic traffic is controlled by the so-called transmis- sion control protocol (TCP), which has been designed in order to achieve a fair bandwidth allocation among sufficiently long flows at bottleneck links. If we as- sume that the link under consideration is the bottleneck, say, the access link to Date:February1,2008. Keywordsandphrases. PerturbationAnalysis. ExpansionofCycleFormulas. M/M/1queues. 1 2 N.ANTUNES,C.FRICKER,F.GUILLEMIN,ANDPH.ROBERT the network, then it is reasonable to assume that bandwidth is distributed among the different competing elastic flows according to the processor sharing discipline (seeforinstanceMassouli´eandRoberts[10]andDelcoigneet al.[6]). Unresponsive traffic is then composed of small data transfers, which are too short to adapt to the congestionlevelofthe network. Throughoutthe paper,itwillbe assumedthat long flows arrive according to a Poisson process. With the above modeling assumptions, unresponsive traffic appears for elastic flowsasasmallperturbationoftheavailablebandwidth. Inaddition,whenthereis no unresponsive traffic,owing to the insensitivity propertysatisfiedby the M/G/1 processor sharing queue, the number of long flows is identical to the number of customers in an M/M/1 queue. Hence, in order to obtain a global system able to describethebehavioroflongflowsinthe presenceofunresponsivetraffic,westudy anM/M/1queuewithatimevaryingserverrate,whichdependsuponunresponsive traffic (for instance the number of small flows and their bit rate). The problem is then to estimate the impact of unresponsive traffic on the performance of the system. A classical issue is in particular to investigate the validity of the so-called reduced service rate (RSR) approximation, which states that everything happens as if the server rate for long flows were reduced by the mean load of unresponsive traffic. RSRapproximationresults(alsocalledreducedloadequivalence)havebeen shownto hold in a large number of queueing systems where some distributions are heavy tailed see Agrawalet al. [1], Jelenkovi´c and Momˇcilovi´c [9] for example. It is worth noting that queueing systems with time varying server rate have been studied in the literature in many different situations. In Nu´n˜ez-Queija and Boxma[13],theauthorsconsideraqueueingsystemwherepriorityisgiventosome flows driven by Markov Modulated Poisson Processes (MMPP) with finite state spaces and the low priority flows share the remaining server capacity according to the processorsharing discipline. By assuming that arrivals are Poissonand service timesareexponentiallydistributed,theauthorssolvethesystembymeansofmatrix analysis methods. Similar models have been investigated in Nu´n˜ez-Queija [11, 12] by still using the quasi-birth and death process associated with the system and a matrix analysis. In this setting, the characteristics of the queue at equilibrium are expressed in terms of the spectral quantities of some matrices leading to potential numericalapplications. More recently, priority queueing systems with fast dynam- ics,whichcanbedescribedbymeansofquasi-birthanddeathprocesses,havebeen studied via a perturbationanalysis of a Markovchain by Altman et al. [2]. Boxma andKurkova[4]studies the taildistributions of anM/M/1queue with two service rates. Getting qualitative results for queueing systems with variable service rates to study, for example, the impact of the variability of the service rate on the perfor- mancesofthesystemisratherdifficult. Attheintuitivelevel,itisquitewellknown thatthe variabilitydeterioratesthembut, rigorouslyspeaking,only few resultsare available. Themainobjectiveofthispaperistogetsomeinsightonthesephenom- ena by considering a slightly perturbed system. As it will be seen, deriving such an expansion is already quite technical. In this paper, it is assumedthatthe serverrate ofthe M/M/1queue is equalat time t to µ+εp(X(t)) for some function p, where (X(t)) is the process describing theenvironmentaffectingthe servicerate. InFrickeret al.[7],ithasbeenassumed that the process (X(t)) is a diffusion process and that p(x) = −x. In this paper, PERTURBATION ANALYSIS OF A VARIABLE M/M/1 QUEUE 3 the perturbation function p is quite general and the environment process (X(t)) is only assumed to be stationary and Markovian. Moreover, we are specifically interested in the power series expansion of mean busy period duration in ε, which quantifiesthemagnitudeoftheperturbation. Asfarasthefirstorderisconcerned, the RSR approximation is valid: The time-varying server queue is identical to an equivalentM/M/1queue witha fixedservicerateequaltothe averageservicerate µ+εE[p(X(0))]. Combining the observation with the results obtained in Antunes etal.[3],onecaneasilyconclude,viaasimpleregenerativeargument,thattheRSR holds for the mean number of customers in the queue. The analysis of the second order is much more intricate; the correlations of the process (X(t)) play a key role and, consequently, the RSR approximation is no more valid. Theorganizationofthispaperisasfollows: ThemodelisdescribedinSection2. The first order term in the power series expansion of the mean busy period du- ration is computed in Section 3. The second order term is derived in Section 4. Applications of the results are discussed in Section 5. Some basic elements of the M/M/1 queue are recalled in Appendix. 2. Model 2.1. Notation and Assumptions. Throughoutthe paper L(t) denotes the num- ber of customers at time t in an M/M/1 queue with arrival rate λ and service rate µ. The variable B denotes the duration of a busy period starting with one customer: Given L(0)=1, B =inf{s≥0:L(s)=0}. Itisassumedthatthestabilityconditionλ<µholds. Theinvariantdistributionof (L(t))isgeometricallydistributedwithparameterρ=λ/µ. Forx≥1,thevariable B denotes the durationofabusy periodstartingwith xcustomers. By definition, x B d=ist. B. By convention, in the following when the variables B, B and B′ are 1 1 1 used in the same expression, they are assumed to be independent with the same distribution as B. This queue will be referred to as the standard queue denoted, for short, by S-Queue. For ξ ≥ 0, N denotes a Poisson process with intensity ξ and for 0 ≤ a < ξ b, N ([a,b]) denotes the number of points of this point process in the interval ξ [a,b]. Inparticular,N willrepresentthe arrivalprocessandN the processofthe λ µ services of the S-Queue. The Poisson processes N and N will be assumed to be λ µ independent one of each other and independent of the modulating Markov process (X(t)). The process (L(t)) can be represented as the solution of the stochastic differential equation def. dL(t) = L(t)−L(t−)=N ([t,t+dt])− Nµ([t,t+dt]) λ {L(t−)>0} 1 (1) =dN (t)− dN (t), λ {L(t−)>0} µ 1 where L(t−) is the left limit of L(s) at s ր t. For the representation of queueing Markovprocessesas solutions of stochastic differential equations, see Robert [14]. The perturbed queue. In the following, we consider an M/M/1 queue with a service rate varying in time as a function of some process (X(t)) taking values in some space, denoted by S. We assume that the process (X(t)) is an ergodic Markov process on S. Typically, the state space of the environment S is a finite or countable set when (X(t)) is a Markov Modulated Poisson Process (MMPP) or 4 N.ANTUNES,C.FRICKER,F.GUILLEMIN,ANDPH.ROBERT S = R in the case of a diffusion, for instance an Ornstein-Uhlenbeck process (see Frickeret al.[7]). Theinvariantmeasureoftheprocess(X(t))isdenotedbyν. The MarkoviannotationE (·)willreferonlytotheinitialstatexoftheMarkovprocess x (X(t)), therefore E (·) will denote the expected value when the process (X(t)) is ν at equilibrium. The variable Lε(t) denotes the number of customers at time t in the M/M/1 queuewithtime-varyingservicerate. Theprocess(Lε(t),X(t))isaMarkovprocess. The transitions oef the process (Lε(t)) are given by: If Lε(t) = l and X(t) = x at time t, e l+1e at rate λ e l→ (l−1 ′′ (µ+εp(x)) {l>0} 1 for some function p(x) on the state space of the environment S and some small parameter ε ≥0. When p(x)>0, this implies that there is an additional capacity of service when compared to the S-Queue. On the contrary, when p(x) < 0, the server is with a slower rate than in the S-Queue. The quantity p+(a) (respectively p−(a)) is defined as max(p(a),0) (respectively max(0,−p(a))). At time t ≥ 0, the additionalcapacityisthereforeεp+(X(t))and−εp−(X(t))isthelostcapacity. The perturbation considered in this paper is regular, see Altman et al. [2]. The variable Bε is the duration of a busy period starting with one customer, that is, given Lε(0)=1, e Bε =inf{s≥0:Lε(s)=0}. e For x ≥ 1, the variable Bε denotes the duration of a busy period starting with xe e x customers (Bε d=ist. Bε). In the rest of this paper, we make the two following 1 assumptions: e e e (H ) the function |p(x)| is bounded by a constant M >0 1 (H ) εsup{|p(x)|:x∈S}<µ. 2 The following propositionestablishes that the length of the busy cycle is indeed integrable. The rest of the paper is devoted to the expansion of its expected value with respect to ε. Proposition 1. Under the condition λ < µ, there exist some constants K and ε >0 such that for any ε<ε and n≥1, 0 0 supE Bε |X(0)=x ≤Kn. n x∈S (cid:16) (cid:17) Proof. If one chooses ε so that e 0 µ d=ef.µ−ε inf{p−(x):x∈S}>λ, 0 0 then clearly the number of customers of the P-Queue is certainly smaller than the number of customers of an M/M/1 queue with arrival rate λ and service rate µ . 0 Consequently, the corresponding busy periods compare in the same way, hence it is enough to take K =1/(µ −λ). (cid:3) 0 The queue with time-varying service rate as defined above will be referredto as the perturbed queue, denoted, for short, by P-Queue. The case ε = 0 obviously corresponds to the S-Queue. PERTURBATION ANALYSIS OF A VARIABLE M/M/1 QUEUE 5 2.2. Adding and Canceling Departures. The basic idea of the perturbation analysis carried out in this paper is to construct a coupling of the busy periods of the processes (L(t)) and (Lε(t)). This is done as follows, provided that for both queues the arrival process is N . λ e Additionaldepartures. WedenotebyN+ thenon-homogeneousPoissonprocess whose intensity is given by t → εp+(X(t)). Conditionally on (X(t)), the number of points of N+ in the interval [a,b], 0≤a≤b is Poisson with parameter b ε p+(X(s))ds. Za The points of N+ are denoted by 0 < t+ ≤ t+ ≤ ... ≤ t+ ≤ ... and are called 1 2 n additional departures. In particular the distribution of the location t+ of the first 1 point of N+ after 0 is given by, for x≥0, x (2) P(t+ ≥x)=P(N+([0,x])=0)=E exp −ε p+(X(s))ds . 1 (cid:18) (cid:18) Z0 (cid:19)(cid:19) See Grandell [8] for an account on non-homogeneousPoissonprocesses,referred to as doubly stochastic Poissonprocesses. CancelingDepartures. WedenotebyN− thepointprocessobtainedbythinning the point process N (see Robert [14]). It is defined as follows: A point at s > 0 µ of the Poisson process N is a point of N− with probability εp−(X(s))/µ. In this µ way, N− is a stationary point process with intensity εp−(X(s)). A point of N− is called a canceled departure. The points of the point process N− are denoted by 0<t− ≤t− ≤...≤t− ≤.... For x>0, by definition, 1 2 n Nµ([0,x]) εp−(X(s )) (3) P(t− ≥x)=E 1− i , 1  µ  i=1 (cid:18) (cid:19) Y   where (s ) are the points of the point process N . i µ With the above notation, it is not difficult to show that the Markov process (Lε(t)) hasthe samedistributionasthe solutionofthe stochasticdifferentialequa- tion e (4) dLε(t)=dN (t)− d N +N+−N− (t), λ 1{Lε(t−)>0} µ which is the analogue of Equation (1) for the P(cid:0)-Queue. (cid:1) e e 3. Busy period analysis: First order term Let us assume that a busy period with one customer starts at time 0 in the S-Queue and P-Queue. In this section, we determine the first term of the power seriesexpansioninεoftheexpectedvalueofBε,thedurationofthebusyperiodin theP-Queue. Thisderivationallowsusinadditiontolaydownpartofthematerial neededin the next sectionto compute the moere intricate secondtermof the power series expansion in ε. For the first order term, we only have to consider the cases when there is either a single additional departure or else a single canceled departure. The probability thatbotheventsoccurinthesamebusy periodisclearlyofthe orderofmagnitude of ε2 since the intensities of the associatedPoissonprocesses are proportionalto ε. 6 N.ANTUNES,C.FRICKER,F.GUILLEMIN,ANDPH.ROBERT For x≥1,the stabilityassumptions ensurethat the expectedvalues ofthe busy periodsstartingwithxcustomers,namelyE(B )andE(Bε),arebothfinite. When x x the first additional and canceled departures are such that t+ > Bε and t− > Bε 1 1 then B =Bε. We now consider the different possibilitiese. e e A single additional departure. If there is only one additional departure and no e canceled departure in (0,Bε) then at time Bε, the P-queue is empty and the S- queue is with one customer (see Figure 1). e e P-Queue 6 6 S-Queue 1 - 0 t+ Bε B 1 Figure 1. A busy Periodewith an Additional Departure We specifically prove the following lemma. Lemma 2. In the case of a single departure, we have E [p(X(0))+] (5) E (B−Bε) =ε ν +o(ε), 1{t+1<B} (µ−λ)2 (cid:16) (cid:17) where ν is the equilibrium deistribution of the environment (X(t)). Proof. When there is only one additional departure, the variable Bε is between t+ 1 and t+. We can write 2 e (6) E (B−Bε)1{t+1<B} =E (B−Bε)1{t+1<Bε<t+2,t−1>Bε} +∆, where the o(cid:16)ffset term ∆ can be(cid:17)boun(cid:16)ded as follows (cid:17) e e e e (7) ∆≤E |B−Bε| 1{t+2<Bε,t−1>Bε}+1{t−1≤Bε,t+1≤Bε} . (cid:16) (cid:16) (cid:17)(cid:17) Let us estimate the first term of the right-hand side of (6). Equation (2) and e e e e e the boundedness of p give that B P(t+ ≤B)=1−E exp −ε p+(X(s))ds 1 Z0 !! B =εE p+(X(s))ds +o(ε) Z0 ! ε =εE(B)E p+(X(0)) +o(ε)= E p+(X(0)) +o(ε), ν ν µ−λ by independence between B(cid:2)and (X(t(cid:3))) and the stationa(cid:2)rity of (X(cid:3)(t)). By the strongMarkovproperty at the stopping time Bε, conditionally onthe event{t+ < 1 e PERTURBATION ANALYSIS OF A VARIABLE M/M/1 QUEUE 7 Bε <t+,Bε <t−},the S-Queue startsatBε anindependentbusy periodwithone 2 1 customer, therefore e e e E (B−Bε)1{t+1<Bε<t+2,t−1>Bε} =P(t+1 <Bε <t+2,t−1 >Bε) (cid:16) (cid:17) ×E (Be−Bε)|t+1e <Bε <et+2,t−1 >Bε =eP(t+1 <Bε <te+2,t−1 >Bε)E(B1). (cid:16) (cid:17) Now, since {t+1e<Bε}={et+1 <B} on thee event {t+1 <Beε <t+2,Bε <te−1}, then P(t+ <Bε <t+,t− >Bε)=P(t+ <B)−P(t+ <Bε, t+ <Bε)− 1 2 e1 1 1 e2 e P(t+ <Bε, t− <Bε)+P(t+ <Bε, t+ <Bε, t+ <Bε) e e 1 1 e 1 e 2 1 =P(t+ <B)+o(ε), 1 e e e e e since two or more extra jumps in the same busy period is o(ε). Similarly, by using again the strong Markov property, one gets the following estimation E |B−Bε|1{t+2<Bε,t−1>Bε} ≤ E(Bn)P(t+n ≤Bε ≤t+n+1,t−1 ≥Bε) (cid:16) (cid:17) nX≥2 e e e 1 e e ≤ nP(N+([0,B])=n). (µ−λ) n≥2 X Indeed, given the S-Queue, N+([0,B]) has a Poisson distribution with parameter Bεp+(X(s))ds, which implies that 0 R nP(N+([0,B])=n)= n≥2 X B B E εp+(X(s))ds −E εp+(X(u))due−ε 0Bp+(X(s))ds =o(ε) Z0 ! Z0 R ! and the first term in the right hand side of Inequality (7) is thus negligible at the first order in ε. To estimate the secondterm in the righthand side of Inequality (7), we need to consider the different possibilities for the location of the points t+ and t−. In the 1 1 case that t+ and t− occur during [0,B] and Bε ≥ B, at time B the P-Queue has 1 1 at most p≥0 customers if there have been p+1 canceled departures. If D([0,B]) is the number of customers during the busy peeriod of the S-Queue, then certainly E (Bε−B) 1{Bε≥B,t−1≤B,t+1≤B} (cid:16) ≤E E B (cid:17) P(t− <B,t+ ≤B ≤t+) e e X(B) D([0,B]) 1 1 2 ≤K(cid:0)E(D([0,(cid:0)B]))P(t−1(cid:1)(cid:1)<B,t+1 ≤B ≤t+2)=o(ε), by Proposition 1. On the other hand, E Bε−B 1{Bε<B,t−1≤B,t+1≤B} ≤E B1{t−1≤B,t+1≤B} =o(ε). (cid:16)(cid:12) (cid:12) (cid:17) (cid:16) (cid:17) Finally, (cid:12)(cid:12)e (cid:12)(cid:12) e E Bε−B 1{t−1≤Bε,t+1≤Bε} (cid:16)(cid:12) (cid:12) (cid:17) (cid:12)(cid:12)e (cid:12)(cid:12) e≤E eBε−B 1{t−1≤B,t+1≤B} +E B1{t−1≤B,B≤t+1≤Bε} , (cid:16)(cid:12) (cid:12) (cid:17) (cid:16) (cid:17) (cid:12)(cid:12)e (cid:12)(cid:12) e 8 N.ANTUNES,C.FRICKER,F.GUILLEMIN,ANDPH.ROBERT where it can be shown in a similar way as before that the last term is o(ε). One concludes that the term ∆ is o(ε) as ε goes to 0. By using Equation(6), we obtain the desired result. (cid:3) The estimation of the right hand side of Equation (6) may appear quite cum- bersome. It is however worth noting that the environment (X(t)) of the P-Queue introduces delicate dependences, which have to be handled with care. This is why we have chosen to explicitly write the precise setting in which the strong Markov propertyisusedtogetthefirstorderterm. Inthefollowing,similarargumentswill not be explicitly formulated. Asinglecanceleddeparture. Supposenowthatthereisonlyonecanceleddeparture, i.e. adepartureoftheS-QueueiscanceledfortheP-Queue,andnoadditionaljumps during the busy period of the S-Queue. In this case, at the end of the busy period of the S-Queue, at time B, the P-queue has one customer and thus starts a busy period. Providedthattherearenomorecanceledandadditionaldeparturesduring (B,Bε)intheP-Queuethenthedifferencebetweenbothbusyperiodshasthesame distribution as the length B of a standard busy period. See Figure 2. 1 e P-Queue 6 6 S-Queue 1 - 0 t− B Bε 1 Figure 2. A Busy Period with a CanceledeDeparture Lemma 3. In the case of a single canceled departure, we have E [p−(X(0))] (8) E (Bε−B)1{t−1≤B} =ε ν(µ−λ)2 +o(ε). (cid:16) (cid:17) Proof. By using the saeme arguments as before, one obtains the relation E (Bε−B)1{t−1≤B} =E B11{t−1≤B,B+B1<min(t+1,t−2)} +o(ε) (cid:16) (cid:17)=E((cid:16)B )P(t− ≤B)+o(ε). (cid:17) e 1 1 To estimate P(t− ≤B), denote by (D ) the sequence of departures times in the 1 i S-Queue and N the number of customers served during the busy period of length PERTURBATION ANALYSIS OF A VARIABLE M/M/1 QUEUE 9 B, then Equation (3) gives the identity N εp−(X(D )) i−1 εp−(X(D )) P(t− ≤B)=E i 1− j 1  µ µ  i=1 j=1(cid:18) (cid:19) X Y  N  ε = E p−(X(D )) +o(ε) i µ ! i=1 X ε = E(N)E p−(X(D )) +o(ε) 1 µ by stationarity of (X(t)) and Wal(cid:0)d’s Formula.(cid:1) Since E(N) = µ/(µ−λ) (see Ap- pendix), Equation (8) follows. (cid:3) IntheexpansionofthebusyperiodoftheP-Queue,theterminεisgivenbythe two events consisting in only one canceled or only one additional departure during the busy period of the S-queue. The next proposition follows from Equations (5) and (8). Proposition 4 (First Order Expansion). 1 E [p(X(0))] (9) E(Bε)= −ε ν +o(ε). µ−λ (µ−λ)2 Equation (9) is consisetent with the so-called Reduced Service Rate approxima- tion. As a matter of fact, everything happens as if we had a classical M/M/1 queue with service rate µ+εE [p(X(0))] and arrival rate λ. In that queue, the ν mean length of the busy period is given by 1 1 E [p(X(0))] ν = −ε +o(ε), µ+εE [p(X(0))]−λ µ−λ (µ−λ)2 ν which coincides with Equation (9). In the following section, we investigate the second order term and show that the RSR approximation is no more valid. 4. Busy Period: Second order term Inthis section,the coefficientofε2 ofthe meanbusy periodE(Bε)is calculated. Inthesamewayasforthefirstorder,thiscoefficientisrelatedtotheeventthattwo extrajumpsoccurduringabusyperiodoftheperturbedM/M/1queeue. Sinceextra jumps can be either additional departures or canceled departures, there are three cases to investigate. As it will be seen, this coefficient stresses the importance of theevolutionofthevaryingcapacity,inparticularthroughits correlationfunction. This was not the case for the first order term, since only the average value of the capacity shows up there. Inthefollowing,inordertogettheε2coefficient,onehastoconsiderthedifferent possibilities for the location of the points t+, t+ and t−, t−. By using similar 1 2 1 2 arguments as in Section 3, it is not difficult to show that any event involving t+ or 3 t− yields a term of the order ε3 in the expansion of E(Bε−B). 3 Define A ={t+ ≤B,t− ≥t++B e }. + 1 1 1 L(t+)−1 1 On this event, at least one departure is added and the busy period of the P-Queue finishes before a departure is canceled (note that B is the length of a busy L(t+)−1 1 10 N.ANTUNES,C.FRICKER,F.GUILLEMIN,ANDPH.ROBERT period of S-Queue starting at time t with L(t+)−1 customers). On the event 1 1 A ={t− ≤B, B ≤t+ ≤B+B }, ± 1 1 1 a canceled departure occurs and another departure is added before the completion ofthe busy periodofthe P-queue,whereB denotes the durationofthe additional 1 busy period due to the canceled departure. Finally, on the event A ={t− ≤B, B+B ≤t+}, − 1 1 1 atleastacanceleddepartureoccurs andno additionaldeparturesare addedbefore the completion of the busy period B . 1 Bycheckingallthedifferentcases,itisnotdifficulttoseethatifA=A ∪A ∪ + ± A , the expression E((Bε −B) ) is o(ε2) (and even equal to 0 in some cases, − Ac 1 for instance when there are a canceled departure and an additional departure in such a way that Bε =Be). The following sections are devoted to the estimation of E((Bε−B) ) for A∈{A ,A ,A }. A + ± − 1 Inafirststep,eweanalyzethecasewhenthereareonlyadditionaldeparturesbe- foreeB,thatis,weconsiderthetermE((Bε−B) ). Whennocanceleddeparture 1A+ occurs, at most two additional departures in the time interval [0,B], occurring at times t+ and t+ respectively, may play aerole in the computation of the coefficient 1 2 ofε2 ofE(B−Bε). Inthis case,the differencebetweenB−Bε isequalto the busy period of an S-Queue which starts with either one or two customers, depending on the fact that, oen the event {t+ ≤ B}, the busy period of thee P-Queue is already 1 completed at time t+ or not. See Figure 3. 2 As before, B denotes a random variable with the same distribution as the sum 2 of two independent variables distributed as B and independent of B, t+ and t+. 1 1 2 One gets E(cid:16)(B−Bε)1A+(cid:17)=E(cid:18)(B−Bε)1{t+1≤B,t−1≥t+1+BL(t+1)−1}(cid:19) =eE(B )P t+ <B,t+e<t++B ,t− ≥t++B 2 1 2 1 L(t+)−1 1 1 L(t+)−1 1 1 (cid:16) (cid:17) +E(B )P t+ <B,t+ ≥t++B ,t− ≥t++B +o(ε2). 1 1 2 1 L(t+)−1 1 1 L(t+)−1 1 1 (cid:16) (cid:17) This decomposition entails that (10) E (B−Bε) =(E(B )−E(B ))P t+ <B,t+ <t++B 1A+ 2 1 1 2 1 L(t+1)−1 (cid:16) (cid:17) (cid:16) (cid:17) +eE(B1) P t+1 <B −P t+1 <B,t−1 ≤t+1 +BL(t+)−1 +o(ε2). 1 FromEquation(10),(cid:16)on(cid:0)ehasto(cid:1)expan(cid:16)dthreeexpressionswithresp(cid:17)ec(cid:17)ttoε. This is done by proving the three following lemmas. Lemma 5. The quantity P t+ <B,t+ <t++B can be expanded as 1 2 1 L(t+)−1 1 (cid:16) (cid:17) (11) P t+ <B,t+ <t++B 1 2 1 L(t+)−1 1 (cid:16) (cid:17) B =ρε2E (B−v)E p+(X(0))p+(X(v)) dv+o(ε2). ν Z0 ! (cid:0) (cid:1)