Bit indexed explicit replication forwarding optimization

• US 10,404,482 B2
• Filed: 07/24/2017
• Issued: 09/03/2019
• Est. Priority Date: 09/17/2013
• Status: Active Grant

• 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 G
• Assistant Examiner(s): Persaud, Amar
• Application Number:
  US15/658,110
• Publication Number:
  US 20170324575A1
• Time in Patent Office: 771 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:

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.

2. The method of claim 1, wherein

the entry comprises

a bit position identifying information field,

the forwarding bit mask field, and

the neighbor information field.

3. The method of claim 1, wherein:

one or more egress network nodes of the plurality of egress network nodes are a destination of the packet.

4. The method of claim 1, wherein:

the forwarding bit mask information is configured to represent one or more egress nodes that are reachable from the neighbor network node.

5. The method of claim 4, wherein:

the neighbor information comprises an identifier that identifies the neighbor network node.

6. The method of claim 1, wherein

the BIRT comprises one or more mappings that map the each bit position to at least one of the plurality of egress network nodes.

7. The method of claim 1, wherein the updating the forwarding bit mask information comprises:

generating the forwarding bit mask information, wherein

the generating the forwarding bit mask information comprises

sorting the plurality of BIRT entries, wherein

the plurality of BIRT entries are sorted by a neighbor network node associated with each BIRT entry,

selecting one or more selected BIRT entries, wherein

each of the one or more selected BIRT entries is associated with a common neighbor network node, and

generating combined entry information by combining the one or more selected BIRT entries, wherein

the updating the neighbor information field and the updating the forwarding bit mask information are performed using the combined entry information.

8. The method of claim 1, wherein the accessing further comprises:

selecting the BIRT entry based on a value of a bit in the selected bit position;

identifying a neighbor network node associated with the BIRT entry;

determining whether a destination network node is reachable from the first network node via the neighbor network node associated with the BIRT entry; and

in response to the destination network node being reachable from the first network node via the neighbor network node associated with the BIRT entry, setting a bit in a forwarding bit mask associated with the selected bit position, wherein

the forwarding bit mask information comprises the forwarding bit mask.

9. The method of claim 1, wherein the accessing further comprises:

selecting the BIRT entry;

determining a neighbor network node associated with the BIRT entry;

determining a bit position associated with the BIRT entry;

determining whether the BIFT comprises an associated entry associated with the neighbor network node associated with the BIRT entry;

if the BIFT does not comprise the associated entry, creating the associated entry in the BIFT; and

setting a bit in the associated entry, wherein

the bit in the associated entry corresponds to the bit position associated with the BIRT entry, and

the setting the bit in the associated entry represents that a destination network node corresponding to the bit position is reachable via the neighbor network node associated with the BIRT entry.

10. The method of claim 1, wherein

as a result of the generating, the BIFT comprises a plurality of entries, each of which corresponds to a corresponding bit position and stores a corresponding identifier of a plurality of identifiers.

11. The method of claim 10, wherein

the BIFT is indexed by bit position such that the BIFT allows a plurality of corresponding identifiers of the plurality of identifiers to correspond to another network node.

12. The method of claim 1, further comprising:

determining whether another BIRT entry of the plurality of BIRT entries is associated with the neighbor network node, wherein

the another BIRT entry is associated with the neighbor network node if the neighbor information of the another BIRT entry identifies the neighbor network node.

13. The method of claim 12, further comprising:

in response to the another BIRT entry being associated with the neighbor network node, updating the forwarding bit mask information in the forwarding bit mask field of the entry, using bit position information from the another BIRT entry.

14. The method of claim 13, wherein the updating the forwarding bit mask information in the forwarding bit mask field of the entry, using bit position information from the another BIRT entry, comprises:

setting a bit in the forwarding bit mask field of the entry, wherein the bit is associated with the another BIRT entry.

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, and

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

16. The computer program product of claim 15, further comprising:

a second set of instructions, executable by a processor of a network device, configured to determine whether another BIRT entry of the plurality of BIRT entries is associated with the neighbor network node, wherein

the another BIRT entry is associated with the neighbor network node if the neighbor information of the another BIRT entry identifies the neighbor network node; and

a third set of instructions, executable by a processor of a network device, configured to, in response to the another BIRT entry being associated with the neighbor network node, update the forwarding bit mask information in the forwarding bit mask field of the entry, using bit position information from the another BIRT entry.

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, and

update forwarding bit mask information in a forwarding bit mask field of the entry, using bit position information from the BIRT entry.

18. The network device of claim 17, wherein the plurality of instructions configured to cause the one or more hardware processors to update the forwarding bit mask information are further configured to:

generate the forwarding bit mask information, wherein

the forwarding bit mask information is generated by

sorting the plurality of BIRT entries, wherein

the plurality of BIRT entries are sorted by a neighbor network node associated with each BIRT entry,

selecting one or more selected BIRT entries, wherein

each of the one or more selected BIRT entries is associated with a common neighbor network node, and

generating combined entry information by combining the one or more selected BIRT entries, wherein

the neighbor information field and the forwarding bit mask field are updated using the combined entry information.

19. The network device of claim 17, wherein the plurality of instructions configured to cause the one or more hardware processors to update the forwarding bit mask information are further configured to:

select the BIRT entry based on a value of a bit in the selected bit position;

identify a neighbor network node associated with the BIRT entry;

determine whether a destination network node is reachable from the network device via the neighbor network node associated with the BIRT entry; and

in response to the destination network node being reachable from the network device via the neighbor network node associated with the BIRT entry, set a bit in a forwarding bit mask associated with the selected bit position, wherein

the forwarding bit mask information comprises the forwarding bit mask.

20. The network device of claim 17, wherein the plurality of instructions configured to cause the one or more hardware processors to update the forwarding bit mask information are further configured to:

select the BIRT entry;

determine a neighbor network node associated with the BIRT entry;

determine a bit position associated with the BIRT entry;

determine whether the BIFT comprises an associated entry associated with the neighbor network node associated with the BIRT entry;

if the BIFT does not comprise the associated entry, create the associated entry in the BIFT; and

set a bit in the associated entry, wherein

the bit in the associated entry corresponds to the bit position associated with the BIRT entry, and

the bit in the associated entry being set represents that a destination network node corresponding to the bit position is reachable via the neighbor network node associated with the BIRT entry.