=?iso-8859-1?q?Some=20Guy?= <[EMAIL PROTECTED]> writes: >Consider Really Stupid Routing (RSR), where each >request or insert is forwarded to some random >neighbor. > >Assuming all y nodes cache data on insertion. We can >caculate the chance of a single request returning data >from a single insert: >x = HTL insert >y = HTL request >N = number >chance one not one particular node =(N-x)/N >c = chance request is found = 1-( (N-x)/N)^y
Actually, it's a bit more complicated than that, because there isn't an equal probability for any node to get the request. The request can only be forwarded to one of your neighbors. Since some nodes have a lot more neighbors than others, they have a higher probability of getting the request. In fact the request will tend to return to the highly-connected nodes again and again. You can imagine that if you went to the airport and started getting on random planes, you would have a lot higher chance of passing through O'Hare than some dinky airstrip in the middle of nowhere. The HP labs guys wrote a paper on this: L.A. Adamic, R.M. Lukose, A.R. Puniyani, and B.A. Huberman, "Search in power-law networks," Physical Review E, Volume 64, 046135 (2001). For a lot of reasons, it would be nice to know what the size N of Freenet is... theo -- Theodore Hong Dept. of Computing, Imperial College London [EMAIL PROTECTED] 180 Queen's Gate, London SW7 2BZ PGP key: http://www.doc.ic.ac.uk/~twh1/ _______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
