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 network. 
It achieves exponential path diversity with linear state in the
network.

Their goal is to have slices that have low stretch and high
diveristy.  They achieve this by computing new path weights that are
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 that
these can be used with only two tries based on the Sprint network
topology.

Q & A:

Q: Why do we need this number of flexibility?  Why not just have 3-4
disjoint paths.

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 at any
hop, which allows us to circumvent the faulty links.  The weights are chosen
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 reliability. Comparing
with k-disjoint, all you have to do is fail one on each of these disjoint paths
to disconnect the path; with splicing you have to disconnect the cut.  Feamster
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.  Even probabilistically
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
variants.

Q: Is it possible for you scheme to guarantee SLAs

A: One of our future work coming up with ways of selecting slices that can
satisfy QoS.

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
slice.

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.