支援變動播放速率及低暫存空間需求之熱門廣播法研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：97

、訪客IP：3.15.211.41

姓名

游象甫(Hsiang-Fu Yu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

支援變動播放速率及低暫存空間需求之熱門廣播法研究
(Hot-video Broadcasting Schemes with VBR Support and with Low Buffer Demands)

相關論文

★ 整合多樣配置組態下的藍芽射頻驗證系統	★ 具檔案敘述相關語查詢之智慧型檔案搜尋系統
★ 具遲到者支援功能之網際網路簡報系統	★ 以快速廣播法建構熱門視訊隨選服務伺服器
★ 具事件同步再現特性之遠程電傳展示伺服器	★ 無線網路環境下之廣播資訊快速下載
★ 中文網站繁簡互訪協助系統	★ 支援時光平移播放之調適性現場直播演算法
★ 用於互動式廣播之段落對齊法	★ 熱門影片廣播法之影片區段復原機制
★ 配合熱門影片廣播的本地伺服器高效快取法	★ 一個增進SIP在防火牆環境中應用的協同模組
★ 考量網頁熱門度之一致性雜湊法解決網頁代理伺服器之負載平衡	★ 以網域名稱伺服器為基礎之色情網站過濾系統
★ 使用熱門廣播法及支援點對點傳輸之影音內容傳遞網路	★ 變動頻寬平滑化之熱門廣播演算法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

有一個在網際網路上廣播熱門影片的方法是先將影片切割成小的區塊, 然後重覆在多個頻道播放. 由於這種方法可以讓使用者分享頻寬, 所以可以在不犠牲等待時間的情況下, 節省頻寬. 按區塊的播放方式, 這種廣播可分為兩種: 每個頻道傳送一個區塊及每個頻道傳送多個區塊. 本論文主要討論基於後者的廣播法, 其中兩個代表性的方法為 Recursive Frequency-Splitting broadcasting (RFS) 及 Fixed-Delay Pagoda Broadcasting (FDPB), 其均可提供非常小的等待時間. 我們提出區塊補償與非同步下載及播放策略讓 RFS 及 FDPB 可以用較平滑的頻寬傳送 VBR 影片. 區塊補償是動態播放影片後面的區塊使得所需頻寬較平穏. 而非同步下載及播放是要求使用者必須下載完區塊後才能播放, 如此讓影片播放才能連續. 利用這兩個策略, 我們發展 Smooth RFS (SRFS) 及 Smooth FDPB (SFDPB), 可以傳送 VBR 影片並降低所需頻寬峰值及變異量, 我們也以數學分析其邊界值. 此外本研究以一部影片測試其效能, 實驗結果顯示 SRFS 比 RFS 有較低的頻寬峰值及變異量, 唯一的代價是稍高的平均使用頻寬. 與 Smooth Fast Broadcasting (SFB) 相比, SRFS 也有較低的頻寬峰值及平均使用頻寬. 當給定頻寬時, SRFS 的阻塞率遠比 RFS 及 SFB 小. 對 SFDB, 我們也得到同樣的實驗結果.
除此之外, 本論文也探討另一個重要的問題-降低使用者暫存器需求. 我們提出一個策略要求使用者儘量延遲區塊的下載, 並證明此策略可讓使用者儲存最少的區塊. 本文進一步提出一個反向排列區塊的策略, 其以由大到小的方式排列頻道中的每個區塊. 利用這兩個策略, 我們設計 Reverse Fast Broadcasting (RFB) 廣播法, 最大只需暫存25%的影片. 與 Fast Broadcasting, New Pagoda Broadcasting 及 RFS 相比, RFB 節省客戶端暫存需求50%, 33% 及 33%. 我們擴充此法提出 RFB-n, 可提供伺服器端頻寬及客戶端暫存需求的調節. 在額外給三個頻道的情況下, RFB-3 只需暫存10%的影片. 我們進一步將這兩個策略用於其他廣播法, 如 Greedy Disk-conserving Broadcasting 及 Pyramid Broadcasting, 發現可以節省客戶端暫存需求30%至75%. 最後, 我們也討論所提出策略在節省客戶端暫存的限制.

摘要(英)

One way to broadcast a popular video is to partition the video into segments, which are broadcasted on several streams periodically. The approach lets multiple users share streams; thus, the stress on the scarce bandwidth can be alleviated without sacrificing viewers’ waiting time. The segment broadcasting can be categorized into two types: one segment per stream and multiple segments per stream. Two representative schemes based on multiple segments per stream are the recursive frequency-splitting (RFS) broadcasting and the fixed-delay pagoda broadcasting (FDPB), which both obtain very small waiting time in the literature. We propose the approaches of segment patching and asynchronous downloading-playing to enable the RFS and the FDPB schemes to broadcast VBR-encoded videos smoothly. Segment patching dynamically arranges the video segments numbered latter to smooth bandwidth requirements. Asynchronous downloading-playing ensures that a client can play a VBR video continuously. With the approaches, the enhanced schemes, named the smooth RFS (SRFS) and the smooth FDPB (SFDPB), reduce peak bandwidth consumption and variance during distributing VBR videos. In addition, we analyze the bounds on the peak and the variance. A simulation was conducted to evaluate both the schemes. The results indicate that the SRFS outperforms the RFS scheme remarkably on reducing the bandwidth peak and the variance. The overhead is slightly higher average bandwidth. In comparison with the smooth fast broadcasting (SFB), our scheme requires lower average bandwidth, and obtains smaller variance. Besides, given a fixed bandwidth smaller than the peak, the SRFS scheme achieves a far smaller blocking rate. The SFDPB scheme also obtains the similar results.
Besides, the work investigates another important issue – client-buffer saving. A proposed approach requires a client to delay downloading segments as late as possible. We further prove that a CBR broadcasting scheme with the approach lets its clients buffer the least segments. In addition, the paper presents a reverse segment arrangement, which arranges the segments in descending order of their numeric indexes on each stream. Using the downloading delay and the reverse arrangement, we improve the fast broadcasting (FB) scheme, and obtain the reverse FB (RFB), which requires a client to buffer only 25% of a playing video without sacrificing waiting time. In comparison with the FB, the new pagoda broadcasting, and the recursive frequency-splitting schemes, the RFB saves the client buffers by 50%, 33%, and 33%. Extending the scheme, we propose the RFB-n, which provides a tradeoff between client buffers and server bandwidths. Given three extra streams, the scheme requires a client to buffer only 10% of a playing video. Furthermore, we apply the approaches to other schemes, such as the greedy disk-conserving broadcasting and the pyramid broadcasting, and their buffer requirements can be reduced by 30% to 75%. The article also discusses the limit of the approaches to buffer saving finally.

關鍵字(中)

★ 客戶端暫存器
★ 動態播放速率
★ 熱門廣播法

關鍵字(英)

★ hot-video broadcasting
★ client buffers
★ VBR

論文目次

ABSTRACT II
ACKNOWLEDGEMENTS V
TABLE OF CONTENTS VI
LIST OF TERMS AND ABBREVIATIONS VIII
LIST OF FIGURES X
CHAPTER 1 INTRODUCTION 1
CHAPTER 2 REVIEW OF THE LITERATURE 5
2.1 SCHEMES BASED ON ONE SEGMENT PER STREAM 5
2.2 SCHEMES BASED ON MULTIPLE SEGMENTS PER STREAM 10
CHAPTER 3 SMOOTH BROADCASTING SCHEMES FOR VBR VIDEOS 13
3.1 SMOOTH RECURSIVE FREQUENCY-SPLITTING (SRFS) SCHEME 13
3.1.1 Recursive Frequency-Splitting (RFS) Scheme 13
3.1.2 The Smooth RFS 14
3.1.3 Workable Verification 19
3.1.4 Bound Analysis 20
3.1.5 Simulation Results 23
3.2 SMOOTH FIXED-DELAY PAGODA BROADCASTING (SFDPB) 29
3.2.1 Fixed-Delay Pagoda Broadcasting (FDPB) 29
3.2.2 The Smooth FDPB 31
3.2.3 Workable Verification 34
3.2.4 Simulation Results 35
CHAPTER 4 BROADCASTING SCHEMES WITH LOW BUFFER DEMANDS 46
4.1 DATA DOWNLOADING DELAY ON THE CLIENT SIDE 46
4.2 REVERSE FAST BROADCASTING SCHEME 50
RFB-n 52
Workable Verification 54
4.3 ANALYSIS AND COMPARISON 55
4.3.1 Viewers’ Waiting Time 55
4.3.2 Buffer Requirements 55
4.4 DISCUSSION 83
CHAPTER 5 CONCLUSIONS 86
REFERENCES 88
VITA 94

參考文獻

[1] A. Bar-Noy, and E. Ladner, “Windows Scheduling Problems for Broadcast Systems,” SIAM Journal on Computing, vol. 32, no. 4, pp. 1091-1113, 2003.
[2] Y. Cai, A. Hua and S. Sheu, “Leverage client bandwidth to improve service latency of distributed multimedia applications,” Journal of Applied Systems Studies, 2(3), 2001.
[3] S. Chand and H. Om, “Modified staircase data broadcasting scheme for popular videos,” IEEE Transactions on Broadcasting, vol. 48, no. 4, pp. 274-280, Dec. 2002.
[4] K. Chandra, and C. K. Wong, “Worst-case analysis of a placement algorithm related to storage allocation,” SIAM Journal on Computing, vol. 4, no. 3, pp. 249-263, 1975.
[5] T. Chiueh and C. Lu, “A periodic broadcasting approach to video-on-demand service,” SPIE, vol. 26, pp 162-169, October 1995.
[6] R. A. Cody, and E. G. Coffman Jr., “Record allocation for minimizing expected retrieval costs on drum-like storage devices,” Journal of the ACM, vol. 23, pp. 103-115, 1976.
[7] A. Dan, D. Sitaram, P. Shahabuddin, “Dynamic batching policies for an on-demand video server,” Multimedia Systems, vol. 4, no. 3, pp. 112–121, June 1996.
[8] L. Gao, J. Kurose, and D. Towsley, “Efficient schemes for broadcasting popular videos,” Multimedia Systems, vol. 8, pp. 284-294, 2002.
[9] R. L. Graham, “Bounds on multiprocessing timing anomalies,” SIAM Journal on Applied Mathematics, vol. 17, pp. 416-429, 1969.
[10] A. Hu, “Video-on-Demand Broadcasting Protocols: A Comprehensive Study,” IEEE INFOCOM, pp. 508-517, 2001.
[11] A. Hu, I. Nikolaidis, P. van Beek, “On the design of efficient video-on-demand broadcast schedules,” in Proceedings of 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 262-269, Oct. 1999.
[12] K.A. Hua and S. Sheu, “Skyscraper broadcasting: A new broadcasting scheme for metropolitan video-on-demand systems,” ACM SIGCOMM, Sept. 1997.
[13] 黃立勳, 曾黎明, 游象甫, “具錯誤回復特性之熱門影片廣播法,” in Proceedings of TANet 2002 Conference, Taiwan, October 2002.
[14] I. Nikolaidis, F. Li, and A. Hu, “An Inherently Loss-Less and Bandwidth-Efficient Periodic Broadcast Scheme for VBR Video,” SIGMETRICS 2000, pp. 116-117, 2000.
[15] L.-S. Juhn and L.-M. Tseng, “Staircase data broadcasting and receiving scheme for hot video service,” IEEE Transactions on Consumer Electronics, vol. 43, no. 4, pp. 1110-1117, November 1997.
[16] L.-S. Juhn and L.-M. Tseng, “Harmonic broadcasting for video-on-demand service,” IEEE Transactions on Broadcasting, vol. 43, no. 3, pp. 268-271, September 1997.
[17] L.-S. Juhn and L.-M. Tseng, “Fast data broadcasting and receiving scheme for popular video services,” IEEE Transactions on Broadcasting, vol. 44, no. 1, pp. 100-105, March 1998.
[18] L.-S. Juhn, and L.-M. Tseng, “Enhanced harmonic data broadcasting and receiving scheme for popular video service,” IEEE Transactions on Consumer Electronics, vol. 44, no. 2, pp. 343-346, May 1998.
[19] L.-S. Juhn, and L.-M. Tseng, “Adaptive fast data broadcasting scheme for video-on-demand services,” IEEE Transactions on Broadcasting, vol. 44, no. 2, pp. 182-185, June 1998.
[20] R. M. Karp, “Reducibility among combinatorial problems,” Complexity of Computer Computations, R.E. Miller and J. W. Thatcher, eds., Plenum Press, New York, pp. 85-103, 1972.
[21] T. L. Kunii et al., “Issues in storage and retrieval of multimedia data,” Multimedia Systems, vol. 3, no. 5, pp. 298–304, 1995.
[22] Y.-T. Leung, and W.-D. Wei, “Tighter bounds on a heuristic for a partition problem,” Information Processing Letters, vol. 56, pp. 51-57, 1995.
[23] A. Mahanti, L. Eager, K. Vernon and D. Sundaram-Stukel, “Scalable On-Demand Media Streaming with Packet Loss Recovery,” IEEE Transactions on Networking, vol. 11, no. 2, pp. 195-209, April 2003.
[24] F. Li, and I. Nikolaidis, “Trace-adaptive fragmentation for periodic broadcasting of VBR video,” in Proceedings of 9th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV’99), June 1999.
[25] J. Liu, S.-C. Yang, H.-F. Yu, and L.-M. Tseng, “Content Delivery Network with Hot-video broadcasting and Peer-to-peer Approach,” to appear in Journal of Information Science and Engineering, vol. 20, no. 6, 2004.
[26] B. Ozden, R. Rastogi, and A. Silberschatz, “On the design of a low cost video-on-demand storage system,” Multimedia Systems, vol. 4, no. 1, pp. 40–54, 1996.
[27] J.-F. Paris, S. W. Carter and D. D. E. Long, “A Low Bandwidth Broadcasting Protocol for Video on Demand,” in Proceedings of the 7th International Conference on Computer Communications and Networks (IC3N'98), Lafayette, LA, pp. 690-697, October 1998.
[28] J.-F. Paris, S. W. Carter, and D.D. E. Long, “Efficient broadcasting protocols for video on demand,” in Proceedings of the 6th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, Montreal, Canada, pp. 127-132, July 1998.
[29] J.-F. Paris, “A simple low-bandwidth broadcasting protocol for video-on-demand,” in Proceedings of International Conference on Computer Communications and Networks, pp. 118–123, 1999.
[30] J.-F. Paris, S. W. Carter and D. D. E. Long, “A Hybrid Broadcasting Protocol for Video on Demand,” in Proceedings of the 1999 Multimedia Computing and Networking Conference (MMCN'99), San Jose, CA, pp. 317-326, January 1999.
[31] J. F. Paris, “A broadcasting protocol for compressed video,” in Proceedings of Euromedia’99 Conference, Munich, Germany, pp 78-84, Apr 1999.
[32] J. F. Paris, “A Fixed-Delay Broadcasting Protocol for Video-on-Demand,” in Proceedings of the 10th International Conference on Computer Communications and Networks (ICCCN '01), Scottsdale, AZ, pp. 418-423, October 15-17, 2001.
[33] D. Saparilla, K. Ross, and M. Reisslein, “Periodic broadcasting with VBR-encoded video,” IEEE INFOCOM 1999, pp 464-471, 1999.
[34] K. Thirumalai, J.-F. Paris and D. D. E. Long, “Tabbycat: an Inexpensive Scalable Server for Video-on-Demand,” in Proceedings of the IEEE 2003 International Conference on Communications (ICC 2003), Anchorage, AK, pp. 896-900, May 2003.
[35] Y.-C. Tseng, M.-H. Yang, C.-M. Hsieh, W.-H. Liao, and J.-P. Sheu, “Data broadcasting and seamless channel transition for highly demanded videos,” IEEE Transactions on Communications, vol. 49, no. 5, pp. 863-874, May 2001.
[36] Y.-C. Tseng, M.-H. Yang, and C.-H. Chang, “A recursive frequency-splitting scheme for broadcasting hot videos in VOD service,” IEEE Transactions on Communications, vol. 50, no. 8, pp. 1348-1355, August 2002.
[37] S. Viswanathan and T. Imielinski, “Pyramid Broadcasting for video on demand service,” in Proceedings of IEEE Multimedia Computing and Networking Conference, vol. 2417, pp. 66-77, San Jose, California, 1995.
[38] H.-C. Yang, H.-F. Yu, and L.-M. Tseng, “Adaptive Live Broadcasting for Highly-Demanded Videos,” Journal of Information Science and Engineering, vol. 19, no3, May 2003.
[39] 楊宏昌, 游象甫, 張庭彰, 曾黎明, 陳奕明, “用於互動式廣播之段落對齊法”, TANet2003, 2003.
[40] H.-C. Yang, H.-F. Yu, L.-M. Tseng, and Y.-M. Chen, “Interleaving Harmonic Broadcasting and Receiving Scheme with Loss-Anticipation Delivery,” The 9th IEEE Symposium on Computers and Communications (ISCC2004), Alexandria, Egypt, June 2004.
[41] H.-C. Yang, H.-F. Yu, L.-M. Tseng, and Y.-M. Chen, “Interleaving Staircase Broadcasting and Receiving Scheme With Loss-Anticipation Delivery,” The 2004 International Conference on Internet Computing (IC'04), Las Vegas, Nevada, USA, June 2004.
[42] H.-C. Yang, H.-F. Yu, L.-M. Tseng, and Y.-M. Chen, “A Segment-alignment Interactive Broadcasting Scheme,” The 6th International Conference on Advanced Communication Technology (IEEE/ICACT2004), Phoenix Park, Korea, Feb. 2004.
[43] Z.-Y. Yang, L.-S. Juhn, and L.-M. Tseng, “On Optimal Broadcasting Scheme for Popular Video Service,” IEEE Transactions on Broadcasting, vol. 45, no. 3, pp. 318-322, September 1999.
[44] Z.-Y. Yang, “The Telepresentation System over Internet with Latecomers Support,” Ph.D. Dissertation, Department of Computer Science and Information Engineering, National Central University, Taiwan, 2000.
[45] 楊政遠, 陳奕明, 曾黎明, 游象甫, 翁志達, “Data Stream Broadcasting with Live Program Support”, in Proceedings of TANet 2001 Conference, Taiwan, October 2001.
[46] H.-F. Yu, H.-C. Yang, Y.-M. Chen, L.-M. Tseng, Chen-Yi Kuo, “Simple VBR Harmonic Broadcasting (SVHB),” National Computer Symposium (NCS2003), Taiwan, December 2003.
[47] H.-F. Yu, Y.-M. Chen, L.-M. Tseng, and C.-T. Wu, “Hot-video Broadcasting Schemes with Cache,” The 3rd International Conference on Networking (ICN’04), France, Feb. 2004.
[48] H.-F. Yu, H.-C. Yang, Y.-M. Chen, L.-M. Tseng, and C.-Y. Kuo, “Smooth Fast Broadcasting (SFB) for Compressed Videos,” The 2nd International Conference on Wired/Wireless Internet Communications (WWIC’04), German, Lecture Notes in Computer Science, 2957, pp. 272-283, Jan. 2004.
[49] H.-F. Yu, H.-C. Yang, L.-M. Tseng, and Y.-M. Chen, “Simple VBR Staircase Broadcasting (SVSB),” IEEE Consumer Communications and Networking Conference (CCNC2004), USA, Jan. 2004.
[50] H.-F. Yu, H.-C. Yang, Y.-M. Chen, and L.-M. Tseng, “A Smooth Recursive Frequency-Splitting Scheme for Broadcasting VBR-encoded Hot Videos,” The 7th IEEE International Conference on High Speed Networks and Multimedia Communications (HSNMC’04), France, to appear in Lecture Notes in Computer Science, June 2004.

指導教授

曾黎明(Li-Ming Tseng)

審核日期

2004-7-5

推文