Bit indexed explicit replication packet encapsulation

• US 9,948,574 B2
• Filed: 08/31/2016
• Issued: 04/17/2018
• 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: Shepherd, Gregory J., Wijnands, Ijsbrand, Martin, Christian
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): PERSAUD, AMARNAUTH G
• Application Number:
  US15/253,025
• Publication Number:
  US 20170099232A1
• Time in Patent Office: 594 Days
• Field of Search: None
• 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

Methods and network devices are disclosed for multicast forwarding. In one embodiment, a 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 set identifier value associated with the incoming message bit array. The method further comprises selecting a first forwarding table entry, the first forwarding table entry comprises a set identifier value matching that of the message header. 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 the first forwarding table entry, determining that for at least one relative bit position 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.

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 set identifier value associated with the incoming message bit array,

the set identifier value is one of a plurality of set identifier values used in the network,

each of the plurality of set identifier values identifies a respective one of a plurality of sets of multiple possible destination nodes for the message, and

each destination node within one of the sets of multiple possible destination nodes is represented by a relative bit position in the incoming message bit array;

selecting a first forwarding table entry of one or more forwarding table entries in a bit-indexed forwarding table at the node, wherein the first forwarding table entry comprises a set identifier value matching the set identifier value in the message header;

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

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

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 set identifier value in the message header is mapped to a topology identifier value for the message.

3. The method of claim 1, wherein the set identifier value in the message header is mapped to a length of the incoming message bit array.

4. The method of claim 1, wherein:

the message header further comprises a topology identifier value for the message, and

the first forwarding table entry comprises a topology identifier value matching the topology identifier value in the message header.

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

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

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

8. The method of claim 7, 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.

9. The method of claim 7, 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.

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

one or more network interfaces;

a memory configured to store a bit-indexed forwarding table comprising one or more forwarding table entries; 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 set identifier value associated with the incoming message bit array,

the set identifier value is one of a plurality of set identifier values used in the network,

each of the plurality of set identifier values identifies a respective one of a plurality of sets of multiple possible destination nodes for the message, and

each destination node within one of the sets of multiple possible destination nodes is represented by a relative bit position in the incoming message bit array,

select a first forwarding table entry of the one or more forwarding table entries, wherein the first forwarding table entry comprises a set identifier value matching the set identifier value in the message header,

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

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

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.

11. The network device of claim 10, wherein the memory is further configured to store a bit-indexed routing table mapping the set identifier value in the message header to a topology identifier value for the message.

12. The network device of claim 10, wherein the memory is further configured to store a bit-indexed routing table mapping the set identifier value in the message header to a length of the incoming message bit array.

13. The network device of claim 10, wherein:

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

the first forwarding table entry comprises a topology identifier value matching the topology identifier value in the message header.

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

15. The network device of claim 14, wherein the processor is further configured to, 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, alter 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.

16. The network device of claim 14, wherein:

the processor is further configured to advertise to the first neighboring node a set of bit values contained in the first neighbor bit array, and

the first neighboring node is configured to use the set of bit values to perform the modification to the forwarded message bit array.

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

one or more network interfaces;

a memory configured to store a group membership table mapping a multicast group identifier to one or more message bit arrays, wherein the group membership table further maps a set identifier value to each of the one or more message bit arrays; and

a processor configured to

receive at the network node a multicast message,

determine a multicast group identifier associated with the multicast message,

obtain from the group membership table a first message bit array and first set identifier value corresponding to the multicast group identifier,

insert the first message bit array and first set identifier value into a header of a first copy of the multicast message,

obtain from the group membership table a second message bit array and second set identifier value corresponding to the multicast group identifier,

insert the second message bit array and second set identifier value into a header of a second copy of the multicast message, wherein

the first and second set identifier values are among a plurality of set identifier values used in the network,

each of the plurality of set identifier values identifies a respective one of a plurality of sets of multiple possible destination nodes for the multicast message,

each destination node within a set of multiple possible destination nodes identified by the first set identifier is represented by a relative bit position in the first message bit array, and

each destination node within a set of multiple possible destination nodes identified by the second set identifier is represented by a relative bit position in the second message bit array,

forward the first copy of the multicast message toward one or more of the destination nodes represented by relative bit positions in the first message bit array, and

forward the second copy of the multicast message toward one or more of the destination nodes represented by relative bit positions in the second message bit array.

18. The network device of claim 17, wherein:

the memory is further configured to store a bit-indexed forwarding table comprising one or more forwarding table entries; and

the processor is further configured to

compare at least a portion of the first message bit array to a corresponding portion of a first neighbor bit array in 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 multicast message and a reachable destination from a first neighboring node associated with the first forwarding table entry, and

forward to the first neighboring node a copy of the multicast message.

19. The network device of claim 17, wherein:

the group membership table further maps a topology identifier value to each of the one or more message bit arrays; and

the processor is further configured to

obtain from the group membership table a first topology identifier value corresponding to the multicast group identifier, and

insert the first topology identifier value into the header of the first copy of the multicast message.