Nous d´ecrivons leur comportement fluide, ce qui permet d’´ecrire les conditions de stabilit´e du r´eseau et de construire les variables d’´etat (telles que temps d’attente aux diff´erentes stations, tailles des files d’attente..) dans leur r´egime stationnaire. Dans ce chapitre, nous ´etudions le comportement du r´eseau dans le cas o`u la distribution des temps de service dans chaque station est sous-exponentielle.
Monotone Separable Networks
- Framework
- Maximal Dater
- Stationary Ergodic Setting and Main Stability Results
- Upper G/G/1/ ∞ Queue and Lower Bound for the maximal Dater
- Event Graphs
- Reducible and Irreducible Event Graphs
- Event Graphs : Examples
- Event Graphs : proofs
This fact will be used in the next section to get a generic form for the applications. Hence by permuting the indices, we obtain for the matrix in the evolution equation of the event graph the following block structure.
Generalized Jackson Networks
Single Server Queue
Now fora1, we have thanks to Assumption A2 that ensures that the event graph is FIFO : a10≥0. The following lemma gives a new description of the departure process in term of counting functions.
Generalized Jackson Networks
We take the following notation : given a departure process for queue 0 : Σ(0), and departure processes for the queues i ∈ [1, K]: X = {X(i)}1≤i≤K, and an initial number of customers in each queuen(i), we construct the following arrival processesY={Y(i)}1≤i≤K. AandD, the arrival and departure processes of the generalized Jackson network are the unique solution of the fixed point equation.
Generalized Processor Sharing Queues
- The case of Single Server Queue
- Fluid Limit and Bottleneck Analysis
- Maximal Dater Asymptotic
- Rare Events in Generalized Jackson Networks
- Computation of the Fluid Limit
We will denote byXcnthe time to empty the systemJNnc, called maximal dater of the network. Equation (3.15) is the traditional traffic equation of the network in term of number of customers.
Fluid Limit for GPS Queues
- Construction of the Stationary Regime
- Rare Events in GPS Queues
- Some Definitions and Notations
- The Single Big Event Theorem
In the caseρ >1, we can still construct a workload process for the “stable” queues of the GPS system. Denote byWdi(D)the stationary workload of queuediwhen queues that are not inDcontinuously claim their full share of the link rate. We proceed now to the analyze of the effect of a very big service of type j when condition (3.41) is not satisfied.
Asymptotics of Subexponential Max Plus Networks : the Stochastic Event Graph
Stochastic Assumptions
We will also adopt the following notations : – ifj∈Ci, we denoteγ(j)=γi;. for all transitionsi, the subset of transitions jsuch that there is a directed path inGfromi tojis denoted[≥i];. MoreoverNxwill denote a non-deceasing integer-valued function tending to infinity such that for all finite real numbersb,. The only difference lies in the fact that Condition (AA) in [14] has to be replaced by (AA’), defined in Lemma 17.
Exact Tail Asymptotic
The proof is omitted but uses the same arguments as the proof of Theorem 8 in [14].
Two Technical Lemmas
Tails in Generalized Jackson Networks with Subexponential Service Time Distri-
- Stochastic Assumptions
- Main Result
- Technical Conditions
- Single Big Event Theorem
- Fluid Limit
- Computation of the Exact Asymptotics
- Proof of Corollary 1
More insights into the shape of the domain will be given in Section 4.3.6. which corresponds to the exact asymptotic of Theorem 9 of [14]. The left-hand part of the definition ofKnj depends on{E(k)}0k=−n+1and the right-hand part depends only onE(−n), hence we have. Thanks to Corollary 1, we know that the tail asymptotic of the maximal dater is linked to the quantityS(j)defined by.
Tails in GPS Queues with Subexponential Service Time Distributions
- Stochastic Assumptions
- Big Event Theorem
- Computation of the Exact Asymptotics
- Some Extensions
We can find a non-increasing sequence ǫn →0such thatnǫn → ∞and such that the probabilities of the following events tend. The end of the proof is a repetition of the proof of last corollary and is skipped. In [21], the authors deal with a possibly unstable GPS system and derive the tail asymptotic of the stable queues.
Towards an Extension of the Single Big Event Theorem
In [5] Anantharam, Heidelberger and Tsoucas use quasi-reversibility arguments (see Kelly [64]) to study rare event in the case of Jackson networks. In the first part, we extend this result by considering instead of the additive processSn, a sub- additive process Y[1,n]. We will show in the second part that the monotone-separable framework allows us to derive the tail asymptotics for ”global” variable of the stationary version of such networks.
Tail asymptotics for the supremum of an independent subadditive process
Framework and main result
Even in the exponential case, the formulation of the rate function is original and seems more explicit than the rate function derived in [59]. A first difference with the additive case is that it is possible thatP(M > x)>0 for anyx >0whileθ∗ =∞: consider the following subadditive process,. In the subadditive case, this not anymore true and Assumption (A3) is needed for Theorem 11 to hold.
Beyond the G¨artner-Ellis theorem
We end this section by showing that the information given by the scaled moment generating function is not enough to prove a LDP. We modify our example in order to get two independent subadditive processes with the same scaled moment generating function but with different rate functions. Hence the processesZ[1,n]andZ¯[1,n]have the same scaled moment generating function but they clearly have different rate functions as shown on Figure 5.2.
Proofs
We have (with the convention that the constantAdiffers from line to line but is always finite), Eh. The functionθ 7→ Λ(θ)is convex, hence the left-hand derivatives Λ′(θ−)and the right-hand derivatives Λ′(θ+) exist for allθ > 0. SinceΛn(defined in (5.9)) is convex and differentiable in 0, we haveΛn(θ)≥Λ′n(0)θand taking the limit on both sides, we get.
Large deviations for monotone-separable networks
Tail asymptotics of the maximal dater
In the rest of the paper, we will make the following assumptions (that are of course compatible with previous stationary ergodic assumptions). Like in the study of the stability of the network, it turns out that the right quantity to look at isZ[m,n](Q)whereQis the degenerate input point process with all its point equal to 0. There is no general result for the tail asymptotics of the maximal dater of a monotone separable network.
Upper G/G/1/ ∞ queue and lower bound for the maximal dater
It is relatively easy to see that under our light-tailed assumption the stationary maximal dater Z will be light-tailed (see Corollary 3 in [14]). It is the goal of the third part of this paper to show that it is actually possible to calculate the logarithmic moment generating functionΛZ for various categories of networks. Then we haveN′ ≥N andX[m,n−1](N′)≤Tn′, hence by the external monotonicity, the separa- bility and the homogeneity properties, we have.
Proofs of the tail asymptotics
Case of study I : (max, plus)-linear systems
Tail asymptotics for (max,plus)-linear networks
In a queueing context, the sequence of matrices {An(ℓ, ℓ)} corresponds to a specific ”com- ponent” of the network. We should stress that we made the assumptions that each component of the vectorζnare independent of each other. Hence for ℓ = 1,2,3, θℓ corresponds to the exponential rate of decay for the supremum of the random walk :supnPn.
Computation of the moment generating function
For small values of λ, the tail of the sojourn time is determined by the total service requirement of a single customer. Moreover thanks to the fixed structure assumption, there exists N such that forn≥ N, we have M[1,n](i,j)>−∞for alliandj, henceΛ(i,j)(θ, n)>−∞and we have. The arguments for the case θ < 0 exactly parallels the one just given, but exploits (min,plus)-.
Case of study II : Large Deviations for generalized Jackson networks
Generalized Jackson networks
The sequences{σj(k)}j≥1and{νj(k)}j≥1, where k ranges over the set of stations, are called the driving sequences of the network. Consider the case n(0) = ∞, we will use the following notation for each of these counting functions. We recall here some results of [78] concerning large deviations of renewal processes and show that our assumptions on the rate function (5.31) are satisfied in the i.i.d case.
An extension of the contraction principle
Moreover thanks to the contraction principle, {H1(Xn, Yn)}nand{H2(Xn, Yn)}nsatisfy LDPs with the good rate functions. Thanks to the lower semicontinuity property ofI˜X,Y, we can find for anyδ >0, anǫ >0such that. To see that the last assertion is true, we show that for any open setO ⊂F, we have,.
Extension of Ψ to piece-wise linear Jackson networks
For a piece-wise linear Jackson network, there exists an unique solution of the fixed point equation (5.33). We still denote byΨthe mapping that to any piece-wise linear Jackson networkJNassociates the corresponding couple(A,D). LetDJNbe the subspace ofEof piecewise linear Jackson networks : namelyJN= (S,P,N)∈ DJNif the functionsu7→N(i)(u), u7→S(i)(u)andu7→P(i,j)(u)are piecewise linear functions such thatρ( ˙P(t))<1for allt≥0andN(i) =0fori /∈S.
Sample path large deviations
The idea to construct the sequence{JNn}nis to consider the piecewise approximation of the fixed point equation (5.33). Let{JNn= (Sn,Pn,Nn)}nbe a sequence inDNJNsuch thatJN˙ nconverges toJN.˙ We consider the case of the sequence of processes{Sn}nin details (we can restrict ourselves to the one dimensional case). The sequence of processes{Qn}nsatisfies a LDP inD(RK . +)with good rate function that is finite forQabsolutely continuous and such thatQ(0) = 0and given by.
Appendix
To the best of our knowledge, there exist few results on the tail asymptotic of the end-to- end delay in a network setting. We consider the steady state distribution of the end-to-end delay of a tagged flow in queueing networks where some of the queues have self-similar cross traffic. We show that the end-to-end delay of the tagged flow in a tandem queueing network is com- pletely dominated by one of the queues.
Stochastic Assumptions
Taking Cross Traffic into Account
We assume that at least one of the queues have the Hurst parameter that is strictly greater than 0.5. If several queues have the same maximal Hurst parameter, then we have to compare the ratio (1−ρ)σ H to determine the dominant queue, whereρis the load of the queue. We also provide upper and lower bounds on the constant that determines the scale parameter of the corresponding Weibull distribution.
Model
We show that the end-to-end delay is still asymptotically Weibullian with the same shape parameter. This means that the matrices{An, Bn}and vectors that are used in the recursion are obtained via two applicationsf andgsuch that. In what follows by feed-forward network, we will understand an event graph such that each com- munication class is made of only one timed transition.
Model Description and Stochastic Assumptions
Under this condition we know that the maximal dater of the event graph is finite a.s.
Logarithmic Tail Asymptotic : the General Case
- Main result
- First result with deterministic arrival times
- Borell’s Inequality
- Auxiliary Results
- Proof of Property 28
- Bounds on σ x 2
- From deterministic times to random arrival times
Based on (6.6), to study the tail asymptotic for Z, it suffices to focus on the supremum of the following centered Gaussian process. The bound of Lemma 54 is tight in the sense that there are cases for which we have. Thanks to inequalities (6.20) and (6.19), we have proved Theorem 15 in the specific case of deter- ministic arrival times.
Logarithmic Tail Asymptotic : the Feed-Forward Case
Main result
Estimates for the probability of ruin with special emphasis on the possibility of large claims. Large deviations for global maxima of independent superadditive processes with negative drift and an application to optimal sequence alignments. Fluid limit of generalized Jackson queueing networks with stationary and ergo- dic arrivals and service times.