Go to Google Home
A data-code-compute resource for research and education in information visualization
InfoVis Home Learning Modules Software Databases Compute Resources References

Software > Content-Addressable Network Model

Description | Pros and Cons | Applications | Details | Usage Hints | References | Acknowledgments


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.

CAN Network Model

Search in a CAN graph

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.


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.


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.



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