Bit indexed explicit replication packet encapsulation

• US 9,438,432 B2
• Filed: 01/23/2015
• Issued: 09/06/2016
• 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: Shepherd, Gregory J., Wijnands, Ijsbrand, Martin, Christian
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): Persaud, Amar
• Application Number:
  US14/604,092
• Publication Number:
  US 20150131660A1
• Time in Patent Office: 592 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 2212/00 Encapsulation of packets
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/806 Broadcast or multicast traffic

Abstract

A method and network device are disclosed for multicast forwarding. In one embodiment, the method includes receiving at a node a multicast message comprising a message header, where the message header comprises an incoming message bit array and a size value representing a length of the incoming message bit array. The method further comprises comparing at least a portion of the incoming message bit array to a corresponding portion of a neighbor bit array of a first forwarding table entry within the node, determining that for at least one relative bit position in the bit arrays a corresponding destination node is both a destination for the message and a reachable destination from a first neighboring node, and forwarding a copy of the message to the first neighboring node. An embodiment of the device includes a network interface, a memory and a processor configured to perform steps of the method.

Claims

1. A method comprising:

receiving at a node in a network a multicast message comprising a message header and a message payload, wherein

the message header comprises an incoming message bit array and a size value representing a length of the incoming message bit array,

the node comprises a bit-indexed forwarding table comprising one or more forwarding table entries,

each of the one or more forwarding table entries comprises a respective neighbor bit array and is associated with a respective neighboring node, and

a set of multiple possible destination nodes for the message corresponds to the same set of respective relative bit positions in the incoming message bit array and each of the neighbor bit arrays;

accessing the size value in the message header;

in response to the accessing, selecting the bit-indexed forwarding table from among multiple bit-indexed forwarding tables stored at the node, wherein the bit-indexed forwarding table corresponds to the size value;

comparing at least a portion of the incoming message bit array to a corresponding portion of a first neighbor bit array of a first forwarding table entry of the one or more forwarding table entries;

determining that for at least one relative bit position the corresponding destination node is both an intended destination for the message and a reachable destination from a first neighboring node associated with the first forwarding table entry; and

in response to the determining, forwarding to the first neighboring node a copy of the message comprising a forwarded message bit array in place of the incoming message bit array.

2. The method of claim 1, wherein the incoming message bit array and size value are stored within a destination bit array field of the message header.

3. The method of claim 1, wherein:

the message header further comprises a set identifier field containing a set identifier value associated with the incoming message bit array;

each set identifier value is associated with a respective set of multiple possible destination nodes for the message; and

the first forwarding table entry further comprises a set identifier value matching that of the set identifier field.

4. The method of claim 1, wherein the message header further comprises a topology identifier field containing a topology identifier value for the message, and further comprising:

accessing the topology identifier value; and

in response to the accessing, selecting the first forwarding table entry.

5. The method of claim 4, wherein selecting the first forwarding table entry comprises selecting, from among multiple bit-indexed forwarding tables stored at the node, a bit-indexed forwarding table corresponding to the topology identifier value.

6. The method of claim 1, wherein the message header further comprises a source identifier field containing a value of a relative bit position assigned to a sending node for the message.

7. The method of claim 1, wherein the message header further comprises a message protocol identifier field containing a value identifying a protocol type associated with the message payload.

8. The method of claim 1, further comprising effectuating a modification to the forwarded message bit array.

9. The method of claim 8, wherein effectuating a modification comprises:

for any destination node that is indicated by the incoming message bit array as an intended destination but indicated by the first neighbor bit array as an unreachable destination, altering the bit value of the corresponding relative bit position in the forwarded message bit array from that of the incoming message bit array to indicate that the destination node is not an intended destination.

10. The method of claim 8, wherein effectuating a modification comprises advertising to the first neighboring node a set of bit values contained in the first neighbor bit array, wherein the first neighboring node is adapted to use the set of bit values to perform the modification to the forwarded message bit array.

11. A network device associated with a network node, the network device comprising:

one or more network interfaces;

a memory configured to store multiple bit-indexed forwarding tables, including a first bit-indexed forwarding table comprising one or more forwarding table entries, wherein each of the one or more forwarding table entries comprises a respective neighbor bit array and is associated with a respective neighboring node; and

a processor configured to

receive at the network node a multicast message comprising a message header and a message payload, wherein

the message header comprises an incoming message bit array and a size value representing a length of the incoming message bit array, and

a set of multiple possible destination nodes for the message corresponds to the same set of respective relative bit positions in the incoming message bit array and each of the neighbor bit arrays,

access the size value in the message header;

in response to the access of the size value, select the first bit-indexed forwarding table from among the multiple bit-indexed forwarding tables, wherein the first bit-indexed forwarding table corresponds to the size value;

compare at least a portion of the incoming message bit array to a corresponding portion of a first neighbor bit array of a first forwarding table entry of the one or more forwarding table entries,

determine that for at least one relative bit position the corresponding destination node is both an intended destination for the message and a reachable destination from a first neighboring node associated with the first forwarding table entry, and

in response to a determination that an intended destination for the message is a reachable destination from the first neighboring node, forward to the first neighboring node a copy of the message comprising a forwarded message bit array in place of the incoming message bit array.

12. The network device of claim 11, wherein:

the message header further comprises a set identifier field containing a set identifier value associated with the incoming message bit array;

each set identifier value is associated with a respective set of multiple possible destination nodes for the message; and

the first forwarding table entry further comprises a set identifier value matching that of the set identifier field.

13. The network device of claim 11, wherein:

the message header further comprises a topology identifier field containing a topology identifier value for the message; and

the processor is further configured to

access the topology identifier value, and

in response to the access of the topology identifier value, select the first forwarding table entry.

14. The network device of claim 13, wherein:

the processor is further configured to select from among the multiple bit-indexed forwarding tables a bit-indexed forwarding table corresponding to the topology identifier value; and

the selected bit-indexed forwarding table comprises the first forwarding table entry.

15. The network device of claim 11, wherein the processor is further configured to effectuate a modification to the forwarded message bit array.

16. The network device of claim 15, wherein the processor is configured to effectuate the modification by:

for any destination node that is indicated by the incoming message bit array as an intended destination but indicated by the first neighbor bit array as an unreachable destination, altering the bit value of the corresponding relative bit position in the forwarded message bit array from that of the incoming message bit array to indicate that the destination node is not an intended destination.