Path Splicing with Network Slicing
by Nick Feamster

Abstract:
We present path splicing, a new routing primitive that allows network paths to
be constructed from multiple independent routing processes that run over a
single network topology.  Path splicing computes multiple independent routing
trees by randomly perturbing link weights and, using network virtualization,
runs multiple routing protocols in parallel slices, which collectively insert
entries into a shared forwarding table.  Using a small number of additional
bits in packet headers, end systems can then redirect traffic between
forwarding tables at any hop in the network. By allowing paths to be
``spliced'' by assembling segments from each of these trees, path splicing
achieves exponential improvements in path diversity with only a linear
increase in state and message complexity.  Our evaluation of path splicing on
several 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.  We also describe the
implementation and deployment of path splicing on the VINI testbed.

Joint work with Murtaza Motiwala and Santosh Vempala.