MULTICAST GROUP ASSIGNMENT USING PROBABILISTIC APPROXIMATIONS

• US 20140036912A1
• 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., Hong, Wei, Vasseur, Jean-Philippe
• Granted Patent: US 9,071,533 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/023 Limited or focused flooding to selected areas of a network
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

In one embodiment, a source node (e.g., responsible node) determines a plurality of destination nodes of a message, and generates a probabilistic data structure that encodes each of the plurality of destination nodes without any false negatives and with zero or more false positives. The source node may then transmit the message with the probabilistic data structure toward the plurality of destination nodes, wherein nodes receiving the message interpret the probabilistic data structure to determine whether the receiving node is probabilistically one of the intended plurality of destination nodes.

Claims

1. A method, comprising:

determining a plurality of destination nodes of a message;

generating a probabilistic data structure that encodes each of the plurality of destination nodes without any false negatives and with zero or more false positives; and

transmitting the message with the probabilistic data structure toward the plurality of destination nodes, wherein nodes receiving the message interpret the probabilistic data structure to determine whether the receiving node is probabilistically one of the intended plurality of destination nodes.

2. The method as in claim 1, wherein the probabilistic data structure is a Bloom filter.

3. The method as in claim 1, further comprising:

adjusting a rate of the false positives.

4. The method as in claim 3, wherein adjusting comprises:

adjusting one or both of a bit vector size of the probabilistic data structure and a hash function used to generate the probabilistic data structure.

5. The method as in claim 1, wherein the message is a routing protocol control message to solicit a routing protocol response from the plurality of destination nodes.

6. The method as in claim 5, wherein the routing protocol control message is a route request (RREQ) message to solicit route reply (RREP) messages from the plurality of destination nodes.

7. The method as in claim 5, wherein the routing protocol control message is a Destination Oriented Directed Acyclic Graph (DODAG) Information Object (DIO) message to solicit Destination Advertisement Object (DAO) messages from the plurality of destination nodes.

8. The method as in claim 1, wherein the probabilistic data structure is contained within a field within the message selected from a group consisting of:

an address space of the message;

a type-length-value (TLV) field of the message;

a target identifier field of the message;

an application header of the message; and

a payload of the message.

9. A method, comprising:

receiving, at a receiving node, a message having a probabilistic data structure that encodes each of a plurality of destination nodes without any false negatives and with zero or more false positives;

interpreting the probabilistic data structure to determine whether the receiving node is probabilistically one of the intended plurality of destination nodes;

in response to the receiving node being probabilistically one of the intended plurality of destination nodes, performing an action on the message as dictated by the message as an intended destination node; and

in response to the receiving node not being one of the intended plurality of destination nodes, managing the message as dictated by the message as a node other than an intended destination node.

10. The method as in claim 9, wherein managing the message as dictated by the message as a node other than an intended destination node comprises forwarding the message toward one or more of the plurality of destination nodes.

11. The method as in claim 9, wherein the probabilistic data structure is a Bloom filter.

12. The method as in claim 9, wherein the message is a routing protocol control message to solicit a routing protocol response from the plurality of destination nodes.

13. The method as in claim 9, wherein the routing protocol control message is a route request (RREQ) message to solicit route reply (RREP) messages from the plurality of destination nodes.

14. The method as in claim 9, wherein the routing protocol control message is a Destination Oriented Directed Acyclic Graph (DODAG) Information Object (DIO) message to solicit Destination Advertisement Object (DAO) messages from the plurality of destination nodes.

15. The method as in claim 9, wherein the probabilistic data structure is contained within a field within the message selected from a group consisting of:

an address space of the message;

a type-length-value (TLV) field of the message;

a target identifier field of the message;

an application header of the message; and

a payload of the message.

16. An apparatus, comprising:

one or more network interfaces to communicate within 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;

determine a plurality of destination nodes of a message;

generate a probabilistic data structure that encodes each of the plurality of destination nodes without any false negatives and with zero or more false positives; and

transmit the message with the probabilistic data structure toward the plurality of destination nodes, wherein nodes receiving the message interpret the probabilistic data structure to determine whether the receiving node is probabilistically one of the intended plurality of destination nodes.

17. The apparatus as in claim 16, wherein the process when executed is further operable to:

adjust a rate of the false positives.

18. The apparatus as in claim 16, wherein the message is a routing protocol control message to solicit a routing protocol response from the plurality of destination nodes.

19. The apparatus as in claim 16, wherein the probabilistic data structure is contained within a field within the message selected from a group consisting of:

an address space of the message;

a type-length-value (TLV) field of the message;

a target identifier field of the message;

an application header of the message; and

a payload of the message.

20. An apparatus, comprising:

one or more network interfaces to communicate within 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 receiving node, a message having a probabilistic data structure that encodes each of a plurality of destination nodes without any false negatives and with zero or more false positives;

interpret the probabilistic data structure to determine whether the receiving node is probabilistically one of the intended plurality of destination nodes;

in response to the receiving node being probabilistically one of the intended plurality of destination nodes, perform an action on the message as dictated by the message as an intended destination node; and

in response to the receiving node not being one of the intended plurality of destination nodes, manage the message as dictated by the message for nodes other than an intended destination node.

21. The apparatus as in claim 20, wherein the process when executed to manage the message as dictated by the message for nodes other than an intended destination node is further operable to:

forward the message toward one or more of the plurality of destination nodes.

22. The apparatus as in claim 20, wherein the message is a routing protocol control message to solicit a routing protocol response from the plurality of destination nodes.

23. The apparatus as in claim 20, wherein the probabilistic data structure is contained within a field within the message selected from a group consisting of:

an address space of the message;

a type-length-value (TLV) field of the message;

a target identifier field of the message;

an application header of the message; and

a payload of the message.