Optimized equal-cost multi-path (ECMP) forwarding decision in bit index explicit replication (BIER)

A network device configured to multicast packets in a multipath network, the network device being configured to reduce an overall number of hops that copies of a packet traverse in the multipath network to serve a set of multicast destination nodes, the network device comprising:

• a non-transitory machine-readable storage medium having stored therein a multicast component;
• and
• a processor communicatively coupled to the non-transitory machine-readable storage medium, the processor being configured to execute the multicast component, wherein the multicast component is configured to:
• receive the packet, wherein the packet is encapsulated in a header that identifies the set of multicast destination nodes,
• determine a first subset of multicast destination nodes, wherein the first subset of multicast destination nodes is a subset of the set of multicast destination nodes that is reachable on a shortest path through a first outgoing interface of the network device,
• determine a second subset of multicast destination nodes, wherein the second subset of multicast destination nodes is a subset of the set of multicast destination nodes that is reachable on a shortest path through a second outgoing interface of the network device,
• determine whether the first subset of multicast destination nodes is a proper subset of the second subset of multicast destination nodes, and
• remove the first outgoing interface from consideration as a candidate outgoing interface through which to forward the packet in response to a determination that the first subset of multicast destination nodes is the proper subset of the second subset of multicast destination nodes.

A non-transitory machine-readable medium having computer code stored therein, which when executed by a set of one or more processors of a network device in a multipath network, causes the network device to perform operations for multicasting packets in the multipath network, the operations being performed to reduce an overall number of hops that copies of a packet traverse in the multipath network to serve a set of multicast destination nodes, the operations comprising:

• receiving the packet, wherein the packet is encapsulated in a header that identifies the set of multicast destination nodes;
• determining a first subset of multicast destination nodes, wherein the first subset of multicast destination nodes is a subset of the set of multicast destination nodes that is reachable on a shortest path through a first outgoing interface of the network device;
• determining a second subset of multicast destination nodes, wherein the second subset of multicast destination nodes is a subset of the set of multicast destination nodes that is reachable on a shortest path through a second outgoing interface of the network device;
• determining whether the first subset of multicast destination nodes is a proper subset of the second subset of multicast destination nodes;
• and
• removing the first outgoing interface from consideration as a candidate outgoing interface through which to forward the packet in response to determining that the first subset of multicast destination nodes is the proper subset of the second subset of multicast destination nodes.

A computing device implementing a plurality of virtual machines for implementing network function virtualization (NFV), wherein a virtual machine from the plurality of virtual machines is configured to multicast packets in a multipath network, the virtual machine being configured to reduce an overall number of hops that copies of a packet traverse in the multipath network to serve a set of multicast destination nodes, the computing device comprising:

• a non-transitory machine-readable storage medium having stored therein a multicast component;
• and
• a processor communicatively coupled to the non-transitory machine-readable storage medium, the processor being configured to execute the virtual machine, wherein the virtual machine is configured to implement the multicast component, the multicast component being configured to:
• determine a first subset of multicast destination nodes, wherein the first subset of multicast destination nodes is a subset of the set of multicast destination nodes that is reachable on a shortest path through a first outgoing interface of the computing device,
• determine a second subset of multicast destination nodes, wherein the second subset of multicast destination nodes is a subset of the set of multicast destination nodes that is reachable on a shortest path through a second outgoing interface of the computing device,
• determine whether the first subset of multicast destination nodes is a proper subset of the second subset of multicast destination nodes, and
• remove the first outgoing interface from consideration as a candidate outgoing interface through which to forward the packet in response to a determination that the first subset of multicast destination nodes is the proper subset of the second subset of multicast destination nodes.