Method and apparatus for routing and congestion control in multicast networks

• US 6,151,633 A
• Filed: 04/20/1998
• Issued: 11/21/2000
• Est. Priority Date: 04/20/1998
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (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/063,637
• Time in Patent Office: 946 Days
• Field of Search: 709/220, 709/223, 709/224, 709/225, 709/227, 709/230, 709/232, 709/233, 709/234, 709/235, 709/238, 370/229, 370/232, 370/235, 370/236, 370/254
• US Class Current: 709/235
• 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 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 the sender to the plurality of heads and to 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 status associated with a receiver of the at least one head;

slowing the data rate, by the sender, in accordance with the status; and

signaling, by the sender, the heads to monitor receivers for pruning candidates if predetermined criteria are satisfied.

2. The method of claim 1, wherein the status is a congestion status.

3. The method of claim 1, wherein the step of signaling includes the step of setting an indicator in at least one of the multicast messages to indicate that the heads should begin to monitor their receivers for pruning candidates.

4. The method of claim 1, wherein the step of signaling includes the step of determining when a minimum data rate has been reached and setting a prune indicator in at least one of the multicast messages to indicate that the heads can begin to prune their receivers.

5. The method of claim 2, further comprising the step of:

incrementally increasing, by the sender, the data rate if there is no congestion reported in the system.

29. The method of claim 1, wherein the predetermined criteria is that at least one of the receivers runs at a data rate lower than the sender data rate.

30. The method of claim 1, wherein the predetermined criteria is that at least one of the receivers is not responsive.

31. The method of claim 1, wherein the predetermined criteria is that at least one of the receivers requests an excessive number of repairs from the at least one head.

6. An apparatus that distributes multicast data, comprising:

circuitry configured to form 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 at least one head;

circuitry configured to send to the plurality of heads and to the plurality of receivers, a plurality of multicast messages at a data rate;

circuitry configured to receive from one of the plurality of heads, a status associated with a receiver of the head;

circuitry configured to slow the data rate in accordance with the status; and

circuitry configured to signal, by the sender, the heads to monitor receivers for pruning candidates if predetermined criteria are satisfied.

7. The apparatus of claim 6, wherein the status is a congestion status.

8. The apparatus of claim 6, wherein the circuitry configured to signal further includes circuitry configured to set an indicator in at least one of the multicast messages to indicate that the heads should begin to monitor their receivers for pruning candidates.

9. The apparatus of claim 6, wherein the circuitry configured to signal further includes circuitry configured to determine when a minimum data rate has been reached and to set a prune indicator in at least one of the multicast messages to indicate that the heads can begin to prune their receivers.

10. The apparatus of claim 7, further comprising:

circuitry configured to increase incrementally, by the sender, the data rate if there is no congestion reported in the system.

11. An apparatus for distributing multicast data, comprising:

means for forming a multicast repair tree including a sender, a plurality of head, and a plurality of receivers wherein at least one head is associated with the sender, and at least one receiver is associated with the at least one head;

means for sending to the plurality of heads and to the plurality of receivers, a plurality of multicast messages having a data rate;

means for receiving from one of the plurality of heads, a status associated with a receiver of the head;

means for slowing the data rate in accordance with the status; and

means for signaling, by the sender, the heads to monitor receivers for pruning candidates if predetermined criteria are satisfied.

12. The apparatus of claim 11, wherein the status is a congestion status.

13. The apparatus of claim 11, wherein the means for signaling further includes means for setting an indicator in at least one of the multicast messages to indicate that the heads should begin to monitor their receivers for pruning candidates.

14. The apparatus of claim 11, wherein the means for signaling further includes means for determining when a minimum data rate has been reached and for setting a prune indicator in at least one of the multicast messages to indicate that the heads can begin to prune their receivers.

15. The apparatus of claim 12, further comprising the step of:

incrementally increasing, by the sender, the data rate if there is no congestion reported in the system.

16. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for distributing multicast data, the computer program product including;

first computer readable program code devices configured to form 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 at least one head;

second computer readable program code devices configured to send, by the sender to the plurality of heads and to the plurality of receivers, a plurality of multicast messages at a data rate;

third computer readable program code devices configured to receive, by the sender from one of the plurality of heads, a status associated with a receiver of the head;

fourth computer readable program code devices configured to slow the data rate, by the sender, in accordance with the status; and

fifth computer readable program code devices configured to signal, by the sender, the heads to monitor receivers for pruning candidates if predetermined criteria are satisfied.

17. The computer program product of claim 16, wherein the fifth computer readable program code devices configured to signal further include computer readable program code devices to set an indicator in at least one of the multicast messages to indicate that the heads should begin to monitor their receivers for pruning candidates.

18. The computer program product of claim 16, wherein the fifth computer readable program code devices configured to signal includes computer readable program code devices configured to determine when a minimum data rate has been reached and to set a prune indicator in at least one of the multicast messages to indicate that the heads can begin to prune their receivers.

19. The computer program product of claim 17, further comprising computer readable program code devices configured to increase, by the sender, the data rate if there is no congestion reported in the system.

20. A computer data signal embodied in a carrier wave and representing sequences of instructions which, when executed by a processor, cause the processor to distribute multicast data by performing the steps of:

executing a first computer program to form 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 at least one head;

executing a second computer program to send, by the sender to the plurality of heads and to the plurality of receivers, a plurality of multicast messages at a data rate;

executing a third computer program to receive, by the sender from one of the plurality of heads, a status associated with a receiver of the head;

executing a fourth computer program to slow the data rate, by the sender, in accordance with the status; and

executing a fifth computer program to signal, by the sender, the heads to monitor receivers for pruning candidates if predetermined criteria are satisfied.

21. The computer data signal of claim 20, wherein the status is a congestion status.

22. The computer data signal of claim 20, wherein the step of executing the fifth computer program to signal includes the step of setting an indicator in at least one of the multicast messages to indicate that the heads should begin to monitor their receivers for pruning candidates.

23. The computer data signal of claim 20, wherein the step of executing the fifth computer program to signal includes the step of determining when a minimum data rate has been reached and setting a prune indicator in at least one of the multicast messages to indicate that the heads can begin to prune their receivers.

24. The computer data signal of claim 21, further comprising the steps of:

executing a sixth computer program to increase incrementally, by the sender, the data rate if there is no congestion reported in the system.

25. An apparatus that distributes multicast data, comprising:

circuitry configured to receive a plurality of multicast messages from a sender at a data rate;

circuitry configured to determine a receiver status;

circuitry configured to send a congestion report to a head in accordance with the receiver status; and

circuitry configured to receive a disowned message from the head in accordance with the congestion report.

26. An apparatus for distributing multicast data, comprising:

means for receiving a plurality of multicast messages from a sender at a data rate;

means for determining a receiver status;

means for sending a congestion report to a head in accordance with the receiver status; and

means for receiving a disowned message from the head in accordance with the congestion report.

27. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for distributing multicast data, the computer program product including;

computer readable program code devices configured to receiv a plurality of multicast messages from a sender at a data rate;

computer readable program code devices configured to determine a receiver status;

computer readable program code devices configured to send a congestion report to a head in accordance with the receiver status; and

computer readable program code devices configured to receive a disowned message from the head in accordance with the congestion report.

28. A computer data signal embodied in a carrier wave and representing sequences of instructions which, when executed by a processor, cause the processor to distribute multicast data by performing the steps of:

executing a computer program to receive a plurality of multicast messages from a sender at a data rate;

executing the computer program to determine a receiver status;

executing the computer program to send a congestion report to a head in accordance with the receiver status; and

executing the computer program to receive a disowned message from the head in accordance with the congestion report.

32. A method of distributing multicast data, performed by a data processor, comprising the steps of:

sending a plurality of multicast messages at a data rate to a plurality of heads and to a plurality of receivers;

receiving a status associated with a receiver of one of the plurality of heads;

slowing the data rate in accordance with the status;

nd

signaling, by the sender, the heads to monitor receivers for pruning candidates if predetermined criteria are satisfied.

33. An apparatus that distributes multicast data, comprising:

circuitry configured to send a plurality of multicast messages at a data rate to a plurality of heads and to a plurality of receivers;

circuitry configured to receive a status associated with a receiver of one of the plurality of heads;

circuitry configured to slow the data rate in accordance with the status; and

circuitry configured to signal, by the sender, the heads to monitor receivers for pruning candidates if predetermined criteria are satisfied.

34. An apparatus for distributing multicast data, comprising:

means for sending a plurality of multicast messages at a data rate to a plurality of heads and to a plurality of receivers;

means for receiving a status associated with a receiver of one of the plurality of heads;

means for slowing the data rate in accordance with the status; and

means for signaling, by the sender, the heads to monitor receivers for pruning candidates if predetermined criteria are satisfied.

35. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for distributing multicast data, the computer program product including;

computer readable program code devices configured to send a plurality of multicast messages at a data rate to a plurality of heads and to a plurality of receivers;

computer readable program code devices configured to receive a status associated with a receiver of one of the plurality of heads;

computer readable program code devices configured to slow the data rate in accordance with the status; and

computer readable program code devices configured to signal, by the sender, the heads to monitor receivers for pruning candidates if predetermined criteria are satisfied.

36. A computer data signal embodied in a carrier wave and representing sequences of instructions which, when executed by a processor, cause the processor to distribute multicast data by performing the steps of:

executing a computer program to send a plurality of multicast messages at a data rate to a plurality of heads and a plurality of receivers;

executing the computer program to receive a status associated with a receiver of one of the plurality of heads; and

executing the computer program to slow the data rate in accordance with the status;

indicating that the head should not respond to a repair request from the receiver in the future.

37. A method of distributing multicast data, performed by a data processor, comprising the steps of:

receiving a plurality of multicast messages from a sender at a data rate, wherein each multicast message contains a congestion signal and a prune signal;

monitoring a receiver in response to the congestion signal;

marking a receiver for pruning in response to the prune signal; and

sending a disowned message to the receiver marked for pruning.

38. An apparatus that distributes multicast data, comprising:

circuitry configured to receive a plurality of multicast messages from a sender at a data rate, wherein each multicast message contains a congestion signal and a prune signal;

circuitry configured to monitor a receiver in response to the congestion signal;

circuitry configured to mark a receiver for pruning in response to the prune signal; and

circuitry configured to send a disowned message to the receiver marked for pruning.

39. An apparatus for distributing multicast data, comprising:

means for receiving a plurality of multicast messages from a sender at a data rate, wherein each multicast message contains a congestion signal and a prune signal;

means for monitoring a receiver in response to the congestion signal;

means for marking a receiver for pruning in response to the prune signal; and

means for sending a disowned message to the receiver marked for pruning.

40. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for distributing multicast data, the computer program product including;

computer readable program code devices configured to receive a plurality of multicast messages from a sender at a data rate, wherein each multicast message contains a congestion signal and a prune signal;

computer readable program code devices configured to monitor a receiver in response to the congestion signal;

computer readable program code devices configured to mark a receiver for pruning in response to the prune signal; and

computer readable program code devices configured to send a disowned message to the receiver marked for pruning.

41. A computer data signal embodied in a carrier wave and representing sequences of instructions which, when executed by a processor, cause the processor to distribute multicast data by performing the steps of:

executing the computer program to receive a plurality of multicast messages from a sender at a data rate, wherein each multicast message contains a congestion signal and a prune signal;

executing the computer program to monitor a receiver in response to the congestion signal;

executing the computer program to mark a receiver for pruning in response to the prune signal; and

executing the computer program to send a disowned message to the receiver marked for pruning.

42. A method of distributing multicast data, performed by a data processor, comprising the steps of:

receiving a plurality of multicast messages from a sender at a data rate;

determining a receiver status;

sending a congestion report to a head in accordance with the receiver status; and

receiving a disowned message from the head in accordance with the congestion report.