DocumentCode :
3613829
Title :
A parallel hill climbing algorithm for pushing dependent data in clients-providers-servers systems
Author :
F.J.O. Martinez;J.S. Gonzalez;I. Stojmenovic
Author_Institution :
DISCA, Univ. Nacional Autonoma de Mexico, Mexico City, Mexico
fYear :
2002
fDate :
6/24/1905 12:00:00 AM
Firstpage :
611
Lastpage :
616
Abstract :
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 proposed by Bay-Noy, Naor and Schieber (see Proc. ACM Mobile Computing Conference, MOBICOM 2000, p.222-230, 2000). 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. 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 an 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/sup 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 a large number of files.
Keywords :
"Network servers","Satellite broadcasting","File servers","Bandwidth","Telecommunication traffic","Information systems","Multimedia communication","Processor scheduling","Circuits","Random number generation"
Publisher :
ieee
Conference_Titel :
Computers and Communications, 2002. Proceedings. ISCC 2002. Seventh International Symposium on
ISSN :
1530-1346
Print_ISBN :
0-7695-1671-8
Type :
conf
DOI :
10.1109/ISCC.2002.1021737
Filename :
1021737
Link To Document :
بازگشت