臺灣博碩士論文加值系統

部分儲存式代理快取或稱分段儲存式快取，是將物件分成許多獨立的檔案片段加以儲存或移除。當快取伺服器收到使用者的要求時，會先將儲存在快取中的檔案片段傳給使用者以減低使用者感受到的回應的延遲。在這篇論文中我們檢視了將這個理念實現在快取上的可能性。首先，我們提出了一個可以利用現有的HTTP來對多媒體檔案進行快取的架構。在這個架構下，可以明顯地降低使用者所感受到的傳輸延遲，互動式VCR多媒體的存取也可實現，最重要的是我們可以簡化現有代理快取伺服器在快取多媒體檔案的設計。同時我們也提到部分儲存式代理快取伺服器所面臨到的重要問題：我們稱它為「過期開頭片段問題」，也就是說快取中儲存的片段和原始伺服器端的不一樣。如果發生這樣的問題將導致使用者前後所得到的檔案不連貫。如此，使用者會先收到在快取上的過期資料，並和後來從伺服端得到的新資料不能連貫。要解決這樣的問題，我們提出了一個創新的演算法稱為「部分移除確認」，這個演算法將取得伺服器端物件一致性的確認，物件的分段以及移除放在一起做。結果顯示我們所提的方法除了有效的降低了上述不一致性的發生機率，且可以簡單地實作在現有的快取軟體架構之下並明顯的降低在多媒體檔案傳輸上的起始延遲。

Proxy partial caching, e.g. segment-based proxy caching or proxy prefix caching, partitions the object into non-overlapping pieces. The proxy cache then treats each piece as an individual file when performing caching and replacing. Upon receipt of request to the object, the proxy cache delivers the cached portion to the client immediately to mask the start-up delay. In this thesis, we examine the viability of applying this technique to web proxy cache. First, we propose a architecture of caching multimedia streams via HTTP. With in this proposed architecture, the start-up delay of video playout is easily masked, the interactive VCR function can be realized, and caching the multimedia streams in the web proxy cache can be greatly simplified. Second, proxy partial caching introduces a problem called dirty-first-segment problem, i.e. cached portion in the proxy cache is inconsistent with the original in the server. If it happens, cached portion cannot be concatenated with the latter portion from the server. As a result, user will receive cached portion first and then perceive an undesirable situation, such as a discontinuous video playout. To relieve this problem, we propose a novel algorithm called validating upon partial replacement, which synchronizes the operation of proactive consistency validation, partition, and replacement performed upon an object. We show that our proposed algorithm bears the merits of controllable chance to disturb users, easily embedding into the existing web proxy cache software with minimum modification, and significant improvement of cache performance in the aspect of start-up delay reduction for multimedia stream accesses.

Chapter 1: Introduction
Chapter 2: Architecture for Streaming Video Retrieval
Chapter 3: Validating upon Partial Replacement
3.1 The Proxy Partial Caching via Objects’ Utilities
3.2 Sizing Object under Partial Replacement
3.3 On Accessing A Partially Cached Object
3.4 Overloading Avoidance and The Algorithm
Chapter 4: Defining ε(•)
Chapter 5: Simulation Results
5.1 Simulation Setup
5.2 Simulation Results
Chapter 6: An Implementation Survey on Squid
6.1 Introduction to Squid
6.2 Software Architecture
6.2.1 Client Side
6.2.2 Server Side
6.2.3 Storage Manager
6.2.4 Network Communication
6.2.5 Redirectors
6.2.6 Event Queue
6.2.7 Callback Data Database
6.2.8 Cache Manager
6.2.9 Network Measurement Database
6.2.10 Other Component
6.3 Flow of a Typical Request
6.4 Replacement Policy
6.4.1 Squid 1.1
6.4.2 Squid 2
6.5 Refreshment Policy
Chapter 7: Related Works
7.1 Cache Replacement Policies
7.2 Cache Consistency Mechanisms
7.3 Previous work on Proxy Partial Caching
7.3.1 Caching fixed-size initial portion of an object
7.3.2 Caching variable-size initial portion of an object
7.3.3 Caching hotspot portion for supporting interactive functions
7.3.4 Partial replacement
Chapter 8: Conclusion and Future Work

[1] Brewington, B.E.; Cybenko, G., “Keeping up with the changing Web,” IEEE Computer , Volume: 33 Issue: 5 , May 2000 Page(s): 52 -58
[2] Pei Cao and Sandy Irani. “Cost-aware WWW proxy caching algorithm,” In Proceedings of the 1997 Usenix Symposium on Internet Technologies and Systems (USITS-97), Monterey, CA, December 1997.
[3] Vincent Cate. “Alex — a global file system,” In Proceedings of the USENIX File System Workshop, pages 1-11, Ann Arbor, Michigan, May 1992.
http://ankara.bcc.bilkent.edu.tr/prv/ftp/INFO/Internet/Alex/usenix.wofs92.ps
[4] Kuei-Hui Chen and Cheng-Zen Yang. Partial caching replacement policies for Web proxy. Master’s thesis, Tuan-Ze University, June 2000.
[5] L. Cherkasova. “Improving WWW proxies performance with greedy-dual-size-frequency caching policy,” Technical Report HPL-98-69R1, Hewlett-Packard Laboratories, November 1998.
[6] Edith Cohen and Haim Kaplan, ”Refreshment policies for Web content caches,” In Proceedings of the IEEE INFOCOM conference, April 2001
[7] Sandra G. Dykes and Kay A. Robbins. “A viability analysis of cooperative proxy caching,” IEEE Infocom’01, April 2001.
[8] Derek L. Eager, Michael C. Ferris, and MaryK. Vernon. “Optimized regional caching for on-demand data delivery,” In Proceedings of Multimedia Computing and Networking, January 1999.
[9] Husni Fahmi et al. “Proxy servers for scalable interactive video support,” IEEE Computer, pages 54-60, September 2001.
[10] Stephane Gruber, Jennifer Rexford, and Andrea Basso. “Protocol consideration for a prefix-caching proxy for multimedia streams,” Computer Networks, 33(1-6):657-668, June 2000.
[11] Shudong Jin and Azer Bestavros, “Temporal Locality in Web Request Streams,” In Proc. 2000 ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems, Santa Clara, CA, June 2000.
[12] Shudong Jin, Azer Bestavros, and Arun Iyengar. Accelerating internet streaming media delivery using network-aware partial caching. In IEEE ICDCS’2002, 2002.
[13] Balachander Krishnamurthy and Jennifer Rexford. Web protocols and Practice. Addison-Wesley, 2000.
[14] Balachander Krishnamurthy and Craig E. Willis. “Piggyback cache validation for proxy caches in the World-Wide Web,” In Proceedings of the 1997 NLANR Web Cache Workshop, June 1997.
[15] W.K. Liao and C.T. King. Proxy prefetch and prefix caching. In ICPP’01, September 2001.
[16] Pei Cao and Chengjie Liu, “Maintaining Strong Cache Consistency in the World-Wide Web,” IEEE Transactions on Computers, 47(4):445--457, Apr. 1998.
[17] Subhabrata Sen, Jennifer Rexford, and Don Towsley. “Proxy prefix caching for multimedia streams,” In IEEE Infocom’99, March 1999.
[18] Takayuki Warabino and et al. Video transcoding proxy for 3Gwireless mobile Internet access. IEEE Communications Magazine, 38(10):66 — 71, October 2000.
[19] Kun-Lung Wu, Philip S. Yu and Joel L. Wolf, “Segment-Based Proxy Caching of Multimedia Streams,” The tenth international World Wide Web conference on World Wide Web, April 2001.
[20] John Dilley, Martin Arlitt and Stephane Perret, ”Enhancement and Validation of Squid’s Cache Replacement Policy,” In Proceedings of the 4th International Web Caching Workshop, March/April 1999.
[21] Jia Wang, “A Survey of Web Caching Schemes for the Internet,” ACM Computer Communication Review, 29(5):36--46, October 1999.
[22] Dilley, J. “The Effect of Consistency on Cache Response Time,” IEEE Network , Volume: 14 Issue: 3 , May-June 2000 Page(s): 24 -28
[23] Tsong-Ho Wu; Korpeoglu, I.; Bo-Chao Cheng, “Distributed interactive video system design and analysis,” IEEE Communications Magazine , Volume: 35 Issue: 3 , March 1997 Page(s): 100 -108