Path Splicing: Reliable Connectivity
with Rapid Recovery Murtaza
Motiwala, Nick Feamster, and Santosh
Vempala (Georgia Tech)
Murtaza presented path splicing, a routing algorithm that can provide
fast recovery whose reliability is approaching the underlying
It achieves exponential path diversity with linear state in the
Their goal is to have slices that have low stretch and high
diveristy. They achieve this by computing new path weights that
perturbed versions of the original weights and new weight is at most
twice the original weight and is further such that we tend to avoid
paths that go through high degree nodes.
Murtaza also explained how splices are generated, and the concept of
splicing bits that can be used to find spliced paths. He showed
these can be used with only two tries based on the Sprint network
Q & A:
Q: Why do we need this number of flexibility? Why not just have
A: There is evidence to suggest that more diversity is useful
Q: You do not guarantee disjointness. Also what are the weight.
How do you pick them.
A: We do not guarantee disjointness because we can switch to any slice
hop, which allows us to circumvent the faulty links. The weights
randomly from from interval [w,2w], where w is the original link weight.
Q: Why slicing would be better than k-disjoint paths.
A: First the stretch is small. Secondly, it has higher
with k-disjoint, all you have to do is fail one on each of these
to disconnect the path; with splicing you have to disconnect the
mentioned that we have a argument
Q: What about loops:
A: The loops are not persistent since the splicing bits are finite and
eventually the packets follow the default splice.
Q: You should avoid loops, as in guarantee that they never occur.
avoiding them is not good enough. Also related to earlier question, what
is the service model.
A: What I have described the simplistic model. But you can think of
Q: Is it possible for you scheme to guarantee SLAs
A: One of our future work coming up with ways of selecting slices that
Q: Usually service providers like "determinism", do you think that
ISPs would like the randomness
Ans: It is not completely random.
Q: What was the stretch.
A: In our experiments it was 1.15-1.20
Q: There are some problems known in Rocket Fuel topology, would that
affect your results.
A: We have also tried GEANT.
Q: What is the expected recovery time?
A: In the case of link failure, router can immediatly shift to a new
Q: Who sets the shim header
A: It is not necessary that the host sets the splicing bits, for
example the first hop router could set these bits.