0

0

1839 days ago,
683 views

PowerPoint PPT Presentation
A tender prologue to liquid and dissemination limits for lines Presented by: Varun Gupta April 12, 2006

Example : Tandem Queues Interarrival times at line An are i.i.d. arbitrary factors Interarrival times at line C are not any more free – they are "pitifully" subordinate Very hard to examine lines with corresponded input/benefit forms.

Example : Non-stationary Queues The landing procedure changes over a day – high load amid day, low load amid night Difficult to investigate lines with 2 environment states Numerical techniques exist if the entry procedure has certain Markovian properties Exact answers for more mind boggling environment procedures are recalcitrant

Example : Non-stationary Queues Observation: The soujorn times in environment states are much bigger than the administration and interarrival times Question: What is the restricting line length conveyance as the mean environment state visit times get to be limitlessness?

A model for non-stationary lines Define E , a reference situation prepare, as an arbitrary procedure taking qualities in {1,2,..,m}. E n are a group of gradually changing environment prepare characterized by time scaling E as n { n (t): t 0} is the line length handle got by giving the framework a chance to advance as a GI/GI/1 line with mean entry rate 1/ i and mean administration rate 1/ i when E n is in state i .

Fluid Approximation

Fluid Approximation

The Functional SLLN X i : i.i.d. arbitrary factors with mean m , limited difference 2 Let Question: How does the plot of first n fractional entireties carry on as n increments?

n=10

n=100

n=10000

The Functional SLLN Define the ceaseless parameter stochastic process Functional SLLN Note that while SLLN says that at every t , Y n ( t ) unites to mt , FSLLN says that whole example ways of the successions of stochastic procedures Y n join to the non-arbitrary process mt.

Fluid cutoff for the non-stationary line Theorem : If then, where Y is the stochastic liquid process with environment prepare E , deterministic stream rate r i = i - i in state i and beginning substance Y ( 0 )= y .

Example: MMPP/M/1 line Take the reference environment prepare, E , to be the accompanying 2-state ceaseless time Markov chain In state H the line acts like a M/M/1 with administration rate and landing rate H ( H > ) In state L the line acts like a M/M/1 with administration rate and entry rate L ( L < ) Fluid breaking point:

n=10

n=100

n=1000

Problems with liquid cutoff points

Problems with liquid points of confinement

Functional Central Limit hypothesis Define the "focused" incomplete wholes of X i as Central Limit Theorem Define the consistent time handle Question: How does Z n ( t ) carry on as n increments?

n=100

n=1000

n=10000

n=1,000,000

Functional Central Limit hypothesis FCLT (Donsker's Theorem) where B (t) is the standard Brownian movement (with float coefficient 0 and dissemination coefficient 1) Brownian movement with float coefficient and dispersion coefficient 2 is a genuine esteemed stochastic process with stationary and autonomous augmentations having persistent specimen ways where

Functional Central Limit hypothesis While CLT says that for any t, FCLT additionally demonstrates that Z n ( t ) merges to an (a.s.) nonstop stochastic process with free augmentations. Take note of that generally as CLT is a refinement of the SLLN, the FCLT is a refinement of the FSLLN and subsequently is more precise.

Diffusion restrict for the non-stationary line Theorem: If then where Z is a zero-float Brownian movement with dissemination coefficient 2 z relying upon the constraining liquid process, Y , and environment handle, E , as takes after If Y(t)=0, then 2 z = 0 If Y(t)>0 and E(t)=I, then 2 z = i 3 An i 2 + i 3 Si 2

Diffusion restrain for the non-stationary line Proof: Lemma: Let X i be a grouping of positive arbitrary factors. Characterize Let denote the checking procedure with X i as the interarrival times. At that point,

Diffusion restrain for the non-stationary line Proof contd. Utilizing the lemma on last slide, the numbering procedure of landings, V A n (t) in environment i meets to Similarly, the checking procedure for administration culminations joins to Taking the distinction of the above Brownian movements gives as far as possible.

Some ramifications of liquid and dissemination restricts as far as possible just rely on upon the method for the administration and entry forms. Thusly, the changeability of the earth procedure influences the lines more than the inconstancy of the landing and administration forms inside every environment state. The restricting appropriation does not relies on upon minutes higher than the second snapshots of entry and administration forms. The liquid and dispersion confines still hold when the entry and administration procedures are not i.i.d but rather pitifully reliant. This is an outcome of the way that FSLLN and FCLT hold under much weaker conditions.

Conclusions Fluid and Diffusion breaking points are intense instruments that create asymptotically correct conveyances by properly scaling time and additionally space for generally obstinate issues by stripping without end superfluous subtle elements of the measurable procedures included. Building Applications Buffer Provisioning for Network Switches and Routers Scheduling Service for Multiple Sources

Thank you! (If you don't mind enroll for Random Distance Run today! Early enrollment still on)

SPONSORS

No comments found.

SPONSORS

SPONSORS