Scheduling algorithms for peer-to-peer collaborative file distribution

Abstract

Peer-to-Peer file sharing applications on the Internet, such as BitTorrent, Gnutella, etc., have been immensely popular. Prior research mainly focuses on peer and content discovery, overlay topology formation, fairness and incentive issues, etc, but seldom investigates the data distribution problem which is also a core component of any file sharing application. In this paper, we present the first effort in addressing this collaborative file distribution problem and formally define the scheduling problem in a simplified context. We suggest several types of algorithms, including a novel Bipartite Matching algorithm, for solving the problem. Simulation results show that our weighted bipartite algorithm finds an optimal solution for all cases tested. Therefore, we believe our algorithm is a promising solution to be employed as the core scheduling module in P2P file sharing applications, shortening the total download time experienced by users. © 2005 IEEE.