Utility maximization in peer-to-peer systems
Authors:
Open Access
- 2 June 2008
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 36 (1) , 169-180
Abstract
In this paper, we study the problem of utility maximization in P2P systems, in which aggregate application-specific utilities are maximized by running distributed algorithms on P2P nodes, which are constrained by their uplink capacities. This may be understood as extending Kelly's seminal framework from single-path unicast over general topology to multi-path multicast over P2P topology, with network coding allowed. For certain classes of 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 (multi-source) 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 applying Primal-dual algorithms to maximize utility under multi-path settings, we have been able to develop a Primal-dual distributed algorithm to maximize the aggregate utility under the multi-path routing environments. Utilizing our proposed sufficient condition, we show global exponential convergence of the Primal-dual algorithm to the optimal solution under different P2P communication scenarios we study. The algorithm can be implemented by utilizing only end-to-end delay measurements between P2P nodes; hence, it can be readily deployed on today's Internet. To support this claim, we have implemented the Primal-dual algorithm for use in a peer-assisted multi-party conferencing system and evaluated its performance through actual experiments on a LAN testbed and the Internet.Keywords
This publication has 18 references indexed in Scilit:
- Optimization Based Rate Control for Multicast with Network Coding2007
- Layering as Optimization Decomposition: A Mathematical Theory of Network ArchitecturesProceedings of the IEEE, 2007
- Multi-Path TCP: A Joint Congestion Control and Routing Scheme to Exploit Path Diversity in the InternetIEEE/ACM Transactions on Networking, 2006
- The H.264 Video Coding StandardIEEE MultiMedia, 2006
- Polynomial Time Algorithms for Multicast Network Code ConstructionIEEE Transactions on Information Theory, 2005
- Congestion Control for Fair Resource Allocation in Networks With Multicast FlowsIEEE/ACM Transactions on Networking, 2004
- Fairness and Stability of End-to-End Congestion Control*European Journal of Control, 2003
- Optimization based rate control for multirate multicast sessions2002
- Network information flowIEEE Transactions on Information Theory, 2000
- TCP Vegas: end to end congestion avoidance on a global InternetIEEE Journal on Selected Areas in Communications, 1995