全文文献

J Sched (2008) 11: 105120 DOI 10.1007/s10951-007-0017-9

Optimal scheduling of peer-to-peer le dissemination

Jochen Mundinger Richard Weber Gideon Weiss

Received: 27 June 2006 / Accepted: 19 February 2007 / Published online: 23 August 2007 Springer Science+Business Media, LLC 2007

Abstract Peer-to-peer (P2P) overlay networks such as Bit-Torrent and Avalanche are increasingly used for disseminating potentially large les from a server to many end users via the Internet. The key idea is to divide the le into many equally-sized parts and then let users download each part (or, for network coding based systems such as Avalanche, linear combinations of the parts) either from the server or from another user who has already downloaded it. However, their performance evaluation has typically been limited to comparing one system relative to another and has typically been realized by means of simulation and measurements. By contrast, we provide an analytic performance analysis that is based on a new uplink-sharing version of the well-known broadcasting problem. Assuming equal upload capacities, we show that the minimal time to disseminate the le is the same as for the simultaneous send/receive version of the broadcasting problem. For general upload capacities, we provide a mixed integer linear program (MILP) solution

Research of G. Weiss is supported in part by Israel Science Foundation Grants 249/02 and 454/05. Collaboration of the authors was supported in part by European Network of Excellence Euro-NGI.

J. Mundinger ( )

EPFL-IC-LCA, BC203, Station 14, 1015 Lausanne, Switzerland e-mail: [email protected]

R. WeberStatistical Laboratory, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UKe-mail: [email protected]

G. WeissDepartment of Statistics, University of Haifa, Mount Carmel 31905, Israele-mail: [email protected]

and a complementary uid limit solution. We thus provide a lower bound which can be used as a performance benchmark for any P2P le dissemination system. We also investigate the performance of a decentralized strategy, providing evidence that the performance of necessarily decentralized P2P le dissemination systems should be close to this bound and, therefore, that it is useful in practice.

Keywords BitTorrent protocol Broadcasting problem Content distribution File sharing Load balancing Makespan Peer-to-peer Performance evaluation

1 Introduction

Suppose that M messages of equal length are initially known only at a single source node in a network. The so-called broadcasting problem is about disseminating these M...