Adaptive Peer Selection

Daniel S. Bernstein, Zhengzhu Feng, Brian Neil Levine, and Shlomo Zilberstein
Department of Computer Science
University of Massachusetts
Amherst, Massachusetts 01003
{bern, fengzz, brian, shlomo}@[Link]

Abstract of the existing techniques rely on assumptions that ren-

der them inapplicable in the dynamic setting of peers.
In a peer-to-peer file-sharing system, a client de-
For instance, selection strategies based on experience
siring a particular file must choose a source from
which to download. The problem of selecting a with specific hosts do not apply when hosts are not
good data source is difficult because some peers likely to be encountered more than once. In addition,
may not be encountered more than once, and many selection strategies that rely on network-layer assistance
peers are on low-bandwidth connections. Despite are not feasible.
these facts, information obtained about peers just In this paper, we introduce techniques for efficiently
prior to the download can help guide peer selec- obtaining replicated content in peer-to-peer networks.
tion. A client can gain additional time savings by We assume that the client has obtained a list of peers,
aborting bad download attempts until an acceptable
each possessing a desired file. No assumptions are made
peer is discovered. We denote as peer selection the
entire process of switching among peers and finally about whether the client has previously encountered any
settling on one. Our main contribution is to use the of the peers on the list. The client has access to limited
methodology of machine learning for the construc- information about its bandwidth to each of the peers. In
tion of good peer selection strategies from past ex- addition, the client can perform partial downloads from
perience. Decision tree learning is used for rating peers before finally settling on one. We define as peer
peers based on low-cost information, and Markov selection the problem of switching among peers and fi-
decision processes are used for deriving a policy for nally settling on one, while keeping the total time to a
switching among peers. Preliminary results with minimum.
the Gnutella network demonstrate the promise of
this approach. The novel aspect of our approach to this problem is
that it is based on the machine learning methodology
from artificial intelligence. Our approach is not to intro-
1 Introduction duce a new strategy for peer selection, but rather to in-
In a peer-to-peer file-sharing system, data is replicated troduce techniques by which a client can automatically
among the peers participating in the system. Replicated derive a selection strategy based on its own experience.
data, while providing scalability and fault-tolerance, in- The strategies that are eventually produced are actually
troduces the problem of source selection. After deter- adapted to the client (hence the title).
mining the locations of a desired file, a client must de- The two phases of selection strategy execution pro-
cide where to download from in order to receive the file ceed as follows. First, passively collected information
quickly. We assume that only one peer can send data is used to rate each peer on the list in terms of expected
at a time, but our work can be extended to multi-source transfer time. In the Gnutella network, this information
downloading (see the discussion section). includes attributes from the search response messages
This problem has been studied mainly in the context regarding each peer’s current load, current bandwidth,
of mirrored Web data, where it is called the server se- and past uploading experience. A decision tree, learned
lection problem. Various solutions have been proposed using data from previous downloads, rates never-before-
and validated with experiments on the Internet [Gwertz- seen peers based on attribute values. One benefit of us-
man and Seltzer, 1995; Guyton and Schwartz, 1995; ing decision trees as a basis for the rating system is that
Yoshikawa et al., 1997; Sayal et al., 1998; Carter and they allow us to rate peers based on combinations of at-
Crovella, 1999; Dykes et al., 2000; Stemm et al., 2000; tributes. When individual attributes are unreliable, as is
Zegura et al., 2000; Hanna et al., 2001 ]. However, many the case in peer-to-peer networks, this becomes impor-
tant. response message: an indication of whether all of the
In the second phase of peer selection, the client uses peer’s upload slots were currently full (busy flag), an in-
the rating system to sort its list of peers, and then exe- dication of whether the peer had successfully uploaded
cutes a policy for performing partial file downloads from at least one file (uploaded flag), an indication of whether
the most promising ones and finally settling on a peer. the peer was firewalled (firewall flag), a number repre-
An appropriate framework for deriving such a policy is senting the connection speed (speed field), and an indi-
the Markov decision process (MDP) framework. The cation of whether the speed field was measured or set by
peer selection process can be modeled as an MDP, the the user (measured flag). Note that the accuracy of this
parameters of which are obtained from previous experi- information is dubious, as different client programs have
ence. The MDP can be solved for a selection policy that different policies for providing it. If the client was able
is optimal with respect to the model. to connect to the peer, the connection time was recorded,
We implemented our ideas using the Gnutella net- and if the client was able to download from the peer, the
work as our experimental platform. Downloading data number of bytes received was recorded every 0.5 sec-
was collected from four different client sites. Using this onds.
data, a different decision tree was learned for each of Data was collected separately at each of the four
the clients. The resulting rating systems turned out to be clients. The derivation of each client’s selection strat-
fairly accurate in their predictions. In addition, we con- egy, as described in the following sections, relied only
structed an MDP for each client and solved each MDP on that client’s data.
for a complete peer selection strategy. Although mostly
the same, the resulting policies did show some interest- 3 Rating Peers
ing differences across clients. We are in the process of In this section, we describe how to use training data to
evaluating the complete selection strategies with respect learn a decision tree for rating peers. We begin with a
to other possible strategies. brief introduction to decision trees. A more thorough
As we mentioned, by focusing on peer selection, we treatment can be found in [Quinlan, 1993] .
address issues not dealt with in the classical server selec-
tion work. In addition, there been little research on com- 3.1 Decision Trees
bining attributes to yield better predictions. Two excep- The decision trees we consider are used to approximate
tions are [Dykes et al., 2000] , in which prior bandwidth noisy binary-valued functions. The input to a decision
and round-trip latency were combined, and [Carter and tree consists of a set of attributes. In order to compute
Crovella, 1999], in which linear regression was used to the output of a decision tree, one traverses down from
combine round-trip latency and current available band- the root, following the branches dictated by the attribute
width. Finally, our focus on techniques for automati- values, until a leaf is reached. Each leaf contains an
cally learning a peer selection strategy from experience output value. A decision tree can also be viewed as a
is novel. list of if-then rules, one for each leaf. A decision tree
is learned using a dataset of input-output pairs from the
2 Data Collection function. In our case, the inputs were search message
attributes, and the output was an indication of whether
Our machine learning approach requires that we have a
the download from the corresponding source was fast
set of training data from which to learn. To this end,
(above the median speed) or slow (below the median
a period of approximately two weeks was set aside to
speed). Figure 1 shows an artificial dataset along with
perform several downloads and record statistics about
a decision tree that could have been learned from the
them. We note that, in practice, this training data could
dataset.
be produced as a byproduct of actual system use. This is
Given a dataset, one desires a reasonably-sized deci-
left for future work and is discussed briefly in the final
sion tree that returns outputs with a high degree of cer-
section of the paper.
tainty. In other words, for a given leaf, one would like
For data collection, we modified a version of Gtk-
most of the training instances associated with that leaf
Gnutella 0.85. The program was run at four client
to agree on the output. Notice that in the decision tree
sites: University of Massachusetts in Amherst, Univer-
in the figure, only one of the leaves contains a disagree-
sity of Maryland in College Park, University of Cali-
ment. One quantitative measure of the confidence of a
fornia in San Diego, and on an AT&T Broadband ca-
leaf is the entropy of the leaf. The entropy of a leaf is
ble modem connection in Boston, Massachusetts. Dur-
defined as
ing this time the clients repeatedly attempted to down-
load the first megabyte of randomly selected mp3 files E = −p0 log p0 − p1 log p1 ,
from randomly selected peers. For each peer contacted, where p0 is the fraction of instances with output 0, and
the following attributes were recorded from its search p1 is the fraction of instances with output 1.
  
  90 VLS
 LS
 
 
 80 U


Download Speed (KBytes/sec)

LF
 70 VLF
  
 60


 
 
 50

 
  40

  
 
 30
 

 20
 
10
 

 
 0
UMass UMD UCSD Boston

Figure 1: A dataset along with a decision tree that could have Figure 2: The average download speed corresponding to the
been learned from the dataset. ratings for each client, measured on the test data. Note that
the UMass and UMD decision trees had no VLS leaves.
3.2 Application to Rating Peers
ploy firewalls more often, but we have no data to back
Preliminary experiments revealed that the busy flag is this claim. Our cable modem was behind a firewall,
strongly correlated with connection success. Thus we which prevented it from downloading from firewalled
did not use the busy flag in the decision tree and decided peers (the Gnutella protocol does not allow this), and
to assign all instances with the busy flag set the lowest consequently rendered the firewall flag irrelevant. The
rating, B. Furthermore, we used only training down- best indicators of a fast download in this case seem to
loads that completed successfully for learning a decision be previous upload success and a high measured speed.
tree with the remaining four attributes. The indicators of a slow download seem to be that the
We used the ITI decision tree algorithm [Utgoff et al., peer has not successfully uploaded before and has a low
1997] to learn a decision tree for each client site. The value in its speed field.
leaves of the decision trees are rated in the following Figure 2 provides evidence of the rating system’s util-
way. First the leaves are sorted according to how many ity. It illustrates how rating correlates with download
instances each contains. The bottom 50% are assigned speed on test data (a small part of the dataset not used
the rank U (uncertain). These leaves contain too few for training). We see that peers rated as VLF give signif-
instances to provide reliable information. Any of the icantly faster downloads than those with other ratings.
remaining leaves with E > 0.918 are assigned rank U
because of the high uncertainty inherent in them. For
each of the remaining leaves, if the majority of the leaf’s
4 Peer Selection
instances are above the median speed, and E > 0.65, In the preceding section, we showed how to construct
then the leaf is assigned LF (likely fast). A similar rule a rating system for peers based on low-cost attributes.
holds for categorizing leaves as LS (likely slow). For After sorting its list according to rating, the client can
the leaves still remaining, if the majority of the leaf’s perform a sequence of partial downloads, eventually set-
instances are above the median speed, then the leaf was tling on a peer. Since partial downloads consume time,
assigned VLF (very likely fast). A similar rule holds for the client must proceed in an intelligent manner. It basi-
categorizing leaves as VLS (very likely slow). This com- cally needs to make a sequence of good decisions, end-
pletes the rating system (from least to most desirable): ing with the decision to commit to a peer.
B, VLS, LS, U, LF, VLF. An elegant framework for addressing this kind of se-
Examining the resulting rating systems, we were able quential decision-making problem is the Markov deci-
to extract some general rules. For the campus connec- sion process (MDP) framework [Puterman, 1994]. An
tions, a measured high speed along with a positive fire- MDP models an agent acting in a stochastic environ-
wall flag were indicative of a fast download. The mea- ment with the aim of minimizing expected long-term
sured high speed makes sense, but there is not a clear cost. Our agent is the Gnutella client, and its long-term
explanation of why firewalled hosts would be faster; we cost is the total time to obtain the first megabyte of a
speculate that “always on,” high-speed hosts tend to em- file, including the time for connection establishment and
aborted downloads. To achieve this goal, it has a policy may either continue its download attempt with the ac-
that indicates the situations in which it should abort its tive peer or start over with a new peer. In the connecting
current download and start over with the next peer on phase, an action is chosen every 0.5 seconds, and in the
the list. After describing the MDP framework in more downloading phase, an action is chosen every 1.0 sec-
detail, we show how an MDP can be constructed from onds. The states of the problem are as follows. The
training data and solved to yield a selection strategy. pre-connecting states,
4.1 Markov Decision Processes P = {B, VLS , LS , U, LF , VLF },
We consider a type of MDP in which the agent tries indicate the rating of the active peer. The connecting
to minimize the expected total time to reach a goal. states,
The process proceeds through a sequence of stages t = N = {B, VLS , LS , U, LF , VLF } ×
0, 1, 2, 3, . . . At each stage, the agent perceives the state {0.5, 1.0, 1.5, 2.0, 2.5, 3.0},
of the process, st ∈ S, and chooses an action, at ∈ A.
One stage later, the process produces a numerical cost, indicate the rating of the active peer and how much time
ct , and a next state, st+1 . This continues until a zero- has passed since the active peer was first contacted. The
cost absorbing state is reached, which indicates the at- downloading states,
tainment of the goal and the end of an episode. D = {B , VLS , LS , U , LF , VLF } × {1.0, 2.0, 3.0} ×
Formally, an MDP is a tuple hS, A, T, Ci, where S
{(0-1), (1-2), (2-4), (4-8), (8-16),
is a finite set of states; A is a finite set of actions;
T (s, a, s0 ) is a transition function representing the prob- (16-32), (32-64), (64-128), (128-∞)},
ability of transitioning from state s to state s 0 under ac- indicate the rating of the active peer, the time spent
tion a; and C(s, a, s0 ) is a cost function giving the cost downloading so far, and the (discretized) average speed
for executing action a in state s and transitioning to state so far (KB/sec). Finally we have an absorbing state, a,
s0 . Actions are chosen according to a policy, δ : S → A. which is entered at the end of the downloading phase.
The cost-to-go function, Jδ (s), for a policy δ gives the Thus S = P ∪ N ∪ D ∪ {a}, and |S| = 205.
expected (discounted) sum of future costs upon execut- Since the only cost in our problem is time, our cost
ing δ from state s. The aim is to find a policy δ that function is relatively straightforward. A transition into a
minimizes Jδ (s) for all states s. MDPs can be solved ef- pre-connecting state incurs no cost. For transitions into
ficiently using dynamic programming [Bellman, 1957]. connection and download states, the immediate costs are
0.5 and 1.0, respectively. Upon entry into the absorbing
4.2 Peer Selection as an MDP state, a final cost is incurred. This cost is the time that it
We first provide a high-level description of the MDP would take to download the rest of a 1 MB file, assuming
model that is constructed from the training data. This the speed from the first 3 seconds persists. Given this
MDP is an idealized model of the peer selection pro- cost function, the total cost for an episode is equal to the
cess, in which the client desires a 1 MB file and has ac- time taken to download a complete 1 MB file, including
cess to an unlimited list of peers possessing the file. At the overhead for connection establishment and aborted
any given time, it interacts with only one peer, denoted downloads.
the active peer. The interaction consists of two phases. The parameters for the transition dynamics are de-
First is the connecting phase, which lasts a maximum of rived using the training data. The initial pre-connecting
3 seconds. If no connection is made during that time, a state is drawn from a distribution that matches the distri-
new peer is randomly drawn from the list. If a connec- bution over ratings observed in the data. The rating com-
tion is established, the downloading phase begins. After ponent of the state remains fixed until the episode ends
3 seconds of downloading have passed, the client au- or an abort action has been performed. At any stage, an
tomatically commits to downloading the rest of the file abort action causes a transition to a new pre-connecting
from the currently active peer, and the episode is over. state, drawn from the distribution mentioned above. For
Failures can only occur during the connecting phase. transitions into connecting states, the probabilities are
For the first 3 seconds after a connection is made, the determined from the distribution over connect times in
download speed may fluctuate, but it remains constant the training data. If the 3 second point of the connect-
from the 3 second point on. Some aspects of our model ing phase is reached, an automatic transition to a new
may seem unrealistic; however, our objective is not re- pre-connecting state occurs on the next step. The proba-
alism but a model that can be solved quickly to yield an bilities for transitions into downloading states are deter-
effective policy. mined from the training data. At the end of the down-
We now describe the model in more detail. The ac- loading phase, there is a deterministic transition into the
tion set contains two elements. At each stage, the agent absorbing state.
4.3 The Resulting Policies One natural question that arises from this work is
We solved each of the clients’ MDPs using a dynamic whether the rating system and MDP can be updated on-
programming algorithm. Not surprisingly, the policies line, based on data from actual system use. This is often
are similar. In most cases, the policy aborts if no con- referred to as reinforcement learning [Sutton and Barto,
nection has been made in 0.5 seconds, or if a connec- 1998] in the artificial intelligence community. We see
tion has been made but the speed at 1 second is below no major obstacles to doing this, and it has advantages
a threshold. The threshold is usually 32 KB/sec. For over offline training. One advantage is that the time
the cable modem connection, there are a few ratings for and congestion incurred by gathering large batches of
which the threshold is lower. This makes intuitive sense. training data are eliminated. In addition, an online ap-
As connection speed decreases, the client’s connection proach allows for adaptation to changes in the Gnutella
becomes more of a bottleneck, and it makes less sense network and in local traffic conditions, which could in
for the client to be choosy about which peer it down- turn lead to better overall performance. Also interesting
loads from. We conjecture that a modem would have a are model-free online learning techniques, which learn
very low threshold. a policy without first constructing an MDP (see, e.g.,
[Williams, 1992]). These more direct approaches can
There are some exceptions to the aforementioned pol-
alleviate some the burdensome assumptions implicit in
icy rules. Some are difficult to explain and could be due
an MDP model, but usually require more data.
to modeling assumptions and noise in the data. There is
however, one apparently meaningful exception. If a peer In our study, we restricted the number of concurrent
is highly rated, policies are sometimes willing to wait download attempts to be one. It has been shown, how-
longer to establish a connection. This makes sense, as it ever, that parallel access to multiple sources can lead
is worth investing extra time when the potential payoff to lower transfer times [Byers et al., 1999; Rodriguez
is high. and Biersack, 2002]. Indeed, many of today’s peer-to-
We performed some preliminary experiments inte- peer clients employ multi-source downloads. We be-
grating the complete selection strategies into a client and lieve that our methods can be extended to provide in-
using the client to obtain popular files. Our strategies are telligent management of parallel transfers. A set of
competitive with random strategies and strategies based promising peers can be identified before the start of the
on round-trip latency because they often quickly find download, and peers can be switched into and out of
peers with high bandwidth connections. A careful as- the set during the download. Intelligent parallel trans-
sessment of our strategies under a variety of conditions fers should achieve maximal performance with fewer
remains to be done. connections than naive parallel transfers, thus reducing
congestion in the network. Some evidence of this is
provided in [Zeitoun et al., 2002], in which round-trip
5 Discussion latency is used to select a set of servers for a parallel
We have presented an approach to peer selection based download.
on the machine learning methodology. Decision trees
were used for learning peer rating systems, and our ex- Acknowledgments
periments showed the resulting rating systems to be ac-
curate. The MDP framework was used for deriving We are grateful to Geoff Volker and Stephen Savage at
policies for aborting downloads. These policies decide UCSD and Samrat Bhattacharjee at UMD for provid-
whether to continue or abort based on the state of the ing the remote accounts used in our experiments. We
current download, so as to minimize the total time to also thank Zihui Ge for helping with our data collection.
receive the file. This work was supported in part by the National Science
By adding more information to the client’s state, more Foundation under grants IIS-9907331, ANI-0133055,
sophisticated and better-performing policies should be and EIA-0080119. Daniel Bernstein was supported by a
possible. Information about peers other than the active NASA GSRP Fellowship. Any opinions, findings, and
peer should be useful—whether or not it is advantageous conclusions or recommendations expressed in this mate-
to abort sometimes depends on whether other promising rial are those of the authors and do not reflect the views
peers are available. In situations where a client will be of the NSF or NASA.
downloading files of varying sizes, it may also be useful
to base decisions on the size of the desired file. As files References
get larger, it is probably worth investing more time in
trying to find a well-performing one. Finally, it may be [Bellman, 1957] Richard E. Bellman. Dynamic Pro-
a good idea to incorporate performance estimators such gramming. Princeton University Press, Princeton,
as hop count and round-trip latency into the MDP. NJ, 1957.
[Byers et al., 1999] John Byers, Michael Luby, and [Williams, 1992] Ronald J. Williams. Simple statistical
Michael Mitzenmacher. Accessing multiple mirror gradient-following algorithms for connectionist rein-
sites in parallel: Using tornado codes to speed up forcement learning. Machine Learning, 8:229–256,
downloads. In Proceedings of INFOCOM ’99, April 1992.
1999. [Yoshikawa et al., 1997] Chad Yoshikawa, Brent Chun,
[Carter and Crovella, 1999] Robert L. Carter and Paul Eastham, Amin Vadhat, Thomas Anderson, and
Mark E. Crovella. On the network impact of David Culler. Using smart clients to build scalable
dynamic server selection. Computer Networks, services. In Proceedings of the First USENIX Sympo-
31(23-24):2529–2558, 1999. sium on Internet Technologies and Systems, Decem-
[Dykes et al., 2000] Sandra G. Dykes, Kay A. Robbins, ber 1997.
and Clinton L. Jeffery. An empirical evaluation of [Zegura et al., 2000] Ellen W. Zegura, Mostafa H. Am-
client-side server selection algorithms. In Proceed- mar, Zongming Fei, and Samrat Bhattacharjee.
ings of INFOCOM ’00, March 2000. Application-layer anycasting: A server selection
[Guyton and Schwartz, 1995] James D. Guyton and architecture and use in a replicated web service.
Michael F. Schwartz. Locating nearby copies of IEEE/ACM Transactions on Networking, 8(4):455–
replicated Internet servers. In Proceedings of SIG- 466, 2000.
COMM ’95, August 1995. [Zeitoun et al., 2002] Amgad Zeitoun, Hani Jomjoom,
[Gwertzman and Seltzer, 1995] James Gwertzman and and Mohammed El-Gendy. Scalable parallel-access
Margo Seltzer. The case for geographical push- for mirrored servers. In Proceedings of IASTED
caching. In Proceedings of the 1995 Workshop on International Conference on Applied Informatics,
Hot Operating Systems, 1995. February 2002.
[Hanna et al., 2001] Katrina M. Hanna, Nandini
Natarajan, and Brian Neil Levine. Evaluation of a
novel two-step server selection metric. In Proceed-
ings of IEEE International Conference on Network
Protocols, November 2001.
[Puterman, 1994] Martin L. Puterman. Markov Deci-
sion Processes. J Wiley & Sons, New York, NY,
1994.
[Quinlan, 1993] J. Ross Quinlan. C4.5: Programs for
Machine Learning. Morgan Kaufmann, San Mateo,
CA, 1993.
[Rodriguez and Biersack, 2002] Pablo Rodriguez and
Ernst W. Biersack. Dynamic parallel-access to repli-
cated content in the Internet. IEEE/ACM Transac-
tions on Networking, 10(4):455–464, 2002.
[Sayal et al., 1998] Mehmet Sayal, Yuri Breitbart, Peter
Scheuermann, and Pradek Vigralek. Selection algo-
rithms for replicated web servers. Performance Eval-
uation Review, 26(3):44–50, 1998.
[Stemm et al., 2000] Mark Stemm, Randy Katz, and
Srinivasan Seshan. A network measurement archi-
tecture for adaptive applications. In Proceedings of
INFOCOM ’00, March 2000.
[Sutton and Barto, 1998] Richard S. Sutton and An-
drew G. Barto. Reinforcement Learning: An Intro-
duction. MIT Press, Cambridge, MA, 1998.
[Utgoff et al., 1997] Paul E. Utgoff, Neil C. Berkman,
and Jeffery A. Clouse. Decision tree induction based
on efficient tree restructuring. Machine Learning,
29:5–44, 1997.