Murtaza Motiwala, Nick Feamster, Santosh Vempala
Hotnets Workshop, Atlanta, GA, November 2007
We present path splicing, a primitive that constructs network
paths from multiple independent routing processes that run over a single
network topology. The routing processes compute distinct routing trees
using randomly perturbed link weights. A few additional bits in packet
headers give end systems access to a large number of paths. By changing
these bits, nodes can redirect traffic without detailed knowledge of
network paths. Assembling paths by splicing segments can yield up to
an exponential improvement in path diversity for only a linear increase
in storage and message complexity. We present randomized approaches for
slice construction and failure recovery that achieve near-optimal
performance and are extremely simple to configure. Our evaluation of
path splicing on realistic ISP topologies demonstrates a dramatic
increase in reliability that approaches the best possible using
only a small number of slices and for only a small increase in latency.
[PDF (143KB)] [Presentation (269KB)]
Bibtex Entry:
@inproceedings{motiwala2007path,
author = "Murtaza Motiwala and Nick Feamster and Santosh Vempala",
title = "{Path Splicing: Reliable Connectivity with Rapid Recovery}",
booktitle = {Hotnets Workshop},
year = {2007},
month = {November},
address = {Atlanta, GA}
}