Guaranteeing Fair Service to Persistent Dependent Tasks

Copyright © [1998] by The Society for Industrial and Applied Mathematics. All rights reserved

We introduce a new scheduling problem that is motivated by applications in the area of access and flow-control in 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 are imposed implicitly because some tasks may be in conflict and cannot be scheduled simultaneously. These conflicts are presented in the form of a conflict graph. We define parameters which 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 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.

Also appeared inAnnual ACM-SIAM Symposium on Discrete Algorithms (6th) Proceedings. Philidelphia, PA, Association of Computing Machinery, 1995. p. 243-52

By: Amotz Bar-Noy, Alain Mayer (Columbia Univ.), Baruch Schieber and Madhu Sudan

Published in: SIAM Journal on Computing, volume 27, (no 4), pages 1168-89 in 1998

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .