reines / oversim Goto Github PK
View Code? Open in Web Editor NEWOpen-source overlay and peer-to-peer network simulation framework for the OMNeT++ simulation environment
Open-source overlay and peer-to-peer network simulation framework for the OMNeT++ simulation environment
OverSim - A Flexible Overlay Network Simulation Framework OverSim is an open-source overlay network simulation framework for the OMNeT++/OMNEST simulation environment. The simulator contains several models for structured (e.g. Chord) and unstructured (e.g. GIA) peer-to-peer protocols. OverSim is developed at the Karlsruhe Institut of Technology (KIT), Institute of Telematics. Please look into the doc/ subdirectory where you'll find installation instructions, the license and the API documentation. If you need help, please visit the project website: http://www.oversim.org/ Disclaimer: OverSim is continuously being improved: new parts are added, bugs are corrected, and so on. We cannot assert that any protocol implemented here will work fully according to the specifications. YOU ARE RESPONSIBLE YOURSELF TO MAKE SURE THAT THE MODELS YOU USE IN YOUR SIMULATIONS WORK CORRECTLY, AND YOU'RE GETTING VALID RESULTS. The OverSim team
Maybe the resulting lookup rate is off?
Our Symmetric DHT implementation needs merged. It would be nice to do this in a more tidy way, but I'm not sure how possible that actually is...
When returning the best next hops we are meant to also return our direct successor/predecessor (depending on which side of us the query came from).
Internally expires should be stored as times, but for transmission we should calculate TTL = expire - simTime()
and send that (if > 0). When receiving values we should calculate expire = simTime() + TTL
, and store this in the cache.
The hop counts produced by EpiChord don't fit those in the original EpiChord paper, implying part of our implementation is incorrect - this needs fixed otherwise we cannot assume results generated are correct.
When plotting network size vs hop count the lines have a different gradient, with the hop count on our implementation deteriorating as the network size increases.
There are a few areas which come to mind:
The original implementation checks for false negative responses during a lookup and alerts nodes if they should re-check their neighbours, resulting in the low periodic neighbour update causing a slightly higher hop count but not affecting the success rate.
Probes in the original implementation seem to include:
They also seem to be triggered instantly when an update occurs, pushing that update to neighbours - instead of waiting for neighbours to request a refresh.
Compact probes should be used unless we know of any changes, in which case we send a full probe.
First we should check that message sizes are calculated and recorded correctly. We should then check that the bandwidth used matches that in the paper.
I think this is down to how nodes are sorted.
When merge = true nodes are sorted based on their distance from the destination key. This means potentially the closest node might be before the key, but the actual node we want to contact first is the one closest after the key - since data is stored at the successor.
When performing a lookup seem to include failed lookups when calculating both the accumulated and min hop counts. We should probably only calculate the min hops over successful lookups.
EpiChord states that findNode should return the immediate successor of the key, then p-1 predecessors. This results in a much worse success rate than p-1 successors, but should be done otherwise we aren't properly modelling EpiChord...
Example:
2b4c7f7f8fb4e726902528c4e2c8d3b89ee51af6467cef76117c9581c490995623e11fa7f7bd5821e1e7fff904835de7e3db0fff721f97b3a19392251ada4778 / 007fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff = 00000000000000002b4c7f7f8fb4e726bb71a844727dbadf5a56c33ab8faaa556bd358bc7d8b43ab8fb4786475489bcd719c785d79cbf9b55577885cebeb9168
The maintenance in the DHT depends on knowing which node is responsible for a key. This probably needs modified to work correctly with Symmetric and RepeatedHashing replicaiton.
When node lifetime estimation is enabled the estimates even after being multiplied by the modifier are generally higher than 60s, which cause a poor success rate.
In Chord nodes check their predecessor every 5s but only stabilize every 20s, and check fingers every 120s. Doing both stabilization and checking cache every 60s as suggested in the EpiChord paper seems rather odd.
When using active propagation the success rate actually drops. This needs fixed obviously.
The success rate of Chord and EpiChord is hurt quite badly by churn - worse than it should be I think.
With 600s lifetime mean Chord is seeing a lookup success rate of 40-50%. EpiChord is getting 80-90%. Does this imply the redundant nodes being provided aren't being used correctly, or are there simply not enough to handle this level of churn?
Tidy up and merge blind-search branch into master. It currently has a different commit history so will need done manually.
The EpiChord implementation is based on Chord, which does not work when merge = true. For parallel paths to be enabled, merge must = true. We need to figure out why EpiChord does not support merge = true, and fix/enable it.
When a slice is found that requires more nodes, according to the paper a request should be sent to the midpoint of the slice.
Since a lookup returns only nodes proceeding the requested key, this means it is impossible for a node in the second half of the slice to be found, and hence we end up with half the slice empty.
I have currently solved this by looking up at the end of the slice rather than the midpoint, however this isn't a good solution either as, assuming the slice has a large number of nodes in it, only the last few will be found. Ideally we want nodes spread evenly throughout the slice, but the paper doesn't seem to address this. Perhaps we could use a custom lookup message that would return X nodes centred around the key?
The original EpiChord paper claims their simulations were performed with exponentially distributed lifetime mean, however the code doesn't look like it does.
node_lifespan = (long) (((double) Global.action_interval) * Global.base_node_lifespan
+ parent.rng.nextDouble() * ((double) Global.node_lifespan));
Responses in blind-search should have the option of direct or source response routing.
When p>1 a huge number of maintenance messages are generated. For a network of 600 nodes we were generating 72 maintenance messages/second/node. When p=1 this is 0.3 maintenance messages/second/node.
The amount of nodes required in a cache slice should be calculated based on a parameter j
and an estimate of the likely-hood of existing nodes being dead. Currently we require numSiblings
, which is wrong!
I didn't see it in the original paper, but the code seems to dynamically calculate the average node lifetime based on observations from the cache, and use this to set the successor/predecessor stabilization interval.
We should only send a full successor/predecessor list if a change was detected since the last stabilization with the same node.
When sending a lookup response or findnode response we should attach expire times for each node mentioned.
Our code is currently from OverSim-20090908, which is obviously rather out-of-date now. We should update, however merging changes for the blind-search branch is not trivial.
EpiChord specifies we should return numRedundantNodes proceeding nodes not succeeding. This causes issues with sorting the NodeVector since we always want the node after the ID first, then numRedundantNodes proceeding nodes.
I don't think this should have much effect on the performance since EpiChord keeps both a predecessor and successor list, but we should try follow the spec if possible...
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.