Utility Maximization in P2P Systems

Real-time peer-to-peer applications such as video conferencing have witnessed unprecedented growth but their design today does not strive to achieve any systematic optimization of the total value to all peers under a resource sharing constraint. We study the problem of maximizing aggregate application-specific utility of peers constrained by uplink capacities. We develop distributed algorithms for multi-tree routing and show exponentially-fast convergence to the optimal solution. We utilize only end-to-end delay measurements between nodes which allows the algorithms to be readily deployed on the Internet as shown through our experiments. For common P2P topologies we show that routing along a linear number of trees per source can achieve the largest possible rate region obtainable by network coding. This allows us to develop new multi-tree routing formulation of the problem. Our approach offers low delay and fast convergence along with automatic adaptation to dynamic network conditions and video stream characteristics. Moreover, we systematically extend it to handle the multi-rate case and show its performance in a video-conferencing application using scalable layered coding.