Reduced-overhead protocol for discovering new neighbor nodes and detecting the loss of existing neighbor nodes in a network

• US 7,031,288 B2
• Filed: 12/01/2000
• Issued: 04/18/2006
• Est. Priority Date: 09/12/2000
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Ogier, Richard G.
• Primary Examiner(s): Sam, Phirin
• Application Number:
  US09/728,192
• Publication Number:
  US 20030095504A1
• Time in Patent Office: 1,964 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/235, 370/238, 370/248, 370/252, 370/254, 370/256, 370/257, 370/258, 370/278, 370/310.2, 370/312, 370/315, 370/329, 370/331, 370/332, 370/335, 370/338, 370/346, 370/350, 370/377, 370/384, 370/402, 370/255, 370/399, 370/395.32, 370/228, 370/400, 370/410, 370/448, 370/477, 370/342, 370/401, 370/408, 370/440, 370/496, 370/282, 370/432, 370/491, 370/328, 370/351, 370/352, 370/392, 370/395.52, 370/437, 370/465, 370/468, 370/469, 370/397, 370/313, 370/353, 370/354, 370/386, 370/389, 370/395.31, 370/404, 370/405, 370/439, 375/133, 375/225, 455/73, 455/343.3, 455/519, 455/574, 709/220, 709/224, 709/238, 709/250, 709/477, 709/200, 709/223, 709/242, 710/100, 710/104
• US Class Current: 370/338
• CPC Class Codes: H04L 1/1614 using bitmaps
• CPC Class Codes: H04L 1/1887 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/167 Adaptation for transition between two IP versions, e.g. between IPv4 and IPv6 translation of Internet protocol [IP] addresses H04L61/2503
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 80/04 Network layer protocols, e.g. mobile IP [Internet Protocol]

Abstract

A protocol for discovering a new neighbor node and detecting the loss of an existing neighbor node in a network is described. A node receives a neighbor discovery message from a neighbor node. The node receiving the neighbor discovery message periodically transmits a predetermined number of neighbor discovery messages in response to the received neighbor discovery message. Each neighbor discovery message includes an identity of the neighbor node. After transmitting the predetermined number of neighbor discovery messages, the node transmits neighbor discovery messages that omit the identity of the neighbor node until another neighbor discovery message is received from the neighbor node that indicates a change in a communications state associated with the neighbor node.

Claims

1. A method of operating a network having a plurality of nodes, comprising:

maintaining in a receiving node a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node;

receiving a HELLO message containing an address of a new sending node;

transmitting a NEIGHBOR message that includes an address of the receiving node to said new sending node;

receiving a NEIGHBOR ACK message from said new sending node;

updating said neighbor table to reflect discovery of said new sending node and communication status of said new sending node; and

transmitting at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a lost status, wherein a neighbor node is determined to be in the lost status when a HELLO message containing the address of that neighbor node has not been heard by the receiving node in a predetermined period of time.

2. The method of claim 1, wherein the predetermined period of time corresponds to a HELLO-INTERVAL period multiplied by a predetermined number K.

3. The method of claim 1, further comprising subsequently transmitting at least one HELLO message containing the address of the receiving node but not the address of a neighbor node that was previously in the list of neighbor nodes in the lost state.

4. The method of claim 1, further comprising subsequently transmitting at least one HELLO message containing a list of neighbor nodes in a lost status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a heard status.

5. The method of claim 1, further comprising subsequently transmitting at least one HELLO message containing a list of neighbor nodes in a lost status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a symmetric status.

6. The method of claim 1, further comprising subsequently transmitting at least one HELLO message containing a list of neighbor nodes in a symmetric status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a heard status.

7. A network having a plurality of nodes, comprising:

a new sending node; and

a receiving node having a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node, wherein said receiving node receives a HELLO message from said new sending node containing an address of said new sending node, wherein said receiving node transmits a NEIGHBOR message that includes an address of the receiving node to said new sending node, wherein said receiving node receives a NEIGHBOR ACK message from said new sending node, wherein said receiving node updates said neighbor table to reflect discovery of said new sending node and communication status of said new sending node, wherein said receiving node transmits at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, and wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a lost status, wherein a neighbor node is determined to be in the lost status when a HELLO message containing the address of that neighbor node has not been heard by the receiving node in a predetermined period of time.

8. The network of claim 7, wherein the predetermined period of time corresponds to a HELLO-INTERVAL period multiplied by a predetermined number K.

9. The network of claim 7, wherein said receiving node subsequently transmits at least one HELLO message containing the address of the receiving node but not the address of a neighbor node that was previously in the list of neighbor nodes in the lost state.

10. The network of claim 7, wherein said receiving node subsequently transmits at least one HELLO message containing a list of neighbor nodes in a lost status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a heard status.

11. The network of claim 7, wherein said receiving node subsequently transmits at least one HELLO message containing a list of neighbor nodes in a lost status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a symmetric status.

12. The network of claim 7, wherein said receiving node subsequently transmits at least one HELLO message containing a list of neighbor nodes in a symmetric status, wherein that list of neighbor nodes includes a neighbor node that was in a previous list of neighbor nodes in a heard status.

13. A method of operating a network having a plurality of nodes, comprising:

maintaining in a receiving node a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node;

receiving a HELLO message containing an address of a new sending node;

transmitting a NEIGHBOR message that includes an address of the receiving node to said new sending node;

receiving a NEIGHBOR ACK message from said new sending node;

updating said neighbor table to reflect discovery of said new sending node and communication status of said new sending node; and

transmitting at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a heard status, wherein neighbor nodes in the heard status have been heard by the receiving node but have not been determined to have heard a previous HELLO message from the receiving node.

14. A method of operating a network having a plurality of nodes, comprising:

maintaining in a receiving node a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node;

receiving a HELLO message containing an address of a new sending node;

transmitting a NEIGHBOR message that includes an address of the receiving node to said new sending node;

receiving a NEIGHBOR ACK message from said new sending node;

updating said neighbor table to reflect discovery of said new sending node and communication status of said new sending node; and

transmitting at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a symmetric status, wherein neighbor nodes in the symmetric status have been heard by the receiving node and have been determined to have heard a previous HELLO message from the receiving node.

15. A network having a plurality of nodes, comprising:

a new sending node; and

a receiving node having a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node, wherein said receiving node receives a HELLO message from said new sending node containing an address of said new sending node, wherein said receiving node transmits a NEIGHBOR message that includes an address of the receiving node to said new sending node, wherein said receiving node receives a NEIGHBOR ACK message from said new sending node, wherein said receiving node updates said neighbor table to reflect discovery of said new sending node and communication status of said new sending node, wherein said receiving node transmits at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, and wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a heard status, wherein neighbor nodes in the heard status have been heard by the receiving node but have not been determined to have heard a previous HELLO message from the receiving node.

16. A network having a plurality of nodes, comprising:

a new sending node; and

a receiving node having a neighbor table comprised of each known neighbor node of the receiving node and the communication status of each known neighbor node, wherein said receiving node receives a HELLO message from said new sending node containing an address of said new sending node, wherein said receiving node transmits a NEIGHBOR message that includes an address of the receiving node to said new sending node, wherein said receiving node receives a NEIGHBOR ACK message from said new sending node, wherein said receiving node updates said neighbor table to reflect discovery of said new sending node and communication status of said new sending node, wherein said receiving node transmits at least one HELLO message comprising only a list of neighbor nodes that have communication status changes, and wherein each of said at least one HELLO message includes the address of the receiving node and a list of neighbor nodes that have their communication status changed to a symmetric status, wherein neighbor nodes in the symmetric status have been heard by the receiving node and have been determined to have heard a previous HELLO message from the receiving node.