research-article

Utility maximization in peer-to-peer systems

Authors:

Miroslav Ponec,

Sudipta Sengupta,

Philip A. ChouAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 36, Issue 1

Pages 169 - 180

https://doi.org/10.1145/1384529.1375477

Published: 02 June 2008 Publication History

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.

References

[1]

R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network information flow. IEEE Trans. Inform. Theory, (4):1204--1216, July 2000.

Digital Library

[2]

D. P. Bertsekas. Nonlinear Programming. Athena Scientific, 1999.

[3]

D. Bertsimas and J. N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997.

Digital Library

[4]

L. S. Brakmo and L. L. Peterson. TCP Vegas: end-to-end congestion avoidance on a global internet. IEEE J. Select. Areas Commun., (8):1465--1480, Oct. 1995.

Digital Library

[5]

L. Chen, T. Ho, S. H. Low, M. Chiang, and J. C. Doyle. Optimization based rate control for multi-cast with network coding. In Proceedings of IEEE INFOCOM, Anchorage, Alaska, May 2007.

Digital Library

[6]

M. Chen, M. Ponec, S. Sengupta, J. Li, and P. A. Chou. Utility Maximization in Peer-to-Peer Systems Microsoft Research Technical Report, August 2007.

[7]

M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle. Layering as optimization decomposition: a mathematical theory of network architectures. 95(1):255--312, Jan. 2007.

[8]

S. Deb and R. Srikant. Congestion control for fair resource allocation in networks with multicast flows. IEEE Trans. Automat. Contr., (2):274--285, Apr. 2004.

Digital Library

[9]

J. Edmonds. Edge-disjoint branchings. Combinatorial Algorithms, R. Rustin, ed., pages 91--96, 1973.

[10]

H. Han, S. Shakkottai, C. Hollot, R. Srikant, and D. Towsley. Multi-path TCP: A joint congestion control and routing scheme to exploit path diversity in the internet. IEEE/ACM Trans. Networking, 2006.

Digital Library

[11]

S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhiuzen. Polynomial time algorithms for multicast network code construction. IEEE Trans. on Info. Thy., 51(6):1973--1982, 2005.

Digital Library

[12]

K. Jain, M. Mahdian, and M. R. Salavatipour. Packing steiner trees. In 14th ACM-SIAM Symp. on Discrete Algorithms (SODA), Jan. 2003.

Digital Library

[13]

H. Kalva. The h.264 video coding standard. IEEE Trans. Multimedia, 13(4).

Digital Library

[14]

K. Kar, S. Sarkar, and L. Tassiulas. Optimization based rate control for multirate multicast sessions. In IEEE INFOCOM, Anchorage, Alaska, Apr. 2001.

[15]

F. P. Kelly. Fairness and stability of end-to-end congestion control. European Journal of Control, pages 159--176, 2003.

[16]

F. P. Kelly, A. Maulloo, and D. Tan. Rate control for communication networks: shadow prices, proportional fairness, and stability. Journal of the Operational Research Society, pages 237--252, 1998.

[17]

J. Li, P. A. Chou, and C. Zhang. Mutualcast: an efficient mechanism for content distribution in a p2p network. In Proceedings of Acm Sigcomm Asia Workshop, Beijing, China, Apr. 2005.

[18]

X. Lin and N. B. Shroff. Utility maximization for communication networks with multi-path routing. IEEE Trans. Automat. Contr., (5):766--781, May 2006.

[19]

T. Liu, Y. Wang, J. Boyce, Z. Wu, and H. Yang. Subjective quality evaluation of decoded video in the presence of packet losses. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1125--1128, April 2007.

[20]

S. H. Low and D. E. Lapsley. Optimization flow control, i: Basic algorithm and convergence. IEEE/ACM Trans. Networking, (6):861--875, Dec. 1999.

Digital Library

[21]

S. H. Low, L. Peterson, and L. Wang. Understanding vegas: A duality model. Journal of ACM, 49(2):207--235, Mar. 2002.

Digital Library

[22]

D. S. Lun, N. Ratnakar, M. Maäedard, R. Koetter, D. R. Karger, T. Ho, E. Ahmed, and F. Zhao. Minimum-cost multicast over coded packet networks. IEEE Trans. Inform. Theory, (6):2608--2623, June 2006.

Digital Library

[23]

J. Mo and J. Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Trans. Networking,(5):556--567, Oct. 2001.

Digital Library

[24]

MOSEK ApS. MOSEK Optimization Software.

[25]

Z. Ni. Network Emulator for Windows/CE. Microsoft Research Asia, Internal documentation.

[26]

V. Padman and N. Memon. Design of a virtual laboratory for information assurance education and research. In Proceedings of the 2002 IEEE Workshop on Information Assurance and Security, West Point, NY, June 2002.

[27]

T. Voice. Stability of Congestion Control Algorithms with Multi-Path Routing and Linear Stochastic Modelling of Congestion Control. PhD thesis, University of Cambridge, Cambridge, UK, May 2006.

[28]

Y. Wu and S.-Y. Kung. Distributed utility maximization for network coding based multicasting: a shortest path approach. IEEE J. Select. Areas Commun., (8):1475--1488, Aug. 2006.

Digital Library

[29]

X. Yan, R. W. Yeung, and Z. Zhang. The capacity region for multi-source multi-sink network coding. In 2007 IEEE International Symposium on Information Theory (ISIT2007), Nice, France, June 2007.

Cited By

Cheng JChinchali STang A(2023)Task-aware Network Coding over Butterfly Network2023 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT54713.2023.10206825(1496-1501)Online publication date: 25-Jun-2023
https://doi.org/10.1109/ISIT54713.2023.10206825
Huang GLiu JZhang BLi C(2022)Quality-driven video streaming for ultra-dense OFDMA heterogeneous networksComputer Networks10.1016/j.comnet.2022.109398218(109398)Online publication date: Dec-2022
https://doi.org/10.1016/j.comnet.2022.109398
Anandaraj MGaneshkumar PSelvaraj KVijayakumar K(2019)An Efficient Framework for Network Code based Multimedia Content Distribution in a Hybrid P2P NetworkJournal of Circuits, Systems and Computers10.1142/S0218126620501571Online publication date: 7-Nov-2019
https://doi.org/10.1142/S0218126620501571
Show More Cited By

Index Terms

Utility maximization in peer-to-peer systems

Recommendations

Utility maximization in peer-to-peer systems
SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

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 ...
Understanding overlay characteristics of a large-scale peer-to-peer IPTV system

This article presents results from our measurement and modeling efforts on the large-scale peer-to-peer (p2p) overlay graphs spanned by the PPLive system, the most popular and largest p2p IPTV (Internet Protocol Television) system today. Unlike other ...
Interest-Intended Piece Selection in BitTorrent-like peer-to-peer file sharing systems

BitTorrent is a popular peer-to-peer file sharing system and a target file shared through BitTorrent is partitioned into pieces and downloaded from multiple peers in parallel in order to shorten the download process. However, due to peer dynamics in P2P ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 36, Issue 1

SIGMETRICS '08

June 2008

469 pages

ISSN:0163-5999

DOI:10.1145/1384529

Issue’s Table of Contents

SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2008
486 pages
ISBN:9781605580050
DOI:10.1145/1375457
General Chair:
Zhen Liu
IBM T. J. Watson Research Center, USA
,
Program Chairs:
Vishal Misra
Columbia University, USA
,
Prashant Shenoy
University of Massachusetts, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2008

Published in SIGMETRICS Volume 36, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

104
Total Citations
View Citations
833
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)2

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng JChinchali STang A(2023)Task-aware Network Coding over Butterfly Network2023 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT54713.2023.10206825(1496-1501)Online publication date: 25-Jun-2023
https://doi.org/10.1109/ISIT54713.2023.10206825
Huang GLiu JZhang BLi C(2022)Quality-driven video streaming for ultra-dense OFDMA heterogeneous networksComputer Networks10.1016/j.comnet.2022.109398218(109398)Online publication date: Dec-2022
https://doi.org/10.1016/j.comnet.2022.109398
Anandaraj MGaneshkumar PSelvaraj KVijayakumar K(2019)An Efficient Framework for Network Code based Multimedia Content Distribution in a Hybrid P2P NetworkJournal of Circuits, Systems and Computers10.1142/S0218126620501571Online publication date: 7-Nov-2019
https://doi.org/10.1142/S0218126620501571
Fouladi SEmmons JOrbay EWu CWahby RWinstein KSeshan SBanerjee S(2018)SalsifyProceedings of the 15th USENIX Conference on Networked Systems Design and Implementation10.5555/3307441.3307464(267-282)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.5555/3307441.3307464
D'aronco SMena SFrossard P(2017)Distributed Rate Allocation in Switch-Based Multiparty Videoconferencing SystemACM Transactions on Multimedia Computing, Communications, and Applications10.1145/309283513:3s(1-23)Online publication date: 28-Jun-2017
https://dl.acm.org/doi/10.1145/3092835
He QZhang CMa XLiu J(2017)Fog-Based Transcoding for Crowdsourced Video LivecastIEEE Communications Magazine10.1109/MCOM.2017.160082655:4(28-33)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/MCOM.2017.1600826
Apu KMahmud NHasan FSagar S(2017)P2P video conferencing system based on WebRTC2017 International Conference on Electrical, Computer and Communication Engineering (ECCE)10.1109/ECACE.2017.7912968(557-561)Online publication date: Feb-2017
https://doi.org/10.1109/ECACE.2017.7912968
Wu WMao HWang YWang JWang WTian C(2017)CoolConferencing: Enabling Robust Peer-to-Peer Multi-Party Video ConferencingIEEE Access10.1109/ACCESS.2017.27687985(25474-25486)Online publication date: 2017
https://doi.org/10.1109/ACCESS.2017.2768798
D'Aronco SMena SFrossard PTimmerer C(2016)Distributed rate allocation in switch-based multiparty videoconferenceProceedings of the 7th International Conference on Multimedia Systems10.1145/2910017.2910595(1-11)Online publication date: 10-May-2016
https://dl.acm.org/doi/10.1145/2910017.2910595
Wei NZhang Z(2016)Competitive access in multi-RAT systems with regulated interference constraints干扰约束条件下多无线接入系统中的竞争接入Science China Information Sciences10.1007/s11432-015-0625-360:2Online publication date: 9-Nov-2016
https://doi.org/10.1007/s11432-015-0625-3
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents