Failure Control in Multipath Route Tracing

Free registration required

Executive Summary

Traceroute is widely used to report the path packets take between two internet hosts, but the widespread deployment of load balancing routers breaks a basic assumption - that there is only a single such path. The authors specify an adaptive, stochastic probing algorithm, the Multipath Detection Algorithm (MDA), to report all paths that probes can follow between a source and a destination. They establish the foundations of, and show how to calculate, rigorous statistical guarantees for the discovery of the entire multipath route. They explore algorithm cost/guarantee tradeoffs in real experiments and show the inadequacy of the classic practice of sending three probes per hop.

  • Format: PDF
  • Size: 219.9 KB