Hornet
October 9th, 2005, 07:04 AM
To make Ants P2P faster, use less bandwidth and be more scalable it needs to be a small world network.
Freenet has published a method to determine if a network is small world. It involves giving each node a circle number using the Kleinberg algorithm. A node can then test if it is in small world network by comparing its circle number with that of its neighbors. If it is not then it can make new connections and retest.
This should lead to nodes being fewer hops apart without affecting anonymity.
See below for application of Kleinberg algorithm to Ants P2P taken from Freenet Las Vagas Paper (http://www.math.chalmers.se/~ossa/defcon13/vegas1_print.pdf).
From Freenet Paper
Overview of “Peer to Peer” networks
• Information is spread across many interconnected computers
• Users want to find information
• Some are centralized (e.g. Napster), some are semi- centralized (e.g. Kazaa), others are distributed (e.g. Ants p2p)
The Small World Phenomenon
• In "Small world" networks short paths exist between any two peers
• People tend to form this type of network (as shown by Milgram experiment)
• Short paths may exist but they may not be easy to find
Navigable Small World Networks
• Concept of similarity or “closeness” between peers
• Similar peers are more likely to be connected than dissimilar peers
• You can get from any one peer to any other simply by routing to the closest peer at each step
• This is called “Greedy Routing”
• Ants P2P and “Distributed Hash Tables” rely on this principal to find data in a scalable decentralized manner
Dark or “Friend to Friend” P2P
Networks
• Possible for peers only communicate directly with “trusted” peers
• Examples: Waste and Ants P2P (node connected to trusted peers only)
• Advantage: Possible for only your trusted friends to know you are part of the network (if in Ants you don’t use IRC or web cache and use only trusted peers)
• Disadvantage: Networks are disconnected and small, they typically don’t scale well
Application
How can we apply small world theory to routing in a Dark peer to peer network like Ants p2p?
• A Darknet is, essentially, a social network of peoples trusted relationships.
• If people can route in a social network, then it should be possible for computers.
• Jon Kleinberg explained in 2000 how small world networks can be navigable.
Kleinberg’s Result
• The possibility of routing efficiently depends on the proportion of connections that have different lengths with respect to the “position” of the nodes (In other words to get from start node to destination node efficiently you need the majority of nodes to be directly linked, clustered and a minority to be not directly linked with several hops separating start and destination nodes. http://img220.imageshack.us/img220/5099/image0026yd.jpg
• If the positions are in a ring (in other words you imagine the nodes placed in a ring with their arrangement corresponding to how close they are to each other in terms of hops), the proportion of connections with a certain length should be inverse to the length (In other words most connections will be short between nodes near to each other on circle. Fewer connections will span circle to connect distant nodes. High number of hops few connections, small number of hops or directly connected a lot of connections):
• In this case a simple greedy routing algorithm performs in O(log2 n) steps (In other words this is scalable).
http://img220.imageshack.us/img220/9718/image0040ov.jpg
But in a social network, how do we see if one person is closer to the destination than another?
Is Alice closer to Harry than Bob?
• In real life, people presumably use a large number of factors to decide this. Where do they live? What are their jobs? What are their interests?
• One cannot, in practice, expect a computer to route based on such things.
• Instead, we let the network tell us! (In other words use Ants P2P routing method to route over a scalable small world net)
• Kleinberg’s model suggests: there should be few long connections, and many short ones. (So using the model a node can detect if it is in a small world net and then make or break connections to optimize that net.)
• We can assign numerical identities placing nodes in a circle, and do it in such a way that this is fulfilled. (In other words a network of nodes can be represented by nodes arranged in a circle with each nodes position dependant on minimizing overall the length of connections (Chords).
• Then greedy route with respect to these numerical identities. (Or form new connections so that most lengths (chords) small and a few long to make net scalable small world net that Ants P2P can route over.)
The Method (to place nodes on circle such that their position on circle reflects how closely connected they are to other nodes.)
• When nodes join the network, they choose a position on the circle randomly.
• They then switch positions with other nodes, so as to minimize the product of the edge distances (in total for the imaginary circle).
An advantageous switch of position (on imaginary circle):
http://img220.imageshack.us/img220/4273/image0069px.jpg
Some notes:
• Switching is essential!
• Because this is an ongoing process as the network grows (and shrinks) it will be difficult to keep permanent positions.
The Algorithm
• Two nodes are chosen in some random fashion, and attempt to switch.
• They calculate Lb as the product of all the lengths of their current connections. Then they calculate La as the product of what all their respective connection lengths would be after they switched.
• If Lb > La they switch. Otherwise they switch with probability Lb/La. (When they switch they get the circle number of the node they switch with. Their connections to other nodes don’t change. They just get a circle number that better reflects how close they are to other nodes.)
http://img379.imageshack.us/img379/9209/image0082ns.jpg
• This is an application of the Metropolis- Hastings algorithm.
• Because there is a greater chance of moving to positions with shorter connection distances, it will tend to minimize the product of the distances.
• Because the probability of making a switch is never zero, it cannot get stuck in a bad configuration (a local minima). (In other words once minimized using this algorithm the circle number of each node will give a measure of how close each node is to every other node. This algorithm does not change connections between nodes or the arrangement of the real network in any way. It only changes how the imaginary representation of the network is arranged.)
How do nodes choose each other to attempt to switch?
• Any method will work in theory, but some will work better than others. Only switching with neighbors does not seem to work in practice.
• Our current method is to do a short random walk starting at one of the nodes and terminating at the other.
Hornet :icon_rr:
Freenet has published a method to determine if a network is small world. It involves giving each node a circle number using the Kleinberg algorithm. A node can then test if it is in small world network by comparing its circle number with that of its neighbors. If it is not then it can make new connections and retest.
This should lead to nodes being fewer hops apart without affecting anonymity.
See below for application of Kleinberg algorithm to Ants P2P taken from Freenet Las Vagas Paper (http://www.math.chalmers.se/~ossa/defcon13/vegas1_print.pdf).
From Freenet Paper
Overview of “Peer to Peer” networks
• Information is spread across many interconnected computers
• Users want to find information
• Some are centralized (e.g. Napster), some are semi- centralized (e.g. Kazaa), others are distributed (e.g. Ants p2p)
The Small World Phenomenon
• In "Small world" networks short paths exist between any two peers
• People tend to form this type of network (as shown by Milgram experiment)
• Short paths may exist but they may not be easy to find
Navigable Small World Networks
• Concept of similarity or “closeness” between peers
• Similar peers are more likely to be connected than dissimilar peers
• You can get from any one peer to any other simply by routing to the closest peer at each step
• This is called “Greedy Routing”
• Ants P2P and “Distributed Hash Tables” rely on this principal to find data in a scalable decentralized manner
Dark or “Friend to Friend” P2P
Networks
• Possible for peers only communicate directly with “trusted” peers
• Examples: Waste and Ants P2P (node connected to trusted peers only)
• Advantage: Possible for only your trusted friends to know you are part of the network (if in Ants you don’t use IRC or web cache and use only trusted peers)
• Disadvantage: Networks are disconnected and small, they typically don’t scale well
Application
How can we apply small world theory to routing in a Dark peer to peer network like Ants p2p?
• A Darknet is, essentially, a social network of peoples trusted relationships.
• If people can route in a social network, then it should be possible for computers.
• Jon Kleinberg explained in 2000 how small world networks can be navigable.
Kleinberg’s Result
• The possibility of routing efficiently depends on the proportion of connections that have different lengths with respect to the “position” of the nodes (In other words to get from start node to destination node efficiently you need the majority of nodes to be directly linked, clustered and a minority to be not directly linked with several hops separating start and destination nodes. http://img220.imageshack.us/img220/5099/image0026yd.jpg
• If the positions are in a ring (in other words you imagine the nodes placed in a ring with their arrangement corresponding to how close they are to each other in terms of hops), the proportion of connections with a certain length should be inverse to the length (In other words most connections will be short between nodes near to each other on circle. Fewer connections will span circle to connect distant nodes. High number of hops few connections, small number of hops or directly connected a lot of connections):
• In this case a simple greedy routing algorithm performs in O(log2 n) steps (In other words this is scalable).
http://img220.imageshack.us/img220/9718/image0040ov.jpg
But in a social network, how do we see if one person is closer to the destination than another?
Is Alice closer to Harry than Bob?
• In real life, people presumably use a large number of factors to decide this. Where do they live? What are their jobs? What are their interests?
• One cannot, in practice, expect a computer to route based on such things.
• Instead, we let the network tell us! (In other words use Ants P2P routing method to route over a scalable small world net)
• Kleinberg’s model suggests: there should be few long connections, and many short ones. (So using the model a node can detect if it is in a small world net and then make or break connections to optimize that net.)
• We can assign numerical identities placing nodes in a circle, and do it in such a way that this is fulfilled. (In other words a network of nodes can be represented by nodes arranged in a circle with each nodes position dependant on minimizing overall the length of connections (Chords).
• Then greedy route with respect to these numerical identities. (Or form new connections so that most lengths (chords) small and a few long to make net scalable small world net that Ants P2P can route over.)
The Method (to place nodes on circle such that their position on circle reflects how closely connected they are to other nodes.)
• When nodes join the network, they choose a position on the circle randomly.
• They then switch positions with other nodes, so as to minimize the product of the edge distances (in total for the imaginary circle).
An advantageous switch of position (on imaginary circle):
http://img220.imageshack.us/img220/4273/image0069px.jpg
Some notes:
• Switching is essential!
• Because this is an ongoing process as the network grows (and shrinks) it will be difficult to keep permanent positions.
The Algorithm
• Two nodes are chosen in some random fashion, and attempt to switch.
• They calculate Lb as the product of all the lengths of their current connections. Then they calculate La as the product of what all their respective connection lengths would be after they switched.
• If Lb > La they switch. Otherwise they switch with probability Lb/La. (When they switch they get the circle number of the node they switch with. Their connections to other nodes don’t change. They just get a circle number that better reflects how close they are to other nodes.)
http://img379.imageshack.us/img379/9209/image0082ns.jpg
• This is an application of the Metropolis- Hastings algorithm.
• Because there is a greater chance of moving to positions with shorter connection distances, it will tend to minimize the product of the distances.
• Because the probability of making a switch is never zero, it cannot get stuck in a bad configuration (a local minima). (In other words once minimized using this algorithm the circle number of each node will give a measure of how close each node is to every other node. This algorithm does not change connections between nodes or the arrangement of the real network in any way. It only changes how the imaginary representation of the network is arranged.)
How do nodes choose each other to attempt to switch?
• Any method will work in theory, but some will work better than others. Only switching with neighbors does not seem to work in practice.
• Our current method is to do a short random walk starting at one of the nodes and terminating at the other.
Hornet :icon_rr: