A Distributed Constraint Optimization Solution to the P2P Video Streaming Problem

Theodore Elhourani, Nathan Denny, Michael M. MarefatAAAI 2007

Abstract

Peer-to-peer (P2P) video streaming faces significant challenges in scalability and timing, particularly under high churn. This paper proposes a decentralized solution by modeling the streaming network as a Distributed Constraint Optimization Problem (DCOP). By employing a "bounded negotiation" strategy based on the Distributed Breakout Algorithm (DBA), nodes can autonomously organize into streaming trees within strict playback buffer deadlines. Simulations on scale-free networks show that the system provides reliable, high-quality solutions rapidly, outperforming traditional decentralized methods.

Introduction

Scaling video multicast to large audiences is difficult due to the limitations of server-client architectures and the dynamic nature of P2P networks. The primary challenge is ensuring that nodes can find new content sources immediately when peers join or leave, preventing video stuttering or "rejection." This requires a decentralized mechanism that respects bandwidth constraints and operates within the tight timeframes of video playback buffers.

Methodology: DCOP and Bounded Negotiation

The authors frame the P2P streaming problem as a DCOP, where each node acts as an agent negotiating with neighbors to satisfy specific rules:

  • Hard Constraints: Essential requirements such as cycle prevention (a node cannot be its own ancestor), content availability (parents must have more cached data than children), and upload bandwidth limits.
  • Soft Constraints: Optimization goals like balancing bandwidth load across the network to prevent peer exhaustion.

The solution utilizes the Distributed Breakout Algorithm (DBA) with a "Bounded Negotiation" modification. Given the "anytime" nature of the algorithm, it can provide the best available solution at any point, which is crucial for meeting the hard deadlines imposed by the playback buffer.

Experimental Setup

The approach was evaluated using discrete event simulations on scale-free networks of 200 nodes, generated via the Holme and Kim model to reflect real-world internet topologies. Node churn was simulated using Poisson distributions to test the system's resilience to frequent arrivals and departures.

Analysis of Network Topology and Convergence

A key finding is the relationship between the network's clustering coefficient ($\gamma$) and the speed of convergence. As the clustering coefficient increases, the complexity of the negotiation grows, leading to more cycles required to reach a stable solution.

Impact of clustering coefficient ($\gamma$) on the average number of cycles required for convergence.

When $\gamma$ exceeds 0.5, the negotiation time spikes, suggesting that maintaining a lower clustering coefficient is beneficial for rapid tree formation in dynamic P2P environments.

Performance Evaluation

The "anytime" capability of the DCOP approach is a significant advantage. The system reaches high-quality solutions well within the safety margins of typical video buffers. For instance, even in complex scenarios, solutions are found in approximately 0.6 seconds.

Evolution of hard constraint satisfaction (a), soft constraint satisfaction (b), and overall solution quality (c) over negotiation cycles for varying clustering coefficients.

As shown in the figures above, the percentage of satisfied hard constraints and the overall quality of the solution ($Q$) improve rapidly within the first 10-15 cycles. This rapid improvement ensures that even if the negotiation is interrupted by the buffer deadline, the resulting streaming tree is highly functional. Furthermore, the DCOP approach demonstrated lower node rejection rates compared to existing schemes like P2CAST.

Conclusion and Future Work

This DCOP-based approach provides a resilient and decentralized framework for P2P video streaming. While effective, the current model assumes full caching of viewed content and an error-free communication channel. Future research should address the impact of limited peer storage, network latency, and packet loss on negotiation efficiency, as well as the effects of fluctuating bandwidth on tree stability.

Summary updated

BibTeX
@inproceedings{elhourani2007distributed,
  author = {Theodore Elhourani and Nathan Denny and Michael M. Marefat},
  title = {{A Distributed Constraint Optimization Solution to the P2P Video Streaming Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2007},
}
Figure