Method and apparatus for the fast detection of connectivity loss between devices in a network

• US 8,396,950 B1
• Filed: 02/27/2001
• Issued: 03/12/2013
• Est. Priority Date: 03/02/2000
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Rockstar Consortium US LP (Rockstar Consortium Inc.)
• Inventors: Squire, Matthew, Cain, Bradley, Duncan, Ian, Sandick, Haldon, Haberman, Brian
• Primary Examiner(s): Pollack, Melvin H
• Application Number:
  US09/794,317
• Time in Patent Office: 4,396 Days
• Field of Search: 709223-225, 709227-230, 709/238, 709/242, 709/246, 709/245, 340/504, 370/242, 370/252, 370/395.3, 370/231, 370/235, 370/236, 370/254, 370/255, 370/395.1, 370/395.2
• US Class Current: 709/223
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 65/1069 Session establishment or de-establishment

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 device. The status inquiry messages are transmitted periodically to the at least one neighboring device. In addition, the network device may communicate an advertisement message over the control plane to discover the at least one neighboring network device prior to the communication of the status inquiry messages over the forwarding plane. The network devices may negotiate communication parameters for the exchange of status inquiry messages with the at least one network device.

Claims

1. A method including the steps of:

communicating a status by a network device to a neighboring network device in a network, the network device having a control plane and a forwarding plane, wherein the forwarding plane comprises a processing pathway in which packets are forwarded based on previously resolved forwarding information stored within the network device, and wherein the control plane comprises a processing pathway in which packets are processed so that forwarding information is resolved by communicating with other devices in the network, the step of communicating including the step of forwarding a connectivity status message indicating the status of the network device to the neighboring network device, the status message generated and communicated using the forwarding plane of the network device.

2. The method of claim 1, wherein the status message also includes information associated with the neighboring network device, including information regarding receipt of status inquiries from the neighboring network device.

3. The method according to claim 1, further including the steps of:

communicating an advertisement message including communication parameters to the neighboring network device using the control plane of the network device to permit discovery of the network device by the neighboring device.

4. The method according to claim 3 wherein the communication parameters include a frequency for forwarding the status messages.

5. The method according to claim 3 wherein the communication parameters include an interval defining a minimum frequency for re-transmission of status messages for indication of connectivity between the network device and the neighboring network device.

6. The method according to claim 3 wherein both the status message and the advertisement message are periodically re-transmitted and wherein the advertisement message is re-transmitted at a lower frequency than the status message.

7. The method of claim 1 wherein the network is an Internet Protocol (IP) subnet.

8. A method including the steps of:

receiving, at a network device in a network, a connectivity status message generated and communicated by a forwarding plane of a neighboring network device, the status message including data indicating the status of the neighboring network device, wherein the forwarding plane comprises a processing pathway in which packets are forwarded based on previously resolved forwarding information stored within the neighboring network device.

9. The method of claim 8, wherein the status message also includes information associated with the neighboring network device including information regarding receipt of status inquiries from the network device.

10. The method of claim 8 including the step of receiving, at the network device, an advertisement message from a control plane of the neighboring network device, wherein the advertisement message enables the network device to discover the neighboring device, and wherein the advertisement message includes communication parameters associated with the neighboring network device.

11. The method of claim 10, wherein a receive frequency of the status messages at the network device is higher than a receive frequency of the advertisement messages at the network device.

12. The method according to claim 10 wherein the communication parameters include a frequency for forwarding the status messages.

13. The method according to claim 10 wherein the communication parameters include an interval identifying a time period between receipts of status messages at which it is determined that connectivity between the neighboring network device and the network device is lost.

14. The method according to claim 8 including:

upon receipt of the status message, starting a timer;

determining that a connection with the neighboring network device is lost if another status message is not received before the expiration of the timer.

15. The method of claim 8 wherein the network is an IP subnet.

16. A network device comprising:

a control plane and a forwarding plane, wherein the forwarding plane comprises a processing pathway in which packets are forwarded based on previously resolved forwarding information stored within the network device, and wherein the control plane comprises a processing pathway in which packets are processed so that forwarding information can be resolved by communicating with other devices in the network, the forwarding plane generating and communicating, to a neighboring network device, a connectivity status message indicating the status of the network device.

17. The network device of claim 16, wherein the status message also includes information associated with the neighboring network device including information regarding receipt of status inquiries from the neighboring network device.

18. The network device of claim 16, wherein the control plane of the network device is for forwarding advertisement messages to the neighboring network device to enable discovery of the network device, wherein the advertisement messages include communication parameters associated with the network device.

19. A network device of claim 18, wherein the communication parameters include a frequency for forwarding the status messages.

20. The network device of claim 18 wherein the communication parameters include an interval identifying a time period between status messages at which it is determined that connectivity between the neighboring network device and the network device is lost.

21. The network device of claim 18 wherein both the status message and the advertisement message are periodically re-transmitted and wherein the advertisement message is re-transmitted at a lower frequency than the status message.

22. A network including the network device of claim 16, wherein the network is an Internet Protocol (IP) subnet.

23. A network device including:

a control plane and a forwarding plane, wherein the forwarding plane comprises a processing pathway in which packets are forwarded based on previously resolved forwarding information stored within the network device, and wherein the control plane comprises a processing pathway in which packets are processed so that forwarding information can be resolved by communicating with other devices in the network, the forwarding plane receiving a connectivity status message generated and communicated by a forwarding plane of a neighboring network device, the status message including data indicating the status of the neighboring network device.

24. The network device of claim 23 wherein the status message also includes information associated with the network device including information regarding receipt of status inquiries from the neighboring network device.

25. The network device of claim 23 wherein the control plane is adapted to receive an advertisement message from a control plane of a neighboring network device, wherein the advertisement message enables the network device to discover the neighboring network device, and wherein the advertisement message includes communication parameters associated with the neighboring network device.

26. The network device of claim 25, wherein a receive frequency of the status messages at the network device is higher than a receive frequency of the advertisement messages at the network device.

27. The network device of claim 25 wherein the communication parameters include a frequency for forwarding the status messages.

28. The network device of claim 25 wherein the communication parameters include an interval identifying a time period between receipts of status messages at which it is determined that connectivity between the neighboring network device and the network device is lost.

29. A network including the network device of claim 23, wherein the network is an IP subnet.

30. A computer program product for use on a network device in a network, the network device having a forwarding plane and a control plane, wherein the forwarding plane comprises a processing pathway in which packets are forwarded based on previously resolved forwarding information stored within the network device, and wherein the control plane comprises a processing pathway in which packets are processed so that forwarding information can be resolved by communicating with other devices in the network, the computer program product comprising a computer usable medium having computer readable program code thereon, the computer readable program code comprising:

program code that communicates the status of the network device to the network, including program code that generates and communicates a connectivity status message to a neighboring network device via the forwarding plane, the program code operating independent of the control plane,

the status message including data indicating the status of the network device.

31. The computer program product of claim 30, wherein the status messages includes information associated with the neighboring network device including information regarding receipt of status inquiries from the neighboring network device.

32. The computer program product as defined by claim 30, further comprising program code for communicating an advertisement message over the control plane of the network device to enable discovery of the network device by the neighboring network device, the advertisement message including communications parameters associated with the network device.

33. The computer program product as defined by claim 32 wherein both the status message and the advertisement message are periodically retransmitted, and wherein the status messages are retransmitted at a higher frequency than the advertisement messages.

34. The computer program product as defined by claim 30, wherein the network device is one node in an Internet Protocol subnet.

35. An apparatus for communicating a status of a network device in a network, comprising:

a forwarding plane including a processing pathway in which packets are forwarded based on previously resolved forwarding information stored within the network device;

a control plane including a processing pathway in which packets are processed so that forwarding information is resolved by communicating with other devices in the network; and

means for communicating a connectivity status message over the forwarding plane to a neighboring network device, the status message including data indicating the status of the network device and being generated by the forwarding plane.

36. The apparatus of claim 35 wherein the status message includes information associated with the neighboring network device including information regarding receipt of status inquiries from the neighboring network device.

37. The apparatus as defined by claim 35 further comprising means for forwarding an advertisement message to the neighboring network device using the control plane to enable discovery of the network device by the neighboring network device, the advertisement message including communication parameters associated with the network device.

38. The apparatus as defined in claim 37 wherein the communication parameters include a frequency for forwarding the status message.

39. The apparatus according to claim 37 wherein the communication parameters include an interval identifying a time period between receipts of status messages at which it is determined that connectivity between the neighboring network device and the network device is lost.

40. The apparatus of claim 37, wherein the status messages and advertisement messages are periodically re-transmitted, and wherein the status message is re-transmitted at a higher frequency than the advertisement message.

41. A method comprising:

forwarding, using a control plane of a network device, an advertisement message to a neighboring network device, the advertisement message including communication parameters associated with the network device;

receiving, by the network device in response to the advertisement message, a reply advertisement message from the neighboring network device, the reply advertisement message including communication parameters associated with the neighboring network device;

generating and communicating, using a forwarding plane of the network device, connectivity status messages to the neighboring network device, the status messages indicating a status of the network device,

wherein the forwarding plane comprises a processing pathway in which packets are forwarded based on previously resolved forwarding information stored within the network device, and wherein the control plane comprises a processing pathway in which packets are processed so that forwarding information can be resolved by communicating with other devices in the network.

42. The method according to claim 41, further including the step of the neighboring network device and network device negotiating a transmission frequency for re-transmission of the status messages including information regarding receipt of status inquiries from the neighboring network device.

43. The method according to claim 41, wherein the status messages include information associated with the neighboring network device.

44. A method comprising the steps of:

receiving, at a network device in a network, from a control plane of a neighboring network device, an advertisement message including communication parameters associated with the neighboring network device;

replying to the advertisement message to indicate discovery of the neighboring network device; and

receiving, from a forwarding plane of the neighboring network device, connectivity status messages, the status messages indicating a status of the neighboring network device and being communicated by the forwarding plane,

wherein the forwarding plane comprises a processing pathway in which packets are forwarded based on previously resolved forwarding information stored within the neighboring network device, and wherein the control plane comprises a processing pathway in which packets are processed so that forwarding information can be resolved by communicating with other devices in the network.

45. The method of claim 44 including the steps of:

determining, in response to the communication parameters associated with the neighboring network device and communication parameters associated with the network device, a negotiated transmission frequency of the status messages; and

determining that a connection to the neighboring network device has failed if a rate of receipt of the status messages falls below the negotiated transmission frequency.

46. The method of claim 44, wherein the status messages include information associated with the network device including information regarding receipt of status inquiries from the network device.