臺灣博碩士論文加值系統

隨著資訊技術的快速發展，網路的速度愈來愈快，人們使用網路就再也不是單純傳送文字或檔案，具有即時性的資料，如聲音或影像等多媒體也開始可以在網路上流動，於是如何讓使用者可以得到最佳的服務品質(QoS)自然成為了一個值得探討的問題。
在現今多媒體串流的通訊協定下，例如RTSP(Real Time Streaming Protocol)，我們自行設計了一套可以有效縮短使用者等待時間和提高服務品質的系統架構。在這個架構下，我們會使用到三種伺服器，就是「導向伺服器(Redirector)」、「資料伺服器(Context Repository)」和「多媒體串流伺服器（Prefix Cache）」，他們的功能將會在下面的文章作詳系的介紹。在一開始，使用者會先一個中央控管的導向伺服器提出請求，接著導向伺服器會找出最適合伺服這個使用者的多媒體串流伺服器來傳輸多媒體資料。
在我們設計的系統架構下，多媒體串流伺服器只會儲存多媒體的開頭的片段，這是為了縮短使用者的等待時間，同時也可以節省多媒體串流伺服器的儲存空間。完整的多媒體資料會被放置在資料伺服器上，所以如果使用者想要欣賞完整的多媒體資料時，多媒體串流伺服器便會向資料伺服器下載其餘的多媒體資料。然而該向那一台資料伺服器下載？還有該把完整的資料擺在哪幾台資料伺服器最好？這些關鍵性的問題將在這篇論文裡面獲得解決。

According to the progress of information technology, the bandwidth of network has become larger and larger. Not only pure data or file can be conveyed in network, people can transmit real-time data such as audio and video. As a result, the question of how to improve user’s quality of service (QoS) naturally becomes an important issue of research.
According to multimedia streaming protocol today, such as RTSP (Real Time Streaming Protocol), we design a multimedia streaming framework which can reduce user’s waiting time and improve user’s quality of service efficiently. In our framework, we use three kinds of servers, namely “Redirector”, “Content Repository”, and “Prefix Cache”, the details of their functionality will be explained later. At the beginning, user’s request will be handled by our central-control Redirector first, and then Redirector will find the most suitable Multimedia Streaming Server to transfer multimedia data.
In our framework, Prefix Caches could merely store the prefix of multimedia data, this is for the reason of reducing user’s waiting time, and save servers’ hard-disk space at the same time. Entire multimedia data will be stored at Content Repositories, therefore, when somebody want to appreciate entire multimedia data, Multimedia Streaming Servers will download the rest of multimedia data from Content Repositories, of course. However, which Content Repository should we choose? Furthermore, which Content Repository would the best choice to store the entire replica of multimedia data? These critical problems would be solved in this paper.

目錄
第一章 緒論1
第一節 前言1
第二節 Multimedia Streaming Framework簡介1
第三節 Content Replication and Migration簡介3
第四節 論文章節編排4
第二章 相關研究5
第三章 Multimedia Streaming Framework6
第一節 Framework概觀6
第二節 Redirector功能介紹7
第三節 Content Repository功能介紹10
第四節 Prefix Cache功能介紹12
第四章 Content Replication and Migration15
第一節 Location Problem15
§4.1.1 Maximum Covering Location Problem17
§4.1.2 Greedy Algorithm19
§4.1.3 Lagrangian Relaxation23
第二節 Mapping to Computer Network28
第三節 Example33
第四節 Migration的時機38
第五章 結論及未來展望40
第一節 結論40
第二節 未來工作41
參考資料43

〔1〕P. Krishnan, Danny Raz, Member, IEEE, and Yuval Shavitt, Member IEEE, “The Cache Location Problem”, IEEE/ACM Transaction On Networking, Vol 8, No. 5, October 2000
〔2〕Mark S. Daskin, “Network and Discrete Location Models, Algorithms, and Application”, 1995, John Wiley & Sons, Inc.
〔3〕Mark S. Daskin, “A New Approach to Solving the Vertex P-Center Problem to Optimality: Algorithm and Computational Results”
〔4〕Makhtar S. Bazaraa, Hanif D. Sherali, C. M. Shetty, “Nonlinear Programming Theory And Algorithms”, 1995, John Wiley & Sons, Inc.
〔5〕Robert L. Carter, Mark E. Crovella, “Dynamic Server Selection using Bandwidth Probing in Wide-Area Networks”, Boston University, March 18, 1996
〔6〕Robert L. Carter, Mark E. Crovella, “Measuring Bottleneck Link Speed in Packet-Switched Networks”, Boston University, March 15, 1996
〔7〕Mark E. Crovella Robert L. Carter, “Dynamic Server Selection in the Internet” , Boston University, June 30, 1995
〔8〕Fabian A. Chudak, “Improved approximation algorithms for uncapacitated facility location”, School of Operations Research & Industrial Engineering, Cornell University, Ithaca, NY
〔9〕Fabian A. Chudak David B. Shmoys, “Improved approximation algorithms for capacitated facility location problem”, School of Operations Research & Industrial Engineering, Cornell University, Ithaca, NY
〔10〕Eitan Altman, Konstantin Avrachenkov, Chadi Barakat, “A Stochastic Model of TCP/IP with Stationary Random Losses”, Sigcomm ’00
〔11〕David A. Turner, Keith W. Ross, “Continuous Media E-Mail on the Internet: Infrastructure Inadequacies and a Sender-Side Solution”, IEEE Network, July/August 2000.
〔12〕Li Fan, Pei Cao Jussara Almeida, Andrei Z. Broder, “Summary Cache: A Scalable Wide-Area Sharing Protocol”, IEEE/ACM Transaction On Networking
〔13〕John Dilley Martin Arlitt, “IMPROVING PROXY CACHE PERFORMANCE: Analysis of Three Replacement Policies”, IEEE Internet computing, November/December 1999
〔14〕Sanjoy Paul Zongming Fei, “Distributed Caching with Centralized Control”
〔15〕Michael Rabinovich, Amit Aggarwal, “RaDaR: A Scalable Architecture for a Globla Web Hosting Service”, WWW8 / Computer Networks
〔16〕Amit Aggarwal Michael Rabinovich, “Performance of Dynamic Replication Schemes for an Internet Hosting Service”, Department of Computer Science, University of Washington
〔17〕Michael Rabinovich, Irina Rabinovich, Rajmohan Rajaraman, “A Dynamic Object Replication and Migration Protocol for an Internet Hosting Service”, Department of Computer Science, University of Washington
〔18〕P. Krishnan, Danny Raz, Yuval Shavitt, “Transparent En-Route Cache Location for Regular Networks”, Department of Computer Science, University of Washington
〔19〕Michael Rabinovich, Irina Rabinovich, Rajmohan Rajarman, “Dynamic Replication on the Internet”, AT&T Labs Research.
〔20〕Kevin Lai, Mary Baker, “Measuring Link Bandwidths Using a Deterministic Model of Packet Delay”, SIGCOM ‘00
〔21〕Bo Li, Morecai J. Golin, Giuseppe F. Italiano, Xin Den, “On the Optimal Placement of Web Proxies in the Internet”, Proceedings of Infocom'99
〔22〕Moses Charikar, Sudipto Guha, Eva Tardos, David B. Shmoys, “A constant-factor approximation algorithm for the k-media problem”, ACM Symposium on Theory of Computing
〔23〕N.G. Duffield, K. K. Ramakrishnan, Amy R. Reibman, “SAVE: An Algorithm for Smoothed Adaptive Video Over Explicit Rate Networks”, IEEE/ACM Transaction on Networking 2000
〔24〕Luigi Rizzo, Member, IEEE, Lorenzo Vicisano, “Replacement Policies for a Proxy Cache”, IEEE/ACM Transaction on Networking 2000
〔25〕Paul Barford, Mark Crovella, “Critical Path Analysis of TCP Transaction”, In Proceedings of the 2000 ACM SIGCOMM Conference
〔26〕Mark Crovella , Paul Barford, “The Network Effects of Prefetching”, In Proceedings of the IEEE Infocomm ‘98
〔27〕Robert L. Carter, Mark E. Crovella, “Server Selection using Dynamic Path Characterization in Wide-Area Networks”, In Proceedings of the IEEE Infocomm ‘97
〔28〕Charu Aggarwal, Member, IEEE, Joel L. Wolf, Fellow, IEEE, Philip S. Yu, Fellow, IEEE, “Caching on the World Wide Web”, IEEE Transactions on Knowledge and Data Engineering Vol 11, NO. 1, January/February 1999
〔29〕Dan Foygel, Dennis Strelow, “Reducing Web Latency with Hierarchical Cache-based Prefetching”, IEEE/ACM Transaction on Networking 2000
〔30〕Annie P. Foong, Yu-Hen Hu, Dennis M. Heisey, “Web Caching: Locality of References Revisited”, IEEE/ACM Transaction on Networking 2000
〔31〕Annie P. Foong, Yu-Hen Hu, Dennis M. Heisey, “Adaptive Web Caching using Logistic Regression”, IEEE/ACM Transaction on Networking 1999
〔32〕Cho-Yu Chiang, Yingjie Li, Ming T. Liu Mervin E. Muller, “On Request Forwarding for Dynamic Web Caching Hierarchies”, IEEE/ACM Transaction on Networking 2000
〔33〕Wu-chang Feng, Dilip D. Kandlur, Debanjan Saha Kang G. Shin, “Understanding and Improving TCP Performance over Networks with Minimum Rate Guarantees”, IEEE/ACM Transaction on Networking 2000
〔34〕Guillaume Pierre, Ihor Kuz, Maarten van Steen, Andrew S. Tanenbaum, “Differentiated Stategies for Replicating Web Documents”, IEEE/ACM Transaction on Networking 2000
〔35〕Chen, Haoxun, Chengbin Chu, and Proth, J.-M., "An Improvement of the Lagrangean Relaxation Approach for Job Shop Scheduling: a Dynamic Programming Method", IEEE Transactions on Robotics and Automation, Vol. 14, No. 5, Oct. 1998.
〔36〕Fisher, M. L., "The Lagarangian Relaxation Method for Solving Integer Programming Problems", Management Science, vol. 27, no.1, January 1981.
〔37〕Geoffrion, A. M., "Lagrangean Relaxation and Its Use in Integer Programming", Math. Programming Study, vol. 2, 1974
〔38〕Guignard, M., "On Solving Structured Integer Programming Problems with Lagrangean Relaxation and/or Decomposition", Proceedings of the 28th IEEE Conference on Decision and Control, Vol. 2, 1989.
〔39〕Y. Rekhter, T. Li, “A Broder Gateway Protocol 4 (BGP-4)”, RFC1771, March, 1995