tsafa1
December 15th, 2004, 01:18 PM
The following was posted by Gwren in the Mute forum. I will copy and paste here. As you read this please keep in mind that English is not Gwrens primary language. Also please be forwarned that this is not light reading. At times this my get very detailed:
The attached mail shows some ideas I was working on in these days... I'm
testing right now a particular client of Ants that uses the same
protocol of the beta0.7.7 but that can perform a random walk over the
net in order to get nearer and nearer to the sources of its downloads.
Obiously no information exchange happends between nodes, cuz this would
harm privacy. The new client just keep track of which nodes are not
actually useful for download or upload purpose. In practice if you have
some neighbours that only perform routing, that is you are not uploading
your stuff or downloading something through them, those nodes will be
disconnected. This doesn't happend for all your neighbours, cause it
would let some evil node be sure that you are the actual uploader of
something, so only uder certain conditions the disconnection will be
performed, that is only if more than half of your total nodes are not
active, one (randomly) will be disconnected so that the random walk can
take place.
----------------------------------------------------------------
Attached mail from Springfield@itsHackney.com
-----------------------------------------------------------------
An idea on how to optimise ANts routing to increase network capacity
without changing ANts protocol but only improving node discovery by
using pheromones.
What do you think?
--------------------------------------------------------------------------------
Increasing Ants Network Capaicty by Reducing Number of Hops Using Pheromones
The connection speed (bandwidth) of a node should not be used to
determine if that node should be connected to. Instead only a
historical record of whether that node has provided or forwarded that
user’s content should be used. As the objective of a node is to file
share (upload or download content) NOT to proxy.
Una rete Multi-hop Ad-Hoc anonima e sicura
The idea for the Ants algorithms is taken from the way in which the ants
behave when searching for food.
Ants first move directly towards the food, but if an obstacle is in the
way between them and the food then they change direction, typically in
an accidental way.
While they move they leave a pheromone trails in their wake.
The concentration of pheromone along a particular trail indicates how
often it was used; in time the pheromone concentration decreases on a
trail if it is not used.
The shortest route to food is used more often, as it takes less time, so
has a stronger concentration of pheromones.
Ants prefer trails with high pheromone concentration so naturally
eventually most will use the shortest route.
Una rete Multi-hop Ad-Hoc anonima e sicura covers:
Route Discovery
Route Maintenance
Route Failure Handling
Una rete Multi-hop Ad-Hoc anonima e sicura does not cover:
Ad-Hoc Overlay Network Capacity
Ad-Hoc Overlay Network Topology
Node discovery
Ad-Hoc Overlay Network Capacity
In the Ants P2P Ad-Hoc Network bandwidth is the scarce resource. It
must be conserved or the network capacity is adversely affected.
Bandwidth is consumed for every hop on network path between two
communicating nodes. To increase capacity the number of hops has to be
reduced.
Say a network has two nodes i and j with bandwidth Bi and Bj then the
available bandwidth is the lower of Bi and Bj.
Say a network has three nodes i, j and k each with same bandwidth B then
the available bandwidth for a proxy connection (two hops) per node: 1/2 x B.
If the minimum optimal path* length is L (number of hops) and number of
nodes is N:
Then for large N see (http://polymer.bu.edu/hes/articles/bbschs04.pdf):
In a random network L scales as N^(1/3)
In a “small world” network L scales as log N
*some paths are direct not proxy
So the capacity for:
A random network scales B/N^(1/3)
A “small world” network scales B/(log N)
Looking at example below it can be seen that network topography does not
significantly affect capacity scaling except when the number of nodes is
large (greater than a 100):
Hops (path length L)
Capacity (B)
No. of Nodes(N)
Random
Small World
Random
Small World
5
1.7
0.7
0.585
1.431
10
2.2
1.0
0.464
1.000
20
2.7
1.3
0.368
0.769
30
3.1
1.5
0.322
0.677
40
3.4
1.6
0.292
0.624
50
3.7
1.7
0.271
0.589
100
4.6
2.0
0.215
0.500
200
5.8
2.3
0.171
0.435
500
7.9
2.7
0.126
0.371
1,000
10.0
3.0
0.100
0.333
1,000,000
100.0
6.0
0.010
0.167
Ad-Hoc Overlay Network Topology
From the above it can be seen that clustering nodes, for example by
connection speed, without taking into account likelihood of file sharing
only marginally increases network capacity for N less than 100.
To increase network capacity the number of hops between file sharing
nodes must be significantly reduced.
This can be done by ensuring that nodes that have a high probability of
sharing content are close together in the network.
ANts needs to use pheromones to discover nodes as well as to discover
routes.
ANts needs to separately record pheromone (content proximity pheromone)
on node IPs when the user’s content is successfully sent or received as
well as when another node’s content is successfully proxied (route
pheromone).
This node IP “content proximity pheromone” needs to be saved between
ANts’ file sharing sessions.
Node IPs that have successfully proxied the user’s content to or from
the user’s node will have a much higher concentration of “content
proximity pheromone”.
Like route pheromone, “content proximity pheromone” should have a TTL
(Time To Live) that decreases as ANts runs.
Users should be more likely to connect to node IPs that have a
historically high concentration of “content proximity pheromone” as
recorded in that user’s records.
The resulting network topology would cluster nodes that are likely to
file share together so dramatically reducing number of hops and so
increasing network capacity.
The average number of hops will never be one (except in very small
network) and so some content will always be proxied.
Also Ants’ ID still will not be able to be linked to IP.
Therefore network will still be anonymous (retain deniability).
Node discovery
The connection speed (bandwidth) of a node should not be used to
determine if that node should be connected to. Instead only historical
record of “content proximity pheromone” should be used as the objective
of the node is to file share (upload or download content).
So slow nodes that historically have proxied the user’s content to and
from their node are better to connect to, than fast nodes that have only
proxied content for other nodes.
The probability of connecting to a node should be weighted by the
“content proximity pheromone”.
The majority of a node’s neighbours will then be nodes that are near
desired content or users wanting that user’s content. However, some
will be random nodes as probability is used. The resulting network
topology will be similar to a “small world” or “power law” topology
(content clusters with a small number of random non content related links).
The “content proximity pheromone” with TTL should also be used to
determine if a neighbour should be disconnected.
Neighbours which do not proxy content to or from a user due to lack of
bandwidth should be disconnected when the “content proximity pheromone”
falls to zero.
NMAX can still be used in node discovery.
Faster connections can have a higher number of neighbours as they have
the capacity to proxy more content to or from neighbours.
Slower connections have less capacity so would only be able to support
fewer nodes.
The ability of a node to upload and download would therefore increase as
the speed of the node increase.
Note, as a node cannot determine if data is own or network traffic prior
to the receipt of the data, the users selfish intention to connect to
other nodes that produce most own traffic benefits the network as a whole.
The attached mail shows some ideas I was working on in these days... I'm
testing right now a particular client of Ants that uses the same
protocol of the beta0.7.7 but that can perform a random walk over the
net in order to get nearer and nearer to the sources of its downloads.
Obiously no information exchange happends between nodes, cuz this would
harm privacy. The new client just keep track of which nodes are not
actually useful for download or upload purpose. In practice if you have
some neighbours that only perform routing, that is you are not uploading
your stuff or downloading something through them, those nodes will be
disconnected. This doesn't happend for all your neighbours, cause it
would let some evil node be sure that you are the actual uploader of
something, so only uder certain conditions the disconnection will be
performed, that is only if more than half of your total nodes are not
active, one (randomly) will be disconnected so that the random walk can
take place.
----------------------------------------------------------------
Attached mail from Springfield@itsHackney.com
-----------------------------------------------------------------
An idea on how to optimise ANts routing to increase network capacity
without changing ANts protocol but only improving node discovery by
using pheromones.
What do you think?
--------------------------------------------------------------------------------
Increasing Ants Network Capaicty by Reducing Number of Hops Using Pheromones
The connection speed (bandwidth) of a node should not be used to
determine if that node should be connected to. Instead only a
historical record of whether that node has provided or forwarded that
user’s content should be used. As the objective of a node is to file
share (upload or download content) NOT to proxy.
Una rete Multi-hop Ad-Hoc anonima e sicura
The idea for the Ants algorithms is taken from the way in which the ants
behave when searching for food.
Ants first move directly towards the food, but if an obstacle is in the
way between them and the food then they change direction, typically in
an accidental way.
While they move they leave a pheromone trails in their wake.
The concentration of pheromone along a particular trail indicates how
often it was used; in time the pheromone concentration decreases on a
trail if it is not used.
The shortest route to food is used more often, as it takes less time, so
has a stronger concentration of pheromones.
Ants prefer trails with high pheromone concentration so naturally
eventually most will use the shortest route.
Una rete Multi-hop Ad-Hoc anonima e sicura covers:
Route Discovery
Route Maintenance
Route Failure Handling
Una rete Multi-hop Ad-Hoc anonima e sicura does not cover:
Ad-Hoc Overlay Network Capacity
Ad-Hoc Overlay Network Topology
Node discovery
Ad-Hoc Overlay Network Capacity
In the Ants P2P Ad-Hoc Network bandwidth is the scarce resource. It
must be conserved or the network capacity is adversely affected.
Bandwidth is consumed for every hop on network path between two
communicating nodes. To increase capacity the number of hops has to be
reduced.
Say a network has two nodes i and j with bandwidth Bi and Bj then the
available bandwidth is the lower of Bi and Bj.
Say a network has three nodes i, j and k each with same bandwidth B then
the available bandwidth for a proxy connection (two hops) per node: 1/2 x B.
If the minimum optimal path* length is L (number of hops) and number of
nodes is N:
Then for large N see (http://polymer.bu.edu/hes/articles/bbschs04.pdf):
In a random network L scales as N^(1/3)
In a “small world” network L scales as log N
*some paths are direct not proxy
So the capacity for:
A random network scales B/N^(1/3)
A “small world” network scales B/(log N)
Looking at example below it can be seen that network topography does not
significantly affect capacity scaling except when the number of nodes is
large (greater than a 100):
Hops (path length L)
Capacity (B)
No. of Nodes(N)
Random
Small World
Random
Small World
5
1.7
0.7
0.585
1.431
10
2.2
1.0
0.464
1.000
20
2.7
1.3
0.368
0.769
30
3.1
1.5
0.322
0.677
40
3.4
1.6
0.292
0.624
50
3.7
1.7
0.271
0.589
100
4.6
2.0
0.215
0.500
200
5.8
2.3
0.171
0.435
500
7.9
2.7
0.126
0.371
1,000
10.0
3.0
0.100
0.333
1,000,000
100.0
6.0
0.010
0.167
Ad-Hoc Overlay Network Topology
From the above it can be seen that clustering nodes, for example by
connection speed, without taking into account likelihood of file sharing
only marginally increases network capacity for N less than 100.
To increase network capacity the number of hops between file sharing
nodes must be significantly reduced.
This can be done by ensuring that nodes that have a high probability of
sharing content are close together in the network.
ANts needs to use pheromones to discover nodes as well as to discover
routes.
ANts needs to separately record pheromone (content proximity pheromone)
on node IPs when the user’s content is successfully sent or received as
well as when another node’s content is successfully proxied (route
pheromone).
This node IP “content proximity pheromone” needs to be saved between
ANts’ file sharing sessions.
Node IPs that have successfully proxied the user’s content to or from
the user’s node will have a much higher concentration of “content
proximity pheromone”.
Like route pheromone, “content proximity pheromone” should have a TTL
(Time To Live) that decreases as ANts runs.
Users should be more likely to connect to node IPs that have a
historically high concentration of “content proximity pheromone” as
recorded in that user’s records.
The resulting network topology would cluster nodes that are likely to
file share together so dramatically reducing number of hops and so
increasing network capacity.
The average number of hops will never be one (except in very small
network) and so some content will always be proxied.
Also Ants’ ID still will not be able to be linked to IP.
Therefore network will still be anonymous (retain deniability).
Node discovery
The connection speed (bandwidth) of a node should not be used to
determine if that node should be connected to. Instead only historical
record of “content proximity pheromone” should be used as the objective
of the node is to file share (upload or download content).
So slow nodes that historically have proxied the user’s content to and
from their node are better to connect to, than fast nodes that have only
proxied content for other nodes.
The probability of connecting to a node should be weighted by the
“content proximity pheromone”.
The majority of a node’s neighbours will then be nodes that are near
desired content or users wanting that user’s content. However, some
will be random nodes as probability is used. The resulting network
topology will be similar to a “small world” or “power law” topology
(content clusters with a small number of random non content related links).
The “content proximity pheromone” with TTL should also be used to
determine if a neighbour should be disconnected.
Neighbours which do not proxy content to or from a user due to lack of
bandwidth should be disconnected when the “content proximity pheromone”
falls to zero.
NMAX can still be used in node discovery.
Faster connections can have a higher number of neighbours as they have
the capacity to proxy more content to or from neighbours.
Slower connections have less capacity so would only be able to support
fewer nodes.
The ability of a node to upload and download would therefore increase as
the speed of the node increase.
Note, as a node cannot determine if data is own or network traffic prior
to the receipt of the data, the users selfish intention to connect to
other nodes that produce most own traffic benefits the network as a whole.