Change search
ReferencesLink to record
Permanent link

Direct link
Distributed Optimization of P2P Media Delivery Overlays
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.
2011 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Media streaming over the Internet is becoming increasingly popular. Currently, most media is delivered using global content-delivery networks, providing a scalable and robust client-server model. However, content delivery infrastructures are expensive. One approach to reduce the cost of media delivery is to use peer-to-peer (P2P) overlay networks, where nodes share responsibility for delivering the media to one another. The main challenges in P2P media streaming using overlay networks include: (i) nodes should receive the stream with respect to certain timing constraints, (ii) the overlay should adapt to the changes in the network, e.g., varying bandwidth capacity and join/failure of nodes, (iii) nodes should be intentivized to contribute and share their resources, and (iv) nodes should be able to establish connectivity to the other nodes behind NATs. In this work, we meet these requirements by presenting P2P solutions for live media streaming, as well as proposing a distributed NAT traversal solution. First of all, we introduce a distributed market model to construct an approximately minimal height multiple-tree streaming overlay for content delivery, in gradienTv. In this system, we assume all the nodes are cooperative and execute the protocol. However, in reality, there may exist some opportunistic nodes,  free-riders, that take advantage of the system, without contributing to content distribution. To overcome this problem, we extend our market model in Sepidar to be effective in deterring free-riders. However, gradienTv and Sepidar are tree-based solutions, which are fragile in high churn and failure scenarios. We present a solution to this problem in GLive that provides a more robust overlay by replacing the tree structure with a mesh. We show in simulation, that the mesh-based overlay outperforms the multiple-tree overlay. Moreover, we compare the performance of all our systems with the state-of-the-art NewCoolstreaming, and observe that they provide better playback continuity and lower playback latency than that of NewCoolstreaming under a variety of experimental scenarios. Although our distributed market model can be run against a random sample of nodes, we improve its convergence time by executing it against a sample of nodes taken from the Gradient overlay. The Gradient overlay organizes nodes in a topology using a local utility value at each node, such that nodes are ordered in descending utility values away from a core of the highest utility nodes. The evaluations show that the streaming overlays converge faster when our market model works on top of the Gradient overlay. We use a gossip-based peer sampling service in our streaming systems to provide each node with a small list of live nodes. However, in the Internet, where a high percentage of nodes are behind NATs, existing gossiping protocols break down. To solve this problem, we present Gozar , a NAT-friendly gossip-based peer sampling service that: (i) provides uniform random samples in the presence of NATs, and (ii) enables direct connectivity to sampled nodes using a fully distributed NAT traversal service. We compare Gozar with the state-of-the-art NAT-friendly gossip-based peer sampling service, Nylon, and show that only Gozar supports one-hop NAT traversal, and its overhead is roughly half of Nylon’s.

  

 

 

 

 

 

 

 

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology , 2011. , x, 31 p.
Series
Trita-ICT-ECS AVH, ISSN 1653-6363 ; 2011:04
Keyword [en]
P2P overlay networks, P2P live streaming, Distributed optimization
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering Information Science
Identifiers
URN: urn:nbn:se:kth:diva-33287ISBN: 978-91-7415-970-7OAI: oai:DiVA.org:kth-33287DiVA: diva2:414141
Presentation
2011-06-03, Sal D, KTH-Forum, Isafjordsgatan 39, Kista, 14:17 (English)
Opponent
Supervisors
Note
QC 20110517Available from: 2011-05-17 Created: 2011-05-02 Last updated: 2011-05-18Bibliographically approved
List of papers
1. gradienTv: Market-Based P2P Live Media Streaming on the Gradient Overlay
Open this publication in new window or tab >>gradienTv: Market-Based P2P Live Media Streaming on the Gradient Overlay
2010 (English)In: 10th IFIP International Conference on Distributed Applications and Interoperable Systems (DAIS´10), LNCS, 2010, Vol. 6115, 212-225 p.Conference paper (Refereed)
Abstract [en]

This paper presents gradienTv, a distributed, market-based approach to live streaming. In gradienTv, multiple streaming trees are constructed using a market-based approach, such that nodes with increasing upload bandwidth are located closer to the media source at the roots of the trees. Market-based approaches, however, exhibit slow convergence properties on random overlay networks, so to facilitate the timely discovery of neighbours with similar upload bandwidth capacities (thus, enabling faster convergence of streaming trees), we use the gossip-generated Gradient overlay network. In the Gradient overlay, nodes are ordered by a gradient of node upload capacities and the media source is the highest point in the gradient. We compare gradienTv with state-of-the-art New-Coolstreaming in simulation, and the results show significantly improved bandwidth utilization, playback latency, playback continuity, and reduction in the average number of hops from the media source to nodes.

Series
, Lecture Notes in Computer Science, ISSN 0302-9743
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering Information Science
Identifiers
urn:nbn:se:kth:diva-33775 (URN)000279567500016 ()2-s2.0-77953776951 (ScopusID)
Funder
Swedish e‐Science Research Center
Note
QC 20110517Available from: 2011-05-17 Created: 2011-05-17 Last updated: 2012-05-22Bibliographically approved
2. Sepidar: Incentivized market-based P2P live-streaming on the Gradient overlay network
Open this publication in new window or tab >>Sepidar: Incentivized market-based P2P live-streaming on the Gradient overlay network
2010 (English)In: Proceedings - 2010 IEEE International Symposium on Multimedia, ISM 2010, Taichung, 2010, 1-8 p.Conference paper (Refereed)
Abstract [en]

Live streaming of video content using overlay networks has gained widespread adoption on the Internet. This paper presents Sepidar, a distributed market-based model, that builds and maintains overlay network trees, which are approximately minimal height, for delivering live media as a number of substreams. A streaming tree is constructed for each substream such that nodes that contribute higher amounts of upload bandwidth are located increasingly closer to the media source at the root of the tree. While our distributed market model can be run against a random sample of nodes, we improve its convergence time to stabilize a tree by executing against a sample of nodes that contribute similar amounts of upload bandwidth. We use the Gradient overlay network to generate samples of such nodes. We address the problem of free-riding through parent nodes auditing the behaviour of their child nodes. We evaluate Sepidar by comparing it in simulation with state-of-the-art NewCoolstreaming. Our results show significantly improved playback latency and playback continuity under churn, flash-crowd, and catastrophic failure experiment scenarios. We also show that using the Gradient improves convergence time of our distributed market model compared to a random overlay network. Finally, we show that Sepidar punishes the performance of free-riders, and that nodes are incentivized to contribute more upload bandwidth by relatively improved performance. © 2010 IEEE.

Place, publisher, year, edition, pages
Taichung: , 2010
Keyword
Distributed market model, Gradient overlay, Live streaming, P2P overlay, Catastrophic failures, Child node, Convergence time, Free-riders, Free-riding, Live media, Market model, P2P overlays, Parent node, Random sample, Sub-streams, Video contents, Bandwidth, Commerce, Overlay networks, Peer to peer networks, Video streaming, Media streaming
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering Information Science
Identifiers
urn:nbn:se:kth:diva-33776 (URN)10.1109/ISM.2010.11 (DOI)2-s2.0-79951742010 (ScopusID)9780769542171 (ISBN)
Note
QC 20110517Available from: 2011-05-17 Created: 2011-05-17 Last updated: 2011-05-17Bibliographically approved
3. GLive: the Gradient overlay as a market maker for mesh-based P2P live streaming
Open this publication in new window or tab >>GLive: the Gradient overlay as a market maker for mesh-based P2P live streaming
2011 (English)In: Proceedings - 2011 10th International Symposium on Parallel and Distributed Computing, ISPDC 2011, 2011, 153-162 p.Conference paper (Other academic)
Abstract [en]

Peer-to-Peer (P2P) live video streaming over the Internet is becoming increasingly popular, but it is still plagued by problems of high playback latency and intermittent playback streams. This paper presents GLive, a distributed market-based solution that builds a mesh overlay for P2P live streaming. The mesh overlay is constructed such that (i) nodes with increasing upload bandwidth are located closer to the media source, and (ii) nodes with similar upload bandwidth become neighbours. We introduce a market-based approach that matches nodes willing and able to share the stream with one another. However, market-based approaches converge slowly on random overlay networks, and we improve the rate of convergence by adapting our market-based algorithm to exploit the clustering of nodes with similar upload bandwidths in our mesh overlay. We address the problem of free-riding through nodes preferentially uploading more of the stream to the best up loaders. We compare GLive with our previous tree-based streaming protocol, Sepidar, and New Cools treaming in simulation, and our results show significantly improved playback continuity and playback latency.

Keyword
Free-riding; Live streaming; Live video streaming; Market-based approach; Market-maker; Peer to peer; Rate of convergence; STreaming protocols; Tree-based
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering Information Science
Identifiers
urn:nbn:se:kth:diva-33778 (URN)2-s2.0-84863328458 (ScopusID)978-076954540-0 (ISBN)
Conference
2011 10th International Symposium on Parallel and Distributed Computing, ISPDC 2011; Cluj Napoca, Cluj; Romania; 6-8 July 2011
Funder
ICT - The Next Generation
Note

QC 20140901

Available from: 2011-05-17 Created: 2011-05-17 Last updated: 2014-10-02Bibliographically approved
4. Gozar: NAT-friendly peer sampling with one-hop distributed NAT traversal
Open this publication in new window or tab >>Gozar: NAT-friendly peer sampling with one-hop distributed NAT traversal
2011 (English)Conference paper (Other academic)
Abstract [en]

Gossip-based peer sampling protocols have been widely used as a building block for many large-scale distributed applications. However, Network Address Translation gateways (NATs) cause most existing gossiping protocols to break down, as nodes cannot establish direct connections to nodes behind NATs (private nodes). In addition, most of the existing NAT traversal algorithms for establishing connectivity to private nodes rely on third party servers running at a well-known, public IP addresses. In this paper, we present Gozar, a gossip-based peer sampling service that: (i) provides uniform random samples in the presence of NATs, and (ii) enables direct connectivity to sampled nodes using a fully distributed NAT traversal service, where connection messages require only a single hop to connect to private nodes. We show in simulation that Gozar preserves the randomness properties of a gossip-based peer sampling service. We show the robustness of Gozar when a large fraction of nodes reside behind NATs and also in catastrophic failure scenarios. For example, if 80% of nodes are behind NATs, and 80% of the nodes fail, more than 92% of the remaining nodes stay connected. In addition, we compare Gozar with existing NAT-friendly gossip-based peer sampling services, Nylon and ARRG. We show that Gozar is the only system that supports one-hop NAT traversal, and its overhead is roughly half of Nylon's.

Series
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 03029743 ; 6723
Keyword
Break down, Building blockes, Catastrophic failures, Gossiping protocols, IP addresss, Large-scale distributed applications, NAT traversal, Network address translation gateways, Random sample, Randomness property, Sampling protocol, Single hop, Third parties
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering Information Science
Identifiers
urn:nbn:se:kth:diva-33780 (URN)10.1007/978-3-642-21387-8_1 (DOI)000306288500001 ()2-s2.0-79959993895 (ScopusID)978-364221386-1 (ISBN)
Conference
11th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems, DAIS 2011; Reykjavik; Iceland; 6-9 June 2011
Funder
ICT - The Next Generation
Note

QS 20140915

Available from: 2011-05-17 Created: 2011-05-17 Last updated: 2014-09-15Bibliographically approved

Open Access in DiVA

fulltext(295 kB)424 downloads
File information
File name FULLTEXT02.pdfFile size 295 kBChecksum SHA-512
9272ffa4f760669b2bdf5b42aee59b489b2946bfbf7a4e2e73667a7b004169878c4fc56eb14e2054180ce40ef1cc7a6056e9f6e704af11f2dbfca9a1d25f8c25
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Payberah, Amir H.
By organisation
Software and Computer Systems, SCS
Other Electrical Engineering, Electronic Engineering, Information EngineeringInformation Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 424 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 308 hits
ReferencesLink to record
Permanent link

Direct link