E-Chord: An implementation of Chord

E-Chord is an implementation of the Chord protocol. Specifically, we implement the version of Chord that utilizes stabilization routines.

We refer to this version of Chord as asynchronous, as opposed to the synchronous version. This is because, as described in the previous discussion, this version of the protocol allows a node to join and slowly build its pointers, as opposed to immediately blocking the network until all pointers can be updated.

Seed server

E-Chord uses a seed server to keep track of nodes in the network. This serves a few purposes. Mainly, a node asks the seed server for the address of another in order to join the network. Without the seed server, this would only be possible by using a fixed address for some node, which would likely be infeasible in most systems.

Additionally, after a massive node failure, if a node is unable to locate any others through its pointers, it will ask the seed server for the address of a node in order to re-join the network. In practice, due to the types of pointers an E-Chord node holds, this situation is statistically impossible.

Finally, the seed server can be used by an outside client to learn the address of some node, in order to then perform a query.

It might seem like using a seed server makes the network less decentralized. However, this is not the case. The seed server's only job is providing initial contact information for the network. Beyond that, it does not affect network operation at all, nor is it required for any purpose. In fact, after a network is running, the seed server can be shut down. Of course, this means that new nodes won't be able to join the network, but the network itself will continue regular operation.

Routing data

The routing information kept by E-Chord nodes includes the main types of information described by the Chord protocol. Specifically, each node keeps a finger table of size r, where r is the number of bits of IDs in the ring. Each node also keeps its predecessor.

Additionally, instead of just a single successor pointer, each node keeps a successor list of size r. This is done so, if a massive node failure occurs, it is highly unlikely that some node will be cut off from the network completely.

All of this data is kept up to date by stabilization routines.

Stabilization

An E-Chord stabilize event is made up of three parts: stabilize, fix_successor_list and fix_fingers. All of these take into account various edge cases where pointers might point to dead nodes. Here, we'll only describe their basic function, while ignoring these details.

The first part, stabilize, works as described by the Chord protocol. A node asks its successor for its predecessor and updates its own successor accordingly.

The second part, fix_successor_list, uses a custom algorithm created for this purpose. The algorithm keeps the successor list, as well as a current index on the list. A description of the algorithm follows.

  1. If successor list empty or index<0, ask successor for successor; if successor dead, end; if successor alive, place response at start of list (override or append); if index<0, index=0; end
  2. Else, ask current index node in successor list for successor
  3. If alive and last in list and list is full, index=-1; end
  4. If alive and last in list and list not full, append new successor; index+=1; end
  5. If alive and not last in list, verify next; if same, index+=1; end; else if different, override next; index+=1; end
  6. If dead, remove node from successor list; index-=1; end

This algorithm ensures that the successor list remains up to date. It also serves to build an empty successor list, meaning that new nodes can simply initialize their successor list to empty.

Finally, fix_fingers picks a random finger from the finger table and updates it. It does this by searching for the successor of the key n + 2i, where i is the index of the finger, and using that as the new finger.

Local simulation

E-Chord comes with scripts that allow users to simulate an E-Chord network on a single machine. We refer to a network created in such a manner as a simulation.

Besides the fact that the network is running on a single computer, there isn't much difference in the function of a simulated network. When a node is started on a computer, it creates a process that runs this node. Through the local network, this process communicates with other nodes and thus makes up the DHT.

When executing the scripts, multiple such processes are started on the same computer. They all use the IP address localhost, while they listen on different ports.

The visualizer script itself could be modified, so that it works for actual E-Chord networks. To do this, one would simply have to provide it with a list of addresses of existing nodes that it can make requests to. As it now stands, the visualizer makes requests to nodes with localhost IP addresses that use ports in the range defined by the testing parameters.