loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Minimal Cost Replication of Dynamic Web Contents under Flat Update Delivery
May 2004 (vol. 15 no. 5)
pp. 431-439
ASCII Text
x 
 
Xueyan Tang, Samuel T. Chanson, "Minimal Cost Replication of Dynamic Web Contents under Flat Update Delivery," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 5, pp. 431-439, May, 2004.
 
 
BibTex
x
 
@article{ 10.1109/TPDS.2004.1278100,
author = {Xueyan Tang and Samuel T. Chanson},
title = {Minimal Cost Replication of Dynamic Web Contents under Flat Update Delivery},
journal ={IEEE Transactions on Parallel and Distributed Systems},
volume = {15},
number = {5},
issn = {1045-9219},
year = {2004},
pages = {431-439},
doi = {http://doi.ieeecomputersociety.org/10.1109/TPDS.2004.1278100},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Parallel and Distributed Systems
TI - Minimal Cost Replication of Dynamic Web Contents under Flat Update Delivery
IS - 5
SN - 1045-9219
SP431
EP439
EPD - 431-439
A1 - Xueyan Tang,
A1 - Samuel T. Chanson,
PY - 2004
KW - Data replication
KW - data consistency
KW - object dependency
KW - dynamic Web contents
KW - flow network
KW - maximum flow/minimum cut.
VL - 15
JA - IEEE Transactions on Parallel and Distributed Systems
ER -
 

Abstract—Dynamic Web contents are generated by running application programs on base data which often change frequently. Geographically replicating the applications that construct these contents (including the programs and the related data they access) is an effective approach to improve their access latency. To maintain the freshness of an object replica, the new version of the object either has to be fetched from remote servers or be reconstructed locally when the origin copy is updated. This paper presents a theoretical study on geographical replication of dynamic Web contents with the objective of minimizing the consistency management costs in terms of update transfers and object reconstruction. The dependencies among dynamic objects and base data are modeled as a directed acyclic graph. We formulate the minimum cost replication problem under a flat framework of update delivery. The problem is solved by first transforming it into a minimum cut problem in a flow network. A polynomial-time algorithm is then proposed to compute the optimal replication strategy which designates where each object should be replicated and how to keep the replicas up-to-date.

[1] E.A. Brewer, R.H. Katz, Y. Chawathe, S.D. Gribble, T. Hodes, G. Nguyen, M. Stemm, T. Henderson, E. Amir, H. Balakrishnan, A. Fox, V.N. Padmanabhan, and S. Seshan, A Network Architecture for Heterogeneous Mobile Computing IEEE Personal Comm., vol. 5, no. 5, pp. 8-24, Oct. 1998.
[2] V. Cardellini, M. Colajanni, and P.S. Yu, Geographic Load Balancing for Scalable Distributed Web Systems Proc. Eighth IEEE/ACM Int'l Symp. Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 20-27, Aug. 2000.
[3] J. Challenger, A. Iyengar, and P. Dantzig, A Scalable System for Consistently Caching Dynamic Web Data Proc. IEEE INFOCOM, pp. 294-303, Mar. 1999.
[4] J. Challenger, A. Iyengar, K. Witting, C. Ferstat, and P. Reed, A Publishing System for Efficiently Creating Dynamic Web Content Proc. IEEE INFOCOM, pp. 844-853, Mar. 2000.
[5] J.W. Chinneck, Practical Optimization: A Gentle Introduction,http://www.sce.carleton.ca/faculty/chinneck po.html, 2003.
[6] E. Cohen and H. Kaplan, Refreshment Policies for Web Content Caches Proc. IEEE INFOCOM, pp. 1398-1406, Apr. 2001.
[7] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms. second ed., MIT Press, 2001.
[8] B.D. Davison, “A Web Caching Primer,” IEEE Internet Computing, vol. 5, no. 4, pp. 38-45, July/Aug. 2001.
[9] J. Dilley et al., "Globally Distributed Content Delivery," IEEE Internet Computing, vol. 6, no. 5, 2002, pp. 50-58.
[10] F. Douglis, A. Feldmann, B. Krishnamurthy, and J. Mogul, Rate of Change and Other Metrics: A Live Study of the World Wide Web Proc. First USENIX Symp. Internet Technologies and Systems, pp. 147-158, Dec. 1997.
[11] S.G. Dykes, K.A. Robbins, and C.L. Jeffery, An Empirical Evaluation of Client-Side Server Selection Algorithms Proc. IEEE INFOCOM, pp. 1361-1370, Mar. 2000.
[12] A.V. Goldberg and R.E. Tarjan, A New Approach to the Maximum-Flow Problem J. ACM, vol. 35, no. 4, pp. 921-940, Oct. 1988.
[13] J. Gwertzman and M. Seltzer, "The Case for Geographical Push Caching," Proc. Workshop Hot Operating Systems, 1995.
[14] V. Holmedahl, B. Smith, and T. Yang, Cooperative Caching of Dynamic Content on a Distributed Web Server Proc. Seventh IEEE Int'l Symp. High Performance Distributed Computing, pp. 243-250, July 1998.
[15] S. Jamin, C. Jin, A.R. Kurc, D. Raz, and Y. Shavitt, Constrained Mirror Placement on the Internet Proc. IEEE INFOCOM, pp. 31-40, Apr. 2001.
[16] A. Labrinidis and N. Roussopoulos, WebView Materialization Proc. ACM SIGMOD, pp. 367-378, May 2000.
[17] A. Labrinidis and N. Roussopoulos, Update Propagation Strategies for Improving the Quality of Data on the Web Proc. 27th Int'l Conf. Very Large Data Bases, pp. 391-400, Sept. 2001.
[18] J.C. Mogul, F. Douglis, A. Feldmann, and B. Krishnamurthy, Potential Benefits of Delta-Encoding and Data Compression for HTTP Proc. ACM SIGCOMM, pp. 181-194, Sept. 1997.
[19] R. Mohan, J.R. Smith,, and C.-S. Li,"Adapting Multimedia Internet Content for Universal Access," IEEE Trans. Multimedia, vol. 1, no. 1, Mar. 1999, pp. 104-114.
[20] P. Mohapatra and H. Chen, WebGraph: A Framework for Managing and Improving Performance of Dynamic Web Content IEEE J. Selected Areas in Comm., vol. 20, no. 7, pp. 1414-1425, Sept. 2002.
[21] A. Myers, P. Dinda, and H. Zhang, Performance Characteristics of Mirror Servers on the Internet Proc. IEEE INFOCOM, pp. 304-312, Mar. 1999.
[22] V.N. Padmanabhan and L. Qiu, The Content and Access Dynamics of a Busy Web Site: Findings and Implications Proc. ACM SIGCOMM, pp. 111-123, Aug. 2000.
[23] M. Rabinovich, I. Rabinovich, R. Rajaraman, and A. Aggarwal, “A Dynamic Object Replication and Migration Protocol for an Internet Hosting Service,” Proc. 19th Int'l Conf. Distributed Computing Systems, pp. 101-113, June 1999.
[24] M. Rabinovich and O. Spatscheck, Web Caching and Replication. Addison-Wesley, 2002.
[25] P. Rodriguez, A. Kirpal, and E.W. Biersack, Parallel-Access for Mirror Sites in the Internet Proc. IEEE INFOCOM, pp. 864-873, Mar. 2000.
[26] P. Rodriguez and S. Sibal, SPREAD: Scalable Platform for Reliable and Efficient Automated Distribution Computer Networks, vol. 33, nos. 1-6, pp. 33-49, June 2000.
[27] N. Roussopoulos, Materialized Views and Data Warehouses ACM SIGMOD Record, vol. 27, no. 1, pp. 21-26, Mar. 1998.
[28] M. Zari, H. Saiedian, and M. Naeem, Understanding and Reducing Web Delays Computer, vol. 34, no. 12, pp. 30-37, Dec. 2001.
[29] H. Zhu and T. Yang, Class-Based Cache Management for Dynamic Web Content Proc. IEEE INFOCOM, pp. 1215-1224, Apr. 2001.

Index Terms:
Data replication, data consistency, object dependency, dynamic Web contents, flow network, maximum flow/minimum cut.
Citation:
Xueyan Tang, Samuel T. Chanson, "Minimal Cost Replication of Dynamic Web Contents under Flat Update Delivery," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 5, pp. 431-439, May 2004, doi:10.1109/TPDS.2004.1278100
Usage of this product signifies your acceptance of the Terms of Use.