Software > Content-Addressable Network Model
Description | Pros and Cons | Applications | Details | Usage Hints | References | Acknowledgments  Description |
The Content-Addressable Network (CAN) [1] is a framework for structured P2P
systems based on a virtual d-dimensional
Cartesian coordinate space on a d-torus. Nodes in a CAN graph
have as an attribute the coordinates of a subspace of this space that
are used in adding nodes and edges to the graph. Initially, the graph
consists of one node and no edges. This initial node is assigned
the entire virtual space. As nodes are added to the graph, they
are assigned a subspace in the virtual space from a uniform
distribution. So for a new node to join the CAN graph,
it must find a node already in the graph and then using the
routing mechanism, it should locate the node whose zone will
be split. The system self-organizes to adjust to a new node
by adding edges from the new node to adjacent nodes in the space.
A typical CAN network graph is given below.
Performing efficient decentralized search is a fundamental problem in Peer-to-Peer systems. An effective search facility that uses only local information is essential for their scalability and, ultimately, their success. It is suggested that there is a strong relationship between network topology and search algorithms.
Structured P2P Network models, like CAN, enforce strict constraints on network evolution and resource placement. The main advantage, therefore of CAN, is that the added constraints result in sub-linear search mechanisms. CAN has an associated native search mechanism that takes advantage of the added structure.
Search in a graph is defined as finding a path from a randomly chosen start node to a randomly chosen target node. The cost of a search is the number of edges traversed in locating the destination node (i.e. the number of "messages" sent in the network during the search process). Search in a CAN graph follows a straight line path from start to target through the virtual coordinate space. Since every node in a CAN graph is aware of its neighbor coordinate set, a node passes on the message to the neighbor with coordinates closest to that of target node. Thus, it utilizes pure local information to route messages through the virtual coordinate space.
| Pros & Cons |
Applicable to network graphs only. Since placement of system resources at nodes is strictly controlled in a centralized fashion, network evolution has costly overhead. Centralized control limits network robustness and node autonomy.
CAN model is advantageous for building systems where controlled resource placement is a high priority, such as distributed file storage. CAN model provides sub-linear search mechanisms.
| Applications |
These algorithms can be used to generate CAN structured P2P graphs. These graphs can then be visualized and analyzed using Pajek or any other network visualization program.
| Details |
Pseudo code for building CAN network model:
1. Add first node to the graph.
2. Choose a random position in the virtual coordinate space for new_node.
3. Add new_node to the graph.
4. Find the old_node that owns that position.
5. Split the region occupied by old_node along the longer axis and assign one
half to the new_node.
6. Fix the edges in the graph for both the old_node and new_node.
7. nodesAdded = nodesAdded + 1.
8. Repeat Step 2 if nodesAdded < desiredNetworkSize.
Pseudo code to search CAN network model:
define searchCanNetwork(Node fromNode, Node toNode, int count, boolean isFirst)
{
if (fromNode equals toNode)
print "Search successful. Search Cost = " + count
if (count equals networkSize)
print "Search failed."
visited[fromNode] := true
for each neighbor of fromNode
Find the distance of neighbors from fromNode
nextNode := closest neighbor of fromNode
searchCanNetwork(nextNode, toNode, count+1, false)
}
| Usage Hints |
In the IVC Software Framework, simply select Modeling > P2P > Structured > CAN to generate a network. Use Analysis > Search > CAN Search to analyze the network.
| References |
-
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. A scalable content-addressable network. Proc. ACM SIGCOMM 2001, pp. 161-172, August 2001.
| Acknowledgments |
This package was developed by George Fletcher and Hardik Sheth. Hardik Sheth integrated the code into the IVC Software Framework.
Information Visualization
Cyberinfrastructure @ SLIS,
Indiana University
Last Modified July 10th, 2004