TY - GEN
T1 - Guaranteeing fair service to persistent dependent tasks
AU - Bar-Noy, Amotz
AU - Mayer, Alain
AU - Schieber, Baruch
AU - Sudan, Madhu
N1 - Funding Information:
$Dept. of Computer Science, Columbia University, New York, NY 10027. Email: mayerQcs .columbia.edu. Part of this work was done while the author was at the IBM T. J. Watson Research Center. Partially supported by an IBM Graduate Fellowship, NSF grant CCR-93-16209, and CISE Institutional Infrastructure Grant CDA-90-24735
Funding Information:
Part of this work was done while the author was at the IBM T. J. Watson Research Center. Partially supported by an IBM Graduate Fellowship, NSF grant CCR-93-16209, and CISE Institutional Infrastructure Grant CDA-90-24735
PY - 1995/1/22
Y1 - 1995/1/22
N2 - We introduce a new scheduling problem that is motivated by applications in the area of access and flow-control of high-speed and wireless networks. An instance of the problem consists of a set of persistent tasks that have to be scheduled repeatedly. Each task has a demand to be scheduled "as often as possible". There is no explicit limit on the number of tasks that can be scheduled concurrently. However, such limits gets imposed implicitly by the fact that some tasks are in conflict and cannot be scheduled simultaneously. The conflicts are presented in the form of a conflict graph. We define parameters that quantify the fairness and regularity of a given schedule. We then proceed to show lower bounds on these parameters, and present fair and efficient scheduling algorithms for the special case where the conflict graph is an interval graph. Some of the results presented here extend to the case of perfect graphs and circular-arc graphs as well.
AB - We introduce a new scheduling problem that is motivated by applications in the area of access and flow-control of high-speed and wireless networks. An instance of the problem consists of a set of persistent tasks that have to be scheduled repeatedly. Each task has a demand to be scheduled "as often as possible". There is no explicit limit on the number of tasks that can be scheduled concurrently. However, such limits gets imposed implicitly by the fact that some tasks are in conflict and cannot be scheduled simultaneously. The conflicts are presented in the form of a conflict graph. We define parameters that quantify the fairness and regularity of a given schedule. We then proceed to show lower bounds on these parameters, and present fair and efficient scheduling algorithms for the special case where the conflict graph is an interval graph. Some of the results presented here extend to the case of perfect graphs and circular-arc graphs as well.
UR - http://www.scopus.com/inward/record.url?scp=85030060536&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85030060536&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85030060536
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 243
EP - 252
BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PB - Association for Computing Machinery
T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Y2 - 22 January 1995 through 24 January 1995
ER -