政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/60233

政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/60233

English | 正體中文 | 简体中文 | Post-Print筆數 : 27 | Items with full text/Total items : 109952/140887 (78%)
Visitors : 46285064 Online Users : 830

RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.

Scope

please add "double quotation mark" for query phrases to get precise results

please goto advance search for comprehansive author search

Adv. Search

Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer

Goto mobile version

政大典藏 > College of Informatics > Department of Computer Science > Theses > Item 140.119/60233

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:	[Department of Computer Science ] Theses

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.

社群 sharing

著作權政策宣告 Copyright Announcement

1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.

DSpace Software Copyright © 2002-2004 MIT & Hewlett-Packard / Enhanced by NTU Library IR team Copyright © - Feedback