# US 10,873,524 B2 · Optimized equal-cost multi-path (ECMP) forwarding decision in bit index explicit replication (BIER) > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,873,524 B2 - Document ID: US10873524B2 - Status: Granted - Kind: B2 - Application number: 16/064,663 - Filed: 2016-01-07 - Published: 2019-01-10 - Granted: 2020-12-22 - Earliest claimed: 2016-01-07 - Assignees: Telefonaktiebolaget LM Ericsson (publ) - Applicants: Telefonaktiebolaget LM Ericsson (publ) - Inventors: David Ian Allan - Web page: https://patentgrep.com/patent/US10873524B2 ## CPC - H04L 45/16: Multipoint routing - H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops - H04L 45/24: Multipath - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method implemented by a network device for multicasting packets in a network. The method reduces an overall number of hops that copies of a packet traverse in the network to serve a set of multicast destination nodes. The method includes receiving a packet, determining a first subset of multicast destination nodes that is a subset of the set of multicast destination nodes that is reachable on a shortest path through a first outgoing interface, determining a second subset of multicast destination nodes that is a subset of the set of multicast destination nodes that is reachable on a shortest path through a second outgoing interface, 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 in response to determining that the first subset is a proper subset of the second subset. ## Claims ### Claim 1 A method implemented by a network device for multicasting packets in a multipath network, the method being implemented 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 method 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. ### Claim 2 (depends on 1) The method of claim 1, further comprising: determining one or more outgoing interfaces through which to forward the packet among one or more candidate outgoing interfaces that were not removed from consideration; and forwarding the packet through the determined one or more outgoing interfaces. ### Claim 3 (depends on 2) The method of claim 2, wherein determining the one or more outgoing interfaces through which to forward the packet comprises tie-breaking, among the one or more candidate outgoing interfaces that were not removed from consideration, using an entropy value either specified in the packet or gleaned from packet information. ### Claim 4 (depends on 2) The method of claim 2, further comprising: determining whether all outgoing interfaces of the network device that can only serve a proper subset of the set of multicast destination nodes that can be served by any other outgoing interface of the network device have been removed from consideration before determining the one or more outgoing interfaces through which to forward the packet. ### Claim 5 (depends on 1) The method of claim 1, wherein the multipath network implements Bit Index Explicit Replication (BIER) and the network device acts as a bit-forwarding router (BFR) in the multipath network. ### Claim 6 (depends on 5) The method of claim 5, wherein the header includes a destination bitstring, and wherein each bit flagged in the destination bitstring represents a multicast destination node to which a copy of the packet should be delivered. ### Claim 7 (depends on 6) The method of claim 6, wherein determining the first subset of multicast destination nodes comprises creating a first bitstring by applying a bit-wise AND operation on the destination bitstring and a first outgoing interface bitstring, wherein the first outgoing interface bitstring identifies one or more BFRs reachable on the shortest path through the first outgoing interface, wherein determining the second subset of multicast destination nodes comprises creating a second bitstring by applying a bit-wise AND operation on the destination bitstring and a second outgoing interface bitstring, and wherein the second outgoing interface bitstring identifies one or more BFRs reachable on the shortest path through the second outgoing interface. ### Claim 8 (depends on 7) The method of claim 7, wherein determining whether the first subset of multicast destination nodes is the proper subset of the second subset of multicast destination nodes comprises determining whether a set of bits flagged in the first bitstring is a proper subset of a set of bits flagged in the second bitstring. ### Claim 9 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. ### Claim 10 (depends on 9) The network device of claim 9, wherein the multicast component is further configured to determine one or more outgoing interfaces through which to forward the packet among one or more candidate outgoing interfaces that were not removed from consideration and forward the packet through the determined one or more outgoing interfaces. ### Claim 11 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. ### Claim 12 (depends on 11) The non-transitory machine-readable medium of claim 11, wherein the computer code, when executed by the set of one or more processors of the network device, causes the network device to perform further operations comprising: determining one or more outgoing interfaces through which to forward the packet among one or more candidate outgoing interfaces that were not removed from consideration; and forwarding the packet through the determined one or more outgoing interfaces. ### Claim 13 (depends on 12) The non-transitory machine-readable medium of claim 12, wherein determining the one or more outgoing interfaces through which to forward the packet comprises tie-breaking, among the one or more candidate outgoing interfaces that were not removed from consideration, using an entropy value either specified in the packet or gleaned from packet information. ### Claim 14 (depends on 12) The non-transitory machine-readable medium of claim 12, wherein the computer code, when executed by the set of one or more processors of the network device, causes the network device to perform further operations comprising: determining whether all outgoing interfaces of the network device that can only serve a proper subset of the set of multicast destination nodes that can be served by any other outgoing interface of the network device have been removed from consideration before determining the one or more outgoing interfaces through which to forward the packet. ### Claim 15 (depends on 11) The non-transitory machine-readable medium of claim 11, wherein the multipath network implements Bit Index Explicit Replication (BIER) and the network device acts as a bit-forwarding router (BFR) in the multipath network. ### Claim 16 (depends on 15) The non-transitory machine-readable medium of claim 15, wherein the header includes a destination bitstring, and wherein each bit flagged in the destination bitstring represents a multicast destination node to which a copy of the packet should be delivered. ### Claim 17 (depends on 16) The non-transitory machine-readable medium of claim 16, wherein determining the first subset of multicast destination nodes comprises creating a first bitstring by applying a bit-wise AND operation on the destination bitstring and a first outgoing interface bitstring, wherein the first outgoing interface bitstring identifies one or more BFRs reachable on the shortest path through the first outgoing interface, wherein determining the second subset of multicast destination nodes comprises creating a second bitstring by applying a bit-wise AND operation on the destination bitstring and a second outgoing interface bitstring, and wherein the second outgoing interface bitstring identifies one or more BFRs reachable on the shortest path through the second outgoing interface. ### Claim 18 (depends on 17) The non-transitory machine-readable medium of claim 17, wherein determining whether the first subset of multicast destination nodes is the proper subset of the second subset of multicast destination nodes comprises determining whether a set of bits flagged in the first bitstring is a proper subset of a set of bits flagged in the second bitstring. ### Claim 19 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. ### Claim 20 (depends on 19) The computing device of claim 19, wherein the multicast component is further configured to determine one or more outgoing interfaces through which to forward the packet among one or more candidate outgoing interfaces that were not removed from consideration and forward the packet through the determined one or more outgoing interfaces.