Forming multicast distribution structures using exchanged multicast optimization data

• US 8,270,395 B2
• Filed: 06/01/2006
• Issued: 09/18/2012
• Est. Priority Date: 01/30/2006
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Kompella, Kireeti
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Zhao, Wei
• Application Number:
  US11/445,353
• Publication Number:
  US 20070177593A1
• Time in Patent Office: 2,301 Days
• Field of Search: 370/329, 370/341, 370/338, 370/390, 370/432, 370/353, 455/518, 709/238, 709/232, 709/205
• US Class Current: 370/353
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• 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

Abstract

Network devices in a multicast network exchange multicast optimization data to improve efficiency of multicasting in the network. A protocol, e.g., a routing protocol or a multicast protocol, may be extended to allow the network devices to exchange the multicast optimization data. Alternatively, a separate protocol may be established for exchanging MOD. A network device may receive a message from an upstream device 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. The device may use the data to intelligently select an optimal upstream device for receiving multicast using any of a variety of criteria to rank the upstream routers, such as minimization of multicast traffic duplication, load balancing current bandwidth levels, and avoiding paths experiencing communication delays.

Claims

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

receiving with a device a respective message from two or more different upstream devices located between the device and a source for a multicast group,

wherein each of the messages includes respective multicast optimization data that at least indicates whether the respective upstream device already receives multicast traffic for the multicast group;

ranking at least two of the two or more different upstream devices based on one or more criteria applied to the multicast optimization data;

selecting one of the two or more different upstream devices to which to send a join request for the multicast group based on the ranking; and

sending the join request for the multicast group from the device to the selected upstream device to join the multicast group in response to the received messages.

2. The method of claim 1,

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

3. The method of claim 1, wherein the multicast optimization data indicates at least one of a number of other devices downstream from the respective upstream device that have already joined the multicast group, a number of dependent downstream devices for which the upstream device is the only potential upstream device that can provide the multicast data for the multicast group, a number of non-dependent downstream devices capable of receiving the multicast data from the upstream device or at least one other upstream device, a number of potential upstream devices, a number of potential downstream devices, a distance from a source of the multicast group to the respective upstream device, a distance to the source from the respective upstream device, a delay from the source to the respective upstream device, a number of multicast groups transiting the upstream device, and a total multicast bandwidth transiting the upstream device.

4. The method ofclaim 1, wherein receiving with the device the message from the upstream device comprises receiving a reply packet from the upstream device.

5. The method of claim 1, wherein receiving with the device the message from the upstream device comprises receiving an update packet from the upstream device.

6. The method of claim 1, wherein the device comprises an intermediate device having a plurality of downstream devices, the method further comprising:

receiving with the device a message from at least one downstream device, wherein the message includes multicast optimization data that specifies a criterion for selecting an upstream device; and

outputting messages relaying the multicast optimization data to the other downstream devices.

7. The method of claim 1, wherein receiving a message comprises receiving the message using one of an extended routing protocol or an extended multicast protocol.

8. The method of claim 1, wherein receiving with the device the message from the upstream device comprises receiving a message that identifies the multicast group and the source.

9. The method of claim 1, further comprising:

in response to receiving each of the messages from the different upstream devices, generating a message containing the multicast optimization data from each of the messages; and

communicating the generated message to the other one of the upstream devices.

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, wherein selecting one of the different upstream devices comprises selecting one of the upstream devices already receiving multicast content for the multicast group based on the received multicast optimization data.

12. The method of claim 1, further comprising sending a leave request to the non-selected upstream devices to leave the multicast group prior to issuing the join request to the selected upstream device.

13. The method of claim 1, further comprising storing the data to a data structure,

wherein the data structure includes entries for pairs of multicast groups and sources for different upstream and downstream devices, and

wherein each entry stores the multicast optimization data.

14. A network device comprising:

an interface to receive a respective message from at least two different upstream devices located between the network device and a source for a multicast group,

wherein each of the messages contains respective multicast optimization data (MOD) that at least indicates whether the respective upstream device already receives multicast traffic for the multicast group; and

a control unit to rank at least two of the two or more different upstream devices based on one or more criteria applied to the multicast optimization data, and to select one of the different upstream devices to which to

send an appropriate multicast action request for the multicast group based on the ranking and

generate the appropriate multicast action request with respect to a multicast distribution structure within a network based on the ranking,

wherein the interface outputs the multicast action request to the selected upstream device.

15. The network device of claim 14, wherein the control unit maintains a data structure storing the MOD.

16. The network device of claim 14, wherein the received MOD indicates at least one of a number of other devices downstream from the respective upstream device that have already joined the multicast group, a number of dependent downstream devices for which the upstream device is the only potential upstream device that can provide the multicast data for the multicast group, a number of non-dependent downstream devices capable of receiving the multicast data from the upstream device or at least one other upstream device, a number of potential upstream devices, a number of potential downstream devices, a distance from a source of the multicast group to the respective upstream device, a distance to the source from the respective upstream device, a delay from the source to the respective upstream device, a number of multicast groups transiting the upstream device, and a total multicast bandwidth transiting the upstream device.

17. The network device of claim 14, wherein the control unit generates a message containing at least some of the stored MOD, and wherein the interface communicates the message to a routing device in accordance with a protocol.

18. The network device of claim 17, wherein the protocol is one of a multicast protocol and a routing protocol.

19. The network device of claim 14,

wherein the appropriate multicast action request comprises a join request, and

wherein the interface communicates the join request to the selected upstream device, and receives multicast content for the multicast group from the selected upstream device.

20. A system comprising:

a first network device to generate a first message containing first multicast optimization data (MOD) that specifies at least one criterion for selecting an upstream device to which to send an appropriate multicast action request for a multicast group, and communicate the first message to a second network device via a protocol; and

the second network device to receive the first message, generate a second message containing second MOD that at least indicates whether the respective upstream device already receives multicast traffic for the multicast group, and communicate the second message to the first network device via the protocol,

wherein the first network device receives the second message,

ranks at least two of the two or more different upstream devices based on one or more criteria applied to the multicast optimization data;

selects one of a plurality of potential upstream devices based on the first and second MOD, and

issues the appropriate multicast action request for the multicast group based on the ranking.

21. The system of claim 20, wherein the multicast action request is one of a multicast join request and a multicast leave request.

22. The system of claim 20, wherein the protocol comprises one of a multicast protocol and a routing protocol.

23. The system of claim 20, wherein the multicast action request comprises a join request for the multicast group, wherein the first network device communicates the join request to the selected upstream device, and receives multicast content for the multicast group from the selected upstream device.

24. The system of claim 20, wherein the system comprises a local area network (LAN).

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

receive a respective message from at least two different upstream devices for a multicast group,

wherein each of the messages includes respective multicast optimization data pertaining to a plurality of upstream devices for the multicast group, and

wherein the multicast optimization data at least indicates whether the respective upstream device already receives multicast traffic for the multicast group;

rank at least two of the two or more different upstream devices based on one or more criteria applied to the multicast optimization data;

select one of the different upstream devices from which to receive multicast content for the multicast group based on the ranking; and

issue the appropriate multicast action request for the multicast group to the selected upstream device based on the ranking.

26. The non-transitory computer-readable medium of claim 25, wherein the instructions cause the processor to:

communicate a join request for the multicast group to the selected upstream device; and

receive the multicast content for the multicast group from the selected upstream device.

27. A method comprising:

prior to joining a multicast group, determining, with a device, a plurality upstream devices located between the device and a source for the multicast group;

sending, with the device, a respective message to at least two different upstream devices of the plurality of upstream devices, wherein each of the multicast optimization messages specifies a first set of multicast optimization data that includes information about the plurality of upstream devices;

receiving with the device a respective reply message from the at least two different upstream devices, wherein each of the reply messages includes a respective second set of multicast optimization data that at least indicates whether the respective upstream device already receives multicast traffic for the multicast group;

ranking at least two of the two or more different upstream devices based on one or more criteria applied to the multicast optimization data;

selecting one of the different upstream devices to which to send a join request for the multicast group based on the ranking;

sending the join request for the multicast group from the device to the selected upstream device to join the multicast group in response to the received response messages; and

receiving, with the device, multicast packets for the multicast group from the selected upstream device.