File Swarming Systems
New: The paper on coupon replication systems
won the ACM SIGMETRICS 2005 Best Paper Award
Overview
We refer
to file swarming systems as a general
paradigm of file distribution where file is sliced into chunks; user is granted
initial chunk from a server; and other chunks are replicated among users.
Example: BitTorrent
A benefit
of the swarming paradigm is better scalability compared to standard central
server solutions. Swarming may also better utilize network links, thus achieve
larger throughput.
System is
characterized by replication strategy
that consists of (i) peering strategy (who to exchange from ?) and (ii) chunk selection strategy (which
chunk to pull ?) For example, BitTorrent uses as replication strategy a mixture
of local, greedy and random choices. Choice of replication strategy may significantly
effect the file download time.
Performance
of file swarming systems is believed to critically depend on user altruism in uploading chunks even
after have downloaded all chunks of a file (acting as seeds). It is believed
that if users were not altruistic, then some chunks may become rare and this
would severely increase the time for a user to acquire all file chunks. This
problem may be mitigated by some smart choice of replication strategy, for
example, rarest chunk first.
We
provide analysis of file swarming based on a model: we call coupon replication systems.
We
consider simple-minded replication strategies. The peering strategy is either
(layer) pick a random user from those having same number of coupons as the
instigator (flat) pick a random user. Once a peering is made, the instigator pulls
a random chunk of interest from the encounter user.
We assume
users are non altruistic.
The
results suggest: already simple random replication strategies yield good
performance. The choice of either replication strategy or user altruism may not
be critical.
References
- Coupon Replication
Systems, L. Massoulie and M. Vojnovic, ACM Sigmetrics 2005,
- ACM Sigmetrics 2005 talk slides,
June 2005.
Tutorials & lectures
- New: File Swarming Systems, Lecture, OPT
012 Operations Research Lecture, Charles University, Prague, Czech
Republic, Dec 2005.
People
Laurent Massoulie, Milan Vojnovic
Related work
Models
- Service Capacity
of Peer to Peer Networks, X. Yang and G. de Veciana, IEEE Infocom
2004,
- Modeling and Performance Analysis of BitTorrent-like Peer-to-Peer Networks, D. Qiu and R. Srikant, ACM Sigcomm 2004, Portland, Oregon, 2004.
-
Modeling,
Analysis and Improvement for BitTorrent-Like File Sharing Networks, Y.
Tian, D. Wu, K.-W. Ng, IEEE Infocom 2006, Barcelona, Spain, 2006.
Measurements
- Dissecting
BitTorrent: Five Months in a Torrent's Lifetime, M. Izal, G.
Urvoy-Keller, E. W. Biersack, P. A. Felber, A. Al Hamra, and L.
Garces-Erice, PAM 2004,
- The
BitTorrent P2P File-sharing System: Measurement and Analysis, J. A.
Pouwelse, P. Garbacki, D. H. J. Epema, H. J. Sips , IPTPS'05, Feb 2005.
- Measurements,
Analysis, and Modeling of BitTorrent-like Systems, L. Guo, S. Chen, Z.
Xiao, E. Tan, X. Ding, X. Zhang, IMC 2005.
May 04, 2006, http://research.microsoft.com/~milanv