GPS: Delay (Di*) and Backlog (Qi*) bounds
To minimize the service to connection i which is continually backlogged during [t, t), every other connection j should get as much share as possible
I.e., each j should “arrange” its traffic arrivals to be backlogged for as long as possible during [t, t)
Claim: this happens under greedy arrivals -- for any interval [t,t), Si(t, t) ? Si(g)(t, t)
Suppose that Qi becomes fullest at t*, and let to denote the last time prior to t* that Qi was empty
- Qi(t*) ? Ai(to, t*) - Si(to, t*)
- Ai(to, t*) ? Ai(g)(to, t*)
- Si(to, t*) ? Si(g)(to, t*)
- ...