P2P Chord Sim.

This page is dedicated to my continuing P2P Chord Simulator that I am developing for my P2P Networking class here at the University of Iowa (Spring 2008).

The final Spring 2008 Research Paper can be found here in PDF format: Chord Network Simulation

Those of you who are interested in the current pre-beta source code, can find it here: Chord P2P Network Simulator (Pre-Beta)

The project objectives are as such:

  1. Implement a Chord network with a key space of size n=2^16 , and place 1024 nodes (machines) on the network.
  2. Name each machine with a string of three randomly chosen alphabets ‘a’-‘z’.
  3. Name 256 objects each with a string of three randomly chosen hex digits (0-F) and place them on the different machines.
  4. Allow 2*log2(n) nodes for each node to support bidirectional routing.
  5. Simulate the search object operation for 50 different accesses originating from random machines a few designated objects
  6. verify that the search indeed terminated at the host machine.
  7. Tabulate these operations and in each case, record the number of steps needed to perform the search.
  8. Simulate the addition and deletion operations of nodes.
  9. Run the stabilization protocol after every 10 addition and deletion operations, and record partial snapshots to verify that the new nodes were indeed correctly added and the departing nodes were flushed out of the system.

How Chord Works

The key to the Chord topology is the finger-table that each peer holds. The finger table consists of the information necessary to connect each peer to adjacent peers, along with the files that each peer is responsible. If all the nodes within the Chord network are filled, then the finger-table for Node 0 would be as follows, given the size of the network is 8:

[singlepic id=58 w= h= float=center]

Node 0 would be responsible for the files (keys) that map to Node 0.

If Node 2 were the only peer that did not exist within the network, then Node 0’s finger-table would look like this:

[singlepic id=59 w= h= float=center]

If the ending node (peer) is not available, the finger-table simple drops back, looking for the first network peer it can find.

[singlepic id=60 w= h= float=center]

Figure 1 – from “Chord: A scalable peer-to-peer lookup service for Internet applications”

Figure 1 exemplifies just how the Chord topology works around a network with missing peers. Nodes 0, 1 and 3 are the only available peers (with a network size of: n=8) and their associated finger-tables are shown above. In addition, the files (keys) currently available, map to Nodes 1, 2 and 6.

From this, we can see that the file, key=6, does not map to Node 6, since Node 6 does not exist within the network at this time; it is mapped to the first available node following Node 6. In this case, the file (key=6) maps to Node 0.

The Chord topology continually re-maps files along the Chord circle as peers continually join and leave the network. This is how the Chord method resolves the issue of ‘churn’ and makes the topology relatively robust.

Since each available file within the network is mapped to a particular node within the network, each search is in effect looking for the node that holds the particular file. So, if file “XYZ”, mapped to Node 15, then the search would return the value ‘Node 15’; leaving the search method to run clock-wise along the Chord circle (parsing through each successive nodes finger-table) until it landed upon Node 15 and finally returning the file “XYZ”.

This indicates that there is a hash function involved. How else would we be able to resolve the file “XYZ” and Node 15? By using specific information about the network; such as the peer’s IP address and the size of the network, we can hash each file in such a way that places certain files at particular nodes along the Chord circle. Of course, even if two files map to the same node, we won’t run into any problems as we can pass the particular file we are searching along with the search algorithm. If a peer chooses to lookup file “ABC”, which also maps to Node 15, we can use the file’s name as a way of parsing through the list of files that a particular node is holding; returning “ABC”, instead of the file, “XYZ”.

(April 3, 2008)

Been working on a DHT (dynamic hash table) for the Chord P2P Simulator. Chord typically uses a DHT to map files to certain peers within the Chord network. I’ve come up with the following snippet to see if it works:

public static BigInteger generateSHA1(String key, int keySize ) {
try {
MessageDigest md = MessageDigest.getInstance("SHA-1");
byte[] hashMsg = md.digest(key.toString().getBytes());
BigInteger bi = new BigInteger(hashMsg).abs();
BigInteger mod = new BigInteger( Integer.toString( keySize ) );
return bi.mod( mod );
} catch (Exception e) {
}
return null;
}

(Feb. 16, 2008)

A ‘back-of-the-envelope’ session has lead me to believe I’ll need the following classes:

  • Node(): must keep track of it’s FingerTable.
  • Network(): the Chord network itself. This will basically hold the an array of Nodes(), not to mention the necessary methods to add, delete and stabilize the nodes after nodes have been added and removed. Hooks will be needed to forward updated information the the nodes.
  • NetworkTest(): This is simply an instantiation of the Network() class. How much work this class will need is still up for debate.

I’m not sure what types of data structures I will use for the the particular variables within the classes. Arrays would be fine, but if I need to search them, the iterating through them all can prove to be a daunting task. Perhaps, I should look around for a good search algorithm built upon Java.

(Feb. 7, 2008)

Found a relatively painless port of the Java IDE, Eclipse, which is built specifically for Mac OSX. Installed just fine. Tested its compiling operation by using past classes I had built. Everything looks fine. My partner bailed out on me early in the semester after we had already decided upon this project. It’s a bit too late to go back now. I’m not sure if anyone else is working on this project. I’ll check around.