MAINTAINING AND COMMUNICATING NODAL NEIGHBORING INFORMATION

• US 20140108643A1
• Filed: 10/16/2012
• Published: 04/17/2014
• Est. Priority Date: 10/16/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Hong, Wei, Vasseur, Jean-Philippe
• Granted Patent: US 9,712,433 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

In one embodiment, a nodal device receives information from each of its neighboring nodes in a network. The information identifies a link quality between the nodal device and each of its neighboring nodes. The link quality information is stored in one or more bloom filters in the nodal device such that a table having a compressed format is provided in the bloom filter. The table includes probabilistic identifiers to identify link quality between the nodal device and each of its neighboring nodes.

Claims

1. A Method, Comprising:

receiving information in a nodal device from each of its neighboring nodes in a network wherein the information identifies a link quality between the nodal device and each of the neighboring nodes; and

storing the link quality information using one or more bloom filters in the nodal device such that a table is provided in the using one or more bloom filters using probabilistic identifiers to identify link quality between the nodal device and each of its neighboring nodes.

2. A method as recited in claim 1, wherein the network is a Low Power and Lossy Network.

3. A method as recited in claim 1, wherein information is received from neighboring nodes only 1-hop away from the nodal device.

4. A method as recited in claim 1, wherein the information identifying link quality received at the nodal device includes a 64-bit extended unique identifier (EUI-64) signal.

5. A method as recited in claim 1, wherein a set of N bloom filters is provided in the nodal device with N being equal or greater than 2.

6. A method as recited in claim 5, wherein link quality information is stored using N bloom filters during a predetermined time period after which link quality information is stored using a different bloom filter in the set of N bloom filters for a predetermined time period.

7. A method as recited in claim 6, wherein link quality information is stored using a different bloom filter according to a predetermined sequence of the N bloom filters.

8. A method as recited in claim 6 wherein the nodal device performs a bitwise OR operation on the set of N bloom filters to provide a unified view of all neighboring nodes.

9. A method as recited in claim 5 wherein the nodal device adaptively adjusts a bit-vector size for each of its N bloom filters based upon a number of neighboring nodes it has added to each of its N bloom filters.

10. A method as recited in claim 1, further including the step of the nodal device determining a signal quality of a recent signal transmission to a neighboring 1-hop node by querying the identifier of the nodal device as stored in the one or more bloom filters.

11. A method as recited in claim 10, wherein the identifier of the nodal device as stored in the one or more bloom filters was determined via an advertisement message.

12. A method as recited in claim 1, wherein the nodal device transmits information from the one or more bloom filters to a Network Management System (NMS).

13. A method as recited in claim 12, wherein in predetermined time intervals, the nodal device transmits information stored in the one or more bloom filters to the NMS.

14. A method, comprising:

receiving in a Network Management System (NMS) for a network having nodal devices coupled via communication links, information from a bloom filter provided in one of the nodal devices wherein the information identifies link qualities between the nodal device and each neighboring node in the network; and

interpolating in the NMS the received information from the bloom filter to determine a status of the communication links coupling the nodal devices in the network.

15. A method as recited in claim 14 further including the step of the NMS querying a bloom filter of a nodal device in the network to determine the presence of nodes which neighbor the nodal device.

16. An apparatus, comprising:

one or more network interfaces to communicate with a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

receive, as a nodal device, information from neighboring network nodes wherein the information identifies a link quality between the nodal device and each of the neighboring nodes; and

store the link quality information in a nodal device, such that a table is provided in the bloom filter using probabilistic identifiers to identify link quality between the nodal device and each of its neighboring nodes.

17. An apparatus as recited in claim 16, wherein the nodal device is provided with N bloom filters with N being greater than or equal to 2, and wherein the process when executed is further operable to store the link quality information in one of the N bloom filters during a predetermined time period after which link quality information is stored in a different bloom filter in one the N bloom filters for a predetermined time period.

18. An apparatus as recited in claim 17 wherein link quality information is stored in a different bloom filter according to a predetermined sequence of the N bloom filters.

19. An apparatus as recited in claim 16, wherein the process when executed is further operable to determine a signal quality of a recent signal transmission from a nodal device to a neighboring 1-hop node by querying the identifier of the nodal device as stored in the bloom filter.

20. An apparatus as recited in claim 19 wherein the identifier of the nodal device as stored in the bloom filter was determined via an advertisement message.

21. An apparatus as recited in claim 16, wherein the process when executed is further operable to transmit information from the bloom filter to a Network Management System (NMS).

22. An apparatus as recited in claim 21, wherein the process when executed is further operable to transmit information stored in the bloom filter to the NMS in predetermined time intervals.

23. An apparatus, comprising:

one or more network interfaces to communicate with a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

receive, as a Network Management System (NMS), information from a bloom filter provided in a nodal device wherein the information identifies link qualities between the nodal device and each of its neighboring node in a network; and

interpolate the received information from the bloom filter to determine a status for communication links coupling nodal devices in the network.

24. An apparatus as recited in claim 23, wherein the process when executed is further operable to query a bloom filter of a nodal device in the network to determine the presence of nodes which neighbor the nodal device.