[Gnugle-developers] Re: gnugle

[Marco L. <ma...@ma...>]

Hi Joe!

> I am interested in your project, having had the same or similar idea
> myself on various occaisions.
> 
> Please send me and my friend Tim (copied above) some more
> information about the project.

Thank you, Joe and Tim, very much for your interest in the project. For 
the time being, we are still in a very early planning phase of the 
project, and currently we are mainly gathering information about 
suitable network topographies and protocols. We have not released any 
source code yet.

We do have a project wiki [2] on our project home page [1], where we 
have already discussed some ideas. But unfortunately, some of the ideas 
are already out-of-date.

Our first plan was to use an unstructured peer-to-peer network, where 
the index is simply distributed among all peers in the network without 
specific structure. To find all entries in the index for a given search 
phrase, a broadcast (TTL-flooding) of the query to all peers would be 
necessary, which is basically the search algorithm used by the Gnutella 
network.

After some discussions with Michael Christen, who has initiated a 
similar project [3] (distributed indexing, but no web crawling, only 
using transparent proxies for indexing), it became clear that this 
approach is not scalable enough for large networks, also see this paper 
[6] for information about the scalability issues of the Gnutella network.

In the meantime, we have realized that we need a structure peer-to-peer 
network for our needs, as only structured peer-to-peer networks provide 
scalability. A structured peer-to-peer network is basically a 
content-addressable network (CAN), i.e. given a search phrase, one can, 
through some simple calculations (mainly hash functions), determine on 
which peer the requested information is stored. This concept is also 
known as a distributed hash table (DHT), as it basically provides the 
actions

   - get(key)
   - put(key, value)
   - delete(key)

in a distributed manner. With the help of such a DHT, we can quickly map 
search phrases to peers in the network. But there still remain open 
problems:

   - How do we cope with the high volatility of peers in the network,
     with peers entering and leaving the network at any time.

   - How does our protocol provide sufficient load-balancing. Certain
     key phrases will surely be queried more frequently than others.
     Taking into consideration that Google answers 200 million query per
     day, a single peer might not be able to handle

   - How to take the underlying Internet topography into account. One of
     the main problems of current P2P networks implementations deployed
     is their disregard for the underlying Internet topology. Most P2P
     networks form an overlay network on top of the Internet at
     application level, providing their own routing algorithms. The main
     problem is that neighborhoods in the network graph of the overlay
     network are often no neighborhoods in the network graph of the
     Internet, thus resulting in high latencies and high cost due to
     excessive peering between different networks. We should take this
     into account in the design of our networks, although he will need
     a trade-off between this problem and the scalability and stability
     of the network.

We would be very glad if you would like to join our project. As you can 
see, this is not a project we can start to code quickly, as we first 
still have to do some kind of research to work out suitable protocols 
and algorithms for our needs. Interesting material about peer-to-peer 
networks and P2P network protocols can be found in the proceedings of 
the IPTPS 2002 [4] and 2003 [5] and following the citations in these 
papers. Nearly all of these papers can be found on Citeseer. Another 
interesting paper about the feasibility of P2P search engines, which 
shows the problems to be overcome, is [7].

Please feel free to join our gnugle-developers mailing list.

Best regards,
   Marco

[1] http://gnugle.sourceforge.net
[2] http://www.marcolange.de/gnugle/gnugle-wiki/
[3] http://www.anomic.de/AnomicHTTPProxy/index.html
[4] http://www.cs.rice.edu/Conferences/IPTPS02/
[5] http://iptps03.cs.berkeley.edu/program.html
[6] http://www.cs.rice.edu/Conferences/IPTPS02/165.pdf
[7] http://iptps03.cs.berkeley.edu/final-papers/search_feasibility.ps