Slot: Shortened Loop Overlay Transport

 

Overview of Slot

Overlay routing has emerged as a promising approach to mitigating many problems with Internet routing, such as improving the reliability of Internet paths and supporting multicast communication. As overlay routing is gaining wider acceptance, we argue that it is time to investigate how overlay networks can benefit Internet transport. We propose Slot, a framework that leverages overlay networks to improve the throughput of feedback-based transport protocols. Slot exploits the observation that the throughput of feedback-based transport protocols is inversely proportional to the length of their end-to-end feedback control loop, and effectively shortens an end-to-end control loop by breaking it up into multiple pipelined shortened sub-loops via intermediaries carefully chosen from an overlay network. As a result, Slot increases the throughput of an end-to-end transport connection to that of the longest sub-loop.
 

A Slot client module transparently hijacks outbound TCP connections from the applications on the client node to route them through an overlay path. For each hijacked TCP connection, a Slot client module uses the following path discovery process: (1) probing the server to obtain the direct server RTT, (2) requesting the intermediaries to
probe the server to obtain path RTTs to the server via paths through the intermediaries. The alternate paths probed can range from a minimum of 2-hops (using 1 intermediary) to multiple hops. Paths with more than 2 hops can be obtained by having each intermediary probed by the client to repeat the above process recursively. The path discovery process is depicted in Figure above in which the client probes multiple paths toward the server. As seen in Figure, the client chooses the path Client-A-B-Server which has the minimum path RTT (35 msec) out of all possible paths. Note that the sum_{i=0}^n RTT_i of this chosen path (90 msec) is higher than the direct RTT to the server (70 msec). However, due to pipelining of data over the TCP sub-connections, this path is expected to have a higher TCP throughput which corresponds to its 35 msec path RTT. Interestingly, our wide area measurements from show that a single intermediary is enough to garner most of the gain from shortened loops.

Slot for 802.11 Networks

We have also implemented MeshCache  a application layer TCP relay and caching system for 802.11 wireless mesh network. MeshCache builds on the idea of Slot of breaking up long haul TCP connections (from clients to gateways)  into multiple shortened sub-loops. MeshCache takes the Slot concept to the extreme and splits the transport connection at each mesh router! It also performs caching along each wireless mesh router to exploit the locality in user traffic. This system has several advantages.(1) It spreads the load in the network and hence alleviates the congestion around the gateway. (2) It promotes local communication between clients and nearby routers (that have a cached copy) which improves the capacity of mesh networks. (3) It also improves client throughput by allowing content to be fetched from nodes closer (in network hops) than the gateway as well as by providing clients the choice of choosing the best cached copy based on link-quality routing metrics. We have extensively evaluated this system through simulation and an implementation extending the squid proxy on our 32 node wireless network testbed and found that it provides significant performance improvements.

Slot is used in MeshCache with a different motivation since long RTTs are not the main issue in wireless mesh networks. Rather, the hop by hop transport allows us to cache data for free as it is transported. There is also no routing detour since the transport is split along the route chosen by the routing protocol. The throughput of per-hop transport  is better than end-to-end transport under fading channels with lossy links. The reason is that losses can be recovered from intermediate routers and the TCP window can ramp up faster in the event of losses since quicker feedback is obtained (from the next hop instead of the gateway/Internet server).
 

Paper Trail

People