Thursday, December 4, 2008

Improving Overlay Performance in Constrained Networks

Background: Our work currently focuses on using structured p2p overlay networks (Brunet) for routing packets for our distributed VPN software (IPOP). Routing small control data through the overlay is fine, but when a user wants to perform bandwidth intensive tasks, routing through the overlay can perform worse than a direct connection to the remote end point.

Problem: In constrained networks, forming direct connections between two peers may not be possible. How do we improve this situation?  Secondly, in our current implementation of forming direct connections, we basically form a direct connection with anyone we have IP traffic with, this will not scale well.

Related Work: Improving routing using user-selected supernodes - SBARC, improving bandwidth with BitTorrent - Ono, best path detection - Ant routing

What We Have Now: Currently in our system we have a Vivaldi system (that is a bit heavy and could possibly use a rewrite) which could potentially be turned into a generic system information database that also includes Vivaldi coordinates and latency between two edges. The ability to select shortcuts based upon physical (latency-based) proximity. Velocity based routing, which is a greedy-like routing algorithm that takes latency into consideration.

Deadline: Ideally, we want to have a paper at ICAC '09 with a deadline of 01/19/09 giving a mere 1.5 months to get something wrapped up!

Possible Solution:  A recently graduated colleague of mine did some initial work on solving this problem. His solution was to have the two end points attempt to discover mutually agreeable proxies and then form a tunnel edge over them. There were two methods to discover proxies: search the Vivaldi coordinates of the system to find good candidates or use existing neighbors of the two nodes. This work has a direct relation to supernodes paper mentioned above with the exception that it is somewhat autonomous.

The problems are a few problems with this approach. By forming a Tunnel edge between the two end points, we move routing decisions away from the routing algorithms and into the Tunnel edge. The basic premise is that if we do not have a connection then we are not performing optimally, this may be untrue! There is no control logic on how many proxy connections we form and connections are not free.

What looks like the best solution is to take this initial work, add ant like capabilties to the system so that we don't create unnecessary optimizations, only make direct connections and only have routing logic in the routers, and to move users towards velocity routing.  The question is where does the Ant go in this problem and personally, I would think we would want the Routers (or data handlers) to communicate with the Ant processor that way we can ignore packets that are delivered locally and do not have to double parse a packet.

Potential Issues:  Should we prequalify the velocity routing prior to this paper?  Perhaps we should potentially simultaneously publish a workshop paper containing the velocity routing at the same time we do the ICAC paper?  This has the potential to conflict with the recent graduates plans for writing a workshop paper discussing shortcut-tunneling, but given that he left over 4 months ago and that we have a test environment to do this in and a need for it, I would like to get it moving!

Next Step:  Design environments for testing what we have now followed by implementing tests for these theories.

No comments:

Post a Comment