18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 12
Jitter-Approximation Tradeoff for Periodic Scheduling
Santa Fe, New Mexico
April 26-April 30
ISBN: 0-7695-2132-0
We consider an asymmetric wireless communication setting, where a server periodically broadcasts data items to different mobile clients. The goal is to serve items in a prescribed rate, while minimizing the energy consumption of the mobile users. Abstractly, we are presented with a set of jobs, each with a known execution time and a requested period, and the task is to design a schedule for these jobs over a single shared resource without preemption. Given any solution schedule, its period approximation is the maximal factor by which the average period of a job in the schedule is blown up w.r.t. its requested period, and the jitter ratio is roughly the maximal variability of times between two consecutive occurrences of the same job. Schedules with low jitter ratio allow the mobile devices to save power by having their receivers switched off longer. In this paper we consider a scenario where clients may be willing to settle for non-optimal period approximation so that the jitter ratio is improved. We present a parametric jitter-approximation tradeoff algorithm that allows us to choose various combinations between jitter optimality and period optimality for any given set of jobs.
Citation:
Zvika Brakerski, Boaz Patt-Shamir, "Jitter-Approximation Tradeoff for Periodic Scheduling," ipdps, vol. 13, pp.222a, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 12, 2004