1 of 22

Relative Arrivals: A New Drift Method for Time-Varying Arrivals

 

SNAPP Seminar - 10/9/23

1

2 of 22

Markov-modulated arrivals

Common situation: light load at baseline, occasional bursts of arrivals

Standard in many application areas: Computing, health care, retail, etc.

SNAPP Seminar - 10/9/23

2

Arrival rate

Time

Average arrival rate

3 of 22

This Talk: Two-level Arrivals Queue

SNAPP Seminar - 10/9/23

3

 

 

 

 

 

Arrival rate

Time

 

 

 

 

 

 

4 of 22

Prior work on two-level arrivals

SNAPP Seminar - 10/9/23

4

Computational Methods

Generating functions [Yechiali & Naor ‘71], [Gupta et al. ‘06], …

​

Matrix analytic methods [Neuts ‘78], [Ramaswami ‘80], [Latouche & Ramaswami’99], …

Symbolic Results

Heavy-traffic, semi-closed form [Mou & Maguluri ’20]

​

Structural and monotonicity results [Gupta et al. ‘06], [Vesilo, Harchol-Balter& Scheller-Wolf’21]

 

5 of 22

Outline

  •  

SNAPP Seminar - 10/9/23

5

6 of 22

Drift Method: Background

  •  

SNAPP Seminar - 10/9/23

6

7 of 22

Drift method: M/M/1

  •  

SNAPP Seminar - 10/9/23

7

8 of 22

Key idea of Drift Method

  •  

SNAPP Seminar - 10/9/23

8

 

 

 

9 of 22

Challenge: Drift under varying arrival rates

  •  

SNAPP Seminar - 10/9/23

9

 

Time

10 of 22

Outline

  •  

SNAPP Seminar - 10/9/23

10

11 of 22

 

  •  

SNAPP Seminar - 10/9/23

11

 

 

 

12 of 22

New idea: Relative arrivals

  •  

SNAPP Seminar - 10/9/23

12

Time

10

8

6

4

2

0

Expected arrivals

0

3

6

9

12

15

 

 

 

 

 

 

13 of 22

Alternate perspective: Relative value function

  •  

SNAPP Seminar - 10/9/23

13

 

Time

14 of 22

Relative arrivals smooth out drift

  •  

SNAPP Seminar - 10/9/23

14

 

 

15 of 22

Outline

  •  

SNAPP Seminar - 10/9/23

15

16 of 22

Result: Mean queue length characterization

  •  

SNAPP Seminar - 10/9/23

16

Arrival moments

17 of 22

Calculations of values in two-level system

  •  

SNAPP Seminar - 10/9/23

17

 

 

 

 

Dominates in heavy traffic

18 of 22

Bounds on empty-queue behavior

  •  

SNAPP Seminar - 10/9/23

18

 

 

 

 

19 of 22

Bounds vs. Simulation

SNAPP Seminar - 10/9/23

19

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fast switching bound

Slow switching bound

 

20 of 22

Generalization: Markovian arrivals, Markovian service

  •  

SNAPP Seminar - 10/9/23

20

21 of 22

Future directions

  •  

SNAPP Seminar - 10/9/23

21

22 of 22

Conclusion

Markov-modulated arrivals, e.g. two-level arrivals:

SNAPP Seminar - 10/9/23

22

 

 

 

 

 

Time

10

8

6

4

2

0

Expected arrivals

0

3

6

9

12

15