Keqiu Li
Abstract
Web caching is an important technology for improving the scalability of Web services. One of the key problems in coordinated enroute Web caching is to compute the locations for storing copies of an object among the enroute caches so that some specified objectives are achieved. In this article, we address this problem for tree networks, and formulate it as a maximization problem. We consider this problem for both unconstrained and constrained cases. The constrained case includes constraints on the cost gain per node and on the number of object copies to be placed. We present dynamic programming-based solutions to this problem for different cases and theoretically show that the solutions are either optimal or convergent to optimal solutions. We derive efficient algorithms that produce these solutions. Based on our mathematical model, we also present a solution to coordinated enroute Web caching for autonomous systems as a natural extension of the solution for tree networks. We implement our algorithms and evaluate our model on different performance metrics through extensive simulation experiments. The implementation results show that our methods outperform the existing algorithms of either coordinated enroute Web caching for linear topology or object placement (replacement) at individual nodes only.
- Awerbuch, B., Bartal, Y., and Fiat, A. 1998. Distributed paging for general networks. J. Algorithms 28, 67--104.]] Google Scholar
- Barford, P. and Crovella, M. 1998. Generating representative Web workloads for network and server performance evaluation. In Proceedings of ACM SIGMETRICS'98. 151--160.]] Google Scholar
- Bates, T., Gerich E., Joncheray, L., Jouanigot, J. M., Karrenberg, D., Terpstra, M. and Yu, J. 1995. Representation of IP routing policies in a routing registry. RFC 1786. IETF.]] Google Scholar
- Breslau, L., Cao, P., Fan, L., Phillips, G., and Shenker, S. 1999. Web caching and zip-like distributions: evidence and implications. In Proceedings of IEEE INFOCOM'99. 126--134.]]Google Scholar
- Calvert, K. L., Doar, M. B., and Zegura, E. W. 1997. Modelling internet topology. IEEE Comm. Magazine 35, 6, 160--163.]]Google Scholar
- Cao, P. and Irani, S. 1997. Cost-aware WWW proxy caching algorithms. In Proceedings of the 1st USENIX Symposium on Internet Technologies and Systems (USITS). 193--206.]] Google Scholar
- Chankhunthod, A., Danzig, P., Neerdaels, C., Schwartz, M., and Worrell, K. 1996. A hierarchical Internet object cache. In Proceedings of the USENIX Technical Conference. 22--26.]] Google Scholar
- Cunha, C., Bestavros, A., and Crovella, M. 1995. Characteriatics of WWWW Client-Based Traces. Tech. rep. TR-95-010, Boston University, Boston, MA.]] Google Scholar
- Dahlin, M. D., Wang, R. Y., Anderson, T. E., and Patterson, D. A. 1994. Cooperative caching: using remote client memory to improve file system performance. In Proceedings of the 1st Symposium on Operating Systems Design and Implementations. 267--280.]] Google Scholar
- Davison, B. D. 2001. A Web caching primer. IEEE Internet Comput. 5, 4, 38--45.]] Google Scholar
- Glassman, S. 1994. A caching relay for the World Wide Web. Comput. Netw. ISDN Syst. 27, 2, 165--173.]] Google Scholar
- Jia, X., Li, D., Hu, X., and Du, D. 2001. Optimal placement of Web proxies for replicated Web servers in the Internet. Comput. J. 44, 5, 329--339.]]Google Scholar
- Jiang, A. and Bruck, J. 2003. Optimal content placement for enroute Web caching. In Proceedings of the 2nd International Symposium on Network Computing and Applications (NCA'03). 9--16.]] Google Scholar
- Jin, S. and Bestavros, A. 2001. Greeddual* Web caching algorithm exploiting the two sources of temporal locality in Web request streams. Comput. Comm. 4, 2, 174--183.]]Google Scholar
- Korupolu, M. R. and Dahlin, M. 2002. Coordinated placement and replacement for large-scale distributed caches. IEEE Tran. Knowl. Data Eng. 14, 6, 1317--1329.]] Google Scholar
- Korupolu, M. R., Plaxton, C. G., and Rajaraman, R. 1999. Placement algorithms for hierarchical coorperative caching. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. 586--595.]] Google Scholar
- Krishnan, P., Raz, D., and Shavitt, Y. 2000. The cache location problem. IEEE/ACM Trans. Netw. 8, 5, 568--582.]] Google Scholar
- Leff, A., Wolf, J. L., and Yu, P. S. 1993. Replication algorithms in a remote caching architecture. IEEE Trans. Paral. Distrib. Syst. 4, 11, 1185--1204.]] Google Scholar
- Li, B., Golin, M. J., Italiano, G. F., Deng, X., and Sohraby, K. 1999. On the optimal placement of Web proxies in the Internet. In Proceedings of IEEE INFOCOM'99. 1282--1290.]]Google Scholar
- Li, K. and Shen, H. 2003. Constrained coordinated enroute Web caching in tree networks. In Proceedings of the 3rd International Conference on Hybrid Intelligent Systems (HIS'03). 1054--1063.]] Google Scholar
- Li, K. and Shen, H. 2003. An optimal method for coordinated enroute Web object caching. In Proceedings of the 5th International Symposium on High Performance Computing (ISHPC-V). 368--375.]]Google Scholar
- Paxson, V. 1997. End-to-end routing behavior in the Internet. IEEE/ACM Trans. Netw. 5, 5, 601--615.]] Google Scholar
- Pierre, G. and Steen, M. 2002. Dynamically selecting optimal distribution strategies for Web documents. IEEE Trans. Comput. 51, 6, 637--651.]] Google Scholar
- Rabinovich, M. and Spatscheck, O. 2002. Web Caching and Replication. Addison-Wesley.]] Google Scholar
- Rabinovich, P. and Wang, H. 2001. Dhttp: an efficient and cache-friendly transfer protocol for Web traffic. In Proceedings of IEEE INFOCOM'01. 1597--1606.]]Google Scholar
- Rodriguez, P. and Sibal, S. 2000. Spread: Scalable platform for reliable and efficient automated distribution. Comput. Netw. 33, 33--49.]] Google Scholar
- Rodriguez, P., Sibal, S., and Spatscheck, O. 2000. Tpot: translucent proxying of TCP. In Proceedings of the 5th International Web Caching and Content Delivery Workshop (WCW'00).]]Google Scholar
- Rodriguez, P., Spanner, C., and Biersack, E. W. 2001. Analysis of Web caching architectures: Hierarchical and distributed caching. IEEE/ACM Trans. Netw. 9, 4, 404--418.]] Google Scholar
- Scheuermann, P., Shim, J., and Vingralek, R. 1997. A case for delay-conscious caching of Web documents. Comput. Netw. ISDN Syst. 2, 8--13, 997--1005.]] Google Scholar
- Shim, J., Scheuermann, P., and Vingralek, R. 1999. Proxy cache algorithms: design, implementation, and performance. IEEE Trans. Knowl. Data Eng. 11, 4, 549--562.]] Google Scholar
- Tang, X. and Chanson, S. T. 2002. Coordinated enroute Web caching. IEEE Trans. Comput. 51, 6, 595--607.]] Google Scholar
- Tennenhouse, D. L., Smith, J. M., Sincoskie, W. D., Wetherall, D. J., and Minden, G. J. 1997. A survey of active network research. IEEE Comm. Magazine 35, 1, 80--86.]]Google Scholar
- Tewari, X., Dahlin, M., Vin, H. M., and Kay, J. S. 1999. Design considerations for distributed caching on the Internet. In Proceedings of the 19th International Conference on Distributed Computing Systems (ICDCS'99). 273--284.]] Google Scholar
- Wang, J. 1999. A survey of Web caching schemes for the internet. ACM SIGCOMM Comput. Comm. Rev. 29, 5, 36--46.]] Google Scholar
- Williams, S., Abrams, M., Standbridge, C. R., Abdulla, G., and Fox, E. A. 1996. Removal policies in network caches for World Wide Web documents. In Proceedings of ACM SIGCOMM'96. 293--305.]] Google Scholar
- Wolfson, O. and Milo, A. 1991. The multicast policy and its relationship to replicated data placement. ACM Trans. Datab. Syst. 16, 1, 181--205.]] Google Scholar
- Xu, J., Li, B., and Li, D. L. 2002. Placement problems for transparent data replication proxy services. IEEE J. Select. Areas Comm. 20, 7, 1383--1398.]]Google Scholar
- Yu, P. S. and MacNair, E. A. 1998. Performance study of a collaborative method for hierarchical caching in proxy servers. Computer Netw. ISDN Syst. 30, 215--224.]] Google Scholar
Index Terms
- Optimal methods for coordinated enroute web caching for tree networks
Recommendations
Coordinated En-Route Web Caching
Web caching is an important technique for reducing Internet access latency, network traffic, and server load. This paper investigates cache management strategies for the en-route web caching environment, where caches are associated with routing nodes in ...
Coordinated enroute multimedia object caching in transcoding proxies for tree networks
Transcoding is a promising technology that allows systems to effect a quality-versus-size tradeoff on multimedia objects. As audio and video applications have proliferated on the Internet, caching in transcoding proxies has become an important technique ...
Constrained coordinated en-route web caching in tree networks
Design and application of hybrid intelligent systemsCaching popular objects close to users can improve web performance greatly. In this paper, we first propose a novel mathematical model for the coordinated enroute web caching problem of computing the locations for the copies of an object to be placed ...
Comments