Improving Web Performance in Broadcast-Unicast Networks

Mukesh Agrawal, Amit Manjhi, Nikhil Bansal, and Srinivasan Seshan


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 loads than existing systems.

Conference Paper (Infocom 2003)

Extended version as CMU CS Technical Report CMU-CS-02-159 [pdf][ps]