Bit indexed explicit replication forwarding optimization

• US 9,806,897 B2
• Filed: 01/23/2015
• Issued: 10/31/2017
• Est. Priority Date: 09/17/2013
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wijnands, Ijsbrand, Shepherd, Gregory J., Bettink, John H. W.
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): Persaud, Amar
• Application Number:
  US14/603,580
• Publication Number:
  US 20150131659A1
• Time in Patent Office: 1,012 Days
• Field of Search: None
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

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.

Claims

1. A method comprising:

receiving a packet at a node, wherein

the packet comprises a bit string;

selecting a selected entry in 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, 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 selecting comprises

identifying 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, selecting 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, forwarding the packet to the another node, wherein

the another node is identified by the identifier, and

the forwarding comprises

creating an outgoing bit string in an outgoing packet using at least the forwarding bit mask and the bit string, and

transmitting the outgoing packet to the another node.

2. The method of claim 1, further comprising:

generating the BIFT such that the BIFT is indexed by bit position, wherein

the generating comprises at least one of

converting the existing BIFT to the BIFT by converting an entry in the existing BIFT to an entry in the BIFT, for each bit forwarding egress router of a plurality of bit forwarding egress routers, or

accessing an entry in the BIRT to generate the entry in the BIFT, for the each bit forwarding egress router of the plurality of bit forwarding egress routers.

3. The method of claim 1, wherein the forwarding further comprises:

performing an update operation comprising

updating the first value of the first bit such that the first bit indicates the forwarding of the packet to the another node.

4. The method of claim 3, wherein the update operation further comprises:

updating a value of another bit at another bit position in the bit string such that the another bit indicates the forwarding of the packet to the another node, wherein

the another bit position is other than the bit position.

5. The method of claim 1, wherein the identifying the bit position comprises:

locating a set bit in the bit string.

6. The method of claim 1, wherein the selecting the entry further comprises:

determining whether the entry in the BIFT corresponding to the bit position should be selected, wherein

the determining is based, at least in part, on the first value and the second value.

7. The method of claim 1, wherein the creating the outgoing bit string comprises:

performing a bit-wise logical AND operation between the forwarding bit mask and the bit string.

8. The method of claim 1, wherein

the plurality of the corresponding identifiers correspond to the another node.

9. 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.

10. The network device of claim 9, wherein the program instructions are further configured to cause the one or more processors to:

generate the BIFT, such that the BIFT is indexed by bit position, by virtue of comprising at least one of program instructions configured to cause the one or more processors to

convert the existing BIFT to the BIFT by converting an entry in the existing BIFT to an entry in the BIFT, for each bit forwarding egress router of a plurality of bit forwarding egress routers, or

access an entry in the BIRT to generate the entry in the BIFT, for the each bit forwarding egress router of the plurality of bit forwarding egress routers.

11. The network device of claim 9, wherein the program instructions configured to cause the one or more processors to forward further comprise program instructions configured to cause the one or more processors to:

perform an update operation comprising

updating the first value of the first bit such that the first bit indicates the forwarding of the packet to the another node.

12. The network device of claim 11, wherein the update operation further comprises:

updating a value of another bit at another bit position in the bit string such that the another bit indicates the forwarding of the packet to the another node, wherein

the another bit position is other than the bit position.

13. The network device of claim 9, wherein the program instructions configured to cause the one or more processors to select the entry further comprise program instructions configured to cause the one or more processors to:

determine whether the entry in the BIFT corresponding to the bit position should be selected, based, at least in part, on the first value and the second value.

14. The network device of claim 9, wherein the program instructions configured to cause the one or more processors to create the outgoing bit string comprise program instructions configured to cause the one or more processors to:

perform a bit-wise logical AND operation between the forwarding bit mask and the bit string.

15. The network device of claim 9, wherein

the plurality of the corresponding identifiers correspond to the another node.

16. 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.

17. The system of claim 16, wherein program instructions are further configured to cause the processing means to:

generate the BIFT, such that the BIFT is indexed by bit position, by virtue of comprising at least one of program instructions configured to cause the processing means to

convert the existing BIFT to the BIFT by converting an entry in the existing BIFT to an entry in the BIFT, for each bit forwarding egress router of a plurality of bit forwarding egress routers, or

access an entry in the BIRT to generate the entry in the BIFT, for the each bit forwarding egress router of the plurality of bit forwarding egress routers.

18. The system of claim 16, wherein the program instructions configured to cause the processing means to forward further comprise program instructions configured to cause the processing means to:

perform an update operation comprising

updating the first value of the first bit such that the first bit indicates the forwarding of the packet to the another node.

19. The system of claim 18, wherein the update operation further comprises:

updating a value of another bit at another bit position in the bit string such that the another bit indicates the forwarding of the packet to the another node, wherein

the another bit position is other than the bit position.

20. The system of claim 16, wherein the program instructions configured to cause the processing means to select the entry further comprise program instructions configured to cause the processing means to:

determine whether the entry in the BIFT corresponding to the bit position should be selected, based, at least in part, on the first value and the second value.