臺灣博碩士論文加值系統

隨著網路的蓬勃發展，越來越多的使用者喜歡在網路上觀看多媒體影音檔案，基於使用者的需求不同與付費不同，因此影音串流伺服器必須對不同類型的使用者提供不同等級的品質服務(Quality of Service)，而不再是對所有使用者都是提供相同的服務品質，最近熱門的即時轉碼(Real-time Transcoding)技術更是有益於伺服器提供差異化服務(Differentiated Services)，當在使用者連線數目多的時候，伺服器可以選擇降低服務的品質來取代直接拒絕使用者的連線。
雖說串流伺服器提供差異化服務可以讓不同類型使用者獲得不同的品質服務，但伺服器服務的人數有限，且大部分頻寬分配的機制都是以總頻寬為考量，我們無法預測網路上使用者的何時會要求影音串流服務，而這會造成早來的使用者都能獲得頻寬服務，而晚來的使用者卻沒頻寬可以使用，為了避免這種情況，通常伺服器會採取流量限制的策略，在固定時間內只會分配固定的頻寬給在這段時間內來的使用者使用，以確保使用者無論在何時要求服務都會有固定的頻寬可以使用，但是在此頻寬確保供應的架構下會有一個問題存在，並非每一個使用者都會觀賞完影音才離開，有可能因為人為或外在因素(ex. 使用者喜好、斷線)，而提早離開串流服務，這些因使用者離開釋放出來的頻寬，勢必會降低系統的總頻寬使用效率，所以本論文提出一個強化型協調比例的頻寬分配策略來有效利用這些釋放出來的頻寬，將釋放出頻寬β部份用來提升使用者的連線品質，以增加串流伺服器的總頻寬使用率，(1-β)部分用來降低使用者的延遲時間，讓原本在此單位時間無法獲得服務的使用者能因此而獲得服務，且 0≦β≦1，並在模擬中，去探討分析究竟 於多少時，會在提升串流伺服器的總頻寬使用率和使用者平均等待時間上取得一個平衡點，最後並驗證本論文所提出的方法無論在使用者離開網路機率很大或很小，甚至在不同的使用者排程上皆都適用。模擬的結果顯示本論文所提出的方法能讓串流伺服器具有高利用度的總頻寬使用率和降低使用者的平均等待時間。

More and more people like watching the multimedia file in the network. With clients’ different demand or different service charge, streaming servers must provide different levels of quality of service (QoS) to different clients rather than providing the same service quality to all. Real-time trans-coding technology is useful in providing such differentiated service that streaming servers can choose to degrade the quality of service instead of rejecting the client’s requests when there are a burst of requests.
Although with the differentiated service in the streaming server, it is possible that the client who requests the service early can get services but the client who requests the service late does not because most bandwidth allocation strategies generally allocate the bandwidth to clients without any reservation. Additionally, it is impossible to predict when the client will access the service to avoid such problem, and thus the server usually limits the bandwidth to use in each time interval, e.g., the server allocates the fixed bandwidth in fixed time for clients who request the service during this period to guarantee them to have the service at any time. But there is still one problem for this method, i.e., not everyone uses services completely. Someone may finish the service early due to some factors, e.g., user preference or losing connection with the server. This can release the bandwidth and decrease the total bandwidth utilization of the streaming server. This paper proposes an enhanced harmonic proportional bandwidth allocation strategy to reuse the released bandwidth. Our strategy uses one part of all released bandwidth (i.e.,β) to raise quality of service of clients to increase total bandwidth utilization and uses the other part of all released bandwidth (i.e., 1-β) to reduce the delay time of clients by serving more clients who are not allowed to be served originally where β is between 0 and 1, inclusively. In the simulation, we try to discuss what the value of is better when simultaneously considering the two factors including the total bandwidth utilization and the delay time of clients, respectively. Furthermore, our proposed strategy is validated through the simulation that the high utilization and lower latency properties for streaming servers can be obtained no matter whether the probability of clients that leave services is high or low even in different request scheduling policies.

中文摘要 I
Abstract III
誌 謝 V
圖案列表 IX
Chapter 1 序論 1
1.1 簡介 1
1.2 論文組織架構 3
Chapter 2 研究背景 4
2.1 串流技術 4
2.2 頻寬分配機制 6
2.3 研究動機 7
2.4 系統模組 9
Chapter 3 所提出改進頻寬效能與降低等待時間的方法 11
3.1系統頻寬分配的機制 11
3.2系統頻寬分配的方法 15
3.2.1協調比例的頻寬分配策略Harmonic Proportional Bandwidth Allocation Strategy 15
3.2.2 轉碼技術的應用 17
3.3頻寬使用率與等待時間改進方法 18
3.3.1 計算釋放頻寬 19
3.3.2 釋放頻寬( )利用的方法 25
Chapter 4 模擬分析 27
4.1 模擬的環境 27
4.2 模擬結果與分析 28
4.2.1 最低串流位元速率( )皆相同 28
4.2.2 最低串流位元速率根據不同類別而不同 35
4.2.3 使用者離開網路機率不同 44
4.2.4 考慮優先權(priority)的情況 49
4.2.5 考慮不同影片長度的情況 53
4.2.6不同需求與Beta值的關係 55
Chapter 5 結論與未來工作 58
參 考 文 獻 60
附 錄 63

[1] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, “An Architecture for Differentiated Services, ” IETF RFC 2475,1998.
[2] S.C.M. Lee, J.C.S. Lui, and D.K.Y. Yau, “Admission Control and Dynamic Adaptation for a Proportional-Delay DiffServ-Enabled Web Server,” Proc. ACM SIGMETRICS Conf., pp. 172-182, 2002.
[3] X. Chen and P. Mohapatra, “Performance Evaluation of Service Differentiating Internet Servers, ” IEEE Trans. Computers, vol. 51, no.11, pp. 1368-1375, Nov. 2002.
[4] H. Zhu, H. Tang, and T. Yang, “Demand-Driven Service Differentiation for Cluster-Based Network Servers,” Proc. IEEE INFOCOM Conf., pp.679-688, 2001.
[5] Xiaobo Zhou, and Cheng-Zhong Xu, “Analysis of a Bandwidth Allocation Strategy for Proportional Streaming Services, ” Proceedings of the IEEE International Conference on E-Commerce Technology, pp. 373-376, July 2004.
[6] Xiaobo Zhou, and Cheng-Zhong Xu, “Harmonic Proportional Bandwidth Allocation and Scheduling for Service Differentiation on Streaming Servers, ” IEEE Trans. Parallel and Distributed Systems, vol.15, no.9, pp. 835-848, Sep. 2004.
[7] P.J. Shenoy, P Goyal, S.Rao, and H.M. Vin, “Symphony: An Integrated Multimedia File System,” Proc.ACM/SPIE Multimedia Computing and Networking Conf., pp.124-138, 1998.
[8] J. Gafsi and E.W. Biersack, “Modeling and Performance Comparison of Reliability Strategies for Distributed Video Servers,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 4, pp. 412-430, Apr. 2000.
[9] Dapeng Wu, Hou, Y.T., Wenwu Zhu, Ya-Qin Zhang, and Peha, J.M, “Streaming Video over the Internet: Approaches and Directions,” IEEE Trans. Circuits and Systems for Video Technology, vol. 11, pp. 282 - 300, Mar. 2001.
[10] C.C. Aggarwal, J.L Wolf, and P.S. Yu, “The Maximum Factor Queue Length Batching Scheme for Video-on-Demand Systems,” IEEE Trans. Computers, vol. 50, no. 2, pp. 97-110, Feb. 2001.
[11] D.Eager, M.Verson, and J.Zahorjan, “Minimizing Bandwidth Requirements for On-Demand Data Delivery,” IEEE Trans. Knowledge and Data Eng., vol. 13, no. 5, pp. 742-757, 2001.
[12] S.V. Anastasiadis, K.C. Sevcik, and M.Stumm, “Server-Based Smoothing of Variable Bit-Rate Streams,” Proc. ACM Multimedia Conf., pp. 147-158, 2001.
[13] W.-C. Feng and J.Rexford, “Performance Evaluation of Smoothing Algorithms for Transmitting Prerecorded Variable-Bit-Rate Video,” IEEE Trans. Multimedia, vol. 1, no. 3, pp. 302-312, 1999.
[14] J. Youn, M.T. Sun, and C.W. Lin, ”Motion Vector Refinement for High-Performance Transcoding , ” IEEE Trans. Multimedia, vol. 1, no. 1, pp. 30-40, 1999.
[15] X. Zhou, J. Wei, and C.-Z. Xu, “Processing Rate Allocation for Proportional Slowdown Differentiation on Internet Servers, ” Proc. IEEE 18th Int’l Parallel and Distributed Processing Symp (IPDPS)., Apr. 2004.
[16] V. Stanisic and M. Devetsikiotis, “An Analysis of Bandwidth Allocation Strategies in Multiservice Networks,” IEEE Trans. ICC, vol. 3, pp.1529 – 1533, May 2005.
[17] T. Ibarkai and N. Katoh, Resource Allocation Problem –Algorithmic Approaches. MIT Press,1988.
[18] W. Leinberger, G. Karypis, and V. Kumar, “Job Scheduling on the Presence of Multiple Resource Requirements,” Proc. SuperComputing Conf., 1999.
[19] http://www.digitalcontent.org.tw