COMPRESSING DATA PACKET ROUTING INFORMATION USING BLOOM FILTERS
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
42 Citations
24 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. - View Dependent Claims (2, 3)
-
-
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 - View Dependent Claims (5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
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. - View Dependent Claims (18, 19)
-
-
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. - View Dependent Claims (21, 22, 23, 24)
-
Specification