Utility Maximization in Peer-to-peer Systems

By

Professor Minghua Chen

Department of Information Engineering
The Chinese University of Hong Kong

Date: Feb 18, 2008 (Monday)

Time: 4:00pm - 5:00 pm

Venue: Rm. 1009 William MW Mong Engineering Building, CUHK

Abstract :

Abstract: Peer-to-Peer (P2P) applications have witnessed unprecedented growth on the Internet and are increasingly being used for real-time applications like video conferencing and live streaming. However, the design of the majority of P2P systems does not strive to achieve any systematic optimization of the total value to all peers under a resource sharing constraint. This may well be the next step in improving the performance of P2P systems. In this talk, we study the problem of utility maximization over P2P topology, in which aggregate application-specific utilities are maximized by running distributed algorithms on P2P nodes that 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. This new tree-rate based formulation is unique in the sense that it not only eliminates some mathematical difficulties associated with link-rate or path-rate based formulations, but also leads to easy implementation. 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. We first characterize the convergence behavior of the Primal-dual algorithm under multi-path settings, and then utilize our proposed sufficient condition to show its global exponential convergence to the optimal solution under different P2P communication scenarios we study. The primal-dual 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. This is a join work with Miroslav Ponec from Polytechnic University, and Sudipta Sengupta, Jin Li, and Philip A. Chou from Microsoft Research Redmond.

Biography:

Minghua Chen received his B.Eng. and M.S. degrees from the Department of Electronics Engineering at Tsinghua University in 1999 and 2001, respectively. He received his Ph.D. degree from the Department of Electrical Engineering and Computer Sciences at University of California at Berkeley in 2006. He spent one year visiting Microsoft Research Redmond as a Postdoc Researcher. He joined the Department of Information Engineering, the Chinese University of Hong Kong, in 2007, where he currently is an Assistant Professor. He wrote the book "IPv6 Principle and Practice" with Haisang Wu, Maoke Chen, Xinwei Hu, and Cheng Yan (People's Posts and Telecommunication Publishing House, 2000). He received the Eli Jury award from UC Berkeley in 2007, for his thesis work on wireless flow control. His current research interests include optimization and control theories with applications in peer-to-peer networking, wireless networking, and multimedia processing.