A Parallel Hill Climbing Algorithm for Pushing Dependent Data in Clients-Providers-Servers Systems

摘要

The up-link bandwidth in satellite networks and in advanced traffic wireless information system is very limited. A server broadcasts data files provided by different independent providers and accessed by many clients in a round-robin manner. The clients who access these files may have different patterns of access. Some clients may wish to access several files in any order (AND), some wish to access one out of several files (OR), and some clients may access a second file only after accessing another file (IMPLY). The goal of the server is to order the files in a way that minimizes the access time of the clients given some a priori knowledge of their access patterns. An appropriate clients-servers model was recently proposed by Bay-Noy, Naor and Schieber. They formulated three separate problems and proposed an algorithm that evaluates certain number of random permutations and chooses the one whose access time is minimized. In this paper, we formulate a combined AOI (AND-OR-IMPLY) problem, and propose to apply a parallel hill climbing algorithm (to each of the four problems), which begins from certain number of random permutations, and then applies hill climbing technique on each of them until there is no more improvement. The evaluation time of neighboring permutations generated in hill climbing process is optimized, so that it requires O(n) time per permutation instead of O(n~2) time required for evaluating access time of a random permutation, where n is the number of files the server broadcasts. Experiments indicate that the parallel hill climbing algorithm is O(n) times faster that random permutations method, both in terms of time needed to evaluate the same number of permutations, and time needed to provide a high quality solution. Thus the improvement is significant for broadcasting large number of files.