Detecting sources of computer network failures

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for detecting sources of computer network failures. One of the methods includes identifying a network flow in a computer network between a source and a destination; performing a first probe to determine whether there is end-to-end connectivity between the source and the destination; in response to determining that there is no end-to-end connectivity between the host and the destination, performing one or more additional probes including a second probe to determine whether each hop in the path of the network flow between the source and the destination is operational including requesting that the source transmit a respective first trace diagnostic packet to each hop in the path of the network flow; and determining whether at least one link of the computer network that is part of the path of the network flow has failed based on the results.

1 - 19 . (canceled) 
     
     
         20 . A method comprising:
 identifying a particular path of a network flow in a computer network between a source and a destination, wherein the particular path comprises one or more network devices coupled by one or more links; and   in response to a determination that there is no end-to-end connectivity between the source and the destination along the particular path, determining whether a network component of the particular path in the network flow has failed comprising:
 requesting that the destination transmit a respective trace diagnostic packet to each network device along the particular path, wherein each trace diagnostic packet is configured to follow the particular path and has a particular value in a time-to-live field configured to cause a corresponding network device to send at least a time exceeded message in response to that trace diagnostic packet, wherein the time exceeded message includes a portion of the trace diagnostic packet that includes a packet identifier inserted into a first plurality of bits of the trace diagnostic packet; and 
 determining whether at least one network component that is part of the particular path of the network flow has failed based on results of the trace diagnostic packets. 
   
     
     
         21 . The method of  claim 20 , wherein determining whether at least one network component has failed comprises:
 determining whether the destination has received a time exceeded message from a particular network device;   in response to determining that the destination has received the time exceeded message from a particular network device, determining that the particular network device is operational from the source along the particular path; and   in response to determining that the destination has not received the time exceeded message from a particular network device, determining that the particular network device has failed from the source along the particular path.   
     
     
         22 . The method of  claim 20 , wherein the time exceeded message is an internet control message protocol (ICMP) message comprising a header portion and a body portion, wherein the header portion comprises an 8-bit type field and an 8-bit code field set as respective values to indicate that the ICMP message is a time exceeded message. 
     
     
         23 . The method of  claim 20 , wherein the time exceeded message is an internet control message protocol (ICMP) message comprising the first plurality of bits of the trace diagnostic packet that trigger the time exceeded message, wherein the first plurality of bits are the first 64 bits of the trace diagnostic packet. 
     
     
         24 . The method of  claim 20 , wherein the first plurality of bits of the trace diagnostic packet where the packet identifier is inserted comprise one of a sequence number of a TCP packet or a length field of a UDP packet. 
     
     
         25 . The method of  claim 20 , further comprising:
 estimating a low reliability for a link of the one or more links in the particular path based on a count of trace diagnostics packets observed to have traveled the link;   determining the low reliability corresponds to a low utilization of the link; and   in response, determining that the estimated low reliability for the link is a false positive detection.   
     
     
         26 . The method of  claim 20 , wherein the determination that there is no end-to-end connectivity between the source and the destination comprises:
 performing a first probe to determine whether there is end-to-end connectivity between the source and the destination including requesting that the destination transmit an end-to-end diagnostic packet to the source, wherein the end-to-end diagnostic packet includes information comprising a source identifier field and a destination identifier field that include identifiers for the source and destination, respectively, that match the packets in the network flow between the source and destination such that one or more network devices in the computer network forward the end-to-end diagnostic packet on the particular path of the network flow.   
     
     
         27 . A system comprising:
 one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
 identifying a particular path of a network flow in a computer network between a source and a destination, wherein the particular path comprises one or more network devices coupled by one or more links; and 
 in response to a determination that there is no end-to-end connectivity between the source and the destination along the particular path, determining whether a network component of the particular path in the network flow has failed comprising:
 requesting that the destination transmit a respective trace diagnostic packet to each network device along the particular path, wherein each trace diagnostic packet is configured to follow the particular path and has a particular value in a time-to-live field configured to cause a corresponding network device to send at least a time exceeded message in response to that trace diagnostic packet, wherein the time exceeded message includes a portion of the trace diagnostic packet that includes a packet identifier inserted into a first plurality of bits of the trace diagnostic packet; and 
 determining whether at least one network component that is part of the particular path of the network flow has failed based on results of the trace diagnostic packets. 
 
   
     
     
         28 . The system of  claim 27 , wherein determining whether at least one network component has failed comprises:
 determining whether the destination has received a time exceeded message from a particular network device;   in response to determining that the destination has received the time exceeded message from a particular network device, determining that the particular network device is operational from the source along the particular path; and   in response to determining that the destination has not received the time exceeded message from a particular network device, determining that the particular network device has failed from the source along the particular path.   
     
     
         29 . The system of  claim 27 , wherein the time exceeded message is an internet control message protocol (ICMP) message comprising a header portion and a body portion, wherein the header portion comprises an 8-bit type field and an 8-bit code field set as respective values to indicate that the ICMP message is a time exceeded message. 
     
     
         30 . The system of  claim 27 , wherein the time exceeded message is an internet control message protocol (ICMP) message comprising the first plurality of bits of the trace diagnostic packet that trigger the time exceeded message, wherein the first plurality of bits are the first 64 bits of the trace diagnostic packet. 
     
     
         31 . The system of  claim 27 , wherein the first plurality of bits of the trace diagnostic packet where the packet identifier is inserted comprise one of a sequence number of a TCP packet or a length field of a UDP packet. 
     
     
         32 . The system of  claim 27 , further comprising:
 estimating a low reliability for a link of the one or more links in the particular path based on a count of trace diagnostics packets observed to have traveled the link;   determining the low reliability corresponds to a low utilization of the link; and   in response, determining that the estimated low reliability for the link is a false positive detection.   
     
     
         33 . The system of  claim 27 , wherein the determination that there is no end-to-end connectivity between the source and the destination comprises:
 performing a first probe to determine whether there is end-to-end connectivity between the source and the destination including requesting that the destination transmit an end-to-end diagnostic packet to the source, wherein the end-to-end diagnostic packet includes information comprising a source identifier field and a destination identifier field that include identifiers for the source and destination, respectively, that match the packets in the network flow between the source and destination such that one or more network devices in the computer network forward the end-to-end diagnostic packet on the particular path of the network flow.   
     
     
         34 . One or more non-transitory computer storage media encoded with computer program instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
 identifying a particular path of a network flow in a computer network between a source and a destination, wherein the particular path comprises one or more network devices coupled by one or more links; and   in response to a determination that there is no end-to-end connectivity between the source and the destination along the particular path, determining whether a network component of the particular path in the network flow has failed comprising:
 requesting that the destination transmit a respective trace diagnostic packet to each network device along the particular path, wherein each trace diagnostic packet is configured to follow the particular path and has a particular value in a time-to-live field configured to cause a corresponding network device to send at least a time exceeded message in response to that trace diagnostic packet, wherein the time exceeded message includes a portion of the trace diagnostic packet that includes a packet identifier inserted into a first plurality of bits of the trace diagnostic packet; and 
 determining whether at least one network component that is part of the particular path of the network flow has failed based on results of the trace diagnostic packets. 
   
     
     
         35 . The one or more non-transitory computer storage media of  claim 34 , wherein determining whether at least one network component has failed comprises:
 determining whether the destination has received a time exceeded message from a particular network device;   in response to determining that the destination has received the time exceeded message from a particular network device, determining that the particular network device is operational from the source along the particular path; and   in response to determining that the destination has not received the time exceeded message from a particular network device, determining that the particular network device has failed from the source along the particular path.   
     
     
         36 . The one or more non-transitory computer storage media of  claim 34 , wherein the time exceeded message is an internet control message protocol (ICMP) message comprising a header portion and a body portion, wherein the header portion comprises an 8-bit type field and an 8-bit code field set as respective values to indicate that the ICMP message is a time exceeded message. 
     
     
         37 . The one or more non-transitory computer storage media of  claim 34 , wherein the time exceeded message is an internet control message protocol (ICMP) message comprising the first plurality of bits of the trace diagnostic packet that trigger the time exceeded message, wherein the first plurality of bits are the first 64 bits of the trace diagnostic packet. 
     
     
         38 . The one or more non-transitory computer storage media of  claim 34 , wherein the first plurality of bits of the trace diagnostic packet where the packet identifier is inserted comprise one of a sequence number of a TCP packet or a length field of a UDP packet. 
     
     
         39 . The one or more non-transitory computer storage media of  claim 34 , further comprising:
 estimating a low reliability for a link of the one or more links in the particular path based on a count of trace diagnostics packets observed to have traveled the link;   determining the low reliability corresponds to a low utilization of the link; and   in response, determining that the estimated low reliability for the link is a false positive detection.   
     
     
         40 . The one or more non-transitory computer storage media of  claim 34 , wherein the determination that there is no end-to-end connectivity between the source and the destination comprises:
 performing a first probe to determine whether there is end-to-end connectivity between the source and the destination including requesting that the destination transmit an end-to-end diagnostic packet to the source, wherein the end-to-end diagnostic packet includes information comprising a source identifier field and a destination identifier field that include identifiers for the source and destination, respectively, that match the packets in the network flow between the source and destination such that one or more network devices in the computer network forward the end-to-end diagnostic packet on the particular path of the network flow.