PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Bertossi A. A., Pinotti M. C. Skewed allocation of non-uniform data for broadcasting over multiple channels. In: 20th IEEE International Parallel and Distributed Processing Symposium. IPDPS (Rodi, Grecia, 25-29 aprile 2006). Proceedings, pp. ON - LINE. IEEE, Los Alamitos, USA, 2006.
 
 
Abstract
(English)
The problem of data broadcasting over multiple channels consists in partioning data among channels, depending on data popularities, and then cyclically transmitting them over each channel so that the average waiting time of the clients is minimized. Such a problem is known to be polynomially time solvable for uniform lenght data items, while it is computationally intractable for non-uniform lenght data items. In this paper, two new heuristics are proposed which exploit a novel characterization of optimal solutions for the special case of two channels and data items of uniform lenghts. Sub-optimal solutions for the most general case of an arbitrary number of channles and data items of non-uniform lenghts are provided. The first heuristic, called Greedy+, combines the novel characterization with the known greedy approach, while the second heuristic, called Dlinear, combines the same characterization with the dynamic programming technique. Such heuristics have been tested on benchmarks whose popularities are characterized by Zipf distributions. The experimental tests reveal that Dlinear finds optimal solutions almost always, requiring good running times, while Greedy+ is faster and scales well when changes occur on the input parameters, but provides worse solutions than Dlinear.
Subject Wireless communication
Data broadcasting
Desing and analysis of algorithms
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
C.2 COMPUTER-COMMUNICATION NETWORKS


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional