Traceroute for multi-path routing

Abstract

In general, techniques are described for extending network connectivity software utilities, such as traceroute, to provide complete visibility into a network topology between a source device and a destination device, even when an intermediate network device may be actively utilizing multiple network links when forwarding packets toward the destination. In one example, a network device coupled to a plurality of paths and positioned between a source network device and destination network device may receive a traceroute packet. The network device may also, for each of the plurality of paths, modify a payload of the traceroute packet to include a respective identifier for a corresponding path of the plurality of paths to construct a respective modified traceroute packet for the corresponding path. The network device may also forward the respective modified traceroute packets on the corresponding paths.

What is claimed is: 
     
         1 . A method comprising:
 receiving, by a network device coupled to a plurality of paths for reaching a destination network device and positioned between a source network device and the destination network device, a traceroute packet;   for each of the plurality of paths, modifying, by the network device, a payload of the traceroute packet to include a respective identifier for a corresponding path of the plurality of paths to construct a respective modified traceroute packet for the corresponding path;   forwarding, by the network device, the respective modified traceroute packets on the corresponding paths.   
     
     
         2 . The method of  claim 1 , wherein receiving the traceroute packet comprises:
 receiving one or more network addresses of one or more intermediate network devices that forwarded the traceroute packet on a path to the network device, wherein the one or more intermediate network devices are positioned between the network device and the source network device; and   receiving one or more session identifiers associated with the path to the network device for which the one or more intermediate network devices forwarded the traceroute packet.   
     
     
         3 . The method of  claim 1 , wherein modifying the payload of the traceroute packet to include the respective identifier further comprises modifying the payload of the traceroute packet to include a network address of the network device. 
     
     
         4 . The method of  claim 1 , further comprising:
 configuring, by the network device, an indicator representing a number of the plurality of paths of the network device; and   sending, by the network device, the indicator to the source network device.   
     
     
         5 . The method of  claim 4 , wherein configuring the indicator further comprises configuring the indicator to include one or more network addresses of one or more next-hops on the plurality of paths of the network device. 
     
     
         6 . The method of  claim 1 , further comprising:
 determining, by the network device, whether the traceroute packet includes a TTL value of zero; and   in response to determining the TTL value is zero, constructing, by the network device, a response comprising a respective identifier included with traceroute packet.   
     
     
         7 . The method of  claim 6 , wherein constructing the response comprising the respective identifier further comprises:
 constructing the response to include one or more network addresses of one or more intermediate network devices that forwarded the traceroute packet to the network device, wherein the one or more intermediate network devices are positioned between the network device and the source network device; and   sending, by the network device, the response towards the source network device.   
     
     
         8 . The method of  claim 6 , wherein configuring the response to the traceroute packet comprises configuring an Internet Control Message Protocol (ICMP) packet. 
     
     
         9 . The method of  claim 1 , wherein the plurality of paths comprises a plurality of Equal Cost Multi-Path (ECMP) paths. 
     
     
         10 . A method comprising:
 sending, by a source network device, a traceroute packet to an intermediate network device coupled to a plurality of paths for reaching a destination network device, wherein the intermediate network device is positioned between the source network device and the destination network device; and   receiving, by the source network device and from the intermediate network device, one or more respective responses, wherein each of the one or more respective responses comprises a payload including a respective identifier for a corresponding path of the plurality of paths.   
     
     
         11 . The method of  claim 10 , wherein receiving the one or more respective responses comprises:
 receiving one or more network addresses of one or more network devices that forwarded the traceroute packet on the corresponding path.   
     
     
         12 . The method of  claim 10 , further comprising:
 receiving, by the source network device and from the intermediate network device, an indicator representing a number of the plurality of paths of the intermediate network device;   determining, by the source network device and based on the indicator, whether the source network device has received a respective response for each of a plurality of traceroute packets generated by the intermediate network device and output on respective ones of the plurality of paths toward the destination network device; and   in response to determining the source network device has received the respective response for each of the plurality of paths, configuring, by the source network device, another traceroute packet with an incremented TTL value.   
     
     
         13 . The method of  claim 12 , further comprising:
 in response to determining the source network device has received the respective response for each of the plurality of paths, constructing, by the source network device and based on the responses, a traceroute tree for each of the plurality of paths.   
     
     
         14 . The method of  claim 10 , wherein sending the traceroute packet comprises sending an identifier for one or more paths from the source network device to the destination network device. 
     
     
         15 . The method of  claim 14 , wherein sending the traceroute packet further comprises sending a network address of the source network device. 
     
     
         16 . The method of  claim 10 , wherein the respective identifier of the corresponding path further comprises:
 one or more network addresses of the one or more network devices that forwarded the traceroute packet on the corresponding path.   
     
     
         17 . A network device comprising:
 a plurality of network interfaces, each of the network interfaces coupled to a different one of a plurality of paths for reaching a destination network device, wherein the network device is positioned between a source network device and the destination network device;   one or more hardware-based processors configured to:
 receive a traceroute packet destined for the destination device; 
 for each of the plurality of paths, modify a payload of the traceroute packet to include a respective identifier for a corresponding path of the plurality of paths to construct a respective modified traceroute packet for the corresponding path; and 
 forward the respective modified traceroute packets on the corresponding paths. 
   
     
     
         18 . The network device of  claim 17 , wherein the one or more hardware-based processors are further configured to:
 determine whether the traceroute packet includes a TTL value of zero; and   in response to determining the TTL value is zero, construct a response comprising a respective identifier included with traceroute packet.   
     
     
         19 . The network device of  claim 17 , wherein the one or more hardware-based processors are further configured to:
 configure an indicator representing a number of the plurality of paths; and   send the indicator to the source network device.   
     
     
         20 . A source network device comprising:
 one or more hardware-based processors configured to:   send a traceroute packet toward a destination network device; and   receive one or more respective responses, wherein each of the one or more respective responses comprises a payload including a respective identifier for a corresponding path of a plurality of paths of an intermediate network device, wherein the intermediate network device is positioned between the source network device and the destination network device.   
     
     
         21 . The source network device of  claim 20 , wherein the one or more hardware-based processors are further configured to:
 receive, from the intermediate network device, an indicator representing a number of the plurality of paths of the intermediate network device;   determine, based on the indicator, whether the source network device has received a respective response for each of the plurality of paths; and   in response to determining the source network device has received the respective response for each of the plurality of paths, configure another traceroute packet with an incremented TTL value.