Efficient heuristics for data broadcasting on multiple channels

The problem of data broadcasting over multi- ple channels consists in partitioning data among channels, depending on data popularities, and then cyclically trans- mitting them over each channel so that the average wait- ing time of the clients is minimized. Such a problem is known to be polynomially time solvable for uniform length data items, while it is computationally intractable for non- uniform length data items. In this paper, two new heuris- tics are proposed which exploit a novel characterization of optimal solutions for the special case of two channels and data items of uniform lengths. Sub-optimal solutions for the most general case of an arbitrary number of channels and data items of non-uniform lengths are provided. The first heuristic, called Greedy +, combines the novel characteri- zation with the known greedy approach, while the second heuristic, called Dlinear, combines the same characteriza- tion with the dynamic programming technique. Such heuris- tics have been tested on benchmarks whose popularities are characterized by Zipf distributions, as well as on a wider set of benchmarks. The experimental tests reveal that Dlinear finds optimal solutions almost always, requiring good run- ning times. However, Greedy + is faster and scales well when changes occur on the input parameters, but provides solutions which are close to the optimum.