Service curves

At t=0, pi1 arrives, with size (1+e)

At t=2, pi2 arrives, with size 1

Algorithm X:

• over [0,2) at rate 1/2

• an additional e service at time 2

• at rate 2/3 over [2, )

Algorithm Y:

• over [0,2) at rate 1/2

• an additional e service at time 2 + d

• at rate 2/3 over [2, )

For algorithm Y, backlogged intervals start at {0}

Problem: Algorithm X observes the service curve, but Algorithm Y doesn’t

For algorithm X, backlogged intervals start at {0,2}

Previous slide

Next slide

Back to first slide

View graphic version