DIMACS TR: 2001-20

Mobile Filters for Efficient Dissemination of Personalized Information Using Content-Based Multicast

Authors: Rahul Shah, Ravi Jain, S. Rajagopalan, Farooq Anjum


There has been a surge of interest in the delivery of personalized information to users (e.g. personalized stocks or travel information), particularly as the amount of information readily available from sources like the World Wide Web increases, and mobile users with limited terminal device capabilities increasingly desire updated, targeted information in real time. When the number of information recipients is large and there is sufficient commonality in their interests, as is often the case, it is worthwhile to use multicast rather than unicast to deliver the information. However, traditional multicast services, e.g. at the IP level, do not consider the structure and semantics of the information in the multicast process. We consider the use of Content-Based Multicast (CBM) where extra content filtering is performed at the interior nodes of the multicast tree so as to reduce network bandwidth usage and delivery delay, as well as to reduce the computation required at the sources and sinks. Note that filtering could be performed at the IP level or, more likely, at higher software layers e.g. in applications such as publish-subscribe and event notification systems.

In this paper we evaluate the situations in which CBM is worthwhile. The benefits of CBM depend critically upon how well filters are placed at interior nodes of the multicast tree, and the costs depend upon those introduced by filters themselves. Further, we consider the benefits of allowing the filters to be mobile so as to respond to user mobility or changes in user interests, and the corresponding costs of filter mobility. We consider two criteria: minimizing total network bandwidth utilization and minimizing mean information delivery delay. For each criterion we also develop a heuristic that runs faster than the optimal algorithm. Finally, we evaluate all the algorithms by means of simulation experiments.

Our results indicate that filters can be effective in substantially reducing bandwidth and delay. We also find filter mobility is worthwhile if there is sufficient locality in the interests of users, or there is marked large-scale user mobility. We conclude with suggestions for further work.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-20.ps.gz

DIMACS Home Page