An Overview of The Application of Heavy Traffic Theoryand Brownian Approximations to the Control of MulticlassQueueing NetworksElif Uysal1Stochastic Networks• Jobs (packets, customents), servers (resources), queues (buffers)• Often cannot be analyzed exactly• Fluid and diffusion models as approximation methods• Theory developed by Riemann, Harrison, Williams, Bramson, ... usingfluid and diffusion approximations to analyze stability, performance ofopen multiclass HL queueing networks2Goals of this Overview• Heavy traffic (HT) scaling• HT analysis technique• Convergence to Brownian motion (BM)• Resource pooling (RP)• State-space collapse (SSC)3Brownian Motion• A stochastic process B(t) is a standard Brownian Motion if and only if ithas– Continuous sample paths– Stationary increments: B(t1) − B(t0) depends only on t1− t0– Independent increments: B(t1) − B(t0), ..., B(tn) − B(tn−1) areindep. for any 0 ≤ t1<t2<...<tn< ∞– Gaussian increments: B(tn) − B(tn−1) ∼N(0,tn−1− tn)• Y (t)=Y (0) + µt + σB(t) is a Brownian motion with drift µ and varianceσ24General Procedure of Heavy Traffic AnalysisMethodology developed by [Reimann 1984], [Harrison 1988] and [Harrison andWilliams 1992]:1. Set up the dynamic scheduling problem, define “heavy traffic”2. Derive a limiting Brownian control problem that plausibly approximatesthe original problem (after some scaling.)3. Solve the Brownian control problem (much simpler than originalproblem)4. Interpret the solution in original context5. Ideally, prove that proposed solution is asymptotically optimal in theoriginal problem.5A Parallel-Server System with Resource Pooling (Harrisonand Lopez 1999)λλλλ1234µµµ123µ75486µµµµ123m classesn activitiesl servers• r job classes, n activities, l servers• λi: avg. arrival rate of classijobs;µj: reciprocal of mean service timefor activityj•Queueiincurs ”holding cost” at a rateciper unit time per job in queue6A Parallel-Server System with Resource Pooling (Harrisonand Lopez 1999)• Problem: dynamically allocate jobs to servers to minimize avg holdingcost per unit time7Heavy Traffic?• Not obvious: multiple queues can share servers• Consider:minimize ρsubject to Rx = λAx ≤ ρex, ρ ≥ 0where Aij=1if server i serves activity j, Aij=0o.w.Rij= µjif server i serves activity j, Rij=0otherwisex is n ×1 the vector of fractions of times allocated to each activity by its server8Heavy Traffic• Heavy traffic assumption: The data (R, A, λ) of the staticallocation problem are such that– its solution (x∗,ρ∗) is unique;– ρ∗=1, and– Ax∗= e.• x∗: nominal processing plan• Activities for which x∗j> 0 are basic activities• When ρ∗=1, the system manager is just able, using the basic activities,to process jobs of the various classes at the required average rates9Dynamic Scheduling QuestionCan server work assignments be dynamically adjusted, relative to the nominalprocessing plan x∗, to minimize cost?Recall: queues have different holding cost rates10Resource PoolingDefinition: Communicating Servers. Server k communicates directly withserver kif there exist basic activities j and jsuch that j = j(i, k) andj= j(i, k) for some class i.Server k communicates with server kif there exist servers k1,...,kwsuch thatk1= k, kw= k, and kαcommunicates directly with kα+1for allα =1,...,w− 1.11Resource Pooling• Servers can be partitioned into disjoint communicating sets• 1 Partition = CRP• Intuition: Under CRP, can shift load from one queue to another• Perhaps in heavy traffic scaled system this can be done in zero time?12Wait: We Need to Define HT Scaling• Xr(t)=X(rt)/√r• F0i(t): number of arrivals into buffer i in [0,t]• Fji(t): number of departures from buffer i resulting from the first t timeunits devoted to activity j by its server• The scaled process F0(rt)/√r − λt√r converges weakly as r →∞to aBrownian motion with zero limit and with an m ×m covariance matrix Γ0• “Shrink time, expand space”13Convergence to Brownian Motion• For all j and t ≥ 0Fj(rt)/√r − Rjt√rconverge weakly to BM with zero drift, covariance matrix Γj14Policy and System Dynamics• Scheduling Policy: n-dimensional stochastic process T = {T (t),t≥ 0}• Tj(t): total time devoted to activity j over [0,t]• The m-dimensional jobcount process:Q(t)=F0(t) −nj=1Fj(Tj(t)),t≥ 0The cost rate process:C(t)=cQ(t)15Queuing System DynamicsUnder the HT assumption• Define the centered allocation: V (t)=x∗t − T (t)• Define ”cumulative idleness process” I(t): vector of cumulative idle timefor the n activities• All components of I(t) must be nondecreasing for T to be an admissiblepolicy• Scaled processesYr(t)=V (rt)/√rZr(t)=Q(rt)/√rUr(t)=I(rt)/√r and,ξr(t)=C(rt)/√r16Limiting Brownian control problem• Under HT assumption, as r →∞, the scaled dynamic schedulingproblem is well approximated byZ(t)=X(t)+RY (t)where X = {X(t),t≥ 0} is the m-dimensional Brownian motion withzero drift, covariance matrix Γ=Γ0+bj=1x∗jΓj[Reiman 1984]• Note that Y (t) is our n-dimensional control• The problem:Y is non-anticipating with respect to XZ(t) ≥ 0 for all t ≥ 0, andU is nondecreasing with U(0) ≥ 0Z(t)=X(t)+RY (t) for all t ≥ 0U(t)=KY (t)for allt ≥ 017How big is the state space of this problem?• The original state Q(t) is an m-dimensional vector• But the limiting Brownian problem will have a 1-dimensional state space!• State space collapse18State Space Collapse [Harrison and Van Mieghem 1997]• In the Brownian control problem apply an immediate impulse controlY (0) = δ at t =0.• Then, initial values Z(0) = z + δ and U(0) = u, where δ = Ry andu = Ky.• The impulse control is admissible only of z + δ ≥ 0 and u ≥ 0• If u =0(i.e. Ky =0), can immediately apply another control incrementof −y which returns the system to state z• Thus, if Ky =0, the control increment y is reversible• Any two state vectors whose difference is a reversible displacement areequivalent!• Summary of the system is given by W (t)=MZ(t), where M is a matrixwhose rows are orthogonal to all reversible displacements, meaningMRy =0ifKy =0.(So,Mgets rid of the reversible component of thesystem state.)19Equivalent Workload Formulation• From SSC, we obtain ”equivalent workload formulation”• state of the system at any time t is described by a workload