Method and Apparatus for the Fast Detection of Connectivity Loss Between Devices in a Network

Abstract

A method and apparatus for quickly determining the status of a network device in a network communicates status inquiry messages over the forwarding plane of one network device to at least one neighboring network device. The status inquiry messages indicate the connectivity status with at least one neighboring network device.

1 . A network device, comprising a forwarding plane adapted:
 to forward packets based on previously resolved forwarding information stored at the network device;   to generate and communicate, with a neighboring network device, connectivity status messages; and   to determine, based on the communicated connectivity status messages, that bidirectional communication between the network device and the neighboring network device is maintained.   
     
     
         2 . The network device of  claim 1 , wherein the forwarding plane is adapted to determine that communication between the network device and the neighboring network device is maintained when a time interval between receipt of successive connectivity status messages from the neighboring network device is shorter than a predetermined time interval. 
     
     
         3 . The network device of  claim 2 , wherein the forwarding plane is adapted to determine that the time interval between receipt of successive connectivity status messages from the neighboring network device is shorter than the predetermined time interval by:
 starting a timer when a connectivity status message is received from the neighboring network device; and   determining that the time interval between receipt of successive connectivity status messages from the neighboring network device is shorter than the predetermined time interval when a subsequent connectivity status message is received from the neighboring network device before the timer expires.   
     
     
         4 . The network device of  claim 1 , wherein the forwarding plane is adapted to determine that communication between the network device and the neighboring network device is not maintained when no successive connectivity status message is received from the neighboring network device within a predetermined time interval. 
     
     
         5 . The network device of  claim 4 , wherein the predetermined time interval begins when a last connectivity status message is received from the neighboring network device. 
     
     
         6 . The network device of  claim 5 , wherein the forwarding plane is adapted to determine that no successive connectivity status message is received from the neighboring network device within the predetermined time interval by:
 starting a timer when a connectivity status message is received from the neighboring network device; and   determining that the time interval between receipt of successive connectivity status messages from the neighboring network device is longer than the predetermined time interval when no subsequent connectivity status message is received before the timer expires.   
     
     
         7 . The network device of  claim 1 , wherein each connectivity status message comprises:
 an indication of a network device to which the connectivity status message is being sent; and   an indication whether the network device sending the connectivity status message has received a connectivity status message from the network device to which the connectivity status message is being sent.   
     
     
         8 . The network device of  claim 7 , wherein the network device determines that bidirectional communication between the network device and the neighboring network device is maintained only when the connectivity status message indicates that the network device sending the connectivity status message has received a connectivity status message from the network device to which the connectivity status message is sent. 
     
     
         9 . The network device of  claim 1 , wherein each connectivity status message comprises:
 an indication of a network device to which the current connectivity status message is being sent; and   an indication whether the network device sending the connectivity status message has received a previous connectivity status message from the network device to which the current connectivity status message is being sent.   
     
     
         10 . The network device of  claim 9 , wherein the forwarding plane determines that communication between the network device and the neighboring network device is maintained only when the current connectivity status message indicates that the network device sending the connectivity status message has received a previous connectivity status message from the network device to which the connectivity status message is sent within the predetermined connectivity loss determination time interval. 
     
     
         11 . The network device of  claim 9 , wherein the forwarding plane determines that communication between the network device and the neighboring network device is maintained only when:
 the current connectivity status message is received from the neighboring network device within the predetermined time interval after network device sends a connectivity status message to the neighboring network device; and   the current connectivity status message indicates that the network device sending the connectivity status message has received a previous connectivity status message from the network device to which the connectivity status message is sent within the predetermined time interval.   
     
     
         12 . The network device of  claim 9 , wherein the indication whether the network device sending the connectivity status message has received a previous connectivity status message from the network device to which the current connectivity status message is being sent comprises a value in a field of the current connectivity status message which matches a number in a field of the previous connectivity status message. 
     
     
         13 . The network device of  claim 1 , wherein the forwarding plane is adapted: to send connectivity status messages to the neighboring network device comprising an indication that communication between the network device and the neighboring network device is maintained when the network device determines that communication between the network device and the neighboring network device is maintained; and to send no connectivity status messages to the neighboring network device when the network device determines that communication between the network device and the neighboring network device is not maintained. 
     
     
         14 . The network device of  claim 13 , wherein the forwarding plane is adapted to determine that communication between the network device and the neighboring network device is maintained based on receipt of a connectivity status message from the neighboring network device, the received connectivity status message comprising an indication that the neighboring network device received a previous connectivity status message from the network device. 
     
     
         15 . The network device of  claim 13 , wherein the forwarding plane is adapted to determine that communication between the network device and the neighboring network device is not maintained based on failure to receive a connectivity status message from the neighboring network device within a predetermined connectivity loss time interval. 
     
     
         16 . The network device of  claim 15 , wherein the connectivity loss time interval begins when a previous connectivity status message is received from the neighboring network device. 
     
     
         17 . The network device of  claim 13 , wherein the forwarding plane is adapted to send connectivity status messages to the neighboring network device which do not comprise an indication that communication has been maintained while the network device is determining whether communication has been established between the network device and the neighboring network device. 
     
     
         18 . The network device of  claim 13 , wherein the forwarding plane is adapted to send connectivity status messages to the neighboring network device which do not comprise an indication that bidirectional communication has been maintained between determining that the neighboring network device is a neighbor and receiving from the neighboring network device a first connectivity status message indicating that the neighboring network device has received a previous connectivity status message from the network device. 
     
     
         19 . The network device of  claim 1 , wherein the forwarding plane is adapted to transmit connectivity status messages to the neighboring network device at times separated by a transmit time interval. 
     
     
         20 . The network device of  claim 19 , wherein the transmit time interval is determined by negotiation with the neighboring network device. 
     
     
         21 . The network device of  claim 20 , wherein each of the network device and the neighboring network device indicates a preferred transmit time interval during the negotiation, and a largest of the preferred transmit time intervals is selected. 
     
     
         22 . The network device of  claim 21 , wherein, when each of the network device and the neighboring network device indicate the same preferred transmit time interval, that same preferred transmit time interval is selected. 
     
     
         23 . The network device of  claim 1 , wherein the forwarding plane is adapted to determine that communication between the network device and the neighboring network device is not maintained when no connectivity status message is received from the neighboring network device within a connectivity loss determination time interval. 
     
     
         24 . The network device of  claim 19 , wherein:
 the forwarding plane is adapted to determine that communication between the network device and the neighboring network device is not maintained when no connectivity status message is received from the neighboring network device within a connectivity loss determination time interval; and   the connectivity loss determination time interval is a function of the transmit time interval.   
     
     
         25 . The network device of  claim 24 , wherein the connectivity loss determination time interval is the transmit time interval multiplied by  3 . 
     
     
         26 . The network device of  claim 1 , wherein the forwarding plane is adapted to transmit connectivity status messages to the neighboring network device at times separated by a regular transmit time interval with an applied jitter. 
     
     
         27 . The network device of  claim 26 , wherein:
 the forwarding plane is adapted to determine that bidirectional communication between the network device and the neighboring network device is not maintained when no connectivity status message is received from the neighboring network device within a connectivity loss determination time interval; and   the connectivity loss determination time interval is a function of the transmit time interval and the applied jitter.   
     
     
         28 . The network device of  claim 1 , further comprising a control plane adapted to process packets for which previously resolved forwarding information is not stored at the network device. 
     
     
         29 . The network device of  claim 1 , further comprising a control plane adapted to resolve forwarding information for packets for which previously resolved forwarding information is not stored at the network device by communicating with other network devices.