OPTIMIZED EQUAL-COST MULTI-PATH (ECMP) FORWARDING DECISION IN BIT INDEX EXPLICIT REPLICATION (BIER)

• US 20190014034A1
• Filed: 01/07/2016
• Published: 01/10/2019
• Est. Priority Date: 01/07/2016
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: ALLAN, David Ian
• Granted Patent: US 10,873,524 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

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

1. A method implemented by a network device for multicasting packets in a multipath network, the method to reduce an overall number of hops that copies of a packet traverse in the 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 a proper subset of the second subset of multicast destination nodes.

2. 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 one or more determined outgoing interfaces.

3. The method of claim 2, wherein determining the one or more outgoing interfaces through which to forward the packet comprises tie-breaking, among candidate outgoing interfaces that were not removed from consideration, using an entropy value either specified in the packet or gleaned from packet information.

4. 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.

5. The method of claim 1, wherein the network implements Bit Index Explicit Replication (BIER) and the network device acts as a bit-forwarding router (BFR) in the network.

6. The method of claim 5, wherein the header includes a destination bitstring, wherein each bit flagged in the destination bitstring represents a multicast destination node to which a copy of the packet should be delivered.

7. 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 a shortest path through the first outgoing interface, and 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, wherein the second outgoing interface bitstring identifies one or more BFRs reachable on a shortest path through the second outgoing interface.

8. The method of claim 7, wherein determining whether the first subset of multicast destination nodes is a 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.

9. A network device configured to multicast packets in a multipath network, the network device configured to reduce an overall number of hops that copies of a packet traverse in the 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 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, the multicast component further 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 network device, the multicast component further configured to 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, the multicast component further configured to 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 determining that the first subset of multicast destination nodes is a proper subset of the second subset of multicast destination nodes.

10. 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 one or more determined outgoing interfaces.

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 network, the operations to reduce an overall number of hops that copies of a packet traverse in the 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 a proper subset of the second subset of multicast destination nodes.

12. 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 one or more determined outgoing interfaces.

13. 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 candidate outgoing interfaces that were not removed from consideration, using an entropy value either specified in the packet or gleaned from packet information.

14. 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.

15. The non-transitory machine-readable medium of claim 11, wherein the network implements Bit Index Explicit Replication (BIER) and the network device acts as a bit-forwarding router (BFR) in the network.

16. The non-transitory machine-readable medium of claim 15, wherein the header includes a destination bitstring, wherein each bit flagged in the destination bitstring represents a multicast destination node to which a copy of the packet should be delivered.

17. 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 a shortest path through the first outgoing interface, and 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, wherein the second outgoing interface bitstring identifies one or more BFRs reachable on a shortest path through the second outgoing interface.

18. The non-transitory machine-readable medium of claim 17, wherein determining whether the first subset of multicast destination nodes is a 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.

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 configured to reduce an overall number of hops that copies of a packet traverse in the 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 couples to the non-transitory machine-readable storage medium, the processor configured to execute the virtual machine, where the virtual machine is configured to implement the multicast component, the multicast component 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, the multicast component further configured to 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, the multicast component further configured to 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 determining that the first subset of multicast destination nodes is a proper subset of the second subset of multicast destination nodes.

20. 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 one or more determined outgoing interfaces.