Broadcast scheduling: when fairness is fine
Jeff A. Edmonds, Kirk R. Pruhs · 2002
We investigate server scheduling policies to minimize user perceived latency in a client-server system where the server uses broadcast communication. We show that no O(1)-competitive online algorithms exist for this problem. We consider the intuitive algorithm BEQUI that broadcasts all requested files at a rate proportional to the number of outstanding requests for that file. We show that BEQUI is an O(1)-speed O(1)-approximation algorithm. We give another algorithm BEQUI-EDF, and show that BEQUI-EDF is also an O(1)-speed O(1)-approximation algorithm. However, BEQUI-EDF has the advantage that it preempts each broadcast on average at most once and will never preempt if the data items have unit size.