Bit indexed explicit replication packet encapsulation

Patent metadata

Field	Value
Publication number	US-9438432-B2
Application number	US-201514604092-A
Country	US
Kind code	B2
Filing date	Jan 23, 2015
Priority date	Sep 17, 2013
Publication date	Sep 6, 2016
Grant date	Sep 6, 2016

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.

First claim

What is claimed is:

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

Assignees

• Cisco Tech Inc

Inventors

• Shepherd Gregory J
• Wijnands Ijsbrand
• Martin Christian

Classifications

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L47/806

  Broadcast or multicast traffic · CPC title

• H04L12/18 Primary

  for broadcast or conference {, e.g. multicast} · CPC title

• H04L45/16

  Multipoint routing · CPC title

• H04L45/74

  Address processing for routing · CPC title