loading...
Optimal Multi-Channel Data Allocation with Flat Broadcast Per Channel
Santa Fe, New Mexico April 26-April 30
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2004.130292418th International Parallel and Distr ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
A. A. Bertossi, University of Bologna
M. C. Pinotti, University of Perugia
S. Ramaprasad, Brown University
R. Rizzi, University of Trento
M. V. S. Shashanka, Boston University
Broadcast is an efficient and scalable way of transmitting data to an unlimited number of clients that are listening to a channel. Cyclically broadcasting data over the channel is a basic scheduling technique, which is known as flat scheduling. When multiple channels are available, partitioning data among channels in an unbalanced way, depending on data popularities, is an allocation technique known as skewed allocation. In this paper, the problem of data broadcasting over multiple channels is considered assuming skewed data allocation to channels and flat data scheduling per channel, with the objective of minimizing the average waiting time of the clients. Several algorithms, based on dynamic programming, are presented which provide optimal solutions for N data items and K channels. Specifically, for data items with uniform lengths, an O(NK logN) time algorithm is proposed, which improves over the previously known O(N2K) time algorithm. When K ≤ 4, faster O(N) time algorithms are exhibited. Moreover, for data items with non-uniform lengths, it is shown that the problem is NP-hard when K = 2, and strong NP-hard for arbitrary K. In the former case, a pseudo-polynomial algorithm is discussed, whose time is O(NZ) where Z is the sum of the data lengths.
Index Terms:
Wireless communication, data broadcast, multiple channels, skewed allocation, flat scheduling, average waiting time, dynamic programming
Citation:
A. A. Bertossi, M. C. Pinotti, S. Ramaprasad, R. Rizzi, M. V. S. Shashanka, "Optimal Multi-Channel Data Allocation with Flat Broadcast Per Channel," ipdps, vol. 1, pp.18b, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Papers, 2004
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions