臺灣博碩士論文加值系統

隨著網際網路指數型的成長，網路壅塞的情形也越來越嚴重。一個熱門網頁可能被數以萬計的使用者要求，而造成整個區域網路癱瘓。為解決上述存在於Web上的問題，proxy cache server讓大多數的使用者從近端proxy server上就可以取得資料，減低使用者等待資料傳遞的時間是最普遍的作法，此外，透過proxy cache server也減低網路上的資料流量，節省大量的網路頻寬，也減輕網頁伺服器的負擔。而在proxy cache server的設計上，置換策略是核心技術，適當的置換策略將使得網路上的資源得到最佳利用。
本論文針對以往的置換策略，提出新的部分置換擷取策略，其中分為兩個部份，一個是部分擷取策略，一個是部分置換策略。以提高Web cache的效能與服務品質。透過模擬分析實驗結果，部分擷取置換策略在保持最低的時間複雜度之情況下，確實可以同時改善Web cache上三種效能與服務品質，並且可以有效的解決置換策略上，因不當置換所帶來的不良影響，
以改善Web上資訊之存取效率。
部分擷取策略對於LRU在hit rate、 byte hit rate與reduced latency rate上，可以達到的最佳改善率分別為26\%、 32\% 與50\%。部分置換策略則可以達到的最佳改善率分別為12\%、18\% 與19\%。同時部分擷取置換策略也改善LRU-THOLD只在hit rate表現較好，在byte hit rate與reduced latency rate上卻表現差的情形。部分擷取策略對於LRU-THOLD在hit rate、 byte hit rate與reduced latency rate上的最佳改善率分別為17\% 、114\% 與48\%。部分置換策略的最佳改善率分別為12\%、 30\% 與20\%。
綜合以上所敘述，部分擷取置換策略，在保持最低的時間複雜度之情況下，確實可以有效改善效能與服務品質，如果實作於目前的網路環境當中，將可以改善Web上資訊之存取效率。

The performance of accessing information is crucial for the success of Web. The Web proxy server plays an important role in improving the performance and quality of services. The access latency time can be reduced, if users get objects from the near proxy servers. In addition, the load of Web servers and network traffic can be thus reduced. From our studies, we find that the caching replacement algorithm is a key issue in Web proxy server design. It decides which object will be evicted from the cache to get enough space for the new object. The design of the cache replacement algorithm influences the re-usability of the cached information.
In this thesis, two novel caching replacement policies are proposed. The first is the Partial Caching LRU( PC-LRU), and the second is called the Partial Replacement LRU-THOLD( PR-LRU-THOLD). Trace-driven simulations are also performed. The experiment results show that our schemes improve the cache hit rate, the byte hit rate and the access latency. In addition, the complexity of the schemes is near O(1) on average.
Compared with LRU, PC-LRU improves the hit rate by 26%,
the byte hit rate by 32%, and the reduced latency rate by 50% in the receptive best case. PR-LRU-THOLD improves the hit rate by 12%, the byte hit rate by 18%, and the reduced latency rate by 19% in the best case. Compared with LRU-THOLD, PC-LRU improves the hit rate by 17%, the byte hit rate by 114%, and the reduced latency rate by 48% in the best case. PR-LRU-THOLD improves the hit rate by 12%, the byte hit rate by 30%, and the reduced latency rate by 20% in the best case.
We conclude that the partial caching replacement policies indeed improve the Web proxy performance. Furthermore, the concept of our schemes can be potentially applied to other categories of replacement algorithms.

1 緒論
1.1 研究動機與背景
1.2 研究目的
1.3 研究方法與步驟
1.4 章節概要
2 相關研究
2.1 效能評估標準
2.2 現有改善效能的方法
2.3 相關置換策略
2.3.1 基礎的置換演算法
2.3.1.1 Least-Recently-Used Policies
2.3.1.2 Least Frequently Used Policy
2.3.1.3 SIZE Policy
2.3.1.4 Lowest Latency First Policy
2.3.2 複合的置換策略
2.3.2.1 Greedy Dual-Size
2.3.2.2 Greedy Dual-Size with Frequency and Least Frequently Used with Dynamic Aging
2.3.2.3 Hybrid Algorithm
2.3.2.4 LNC-R-W3 and LNC-R-W3-U
2.4 Adaptive Replacement Algorithm
2.5 Replacement Policy 的分析比較
2.6 本章總結
3 部分擷取與部分置換演算法
3.1 演算法的設計考量
3.2 Partial Least Recently Used 演算法
3.2.2.1 Partial Replacement Least-Recently-Used 置換演算法
3.2.2.2 Partial Replacement Least-Recently-Used-Threshold 置換演算法
3.3 不完整物件傳輸的爭議
3.4 本章總結
4 效能模擬分析
4.1 模擬環境及假設
4.2 模擬分析實驗之參數說明
4.3 部分擷取策略的模擬分析
4.3.1 實驗一：cache飽和度對Partial Cache LRU-THOLD的影響
4.3.2 實驗二：Partial Cache LRU-THOLD的門檻影響
4.3.3 實驗三：Partial Cache LRU-THOLD結果分析比較
4.3.4 實驗四：不同傳輸延遲下的結果分析比較
4.3.5 實驗五：不同擷取比率下的分析比較
4.4 部分置換策略的模擬分析
4.4.1 實驗六：Partial Replacement LRU 的 threshold 影響
4.4.2 實驗七：Partial Replacement LRU 結果分析比較
4.4.3 實驗八：Partial Replacement LRU-THOLD 結果分析比較
4.4.4 實驗九：改變置換次序後的部分置換策略模擬分析
4.4.5 實驗十：改變置換時機後的部分置換策略模擬分析
4.5 本章總結
5 結論與未來展望
5.1 結論
5.2 未來展望

[1] Scott Michel, Khoi Nguyen, Adam Rosenstein, and Lixia Zhang. Adaptive Web
Caching: Towards a New Caching Architecture. In Proceedings of the 3rd Interna-tional
Web Caching Workshop, June 1998.
[2] Junho Shim, Peter Scheuermann, and Radek Vingralek. Proxy Cache Algorithms:
Desogn, Implementation, and Performance. IEEE Transactions on Knowledge and
Data Engineering, 11(4), July 1999.
[3] Brain D. Davison. A Survey of Proxy Cache Evaluation Techiques. In Proceedings
of the 4th International WWW Caching Workshop, April 1999.
[4] Computer Industry Almanac Inc. U.S. Tops 100 Million Internet Users According
to Computer Industry Almanac, November 1999.
http://www.c-i-a.com/199911iu.htm.
[5] Ovum. Online Population to Quadruple, December 1998.
http://cyberatlas.internet.com.
[6] Mehmet Sayal, Yuri Breitbart, Peter Scheuermann, and Radek Vingralek. Selection
Algorithms for Replicated Web Servers. In Proceedings of the Workshop on Internet
Server Performance, 1998.
[7] Duane Wessels and K. Claffy. ICP and the Squid Web Cache. IEEE Journal on
Selected Areas in Communications, 16(3):345.
[8] Duane Wessels and K. Claffy. Internet Cache Protocol (ICP) version 2. RFC 2186.
[9] Duane Wessels and K. Claffy. Application of Internet Cache Protocol (ICP) version
2. RFC 2187.
[10] Lixa Zhang, Sally Floyd, and Van Jacobson. Adaptive Web Caching, February 1997.
Initial Proposal.
[11] Alex Rousskov and Duane Wessels. Cache Digest. In Proceedings of the 3rd Inter-national
Web Caching Workshop, April 1998.
[12] Plabo Rodriguez, Ernst W. Biersack, and Keith W. Ross. Improving the WWW:
Caching or Multicast? In Proceedings of the 3rd International Web Caching Work-shop,
June 1998.
[13] Pablo Rodriguez, Christian Spanner, and Ernst W. Biersack. Web Caching Architec-tures:
Hierarchical and Distributed Caching. In Proceedings of the 4th International
WWW Caching Workshop, April 1999.
[14] Zheng Wang and Jon Crowcroft. Prefetching in World Wide Web. In IEEE Globe-com’96,
1996.
[15] Mark Russell and Tim Hopkins. CFTP- A Caching FTP Server. In Proceedings of
the 3rd International Web Caching Workshop, June 1998.
[16] 呂信益, 王仕榮, 曾黎明. 以需求為導向之資料複製再用型檔案檔案傳輸伺服器.In Proceedings of the
1999 Workshop on Distribution System Technologies and Applications, pages 360-
367, Tai wan, 1999.
[17] Marc Abrams, Charles R. Standridge, Ghaleb Abdulla, Stephen Williams, and Ed-ward
A. Fox. Caching Proxies: Limitations and Potentials. In Proceedings of the
4th International WWW Conference, July 1995.
[18] Marc Abrams, Ghaleb Abdulla, Stephen Williams, and Edward A. Fox. Removal
Policies in NetWork Caches for WWW Documents. In Proceedings of the ACM
SIGCOMM96, August 1996.
[19] Martin Arlitt, Ludmila Cherkasova, John Dilley, Rich Friedrich, and Tai Jin. Eval-uating
Content Management Techniques for Web Proxy Caches. In Proceedings of
the 4th International WWW Caching Workshop, April 1999.
[20] Roland Peter Wooster. Optimizing Response Time, Rather than Hit Rates, of WWW
Proxy Cache. Master’s thesis, Virginia Polytechnic Institute and State University,
Blacksburg, Virginia, December 1996.
[21] Bradley M. Duska, David Marwood, and Michael J. Feeley. The Measured Ac-cess
Characteristics of World-Wide-Web Client Proxy Caches. In Proceedings of
the USENIX Symposium on Internet Technologies and Systems (USITS), December
1997.
[22] Terence P. Kelly, Yee-Man Chan, Sugih Jamin, and Jeffrey K. Mackie-Mason. Bi-ased
Replacement Policies for Web Caches: Differential Quality-of Service and Ag-gregate
User Value. In Proceedings of the 4th International WWW Caching Work-shop,
April 1999.
[23] Roland P. Wooster and Marc Abrams. Proxy Caching the Estimates Page Load
Delays. In Proceedings of the 6th International World Wide Web Conference, pages
7—11, April 1997.
[24] Annie P. Foong, Yu hen Hu, and Dennis M. Heisey. Logistic Regression in an
Adaptive Web Cache. IEEE Internet Computing, pages 27—36, September 1999.
[25] Squid Internet Object Cache.
http://squid.nlanr.net/Squid.
[26] John Dilley, Martin Arlitt, and Stephane Perret. Enhancement and Validation of
Squid’s Cache Replacement Policy. In Proceedings of the 4th International WWW
Caching Workshop, April 1999.
[27] Charu Aggarwal, Joel L. Wolf, and Philipm S. Yu. Caching on the World Wide Web.
IEEE Transactions on Knowledge and Data Engineering, 11(1), January 1999.
[28] Pei Cao and Sandy Irani. Cost-Aware WWW Proxy Caching Algorithms. In Pro-ceedings
of the USENIX Symposium on Internet Technologies and Systems (USITS),
pages 193—206, December 1997.
[29] Jean-Chrysostome Bolot and Philipp Hoschka. Performance Engineering of the
Wor l d Wi de Web. WWW Journal 1, 3:185—195, 1996.
[30] Junho Shim, Peter Scheuermann, and Radek Vingralek. A Case for Delay-Conscious
Caching of Web Documents. In Proceedings of the 6th International World Wide
Web Conference, 1996.
[31] Fielding et al. Hypertext Transfer Protocol — HTTP/1.1, June 1999. RFC2616.
[32] Apache 1.3 documentation.
http://rukawa.dyndns.org/manual/index.html.
[33] Internet information server 4.0.
http://msdn.microsoft.com/workshop/essentials/forstarters/starts031698.asp.
[34] Pei Cao. Web cache simulator.
http://www.cs.wisc.edu/˜cao/webcache-simulator.html.