Improving the Reliability of Internet Paths with One-hop Source Routing

Paper Review: Improving the Reliability of Internet Paths with One-hop
Source Routing

The paper proposes, one-hop source routing, a simple and scalable
approach to recovering from Internet path failures. The scheme claims
to have very low overhead since it does not require any path
monitoring, but rather uses randomly chosen intermediaries to
indirectly route around failures.

It is imperative to fully understand a problem before attempting to
present a solution. The paper begins by characterizing real Internet
failures by conducting large-scale measurements over a seven-day
period. One result of these measurements was the classification of
loss events into either src_side, middle_core, dst_side, last_hop and
unclassifiable. The distribution of these events for varying types of
connections provides some insight into the types of failures which are
commonly seen by servers and broadband users. Broadband users saw a
high instance of last-hop failures, which also happen to be the
longest-lasting failures. There is not much that can be done to
improve on these failures aside from ISPs provisioning these links
better. Furthermore, their measurements showed that very few paths
experienced zero failures and most paths experienced a small number of
failures. Finally, they determined that 66% of the failures to
servers and 39% of failures to broadband hosts were potentially
recoverable. The results of the measurements show that there is room
for improvement through a scheme such as one-hop source routing and
that the most benefit will be seen for paths to servers.

They propose a scheme called random-k in which after a failure, k
intermediary nodes are selected to re-route through. Their
measurements showed that 4 is the best value for k since it balances
the tradeoff between performance and overhead. Random-4 is said to be
able to route around 61% of all failures for popular servers. Path
diversity is the key for this scheme. Thus, it does not fair as well
for near-source and last-hop failures as there are fewer routing
alternatives.

The paper then proposes two policies, in addition to random-k, said to
perform better at the cost of having to maintain state. The first
alternative, history-k, chooses k-1 intermediaries at random and then
uses the most recent successful intermediary as the final one. The
second alternative, BGP-paths-k, chooses the k intermediaries with the
smallest number of ASes in common with it. This scheme assumes having
knowledge about the ASes in a path from the source to destination.
This scheme attempts to exploit the fact that disjoint paths offer the
best alternatives. Although these schemes provide better performance
for small values of k, the differences disappear when k is increased
slightly.

The experiments also test the necessity of persistent random-4
attempts. It was shown that after a single failed random-4 attempt,
the probability of a successful transmission on the next random-4
attempt was extremely low. Thus one failed random-4 attempt is a
strong indicator that the destination is unreachable.

The paper presents an approach to routing around failed paths on the
Internet using minimal state and overhead. The approach is simple yet
effective. They also supported their work with a prototype
implementation. The tests run on this prototype had promising results
pointing to possible deployment of one-hop source routing. Their
results are similar to other overlay routing schemes (i.e RON) yet
their system does not have scalability limits and high message
overhead. The improvement provided by their scheme is noticeable yet
far from extraordinary. The paper itself claims that their system
would not likely provide any noticeable improvement to a user browsing
the web. It is difficult to get excited about an idea which itself
does not seem enthusiastic. Nevertheless, the work has merit and
provides a viable scheme for improving reliability in the Internet.
This paper was a ?good read?. It was both logical and clear and the
ideas were presented well with enough background and explanation.

-- Nadeem Abji
Received on Sat Oct 14 2006 - 02:54:36 EDT