Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/60233
|
| Title: | 在點對點網路上針對串流資料傳播的品質保證
Quality assurance of streaming data dissemination over p2p network |
| Authors: | 邱威中
Chiu, Wei Chung |
| Contributors: | 連耀南
Lien, Yao Nan
邱威中
Chiu, Wei Chung |
| Keywords: | 點對點
串流
演算法
生成樹
P2P
Streaming
algorithm
spanning tree |
| Date: | 2009 |
| Issue Date: | 2013-09-04 17:04:52 (UTC+8) |
| Abstract: | 網路技術發展的日新月異帶領了眾多新網路服務的崛起，例如即時影音串流這類的多媒體服務。但即時影音串流服務所產生的龐大資料流和傳輸延遲時間的嚴格限制也隨之而來的為網路環境帶來許多挑戰，在這些條件下，傳統Server-client拓樸架構將client要求的影音資料以單一鏈結傳輸時，常會因為頻寬不足而面臨嚴重的封包遺失，或是資料流擁擠造成的額外傳輸延遲使得封包無法達到即時性的需求。P2P網路擁有server-client架構所難以達到的規模伸縮性，且對於節點、鏈結失效所引起的傳輸錯誤也較能容忍，更重要的是，它有效的分散了原本負載在少數link上的龐大資料流。因此P2P架構近年來風行於即時影音串流服務。
目前P2P網路的拓樸多是隨意形成，當網路成員規模龐大時，由傳送端出發到遠方的接收端，途中可能經過無數的鏈結，每一個鏈結都會由於頻寬的不足使得資料流遭受某種程度的品質損害，另一方面，對即時影音服務而言，若資料流的累積延遲時間超出可容忍範圍時，無法為使用者接受。
本研究嘗試找出一個較好的拓樸用以傳輸多媒體資料流，使得位於最遠端節點的累積延遲亦能為使用者接受，且資料品質的損害程度最小。我們將之建置成一NP-Complete複雜度的問題模型，名為MLDST。而解法則是修改Dijkstra single-source shortest-path演算法，並加上每個節點承擔下游節點數量及延遲時間限制而來。我們以PlanetLab環境在實際的網路上進行實驗，證實我們的演算法比傳統的Minimum-Spanning Tree及shortest path spanning tree有更好的影像品質。
Numerous new network services arise with the advanced development of network technologies, such as real-time multimedia streaming services. But challenges to network environment come along with the enormous traffic of data flows and rigorous restriction to transmission delay of real-time multimedia streaming services. Under this circumstance, conventional server-client topology suffers from serious packet loss and packet delay due to the overload of servers and their accessing links. Also, extra transmission delay may make packets fail to meet the requirement of real-timed services. Peer-to-peer network is more scalable than server-client model, and is much more tolerable to the transmission errors caused by node or link failures. More importantly, it effectively distributes load from the server to peers. As a consequence, peer-to-peer service architecture becomes very popular for real-time multimedia streaming services recently.
Peer-to-peer networks are mostly formed in random fashion. As the size of network grows, packets may have to travel through numerous links to reach far-end receivers. The quality of data may be damaged by insufficient bandwidth of links. For real-time multimedia services, it is not acceptable to users if the cumulated packet delay exceeds a tolerable limit.
Our research is trying to find a better topology to transmit multimedia data flows which makes the cumulated delay of the most-far-end user be tolerable and the damage of data quality is minimized. The problem is modeled as a MLDST problem, which is a NP-Complete problem. To solve the problem, we modified Dijkstra’s single-source shortest-path algorithm by bounding the node degree and adding delay constraint. The experiments were carried out on real network environment through PlanetLab. Experiments show that our algorithm outperforms traditional MST and shortest path spanning tree. |
| Reference: | [1] Marc Bui, Franck Butelle, and Christian Lavault, "A Distributed Algorithm for Constructing a Minimum Diameter Spanning Tree", Journal of Parallel and Distributed Computing, Vol. 64, No. 5, May, 2004, pp. 571-577.
[2] Miguel Castro, Peter Druschel, Anne-Marie Kermarrec, Animesh Nandi, Antony Rowstron, Atul Singh, "SplitStream: High-Bandwidth Multicast in Cooperative Environments", Proceedings of the 19th ACM Symposium on Operating Systems Principles, 2003, pp. 298-313.
[3] M. R. GAREY and D. S. JOHNSON, W. H. Freeman, "Computers and intractability: A guide to the theory of NP-completeness", W. H. Freeman and Company, 1979.
[4] Yu-Hsuang Guo, John K. Zao, Wen-Hsiao Peng, Lin-Shung Huang, Fang-Po Kuo, Che-Min Lin, "Trickle: Resilient Real-Time Video Multicasting for Dynamic Peers with Limited or Asymmetric Network Connectivity", Proceedings of 8th IEEE International Symposium on Multimedia, December, 2006.
[5] Jan-Ming Ho, D.T. Lee, Chia-Hsiang Chang, and C.K. Wong, "Bounded-Diameter Minimum Diameter Spanning Trees and Related Problems", Proceedings of the 5th Annual Symposium on Computational Geometry, 1989, pp. 276-282.
[6] Jan-Ming Ho, D. T. Lee, Chia-Hsiang Chang and C. K. Wong, "Minimum Diameter Spanning Trees and Related Problems", SIAM Journal of Computing, Vol. 20, No. 5, 1991, pp. 987-997.
[7] Xiao-Jun Hei, Yong Liu, Keith W. Ross, "IPTV over P2P streaming networks: The mesh-pull approach", IEEE Communications Magazine, Vol. 46, No. 2, February 2008, pp. 86-92.
[8] Hung-Chang Hsiao and Chih-Peng He, "A Tree-Based Peer-to-Peer Network with Quality Guarantees", IEEE Transactions on Parallel and Distributed Systems, Vol. 19, No. 8, August 2008, pp. 1099-1110.
[9] X. Jia, "A Distributed Algorithm of Delay Bounded Multicast Routing for Multimedia Applications in Wide Area Networks", Proceedings of 6th International Conference on Computer Communications and Networks, September, 1997, pp. 208-213.
[10] K. Kalapriya, R. Venkatesh Babu, S. K. Nandy, "Streaming Stored Playback Video Over A Peer-to-Peer Network", Proceedings of IEEE International Conference on Communications, Paris, Vol. 3, June 2004, pp. 1298-1302.
[11] Bo Li, Hao Yin, "Peer-to-Peer Live Video Streaming on the Internet: Issues, Existing Approaches, and Challenges", IEEE Communications Magazine, Vol. 45, No. 6, June, 2007, pp. 94-99.
[12] Jiang-Chuan Liu, Sanjay G. Rao, Bo Li and Hui Zhang, "Opportunities and Challenges of Peer-to-Peer Internet Video Broadcast", Proceedings of the IEEE, Vol. 96, No. 1, January, 2008, pp. 11-24.
[13] Vinay Pai, Kapil Kumar, Tamilmani, Vinay Sambamurthy, Alexander E. Mohr, "Chainsaw: Eliminating Trees from Overlay Multicast", Proceedings of 4th International Workshop on Peer-to-Peer Systems, February, 2005.
[14] Mohit Singh, Lap Chi Lau, "Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal", Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June, 2007, pp.661-670.
[15] Duc A. Tran, Kien A. Hua, Tai Do, "ZIGZAG: An efficient peer-to-peer scheme for media streaming", Proceedings of 22nd IEEE INFOCOM Conference, Vol. 2, 2003, pp. 1283-1292.
[16] DEB Veeravalli, JB Weissman, "A Robust Spanning Tree Topology for Data Collection and Dissemination in Distributed Environments", IEEE Transactions on Parallel and Distributed Systems, Vol. 18, No. 5, May, 2007, pp. 608-620.
[17] Vidhyashankar Venkataraman, Kaouru Yoshida, Paul Francis, "Chunkyspread: Heterogeneous Unstructured Tree-Based Peer-to-Peer Multicast", Proceedings of the 14th IEEE International Conference on Network Protocols, 2006, pp. 2-11.
[18] Aggelos Vlavianos, Marios Iliofotous and Michalis Faloutsos, "BiTos: Enhancing BitTorrent for Supporting Streaming Applications", Proceedings of 25th IEEE International Conference on Computer Communications, 2006, pp. 1-6. |
| Description: | 碩士
國立政治大學
資訊科學學系
95753039
98 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0095753039 |
| Data Type: | thesis |
| Appears in Collections: | [資訊科學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| 303901.pdf | 834Kb | Adobe PDF2 | 395 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
