Traffic engineering for bit indexed explicit replication

• US 10,341,222 B2
• Filed: 09/23/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/862,915
• Publication Number:
  US 20160254988A1
• Time in Patent Office: 1,378 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:

determining a path to be taken by a message through multiple nodes of a network configured for bit indexed forwarding, wherein the message is configured to carry a message bit array from node to node along the path;

assigning a first bit position within the message bit array to a first path segment within the path, wherein the first path segment is not directly connected to an egress node of the network;

storing, in a data structure accessible by a network controller, a mapping of the first path segment to the first bit position, wherein

the data structure is configured for storing bit position assignments for path segments, throughout the network, having assigned bit positions,

the data structure is configured for use in generating the message bit array and in generating additional message bit arrays incorporating the mapping of the first path segment to the first bit position, and

the additional message bit arrays encode additional paths through the network, including one or more paths not comprising the first path segment;

communicating, to a first network node along the path, the mapping of the first path segment to the first bit position, wherein the first network node is directly connected to the first path segment;

generating the message bit array, wherein bit values at bit positions in the message bit array indicate whether respective path segments having the assigned bit positions are included in the path to be taken by the message; and

communicating, to an ingress node to the network, the message bit array and information associated with a corresponding message flow comprising the message, wherein the message bit array encodes the path for messages in the message flow.

2. The method of claim 1, wherein:

the message comprises a multicast message; and

determining a path comprises determining a multicast tree.

3. The method of claim 2, further comprising:

identifying a flood portion of the network in which all nodes can receive the multicast message;

determining non-looping paths within the flood portion; and

assigning a single bit position to all of the path segments along the non-looping paths, wherein the assigned bit position corresponds to a single direction of crossing each corresponding path segment.

4. The method of claim 1, wherein a path segment within the path directly connects a network node to an adjacent network node.

5. The method of claim 4, wherein a two-way bit position assigned to the path segment is assigned to both directions of crossing the path segment, and further comprising:

communicating, to both the network node and the adjacent network node connected by the path segment, a mapping between the two-way bit position and the path segment.

6. The method of claim 5, wherein communicating the mapping further comprises communicating instructions to reset, in the message bit array of a received message, the bit in the two-way bit position prior to forwarding a replica of the received message over the path segment having the assigned two-way bit position.

7. The method of claim 1, wherein determining a path comprises receiving input of a definition of the path.

8. The method of claim 1, further comprising:

identifying a bypass portion of the path over which neither replication of the message nor explicit routing of the message is required; and

assigning a bit position to a bypass link between a first end node and a second end node along the path at opposite ends of the bypass portion.

9. The method of claim 1, further comprising:

assigning a bit position to an egress node of the network, wherein the egress node is included in the path; and

communicating to the egress node the correspondence between the egress node and the bit position.

10. The method of claim 9, wherein:

assigning a bit position further comprises assigning the bit position to each of multiple egress nodes of the network, wherein each of the multiple egress nodes is included in the path; and

communicating to the egress node the correspondence between the egress node and the bit position comprises communicating to each of the multiple egress nodes the correspondence between the bit position and the respective egress node.

11. The method of claim 1, further comprising:

identifying a pair of nodes connected by multiple links in parallel; and

assigning a single bit position to each of the multiple links.

12. The method of claim 1, wherein

communicating, to a first network node along the path, a mapping of the first path segment to the first bit position comprises communicating the mapping for storage in a forwarding table used by the first network node, and

the forwarding table comprises an entry specific to the first bit position.

13. The method of claim 1, wherein the communicating comprises communicating via a control protocol.

14. The method of claim 1, wherein the communicating to the first network node of the mapping is performed prior to arrival at the first network node of the message configured to carry the message bit array.

15. A device for controlling a network configured for bit indexed forwarding, the device comprising:

one or more communication interfaces;

one or more computer-readable storage media configured to store topology information for the network;

a processor; and

stored program instructions configured, when executed by the processor, to

determine, using the topology information, a path to be taken by a message through multiple nodes of the network, wherein the message is configured to carry a message bit array from node to node along the path,

assign a first bit position within the message bit array to a first path segment within the path, wherein the first path segment is not directly connected to an egress node of the network,

store, in a data structure accessible by a network controller, a mapping of the first path segment to the first bit position, wherein

the data structure is configured for storing bit position assignments for path segments, throughout the network, having assigned bit positions,

the data structure is configured for use in generating the message bit array and in generating additional message bit arrays incorporating the mapping of the first path segment to the first bit position, and

the additional message bit arrays encode additional paths through the network, including one or more paths not comprising the first path segment,

communicate, to a first network node along the path, the mapping of the first path segment to the first bit position, wherein the first network node is directly connected to the first path segment,

generate the message bit array, wherein bit values at bit positions in the message bit array indicate whether respective path segments having the assigned bit positions are included in the path to be taken by the message, and

communicate, to an ingress node of the network, the message bit array and information associated with a corresponding message flow comprising the message, wherein the message bit array encodes the path for messages in the message flow.

16. The device of claim 15, wherein the one or more computer-readable storage media are further configured to store a data structure relating one or more message bit arrays to information associated with respective message flows.