|
EmpiricalEvaluation
This page contains the produced simulation outputs.
Empirical Evaluation1. IntroductionIn this wiki page I'll be including the simulation results produced using the latest release. This article is likely to change as newer versions are released, but in case it's not up-to-date, please refer to the version number corresponding to these outputs. 2. ResultsThe outputs shown in this section are produced using revision r13. Please note that in sections 2.2 and 2.3, the outputted results were consolidated in a single graph for simplicity. Note: 1 Time advance/step indicates 5 Cyclon shuffle initiations and 5 T-Man exchange initiations. The following simulations were ran with the following Out-Degree frequencies (for 6000 and 10000 peers):
2.1. Convergence RatesThese graphs show the error rates (or deviation from the optimal solution) per simulation cycle. It gives an indication of how fast the topology converges. 2.1.1 Scenario 1Input parameters:
2.1.2 Scenario 2Input parameters:
2.1.3 Scenario 3Input parameters:
2.1.4 Scenario 4Input parameters:
2.2. Average View AgeThese graph results shows the global average view ages across all nodes. This metric should give us an indication of how fast our protocols are disposing of higher aged nodes.
2.3. Average View AccuracyThese results show how accurate of a representation are the peer descriptors in our views compared to the current nodes' states. This should usually have a negative correlation with age.
3. Analysis & EvaluationFrom Scenarios 1 & 2, we can observe that there's a positive correlation between Cyclon View Size (cvs) and the convergence rate. Scenario 1 takes about 11 and 17 cycles to converge for 6000 & 10000 peers respectively. Scenario 2, which has a higher cvs, takes about 2-3 less cycles but the overall error rate (across all cycles) is significantly lower. However, the results depicted in Scenarios 3 & 4 are not what you would normally expect. Both scenarios have a higher T-Man View Size (tvs) of 6, yet it never converges for 10000 peers even after 35 time steps. If we compare the results of 1 & 3, we'll also notice that the overall convergence rate is lower for the 6000 peer simulation run. These results show that a higher tvs can work antagonistically and prevent the overlay from reaching its target topology. The reasoning for this is depicted in the graphs shown in sections 2.2 & 2.3. As we can see in 2.2, the average T-Man view age is increasing uniformly as we progress through the simulation, reaching an age of 75 by cycle 25. This indicates that the way our ranking function works bears no weight on the age of our peer descriptors. In other words, it doesn't discriminate based on age. The Cyclon views on the other hand plateau at a constant age of ~8 throughout the simulation. This is because of of how the Cyclon algorithm behaves (refer to section 3.2 in the Design entry for more information). Basically, Cyclon makes peers choose the nodes that they will communicate with based on age - to be more specific, they only shuffle with the oldest node in their views. This consequently causes the average view ages to be maintained at a constant level. So how does this affect convergence? Well, age is correlated with another important peer descriptor property - its accuracy. As the descriptor age increases, so does the probability that its dynamic elements (i.e. hop-count & current parents) would have changed. This means that its state might not be accurately represented. This is precisely what happens with our T-Man view. We can see from the graph in section 2.3 that it has a relatively low average accuracy (about 17%). This leads to peer views being populated with "false" highly ranked nodes. These nodes serve to umbrella other "authentic" nodes and thus prevents peers from finding their target children - which results in a failure to reach the target topology. There are multiple possible solutions for this problem that are still under-development. Potential changes that might alleviate this problem would include:
These potential solutions are still in a preliminary phase. Further simulation runs are required to prove their viability. | ||||||||||||||||