Prefix Hash Tree Implementation for PeerSim as described in https://www.eecs.berkeley.edu/~sylvia/papers/pht.pdf
-
Linear lookup
a top-down traversal of the prefix tree (trie) which returns the the unique leaf node whose label is a prefix of the given key.
-
Binary lookup
Try different prefix lengths until the required leaf is reached. (not implemented due to problems with mspastry).
-
Insertion of a key with related split operation.
-
Deletion of a key with the related merge operation.
-
Sequential range query: return all keys in a range using the links between the leaves.
-
Parallel range query: return all keys in a range starting from the smallest common prefix node of the trie.
This Pht implementation can be used with any Distributed hash table as long as an interface is provided to enable communication between the concrete implementation of the Dht and Pht.
The peersim.pht.DhtInterface interface contains the three methods needed for an integration with a Dht:
void send(PhtMessage message, String dest)Send a message to another node of the trie using the Dht.Object getNodeId()Id of the current Node (PeerSim node: a physical machine). This id is set by the Dht, not PeerSim. This method is used for debug and logs rather than for real operations.Node getNode()Current node (PeerSim node). This method is needed for the beginning of the simulation. This information will be used to enable direct communications between PeerSim nodes, thus avoiding extra Dht routing.
PeerSim has additional packages, one of them being the MSPastry protocol. We provide some classes in the peersim.dht package to run simulations with this Dht.
The mspastry package seems to have a little bug, the protocol id variable is not initialized correctly: the value is still 0 when the simulation really starts, and the simulation crashes immediatly. To avoid this I added a little method in mspastry (quick fix): setMspastryId. I have sent an email to one of the authors of mspatry but I still have no response.
You will find five different parameters for the PhtProtocol in the configuration file:
- Key size (bits).
- Maximum amount of keys a leaf can have.
- Dht interface.
- Logs enabled. Possible values: "on" or anything else to disable this.
- Type of range query for the simulation ("seq" for sequential, everything else for parallel).
- Maximum delay (each message is virtually sent with a (very) pseudo-random delay)
- Retry factor (when a message has been stopped, retry the same operation with a Maximum delay * retry factor time)
- Route fail: continue or stop when a routing error has been detected (true: stop)
The mspastry package seems to have another problem: the routing part. The implementation does not allow replication, hence the network must be static. Lots of message with the same recipient should be received by only one Node, which does not always happen.
The PhtUtil class provides static methods to make some tests and check whether the whole Pht is correct (keys only in leaves, threaded leaves are correct, every inserted key is in the Pht, etc.).
At the end of any simulation, the phtStats() method is launched. It provides information
about:
- Number of keys in the Pht
- Number of nodes in the Pht
- Number of leaves in the requests
- Number of requests
- Number of leaves with more than B keys
- Pht height
- Minimum height
- Ten most used nodes
- Ten least used nodes
- Ten most loaded leaves
- Ten least loaded leaves
- Number of insertion, delete, query, range query operations
As PeerSim, this Pht implementation makes use of a Makefile. To compile, simply type
make. To run the simulation with the default configuration file, type make run. To clean the .class files, type make clean. To build the javadoc,
type make doc.