Bit indexed explicit forwarding optimization
Disclosed are systems and methods for generating a bit-indexed forwarding table (BIFT) that includes a plurality of entries, each of which corresponds to a bit position of a number of bit positions. Each such bit position represents an egress network node of a plurality of egress network nodes. The BIFT is generated from an existing BIFT that includes a number of existing BIFT entries. Further, the generating configures the BIFT to be used in forwarding a packet to one or more of the egress nodes, based at least in part on a bit string in the packet. In one embodiment, the generating includes selecting a bit position of the plurality of bit positions as a selected bit position, creating an entry of the plurality of entries, and converting an existing BIFT entry of the plurality of existing BIFT entries to the entry of the plurality of entries.
1. A method comprising:
generating a bit-indexed forwarding table (BIFT), wherein
the BIFT, once generated, comprises a plurality of entries,
each entry of the plurality of entries 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 an existing BIFT,
the existing BIFT comprises a plurality of existing BIFT entries, and
the generating configures the BIFT to be used in forwarding a packet to one or more egress network nodes of the plurality of egress network nodes, based at least in part on a bit string in the packet, and 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,
selecting an existing BIFT entry, wherein
the selected bit position is one of a plurality of bit positions in a bit string,
determining a state of a bit at the selected bit position, and
in response to a determination that the state of the bit indicates that the existing BIFT entry should be converted,
converting the existing BIFT entry of the plurality of existing BIFT entries to the entry of the plurality of entries by
copying neighbor information from the existing BIFT entry to the entry, wherein
the existing BIFT entry corresponds to the selected bit position, and
copying forwarding bit mask information from the existing BIFT entry to a forwarding bit mask field of the entry.
2. The method of claim 1 , wherein
the determining the state of the bit at the selected bit position comprises determining whether the bit at the selected bit position is set, and
the determination that the state of the bit indicating that the existing BIFT entry should be converted corresponds to a determination that the bit at the selected bit position is set.
3. The method of claim 2 , further comprising:
in response to a determination that the bit at the selected bit position is not set,
determining whether another existing BIFT entry of the plurality of existing BIFT entries remains to be processed, and
in response to a determination that another existing BIFT entry remains to be processed,
selecting the another existing BIFT entry, and
performing the determining whether the bit at the selected bit position is set.
4. The method of claim 1 , further comprising:
reading a forwarding bit mask from the existing BIFT, wherein
the forwarding bit mask information comprises the forwarding bit mask,
and
the forwarding bit mask is stored in the existing the BIFT.
5. The method of claim 4 , further comprising:
determining whether another bit position of the plurality of bit positions remains to be processed, and
in response to a determination that another bit position remains to be processed, selecting the another bit position, and
performing the creating and the converting using the another bit position.
6. The method of claim 1 , wherein
the neighbor information comprises at least one of
a neighbor identifier, and/or
reachability information.
7. The method of claim 1 , wherein
the one or more egress network nodes of the plurality of egress network nodes are
a destination of the packet.
8. The method of claim 1 , wherein
the BIFT is generated at a first network node,
the neighbor information is associated with a neighbor network node, and
the neighbor network node is a neighbor of the first network node.
9. The method of claim 8 , wherein
the forwarding bit mask information is configured to represent one or more egress nodes that are reachable from the neighbor network node.
10. The method of claim 9 , wherein:
the one or more egress nodes are a destination of a packet comprising the bit string and having the selected bit position in the bit string set.
11. The method of claim 1 , wherein
the entry of the plurality of entries comprises
a bit position identification information field,
a forwarding bit mask field, and
a neighbor information field.
12. The method of claim 11 , wherein
the converting is performed for each egress node of a plurality of egress nodes by selecting each bit position of a plurality of bit positions of the bit string.
13. A network device comprising:
one or more processors;
one or more network interfaces coupled to the one or more 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 processors; and
a plurality of instructions, encoded in the non-transitory computer-readable storage medium and configured to cause the one or more processors to generate a bit-indexed forwarding table (BIFT), wherein
the BIFT, once generated, comprises a plurality of entries,
each entry of the plurality of entries 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 an existing BIFT,
the existing BIFT comprises a plurality of existing BIFT entries, and
the instructions configured to cause the one or more processors to generate configures the BIFT to be used in forwarding a packet to one or more egress network nodes of the plurality of egress network nodes, based at least in part on a bit string in the packet, and comprise further instructions configured to cause the one or more 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,
select an existing BIFT entry, wherein
the selected bit position is one of a plurality of bit positions in a bit string,
determine a state of a bit at the selected bit position, and
in response to a determination that the state of the bit indicates that the existing BIFT entry should be converted, convert the existing BIFT entry of the plurality of existing BIFT entries to the entry of the plurality of entries by virtue of being configured to cause the one or more processors to
copy neighbor information from the existing BIFT entry to the entry, wherein
the existing BIFT entry corresponds to the selected bit position, and
copy forwarding bit mask information from the existing BIFT entry to a forwarding bit mask field of the entry.
14. The network device of claim 13 , wherein
the state of the bit at the selected bit position is determined, at least in part, by determining whether the bit at the selected bit position is set, and
the determination that the state of the bit indicating that the existing BIFT entry should be converted corresponds to a determination that the bit at the selected bit positions set.
15. The network device of claim 14 , wherein the plurality of instructions is further configured to cause the one or more processors to:
in response to a determination that the bit at the selected bit position is not set,
determine whether another existing BIFT entry of the plurality of existing BIFT entries remains to be processed, and
in response to a determination that another existing BIFT entry remains to be processed,
select the another existing BIFT entry, and
execute the instructions configured to cause the one or more processors to determine whether the bit at the selected bit position is set.
16. The network device of claim 13 , wherein the plurality of instructions is further configured to cause the one or more processors to:
read a forwarding bit mask from the existing BIFT, wherein
the forwarding bit mask information comprises the forwarding bit mask, and
the forwarding bit mask is stored in the existing the BIFT.
17. The network device of claim 13 , wherein
the neighbor information comprises at least one of
a neighbor identifier, and/or
reachability information.
18. The network device of claim 13 , wherein
the BIFT is generated at a first network node,
the neighbor information is associated with a neighbor network node,
the neighbor network node is a neighbor of the first network node, and
the forwarding bit mask information is configured to represent one or more egress nodes that are reachable from the neighbor network node.
19. The network device of claim 13 , wherein
the entry of the plurality of entries comprises
a bit position identification information field,
a forwarding bit mask field, and
a neighbor information field.
20. A computer program product comprising:
a plurality of instructions, comprising
a first set of instructions, executable by a processor of a network device, configured to generate a bit-indexed forwarding table (BIFT), wherein
the BIFT, once generated, 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 an existing BIFT,
the existing BIFT comprises a plurality of existing BIFT entries, and
the first set of instructions configures the BIFT to be used in forwarding a packet to one or more egress network nodes of the plurality of egress network nodes, based at least in part on a bit string in the packet, and comprise
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 select an existing BIFT entry, wherein
the selected bit position is one of a plurality of bit positions in a bit string,
a fourth subset of instructions, executable by the processor of the network device, configured to determine a state of a bit at the selected bit position, and
a fifth subset of instructions, executable by the processor of the network device, configured to, in response to a determination that the state of the bit indicates that the existing BIFT entry should be converted, convert the existing BIFT entry of the plurality of existing BIFT entries to the entry of the plurality of entries by virtue of comprising
a first sub-subset of instructions, executable by the processor of the network device, configured to copy neighbor information from the existing BIFT entry to the entry, wherein the existing BIFT entry corresponds to the selected bit position, and
a second sub-subset of instructions, executable by the processor of the network device, configured to copy forwarding bit mask information from the existing BIFT entry to a forwarding bit mask field of the entry; and
a non-transitory computer-readable storage medium, wherein the instructions are encoded in the non-transitory computer-readable storage medium.