We believe we have been able to track down all of the significant
factors in the apparent disparity between the IDMaps graph in your
infocomm paper and the Detour graphs in the upcoming Sigcomm paper.
Credit for tracking this down goes to Andy Collins.
Here are the factors:
1. Visual impact of log-relative vs. linear-absolute.
You plot relative latency on a log scale, while we plot absolute
latency on a linear scale. This is surprisingly important for
either minimizing or maximizing the visual impact of the differences
between the direct and indirect paths.
2. Extreme points. We trim extreme points off the cumulative distribution,
to allow to zoom in on the mass of the data set -- again, this changes the
visual impact, but doesn't represent a data error.
3. Min vs. mean. We compare the alternate/direct paths using mean
performance; you use minimums. This represents about half the difference
between the graphs once they are plotted in the same way.
4. Path selection. Perhaps most significant, it appears that your alternate
path selection algorithm picks the path that is "closest" in
min latency to the direct path, while ours picks the one that
has the "best"(smallest, shortest) mean latency. Given how you refer
to the graph in the paper, this seems like a bug -- you are trying to
predict the performance on the direct path using the alternate paths,
so presumably you wouldn't have the direct path measurement around
as a reference point.
5. There are a few other minor differences, which seem to have
relatively negligible impact.
Some graphs that show the effect of #4. All of these use minimum latencies:
http://www.cs.washington.edu/homes/acollins/detour/idmaps-closest.ps
-- your graph, using alternate path closest to direct
http://www.cs.washington.edu/homes/acollins/detour/idmaps-best.ps
-- your graph, using shortest alternate path
http://www.cs.washington.edu/homes/acollins/detour/idmaps-closest-ourdata.ps
-- your graph on our datasets, using closest path
http://www.cs.washington.edu/homes/acollins/detour/idmaps-best-ourdata.ps
-- your graph on our datasets, using shortest path
http://www.cs.washington.edu/homes/acollins/detour/idmaps-best-ourdata-zoom.ps
-- your graph on our datasets, clipping off the extremes
Since we need to ship the sigcomm final copy off in about 10 days,
it would be great if you could verify/refute this analysis by then.
If the above explanation is correct, I'm not sure what we put in
our paper about it -- probably nothing. I'm mostly concerned
about making sure we haven't made an obvious error in one of our graphs.
tom