Forming equal cost multipath multicast distribution structures

• US 20070177594A1
• Filed: 06/01/2006
• Published: 08/02/2007
• Est. Priority Date: 01/30/2006
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kompella, Kireeti
• Granted Patent: US 7,839,850 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/24 Multipath

Abstract

Techniques allow network devices to set up multiple multicast distribution structures for a given multicast group and source. According to the techniques, a multicast protocol is extended to include an instance number in the control messages, where the instance number corresponds to one of a plurality of instances for the multicast group and source. The network device sends a join request for each of the N instances for the multicast group to a plurality of upstream routers. Each of the join requests specifies a different instance of the multicast group to be joined. The source device for the multicast group selects one of the N instances, for example using a unicast Equal Cost Multipath (ECMP) hashing algorithm, and sends multicast content for the multicast group to via the multicast distribution structure corresponding to the selected one of the N instances.

Claims

1. A method of forming multicast distribution structures within a network comprising:

joining, at a device, a plurality of instances N of a multicast group from a single source device, wherein each of the N instances corresponds to a different multicast distribution structure within the network for the multicast group.

2. The method of claim 1, wherein joining comprises sending a join request for each of the N instances from the device to a plurality of upstream devices located between the device and the source device for the multicast group, wherein each of the join requests specifies a different one of the N instances of the multicast group to be joined.

3. The method of claim 1, further comprising distributing the join requests among the plurality of upstream devices.

4. The method of claim 1, further comprising specifying at the device the plurality of instances N for the multicast group.

5. The method of claim 4, wherein specifying at a device a plurality of instances N of a multicast distribution structure for a multicast group comprises using a discovery protocol to distribute the plurality of instances N.

6. The method of claim 5, wherein the discovery protocol is one of Multicast Virtual Private Network (MVPN) protocol or Multicast Virtual Private Local Area Network Service (MVPLS) protocol.

7. The method of claim 4, wherein specifying at a device a plurality of instances N of a multicast distribution structure for a multicast group comprises configuring the plurality of instances N by an administrator.

8. The method of claim 7, further comprising configuring the plurality of instances N to be the same for all multicast groups in the network.

9. The method of claim 7, further comprising configuring the plurality of instances N independently for each multicast group in the network.

10. The method of claim 1, wherein the device comprises an end-user receiving device or an intermediate device.

11. The method of claim 1, further comprising:

receiving with a device a respective message from at least two upstream devices located between the device and a source for a multicast group, wherein the message includes multicast optimization data that specifies at least one criterion for selecting an upstream device; and

selecting at least one and up to N of the at least two upstream devices based on the multicast optimization data,

wherein sending a join request comprises sending the join requests for each of the N instances from the device to the selected upstream devices to join the N instances for the multicast group.

12. The method of claim 11,

wherein selecting at least one and up to N of the at least two upstream devices comprises applying one or more criteria to the multicast optimization data of the messages to rank the upstream devices, and

wherein the criteria for ranking the upstream devices includes one or more of minimization of multicast traffic duplication for the instances of the multicast group within the network, load balancing the multicast traffic within the network, and selecting a network path experiencing shorter communication delays.

13. The method of claim 1, wherein the multicast distribution structures corresponding to the N instances are partially overlapping.

14. The method of claim 1, wherein joining the plurality of instances comprises joining the instances using an extension of one of the Protocol-Independent Multicast (PIM) protocol and the point-to-multipoint (P2MP) label distribution protocol (LDP).

15. A method of using multicast distribution structures within a network comprising:

selecting, at a source device for a multicast group, one of a plurality of instances N for the multicast group; and

sending multicast content for the multicast group to the device via the multicast distribution structure corresponding to the selected one of the N instances.

16. The method of claim 15, wherein selecting at the source device for the multicast group one of the N instances comprises using an equal cost multipath (ECMP) flow hash function to select the one of the N instances.

17. The method of claim 15, further comprising specifying at the device the plurality of instances N for the multicast group.

18. The method of claim 17, wherein specifying at a device a plurality of instances N of a multicast distribution structure for a multicast group comprises configuring the plurality of instances N by an administrator.

19. The method of claim 17, wherein specifying at a device a plurality of instances N of a multicast distribution structure for a multicast group comprises using a discovery protocol to distribute the plurality of instances N.

20. A network device comprising:

a control unit storing configuration data that specifies an instance number N;

a multicast protocol executing within the control unit that, based on the instance number N, generates Njoin requests for a plurality of instances N of a multicast group, wherein each of the N instances corresponds to a different multicast distribution structure for the multicast group, and wherein each of the join requests specifies a different one of the N instances of the multicast group to be joined; and

an interface to output the join requests to a plurality of upstream devices located between the network device and a source device for the multicast group to join the multicast group.

21. The network device of claim 20, wherein the control unit distributes the join requests among the plurality of upstream devices.

22. The network device of claim 20, wherein an administrator configures the control unit to specify the plurality of instances N for the multicast group.

23. The network device of claim 20, further comprising a discovery protocol executing within the control unit to distribute the plurality of instances N.

24. The network device of claim 20,

wherein the interface receives a respective message from at least two of the plurality of upstream devices, wherein each of the messages includes multicast optimization data that specifies at least one criterion for selecting an upstream device,

wherein the control unit selects one and up to N of the at least two upstream devices based on the multicast optimization data, and generates a join request for each of the N instances, and

wherein the interface outputs the join requests to the selected upstream devices to join the N instances for the multicast group.

25. The network device of claim 24,

wherein the control unit selects at least one and up to N of the at least two upstream devices by applying one or more criteria to the multicast optimization data of the messages to rank the upstream devices, and

wherein the criteria for ranking the upstream devices includes one or more of minimization of multicast traffic duplication for the instances of the multicast group within the network, load balancing the multicast traffic within the network, and selecting a network path experiencing shorter communication delays.

26. The network device of claim 20, wherein the multicast protocol comprises one of the Protocol-Independent Multicast (PIM) protocol and the point-to-multipoint (P2MP) label distribution protocol (LDP).

27. A system comprising:

a source device that provides multicast content for a multicast group; and

a network device coupled to the source device via a plurality of upstream devices located between the network device and the source device,

wherein the network device sends a join request for each of a specified plurality of instances N for a multicast group from the network device to the plurality of upstream routers,

wherein each of the N instances corresponds to a different multicast distribution structure for the multicast group, and each of the join requests specifies a different one of the N instances to be joined, and

wherein the source device selects one of the N instances and sends the multicast content for the multicast group to the network device via the multicast distribution structure corresponding to the selected one of the N instances.

28. The system of claim 27, wherein the network device distributes the join requests among the plurality of upstream devices.

29. A computer-readable medium comprising instructions for causing a programmable processor to:

specify a plurality of instances N for a multicast group from a single source device, wherein each of the N instances corresponds to a different multicast distribution structure for the multicast group; and

send a join request for each of the N instances from the device to a plurality of upstream routers located between the device and the source device for the multicast group, wherein each of the join requests specifies a different one of the N instances of the multicast group to be joined.