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.