X hits on this document





1 / 8

Minimizing File Download Time over Stochastic Channels in Peer-to-Peer Networks

Yuh-Ming Chiu and Do Young Eun Department of Electrical and Computer Engineering North Carolina State University {ychiu, dyeun}@ncsu.edu

Abstract — The average download time of a file is an important performance metric for a user in a peer- to-peer network. We point out that the common ap- proach of analyzing the average download time based on average service capacity is fundamentally flawed, and show that spatial heterogeneity and temporal cor- relation in the service capacity over different paths are the two major factors that have negative impact on the average file download time. We then propose a simple and distributed algorithm that can completely remove this negative impact of the two factors and yield the smallest possible average download time for each user in the network.

download time has been a common practice in the lit- erature [8, 4, 10, 14, 1, 2, 11]. However, the service ca- pacity of different sources in a network is usually not the same because of hardware limitations [13] of each com- puter or of topological limitation of the network. Further, the service capacity of each source is shown to vary with time [6, 7] due to the source workload or network conges- tion status. Both spatial heterogeneity in service capac- ity of different sources and temporal fluctuation of service capacity in time have significant impact on the average download time, as we will show later in the paper. The theoretical results obtained by the averaged value (F/c) is often too optimistic.

I. Introduction

The P2P file-sharing applications are becoming in- creasingly popular and account for more than 80% of the Internet’s bandwidth usage. Being a completely distrib- uted system, the service capacity of a P2P network, or the aggregated throughput, is shown to increase as the num- ber of uploading peers increases in the network [10, 14]. Thus, in an ideal case, the available bandwidth to each downloading peer will be constrained only by the limita- tion of the access link at the downloading site.

However, there are many factors that prevent a peer from fully utilizing the available bandwidth. The dis- tribution of the data in the network, peer selection al- gorithms, free-riders, and many other reasons impact the performance that a downloading peer receives. It is shown [5] that, in reality, even downloading files of less than 10 MB in size may take from 5 minutes up to several hours. The downloading time for a bigger file, say, 100 MB – 1 GB, can range from hours to a whole week. Fur- ther, even when all users try to download the same file, each of them may have very different downloading times, depending on the available capacity fluctuation, the path it chooses to download the file, etc.

It is a common belief that there exist a direct rela- tionship between the file download time and the service capacity the network can offer. The average download time of a file of size F is simply given by F/c, where

c is the average service capacity. ing the average service capacity to

This approach us- analyze the average

In this paper, we first characterize the relationship be- tween the heterogeneity in service capacity and the av- erage download time for each user, and show that the degree of diversity in service capacities has negative im- pact on the average download time. After we formally de- fine the download time over a stochastic capacity process, we prove that the correlations in the capacity make the average download time much larger than the commonly accepted value F/c, where c is the average capacity of the connection. It is thus obvious that the average download time will be reduced if there exists a (possibly distributed) algorithm that can efficiently eliminate the negative im- pact of heterogeneity in service capacities over different paths and the negative impact of correlations in time of a given path.

In practice, most P2P applications try to reduce the download time by minimizing the risk of getting stuck in a ‘bad’ path (the connection with small service capac- ity) by using smaller file sizes and/or having them down- loaded over different paths (e.g., parallel download). In other words, they try to reduce the download time by minimizing the bytes transferred from that source with small capacity. However, we show in this paper that this approach has almost no benefit at all in terms of explic- itly reducing the average download time for each user in the network. We then propose a simple and distrib- uted algorithm that can effectively remove the negative impact of both the correlations in the available capac- ity of a path and the heterogeneity in different sources and thus achieve the smallest possible download time. Through extensive simulations, we also verify that the


Document info
Document views12
Page views12
Page last viewedFri Oct 28 18:04:55 UTC 2016