Traffic engineering for bit indexed explicit replication

• US 10,341,221 B2
• Filed: 07/31/2015
• Issued: 07/02/2019
• Est. Priority Date: 02/26/2015
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Eckert, Toerless, Wijnands, Ijsbrand, Shepherd, Gregory J., Ranns, Neale D. R.
• Primary Examiner(s): Shah, Chirag G
• Assistant Examiner(s): Persaud, Amarnauth G
• Application Number:
  US14/814,575
• Publication Number:
  US 20160254987A1
• Time in Patent Office: 1,432 Days
• Field of Search: None
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Methods and network devices are disclosed for traffic-engineered forwarding through a new form of bit indexed explicit replication. In one embodiment, a method includes receiving at a first node in a network a message comprising a message bit array, and comparing bit values at one or more bit positions in the message bit array to one or more entries in a forwarding table stored at the first node. The one or more bit positions correspond in this embodiment to links in the network. This embodiment of the method further includes forwarding the message over a link represented in the forwarding table if a result of the comparing indicates that the link is included in a path to be taken by the message. In a further embodiment of the method, the message is a multicast message and forwarding the message comprises forwarding a replica of the multicast message.

Claims

1. A method comprising:

receiving, at a first node in a network configured for traffic-engineered bit indexed forwarding, a message comprising a message bit array;

comparing bit values at one or more bit positions in the message bit array to one or more entries in a forwarding table stored at the first node, wherein the one or more bit positions are assigned to separate segments of a path or tree in the network; and

forwarding the message over a segment represented in the forwarding table if a result of the comparing indicates that the segment is included in a path to be taken by the message, wherein

the segment represented in the forwarding table is assigned one of the bit positions in the message bit array,

the one of the bit positions in the message bit array does not represent an egress node, of the network configured for traffic-engineered bit indexed forwarding, reachable via the segment,

the path to be taken by the message is defined as an end to end connection of multiple segments assigned bit positions having a first bit value in the message bit array, and

the forwarding comprises changing the bit value of the bit position, in the message bit array, assigned to the segment represented in the forwarding table.

2. The method of claim 1, wherein:

the message is a multicast message; and

forwarding the message comprises forwarding a replica of the multicast message.

3. The method of claim 1, wherein

at least one bit position in the message bit array is assigned to a segment from the first node to a core node of the network.

4. The method of claim 1, wherein the comparing comprises comparing at least a portion of the message bit array to a corresponding portion of a link bit array in an entry of the forwarding table.

5. The method of claim 1, wherein the comparing comprises checking a bit value of a bit position in the message bit array, wherein the bit position is assigned to a segment represented in the forwarding table.

6. The method of claim 1, wherein the comparing comprises:

identifying bit positions of one or more set bits in the message bit array; and

checking the forwarding table for segments assigned the respective identified bit positions.

7. The method of claim 1, wherein the segment represented in the forwarding table directly connects the first node to an adjacent node in the network.

8. The method of claim 1, wherein the segment represented in the forwarding table comprises an indirect connection to a second node in the network.

9. The method of claim 1, wherein a segment assigned a bit position in the message bit array comprises a link between a network protocol layer used to receive the message at the first node and a different protocol layer of the network.

10. The method of claim 1, wherein at least a portion of information stored in the forwarding table is received from a network controller.

11. The method of claim 10, wherein a representation of a topology of the network is not stored in the first node.

12. A network device associated with a node in a network configured for traffic-engineered bit indexed forwarding, the network device comprising:

one or more network interfaces;

a memory configured to store a forwarding table comprising one or more entries; and

a processor configured to

receive via one of the network interfaces a message comprising a message bit array,

compare bit values at one or more bit positions in the message bit array to one or more entries in the forwarding table, wherein the one or more bit positions are assigned to separate segments of a path or tree in the network, and

forward the message over a segment represented in the forwarding table if a result of comparing the bit values indicates that the segment is included in a path to be taken by the message, wherein

the segment represented in the forwarding table is assigned one of the bit positions in the message bit array,

the one of the bit positions in the message bit array does not represent an egress node, of the network configured for traffic-engineered bit indexed forwarding, reachable via the segment,

the path to be taken by the message is defined as an end to end connection of multiple segments assigned bit positions having a first bit value in the message bit array, and

forwarding the message comprises changing the bit value of the bit position, in the message bit array, assigned to the segment represented in the forwarding table.

13. The network device of claim 12, wherein the processor is further configured to:

receive a multicast message; and

replicate the multicast message.

14. The network device of claim 12, wherein the segment represented in the forwarding table is a segment from the node to another node of the network.

15. The network device of claim 14, wherein

the another node of the network is a core node of the network.

16. The network device of claim 12, wherein:

the memory is further configured to store topology information for the network; and

the processor is further configured to encapsulate the message for unicast routing to a remote node of the network, wherein the remote node is not directly connected to the node associated with the network device.

17. The network device of claim 12, wherein:

the memory is further configured to store a path table comprising a message bit array encoding a path or tree for a message flow; and

the processor is further configured to receive via one of the network interfaces a message without a message bit array, and encapsulate the message with a message bit array retrieved from the path table.

18. The network device of claim 17, wherein:

one or more sources or receivers of the message flow are members of a multicast group; and

the path table maps multicast group information to the message bit array.

19. The network device of claim 12, wherein:

a segment assigned a bit position in the message bit array is a link to a higher protocol layer in the network; and

the processor is further configured to remove the message bit array from the message and pass the message to the higher protocol layer at the node.