Optimal skewed data allocation on multiple channels with flat broadcast per channel (Articolo in rivista)

Type
Label
  • Optimal skewed data allocation on multiple channels with flat broadcast per channel (Articolo in rivista) (literal)
Anno
  • 2005-01-01T00:00:00+01:00 (literal)
Alternative label
  • Ardizzoni, E., Bertossi A.A., Pinotti M.C. (2005)
    Optimal skewed data allocation on multiple channels with flat broadcast per channel
    in I.E.E.E. transactions on computers (Print)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Ardizzoni, E., Bertossi A.A., Pinotti M.C. (literal)
Pagina inizio
  • 558 (literal)
Pagina fine
  • 572 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 54 (literal)
Rivista
Note
  • ISI Web of Science (WOS) (literal)
Titolo
  • Optimal skewed data allocation on multiple channels with flat broadcast per channel (literal)
Abstract
  • 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. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it