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

• US 6,185,698 B1
• Filed: 04/20/1998
• Issued: 02/06/2001
• 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: Perlman, Radia J., Chiu, Dah Ming, Hanna, Stephen R., Kadansky, Miriam C., Hurst, Stephen A., Rosenzweig, Philip M., Wesley, Joseph
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): ELISCA, PIERRE E
• Application Number:
  US09/063,498
• Time in Patent Office: 1,023 Days
• Field of Search: 714/18, 714/20, 714/38, 714/35, 714/4, 714/748, 709/219, 709/217, 709/218, 709/223
• 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 method may be performed 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 head may also be the sender. There may be a plurality of heads. The ranking values may include “able”, “unable”, “willing”, and “reluctant.” The ranking value of a potential head may be determined in accordance with a static or a dynamic configuration. Ranking values may be determined 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, performed by a data processor, comprising the steps of:

determining, for each of a plurality of potential heads, a ranking value associated with the potential head, wherein the ranking value is selected from a group including “

able”

, “

unable” and

“

reluctant”

;

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 repair group of which the potential receiver is a member and the highest ranking potential head is the head.

2. A method for forming a multicast repair tree, performed by a data processor, comprising the steps of:

determining, for each of a plurality of potential heads, a ranking value associated with the potential head, wherein the ranking value is selected from a group including “

able”

, “

unable” and

“

willing”

;

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 repair group of which the potential receiver is a member and the highest ranking potential head is the head.

3. A method for forming a multicast repair tree, performed by a data processor, comprising the steps of:

(1) determining, for each of a plurality of potential heads, a ranking value associated with the potential head, including

(a) determining whether the potential head has a static configuration, and

(b) determining the ranking value of the potential head in accordance with a dynamic configuration if the potential head is not statically configured to be a head;

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

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

(3) 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.

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

executing a first computer program to determine, for each of a plurality of potential heads, a ranking value associated with the potential head, wherein the ranking value is selected from a group including “

able”

, “

unable”

, and “

reluctant”

;

executing the first computer program to advertise, by the potential heads, to a plurality of potential receivers;

executing a second computer program to prioritize, by a potential receiver, the ranking values from the potential heads; and

executing the second computer program 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.

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

executing a first computer program to determine, for each of a plurality of potential heads, a ranking value associated with the potential head, wherein the ranking value is selected from a group including “

able”

, “

unable”

and “

willing”

;

executing the first computer program to advertise, by the potential heads, to a plurality of potential receivers;

executing a second computer program to prioritize, by a potential receiver, the ranking values from the potential heads; and

executing the second computer program 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.

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

(1) executing a first computer program to determine, for each of a plurality of potential heads, a ranking value associated with the potential head, including

(a) executing a computer program to determine whether the potential head has a static configuration, and

(b) executing a computer program to determine the ranking value of the potential head in accordance with a dynamic configuration if the potential head is not statically configured to be a head;

(2) executing the first computer program to advertise, by the potential heads, to a plurality of potential receivers;

(3) executing a second computer program to prioritize, by a potential receiver, the ranking values from the potential heads; and

(4) executing the second computer program 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.

7. 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, wherein the ranking value is selected from a group including “

able”

, “

unable” and

“

reluctant”

;

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.

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, wherein the ranking value is selected from a group including “

able”

, “

unable” and

“

willing”

;

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. An apparatus for forming a multicast repair tree, comprising:

(1) a circuit configured to determine, for each of a plurality of potential heads, a ranking value associated with the potential head, including

(a) circuitry configured to determine whether the potential head has a static configuration, and

(b) circuitry configured to determine the ranking value of the potential head in accordance with a dynamic configuration if the potential head is not statically configured to be a head;

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

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

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

10. A computer program product, comprising:

a computer usable medium having computer readable code embodied therein for forming a multicast repair tree that includes one or more systems, the computer program product including;

first computer readable program code devices configured to determine, for each of a plurality of potential heads, a ranking value associated with the potential head, wherein the ranking value is selected from a group including “

able”

, “

unable” and

“

reluctant”

;

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

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

fourth computer readable program code devices 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.

11. A computer program product, comprising:

a computer usable medium having computer readable code embodied therein for forming a multicast repair tree that includes one or more systems, the computer program product including;

first computer readable program code devices configured to determine, for each of a plurality of potential heads, a ranking value associated with the potential head, wherein the ranking value is selected from a group including “

able”

, “

unable” and

“

willing”

;

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

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

fourth computer readable program code devices 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. A computer program product, comprising:

a computer usable medium having computer readable code embodied therein for forming a multicast repair tree that includes one or more systems, the computer program product including;

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

computer readable program code devices to determine whether the potential head has a static configuration, and

computer readable program code devices to determine the ranking value of the potential head in accordance with a dynamic configuration if the potential head is not statically configured to be a head;

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

third computer readable program code devices configured to prioritize, by a potential receiver, the rankling values from the potential heads; and

fourth computer readable program code devices 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.