臺灣博碩士論文加值系統

由於多點傳播技術可以有效地降低串流影音應用的伺服器負載與網路頻寬的需求，因此成為主要研究方向之一。目前的多點傳播服務可以允許接收者在相同的時間讀取相同的多點傳播資料，然而，在隨選的視訊服務中，使用者點播影片的時間通常不一樣這樣，上述「相同時間」的讀取限制就降低了多點傳播的好處。為了解決這個問題，我們提出了一種新型態的多點傳播服務，稱之為「隨選多點傳播」（on-demand multicast communications）。在這種新的多點傳播服務裡，即使接收者在不同的時間點播相同的節目，他們仍然可以共享一個隨選多點傳播的頻寬。為了將資料準時的送達各個接收者，我們利用 sliding interval cache 方法在路由器上增加了一個時間控制機制去控制封包交換出去的時間。在這個機制中，封包將暫時儲存在路由器的緩衝記憶體，然後再依照特定的時間將封包送到不同的出口。因此，透過協調封包在每一個路由器停留的時間，我們可以將影音串流在不同的時間送到不同的接收者。然而，這樣的擴充使得多點傳播的路徑選擇變得更為複雜，因為不僅僅要考慮路徑的問題，我們也必須要考慮緩衝記憶體大小與位置以產生足夠的串流時間差。在這篇論文中，我們正式定義隨選多點傳播的問題並且證明這樣的問題在一般的網路結構下是 NP-compete 的問題。因此，我們將針對以下的網路結構提出不同的路徑選擇演算法：1) 完全的網路結構，在此結構下，我們並不需要考慮路徑與緩衝記憶體的位置，只需要考慮緩衝區的大小就已經足夠。2) 樹狀的網路結構，在此結構下，我們必須另外考慮緩衝區的位置，然而，由於每一個使用者到串流伺服器只有唯一的路徑，因此我們並不需要考慮路徑的問題。3) 一般的網路結構，在這種架構下，所有的條件包括緩衝區的大小、位置與路徑都必須要考慮進來。經由我們的實驗數據顯示，我們所提出的方法比目前以多點傳播為基礎的協定有更好的效能。路由器內只需要少許的緩衝區，數萬個使用者將可以同時分享同一個隨選多點傳播的頻寬。除此之外，本篇論文也將討論VCR的控制，容錯處理和流量等控制，以建構一個穩定的系統。最後，我提出在網際網路上實做應用層的隨選多點傳播系統所會面對的挑戰與解決的方案。
關鍵字：

Multicast communications is one of the major researches to reduce the required server load and network bandwidth in streaming video applications. However, current multicast services only allow receivers to share the multicast stream at the same time. This access time limitation diminishes the benefit of multicast communications since users usually access the video at distinct times in ‘on-demand’ streaming services. To address this problem, this dissertation proposes a new type of multicast services, called on-demand multicast communications, to allow receivers to access the multicast stream at distinct times. To deliver multicast data to receivers on time, we add a timing control on intermediate nodes (router or proxy) to control the packet forwarding time via the sliding interval caching. In this control, incoming packets are temporarily stored in node buffer and then forwarded to different output interfaces at different times. Therefore, carefully coordinating the packet delay on each intermediate node, a source stream can be delivered to receivers at the specified delay times. However, this extension makes the multicast routing problem more difficult; not only a routing path should be determined but also the buffers should be allocated to generate appropriate buffering delay. In this dissertation, we formally define the on-demand multicast routing problem and prove this problem in general graphs is NP-complete. For this reason, we study the on-demand multicast routing algorithms in three topologies: 1) complete graphs, in which no path routing and buffer positioning are considered. Only the buffer size should be determined when routing a request. 2) trees, in which the position of allocated buffers should be further considered but the path is still not a routing issue because there is only one path from a receiver to the source. 3) general graphs, in which all criteria including path routing, buffer allocation and buffer positions must be considered. In our simulations, the presented on-demand multicast communications has an outstanding performance than current multicast based protocols. With a little buffer allocated on routing nodes, only a few server streams are required to simultaneously serve ten thousands of clients. In addition, this dissertation also presents the mechanisms to handle VCR functions, fault conditions and flow controls to build a robust system. Finally, we present the challenges and the solutions when implementing the application-layer on-demand multicast communications on the non-QOS supported Internet.

中文摘要 iii
Abstract v
List of Figures vii
Chapter 1. Introduction 1
Chapter 2. Multicast Related Works 8
2.1. Batching 8
2.2. Periodic Broadcasting 9
2.3. Patching / Stream Tapping 11
2.4. Chaining 12
Chapter 3. On-demand Multicast Communications 14
3.1. The Timing Control Mechanism 14
3.2. On-Demand Multicast Routing 16
3.3. Problem Complexity of On-demand Multicast Routing 20
Chapter 4. Optimal Routing Algorithms on Complete Graphs 23
4.1. Off-line Optimal Routing Algorithm 24
4.2. On-line Optimal Routing Algorithm 27
4.3. The Application on Peer-to-Peer Based Streaming Systems 31
4.4. Performance Comparison with Chaining Based Schemes 35
4.5. Performance Comparison with Patching and Periodic Broadcasting Schemes 43
Chapter 5. Heuristic Algorithms on Tree-based Network Topology 46
5.1. Single Node Algorithm 46
5.2. Heuristic Algorithm I 49
5.3. Heuristic Algorithm II 51
5.4. Performance Studies 53
Chapter 6. Heuristic Algorithm on General Graphs and its Applications 56
6.1. A Heuristic Algorithm on General Network Topologies 57
6.2. Control Protocol for Heuristic Algorithm 60
6.3. Performance Studies 62
Chapter 7. Protocols and Prototype Implementation 66
7.1. Basic Control Protocols and VCR support 66
7.2. The Streaming Platform 68
7.2.1. System Architecture 68
7.2.2. Basic System Flows 71
7.2.3. Selection Strategies of Video Sources 73
7.2.4. Piece-wise Control and Fault Handling 75
7.2.5. Stripping Control 78
Chapter 8. Conclusions and Future Works 80
References 83

[1] Te-Chou Su; Jia-Shung Wang, “On-demand multicast routing scheme and its algorithms,” in 13th International and 10th Symposium on Parallel and Distributed Processing, pp. 212-217, 1999.
[2] Microsoft Corporation, http://www.microsoft.com
[3] RealNetworks Inc., http://www.realnetworks.com
[4] Kevin C. Almeroth, Mostafa H. Ammar, “The use of multicast delivery to provide a scalable and interactive video-on-demand service.” IEEE J. Select. Areas Commun., vol. 14, no. 6, pp. 1110-1122, Aug. 1996.
[5] K. Ravindran, T. J. Gong, “Cost analysis of multicast transport architectures in multiservice networks”, IEEE/ACM transactions on networking, vol. 6, no. 1, pp. 94 -109, Feb. 1998.
[6] C. C. Aggarwal, J. L. Wolf, and P. S. Yu, “On optimal batching policies for video-on-demand storage servers,” in Proc of IEEE Int’l Conf. On Multimedia Systems, June 1996.
[7] A. Dan, D. Sitaram, and P. Shahabuddin, “Dynamic batching policies for an on-demand video server,” Multimedia Systems, vol. 4, No. 3, pp. 112-121, Jun 1996.
[8] S. Sheu, K. A. Hua, and T.H. Hu, “Virtual batching: a new scheduling technique for video-on-demand servers,” in Proc. of the 5th DASFAA, April 1997.
[9] Poon, W.-F.; Lo, K.-T.; Feng, J., “Adaptive batching scheme for multicast video-on-demand systems,” IEEE Transactions on Broadcasting, vol. 47 no. 1, pp. 66 -70, March 2001.
[10] Nelson Luis Saldanha da Fonseca, “The look-ahead-maximize-batch batching policy,” IEEE Transaction on Multimedia, vol. 4(1), pp. 114-120, 2002.
[11] S. Viswanathan and T. Imielinski, "Metropolitan area video-on-demand service using pyramid broadcasting," Multimedia Systems, vol. 4(4), pp. 197-208, August 1996.
[12] C. C. Aggarwal, J. L. Wolf, and P. S. Yu, “A permutation-based pyramid broadcasting scheme for video-on-demand systems,” in Proc. of IEEE Int.Conf. Multimedia Computing and Systems, pp. 118—126, June 1996.
[13] Hon-Shing Ma; To, T.-P.J.; Lun, D.P.K, "Enhanced mirrored-pyramid broadcasting for video-on-demand delivery," in Proc. of IEEE Asia-Pacific Conference on Circuits and Systems, pp. 875-878, 2000.
[14] K. A. Hua and S. Sheu, “Skyscraper broadcasting: A new broadcasting scheme for metropolitan video-on-demand systems,” in Proc. of ACMSIG-COMM, Sept. 1997.
[15] D. L. Eager and M. K. Vernon, “Dynamic skyscraper broadcasts for video-on-demand,” in Proc. of 4th Int. Workshop Multimedia Information Systems (MIS’98), Sept. 1998.
[16] L.-S. Juhn and L.-M. Tseng, “Harmonic broadcasting for video-on-demand service,” IEEE Transactions on Broadcasting, vol. 43, pp. 268—271, Sept. 1997.
[17] Li-Shen Juhn; Li-Ming Tseng, "Enhanced harmonic data broadcasting and receiving scheme for popular video service," IEEE Transactions on Consumer Electronics, vol. 44(2), pp. 343-346, May 1998.
[18] Li-Shen Juhn; Li-Ming Tseng, “Fast broadcasting for hot video access,” in Proc. of International Workshop on Real-Time Computing Systems and Applications, pp. 237-243, 1997.
[19] Li-Shen Juhn; Li-Ming Tseng, "Fast data broadcasting and receiving scheme for popular video service," IEEE Transactions on Broadcasting, vol. 44(1), pp. 100-105, March 1998.
[20] Zeng-Yuan Yang; Li-Shen Juhn; Li-Ming Tseng, "On optimal broadcasting scheme for popular video service," IEEE Transactions on Broadcasting, vol. 45(3), pp. 318-322, Sept. 1999.
[21] L. Gao, J. Kurose, and D. Towsley, “Efficient Schemes for Broadcasting Popular Videos,” in Proc. of Int’l. Workshop on Network and Operating System Support for Digital Audio and Video, July 1998.
[22] Yu-Chee Tseng; Ming-Hour Yang; Chi-Ming Hsieh; Wen-Hwa Liao; Jang-Ping Sheu, “Data broadcasting and seamless channel transition for highly demanded videos,” IEEE Transactions on Communications, vol. 49(5), pp. 863-874, May 2001.
[23] J. F. Paris, S. W. Carter, D. D. E. Long, “Efficient broadcasting protocols for video on demand,” in Proc. of 6th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 127-132, 1998.
[24] J. F. Paris, S. W. Carter, D. D. E. Long, “A low bandwidth broadcasting protocol for video on demand,” in Proc. of IEEE International Conference on Computer Communications and Networks, 1998.
[25] Ailan Hu, “Video-on-demand broadcasting protocols: A comprehensive study”, in Proc. of IEEE INFOCOM, 2001.
[26] Steven Carter, Darell Long, "Improving Video-on-Demand Server Efficiency through Stream Tapping," in Proc. of International Conference on Computer Communication and Networks, pp. 200-207, 1997.
[27] Steven Carter, Darell Long, “Improving bandwidth efficiency of video-in-demand servers,” Computer Networks 31, pp, 99-111, 1999.
[28] K. A. Hua, Y. Cai, and S. Sheu, “Patching: A multicast technique for true video-on-demand,” in Proc. of ACM Multimedia, pp. 191-200, September 1998.
[29] Y. Cai, K. A. Hua, and K. Vu, “Optimizing patching performance,” in Proc. IS&TSPIE Conf. Multimedia Computing and Networking 1999.
[30] S. Sen, L. Gao, J. Rexford, and D. Towsley, “Optimal patching scheme for efficient multimedia streaming,” in Proc. NOSSDAV, June 1999.
[31] Lixin Gao; Towsley, D. "Supplying instantaneous video-on-demand services using controlled multicast," in Proc. IEEE International Conference on Multimedia Computing and Systems, vol, 2 , 1999, pp. 117 -121 vol.2.
[32] Kien A. Hua, Simon Sheu, James Z. Wang, “Earthworm: A Network Memory Management Technique for Large-Scale Distributed Multimedia Applications,” in Proc. of IEEE INFOCOM '97. vol. 3, pp. 990-997, 1997.
[33] Simon Sheu, Kien A. Hua, W. Tavanapong, “Chaining: a generalized batching technique for video-on-demand systems.“, in Proc. of IEEE International Conference on Multimedia Computing and Systems, pp.110 —117, 1997.
[34] Jen-Kai Chen and Jean-Lien C. Wu, “Adaptive Chaining Scheme for Distributed VOD Applications”, IEEE Transactions on Broadcasting, vol. 45, no. 2, June 1999.
[35] L. Golubchik, J. Lui, and R. Muntz, “Adaptive piggybacking: a novel technique for data sharing in video on-demand storage servers,” ACM Multimedia Systems Journal, 4(3): 140-155, 1996.
[36] C. Aggarwal, J. Wolf, and P. S. Yu, "On optimal piggybacking merging policies for video-on-demand systems," Performance Evaluation Review, vol. 24, pp. 200-209, May 1996.
[37] Fonseca, N.L.S.; Facanha, R.A., “Integrating batching and piggybacking in video servers,” in Proc. of IEEE GLOBECOM '00. vol. 3, pp. 1334 —1338, 2000.
[38] A. Dan and D. Sitaram, "Buffer management policy for an on-demand video server," IBM Research Report RC 19347, 1993.
[39] A. Dan and D. Sitaram, “A generalized interval caching policy for mixed interactive and long video environments,” In IS&T SPIE Multimedia Computing and Networking Conference, San Jose, CA, January 1996.
[40] Eager, D.; Vernon, M.; Zahorjan, J., "Minimizing bandwidth requirements for on-demand data delivery", IEEE Transactions on Knowledge and Data Engineering, Vol. 13, No.5, pp. 742 —757, 2001.
[41] Wanjiun Liao, Victor O.K. Li, “The split and merge (SAM) protocol for interactive video-on-demand systems.” IEEE Multimedia, vol. 4, no. 4, pp. 51-62, Oct. 1997.
[42] Fred Bauer, Anujan Varma, “Distributed algorithms for multicast path setup in data networks.” IEEE J. Select. Areas Commun., vol. 4, no. 2, pp. 181-191, April 1996.
[43] Anees Shaikh, Kang Shin, “Destination-driven for low-cost multicast.” IEEE J. select. Areas Commun., vol. 15, no. 3, pp. 373-381, April 1997.
[44] Jean-Paul Nussbaumer, Baiju V. Patel, Frank Schaffa, P.G. Sterbenz, “Networking requirements for interactive video on demand.” IEEE J. Select. Areas Commun., vol. 13, no. 5, pp. 779-787, June 1995.
[45] L.A. Rowe, D.A. Berger, J.E. Baldeschwieler, “The Berkeley distributed video-on-demand system.”, in Proc. of Sixth NEC Research Symposion on Multimedia Computing.
[46] D.L.Tennenhouse, J.M.Smith, W.D.Sincoskie, D.J.Wetherall, G.J.Minden, “A survey of active network research.”, IEEE Communications Magazine. Vol. 35, no. 1, pp. 80-86, Jan. 1997.
[47] M. Calderon, M. Sedano, A. Azcorra, C. Alonsa, “Active network support for multicast applications.”, IEEE Network. vol. 12, no. 3, pp. 46-52, May 1998.
[48] A. Banchs, W. Effelsberg, C. Tschudin, V. Turau, “Multicasting multimedia streams with active Networks.”, in Proc. of 23rd Annual Conference on Local Computer Networks, pp. 150-159, 1998.
[49] Y.S. Chen, “Mathematical modeling of empirical laws in computer application: A case study.” Comput. Math. Applicat. pp. 77-87, Oct. 1992.
[50] Michael R. Garey, David S. Johnson, “Computers and Interactivity, A Guide to Theory of NP-completeness”, W.H. Freeman and Co., San Francisco, California 1979.
[51] E. L. Eager, M. K. Vernon, J. Zahorjan, “Minimizing bandwidth requirements for on-demand data delivery,” in Proc. of International Workshop on Advances in Multimedia Information Systems, pp.80-87, 1999.
[52] E. L. Eager, M. K. Vernon, J. Zahorjan, “Optimal and efficient merging schedules for video-on-demand servers,” in Proc. of ACM International Multimedia Conference, 99,199-203, 1999.
[53] Amootz Bar-Noy, J. Goshi, R. E. Ladner, K. Tam, “Comparison of streaming merging algorithms for media-on-demand,” to appear in Multimedia Computing and Networking, 2002.
[54] S. Ramesh, I. Rhee, K. Guo, "Multicast with cache (Mcache): An Adaptive zero-delay video-on-demand service," TEEE Trans. on Circuit and Systems for Video Technology, Vol. 11(3), 2001.
[55] S.-H. Gary Chan, Fouad Tobagi, "Distributed servers architecture for networked video services," IEEE/ACM Trans. on Networking, Vol. 9(2), 2001.
[56] L. Gao, Don Towsley, "Threshold-Based Multicast for Continuous Media Delivery," IEEE Trans. on Multimedia, Vol. 3(4), 2001.
[57] Napster, http://www.napster.com
[58] KaZaA, http://www.kazaa.com
[59] eDonkey, http://www.edonkey2000.com
[60] Morpheus, http://www.musiccity.com
[61] The Institute for Information Industry, http://www.iii.org.tw
[62] The NTHU streaming platform, http://vod.cs.nthu.edu.tw
[63] MySQL, http://www.mysql.com
[64] PHP, http://www.php.net