Maintaining and communicating nodal neighboring information

• US 9,712,433 B2
• Filed: 10/16/2012
• Issued: 07/18/2017
• 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
• Primary Examiner(s): Pollack, Melvin H
• Assistant Examiner(s): Gebre, Messeret f
• Application Number:
  US13/653,037
• Publication Number:
  US 20140108643A1
• Time in Patent Office: 1,736 Days
• Field of Search: 709224, 709238, 709242
• 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 at a nodal device from a plurality of neighboring nodes of the nodal device in a computer network, the information including identifiers of each of the plurality of neighboring nodes;

maintaining a list of 1-hop neighbor nodes at the nodal device by adding the identifiers for each of the plurality of neighboring nodes to a first bloom filter;

storing the bloom filter on the nodal device, the first bloom filter made up of the identifiers for each of the neighboring nodes of the computer network received during a time period;

phasing out 1-hop neighbor nodes that are no longer 1-hop neighbor nodes by, upon the time period expiring, adding any identifiers received after the time period expires to a second bloom filter while continuing to store the first bloom filter on the nodal device until a predetermined amount of time has passed;

getting a unified view of all neighboring nodes of the plurality of neighboring nodes by performing a function on the first bloom filter and the second bloom filter;

transmitting the unified view from the first and second bloom filter to a Network Management System (NMS); and

managing a false positive rate of the first or second bloom filter at the nodal device relative to a number of nodes that neighbor the nodal device by adaptively adjusting a bit-vector size of the first or second bloom filter depending on a number of neighboring nodes added to the first or second bloom filter.

2. A method as recited in claim 1, wherein:

the information received from the plurality of neighboring nodes include link quality information,

one or more nodes of the plurality of neighboring nodes having a first link quality are added to the first bloom filter, and

one or more nodes of the plurality of nodes having a second link quality are added to a different bloom filter.

3. A method as recited in claim 1, wherein the identifiers of the plurality of neighboring nodes are stored using a different bloom filter according to a predetermined sequence of N bloom filters.

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

5. A method as recited in claim 1, further comprising 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 at least the first and second bloom filters.

6. A method as recited in claim 5, wherein the unified view of the first and second bloom filter is advertised to one or more of the plurality of neighboring nodes at least one hop away.

7. A method as recited in claim l, wherein in predetermined time intervals, the nodal device transmits information stored in the first and second bloom filter to the NMS.

8. A method, comprising:

receiving at a Network Management System (NMS) for a network having nodal devices coupled via communication links, a unified view of all neighboring nodes of a plurality of neighboring nodes of at least one nodal device in the network which the NMS manages, the unified view obtained from a first and at least second bloom filter maintained in the at least one nodal device, wherein a false positive rate of the first or the at least second bloom filter at the nodal device is managed relative to a number of nodes that neighbor the at least one nodal device;

using the unified view to determine what nodes are likely reachable to each individual node by interpolating at the NMS the received information from the bloom filter to determine a status of the communication links coupling the nodal devices in the network; and

querying, by the NMS, a bloom filter of the at least one nodal device in the network to determine the presence of nodes which neighbor the nodal device.

9. 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 information at the apparatus from a plurality of neighboring nodes of the apparatus, the information including identifiers of each of the plurality of neighboring nodes;

maintain a list of 1-hop neighbor nodes at the nodal device by adding the identifiers for each of the plurality of neighboring nodes to a first bloom filter;

store the bloom filter on the apparatus, the first bloom filter made up of the identifiers for each of the neighboring nodes of the computer network received during a time period;

phasing out 1-hop neighbor nodes that are no longer 1-hop neighbor nodes by, upon the time period expiring, adding any identifiers received after the time period expires to a second bloom filter while continuing to store the first bloom filter on the nodal device until a predetermined amount of time has passed;

getting a unified view of all neighboring nodes of the plurality of neighboring nodes by performing a function on the first bloom filter and the second bloom filter;

transmitting the unified view from the first and second bloom filter to a Network Management System (NMS); and

managing a false positive rate of the first or second bloom filter at the nodal device relative to a number of nodes that neighbor the nodal device by adaptively adjusting a bit-vector size of the first or second bloom filter depending on a number of neighboring nodes added to the first or second bloom filter.

10. An apparatus as recited in claim 9 wherein the identifiers of the plurality of neighboring nodes are stored using a different bloom filter according to a predetermined sequence of N bloom filters.

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

12. An apparatus as recited in claim 11 wherein a unified view of the first and second bloom filters is advertised to one or more of the plurality of neighboring nodes at least one hop away.

13. An apparatus as recited in claim 9, wherein the process when executed is further operable to transmit information stored in the first and second bloom filter to the NMS in predetermined time intervals.

14. 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, at a Network Management System (NMS) for a network having nodal devices coupled via communication links, a unified view of all neighboring nodes of a plurality of neighboring nodes of at least one nodal device in the computer network which the NMS manages, the unified view obtained from a first and at least second bloom filter maintained in the at least one nodal device, wherein a false positive rate of the first or the at least second bloom filter at the nodal device is managed relative to a number of nodes that neighbor the at least one nodal device;

using the unified view to determine what nodes are likely reachable to each individual node by interpolating at the NMS the received information from the bloom filter to determine a status of the communication links coupling the nodal devices in the network; and

query a bloom filter of the at least one nodal device in the network to determine the presence of nodes which neighbor the nodal device.