A delicate prologue to liquid and dissemination limits for lines

0
0
1839 days ago, 683 views
PowerPoint PPT Presentation

Presentation Transcript

Slide 1

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

Slide 2

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.

Slide 3

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

Slide 4

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?

Slide 5

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 .

Slide 6

Fluid Approximation

Slide 7

Fluid Approximation

Slide 8

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?

Slide 9

n=10

Slide 10

n=100

Slide 11

n=10000

Slide 12

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.

Slide 13

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 .

Slide 14

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:

Slide 15

n=10

Slide 16

n=100

Slide 17

n=1000

Slide 18

Problems with liquid cutoff points

Slide 19

Problems with liquid points of confinement

Slide 20

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?

Slide 21

n=100

Slide 22

n=1000

Slide 23

n=10000

Slide 24

n=1,000,000

Slide 25

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

Slide 26

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.

Slide 27

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

Slide 28

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,

Slide 29

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.

Slide 30

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.

Slide 31

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

Slide 32

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

SPONSORS