Title: Broadcast scheduling: when fairness is fine
Abstract: 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 out-standing 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.
Publication Year: 2002
Publication Date: 2002-01-06
Language: en
Type: article
Access and Citation
Cited By Count: 32
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot