Method and apparatus for using ranking to select repair nodes in formation of a dynamic tree for multicast repair

• US 6,757,843 B1
• Filed: 10/26/2000
• Issued: 06/29/2004
• 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: Perlman, Radia J., Hurst, Stephen A., Rosenzweig, Philip M., Wesley, Joseph, Chiu, Dah Ming, Hanna, Stephen R., Kadansky, Miriam C.
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): ELISCA, PIERRE E
• Application Number:
  US09/698,490
• Time in Patent Office: 1,342 Days
• Field of Search: 714/18, 714/26, 714/20, 714/28, 714/38, 714/35, 714/4, 714/748, 709/219, 709/217, 709/218, 709/223, 705/14
• US Class Current: 714/18
• 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 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/46 Cluster building

Abstract

An embodiment consistent with the present invention includes a method and apparatus for forming a multicast repair tree. The methods perform by a data processor and comprises the steps of determining, for each of a plurality of potential heads in a multicast group, a ranking value associated with the potential head; advertising, by the potential heads to a plurality of potential receivers; prioritizing, by a potential receiver, the ranking values from the potential heads; and binding, by a potential receiver to the head having the highest ranking value, thereby forming a group of which the potential receiver,is a member and the potential head is the head. The ranking values may include “able”, “unable”, “willing”, and “reluctant.” The ranking value of a potential head determines in accordance with a static or a dynamic configuration. Ranking values determine dynamically based on ranges of system resource levels such as memory and available processor resources.

Claims

1. A method for forming a multicast repair tree, comprising:

determining, for each of a plurality of potential heads, a ranking value associated with the potential head;

advertising, by the potential heads to a plurality of potential receivers;

prioritizing, by a potential receiver, the ranking values of the potential heads; and

binding, by a potential receiver to the potential head having the highest ranking value, thereby forming a repair group of which the potential receiver is a member and the highest ranking potential head is the head.

2. The method of claim 1, wherein at least one potential head is a sender.

3. The method of claim 1, further including arbitrating between heads having the same ranking value.

4. The method of claim 1, wherein the membership limitation limits a number of receivers allowable as members of the group to a predetermined maximum.

5. Program code embodied in a carrier wave, the program code for causing a processor to form a multicast repair tree, by performing the steps of:

determining, for each of a plurality of potential heads, a ranking value associated with the potential head;

advertising, by the potential heads, to a plurality of potential receivers;

prioritizing, by a potential receiver, the ranking values from the potential heads; and

binding, by a potential receiver to the potential head having the highest ranking value, thereby forming a group of which the potential receiver is a member and the highest ranking potential head is the head.

6. The computer data signal of claim 5, wherein at least one potential head is a sender.

7. The computer data signal of claim 5, further including arbitrating between heads having the same ranking value.

8. An apparatus for forming a multicast repair tree, comprising:

a circuit configured to determine, for each of a plurality of potential heads, a ranking value associated with the potential head;

a circuit configured to advertise, by the potential heads to a plurality of potential receivers;

a circuit configured to prioritize, by a potential receiver, the ranking values from the potential heads; and

a circuit configured to bind, by a potential receiver to the potential head having the highest ranking value, thereby forming a group of which the potential receiver is a member and the highest ranking potential head is the head.

9. The apparatus of claim 8, wherein at least one potential head is a sender.

10. The apparatus of claim 8, further including circuitry configured to arbitrate between heads having the same ranking value.

11. A computer program product, comprising:

a computer usable medium having computer readable code embodied therein for forming a multicast repair tree, the computer program product including;

first program code configured to determine, for each of a plurality of potential heads, a ranking value associated with the potential head;

second program code configured to advertise, by the potential heads, to a plurality of potential receivers;

third program code configured to prioritize, by a potential receiver, the ranking values from the potential heads; and

fourth program code configured to bind, by a potential receiver to the potential head having the highest ranking value, thereby forming a group of which the potential receiver is a member and the highest ranking potential head is the head.

12. The computer program product of claim 11, wherein at least one potential head is a sender.

13. The computer program product of claim 11, further including arbitrating between heads having the same ranking value.

14. An apparatus for forming a multicast repair tree, comprising:

means for determining, for each of a plurality of potential heads, a ranking value associated with the potential head;

means for advertising, by the potential heads, to a plurality of potential receivers;

means for prioritizing, by a potential receiver, the ranking value from the potential heads; and

means for binding, by a potential receiver to the potential head having the highest ranking value, thereby forming a group of which the potential receiver is a member and the highest ranking potential head is the head.

15. A computer program product, comprising:

a computer useable medium having computer readable code embodied therein for forming a multicast repair tree, the computer program product including;

program code configured to receive advertisements from a plurality of potential heads;

program code configured to prioritize the ranking values from the potential heads; and

program code configured to bind to the potential head having the highest ranking value, thereby forming a group of which the highest ranking potential head is the head.

16. Program code embodied in a carrier wave, the program code for causing a processor to perform the steps of:

receiving a plurality of advertisements, each advertisement containing a ranking value from a plurality of potential heads;

prioritizing the ranking values from the potential heads; and

binding to the potential head having the highest ranking value, thereby forming a group of which the highest ranking potential head is the head.

17. A computer program product, comprising:

a computer usable medium having computer readable code embodied therein for forming a multicast repair tree, the computer program product including;

computer readable code devices configured to determine a ranking value associated with a potential head;

computer readable code devices configured to advertise to a plurality of potential receivers in accordance with the ranking value;

computer readable code devices configured to receive a join message from a potential receiver; and

computer readable code devices configured to add the potential receiver to a group.

18. The computer program product of claim 17, wherein a membership limitation is imposed.

19. Program code embodied in a carrier wave the program code for causing a processor to form a multicast repair tree, by performing the steps of:

determining a ranking value associated with a potential head;

advertising to a plurality of potential receivers in accordance with the ranking value;

receiving a join message from a potential receiver; and

adding the potential receiver to a group.

20. The computer data signal of claim 19, wherein wherein a membership limitation is imposed.