| Abstract | We present path splicing, a primitive that constructs net-work 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 knowl-
edge 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 mes-
sage complexity. We present randomized approaches for
slice construction and failure recovery that achieve near-
optimal performance and are extremely simple to config-
ure. Our evaluation of path splicing on realistic ISP topolo-
gies demonstrates a dramatic increase in reliability that ap-
proaches the best possible using only a small number of
slices and for only a small increase in latency.
|
