MIGRATION SUPPORT FOR BIT INDEXED EXPLICIT REPLICATION

• US 20150085635A1
• Filed: 11/07/2014
• Published: 03/26/2015
• 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., Martin, Christian
• Granted Patent: US 9,544,230 B2
• Time in Patent Office: Days
• US Class Current: 370/216
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• 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/33 using forward notification

Abstract

A method and network device are disclosed for multicast forwarding. In one embodiment, the method includes receiving at a node configured to use a bit-indexed forwarding table a multicast message comprising an incoming message bit array. The method further includes comparing the incoming message bit array to a first neighbor bit array within a first forwarding table entry, and 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. The method further includes forwarding toward the first neighboring node a copy of the message, where a first node on the path of the forwarded message is not configured to use a respective bit-indexed forwarding table. 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 an incoming message bit array, wherein

the node is configured to store and use a bit-indexed forwarding table comprising multiple forwarding table entries,

each of the multiple 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;

comparing the incoming message bit array to a first neighbor bit array associated with a first forwarding table entry of the multiple 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 said determining, forwarding toward the first neighboring node a copy of the message comprising a forwarded message bit array, wherein a first node along the path of the forwarded message is not configured to use a respective bit-indexed forwarding table.

2. The method of claim 1, wherein:

a bit value of a bit position in the message bit array indicates whether the corresponding destination node is an intended destination for the message; and

a bit value of a bit position in each neighbor bit array indicates whether the corresponding destination node is reachable from the respective neighboring node associated with the forwarding table entry.

3. The method of claim 1, further comprising performing a first modification to the forwarded message bit array.

4. The method of claim 3, further comprising:

in response to said determining, performing a second modification to the incoming message bit array to form a comparison message bit array, wherein the comparison message bit array is configured to be compared to a second neighbor bit array associated with a second forwarding table entry of the multiple forwarding table entries.

5. The method of claim 3, wherein said performing a first 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.

6. The method of claim 4, wherein said performing a second modification comprises:

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

7. The method of claim 1, wherein

the multicast message further comprises a set identifier having multiple possible values;

each possible value of the set identifier corresponds to a different set of multiple possible destination nodes for the message; and

a combination of a set identifier value and a relative bit position in the incoming message bit array uniquely identifies a possible destination node for the message.

8. The method of claim 1, wherein said comparing comprises:

identifying a relative bit position in the incoming message bit array corresponding to an intended destination; and

identifying an entry in the bit-indexed forwarding table for which the identified relative bit position corresponds to a reachable destination.

9. The method of claim 1, wherein the multicast message comprises a multicast packet.

10. The method of claim 1, wherein:

The first node along the path of the forwarded message is the first neighboring node; and

said forwarding comprises sending a separate copy of the message to each of the destination nodes determined to be both an intended destination for the message and a reachable destination from the first neighboring node.

11. The method of claim 10, wherein said forwarding further comprises accessing a unicast forwarding table entry associated with each destination node that a copy of the message is forwarded to.

12. The method of claim 11, wherein said forwarding further comprises including within each forwarded message an identifier configured to alert the respective destination node to access the respective forwarded message bit array.

13. The method of claim 1, wherein the first node on the path of the forwarded message is the first neighboring node, and said forwarding comprises:

identifying, for each of the destination nodes determined to be both an intended destination for the message and a reachable destination from the first neighboring node, a nearest node, along a path to the respective destination node, that comprises a respective bit-indexed forwarding table; and

sending a separate copy of the message to each of the identified nodes.

14. The method of claim 13, wherein said sending comprises modifying the respective forwarded message bit array in each copy of the message to indicate as intended destination nodes only those destination nodes indicated as intended by the incoming message bit array and also reachable from the respective identified node that the copy of the message is sent to.

15. The method of claim 13, wherein said sending comprises including within each forwarded message:

a first identifier configured to be used by the first node on the path of the respective forwarded message in conveying the message to the identified node along the path to a destination node for the message; and

a second identifier configured to alert the identified node to access the forwarded message bit array within the message.

16. The method of claim 1, wherein:

the first neighboring node comprises a respective bit-indexed forwarding table; and

the first forwarding table entry comprises

a first identifier configured to be included within the forwarded message and to be used by the first node on the path of the forwarded message in conveying the message to the first neighboring node, and

a second identifier configured to be included within the forwarded message and to alert the first neighboring node to access 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 bit-indexed forwarding table comprising multiple forwarding table entries, wherein each of the multiple 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 an incoming message bit array, wherein

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,

compare the incoming message bit array to a first neighbor bit array associated with a first forwarding table entry of the multiple 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 toward the first neighboring node a copy of the message comprising a forwarded message bit array, wherein a first node on the path of the forwarded message does not comprise a respective bit-indexed forwarding table.

18. The network device of claim 17, wherein:

the first node on the path of the forwarded message is the first neighboring node; and

the processor is further configured to send a separate copy of the message to each of the destination nodes determined to be both an intended destination for the message and a reachable destination from the first neighboring node.

19. The network device of claim 17, wherein:

the first node on the path of the forwarded message is the first neighboring node; and

the processor is further configured to

identify, for each of the destination nodes determined to be both an intended destination for the message and a reachable destination from the first neighboring node, a nearest node, along a path to the respective destination node, that comprises a respective bit-indexed forwarding table, and

send a separate copy of the message to each of the identified nodes.

20. The network device of claim 17, wherein:

the first neighboring node comprises a respective bit-indexed forwarding table; and

the first forwarding table entry comprises

a first identifier configured to be included within the forwarded message and to be used by the first node on the path of the forwarded message in conveying the message to the first neighboring node, and

a second identifier configured to be included within the forwarded message and to alert the first neighboring node to access the forwarded message bit array.

21. The network device of claim 20, wherein:

the memory is further configured to store a bit-indexed routing table; and

the routing table comprises entries only for nodes configured to use respective bit-indexed forwarding tables.