Compressing data packet routing information using bloom filters

• US 9,300,569 B2
• Filed: 07/31/2012
• Issued: 03/29/2016
• Est. Priority Date: 07/31/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Vasseur, Jean-Philippe, Hong, Wei
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US13/563,077
• Publication Number:
  US 20140036925A1
• Time in Patent Office: 1,337 Days
• Field of Search: 370/400, 370/392, 370/395.3, 370/395.31, 370/395.32
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1756 based on delta files
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation

Abstract

In one embodiment, a Transit Information Bloom Filter (TIBF) signal component is generated for use with a routing protocol control message, the TIBF signal component identifying at least one parent node for a corresponding routing topology. The TIBF signal component is encoded in a generated Bloom filter. The parameters of the generated Bloom filter are based at least on one parent node to be encoded and a desired false positive rate for the Bloom filter. The address for each parent node is also encoded in the Bloom filter.

Claims

1. A method, comprising:

generating, at a node in a network, a Transit Information Bloom Filter (TIBF) signal component for use within a routing protocol control message;

encoding the TIBF signal component in a Bloom filter at the node, wherein the TIBF signal component in the Bloom filter at the node identifies a plurality of parent nodes for a routing topology;

generating the Bloom filter at the node by;

determining Bloom filter parameters based on a number of said plurality of parent nodes to be encoded;

determining a desired false positive rate for the Bloom filter at the node; and

encoding an address for each parent node of said plurality of parent nodes in the Bloom filter at the node; and

sending the TIBF signal component toward a root of the node in the network, wherein the root of the node derives the routing topology from information within the TIBF signal component.

2. The method of claim 1, wherein the determined Bloom filter parameters are based on a plurality of parent nodes.

3. The method of claim 2, further including generating a Transit Option signal component identifying preferred parents wherein the TIBF signal component identifies alternative parents, and encoding each of the Transit Option signal component and the TIBF signal component in the Bloom filter.

4. A method, comprising:

receiving, at a Directed Acyclic Graph (DAG) root node in a computer network, a Transit Information Bloom Filter (TIBF) signal component from a plurality of nodes in the computer network; and

interpolating, by the DAG root node, the TIBF signal component to derive a routing topology,

wherein the TIBF signal component is used within a routing protocol control message,

wherein the TIBF signal component and a TIBF signal are encoded in a Bloom filter, and the TIBF signal component in the Bloom filter identifies a plurality of parent nodes for the routing topology, and

wherein the Bloom filter is generated by each node of the plurality of nodes in the computer network by;

determining Bloom filter parameters based on a number of the plurality of parent nodes to be encoded,

determining a desired false positive rate for the Bloom filter, and

encoding an address for each parent node of the plurality of parent nodes in the Bloom filter.

5. The method of claim 4, wherein the DAG root node predetermines hash values for the Bloom filter for each node identified by a Transit Option signal component.

6. The method of claim 4, wherein the DAG root node identifies an address of each device in the routing topology.

7. The method of claim 4 wherein links are added to the DAG root node contingent upon the TIBF signal.

8. The method of claim 7, whereby the DAG root node queries the Bloom filter for each device in correlation with adding links.

9. The method of claim 8, wherein the DAG root node adds a link once a query provides a positive result.

10. The method of claim 8, wherein a false positive result in the Bloom filter is indicative of having more than a value N of positive queries when only a value N of entries are encoded in the Bloom filter.

11. The method of claim 8, further comprising adding a field to the TIBF signal component indicative of a number of entries included in the Bloom filter to detect a false positive occurrence attributable to the Bloom filter.

12. The method of claim 11, wherein if a number of positive queries exceeds the number of entries than a determination of existence of false positives is provided.

13. The method of claim 11, whereby upon the determination of false positives, the DAG root node provides feedback to each device enabling each device to adjust the size of the Bloom filter.

14. The method of claim 13, wherein the DAG root node propagates a desired number of bits to use per entry in a bit-vector field of the Bloom filter.

15. The method of claim 13, wherein the DAG root node indicates a number of nodes in a network enabling devices to adjust a bit-vector field of the Bloom filter based on the number of nodes.

16. The method of claim 11, whereby upon the determination of false positives the DAG root node corrects link errors.

17. An apparatus, comprising:

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

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

a memory configured to store a process executable by the processor, the one or more processes when executed operable to;

generate a Transit Information Bloom Filter (TIBF) signal component for use within a routing protocol control message wherein the TIBF signal component identifies a plurality of parent nodes for a routing topology;

encode the TIBF signal component in a Bloom filter, wherein the TIBF signal component in the Bloom filter identifies a plurality of parent nodes for a routing topology; and

generate the Bloom filter by;

determining Bloom filter parameters based on a number of the plurality of parent nodes to be encoded,

determining a desired false positive rate for the Bloom filter, and encoding an address for each parent node of the plurality of parent nodes in the Bloom filter; and

send the TIBF signal component toward a root of the node in the network, wherein the root of the node derives the routing topology from information within the TIBF signal component.

18. The apparatus as in claim 17 wherein the Bloom filter parameters are based on a plurality of parent nodes.

19. The apparatus as in claim 17, wherein the processor is further operable to generate a Transit Option signal component identifying preferred parent nodes wherein the TIBF signal component identifies alternative parent nodes, and encoding the Transit Option signal and the TIBF signal component in the Bloom filter.

20. 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 a Transit Information Bloom Filter (TIBF) signal component from a plurality of nodes in the computer network, wherein the apparatus is a Directed Acyclic Graph (DAG) root node in the computer network; and

interpolate the TIBF signal component to derive a routing topology, wherein the TIBF signal component is within a routing protocol control message and the TIBF signal component is encoded in a Bloom filter that identifies a plurality of parent nodes for the routing topology, wherein the Bloom filter is generated by each node of said plurality of nodes in the computer network by;

determining Bloom filter parameters based a number of plurality of parent nodes to be encoded,

determining a desired false positive rate for the Bloom filter, and

encoding an address for each parent node of the plurality of parent nodes in the Bloom filter.

21. The apparatus as in claim 20, wherein the DAG root node predetermines hash values for the Bloom filter for each node identified by a Transit Option signal component.

22. The apparatus as in claim 20, whereby the DAG root node queries the Bloom filter for each device in the DAG in correlation with adding device links.

23. The apparatus as in claim 22, wherein if the query provides a positive result, the processor is further operable to cause the DAG root node to add a link to the DAG.