Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Maximizing total upload in latency-sensitive P2P applications

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


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.


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