Please use this identifier to cite or link to this item:
Quality assurance of streaming data dissemination over p2p network
Chiu, Wei Chung
Lien, Yao Nan
Chiu, Wei Chung
|Issue Date: ||2013-09-04 17:04:52 (UTC+8)|
本研究嘗試找出一個較好的拓樸用以傳輸多媒體資料流，使得位於最遠端節點的累積延遲亦能為使用者接受，且資料品質的損害程度最小。我們將之建置成一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: || 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. |
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
|Source URI: ||http://thesis.lib.nccu.edu.tw/record/#G0095753039|
|Data Type: ||thesis|
|Appears in Collections:||[資訊科學系] 學位論文|
Files in This Item:
All items in 政大典藏 are protected by copyright, with all rights reserved.