Forming equal cost multipath multicast distribution structures

• US 7,839,850 B2
• Filed: 06/01/2006
• Issued: 11/23/2010
• Est. Priority Date: 01/30/2006
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kompella, Kireeti
• Primary Examiner(s): Phan; Man
• Assistant Examiner(s): Zhao; Wei
• Application Number:
  US11/445,370
• Publication Number:
  US 20070177594A1
• Time in Patent Office: 1,636 Days
• Field of Search: 370/238, 370/248, 370/392, 370/432, 370/396, 370/216, 370/229, 370/390
• 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:

receiving configuration information at a device indicating a number N of a plurality of instances for a multicast group from a single source device; and

joining, at the device, the N instances of the multicast group by sending join requests to become a member of the N instances of the multicast group, wherein each of the N instances corresponds to a different multicast distribution structure within the network for the multicast group, wherein two or more of the different multicast distribution structures for the multicast group comprise alternate multicast distribution structures that define different paths from the source device to a given receiver device, and wherein each of the join requests specifies a different one of the N instances of the multicast group to be joined.

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.

3. The method of claim 1, further comprising distributing the join requests among the plurality of upstream devices by sending each of the join requests for the different N instances along different paths towards the source device.

4. The method of claim 1, wherein receiving configuration information comprises using a discovery protocol to distribute the number N of instances.

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

6. The method of claim 1, wherein receiving configuration information comprises configuring the number N of instances by an administrator.

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

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

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

10. The method of claim 1, further comprising:

receiving with the 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.

11. The method of claim 10,

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.

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

13. 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 (LOP).

29. The method claim 1, further comprising creating an entry in forwarding information of the device for each of the N instances of the multicast group.

30. The method of claim 1, wherein each of the join requests includes control information that is extended to include an instance number specifying the instance of the multicast group to be joined.

31. The method of claim 30, wherein the control information comprises a header comprising a group identification field that includes a group identifier, a source identifier, and an instance number.

32. The method of claim 1, wherein the device comprises the given receiver device.

33. The method of claim 1, wherein the device comprises an intermediate device between the source device and the given receiver device.

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

receiving, at a source device for a multicast group, join requests for N instances of a multicast group, wherein at least two of the join requests are received on different paths from a single receiver to the source device, wherein each Of the join requests specifies a different one of the N instances of the multicast group to be joined;

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

sending multicast content for the multicast group to the receiver device via a multicast distribution structure corresponding to the selected one of the N instances, wherein the multicast distribution structure is one of two or more alternate multicast distribution structures that define different paths from the source device to the receiver device.

15. The method of claim 14, 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.

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

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

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

19. A network device comprising:

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

a multicast protocol operable on the control unit for generating join requests for N instances of a multicast group, wherein each of the N instances corresponds to a different multicast distribution structure for the multicast group, wherein two or more of the different multicast distribution structures comprise alternate multicast distribution structures that define different paths from the source device to a given receiver device, 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.

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

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

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

23. The network device of claim 19,

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.

24. The network device of claim 23,

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.

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

26. 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 devices,

wherein each of the N instances corresponds to a different multicast distribution structure for the multicast group, wherein two or more of the different multicast distribution structures comprise alternate multicast distribution structures that define different paths from the source device to a given receiver device, and wherein 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.

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

28. A non-transitory computer-readable medium comprising instructions for causing a programmable processor to:

receive configuration information specifying a number N of a plurality of instances 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, wherein two or more of the different multicast distribution structures comprise alternate multicast distribution structures that define different paths from the source device to a given receiver device; 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 to become a member of each of the N instances, wherein each of the join requests specifies a different one of the N instances of the multicast group to be joined.