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:
 at least one line card, at least one line card comprising:   at least one interface for communicating with a neighboring network device;   at least one processor; and   at least one processor-readable medium storing instructions for execution by the at least one processor, the instructions comprising:   instructions executable to forward packets to the neighboring network device via the at least one interface based on previously resolved forwarding information stored at the line card;   instructions executable to generate and communicate, with the neighboring network device via the at least one interface, connectivity status messages; and   instructions executable 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 at least one line card comprises at least one digital signal processor. 
     
     
         3 . The network device of  claim 1 , wherein at least one line card comprises at least one application specific integrated circuit (ASIC). 
     
     
         4 . The network device of  claim 1 , wherein at least one line card comprises at least one field programmable gate array (FPGA). 
     
     
         5 . The network device of  claim 1 , wherein the at least one processor-readable medium comprises at least one read only memory (ROM). 
     
     
         6 . The network device of  claim 1 , wherein the instructions comprise instructions executable 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. 
     
     
         7 . The network device of  claim 6 , wherein the instructions executable 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 comprise:
 instructions executable to start a timer when a connectivity status message is received from the neighboring network device; and   instructions executable 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 when a subsequent connectivity status message is received from the neighboring network device before the timer expires.   
     
     
         8 . The network device of  claim 1 , wherein the instructions comprise instructions executable 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. 
     
     
         9 . The network device of  claim 8 , wherein the predetermined time interval begins when a last connectivity status message is received from the neighboring network device. 
     
     
         10 . The network device of  claim 9 , wherein the instructions executable to determine that no successive connectivity status message is received from the neighboring network device within the predetermined time interval comprise:
 instructions executable to start a timer when a connectivity status message is received from the neighboring network device; and   instructions executable to determine 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.   
     
     
         11 . 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.   
     
     
         12 . The network device of  claim 11 , wherein a line card 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. 
     
     
         13 . The network device of  claim 1 , wherein the instructions executable to generate and communicate, with a neighboring network device, connectivity status messages comprise instructions to transmit the connectivity status messages at times separated by a transmit time interval. 
     
     
         14 . The network device of  claim 13 , wherein the transmit time interval is determined by negotiation with the neighboring network device. 
     
     
         15 . The network device of  claim 1 , wherein the instructions executable to determine, based on the communicated connectivity status messages, that bidirectional communication between the network device and the neighboring network device is maintained comprise instructions executable 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. 
     
     
         16 . The network device of  claim 12 , wherein:
 the instructions executable to determine, based on the communicated connectivity status messages, that bidirectional communication between the network device and the neighboring network device is maintained comprise instructions executable 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.   
     
     
         17 . The network device of  claim 16 , wherein the connectivity loss determination time interval is the transmit time interval multiplied by 3. 
     
     
         18 . The network device of  claim 1 , wherein the instructions executable to generate and communicate, with a neighboring network device, connectivity status messages comprise instructions executable to transmit connectivity status messages to the neighboring network device at times separated by a regular transmit time interval with an applied jitter. 
     
     
         19 . The network device of  claim 18 , wherein:
 the instructions executable to determine, based on the communicated connectivity status messages, that bidirectional communication between the network device and the neighboring network device is maintained comprise instructions executable 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 and the applied jitter.   
     
     
         20 . The network device of  claim 1 , further comprising a control plane, the control plane comprising:
 at least one control plane interface for coupling the control plane to the line cards;   at least one control plane processor; and   at least one processor-readable medium storing instructions for execution by the at least one control plane processor, the instructions comprising instructions executable to process packets received via the interfaces for which previously resolved forwarding information is not stored in the at least one line card.   
     
     
         21 . The network device of  claim 20 , wherein the instructions executable to process packets received via the interfaces for which previously resolved forwarding information is not stored in the at least one line card comprise instructions executable to process packets to resolve forwarding information by communicating with other network devices via the interfaces. 
     
     
         22 . The network device of  claim 20 , wherein the instructions executable by the at least one control plane processor comprise instructions executable to process a routing protocol. 
     
     
         23 . The network device of  claim 20 , wherein the instructions executable by the at least one control plane processor comprise instructions executable to discover neighboring network devices and to identify the discovered neighboring network devices to the line cards via the at least one control plane interface. 
     
     
         24 . The network device of  claim 23 , wherein the instructions executable by the at least one control plane processor comprise instructions executable to discover neighboring network devices by:
 receiving advertisement messages from neighboring network devices; and   determining that the received advertisement messages identify the network device.   
     
     
         25 . The network device of  claim 24 , wherein the instructions executable by the at least one control plane processor comprise instructions executable to multicast a solicitation message on a network upon becoming active on the network, the solicitation message identifying the network device. 
     
     
         26 . The network device of  claim 25 , wherein the instructions executable by the at least one control plane processor comprise instructions executable:
 to receive a solicitation message from a neighboring network device, the solicitation message identifying the neighboring network device; and   responsive to receipt of the solicitation message identifying the neighboring network device, to send an advertisement message to the neighboring network device, the advertisement message identifying the network device and the neighboring network device.   
     
     
         27 . The network device of  claim 20 , wherein the instructions executable by the at least one control plane processor comprise instructions executable to negotiate at least one operating parameter with the discovered neighboring network devices. 
     
     
         28 . The network device of  claim 27 , wherein the at least one operating parameter comprises a transmit time interval. 
     
     
         29 . The network device of  claim 28 , wherein the instructions executable by the at least one control plane processor comprise instructions executable to exchange respective preferred transmit time intervals with a neighboring network device and to select a largest of the preferred transmit time intervals. 
     
     
         30 . The network device of  claim 29 , wherein the instructions executable by the at least one control plane processor comprise instructions executable when each of the network device and the neighboring network device indicate the same preferred transmit time interval, to select that same preferred transmit time interval.