USING BIT INDEX EXPLICIT REPLICATION (BIER) IN LOW-POWER AND LOSSY NETWORKS
First Claim
1. A method comprising:
- receiving, at a first node in a network, one or more bitmaps from one or more child nodes of the first node according to a directed acyclic graph (DAG), wherein each of the one or more child nodes is associated with a corresponding unique bit position in the one or more bitmaps;
storing, in a forwarding table of the first node, the one or more bitmaps received from the one or more child nodes of the first node;
receiving, at the first node, a message that includes a destination bitmap that identifies one or more destinations of the message via one or more set bits at the corresponding bit positions associated with the one or more child nodes; and
forwarding, by the first node, the message towards the identified one or more destinations based on the destination bitmap and the one or more bitmaps stored in the forwarding table of the first node.
0 Assignments
0 Petitions
Accused Products
Abstract
In one embodiment, a first node in a network receives one or more bitmaps from one or more child nodes of the first node according to a directed acyclic graph (DAG). Each of the one or more child nodes is associated with a corresponding unique bit position in the one or more bitmaps. The first node stores, in a forwarding table, the one or more bitmaps received from the one or more child nodes of the first node. The first node receives a message that includes a destination bitmap that identifies one or more destinations of the message via one or more set bits at bit positions associated with the one or more child nodes. The first node forwards the message towards the identified one or more destinations based on the destination bitmap and the one or more bitmaps stored in the forwarding table of the first node.
64 Citations
22 Claims
-
1. A method comprising:
-
receiving, at a first node in a network, one or more bitmaps from one or more child nodes of the first node according to a directed acyclic graph (DAG), wherein each of the one or more child nodes is associated with a corresponding unique bit position in the one or more bitmaps; storing, in a forwarding table of the first node, the one or more bitmaps received from the one or more child nodes of the first node; receiving, at the first node, a message that includes a destination bitmap that identifies one or more destinations of the message via one or more set bits at the corresponding bit positions associated with the one or more child nodes; and forwarding, by the first node, the message towards the identified one or more destinations based on the destination bitmap and the one or more bitmaps stored in the forwarding table of the first node. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method comprising:
-
assigning, by a device in a network, a plurality of nodes in the network to bitmaps, wherein each node is associated with a unique bit position in the bitmaps; causing, by the device, construction of a directed acyclic graph (DAG) in the network by sending the assigned bitmaps to the plurality of nodes, wherein a particular one of the plurality of node stores one or more of the bitmaps that are assigned to one or more children of the particular node in the DAG; determining, by the device, a destination bitmap for a message based on the assigned bitmaps and one or more of the nodes selected as destinations for the message; and sending, by the device, the message and the destination bitmap to the particular node, wherein the particular node forwards the message based on the destination bitmap and on the one or more of the bitmaps assigned to the one or more children of the particular node in the DAG. - View Dependent Claims (8, 9, 10, 11)
-
-
12. 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 configured to execute a process; and a memory configured to store the process executable by the processor, the process when executed operable to; receive one or more bitmaps from one or more child nodes of the apparatus according to a directed acyclic graph (DAG), wherein each of the one or more child nodes is associated with a corresponding unique bit position in the one or more bitmaps; store, in a forwarding table in the memory, the one or more bitmaps received from the one or more child nodes of the apparatus; receive a message that includes a destination bitmap that identifies one or more destinations of the message via one or more set bits at the corresponding bit positions associated with the one or more child nodes; and forward the message towards the identified one or more destinations based on the destination bitmap and the one or more bitmaps stored in the forwarding table. - View Dependent Claims (13, 14, 15, 16, 17)
-
-
18. 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 configured to execute a process; and a memory configured to store the process executable by the processor, the process when executed operable to; assign a plurality of nodes in the network to bitmaps, wherein each node is associated with a unique bit position in the bitmaps; cause construction of a directed acyclic graph (DAG) in the network by sending the assigned bitmaps to the plurality of nodes, wherein a particular one of the plurality of node stores one or more of the bitmaps that are assigned to one or more children of the particular node in the DAG; determine a destination bitmap for a message based on the assigned bitmaps and one or more of the nodes selected as destinations for the message; and send the message and the destination bitmap to the particular node, wherein the particular node forwards the message based on the destination bitmap and on the one or more of the bitmaps assigned to the one or more children of the particular node in the DAG. - View Dependent Claims (19, 20, 21, 22)
-
Specification