Tuesday, December 9, 2008

Rounding Up the Research Results

So it appears velocity routing was handled 1-deep in the Can paper (but you have to look carefully at 3.3 to notice it) although this is for a hypercube and explored with synthetic numbers only.  There implementation closely matches (if not identically) the method I proposed which boils down to "maximum ratio of progress to rtt".  Then there is discussion of optimizing shortcuts by using latency and even the convergence of the two.  Though his metrics really don't make much sense, I quote "To select the candidate set, the distance to the destination is expressed in binary notation, and neighbor i is chosen to the set if there is a 1 in the ith position."  I have NO idea what that has to do with proximity routing and perhaps it is revealed in their results where they suggest that proximity routing has no advantage when used with proximity-based shortcuts.  Finally, all the results are based on very synthetic benchmarks and I can easily lits many cases where PR definitely help PS, think of the case where I am surrounded by all but 1 low latency node, if a packet is incoming, it has a 1 / N chance of coming in on a low latency branch and (N-1)/N chance of not.  Considering that routes in a stable system are static, that could lead to very poor performance!  So while PS helps traversing the ring faster, PR helps when we're getting closer.  Perhaps there is a way to reconcile this.

So what is left undone:  we have a system where there are 2*K near neighbors, when we are routing nearby, most likely the packet will be routed through one of them.  If we make the assumption that each node also has at miniumum 2*K neighbors we can approximate how many hops it would take for this packet to arrive at the remote node.  I propose that we may see a reduction in hops and latency if we come up with some heuristic to evaluate our latency to our neighbors and the potential for increased hop count and make a routing decision based upon that.  If we know our neighbors, neighbors and their latency to them, we could further develop this routing mechanism to bring us even closer.

What makes this relevant?  Well I guess that will be another post.

1 comment: