Project Topics
Get Complete Project Material File(s) Now! »
BitTorrent and BASS : BitTorrent Assisted Streaming System
BitTorrent [18][19][20] splits a file into many pieces and pushes the different pieces to different clients, allowing them to trade pieces amongst each other. It uses a tracker program running on a server (as opposed to a gossip protocol) to disseminate lists of peers. To govern how pieces of the file are requested and swapped amongst peers, it follows rarest-piece-first and tit-for-tat policies, respectively. In rarest-piece-first, the client requests a part based on the number of copies it sees available and chooses the least common one. In tit-for-tat, the peers seeding the most will have the highest priority when requesting content themselves.
Due to the rarest-piece first policy, BitTorrent P2P content sharing system is quite unsuitable for multimedia streaming, which requires data sequencing and timely delivery. Simply forcing BitTorrent to request pieces in-order would not be sufficient because clients would only contain subsets of each others data. Then, bittorrent’s tit-for-tat policy, which aims to have requesting peers seeding parts to each-other would fail, for those peers would all already possess the same parts. In order to assess those issues, BASS [21] augments BitTorrent with an external media server (see Figure 5), with the only modification to BitTorrent being that it does not download any data prior to the current playback point.
P2Cast and P2VoD
P2Cast [22] is an architecture that relies only on unicast connections among peers (see Figure 6). The key idea of P2Cast is to have each client act as a server while it receives the video. P2Cast peers do not only receive the requested stream, but also contribute to the overall VoD service by forwarding the stream to other clients, as well as, caching and serving the initial part of the stream. This system uses a tree-based approach for streaming any given video content. In such a system, whenever a peer requests a content, two cases can occur: first, if the content is not currently requested, the peer will start a new branch, and request a direct seed from the Server. Second, if the content is already requested by another peer, the new requesting peer will attach itself to the lowest level of the branch formed by the peers requesting this content, thus asking other peers to seed the content to it, instead of overloading the server.
P2VoD [23] has a very similar approach, except that the algorithms involved in the creation of a tree differ in some aspects. Also, in P2Cast system, a video session is only open for a short period of time starting when the first client joins the video session. The result is that P2Cast can support more video sessions than P2VoD, which means greater bandwidth requirement to the server in P2Cast than in P2VoD. Several works use a network scheme very close to P2Cast and P2VoD [24][25].
In the case of a lot of clients requesting the same content at the same time, this approach is very efficient in Live Streaming. On the other hand, if we consider VoD streaming, a lot of various contents can be requested at a given time from the server. This means that a lot of client will request a direct seed from the main server, overloading that server. Indeed, VoD streaming systems need to offer large video content libraries, which will put some scalability strain on the overall system: the larger the content library the less likely to have enough peers receiving the same content, and it is more difficult to construct a video content distribution tree.
GridCast
GridCast [26][27][28] is a system, based on OCTOPUS [29], that aims to perfect Live Streaming by using Peer-to-Peer networks. Each peer, when watching a content, stores the content, and acts as a server for any other peer requesting the same content. Another advantage of storing already watched parts of a content, is that when a client decides to go back in time, it can use the data it already stored, instead of requesting a new seed. As for the peer willing to go forth in time, the system uses anchors: some key parts of the movie are pre-loaded, and when the user tries to advance, playback is automatically moved to the closest pre-loaded anchor.
In order to select the seeding peers, and the peers you seed for, an algorithm of distance, based on relative playback positions, is used. According to this algorithm, your closest neighbors are the ones whose movie is at the same playtime as yours (see Figure 5).
This approach tends to cluster the peers in sub-networks, and reduces a bit of the interest of having a large Peer-to-Peer network. Furthermore, while it is efficient for contents watched by many peers at the same time (like, for a Live Streaming System). For a large library of contents, the peers are less likely to be watching the same content, thus reducing the interest of GridCast.
Resource Allocation Strategies in P2P-VoD
The decision of allocating streaming resources to an incoming VoD request is a complex one with diverse implications on the system performances. The resource allocation algorithm can identify many contributing peers that can be used to satisfy the VoD request – these latter peers can have different available bandwidth capacities, and different stored content. The decision to use one of these peers to satisfy the current VoD request means reducing its uplink capacity for an extended period of time, and thus possibly shutting the peer’s content out of the system. In this section, we investigate several strategies for peer resource allocation in VoD systems.
User-based strategies
Several strategies were proposed by Zou et al. [34]. First, they present User algorithms. Those strategies are based on data computed directly from the peers. With those strategies, each peer computes some information, it is ready to send to the requesting peer, when requested. The requesting peer then selects the best peer, based on this information. The User-based Algorithms only uses data computed by the peers individually. This information is easy to access, and doesn’t require any special type of peer-to-peer network.
Random algorithm
This algorithm randomly chooses one serving node regardless of bandwidth and other state information. In most research works reported in the literature, this algorithm serves as a baseline for performance evaluation [47].
Fastest Link
This algorithm selects the peer with the largest uplink bandwidth regardless of the number of current sessions being served by that same peer. It emulates some file sharing systems where the only information available from the searching processes is the peers’ speeds in terms of bandwidth capacity. In this case, it may be reasonable to choose the fastest serving peer [34].
Greedy algorithm
The Greedy strategy [48] selects the peer that has the maximal ratio of uplink bandwidth available over the number of sessions currently served by the peer. It compares the values of !!!! , with b the uplink bandwidth, and n the number of seeding sessions of the peer, and selects the maximal. The rationale here is to tap the available bandwidth capacities at peers while avoiding unfairly putting a burden on peers with many downstream activities.
Fit algorithm
The idea of the fit algorithm [34] is to match the link speed of the requesting peer and the residual bandwidth of serving peers and save fast peers for later requests. It is directly linked to the Greedy Algorithm. However, in the Fit algorithm , if several peers are available for seeding at a speed higher than the download rate of the receiving peer, the receiving peer would select the source peer with uplink capacity that is the closest to the asking peer.
Global-based strategies
Zou et al. also introduce Global strategies [34], based on information of the overlay network. Those strategies require a global overview of the network, and therefore need a central entity gathering the information. By using a central node, it is possible to monitor the network. Then, this node is able to provide information of everything happening in the netwok. This overview the network is relevant for the following resource allocation algorithms.
Key performance factors of a P2P-VoD System
A P2P-VoD system is a complex architecture with respect to many aspects that impact the system performances. In this subsection, we present each of those performance factors. First, we will review the key performance factors affecting a P2P-based streaming system: the number of peers and uplink at each peer. Then, we explain how modifying the number of titles (size of the content library), and the number of parts (fragments) per title can influence a P2P-VoD system. Finally, we investigate the impact of the demand (VoD requests distribution over the content library) before showing how important the initial content dispatching is for the overall system performance.
Table of contents :
1. Problem Statement
2. Overview of the proposed solution
3. Thesis outline
Literature Review
1. Content Streaming Networks
1.1. Server-based approaches
1.2. Peer-based approaches
2. Peer-to-Peer Video-on-Demand Systems
2.1. Tracker-based approaches
2.1.1. pcVoD
2.1.2. BitTorrent and BASS : BitTorrent Assisted Streaming System
2.2. Tree-based approaches
2.2.1. P2Cast and P2VoD
2.2.2. GridCast
2.3. Overlay
2.3.1. PROMISE
2.4. Hybrid CDN-P2P
2.4.1. LiveSky
3. Resource Allocation Strategies in P2P-VoD
3.1. User-based strategies
3.1.1. Random algorithm
3.1.2. Fastest Link
3.1.3. Greedy algorithm
3.1.4. Fit algorithm
3.2. Global-based strategies
3.2.1. Greedy/Fit algorithms
3.2.2. Batch Greedy/Batch Fit
3.3. Reputation System
3.3.1. Highest Reputation Strategy
3.3.2. Tit-for-tat Strategy
3.3.3. Black List Strategy
3.3.4. Comparable Reputation Strategy
3.3.5. FairTrust
3.4. Topology-based Strategies
3.4.1. Neighbor-based
3.4.2. Localization and Congestion-aware system
4. Summary
Analysis of a P2P-VoD System
1. Key performance factors of a P2P-VoD System
1.1. Number of sessions per peer
1.2. Number of peers
1.3. Number of titles
1.4. Popularity per title
1.5. Number of parts per title
1.6. Demand pattern and evolution
1.7. Original Content Dispatching: initial titles injection in the P2P network
2. Performance evaluation metrics of a P2P-VoD System
2.1. Rate of VoD sessions rejected
2.2. Peer Participation and streaming load distribution over active peers
2.3. VoD Provisioning Responsiveness
3. Summary
P2P-VoD System
1. Video Fragmentation
2. System Components
2.1. SuperNode
2.2. Peer
2.3. Cache
3. Summary
1. Popularity-to-Availability Translation
1.1. Impact of Video Content Fragmentation
1.2. Proportional Content Popularity to Content Availability Model
2. Content dispatching strategies
2.1. Serial content fragments dispatching
2.2. Random content fragments dispatching
2.3. Popularity-Weighted content fragments dispatching
3. Summary
Static Resource Allocation
1. Introduction to Peer resource allocation
1.1. Why resource allocation is a key performance factor
1.2. Characterizing the resource allocation process
2. Single-metric based resource allocation
2.1. Caracterisation of basic resource allocation strategies
2.2. Higher Available Uplink Capacity First (HUF)
2.3. Lowest Popularity Score (LPS)
2.4. Lowest Critical-Score (LCS)
3. Multi-criteria resource allocation
3.1. Hierarchically Combined Resource Allocation Strategy
3.2. Multi-objective Optimization
4. Summary
Dynamic Resource Allocation
1. Towards dynamic resource allocation
1.1. Why performances evolve over time
1.2. Why resource allocation is a key performance factor
2. Dynamic resource allocation
2.1. Dynamic Switching between different RA strategies
2.2. Resource Allocation Strategy Evaluation and Selection
2.2.1. Prior probabilities
2.2.2. Probability density
2.2.3. Posterior probabilities
2.2.4. Monte-carlo Simulations
3. Strategy selection based on Evidence Theory
3.1. From Bayes to Dempster-Schafer
3.2. Dempster-Schafer Theory
3.2.1. Basic Probability Assignment
3.2.2. Belief function
3.2.3. Plausibility function
3.3. Application to Resource Allocation Strategy selection
3.3.1. Plausibility applied to strategy evaluation
3.3.2. Problem formulation
3.3.3. Plausibility estimation
4. Summary
Simulation Platform..
1. Experimental platform overview
Content Injection
1. General Study: Random algorithm
2. Popularity-Weighted Content Dispatching (PWCD) Algorithm
Resource Allocation
1. Dynamic demand evolution
2. Resource Allocation Strategies evaluation
2.1. Dynamically Selected Strategies by LB-RA
2.2. Peer Saturation
2.3. Peer Participation
2.4. Rejection Rate
3. Dempster-Schafer Theory applied to LB-RA
3.1. Rejection Rate
3.2. Entropy
3.3. Overall results and discussion
4. Summary
5. Summary of Results and Contributions
6. Future Work
References
