Many of the data-centric network services deployed today hold massive volumes of data at their origin websites, and access the data to dynamically generate responses to user requests. One way to improve the scalability and performance for such services is to develop alternate caching infrastructures, which leverage network intermediaries to detect the often large degrees of usage locality seen by such services, and use this information to redirect requests to service portions replicated on-demand at appropriate network locations. Key to building such infrastructures is the ability to cluster and inspect client requests at various points across a wide-area network.

This paper presents a zone-based scheme for constructing oriented overlays, which provide such an ability. Oriented overlays support network traffic flows between many sources and a small number of destinations and by design enable clustering of similar requests along their paths. Extensive experiments on the PlanetLab network show that our scheme produces overlays that (1) are robust to network dynamics; (2) offer good clustering ability; and (3) minimally impact end-to-end performance metrics of interest to clients.