Maximizing total upload in latency-sensitive P2P applications

John R. Douceur, Jacob R. Lorch, and Thomas Moscibroda

Abstract

Motivated by an application in distributed gaming, we define and study the latency-constrained total upload maximization problem. In this problem, a peer-to-peer overlay network is modeled as a complete graph and each node vi has an upload bandwidth capacity ci and a set of receivers R(i). Each sender-receiver pair (vi, vj), where vj ∈ R(i), is a request that should be satisfied, i.e., vi should send a data packet to each vj ∈ R(i). The goal is to find a set of at most n multicast-trees Ti of depth at most 2, such that each node can be part of multiple trees, all capacity constraints are met, and the number of satisfied requests is maximized. In this paper, we prove that the problem is NP-complete, and we present an algorithm with approximation ratio 1 − 2/√cmin, where cmin is the minimum upload capacity. Finally, we also study the impact of network coding on the quality and approximability of the solution.

Details

Publication typeInproceedings
Published inProceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
Pages270–279
AddressSan Diego, CA
PublisherAssociation for Computing Machinery, Inc.
> Publications > Maximizing total upload in latency-sensitive P2P applications