Method and apparatus for routing and congestion control in multicast networks

• US 6,427,166 B1
• Filed: 09/22/2000
• Issued: 07/30/2002
• Est. Priority Date: 04/20/1998
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Hanna, Stephen R., Kadansky, Miriam C., Hurst, Stephen A., Rosenzweig, Philip M., Wesley, Joseph
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US09/668,432
• Time in Patent Office: 676 Days
• Field of Search: 709/201, 709/220, 709/221, 709/222, 709/223, 709/224, 709/230, 709/238, 709/243, 709/244, 709/250, 709/235, 370/229, 370/232, 370/235, 370/236, 370/254
• US Class Current: 709/220
• CPC Class Codes: H04L 1/1867 Arrangements specially adapted for the transmitter end
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1863 comprising mechanisms for improved reliability, e.g. status reports arrangements for detecting or preventing errors by carrying supervisory signal the return channel H04L1/16
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 2001/0097 Relays

Abstract

An embodiment consistent with the present invention includes a method and apparatus for distributing multicast data. The method may be performed by a data processor and comprises the steps of forming a multicast repair tree including a sender, a plurality of heads, and a plurality of receivers, wherein at least one head is associated with the sender and at least one receiver is associated with the head; sending, by a sender to the plurality of heads and the plurality of receivers, a plurality of multicast messages at a data rate; receiving, by the sender from one of the plurality of heads, a congestion status associated with a receiver of the head; and slowing the data rate, by the sender, in accordance with the congestion status.

Claims

1. A method of distributing multicast data, comprising:

receiving, by a head from a sender, a multicast message having a prune indicator set, the prune indicator set based on a congestion feedback;

beginning, by the head, in response to receiving the multicast message, to monitor a plurality of receivers associated with the head to determine if any of the receivers are candidates for pruning; and

pruning, by the head, if the receiver is a pruning candidate.

2. The method of claim 1, wherein the beginning to monitor includes determining whether any of the plurality of receivers is slow.

3. The method of claim 1, wherein the beginning to monitor includes determining whether any of the plurality of receivers has requested excessive repairs from the head.

4. The method of claim 1, wherein the beginning to monitor includes determining whether any of the plurality of receivers is not responsive.

5. A method of distributing multicast data comprising:

receiving, by a head from a sender, a multicast message having a prune indicator set, the prune indicator set based on a congestion feedback; and

pruning, by the head, in response to the multicast message, the receivers.

6. The method of claim 5, wherein the pruning the receiver includes sending a disowned message to the pruned receiver.

7. The method of claim 5, wherein the pruning the receiver includes indicating that the head should not respond to a repair request from the receiver in the future.

8. A computer-readable medium for storing instructions for a computer to prune receivers, the instructions comprising:

receiving, by a head from a sender, a multicast message having a prune indicator set, the prune indicator set based on a congestion feedback;

beginning, by the head, in response to receiving the multicast message, to monitor a plurality of receivers associated with the head to determine if any of the receivers are candidates for pruning; and

pruning, by the head, if the receiver is a pruning candidate.

9. The computer-readable medium of claim 8, wherein the beginning to monitor includes determining whether any of the plurality of receivers is slow.

10. The computer-readable medium of claim 8, wherein the beginning to monitor includes determining whether any of the plurality of receivers has requested excessive repairs from the head.

11. The computer-readable medium of claim 8, wherein the beginning to monitor includes determining whether any of the plurality of receivers is not responsive.

12. A head in a multicast system, comprising:

means for receiving, from a sender, a multicast message having a prune indicator set, the prune indicator set based on a congestion feedback;

means for beginning, in response to receiving the multicast message, to monitor a plurality of receivers associated with the head to determine if any of the receivers are candidates for pruning; and

means for pruning if the receiver is a pruning candidate.

13. A computer-readable medium for storing instructions for a computer to prune receivers, the instructions comprising:

receiving, by a head from a sender, a multicast message having a prune indicator set, the prune indicator set based on a congestion feedback; and

pruning, by the head, in response to the multicast message, the receivers.

14. The computer-readable medium of claim 13, wherein the pruning the receiver includes sending a disowned message to the pruned receiver.

15. The computer-readable medium of claim 13, wherein the pruning the receiver includes indicating that the head should not respond to a repair request from the receiver in the future.

16. A head in a multicast system, comprising:

means for receiving, from a sender, a multicast message having a prune indicator set, the prune indicator set based on a congestion feedback; and

means for pruning in response to the multicast message, the receivers.