Institute of Electrical & Electronic Engineers
Traceroute is a tool to report the route packets take between two internet hosts. However, with the deployment of load balancing, there is no longer a single route to a destination, hence classic traceroute systematically misses some of these paths. In this paper, the authors specify an adaptive, stochastic probing algorithm, called the Multipath detection algorithm, to report all paths towards a destination. They have deployed this algorithm, probing from a single source towards multiple destinations. In their results, they have found instances of load balancing with as many as 16 interfaces per hop. The algorithm also allows them to count load balancing routers, identify their locations, and characterize them by type.