Uplink allocation beyond choke/unchoke: or how to divide and conquer best

ABSTRACT

Motivated by emerging cooperative P2P applications we study new uplink allocation algorithms for substituting the rate-based choke/unchoke algorithm of BitTorrent which was developed for non-cooperative environments. Our goal is to shorten the download times by improving the uplink utilization of nodes. We develop a new family of uplink allocation algorithms which we call BitMax, to stress the fact that they allocate to each unchoked node the maximum rate it can sustain, instead of an 1/(k + 1) equal share as done in the existing BitTorrent. BitMax computes in each interval the number of nodes to be unchoked, and the corresponding allocations, and thus does not require any empirically preset parameters like k. We demonstrate experimentally that Bit-Max can reduce significantly the download times in a typical reference scenario involving mostly ADSL nodes. We also consider scenarios involving network bottlenecks caused by filtering of P2P traffic at ISP peering points and show that BitMax retains its gains also in these cases.

REFERENCES

• 1: E. Altman, D. Barman, B. Tuffin, and M. Vojnovic. Parallel tcp sockets: Simple model, throughput and validation. In Proc. of IEEE INFOCOM '06, Barcelona, Spain, 2006.
• 2: Ashwin R. Bharambe, Cormac Herley, and Venkata N. Padmanabhan. Analyzing and improving a bittorrent networks performance mechanisms. In Proc. of IEEE INFOCOM '06, Barcelona, Spain, 2006.
• 3: Ruchir Bindal , Pei Cao , William Chan , Jan Medved , George Suwala , Tony Bates , Amy Zhang, Improving Traffic Locality in BitTorrent via Biased Neighbor Selection, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.66, July 04-07, 2006 [doi>10.1109/ICDCS.2006.48]
• 4: Bram Cohen. Incentives build robustness in BitTorrent. In Proc. of First Workshop on Economics of Peer-to-Peer Systems, Berkeley, CA, USA, Jun 2003.
• 5: Michal Feldman , Kevin Lai , Ion Stoica , John Chuang, Robust incentive techniques for peer-to-peer networks, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988788]
• 6: W. Feller. An Introduction to Probability Theory and Its Applications. Wiley, New York, 1968.
• 7: Christos Gkantsidis and Pablo Rodriguez. Network coding for large scale content distribution. In Proc. of IEEE INFOCOM '05, Miami, FL, USA, 2005.
• 8: Lei Guo , Songqing Chen , Zhen Xiao , Enhua Tan , Xiaoning Ding , Xiaodong Zhang, Measurements, analysis, and modeling of BitTorrent-like systems, Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, p.4-4, October 19-21, 2005, Berkeley, CA
• 9: A. Al Hamra, A. Legout, and C. Barakat. Understanding the properties of the Bittorrent Overlay. Technical Report 00162088, version 1, Inria, July 2007.
• 10: Nikolaos Laoutaris , Pablo Rodriguez , Laurent Massoulie, ECHOS: edge capacity hosting overlays of nano data centers, ACM SIGCOMM Computer Communication Review, v.38 n.1, January 2008 [doi>10.1145/1341431.1341442]
• 11: Arnaud Legout , Nikitas Liogkas , Eddie Kohler , Lixia Zhang, Clustering and sharing incentives in BitTorrent systems, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 12: Arnaud Legout , G. Urvoy-Keller , P. Michiardi, Rarest first and choke algorithms are enough, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177106]
• 13: Laurent Massoulié , Milan VojnoviĆ, Coupon replication systems, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 14: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.346, August 15-18, 2001
• 15: J. J. D. Mol, J. A. Pouwelse, M. Meulpolder, D. H. J. Epema, and H. J. Sips. Give-to-get: An algorithm for P2P video-on-demand. In Proc. of SPIE/ACM MMCN '08, San Jose, California, Jan 2008.
• 16: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 17: Michael Piatek, Tomas Isdal, Thomas Anderson, Arvind Krishnamurthy, and Arun Venkataramani. Do incentives build robustness in BitTorrent? In Proc. of NSDI'07, Cambridge, MA, 2007.
• 18: J. A. Pouwelse, P. Garbacki, D. H. J. Epema, and H. J. Sips. The BitTorrent P2P file-sharing system: Measurements and analysis. In Proc. of IPTPS'05, Ithaca, NY, 2005.
• 19: Dongyu Qiu , R. Srikant, Modeling and performance analysis of BitTorrent-like peer-to-peer networks, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 20: Slashdot. Comcast Hinders BitTorrent Traffic, Aug 2007.
• 21: Weishuai Yang , Nael Abu-Ghazaleh, GPS: A General Peer-to-Peer Simulator and its Use for Modeling BitTorrent, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.425-434, September 27-29, 2005 [doi>10.1109/MASCOT.2005.31]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
BitTorrent, peer-to-peer, uplink bandwidth allocation