Abstract:

Many network applications that need to distribute contents and data
to a large number of clients use a hybrid scheme in which one or more
multicast channel is used in parallel to a unicast dissemination.
This way the application can distribute data using one of its
available multicast channels or by sending one or more unicast
transmissions. In such a model the utilization of the multicast
channels is critical for the overall performance of the system.

We study the scheduling algorithm of the sender in such a model. We
describe this scheduling problem as an optimization problem where the
objective is to maximize the utilization of the multicast channel.
Our model captures the fact that it may be beneficial to multicast an
object more than once (e.g. page update). Thus, the benefit depends,
among other things, on the last time the object was sent, which makes
the problem much more complex than previous related scheduling
problems. We show that our problem is NP-hard. and that no
competitive on-line algorithm exists for it. Then, Using the
\emph{local ratio technique\/} we obtain a 4-approximation algorithm
for the case where the objects are of fixed size and a
10-approximation algorithm for the general case. We also consider a
special case which may be of practical interest, and prove that a
simple greedy algorithm is a 3-approximation algorithm in this case.

The talk is self contained; it starts with a description of the
problem and motivation, continues with a detailed review of the
theoretical results, and ends with a discussion of practical use of
the results for Context Aware Services in telecommunication networks.

This is a joint work with Rami Cohen and Dror Rawitz