Review: One-hop source routing

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

Name: Robert Danek.
Course: CS2209, Fall '06.

    This paper discusses the feasibility of recovering from internet
path failures by routing through some intermediate node that typically
would not be part of the path. The authors refer to this as "one-hop
source routing". The motivation for One-Hop Source Routing is to
increase availability of hosts on the internet, and to increase the
speed at which path recovery takes place.

    The authors start the paper by describing a measurement study in
which they attempted to discover the frequency, location, and duration
of path failures, and to asses the benefits of one-hop source routing in
recovering from those failures. The location of failures is particularly
important for assessing the feasibility of one-hop source routing.
Locations of failures can be broken down into the following categories:
last hop, middle core, source side, and destination side. Intuitively,
if failures occur mostly at the last hop (i.e., end system, or last-hop
access link) then one-hop source routing is futile, since any path to
the end-system will be down. However, if the majority of failures occur
in the "core of the internet" (middle core), then one-hop source routing
has a chance of working.

    The authors found that the location of failure varied based on
whether the end-host being studied was a popular server or a broadband
host. In the case that it was a server, then the majority of failures
were due to non-last-hop problems, while for broadband hosts, the
majority of failures were due to last-hop problems. So there is a
potential benefit for using one-hop source routing in the case when
trying to contact end-hosts that are servers on the internet.

    The basic idea behind one-source hop routing is that if a path
failure occurs, then it might still be possible to reach the destination
if the packet is first routed to some "intermediate" node that is not
along the original path. There then may be an alternate path from the
intermediate node to the destination that still works.

    The authors spend some time discussing how the intermediate node
should be chosen. It turns out that the most effective scheme that they
could come up with is called "random-4". Basically, when a path failure
occurs, choose 4 of the possible intermediaries at random, and try
sending the packet via those intermediaries in parallel. The first one
to send an ACK becomes the intermediary through which subsequent packets
should be sent, at least until the original path is repaired.

    The paper also describes a prototype implementation that is built on
top of the Linux netfilter framework. They tested the prototype to see
what the end-user experience would be like when using it as part of a
web-browsing application for popular servers.

    It turns out that web-servers, besides experiencing path failures in
the network, also tend to experience application failures. One-hop
source routing cannot do anything about this problem. Taking
application-level failures into account, the authors found that only 20%
of failures could be recovered from using one-hop source routing.

    Overall this was a good paper, however the authors results with
their prototype implementation are somewhat discouraging. Other positive
aspects of the mechanism that they propose is that it's transparent to
the destination hosts, and it doesn't involve any sort of probing
mechanism that sends frequent messages to the participating nodes, thus
making it scalable. On the negative side, components do need to be
installed at the "intermediate" nodes and not just the source, so it can
still be cumbersome to deploy in practice.
Received on Mon Oct 16 2006 - 18:37:41 EDT