Bit indexed explicit replication forwarding optimization

A network device comprising:

• one or more processors;
• a memory, wherein the memory is
• configured to store a bit indexed forwarding table (BIFT) generated, using at least one of a bit-indexed routing table (BIRT) or an existing BIFT generated using the BIRT, such that the BIFT is indexed by bit position, and
• coupled to the one or more processors;
• a network interface, configured to receive a packet and coupled to the one or more processors, wherein
• the packet comprises a bit string;
• and
• a non-transitory computer-readable storage medium, coupled to the one or more processors and storing program instructions that, when executed, are configured to cause the one or more processors to
• select a selected entry in the BIFT, wherein
• the BIFT comprises a plurality of entries, each of which
• corresponds to a corresponding bit position in the bit string, and
• stores a corresponding identifier of a plurality of identifiers,
• as a result of the BIFT being indexed by bit position, the BIFT allows a plurality of the corresponding identifiers to correspond to another node,
• the program instructions configured to select the selected entry comprise further program instructions configured to identify a bit position, and
• in response to a first value of a first bit stored in the bit string at the bit position and a second value of a second bit stored in the entry indicating that the entry should be selected as the selected entry, select an entry in the BIFT corresponding to the bit position, as the selected entry, and
• the selected entry comprises
• a forwarding bit mask, and
• an identifier, and
• in response to the entry being selected as the selected entry, forward the packet to the another node, wherein
• the another node is identified by the identifier, and
• the program instructions configured to cause the one or more processors to forward comprise further program instructions configured to cause the one or more processors to
• create an outgoing bit string in an outgoing packet using at least the forwarding bit mask and the bit string, and
• transmit the outgoing packet to the another node.

A system comprising:

• processing means for processing program instructions;
• storage means for storing, coupled to the processing means, wherein
• the storage means is configured to store a bit indexed forwarding table (BIFT) generated, using at least one of a bit-indexed routing table (BIRT) or an existing BIFT generated using the BIRT, such that the BIFT is indexed by bit position;
• network interface means for receiving a packet, wherein
• the network interface means is coupled to the processing means, and the packet comprises a bit string;
• and
• non-transitory computer-readable storage means for storing the program instructions, coupled to the processing means and storing the program instructions, which are configured to cause the processing means to select a selected entry in the BIFT, wherein
• the BIFT comprises a plurality of entries, each of which
• corresponds to a corresponding bit position in the bit string, and
• stores a corresponding identifier of a plurality of identifiers,
• as a result of the BIFT being indexed by bit position, the BIFT allows a plurality of the corresponding identifiers to correspond to another node,
• the program instructions configured to select the selected entry comprise further program instructions configured to identify a bit position, and
• in response to a first value of a first bit stored in the bit string at the bit position and a second value of a second bit stored in the entry indicating that the entry should be selected as the selected entry, select an entry in the BIFT corresponding to the bit position, as the selected entry, and
• the selected entry comprises
• a forwarding bit mask, and
• an identifier, and
• in response to the entry being selected as the selected entry, forward the packet to the another node, wherein
• the another node is identified by the identifier, and
• the program instructions configured to cause the processing means to forward comprise further program instructions configured to cause the processing means to
• create an outgoing bit string in an outgoing packet using at least the forwarding bit mask and the bit string, and
• transmit the outgoing packet to the another node.