基于Internet的代理缓存技术研究
|
摘要
随着Internet技术和Web服务的发展，Web流量继续以指数增长，造成网络带宽严重不足，用户面临的两大问题是网络阻塞和服务器过载，严重影响了Internet的持续发展。基于Internet的代理缓存技术是解决这些问题的一个主要和有效的技术，在国际上已经形成一个独立的主流研究领域。其中，一致性策略和替换策略的研究一直是提高代理缓存系统性能的两个研究方向，而如何将一致性策略和替换策略有机地结合起来，以便有效地提高代理缓存系统的性能是代理缓存技术的研究前沿。本文对基于Internet的代理缓存技术进行了比较深入地研究，主要完成了以下几方面的工作：
1、通过对代理缓存的一致性策略的研究，论述了自适应TTL机制是较好的弱一致性维护技术，它容易实现并能降低将灰本响应给用户的概率。
2、通过对代理缓存的替换策略的研究，论述了基于成本／价值模型的替换算法是较优的，但必须修正和简化其模型，使计算相对简单，又能体现Web的访问特性，减少延迟。
3、提出了一个新的性能评价指标——陈旧命中比。它体现了陈旧率和命中率的对比程度，能很好地衡量代理缓存的各种算法的优劣和代理缓存系统的整体性能。
广西大学硕士论文 基于Internet的代理缓存技术研究 摘要
4、提出、设计和实现了自适应一致性一替换算法（即ACR算法人
该算法包括一致性策略和替换策略两部分，一致性策略采用自适应TTL
机制，替换策略是基于成本／价值模型的算法。ACR算法的独到之处在
于将代理缓存的一致性策略和替换策略较好地结合起来，并体现Web
的访问特性，保证以较小的代价从代理缓存中提供更新鲜的资源给用
户，体现了将代理缓存的一致性策略和替换策略结合起来的优越性，
同时提高了代理缓存系统的整体性能。通过 Trace－D＊ yen 4g拟实验，
结果表明ACR算法在陈旧命中比上均忧于传统的几个替换算法，从而
证明了新提出的ACR算法是合理、有效和实用的。
With the development of Internet technologies and Web services, Web traffic still increases exponentially. It results in severe network bandwidth scarcity, network congestion and server overloading, which are the key issues affecting the continuous growing of the Internet. Proxy cache is the main and effective technique to solve these issues. Now it has become an international main research area in which the studies on consistency policies and replacement policies always are the two directions of research, while the front of research on proxy caching techniques is how to better incorporate these two policies which results in a desirable performance of a proxy caching system. In this paper, the research is made more thoroughly on the proxy caching techniques for the Internet. The main results are as follows.
1.According to the research on proxy cache consistency policies, it is discussed that Adaptive TTL is more attractive in weak consistency policies, which can be easily implemented and reduce the probability of returning stale data to users.
2.According to the research on proxy cache replacement policies, it is discussed that replacement algorithms based on cost/value model are
preferable. However, the model requires to be modified and simplified to easily calculate, to reflect Web access characteristics and to reduce access latency.
3. A new performance metric called staleness-hit rate is proposed. It balances these two performance metrics. Therefore, it can better estimate all the algorithms of proxy cache and the overall performance of a proxy caching system.
4. A new algorithm called ACR (Adaptive Consistency and Replacement algorithm) is proposed, designed and implemented. It incorporates cache consistency policy with cache replacement policy in which the cache consistency policy is Adaptive TTL mechanism, while the cache replacement policy is based on a cost/value model. It can better incorporate these two policies and reflect Web access characteristics. It also can guarantee returning the fresher data to users with the lower cost, which reflects the superiority of a combination of these two policies and improves the overall performance of a proxy caching system. Using Trace-Driven simulation, the results show that ACR algorithm is better than several traditional algorithms in staleness-hit rate, hence ACR algorithm proves to be rational, effective and practical.
1、通过对代理缓存的一致性策略的研究，论述了自适应TTL机制是较好的弱一致性维护技术，它容易实现并能降低将灰本响应给用户的概率。
2、通过对代理缓存的替换策略的研究，论述了基于成本／价值模型的替换算法是较优的，但必须修正和简化其模型，使计算相对简单，又能体现Web的访问特性，减少延迟。
3、提出了一个新的性能评价指标——陈旧命中比。它体现了陈旧率和命中率的对比程度，能很好地衡量代理缓存的各种算法的优劣和代理缓存系统的整体性能。
广西大学硕士论文 基于Internet的代理缓存技术研究 摘要
4、提出、设计和实现了自适应一致性一替换算法（即ACR算法人
该算法包括一致性策略和替换策略两部分，一致性策略采用自适应TTL
机制，替换策略是基于成本／价值模型的算法。ACR算法的独到之处在
于将代理缓存的一致性策略和替换策略较好地结合起来，并体现Web
的访问特性，保证以较小的代价从代理缓存中提供更新鲜的资源给用
户，体现了将代理缓存的一致性策略和替换策略结合起来的优越性，
同时提高了代理缓存系统的整体性能。通过 Trace－D＊ yen 4g拟实验，
结果表明ACR算法在陈旧命中比上均忧于传统的几个替换算法，从而
证明了新提出的ACR算法是合理、有效和实用的。
With the development of Internet technologies and Web services, Web traffic still increases exponentially. It results in severe network bandwidth scarcity, network congestion and server overloading, which are the key issues affecting the continuous growing of the Internet. Proxy cache is the main and effective technique to solve these issues. Now it has become an international main research area in which the studies on consistency policies and replacement policies always are the two directions of research, while the front of research on proxy caching techniques is how to better incorporate these two policies which results in a desirable performance of a proxy caching system. In this paper, the research is made more thoroughly on the proxy caching techniques for the Internet. The main results are as follows.
1.According to the research on proxy cache consistency policies, it is discussed that Adaptive TTL is more attractive in weak consistency policies, which can be easily implemented and reduce the probability of returning stale data to users.
2.According to the research on proxy cache replacement policies, it is discussed that replacement algorithms based on cost/value model are
preferable. However, the model requires to be modified and simplified to easily calculate, to reflect Web access characteristics and to reduce access latency.
3. A new performance metric called staleness-hit rate is proposed. It balances these two performance metrics. Therefore, it can better estimate all the algorithms of proxy cache and the overall performance of a proxy caching system.
4. A new algorithm called ACR (Adaptive Consistency and Replacement algorithm) is proposed, designed and implemented. It incorporates cache consistency policy with cache replacement policy in which the cache consistency policy is Adaptive TTL mechanism, while the cache replacement policy is based on a cost/value model. It can better incorporate these two policies and reflect Web access characteristics. It also can guarantee returning the fresher data to users with the lower cost, which reflects the superiority of a combination of these two policies and improves the overall performance of a proxy caching system. Using Trace-Driven simulation, the results show that ACR algorithm is better than several traditional algorithms in staleness-hit rate, hence ACR algorithm proves to be rational, effective and practical.
引文
[1] HenningSchulzrinne, World Wide Web: Hence, Whence, Whither, What Next?, IEEE Network, 1996.10 (2): 10-17
[2] J. Wang, A survey of web caching schemes for the Internet, Computer Communication Review, October 1999. 29 (5): 36-46
[3] 庄伟强，集群服务器代理缓存技术研究：[博士学位论文]，清华大学研究生院，1999
[4] A. Fox, Steven D. Gribble, et. al, Cluster-based Scalable Network Service, In Proc. of the 16th ACM Symposium on Operating System Principles, Saint Malo, Oct 1997:78-91
[5] V. N. Padmanbhan, J. C. Mogul, Using Predictive Prefetching to Improve World Wide Web Latency, ACM Computer Communication Review, July 1996. 27 (3): 22-36
[6] R. Fielding, J. Gettys, J. Mogul, et. al, HyperText Transfer Protocol-HTTP/1. 1, IETF RFC 2068, January, 1997
[7] Rawn Shah, 使用Web高速缓存减少网络流量，http//www-9OO.Ibm.com/developerWorks/cn/web/webcachinga/index.shtml
[8] 陈兆良，代理服务器实战，软件世界，http:/tech.sina.com.cn,2000
[9] J. Shim, P. Scheuermann, R. Vingralek, Proxy Cache Design: Algorithms, Implementation and Performance, IEEE Trans. Knowledge and Data Engineering, 1999. 11(4): 549-562
[10] B. Krishnamurthy, C.E. Wills, Proxy cache coherency and replacement-towards a more complete picture, ICDC99, June 1999
[11] Jose Aguilar, Ernst L. Leiss,An Adaptive Cache Coherency-Replacement Scheme for Web Proxy Systems,in proceedings of SCI, 2001
[12] 沈庆伟，基于Internet的高速缓存技术分析，合肥工业大学学报，2002。25(3)：451-454
[13] 曾明(口月)，李建军，Internet访问管理与代理服务器，人民邮电出版社，2000
[14] 陈兵，王立松，基于哈希链表和时间链表的HTTP代理缓存机制的实现，南京航空航天大学学报，2002。34(1)：50-54
[15] D. Wessels, K. Claffy, Internet cache protocol(IPC),version 2, RFC 2186
[16] Anawat Chankhunthod,Peter B.Danzig,Chuch Neerdaels, et.al, A Hierarchical Internet Object Cache,Technical Report 95-611,Computer Science Department, University of Southern California, Los Angeles,California, March 1995
[17] Netscape Proxy Server 2.0, http://www.netscape.com/comprod/server_central/product/proxy/
[18] Squid, http://squid.nlanr.net/
[19] L. Cherkasova, G. Ciardo, Role of aging, frequency, and size in Web cache replacement policies, http://citeseer.nj.nec.com/cache/papers/cs/25725/http:zSzzSzwww, cs. wm. eduzS z~ciardozSzpubszSz2001taxonomy-gdfs, pdf/role-of-aging-frequency, pdf
[20] Gaura Banga, Fred Douglis, Michael Rabinovich, Optimistic Deltas for WWW Latency Reduction, In Proceedings of 1997 USENIX Technical Conference, 1997:289-303
[21] Gwetzman, M. Seltzer, World Wide Web cache consistency, In Proceedings of the USENIX Technical Conference, January 1996:141-152
[22] V. Cate, Alex-a global file system, In Proceedings of the 1992 USENIX File System Workshop, May 1992:1-12
[23] A. Luotonen, K. Altis, World Wide Web proxies, Computer Networks and ISDN Systems, First International Conference on WWW,. April 1994
[24] D. Wessels, Intelligent caching for World—Wide Web ob jects, In Proceedings of INET' 95, Honohlu, Hawaii, June 1995
[25] A. Chankhunthod, P. B. Danzing, C. Neerdaels, et. al, AhierarchicalInternet object cache, Usenix' 96, January 1996
[26] A. Dingle, T. Partl, Web cache coherence, Fifth International World Wide Web Conference, Paris, France, 1996
[27] Felicia Doswell, Mark Abrams, Srinidhi Varadarajan, The Effectiveness of cache Coherence Implemented on the Web, http://citeseer.nj.nec.com/cache/papers/cs/26297/http:zSzzSzcsgrad.cs.vt.ed uzSz~doswellzSzresearchzSzpaperszSzwc3, pdf/the-effectiveness-of-cache, pdf
[28] E. Cohen, B. Krishnamurthy, J. Rexford, Improving end-to-end performance of the Web using server volumes and proxy filters, In Proceedings of Sigcomm' 98
[29] B. Krishnamurthy, C.E. Wills, Study of piggyback cache validation for proxy caches in theworldwideweb. In Proceedings of the USENIX Symposium on Internet Technologies and Systems(USITS' 97),December 1997:1-12
[30] B. Krishnamurthy, C.E. Wills, Piggyback server invalidation for proxy cache coherency, Computer Networks and ISDN Systems, April 1998. 30:185-194
[31] P. Cao, C. Liu, Maintaining strong cache consistency in the World Wide Web, In Proceedings of the 17th IEEE International Conference on Distributed Computing Systems, May 1997
[32] D. Willick, D. Eager, R. Bunt, Disk Cache Replacement Policies for Network Fileservers, In Proceedings of the 13th International Conference on Distributed Computing Systems, Pittsburgh, PA, May 1993:2-11
[33] S. Williams, M. Abrams, C. Standridge, et. al, Removal Policies in Network Caches for World Wide Web Documents, In Proceedings of the ACM SIGCOMM' 96, Stanford University, 1996
[34] Marc Abrams, Charles R. Standridge, Caching Proxies: Limitations and Potentials, In Proceedings of the 4th WWW Conference, Elsevier, Amsterdam, 1995:119-133
[35] P. Cao, S. Irani, Cost-aware WWW Proxy Caching Algorithms, In Proceedings of the 1997 USENIX Symposium on Internet Technology and Systems, December 1997:193-206
[36] P. Lorenzetti, L. Rizzo, Replacement Policies for a Proxy Cache, Technical Report University di Pisa, 1996
[37] R. Wooster, M. Abrams, Proxy Caching that Estimates Page Load Delays. In Proceedings of the 6th World Wide Web Conference, Santa Clara, California, 1997
[38] S. Irani, Page Replacement with Multi-Size Pages and Applications to Web Caching, In the Proceedings for the 29th Symposium on the Theory of Computing, 1997 701-710
[39] J. E. Pitkow, M. M. Recher, A Simple Yet Robust Caching Algorithm Based on Dynamic Access Patterns. In Proc. 2nd Int. WWW Conf, 1994
[40] 林永旺，网络业务与WWW缓存技术的研究：[博士论文]，中国科学院计算技术研究所，2000
[41] 郝沁汾，WWW访问特性与代理缓存研究：[博士论文]，中国科学院计算技术研究所，2001
[42] M. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979
[43] 孙红星，万麟瑞，李志飞，HTTP分布式缓存机制研究，计算机工程与应用，2002。2：62-65
[44] 周侯滨，Proxy Server中的Cache的管理和使用，现代计算机，2000。83：31-33
[45] M. F. Arlitt, C.L. Williamson, Trace-Driven simulation of Document Caching Strategies for Internet Web Servers, Simulations, 1997. 68(1): 23-33
[46] 铁玲，诸鸿文，戎蒙恬，一种新的优化Web缓存一致性的进化算法，小型微型计算机系统，2001。22(8)：940-942
[2] J. Wang, A survey of web caching schemes for the Internet, Computer Communication Review, October 1999. 29 (5): 36-46
[3] 庄伟强，集群服务器代理缓存技术研究：[博士学位论文]，清华大学研究生院，1999
[4] A. Fox, Steven D. Gribble, et. al, Cluster-based Scalable Network Service, In Proc. of the 16th ACM Symposium on Operating System Principles, Saint Malo, Oct 1997:78-91
[5] V. N. Padmanbhan, J. C. Mogul, Using Predictive Prefetching to Improve World Wide Web Latency, ACM Computer Communication Review, July 1996. 27 (3): 22-36
[6] R. Fielding, J. Gettys, J. Mogul, et. al, HyperText Transfer Protocol-HTTP/1. 1, IETF RFC 2068, January, 1997
[7] Rawn Shah, 使用Web高速缓存减少网络流量，http//www-9OO.Ibm.com/developerWorks/cn/web/webcachinga/index.shtml
[8] 陈兆良，代理服务器实战，软件世界，http:/tech.sina.com.cn,2000
[9] J. Shim, P. Scheuermann, R. Vingralek, Proxy Cache Design: Algorithms, Implementation and Performance, IEEE Trans. Knowledge and Data Engineering, 1999. 11(4): 549-562
[10] B. Krishnamurthy, C.E. Wills, Proxy cache coherency and replacement-towards a more complete picture, ICDC99, June 1999
[11] Jose Aguilar, Ernst L. Leiss,An Adaptive Cache Coherency-Replacement Scheme for Web Proxy Systems,in proceedings of SCI, 2001
[12] 沈庆伟，基于Internet的高速缓存技术分析，合肥工业大学学报，2002。25(3)：451-454
[13] 曾明(口月)，李建军，Internet访问管理与代理服务器，人民邮电出版社，2000
[14] 陈兵，王立松，基于哈希链表和时间链表的HTTP代理缓存机制的实现，南京航空航天大学学报，2002。34(1)：50-54
[15] D. Wessels, K. Claffy, Internet cache protocol(IPC),version 2, RFC 2186
[16] Anawat Chankhunthod,Peter B.Danzig,Chuch Neerdaels, et.al, A Hierarchical Internet Object Cache,Technical Report 95-611,Computer Science Department, University of Southern California, Los Angeles,California, March 1995
[17] Netscape Proxy Server 2.0, http://www.netscape.com/comprod/server_central/product/proxy/
[18] Squid, http://squid.nlanr.net/
[19] L. Cherkasova, G. Ciardo, Role of aging, frequency, and size in Web cache replacement policies, http://citeseer.nj.nec.com/cache/papers/cs/25725/http:zSzzSzwww, cs. wm. eduzS z~ciardozSzpubszSz2001taxonomy-gdfs, pdf/role-of-aging-frequency, pdf
[20] Gaura Banga, Fred Douglis, Michael Rabinovich, Optimistic Deltas for WWW Latency Reduction, In Proceedings of 1997 USENIX Technical Conference, 1997:289-303
[21] Gwetzman, M. Seltzer, World Wide Web cache consistency, In Proceedings of the USENIX Technical Conference, January 1996:141-152
[22] V. Cate, Alex-a global file system, In Proceedings of the 1992 USENIX File System Workshop, May 1992:1-12
[23] A. Luotonen, K. Altis, World Wide Web proxies, Computer Networks and ISDN Systems, First International Conference on WWW,. April 1994
[24] D. Wessels, Intelligent caching for World—Wide Web ob jects, In Proceedings of INET' 95, Honohlu, Hawaii, June 1995
[25] A. Chankhunthod, P. B. Danzing, C. Neerdaels, et. al, AhierarchicalInternet object cache, Usenix' 96, January 1996
[26] A. Dingle, T. Partl, Web cache coherence, Fifth International World Wide Web Conference, Paris, France, 1996
[27] Felicia Doswell, Mark Abrams, Srinidhi Varadarajan, The Effectiveness of cache Coherence Implemented on the Web, http://citeseer.nj.nec.com/cache/papers/cs/26297/http:zSzzSzcsgrad.cs.vt.ed uzSz~doswellzSzresearchzSzpaperszSzwc3, pdf/the-effectiveness-of-cache, pdf
[28] E. Cohen, B. Krishnamurthy, J. Rexford, Improving end-to-end performance of the Web using server volumes and proxy filters, In Proceedings of Sigcomm' 98
[29] B. Krishnamurthy, C.E. Wills, Study of piggyback cache validation for proxy caches in theworldwideweb. In Proceedings of the USENIX Symposium on Internet Technologies and Systems(USITS' 97),December 1997:1-12
[30] B. Krishnamurthy, C.E. Wills, Piggyback server invalidation for proxy cache coherency, Computer Networks and ISDN Systems, April 1998. 30:185-194
[31] P. Cao, C. Liu, Maintaining strong cache consistency in the World Wide Web, In Proceedings of the 17th IEEE International Conference on Distributed Computing Systems, May 1997
[32] D. Willick, D. Eager, R. Bunt, Disk Cache Replacement Policies for Network Fileservers, In Proceedings of the 13th International Conference on Distributed Computing Systems, Pittsburgh, PA, May 1993:2-11
[33] S. Williams, M. Abrams, C. Standridge, et. al, Removal Policies in Network Caches for World Wide Web Documents, In Proceedings of the ACM SIGCOMM' 96, Stanford University, 1996
[34] Marc Abrams, Charles R. Standridge, Caching Proxies: Limitations and Potentials, In Proceedings of the 4th WWW Conference, Elsevier, Amsterdam, 1995:119-133
[35] P. Cao, S. Irani, Cost-aware WWW Proxy Caching Algorithms, In Proceedings of the 1997 USENIX Symposium on Internet Technology and Systems, December 1997:193-206
[36] P. Lorenzetti, L. Rizzo, Replacement Policies for a Proxy Cache, Technical Report University di Pisa, 1996
[37] R. Wooster, M. Abrams, Proxy Caching that Estimates Page Load Delays. In Proceedings of the 6th World Wide Web Conference, Santa Clara, California, 1997
[38] S. Irani, Page Replacement with Multi-Size Pages and Applications to Web Caching, In the Proceedings for the 29th Symposium on the Theory of Computing, 1997 701-710
[39] J. E. Pitkow, M. M. Recher, A Simple Yet Robust Caching Algorithm Based on Dynamic Access Patterns. In Proc. 2nd Int. WWW Conf, 1994
[40] 林永旺，网络业务与WWW缓存技术的研究：[博士论文]，中国科学院计算技术研究所，2000
[41] 郝沁汾，WWW访问特性与代理缓存研究：[博士论文]，中国科学院计算技术研究所，2001
[42] M. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979
[43] 孙红星，万麟瑞，李志飞，HTTP分布式缓存机制研究，计算机工程与应用，2002。2：62-65
[44] 周侯滨，Proxy Server中的Cache的管理和使用，现代计算机，2000。83：31-33
[45] M. F. Arlitt, C.L. Williamson, Trace-Driven simulation of Document Caching Strategies for Internet Web Servers, Simulations, 1997. 68(1): 23-33
[46] 铁玲，诸鸿文，戎蒙恬，一种新的优化Web缓存一致性的进化算法，小型微型计算机系统，2001。22(8)：940-942