Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

On the Clustering of Web Content for Efficient Replication

Yan Chen, Lili Qiu, Weiyu Chen, Luan Nguyen and Randy H. Katz

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-02-1193
2002

http://www.eecs.berkeley.edu/Pubs/TechRpts/2002/CSD-02-1193.pdf

Recently there has been an increasing deployment of content distribution networks (CDNs) that offer hosting services to Web content providers. In this paper, we first compare the un-cooperative pull-based replication of Web contents used by commercial CDNs with the cooperative push-based approach. Our results show that the latter can achieve comparable users¿ perceived performance with much less replication and update traffic ( 4 - 5% of those in the former scheme). Motivated by the observation, we explore how to efficiently push content to CDN nodes. Using trace-driven simulation, we show that replicating content in units of URLs can yield 60 - 70% reduction in clients¿ latency compared to replicating in units of Web sites. On the other hand, it is very expensive to perform such a fine-grained replication.

To address this issue, we propose to replicate content in units of clusters, each containing objects which are likely to be requested by clients that are topologically close. To this end, we describe three clustering techniques, and use various topologies and several real traces from large Web servers to evaluate their performance. Our results show that clusterbased replication achieves 40 - 60% improvement over full Web site replication. In addition, by adjusting the number of clusters, we can smoothly trade off the management and computation cost for better client performance.

To take into account of change in users¿ access patterns, we also explore incremental clusterings to adaptively add new documents to the content clusters. We examine both offline and online incremental clusterings, where the former assumes access history is available while the latter predicts access pattern based on the hyperlink structure. Our results show that the offline clusterings yield close to the performance of the complete re-clustering while at much lower overhead. The online incremental clustering and replication cut down the retrieval cost by 4.6 - 8 times compared to no replication and random replication, so it is especially useful to improve document availability during flash crowds.


BibTeX citation:

@techreport{Chen:CSD-02-1193,
    Author = {Chen, Yan and Qiu, Lili and Chen, Weiyu and Nguyen, Luan and Katz, Randy H.},
    Title = {On the Clustering of Web Content for Efficient Replication},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2002},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2002/5687.html},
    Number = {UCB/CSD-02-1193},
    Abstract = {Recently there has been an increasing deployment of content distribution networks (CDNs) that offer hosting services to Web content providers. In this paper, we first compare the un-cooperative pull-based replication of Web contents used by commercial CDNs with the cooperative push-based approach. Our results show that the latter can achieve comparable users¿ perceived performance with much less replication and update traffic ( 4 - 5% of those in the former scheme). Motivated by the observation, we explore how to efficiently push content to CDN nodes. Using trace-driven simulation, we show that replicating content in units of URLs can yield 60 - 70% reduction in clients¿ latency compared to replicating in units of Web sites. On the other hand, it is very expensive to perform such a fine-grained replication. <p>To address this issue, we propose to replicate content in units of clusters, each containing objects which are likely to be requested by clients that are topologically close. To this end, we describe three clustering techniques, and use various topologies and several real traces from large Web servers to evaluate their performance. Our results show that clusterbased replication achieves 40 - 60% improvement over full Web site replication. In addition, by adjusting the number of clusters, we can smoothly trade off the management and computation cost for better client performance. <p>To take into account of change in users¿ access patterns, we also explore incremental clusterings to adaptively add new documents to the content clusters. We examine both offline and online incremental clusterings, where the former assumes access history is available while the latter predicts access pattern based on the hyperlink structure. Our results show that the offline clusterings yield close to the performance of the complete re-clustering while at much lower overhead. The online incremental clustering and replication cut down the retrieval cost by 4.6 - 8 times compared to no replication and random replication, so it is especially useful to improve document availability during flash crowds.}
}

EndNote citation:

%0 Report
%A Chen, Yan
%A Qiu, Lili
%A Chen, Weiyu
%A Nguyen, Luan
%A Katz, Randy H.
%T On the Clustering of Web Content for Efficient Replication
%I EECS Department, University of California, Berkeley
%D 2002
%@ UCB/CSD-02-1193
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2002/5687.html
%F Chen:CSD-02-1193