Team members: Anirudh Subramanian (UFID:94453124), Divya Ramachandran (UFID:46761308)
A program written as part of Distributed Operating Systems course to implement the Pastry protocol and a simple object access service. Reference: Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems by Antony Rowstron and Peter Druschel
Input arguments are as follows: 1] numNodes : number of nodes forming the Pastry peer to peer network 2] numRequests : number of requests each peer has to make at the rate of 1 request/second
Example: 10000 5
Instructions {How to run}
Now from the Pastry-master folder do:
sbt publishLocal
commands(Make sure you are in Pastry-master folder)
Implementation Details:
Initialisation of the network involves creating actors with randomly generated unique nodeIds to simulate the real world
IDs generated by hashing the IP or public key of a node as explained in the paper. Initialisation involves setting up of
the leaf table and routing table by way of sending a message containing its own nodeId to the last generated node assuming
it to be the closest node (purely an assumption as there is no way to check proximity). Updation of tables of a node on a
join of a new node as well as routing a message to a specific node is implemented using the routing algorithm proposed
by the paper considering three different cases of the target nodeId lying within the range of the leafset, or some way via
a node in the routing table or a third case of finding any node in the tables that is numerically closeset to the target
nodeId. Once a new node's tables are populated, it is sent back to all the nodes contained in its tables in order for those
nodes to update their tables with the information of and from the new node.
Each message holds a hopnumber to keep track of the number of hops it is making to reach its destination to derive an
average number of hops per message metric. This metric illustrates the effectiveness of the algorithm to ensure that the
messages on an average take O(log N) steps in case of no recent failures.
=========================================================================================================================== Test Results and Analysis:
We observed that inititally as the tables are not well-populated, the message routing takes more hopes than the average expected. However, once all the tables are populated with entries of nodeIds the message routing occurs in very short steps.
When a new node is added and shares its routing table and leaf table with nodes in its routing and leaf table, the routing table of those nodes can be updated in two ways - in the event that an entry already exists - 1> between the original entry and the new node, the one with nodeId that is numerically closer to the node that owns the routing table is selected. In this case, any local message traversal will be very quick. This will benefit larger message transfers across the cluster as well, although it might take a number of hops. 2> between the original entry and the new node, the one with nodeId that is numerically away from the node that owns the routing table is selected. In this case, message transfers across the network will be quick. However, the number of hops will be less deterministic and messages being passed within small localised zones will end up needing a higher number of hops.
The effect of base value 'b' determines the number of bits that are change per row in the routing table. A lower value of 'b' will benefit in routing as the table contains more entries and make different parts of the network more accessible. However, this comes at the cost of memory per node as the routing table size increases. We can draw a similar argument when it comes to the size of the leaf set.