COMPRESSING DATA PACKET ROUTING INFORMATION USING BLOOM FILTERS

• US 20140036925A1
• Filed: 07/31/2012
• Published: 02/06/2014
• 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
• Granted Patent: US 9,300,569 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• 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 a Transit Information Bloom Filter (TIBF) signal component for use with a routing protocol control message whereby the TIBF signal component identifies at least one parent node for a routing topology;

encoding the TIBF signal component in a Bloom filter;

generating the Bloom filter by;

determining Bloom filter parameters based on at least one parent node to be encoded;

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

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

2. The method of claim 1, wherein the 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 and the TIBF signal component in the Bloom filter.

4. A method, comprising:

using a Directed Acyclic Graph (DAG) root to interpolate the TIBF signal to derive the routing topology wherein the TIBF signal is used with a routing protocol control message and the TIBF signal component identifies at least one parent node for a routing topology whereby the TIBF signal component is encoded in a Bloom filter and the TIBF signal is encoded in a Bloom filter wherein the Bloom filter is generated by;

determining Bloom filter parameters based on at least one parent node to be encoded; and

determining a desired false positive rate for the Bloom filter;

encoding an address for each parent node in the Bloom filter; and

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

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

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

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

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

10. The method of claim 8, wherein a false positive result in the Bloom filter is indicative of having more than N positive queries when only N 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 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 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 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 corrects link errors.

17. 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;

generate a Transit Information Bloom Filter (TIBF) signal component for use with a routing protocol control message whereby the TIBF signal component identifies at least one parent node for a routing topology;

encode the TIBF signal component in a Bloom filter; and

generate the Bloom filter by;

determining Bloom filter parameters based on at least one parent node to be encoded;

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

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

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 parents wherein the TIBF signal component identifies alternative parents, and encoding each of 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

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

use a Directed Acyclic Graph (DAG) root to interpolate a TIBF signal to derive a routing topology wherein the TIBF signal is used with a routing protocol control message and the TIBF signal component identifies at least one parent node for a routing topology whereby the TIBF signal component is encoded in a Bloom filter.

21. The apparatus as in claim 20, wherein the Bloom filter is generated by:

determining Bloom filter parameters based on at least one parent node to be encoded;

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

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

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

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

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