Computer Science Department
School of Computer Science, Carnegie Mellon University


Improving Web Performance in Broadcast-Unicast Networks

Mukesh Agrawal, Amit Manjhi, Nikhil Bansal, Srinivasan Seshan

July 2002

Keywords: Satellite networks, broadcast scheduling complexity, web caching, web performance, broadcast dissemination

Satellite operators have recently begun offering Internet access over their networks. Typically, users connect to the network using a modem for uplink, and a satellite dish for downlink. We investigate how the performance of these networks might be improved by two simple techniques: caching and use of the return path on the modem link. We examine the problem from a theoretical perspective and via simulation. We show that the general problem is NP-Hard, as are several special cases, and we give approximation algorithms for them. We then use insights from these cases to design practical heuristic schedulers which leverage caching and the modem downlinks. Via simulation, we show that caching alone can simultaneously reduce bandwidth requirements by 33% and improve response times by 62%. We further show that the proposed schedulers, combined with caching, yield a system that performs far better under high loands than existing systems.

24 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by