Traceroute for multi-path routing

A method comprising:

• sending, by a first network device, a first traceroute request packet to a second network device having a plurality of paths for reaching a third network device, wherein the second network device is positioned between the first network device and the third network device;
• based on sending the first traceroute request packet, receiving, by the first network device and from the second network device, a corresponding traceroute response packet for each of the plurality of paths, wherein the corresponding traceroute response packet comprises a payload including a corresponding session identifier that identifies a corresponding path of the plurality of paths that is traced by the first traceroute request packet;
• based on sending the first traceroute request packet, receiving, by the first network device and from the second network device, a message having a value that indicates a number of paths of the plurality of paths;
• determining, by the first network device and based on the value of the received message, whether the first network device has received a corresponding traceroute response packet for each of the plurality of paths;
• and
• based on determining the first network device has received the corresponding traceroute response packet for each of the plurality of paths, determining, by the first network device and based on the corresponding traceroute response packet for each of the plurality of paths, a next hop for each of the plurality of paths.