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

• US 20030095504A1
• Filed: 12/01/2000
• Published: 05/22/2003
• Est. Priority Date: 09/12/2000
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Ogier, Richard G.
• Granted Patent: US 7,031,288 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• 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. In a network having a plurality of nodes, a method for discovering a neighbor node comprising:

receiving from a neighbor node a neighbor discovery message;

periodically transmitting a predetermined number of neighbor discovery messages that each include an identity of the neighbor node in response to the received neighbor discovery message; and

after transmitting the predetermined number of neighbor discovery messages, transmitting 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.

2. The method of claim 1 further comprising determining that the neighbor node is in a lost state if a message used for neighbor node discovery is not received from the neighbor node within a predetermined time period.

3. The method of claim 2 wherein the predetermined time period has a duration that approximately equals the duration of a time interval between subsequent transmissions of neighbor discovery messages multiplied by the predetermined number.

4. The method of claim 1 wherein each periodically transmitted neighbor discovery message includes a list of neighbor nodes that are identified as being in a heard state within a predetermined time period.

5. The method of claim 1 further comprising identifying the neighbor node as being in a symmetric state if a neighbor discovery message received by a particular node includes an identity of the particular node in a list of neighbor nodes identified by the neighbor node as being in a heard state.

6. The method of claim 5 further comprising subsequently transmitting by the particular node a neighbor discovery message that omits the identity of the neighbor node from that neighbor discovery message in response to identifying the neighbor node as being in the symmetric state.

8. The method of claim 1 wherein each transmitted neighbor discovery message includes a list of neighbor nodes that are identified as being in a heard state and a list of neighboring nodes that are identified as being in a lost state.

9. The method of claim 8 wherein each transmitted neighbor discovery message includes a list of neighboring nodes that are identified as being in a symmetric state.

7. The method of clam 5 further comprising subsequently transmitting by the particular node a neighbor discovery message that includes the identity of the neighbor node so that other nodes in the network can identity the neighbor node as having established a symmetric link with the particular node.

10. A network comprising:

a node (i) receiving from a neighbor node a neighbor discovery message, (ii) periodically transmitting a predetermined number of neighbor discovery messages that each include an identity of the neighbor node in response to the received neighbor discovery message, and (iii) after transmitting the predetermined number of neighbor discovery messages, transmitting 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.