Peer-to-peer Utility Maximization

Minghua Chen, Sudipta Sengupta, Miroslav Ponec, Philip A. Chou, and Jin Li

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.

Details

Publication typeInproceedings
Published inConference on Information Sciences and Systems
PublisherInstitute of Electrical and Electronics Engineers, Inc.
> Publications > Peer-to-peer Utility Maximization