Earlier measurements have shown that it is common for packets belonging to different flows to follow different paths between the same source and destination across the internet. However, this work was based on the fact that when performing a traceroute, ICMP messages packets are returned from different source addresses. This does not account for parallel paths between two routers, where ICMP messages are returned with a single source address. Our work finds such parallel paths by measuring reordering.
In order to accurately determine how much load balancing across parallel paths happens, we send packet trains of short UDP, ICMP and TCP packets where we either vary or keep stable header fields that may be used by routers and other devices to identify packets as belonging to the same flow. We further isolate reordering in the forward path from reordering in the return path to the degree possible. Our results show that for random destinations, probes towards 55% of all destinations encounter load balancing along the way. For well-known web destinations this number is 89%. This is a factor two to three higher than what is seen using source address based measurements.