Bit indexed explicit replication forwarding optimization
First Claim
Patent Images
1. A method comprising:
- generating a bit-indexed forwarding table (BIFT) at a first network node, whereinthe BIFT comprises a plurality of entries, each entry of which corresponds to a bit position of a plurality of bit positions,each bit position of the plurality of bit positions represents an egress network node of a plurality of egress network nodes,the BIFT is generated from a bit indexed routing table (BIRT), comprising a plurality of BIRT entries, and is configured to cause a packet to be forwarded toward one or more of the plurality of egress network nodes, based at least in part on a bit string in the packet, andthe generating comprisesselecting a bit position of the plurality of bit positions as a selected bit position,creating an entry of the plurality of entries, wherein the entry corresponds to the selected bit position,accessing a BIRT entry of the plurality of BIRT entries, whereinthe BIRT entry corresponds to the selected bit position,updating a neighbor information field of the entry, using neighbor information from the BIRT entry, whereinthe neighbor information is associated with a neighbor network node, andthe neighbor network node is a neighbor of the first network node, andupdating forwarding bit mask information in a forwarding bit mask field of the entry, using bit position information from the BIRT entry.
0 Assignments
0 Petitions
Accused Products
Abstract
Various systems and methods for performing bit indexed explicit replication (BIER). For example, one method involves receiving a packet at a node. The packet includes a bit string. The node traverses the bit string and selects an entry in a bit indexed forwarding table (BIFT). The entry includes a forwarding bit mask. Based on the forwarding bit mask and the bit string, the node forwards the packet.
158 Citations
20 Claims
-
1. A method comprising:
generating a bit-indexed forwarding table (BIFT) at a first network node, wherein the BIFT comprises a plurality of entries, each entry of which corresponds to a bit position of a plurality of bit positions, each bit position of the plurality of bit positions represents an egress network node of a plurality of egress network nodes, the BIFT is generated from a bit indexed routing table (BIRT), comprising a plurality of BIRT entries, and is configured to cause a packet to be forwarded toward one or more of the plurality of egress network nodes, based at least in part on a bit string in the packet, and the generating comprises selecting a bit position of the plurality of bit positions as a selected bit position, creating an entry of the plurality of entries, wherein the entry corresponds to the selected bit position, accessing a BIRT entry of the plurality of BIRT entries, wherein the BIRT entry corresponds to the selected bit position, updating a neighbor information field of the entry, using neighbor information from the BIRT entry, wherein the neighbor information is associated with a neighbor network node, and the neighbor network node is a neighbor of the first network node, and updating forwarding bit mask information in a forwarding bit mask field of the entry, using bit position information from the BIRT entry. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
15. A computer program product comprising:
-
a non-transitory computer-readable storage medium; and a plurality of instructions, encoded in the non-transitory computer-readable storage medium and comprising a first set of instructions, executable by a processor of a network device, configured to generate a bit-indexed forwarding table (BIFT) at a first network node, wherein the BIFT comprises a plurality of entries, each entry of which corresponds to a bit position of a plurality of bit positions, each bit position of the plurality of bit positions represents an egress network node of a plurality of egress network nodes, the BIFT is generated from a bit indexed routing table (BIRT), comprising a plurality of BIRT entries, and is configured to cause a packet to be forwarded toward one or more of the plurality of egress network nodes, based at least in part on a bit string in the packet, and the first set of instructions comprises a first subset of instructions, executable by the processor of the network device, configured to select a bit position of the plurality of bit positions as a selected bit position, a second subset of instructions, executable by the processor of the network device, configured to create an entry of the plurality of entries, wherein
the entry corresponds to the selected bit position,a third subset of instructions, executable by the processor of the network device, configured to access a BIRT entry of the plurality of BIRT entries, wherein
the BIRT entry corresponds to the selected bit position,a fourth subset of instructions, executable by the processor of the network device, configured to update a neighbor information field of the entry, using neighbor information from the BIRT entry, wherein
the neighbor information is associated with a neighbor network node, and
the neighbor network node is a neighbor of the first network node, anda fifth subset of instructions, executable by the processor of the network device, configured to update forwarding bit mask information in a forwarding bit mask field of the entry, using bit position information from the BIRT entry. - View Dependent Claims (16)
-
-
17. A network device comprising:
-
one or more hardware processors; one or more network interfaces coupled to the one or more hardware processors, wherein the one or more network interfaces are configured to couple the network device to a network; a non-transitory computer-readable storage medium coupled to the one or more hardware processors; and a plurality of instructions, encoded in the non-transitory computer-readable storage medium and configured to cause the one or more hardware processors to generate a bit-indexed forwarding table (BIFT), wherein the BIFT comprises a plurality of entries, each entry of which corresponds to a bit position of a plurality of bit positions, each bit position of the plurality of bit positions represents an egress network node of a plurality of egress network nodes, the BIFT is generated from a bit indexed routing table (BIRT), comprising a plurality of BIRT entries, and is configured to cause a packet to be forwarded toward one or more of the plurality of egress network nodes, based at least in part on a bit string in the packet, and the instructions configured to cause the one or more hardware processors to generate the BIFT comprise further instructions configured to cause the one or more hardware processors to select a bit position of the plurality of bit positions as a selected bit position, create an entry of the plurality of entries, wherein
the entry corresponds to the selected bit position, access a BIRT entry of the plurality of BIRT entries, wherein
the BIRT entry corresponds to the selected bit position,update a neighbor information field of the entry, using neighbor information from the BIRT entry, wherein
the neighbor information is associated with a neighbor network device, and
the neighbor network device is a neighbor of the network device, andupdate forwarding bit mask information in a forwarding bit mask field of the entry, using bit position information from the BIRT entry. - View Dependent Claims (18, 19, 20)
-
Specification