DHT based: Every node maintains a full routing table containing information about every other node in the overly. Node in the overlay is assigned an id. The id space forms a Chord ring. Every node sends keep-alive to its predecessor and successor. Use a hierarchy to form dissemination trees. Divide the 128-bit circular id space into k intervals called slices. Every slice has a slice leader. The slice is further divided into units, and each unit has a unit leader. When node detect a change it the membership, it sends an event to notify its slice leader. The slice leader collects all local events for some period sent it to other slice leaders. The slide leaders aggregate messages they received and dispatch the messages to all unit leasers of its slice. A unit leader sends this info on its keep-alive messages to its successor and predecessor. Other nodes propagate this information in one direction: if they receive info from their predecessors, they send it to their successors and vice versa.
Two hops lookup: For systems of larger size. Every slice leader chooses a group from its local node for each other slice leader. (if there are k slices, there are k-1 such groups). The slice leader sends each other slice leader the routing information of nodes in the group, instead of all node’s routing information. When a node sends a query, it sends a lookup request to its chosen node in the slice containing the key. The chosen node then examines its own routing table to identify the successor of the key and forward the request to that node.
How to choose the parameters, and cost analysis.
(Efficient Routing for Peer-to-peer overlays) (One Hop lookups for peer-to-peer overlays)
Unstructured: GUESS. A successor of Gnutella. Instead of keep a active neighbor list. Nodes don't maintain connections with other nodes. They maintain 2 caches: link cache and query cache. Nodes uses UDP send ping, and get reply Pong which has a list of links from replying node's cache. Then node can update its link cache accordingly. To send a query, nodes send probe query to nodes from its link cache and wait to see result then send next. To get enough result, node may need send probe query to a large number of nodes, while the size of the link cache could not be that large. Then use the query cache. When not send query probe, the replying node reply a query Pong, besides the query result. And node updates its query cache according to the query pong, then send query probe to nodes in the query cache. Many policies for: the order of query probing, cache update policies, etc.
(Evaluating GUESS and Non-forwarding Peer-to-Peer Search)
