Path Splicing: Reliable Connectivity with Rapid Recovery

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}
}