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  v  i  has an upload bandwidth capacity  c  i  and a set of receivers  R ( i ). Each sender-receiver pair ( v  i , v  j ), where  v  j  ∈  R ( i ), is a  request  that should be satisfied, i.e.,  v  i  should send a data packet to each  v  j  ∈  R ( i ). The goal is to find a set of at most  n  multicast-trees  T  i  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/√ c min, where  c min is the minimum upload capacity. Finally, we also study the impact of  network coding  on the quality and approximability of the solution.
['John R. Douceur', 'Jacob R. Lorch', 'Thomas Moscibroda']
Maximizing total upload in latency-sensitive P2P applications