Existing p2p file sharing networks doesn't always give their users abilities to make an effective and fast searches for particular data. In this paper we introduce some improvements for main subset of these networks, especially for bittorrent and descript some well known methods of search query routing, used in other networks that may be useful for our purposes too. We describe some ideas of modification source of engines, used by usual and super peers of bittorrent network and illustrate some possibly useful changes in bittorrent dht structure.
The utilization of internet bandwidth by p2p
traffic grows very fast in the past years. The pure p2p
system is presented by some number of nodes with
absolutely identical functionality and connected
between each other. Such type of distributed systems
is a base of many file sharing networks like
kademlia,1gnutella2, etc. But there are a number of
file sharing networks with not pure p2p structure,
which are also called p2p networks. One of the most
popular of them is bittorrent [
Many of p2p systems (especially file sharing) are unstructured: their nodes with shared data on it appear and disappear constantly, network topology changes in time. So, success of particular data search request depends on this feature.
There are some known and successfully
implemented search algorithms in p2p networks.
They can be united in some classes: blind and
informed [
- original gnutella algorithm (FS/BFS): one
node contacts each other accessible nodes within
TTL hop; produces huge overhead [
- Modified BFS (MBFS): each node send
request to a random subset of other nodes, connected
to it; number of requests reduced in comparison with
FS [
- Iterative Deeping (ID): rather similar to
previous two methods, but realizes a special feature –
user defined termination condition; ID is
implemented in ed2k/kademlia [
- Random Walks (RW) [
- Super Peer (SP): initial (leaf) node contacts
a special super peer (hub) node, when sending a
search request; hub node processes this request and
send it to relevant leaves and neighbor hubs [
- Intelligent BFS (IBFS): each node stores a
special local index - pairs (query, neighbor_id) for
recently processed queries; when a new request
arrives, node checks its similarity to stored requests
and then extracts target nodes, which returned
maximum number of results to this requests and at
least redirects new request to them, waiting for
feedback with number of hits to update its local index
[
- APS: each node stores a special local index
– (neighbor_id, last_requested_object,
successesfailures value), where success-failures value updated
by walkers; this algorithm produces very small
overhead [
- GIA: each node sends request to subset of its neighbors, based on it’s announced capacity; this algorithm provides ability to make rather bandwidthefficient searches
- Routing indices (RI): nodes builds thematic
indices for stored documents (only documents, not
files), and stores some type of “goodness value” for
neighbors; this algorithm is bandwidth-effective for
searches, but not for indices and “goodness values”
building, updating and calculating [
- Distributed Resource Location Protocol
(DRLP): if current node has no data matching the
query, it forwards query to its neighbors waiting for
feedback about number of hits; all subsequent queries
are forwarded directly to the neighbors with non zero
hits [
- Gnutella with shortcuts (GS): original
gnutella FS algorithm is extended by making
shortcuts to nodes, which are useful to answering
queries (returns more results, than others) – so further
queries are sending to these nodes [
There are a number of P2P file sharing systems
with implemented informed and blind search
methods. For example Gnutella/Gnutella2 uses FS
method, so their each node’s query flood some part of
entire network resulting in rather robust and simple,
but bandwidth costly approach. SoulSeek uses
centralized indices, so it has bad load balancing and
vulnerable for technical failures or attacks (like
Distributed Denial of Service by generating too many
queries by leaf nodes to central indexing node). There
are also a number of research systems, developed
especially for searching documents: CHORD [
Search request routing in P2P is also similar to
traditional routing algorithms [
As it was noticed in the introduction of this article, utilization of internet bandwidth by p2p traffic grows very fast in the past years.
As we can see on the diagram presented below
(made by IDG News Service in 11.2007), p2p traffic
can utilize up to 70% of total internet bandwidth and
main part of this traffic is used by bittorrent/dht [
These networks were designed for effective sharing of huge data amounts (files of different types: video, music, software, etc). So their high popularity may be expected.
Kademlia and bittorrent dht uses a special distributed hash table like structures to store information about shared data and its source nodes. When new node wants to connect to network, it calculates a special hash value that will be used as unique id (node_id) of this node, and than announces it to some other subset (usually random) of known nodes - his immediate neighbors. While process of sharing new files in network, the new node calculates the hashes of these files content, using the same hash function and than announces these file hashes to nodes with the most similar node_id. So when other node wants to send search request to find sources of files with known content hashes, it send this request to most similar node_id neighbors. They forward this query to their neighbors with node_id most similar to hash, specified in query, etc. Usual termination condition is TTL hops or number of sources already found. But this is only file sources search method. In bittorrent dht nodes haven’t ability to search files by their name or other criteria. Kademlia allows using file search by their names using previously described ID method. As main terminate condition it uses number of unique file hashes, found during the query processing.
As we noticed before, bittorrent and bittorrent dht are the most popular networks nowadays. One of the key advantages of these networks is fast filetransfer protocol and descriptions for every file or group of files in the network. But they also have a big disadvantage: distributed file search by names or descriptions is not suggested and implemented for this network. There was a small Exeem project [3], which allows its users to search files by names in bittorrent using simple FS method for requesting other nodes with Exeem clients, but it wasn’t fast, stable and user friendly, so its development has been stopped in 2005.
So we want to suggest some new improvements
to bittorrent, based on building thematic indices [
Here we can see one peer, sending request (a special type of thin dotted link) to tracker I. Tracker I returns a number of different file group hashes if it can and then forwards this request for some neighbors – for example tracker III, because it have a similar local thematic index and then receives some results from this tracker and a number or sources for this results. At the last stage, Tracker I sends to the initial leaf node merged results, sorted by the number of peers or relevance to the search query. These results include only names of file groups, number of sources and hashes of this file groups. Than initial node can chose one or more of presented results and start download them, finding sources ip addresses and ports by hash in usual way (it can send new request for tracker I for these sources or find them using DHT). The main problem in implementing this feature is special private trackers and a client ratio system on it: every client node reports its uploaded and downloaded amount of data to such tracker and then receives sources for downloading files. This ratio system can prevent clients from downloading huge amounts of data without any uploading to other nodes. When DHT is used in sources searching process, these values can’t be checked by tracker for each group of files, so there is a way to fake them. The simple solution for this issue can be made with creating a special hash id for each peer, connected to particular tracker. These ids can be used in reports to private trackers by peers to prevent calculating upload/download statistics for alien nodes. So a node can upload and download data from a large set of nodes and report to tracker all of them, but in their responses, trackers can inform peers, that particular values in statistics are rejected, so these peers can exclude nodes with some ids from further statistic reports to trackers.
But it’s clear enough that only subset of tracker’s owners will accept and introduce new specification updates listed above. So another way of improving search routing methods in bittorrent/bittorrent dht network is modifying functionality only of usual nodes, not trackers. We took source code of bittornado torrent client and now applying the following modifications to it.
First way of client routing features improving is to give it ability to make its local thematic indices of downloaded files descriptions. These descriptions can be simply grubbed from tbsource or torrentpier based trackers (may be with the help of client’s user, providing his trackers login/password, needed to access descriptions via web interface). This improvement gives bittorrent nodes an ability to search files in dht with standard methods (FS/BFS, ID, etc) and also can become a base for further improvement of entire bittorrent dht with adding it functionality to store hashes of local thematic index keywords in the same way, as file content hashes are stored in it or in kademlia network. This will allow applying search queries via bittorrent dht in a native sources search way, used before and using now. The one disadvantage, which can decrease effectiveness of using this method, is different keywords frequency. It can critically increase the number of requests to particular nodes, which have “too popular” hashes as their ids. This problem is not solved yet, but we have some ideas about it, which need some experiments to be done in real bittorrent network segment and with a set of real trackers and clients.
4.1. Plan of experiments.
We will use our own bittorrent tracker with the current number or different nodes of about 8600 and some of the other trackers with similar material shared and some equal nodes between them that use the bittornado bittorrent client or original open source bittorrent or mainline clients. Our main goal is to test bittorrent dht network improvements with a set of criterias, which including
- query search time for data, which exists in the network
- query search time for data, which doesn’t exists in the network at the moment, where search request is performed
- number of peers and super-peers involved in random search query processing
- number of unique results returned on successful queries - number of sources of unique results returned These parameters will be compared with the same ones for usual bittorrent-dht network, including approximately the same set of nodes (not exactly the same set because of the permanently changing structure of the network) and not using any stored data about nodes content anywhere except one supernode per usual node.
This paper describes some well known methods of search query routing in p2p file sharing networks like FS/BFS, ID, IW, etc. In this paper we also introduce some methods that can help to improve search request routing methods in widely using p2p file sharing networks, especially bittorrent. No experimental results were given, because our work is not completed yet, but we believe that our approach should be useful for entire bittorrent network and it users and will give it some important features or search queries routing and information sources node discovery.