Approximations to GPS

• Among packets that have arrived at time t:

• Consider all such packets that are at the heads of their queues

  • pik, pjk’ --- at heads of queues (in the GPS schedule)

• Amount remaining to be transmitted: lik, ljk’ (in the GPS schedule)

• Lemma: If (lik / ?i) ? (ljk’ / ?j) then pik completes no later than pjk’ in the GPS schedule

• Proof:

Previous slide

Next slide

Back to first slide

View graphic version