We describe scheduling algorithms for monitoring an information source whose contents change at times modeled by a nonhomogeneous Poisson process. In a given time period of length T, we enforce a politeness constraint that we may only probe the source at most n times. This constraint, along with an optional constraint that no two probes may be spaced less than delta time units apart, is intended to prevent the monitor from being classified as a nuisance to be locked out of the information source. To develop our algorithms, we use a portion of the cost model developed in our earlier work. Our first algorithm assumes a discrete set of N > n possible update times, and uses dynamic programming to identify a provably optimal subset of n of these times at which to probe the server. Our second algorithm is a simple direct search procedure for locally improving any continuous-time schedule with respect to the same cost model. In particular, this improvment procedure may be applied to the schedule obtained from our first algorithm. We demonstrate the effectiveness of the algorithms by comparing them with previously-proposed methods, using real-world data feeds and varying preference parameters.
Citation
RUTCOR Research Report RRR 16-2005 RUTCOR, Rutgers University 640 Bartholomew Road, Busch Campus Piscataway, NJ 08854 USA