Abstract

In this paper, we study the problem of utility
maximization in Peer-to-Peer (P2P) systems, in which aggregate
utilities are maximized by running distributed algorithms on P2P
nodes that are constrained by their uplink capacities. This may
be understood as extending the seminal flow control framework
in [1] and [2] from single-path unicast over general topology
to multi-path multicast over P2P topology, with network coding
allowed.
For single-rate multicast over certain popular P2P topologies,
we show that routing along a linear number of trees per
source can achieve the largest rate region that can be possibly
obtained by (inter-session) network coding. This simplification
result allows us to develop a new multi-tree routing formulation
for the problem. Despite of the negative results in literature on
convergence of Primal-dual algorithms under multi-path settings,
we have been able to develop a delay-based Primal-dual algorithm
to solve our multi-tree based utility maximization problem.
We characterize the convergence behavior of the Primal-dual
algorithm, and utilize our proposed sufficient condition to show
its global convergence to the optimal solution under different P2P
communication scenarios we study. We also discuss how to extend
our solution for single-rate multicast to multi-rate multicast.