Forming multicast distribution structures using exchanged multicast optimization data

• US 20070177593A1
• 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 8,270,395 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• 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 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; and

sending a join request from the device to a selected upstream device to join the multicast group in response to the received message.

2. The method of claim 1, further comprising:

receiving a respective message from at least two upstream devices, wherein each of the messages includes multicast optimization data; and

selecting one of the different upstream devices based on the multicast optimization data.

3. The method of claim 2,

wherein selecting one of the different upstream devices comprises applying one or more criteria to the data of the messages to rank the upstream devices,

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.

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

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

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

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

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

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

10. The method of claim 2, further comprising:

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

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

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

12. The method of claim 2, wherein selecting one of the different upstream devices comprises selecting one of the upstream devices already receiving multicast content for the group based on the received multicast optimization data.

13. The method of claim 2, 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.

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

15. A method comprising:

sending with a device a message to one or more downstream devices located between the device and a receiver for a multicast group, wherein the message includes multicast optimization data that specifies at least one criterion for selecting an upstream device; and

receiving a join request from at least one of the downstream devices to join the multicast group in response to the sent message.

16. A network device comprising:

an interface to receive a message from an upstream device, wherein the message contains multicast optimization data (MOD) that specifies at least one criterion for selecting an upstream device; and

a control unit to generate an appropriate multicast action request with respect to a multicast distribution structure within a network based on the MOD, wherein the interface outputs the multicast action request to at least one other device in the network.

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

18. The network device of claim 16, 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.

19. The network device of claim 16, 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.

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

21. The network device of claim 16,

wherein the control unit selects one of a plurality of potential upstream devices that could provide content for the multicast group based on the MOD, and

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

22. 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, and communicate the first message to a second network device via a protocol; and

a second network device to receive the first message, generate a second message containing second MOD that specifies at least one criterion for selecting an upstream device, and communicate the second message to the first network device via the protocol,

wherein the first network device receives the second message and issues an appropriate multicast action request based on the first and second MOD.

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

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

25. The system of claim 22, wherein the first network device selects one of a plurality of potential upstream devices that could provide content for the multicast group based on the MOD, communicates a join request to the selected upstream device, and receives multicast content for the multicast group from the selected upstream device.

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

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

receive messages containing multicast optimization data pertaining to a plurality of upstream devices for a multicast group, wherein the multicast optimization data specifies at least one criterion for selecting an upstream device; and

issue an appropriate multicast action request based on the data.

28. The computer-readable medium of claim 27, wherein the instructions cause the processor to:

select one of the plurality of potential upstream devices from which to receive multicast content for the multicast group based on the multicast optimization data;

communicate a join request to the selected upstream device; and

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