網際網路和相關服務的發展已經深遠的改變了人們的生活。隨選視訊的應用也大量的成長。但此類的服務往往會由於本身大量的頻寛使用和儲存空間需求而成為網路的瓶頸。為了要解決這個問題，我們在本篇論文中提出一個視訊快取伺服器的架構。為了讓快取伺服器中快取資料的命中率提高，我們針對每一部影片的受歡迎程度儲存部份的資料。此外，我們利用Fibonacci 函數將多媒體資料切割成不同大小的片段。藉由這個切割方式，我們可以增加資料配置及代換的速度。在多媒體資料的傳輸時期，我們利用指數函數提出一個新的傳輸速率調整機制。這個方法可以增加可用頻寛的使用量以及減少資料遺失的比例。根據初步的分析和模擬結果的成果評估可以得知我們的方法與其他的類似方法相比具有正面的效能改善。詳細的設計原理、運作流程以及效能評估將會在論文往後的章節中一一介紹。

The advances in Internet and related services have changed human’s life. The application of multimedia-on-demand also grows up dramatically. However, this kind of services may cause the bottleneck of Internet due to the bandwidth requirement and storage constraint of multimedia data. In order to resolve this problem, we propose the streaming proxy architecture in this thesis. We place a streaming proxy that is close to clients, and the proxy forwards and caches frequent and popular video programs according to the viewing behavior of clients. The cache-hit rate should be high in order to reduce the load of network and response time of client. To achieve this goal, we store portions of each video program according to its popularity. Additionally, we use Fibonacci function to divide the video data into variable-sized segments. By this way, we can speed up the data allocation and cache replacement. During the transmission of video data for each session, we also propose a new transmission rate control mechanism based on exponential function. It can achieve higher bandwidth utilization and lower data loss rate. According to our preliminary analysis and performance evaluations by simulation, we can show that our techniques have positive results compared with other similar methods. The detail information will be given in the contents.

摘要 i
Abstract ii
Acknoledgement iii
Table of Contents iv
List of Figures and Tables vi
Chapter 1 Introduction 1
Chapter 2 Fundamental Background and Related Work 5
2.1 Overview Architecture 5
2.2 Survey of Replacement Methods 6
2.2.1 Fine-Grained Scalable Video Coding 6
2.2.2 Prefix Caching 7
2.2.3 Smallest Caching Utility 8
2.2.4 Segment-Based Caching 10
2.3 Survey of Rate Control Techniques 12
2.3.1 AIMD Rate Control Mechanism 12
2.3.2 Receiver-Based Rate control 13
Chapter 3 Fibonacci Replacement Scheme 16
3.1 Basic Service Flow 16
3.2 Design Issues and Architecture Properties 18
3.3 Fibonacci Replacement Scheme 20
3.3.1 Data Placement 20
3.3.2 Popularity Function 21
3.3.3 Replacement Scheme 23
Chapter 4 Exponential Rate Control Scheme 30
4.1 Exponential Rate Control Scheme 30
4.1.1 Available Bandwidth Prediction 31
4.1.2 Upper Bound Selection 33
4.1.3 Video Quality Adaptation 34
4.4.4 Design of Our Exponential Rate Control Mechanism 35
4.2 Preliminary Analysis 40
4.2.1 Analysis of Replacement Decision 40
4.2.2 Analysis of Rate Control Mechanism 43
Chapter 5 Simulation Environment and Performance Evaluation 46
5.1 Simulation Environment 46
5.1.1 Structure of Simulator 46
5.1.2 Input Data Pattern and System Parameters 48
5.2 Performance Evaluation 48
5.2.1 Evaluation of Replacement 48
5.2.2 Evaluation of Rate Control 57
Chapter 6 Conclusion and Future Work 62
Bibliography 65

[1] Meira, W., Jr., Fonseca, E., Murta, C., and Almeida, V., “Analyzing performance of cache server hierarchies”, Proc. of XVIII International Conference of the Chilean Society on Computer Science, pp. 113 —121, 1998.
[2] Y.B. Lee, “Parallel Video Servers : A Tutorial”, IEEE Multimedia, No. 5, Issue 2, pp. 20 —28, April-June 1998.
[3] A.; Das, Sun-Euy Kim and C.R., “Analyzing Cache Performance for Video Servers”, Proceedings of the 1998 ICPP Workshops on Sivasubramaniam, Architectural and OS Support for Multimedia Applications/Flexible Communication Systems/Wireless Networks and Mobile Computing, pp.38 —47, 1998.
[4] Chiu, Y.M. and Yeung, K.H., “Partial video sequence caching scheme for VOD systems with heterogeneous clients”, Proc. Of 13th International Conference on Data Engineering, pp.323 —332, 1997.
[5] Radhika Malpani, Jacob Lorch, and David A. Berger, “Making World Wide Web Caching Servers Cooperate”, available at http://www.bmrc.berkeley.edu/research/publication/1995/138/paper-59.html.
[6] S. Sen, J. Rexford, and D. Towsley, “Proxy prefix caching for multimedia streams”, Proc. of the Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 3, pp.1310-1319, 1999.
[7] Eun-Ji Lim, Seong-Ho Park, Hyeon-Ok Hong, and Ki-Dong Chung, ”A proxy caching scheme for continuous media streams on the Internet”, Proc. of the 15th International Conference on Information Networking, pp. 720—725,2001.
[8] Kun-Lung Wu, Philip S. Yu, and Joel L. Wolf, “Segment-based proxy caching of multimedia streams”, Proc. of the Tenth International World Wide Web Conference, pp. 36-44, 2001.
[9] Y.R. Yang and S.S. Lam, “General AIMD congestion control“, Proc. of International Conference on Network Protocols, pp. 187—198, 2000.
[10] Yon Jun Chung, Young-Gook Kim, JongWon Kim, C.-C. Jay Kuo, “Receiver-Based Congestion Control Mechanism for Internet Video Transmission”, IEEE International Symposium on Circuits and Systems, Vol. 4, pp. 239-242, 1999.
[11] Dapeng Wu; Hou, Y.T.; Wenwu Zhu; Ya-Qin Zhang; Peha, J.M., “Streaming video over the Internet: approaches and directions”, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 11, Issue: 3, pp.282 —300,March 2001.
[12] Radha, H.M., van der Schaar, M., Yingwei Chen, “The MPEG-4 fine-grained scalable video coding method for multimedia streaming over IP”, IEEE Transactions on Multimedia, Vol. 3, Issue: 1, pp.53 —68, March 2001.
[13] Fibonacci Numbers, the Golden section and the Golden String, http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html.
[14] Busari, M. and Williamson, C, “On the sensitivity of Web proxy cache performance to workload characteristics”, Proc. of IEEE INFOCOM, Vol. 3, pp. 1225 —1234, 2001.
[15] The Exponential Function, http://mathinsite.bmth.ac.uk/applet/exponential/exp.html.
[16] Iperf 1.6 - The TCP/UDP Bandwidth Measurement Tool, http://dast.nlanr.net/Projects/Iperf/.
[17] Shin-Tse Cheng, Yu-Zhan Hou, Cheng Chen, and Suh-Yin Lee, “An Effective Data Placement Scheme for Supporting VCD Functionality in an Video Server”, Proc. of the International Computer Symposium, Taiwan, R.O.C., Workshop on Computer Network, Internet and Multimedia, pp.96-103, 1998.
[18] Windows 2000 Professional Home, http://www.microsoft.com/windows2000/professional/default.asp.
[19] Microsoft Visual C++ .NET Home Page, http://msdn.microsoft.com/visualc/.
[20] T.T. Kwan, R. McGrath, and D.A. Reed, “NCSA’s World Wide Web Server: Design and Performance”, Computer, Vol. 28, no. 11, pp. 68-74, Nov. 1995.
[21] Michael Rabinovich and Amit Aggarwal, “RaDaR: a scalable architecture for a global Web hosting service”, ACM Computer Networks, Vol.31, pp.1545-1561, July 1999.
[22] E. Casalicchio and M. Colajanni, “Scalable Web clusters with static and dynamic contents”, Proc. of IEEE International Conference on Cluster Computing, pp. 170—177, 2000.
[23] Ramesh, S.; Rhee, I.; Guo, K, ”Multicast with cache (Mcache): an adaptive zero-delay video-on-demand service”, IEEE Trans. on Circuits and Systems for Video Technology, Vol. 11, Issue: 3, pp. 440 —456,March 2001.
[24] Multicast Transport Protocols, http://www.roads.lut.ac.uk/DS-Archive/MTP.html.
[25] R. Rejaie and J. Kangasharju, ”Mocha: A Quality Adaptive Multimedia Proxy Cache for Internet Streaming”, Proc. of NOSSDAV, Port Jefferson, NY, USA, June 25-26 2001.
[26] Chia-Wen Lin, Jian Zhou, Jeongnam Youn, and Ming-Ting Sun, “MPEG video streaming with VCR functionality,” IEEE Trans. on Circuits and Systems for Video Technology, special issue on Internet streaming video, Vol. 11, no. 3, pp. 415-425, Mar. 2001.
[27] Jau-Hsiung Huang and Yin-Ting Tsai, “Content Replication and Migration in Multimedia Streaming Framework”, Master Thesis, National Taiwan University, June 2001.
[28] Yu-Jin Wang, Yi-Shou Lin, S.W.Huang and Cheng Chen, "An Efficient Data Replacement Scheme within Video Proxy for VOD System", Proc. of the National Computer Symposium, Workshop on Multimedia, Computer Graphics, and Image Processing, Taiwan, R.O.C., pp. D123-D133, 2001.
[29] Ju-Kau Chen, Wen-Shih Huang, Cheng Chen, and Suh-Yin Lee, “CSSP: An Effective Static Content Placement Policy for Load-Balancing in Video Server”, Proc. of the International Computer Symposium, Workshop on Computer Network, Internet and Multimedia, Taiwan, R.O.C., pp.104-110, 1998.
[30] Wen Shih Huang, Cheng Zen Yang, and Cheng Chen, “An Effective Data Placement Scheme to Support Fault-Tolerance in Video on Demand Server System”, Proc. of the National Computer Symposium, Taiwan, R.O.C., Vol.3, pp.297-304, 1999.
[31] Yu-Zhan Hou, Yu-Jiin Wang, and Cheng Chen, “An Effective Scheduling Policy in Large-Scale Video Servers”, Proc. of the National Computer Symposium, Taiwan, R.O.C., Vol.3, pp.345-352, 1999.