Proof of bound
work-conserving ==> busy intervals coincide for GPS and A
Let pkt1, pkt2, ..., pktn,... denote the pkts in alg A’s service order
- Let ti denote pkti’s completion time in A’s schedule
- Let ui denote pkti’s completion time in GPS’s schedule
Let pktm denote the last pkt to complete in A’s schedule prior to pktn, such that um > un
- (No such pktm ==> tn ? un )
Then um+1, um+2, ..., un are all < um
pktm chosen instead of pktm+1, pktm+2, ..., pktn ==> they all arrived after (tm - Lm / r) --- when pktm had started service in A’s schedule
All completed ? un (in GPS schedule) ==>
- un ? (tm - Lm / r) + (Lm+1 + Lm+2 + ... + Ln)/r
- ==> tn ? un + Lm / r