臺灣博碩士論文加值系統

網路頻寬是珍貴的資源，使用者的需求總是超出既有的頻寬，網路擁塞因此而不斷地在現今的網路上發生。網路擁塞會造成網路封包的遺失，因此，如何確保資料流能夠在網路上完整地傳送資訊，這對於傳輸通訊協定的設計來說，是一項困難的挑戰。雖然重傳的方法能夠準確有效率地重新傳遞遺失的封包，卻需要花費許多週期才能完成。而錯誤更正的方法，預先送出多個多餘的封包，來避免網路發生擁塞時封包的遺失，但卻也可能因此浪費許多珍貴的頻寬。本篇論文提出了一個構想，透過數學機率的分析，找出在各種網路擁塞狀況下，最合適的錯誤更正碼比例，因此而能夠改善網路的傳輸效率。我們並利用此構想設計了一個以效率為導向的錯誤更正碼通訊協定，模擬的實驗其數據也驗正了，在相同的網路擁塞狀態下，此通訊協定的效率能趨近重傳方法的高效率，並以較少的週期來完成資訊的傳遞。此一通訊協定在效率與時間內取得了一個最佳的平衡。此外，我們也設計了一套多媒體串流系統的原型，能在網際網路上有效率地傳遞多媒體資訊。我們將在其後討論相關的設計細節與如何應用高效率的錯誤更正碼調適機制於此原型之中。

Occasional network congestions on the modern networks induce irksome packets dropping. This effect seriously challenges the protocol designs to preserve the integrity of information flows. While ARQ-variants precisely specify the exact data for retransmission, FEC-based schemes rectify the packet loss beforehand. They suffer either elongated correction time or excessive bandwidth consumption for delivery of supportive packets. This thesis presents an idea from analytical evidences to improve the amount of data applicable to the receiver for every unit of data sent from the sender. Consequently, the derived transport protocol can achieve the superior efficiency close to ARQ-variants and offer punctual data correction capability like FEC-based approaches. The performance results from experimental investigations concretely substantiate this favorable feature. We also present our prototype of media streaming system to demonstrate efficient delivery of multimedia content over the Internet. The incorporation of the adaptive erasure codes into the prototype and the corresponding design considerations are discussed in the end.

CONTENTS iv
LIST OF FIGURES vi
LIST OF TABLES vii
Chapter 1 Introduction 1
Chapter 2 Analysis of Delivery Efficiency 4
2.1 The number of lost packets 4
2.2 The Decodable Probability of (n, k) Erasure Code 5
2.3 The Efficiency of (n, k) Erasure Coded Blocks 7
2.4 The Effect of Network Status and Block Size 9
2.5 rn,p* Estimation 13
2.5.1 r* Table 13
2.5.2 Approximating to r* 13
Chapter 3 Transport Protocol 16
3.1 Sender Side 16
3.1.1 Bursts 16
3.1.2 Feedback 17
3.2 Receiver Side 19
3.3 Flow Control 20
Chapter 4 Performence Study 21
4.1 Simulation Environment 21
4.2 Measurement 22
4.3 Constant Sending-rate, without Retransmission. 23
4.4 Constant Sending-rate, with Retransmission. 25
4.5 Flow Controlled Sending-rate 27
Chapter 5 Prototyping On-Demand Media Streaming Systems 32
5.1 Introduction 32
5.2 Framework and System Components 34
5.2.1 Sender 34
5.2.2 Receiver 36
5.2.3 Central Controller 38
5.3 Features 39
Chapter 6 Concluding Remark and Future Works 45
Bibliography 47

[1] A. Albanese, J. Bloemser, J. Edmonds, M. Luby, and M. Sudan, “Priority Encoding Transmission,” In Proc. of the 35th Annual IEEE Symposium on Foundations of Computer Science Conf., pages 604-612, November 1994.
[2] J. Bolot, S. Fosse-Parisis, and D. Towsley, “Adaptive FEC-Based Error Control for Interactive Audio in the Internet,” In Proc. of the IEEE INFOCOM Conf., pages 1453-1460, New York, U.S.A, March 1999.
[3] A.J. McAuley, “Reliable Broadband Communication Using a Burst Erasure Correcting Code,” In Proc. of the ACM SIGCOMM’90 Conf., pages 297-306, Philadelphia, PA, September 1990.
[4] Rizzo, L., and Vicisano, L., “Effective Erasure Codes for Reliable Computer Communication Protocols,” In the ACM SIGCOMM Computer Communication Review, 27(2): 24-36, April 1997.
[5] R.E. Blahut, “Theory and Practice of Error Control Codes,” Addison Wesley, MA, 1984.
[6] J. Hagenauer, “Rate Compatible Punctured Convolutional Codes (RCPC Codes) and their Applications," IEEE Trans. on Communications, 36:389-400, April 1988.
[7] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes," In Proc. of the International Communications Conference, pages 1064-1070, Geneva, Switzerland, May 1993.
[8] John W. Byers, Michael Luby, Michael Mitzenmacher, and Ashutosh Rege, “A Digital Fountain Approach to Reliable Distribution of Bulk Data,” In Proc. of the ACM SIGCOMM Conf., pages 56—67, Vancouver, Canada, September 1998.
[9] Rizzo. L, “On the Feasibility of Software FEC,” DEIT Technical Report, http://www.iet.unipi.it/~luigi/softfec.ps, January 1997
[10] K. Park and W. Wang, “QoS-Sensitive Transport of Real-time MPEG Video Using Adaptive Forward Error Correction,” In Proc. of the IEEE Multimedia Systems Conf., pages 426-432, Florence, Italy, June 1999.
[11] B. Lamparter, Otto Bohrer, W. Effelsberg, and V. Turau. “Adaptable Forward Error Correction for Multimedia Data streams,” 1993. Preprint.
[12] Daji Qiao and Kang G. Shin, “A Two-Step Adaptive Error Recovery Scheme for Video Transmission over Wireless Networks,” In Proc. of the INFOCOMM Conf., pages1698-1704, Tel-Aviv, Israel, March 2000.
[13] K. Park and W. Wang, “AFEC: An Adaptive Forward Error Correction Protocol for End-to-End Transport of Real-Time Traffic," In Proc. of the IEEE IC3N Conf., pages. 196-205, Los Alamitos, CA, October 1998.
[14] Sunghyun Choi and Kang G. Shin, “Cost Effective Adaptive Error Control Using a Hybrid of FEC and ARQ in Wireless Networks,” University of Michigan CSE-TR-402-99, 1999.
[15] Sheldon Ross, “A First Course in Probability,” Prentice-Hall Inc, 1998.
[16] Lettieri, P., Srivastava, M.B.: "Adaptive Frame Length Control for Improving Wireless Link Throughput, Range, and Energy Efficiency", In Proc. of the IEEE INFOCOM Conf., pages 307-314, San Francisco, USA, March 1998.
[17] Kien A. Hua and Simon Sheu, “Skyscraper Broadcasting: A New Broadcasting Scheme for Metropolitan Video-on-Demand Systems,” In Proc. of the ACM SIGCOMM Conf., pages 89-100, Cannes, France, September 1997.
[18] A. Hu, “Video-on-Demand Broadcasting Protocols: A Comprehensive Study,” In Proc. of the IEEE INFOCOM Conf., pages 508-517, Anchorage, Alaska, April 2001.
[19] A. Mahanti, D. L. Eager, M. K. Vernon, and D. Sundaram-Stukel, “Scalable On-Demand Media Streaming with Packet Loss Recovery,” In Proc. of the ACM SIGCOMM Conf., pages 97-108, San Diego, CA, August 2001.
[20] J. Padhye and S. Floyd, “On Inferring TCP Behavior,” In Proc. of the ACM SIGCOMM Conf., pages 287-298, San Diago, CA, August 2001.
[21] I. Rhee, “Error Control Techniques for Interactive Low-bit Rate Video Transmission over the Internet,” In Proc. of the ACM SIGCOMM Conf., pages 290-301, Vancouver, Canada, September 1998.
[22] “The Network Simulator — ns-2,” URL: http://www.isi.edu/nsnam/ns/.
[23] S. Sheu, K.A. Hua and Y. Cai, “A Novel Broadcast Technique for Theaters in the air,” In Proc. of the WVUME Conf., pages 218-225, Chicago, IL, July 2000.
[24] Simon Sheu, Sang-Fong Chien, Jeng-Ming Wu, and Kou-Jeng Huang, “Prototyping On-Demand Media Streaming Systems,” In Proc. of International Conference on Advanced Communication Technology 2002, Seoul, Korea, February 2002.
[25] J.-F. Pâris, S. W. Carter, and D. D. E. Long, “Efficient Broadcasting Protocols for Video on Demand,” In Proc. of the MASCOTS Conf., pages 127-132, Montreal, Canada, July 1998.
[26] L. Wu, R. Sharma, and B. Smith, “Thin Streams: An Architecture for Multicating Layered Video,” In the 7th International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV 97), St. Louis, USA, May 1997.
[27] Michael F. Speer and Steven McCanne, “RTP Usage with Layered Multimedia Streams”, Internet Engineering Task Force, Audio-Video Transport Working Group, March. 1996.
[28] Simon Sheu, Sang-Fong Chien, and Jeng-Ming Wu, ”An Efficacy-Oriented Transmission Control Protocol,” submitted to IEEE Globecom 2002 for publication.
[29] A. Veres, Zs. Kenesi, S. Moln ar, and G. Vattay, “On the Propagation of Long-Range Dependence in the Internet,” In Proc. of the ACM SIGCOMM Conf., Stockholm, Sweden, August-September 2000.
[30] L. Vicisano, L. Rizzo, and J. Crowcroft, "TCP-Like Congestion Control for Layered Multicast Data Transfer," In Proc. of the INFOCOM Conf., pages 996-1003, San Francisco, USA, March 1998.
[31] Sally Floyd, Mark Handley, Jitendra Padhye, and Joerg Widmer, “Equation-Based Congestion Control for Unicast Applications," In Proc. of the ACM SIGCOMM Conf., pages 43-56, Stockholm, Sweden, August-September 2000.
[32] Thekkath, C. A., Nguyen, T. D., Moy, E., and Lazowska, E. D. “Implementing Network Protocols at User Level,” In Proc. of the ACM SIGCOMM Conf., pages 554-565, San Francisco, CA, September 1993.
[33] R. J. La and V. Anantharam, "Window-Based Congestion Control with Heterogeneous Users," In Proc. of the IEEE INFOCOM Conf., pages 1320-1329, Anchorage, AL, April 2001.
[34] S. Ben Fredj, T. Bonald, A. Proutiere, G. Regnie, and J.W. Roberts, “Statistical Bandwidth Sharing: A Study of Congestion at Flow Level,” In Proc. of the SIGOMM Conf., San Diego, CA, August 2001.
[35] J. Zhou and J. Li, “Scalable Audio Streaming over the Internet with Networkaware Rate-Distortion Optimization,” In Proc. of the Int'l Conf. Image Processing, Thessaloniki, Greece, October 2001.
[36] Paul P. White and Jon Crowcroft, "Optimized Batch Patching with Classes of Service," In the ACM Communications Review, vol. 30, no. 4, October 2000.
[37] Jehan-Francois Pâris, Darrell D. E. Long, and Patrick E. Mantey, “Zero-Delay Broadcasting Protocols for Video-on-Demand,” In Proc. of the ACM Multimedia Conf., pages 189-197, Orlando, FL, October 1999.
[38] Jehan-Francois Pâris, “An Interactive Broadcasting Protocol for Video-on-Demand,” In Proc. of the IEEE International Performance, Computing, and Communication Conf., pages 347-353, Phoenix, AZ, April 2001.
[39] Sue-Zhe Weng, Simon Sheu, and Jun-Yi Lee, “A Cost-Effective Interactive Broadcasting Protocol for Media Streaming,” In Proc. of the National Computer Symposium Conf., pages 115-122, Taipei, Taiwan, December 2001.
[40] Simon Sheu, Sue-Zhe Weng, San-Fong Chien, and Jeng-Ming Wu, “A Novel Streaming Protocol for Scalable Interactive Services,” In Proc. of the ICACT Conf., Seoul, Korea, February 2002.
[41] J.-F. Pâris, Steven W. Carter, and Darrell D. E. Long, “A Low Bandwidth Broadcasting Protocol for Video on Demand,” In Proc. of the Computer Communications and Networks Conf., pages 690-697, Lafayette, LA, October 1998.
[42] S. Viswanathan and T. Imielinski, “Pyramid Broadcasting for Video-on-Demand Service,” In Proc. of the SPIE Multimedia Computing and Networking Conf., pages 66-77, San Jose, CA, February 1995.
[43] L. Juhn and L. Tseng, “Fast Data Broadcasting and Receiving Scheme for Popular Video Service,” IEEE Trans. on Broadcasting, 44(1):100--105, March 1998.
[44] Jehan-Francois Pâris, Steven W. Carter, and Darrell D. E. Long, “A Hybrid Broadcasting Protocol for Video on Demand,” In Proc. of the SPIE Multimedia Computing and Networking Conf., pages 317-326, San Jose, CA, January 1999.
[45] Ming-Syan Chen and Dilip D. Kandlur, “Stream Conversion to Support Interactive Video Playout,” IEEE Multimedia Magazine, 3(2):51--58, June 1996.
[46] 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, 11(3):415--425, March 2001.