Multicast group assignment using probabilistic approximations
AssigneeCisco Technology, Inc.
InventorsJonathan W. Hui, Wei Hong, Jean-Philippe Vasseur
Life of this patent
Estimating the term…
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.
Claims23
A method, comprising:
- determining a plurality of destination nodes of a message;
- generating, on a source node, 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.
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.
An apparatus, comprising:
- one or more network interfaces to communicate within a computer network;
- a processor coupled to the network interfaces and configured to execute one or more processes;
- and
- a memory configured to store a process executable by the processor, the process when executed configured 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.
An apparatus, comprising:
- one or more network interfaces to communicate within a computer network;
- a processor coupled to the network interfaces and configured to execute one or more processes;
- and
- a memory configured to store a process executable by the processor, the process when executed configured 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.
Dependencies are inferred from the claim text.