PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Ardizzoni E., Bertossi A. A., Pinotti M. C., Ramaprasad S., Rizzi R., Madhusudana V. S. Optimal skewed data allocation on multiple channels with flat broadcast per channel. In: Ieee Transactions on Computers, vol. 54 (5) pp. 558 - 572. IEEE Computer Society Washington, DC, USA, 2005.
 
 
Abstract
(English)
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, a data allocation technique is needed to assign data to channels. 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. First, 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šNKlogNŽ time algorithm is proposed, which improves over the previously known OšN2KŽ time algorithm. When K 4, a simpler OšN logNŽ time algorithm is exhibited which requires only OšNŽ time if the data items are sorted. Moreover, for data items with nonuniform 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 pseudopolynomial algorithm is discussed whose time is OšNZŽ, where Z is the sum of the data lengths. In the latter case, an algorithm is devised with time exponential in the maximum data length, which can optimally solve, in reasonable time, only small instances. For larger instances, a new heuristic is devised which is experimentally tested on some benchmarks whose popularities are characterized by Zipf distributions. Such experimental tests reveal that the new heuristic proposed here always outperforms the best previously known heuristic in terms of solution quality.
Subject Wireless Communication
Data Broadcast
Multiple Channels
Skewed Allocation
Flat Scheduling
Average Waiting Time
Dynamic Programming
F.2 Analysis of Algorithms and Problem Complexity


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