Gnutella Forums - Appendix: Estimating Horizon Size

Gnutella Forums (https://www.gnutellaforums.com/)

- General Gnutella / Gnutella Network Discussion (https://www.gnutellaforums.com/general-gnutella-gnutella-network-discussion/)

- - Appendix: Estimating Horizon Size (https://www.gnutellaforums.com/general-gnutella-gnutella-network-discussion/1791-appendix-estimating-horizon-size.html)

Appendix: Estimating Horizon Size

[/QUOTE]The best approach is to introduce one or two messages solely for the purpose of communicating horizon size. Assume for simplicity that the Gnutella network is a tree, i.e., there is only one path between any two hosts. A key observation is that the number of hosts reachable from some host with TTL N is the sum of the number of hosts reachable from all its neighbors with TTL N-1. For formally, let H[A, n, B] be the number of hosts within n hops of host A that are reachable through B. Let H’[A, n, B] be the number of hosts within n hops of host A that are not reachable through B. Then for any host A with neighbors N1...Nm,

H[A, n, Ni]=1+H’[Ni, n-1, A]

H’[A, n, Ni]=H[A, n, N1]+…+H[A, n, N(i-1)+H[A, n, N(i+1)]+…+H[A, n, Nm]

H’[A, 0, Ni]=0

Horizon estimation now works through a sort of dynamic programming algorithm. Each host maintains the horizon size per connection, i.e., H[A, n, Ni] for all n and i. Every few seconds or so, hosts calculate their H’ tables from these values, exchange them with neighbors, and use these values to update their H tables. The total horizon size reported to the user is the sum over all i of H[A, n, Ni]. This scheme is accurate, efficient, and uses almost no bandwidth.[/QUOTE]

I would like for someone to explain those equations. I dont see what they represent as in if I plugged in values for the variables how I would work it out to get an answer. ???

I what to know it too.

Or at least give some more reference. Thanks.

Re: I what to know it too.

Quote:

Originally posted by peng
Or at least give some more reference. Thanks.

That 'quote' was from LimeWire's web site.

Re: Appendix: Estimating Horizon Size

Why don't you try BearShare, which calculates the horizon for you?

So I thought I might try and give my interpretation of the equations you posted.

Which means it's time to break out the ascii art:

First off there is one assumsion in these equations that is very important: there is only one route to a host.

Code:

A ---> N1 ---> O1

If there is more than one route to a host this won't work.

Code:

    --> N1 -

A--|       |--> O1

    --> N2 -

So a situation is descibed where a host A is connected to a number of hosts. I'm just going to say two for simpicity, but this should be scalible. Each of these hosts is connected to a number of hosts and so on a so forth. I'm going to diagram 2 hops here, but again this is scaleble.

Code:

0 hop  1 hop   2 hops

           |--- O1

   --- N1--|

   |       |--- O2

A--|

   |       |--- O3

   --- N2--|--- O4

           |--- O5

The first part of the first equation states H[A,n,N1] or the number of hosts accessable to host A within n hops through host N1. In the example I've given we could write it:

H[A,2,N1] = 3

So, A can access three computers through N1: O1,O2 and N1.

This is equal to the number of hosts N1 can access in n-1 hops not reachable through A plus 1. Or, H'[N1,n-1,A] + 1. In our spacific case H'[N1,1,A] +1.

Redrawing the diagram from N1's point of view:

Code:

0 hop   1 hop

    |-- O1

N1--|-- O2

    |-- A

As we can see N1 can access 3 computers within 1 hop, but only 2 are not reachable through A. H'[N1,1,A] = 2. If we add 1 we get three which is the number of hosts A could access through N1:

Code:

H[A,2,N1] = H'[N1,1,A] + 1

    3     =    2       + 1

The second equation says that the number of hosts with in n hops of A not accessable through the host N1 is equal to the number of hosts within n hops of A accessable though the other hosts its connected to.

From the above diagram we can see that A is connected to a total of 7 hosts, 3 through N1 and 4 through N2.

The last equation says that if you go 0 hops you're not connected to anything. Go figure.

Anyway, I hope this helped out some. If there is still something confusing in my explination, post and I'll try and clear it up. Sorry for anything that is confusing or misspelled.

those equations are really just a rough guess.

I always wanted some better data, so I started a little project. Though of it after seeing the stat page that Gnucleus nodes send out when a web browser tries to connect. Pretty cool, You can use a spider to "surf" the gnutella network. Only works with gnucleus and shareaza, but check it out if you want.

gnuMap project:
http://home.attbi.com/~gregory.bray/