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

The paper proposes a simple, scalable and effective approach to
recovering from Internet path failures called one-hop source routing,
which attempts to recover from path failures by routing indirectly
through a small set of randomly chosen intermediaries. The 3 main
contributions of the paper are:
1. A one-week broad measurement study of Internet path failures from 67
PlanetLab vantage points to over 3000 widely dispersed Internet
destinations, including popular services, broadband hosts, and randomly
selected IP addresses. They analyzed the location, frequency and
duration of failures. The very detailed experimental results showed that
most Internet path worked well and only experienced a handful of
failures. Also most paths exprienced less than 15minutes of downtime
over the one week trace. They observed that when failures do occur they
were widely distributed across paths and portions of the network.
Furthermore, broadband hosts experienced more of the longer lasting
last-hop failures than servers.
2. The authors used the their measurements to show that when an
alternative path exists, that path can be exploited through the
extremely simple technique of one-hop source routing (the source
attempts to reach the destination indirectly through a small set of
intermediary nodes). After exploring 3 policies (random-k, history-k and
BGP-paths-k), they found that the stateless random-4 policy comes the
closest to obatining the maximum possible gain. Although the more
sophisticated policies had some positive effect on the ability to
recover from paths failures, they have a higher cost and only limited
benefit and are, hence, not scalable. The authors concluded that the
best policy was random-4: begin recovery after a single packet loss,
attempt to route through both the default path and four randomly
selected intermediaries, and to abandon recovery after four attempts to
each of the randomly selected intermediaires fail and to wait instead
for the default path to recover. This is scalable and requires no
overhead messages.
3. Implementation and deployment of a prototype one-hop source routing
infrastructure on PlanetLab (called SOSR). The paper describes the
implementation on Linux using ipfilters and netstat, and evaluates it as
well.

The authors conclude that one-hop-source routing is easy to implement,
adds negligible overhead, and acheives close to the maximum benefit
available to any alternative routing scheme, without path monitoring,
history or a priori knowledge of any kind.

The paper is well written, although I find that they repeat their
goals/contributions several times. The authors conduct a very in-depth
study and present their detailed results in a very comprehensive manner.
The only question at the end of the paper is if the technique is
actually useful given that most failures are last hop failures which are
not recoverable with one-hop source routing and furthermore, there is no
noticeable improvement to the user's Web browsing experience.
Received on Sun Oct 15 2006 - 18:15:33 EDT