Waarom kleintjes niet altijd voor moeten gaan (maar vaak wel)

Waarom kleintjes niet altijd voor moeten gaan (maar vaak wel) Sindo N´ u˜ nez Queija Universiteit van Amsterdam & Centrum voor Wiskunde en Informatica + Maaike Verloop en Sem Borst

OVERZICHT: Wachtrijen en bedieningsdisciplines Data-netwerken Benaderingen van optimale strategie¨ en

Wachtrijen

Voorbeeld: masseur van een grote voetbalclub “Aankomsten”: gemiddeld λ per minuut Massageduur hangt af van de lichaamsgrootte: gemiddeld β (minuten), variantie σ 2 Belasting: ρ := λβ < 1 Bedienen in volgorde van aankomst?

R. N´ u˜ nez-Queija

Leve de Wiskunde – 12 april 2013 1

Bedieningsdiscipline

Bedienen in volgorde van aankomst: 

ρ ρ  1 + gemiddeld aantal klanten = 1−ρ

σ2 β2



−1 

2

 

ρ Alternatieven: “Processor sharing” of “laatste eerst”: 1−ρ Wat is het best? Als je de bedieningsduur kent: Kleinste Eerst! [Schrage’68]



Waarom eerst de kleinste? Werkvoorraad:

Volgorde van bediening doet er niet toe voor de werklast! ⇒ Concentreer het werk in de grootste klanten, door de kleinsten eerst te bedienen!



Illustratie Werkvoorraad

Aantal klanten op gegeven moment

⇒ Reduceer aantal klanten zonder werkvoorraad te veranderen....



Volgorde van bediening bepalen in de praktijk De exacte grootte van een klant kennen we vaak niet Als we de reeds verkregen bedieningsduur weten en de bedieningsduurverdeling dan is het optimaal om te bedienen volgens

• de volgorde van aankomst: voor bijvoorbeeld Gamma verdelingen

• de minst verkregen bediening: voor bijvoorbeeld Pareto en hyperexponenti¨ ele verdelingen

• “Klimov” indexen: in het algemeen



Data-netwerken

• capaciteit van meerdere knooppunten tegelijk nodig • email, VoIP (telefonie), video, muziek, live streaming • IDEE: laat de knooppunten eerst de kleintjes doorsturen R. N´ u˜ nez-Queija


Data-netwerken

Concentreer je op het pad dat door een collectie van stromen wordt doorkruist


Leve de Wiskunde – 12 april 2013 6-1

Data-netwerken

Concentreer je op het pad dat door een collectie van stromen wordt doorkruist

⇒ lineair netwerk 6-2

Lineair netwerk gerepresenteerd door wachtrijen

S0(t) + Si(t) ≤ 1,

i = 1, . . . , L.

Klasse i: elke “klant” in rij i vertegenwoordigt een stroom door “route” i



Stabiliteit in het netwerk

Zeker nodig: ρ0 + ρi < 1 voor alle i = 1, . . . , L Niet voldoende! Bijv.: prioriteit voor klassen 1 & 2: Nodig: ρ0 < (1 − ρ1)(1 − ρ2) Ook als 1 & 2 kleiner zijn Op

lange

paden:

ρ0

<

QL i=1 (1 − ρi )




Zeker nodig: ρ0 + ρi < 1 voor alle i = 1, . . . , L Niet voldoende! Bijvoorbeeld: prioriteit voor klassen 1 & 2: Nodig: ρ0 < (1 − ρ1)(1 − ρ2) Ook als 1 & 2 kleiner zijn Op

lange paden: QL i=1 (1 − ρi )


ρ0

<



Zeker nodig: ρ0 + ρi < 1 voor alle i = 1, . . . , L Niet voldoende! Bijvoorbeeld: prioriteit voor klassen 1 & 2: Nodig: ρ0 < (1 − ρ1)(1 − ρ2) Ook als 1 & 2 kleiner zijn Op

lange paden: QL i=1 (1 − ρi )


ρ0

<


Wat nu? • Zoek naar de structuur van optimale strategie¨ en

• Bepaal goede benaderingen

Speciaal geval: exponenti¨ ele bedieningsduur verdelingen

• σ2 = β 2

• Geheugenloos: P (B > x + y|B > x) = P (B > y) δ • P (x < B < x + δ|B > x) ∼ E[B]



Bedieningsdiscipline

Bedienen in volgorde van aankomst: 

ρ ρ  1 + gemiddeld aantal klanten = 1−ρ

σ2 β2



−1 

2

 

ρ Alternatieven: “Processor sharing” of “laatste eerst”: 1−ρ Wat is het best? Als je de bedieningsduur kent: Kleinste Eerst! [Schrage’68]






• σ2 = β 2







• σ2 = β 2




Wat nu? • Zoek naar de structuur van optimale strategie¨ en • Bepaal goede benaderingen

Speciaal geval: exponenti¨ ele bedieningsduur verdelingen • σ2 = β 2 • Geheugenloos: P (B > x + y|B > x) = P (B > y) δ • P (x < B < x + δ|B > x) ∼ E[B]

1 • µ = E[B] R. N´ u˜ nez-Queija


Na¨ıeve aanpak Maximaliseer de vertrekintensiteit: • Vergelijk µ0 1N0 (t)>0 met µ1 1N1 (t)>0 + µ2 1N2 (t)>0 en kies het maximum alle capaciteit naar 0 alle capaciteit naar 1 & 2 • Optimaal op de korte termijn: kleintjes eerst! • Wat kan er dan mis gaan? bijvoorbeeld: als µ1 > µ0 en N2 (t) = 0 capaciteit in knooppunt 2 wordt helemaal niet gebruikt als N0 (t) > 0 een strategie die 0 bedient heeft dan altijd minder werk in knooppunt 2 en zal dus eerder het systeem leeg hebben! • Hebben al gezien dat dit instabiel kan zijn als zowel µ1 > µ0 en µ2 > µ0 (prioriteit voor 1 & 2) Goede balans vinden tussen het concentreren van werk in de grote klanten en het verlagen van de totale hoeveelheid werk! R. N´ u˜ nez-Queija






Wanneer is de keuze makkelijk? Propositie Klasse 0 bedienen is altijd optimaal als µ1 + µ2 ≤ µ0 Propositie Klasse i = 1, 2, bedienen als ze er beide zijn, en anders klasse 0 bedienen is optimaal als µ1 + µ2 ≥ µ0 ≥ max{µ1, µ2}



Algemene structuur van de optimale keuze I Focus op µ0 < µ1 • Makkelijk: Als zowel klasse 1 en 2 er zijn, moeten die worden bediend want µ0 ≤ µ1 + µ2

• Op een gegeven moment is N2(t) = 0: klasse 0 bedienen verlaagt de werklast het meest klasse 1 bedienen concentreert het werk in de groten

• Doel: het gemiddelde minimaliseren



Algemene structuur van de optimale keuze II Propositie Als klasse 2 leeg is, dan is er een optimale “switching curve”

Het precies bepalen van de switching curve is vaak ondoenlijk



Kijk naar de “fluid” limiet dwi (t) = ρi − si (t), for i = 0, 1, 2, dt wi (t) ≥ 0, for i = 0, 1, 2, s0 (t) + si (t) ≤ 1, for i = 1, 2, si (t) ≥ 0, for i = 0, 1, 2.



De makkelijke gevallen in de fluid limiet (ρ1 ≤ ρ2) • Als µ1 + µ2 ≤ µ0 : triviaal • Als µ1 + µ2 ≥ µ0 ≥ µ1 , µ2



Moeilijkere gevallen (ρ1 ≤ ρ2 ) • µ1 ≥ µ0 ≥ µ2

switching curve n1 =


µ1 ρ2 −ρ1 µ2 n µ1 +µ2 −µ0 µ0 1−ρ0 −ρ2 0


Moeilijkere gevallen (ρ1 ≤ ρ2 ) • µ1 ≥ µ0 ≥ µ2

switching curve n1 =

µ2 µ1 ρ2 −ρ1 n µ1 +µ2 −µ0 µ0 1−ρ0 −ρ2 0

• µ1 , µ2 ≥ µ0

ρ2 −ρ1 switching-curve n1 = 1−ρ n0 or if n2 > 0 0 −ρ2 (stricte prioriteit voor 2!)



Lineaire benaderingen als ρ1 6= ρ2

Optimale strategie en lineaire “fluid” approximatie



Lineaire benaderingen als ρ1 6= ρ2

Optimale strategie en lineaire “fluid” approximatie

Hoe goed doet de “fluid” approximatie het:



Is het altijd “mooi lineair”?



Is het altijd “mooi lineair”? NEE....



Wat als ρ1 = ρ2? (Centrale Limiet Stelling) De lineaire strategie is misschien niet eens stabiel!!! • µ1 , µ2 ≥ µ0 • beide “fluid” switching curves liggen op de horizontale as • probleem als 0 de grootste is...



Wat als ρ1 = ρ2? (Centrale Limiet Stelling) De lineaire strategie is misschien niet eens stabiel!!! • µ1 , µ2 ≥ µ0 • beide “fluid” switching curves liggen op de horizontale as • probleem als 0 de grootste is...

• onder de switching curve heeft N1 geen “drift” • in het “uitgezoomde proces” lineaire drift voor N0 Brownse beweging voor N2 • de switching curve kan vele keren van onder worden “geraakt” en elke keer verliest knooppunt 2 capaciteit R. N´ u˜ nez-Queija


Lastiger dan de “lineaire gevallen”maar soms heel relevant

20

CLT scaling below the switching curve w ˜0 (t) = w ˜0 (0) − (1 − ρ0 − ρ1 )t ˜ 1n (nt) W ˜ 1n (nt) − W ˜ 2n (nt)) lim = lim 1(W √ ˜ 1n (nt)≥W ˜ 2n (nt)) (W n→∞ n→∞ n b1 = 1(BM (t)+ b1 ≥0) (BM (t) + ), µ1 µ1 ˜ 2n (nt) −W ˜ 1n (nt) − W ˜ 2n (nt)) = lim 1(W lim √ ˜ 2n (nt)≥W ˜ 1n (nt)) (W n→∞ n→∞ n b1 = 1(BM (t)+ b1 ≤0) (BM (t) + ), µ1 µ1 BM (t) is a Brownian motion with • variance θ2 := λ1 θ12 + λ2 θ22 • θj2 = Var(Bj ) Main ingredient in the proof: ˜ in (t) = W ˜ in (0) + Ai (0, t) − B ˜i (0, t) W ˜1 (0, t) = B ˜2 (0, t), B



CLT scaling below the switching curve w ˜0 (t) = w ˜0 (0) − (1 − ρ0 − ρ1 )t ˜ 1n (nt) W ˜ 1n (nt) − W ˜ 2n (nt)) lim = lim 1(W √ ˜ 1n (nt)≥W ˜ 2n (nt)) (W n→∞ n→∞ n b1 = 1(BM (t)+ b1 ≥0) (BM (t) + ), µ1 µ1 ˜ 2n (nt) −W ˜ 1n (nt) − W ˜ 2n (nt)) = lim 1(W lim √ ˜ 2n (nt)≥W ˜ 1n (nt)) (W n→∞ n→∞ n b1 = 1(BM (t)+ b1 ≤0) (BM (t) + ), µ1 µ1 BM (t) is a Brownian motion with • variance θ2 := λ1 θ12 + λ2 θ22 • θj2 = Var(Bj ) Main ingredient in the proof: ˜ in (t) = W ˜ in (0) + Ai (0, t) − B ˜i (0, t) W ˜1 (0, t) = B ˜2 (0, t), B



Illustratie

Optimale strategie en de “wortel” strategie



Illustratie

Optimale strategie en de “wortel” Pad voor een “wortel” strategie strategie



Waarom kleintjes niet altijd voor moeten gaan (maar vaak wel) Sindo N´ u˜ nez Queija Universiteit van Amsterdam & Centrum voor Wiskunde en Informatica Dank u wel!

Waarom kleintjes niet altijd voor moeten gaan (maar vaak wel)

Recommend Documents