Monday, March 26, 2007

How to Make Ants P2P Scalable (Bigger)

Often Ants users have said, "It would be nice to have the option to be able to connect to both the general ants and your variation simultaneously. This way we don't dilute the ants between two separate networks."

I agree that it would be nice to connect to the general Ants network and the "Ants network Mod" at the same time.

However, this would defeat to objective which is to make it possible for ANts to have networks bigger than 60.

When 60 users connect together in ANts, the average path lengths become very long and so uploads and downloads grind to a HALT.

Jon Kleinberg has proved why this happens. It is due to the fact that although large random networks have very short path lengths they CANNOT be navigated (one user cannot find a path to a next user).

Jon Kleinberg has also proved that small world networks have short path lengths and ALSO can be navigated.

So if ANts was a small world network rather than a random network it would scale beyond 60.

So how do you make a small world network?

With great difficulty except for the fact that humans generally form small world networks in their social interactions.

Hence, kerjodando and, people join ANts network according to their interests or friendships. And as each user can be a member of 2 meetups (swarms) then ONE LARGE NETWORK is formed with short path lengths between most users and long path lengths between a minority of users, a small world network.

Then the ANts network is scalable, it can grow to as big as any other 2nd en network without reducing the upload and download speed of users.


Saturday, July 01, 2006

Only Small World P2P Network Navigation (Search) Scalable

Only small world networks are scalable i.e. can grow in size without becoming very inefficient.

A small world network, where nodes represent people and edges connect people that know each other, captures the small world phenomenon of strangers being linked by a mutual acquaintance.

The small world phenomenon (also known as the small world effect) is the hypothesis that everyone in the world can be reached through a short chain of social acquaintances. The concept gave rise to the famous phrase six degrees of separation after a 1967 small world experiment by social psychologist Stanley Milgram which suggested that two random US citizens were connected on average by a chain of six acquaintances.

This has far reaching consequences for 'anonymous' P2P file sharing. A leading researcher on small world networks, Jon Kleinberg, states the following:

Moreover, α=2 is the only exponent at which any decentralized algorithm can achieve a delivery time bounded by any polynomial in logN: for every other exponent, an asymptotically much larger delivery time is required, regardless of the algorithm employed.

Jon Kleinberg

Lets take this phrase by phrase to see what does this actually mean for anonymous file sharing clients like ANts P2P, MUTE and Freenet.

  • α=2 is the only exponent at which any decentralized algorithm can achieve a delivery time bounded by any polynomial in logN.

  • logN refers to the width of a network.

  • As the number of users (N) increases, the average number of hops between any two users, the width, increases by a factor of logN.

  • However, it is expected delivery time (T) for messages sent between users that is important for file sharing.

  • T increases by a factor of logN only for small world networks (α=2). For other networks T is very much larger.

  • T for a ad-hoc overlay p2p net (like ANts, MUTE or Freenet) is the number of users a file or query has to be forwarded via to reach its destination, the path length (L).

  • For a small network the path length is small so that a workable amount of bandwidth in total is used in uploading and downloading for each hop along path length.

  • For a large network L is far too large unless the network is small world although ironically the width of the network still scales by logN.
  • for every other exponent, an asymptotically much larger delivery time is required, regardless of the algorithm employed.

  • So you can come up with whatever clever message routing method you like, it will not scale unless it is small world.

  • It is the network structure, the topology not the routing algorithm that determines if a network scales.

  • So neither ANts P2P or MUTE will scale by improving routing algorithms while they remain networks with a random topology(structure).

  • However, Iain Clark of Freenet seems to have already made this break through and has redesigned Freenet 0.7 to be small world.

I have decided to do the same for ANts p2p file sharing by making a very simple mod that will force the network to be small world.

kerjodando, the name of my ANts p2p mod, will force users to connect to only friends or others that share a similar interest to themselves, a p2p small world social network.

I call these groups, swarms and they are controlled, like bit torrent, by a simple tracker. Users can be members of many swarms covering all their interests and social networks. Swarms can either be private (invitation only) or public.

In this way kerjodando will be more scalable and be able to grow much bigger.

I hope this make sense.

But as you can see ANts has to change if is going to get bigger rather than gradually die.