Gnutella Forums - View Single Post

FuzzeX · #5 (**permalink**) December 8th, 2002

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.