Method and apparatus for building a medium cost, self similar, self organizing multicast routing tree

• US 6,791,981 B1
• Filed: 03/21/2000
• Issued: 09/14/2004
• Est. Priority Date: 03/21/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Novaes, Marcos N.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Lee, Timothy
• Application Number:
  US09/532,638
• Time in Patent Office: 1,638 Days
• Field of Search: 370/256, 370/408, 370/432, 370/390, 370/254, 370/400, 709/238
• US Class Current: 370/390
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• 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/48 Routing tree calculation

Abstract

A method for building a hierarchical multicast tree which is centered around a specific node in an Internet Protocol (IP) communications network. The method on a subnetwork comprising dynamically electing a subnetwork leader node for each subnetwork using multicast communications confined to the subnetwork. Receiving a configuration file containing a list of all the network addresses of the nodes in a network. Receiving a number of permissible connections each subnetwork leader node in the network is permitted with other subnetwork leader nodes. And establishing a multicast connection between each subnetwork leader node as identified in the configuration file so that there is a multicast connection path from each subnetwork leader node for each subnetwork and a subnetwork containing a network leader node. In another embodiment, a system and computer readable medium is disclosed to carry out the above method.

Claims

1. A method for building a hierarchical multicast tree which is centered around a specific node in an Internet Protocol (IP) communications network, the method on a subnetwork comprising the steps of:

forming at least one subnetwork by joining one or more nodes with an identical subnetwork address using multicast communications confined to the subnetwork;

dynamically electing a subnetwork leader node for each subnetwork, using multicast communications confined to the subnetwork;

receiving a subnetwork list of all identified subnetwork leaders;

receiving a configuration file containing a list of all the network addresses of the nodes in a network, wherein the configuration file does not include a preconfigured groupings of nodes for each subnetwork;

receiving a number of permissible connections each subnetwork leader node in the network is permitted with other subnetwork leader nodes; and

establishing a multicast connection between each subnetwork leader node, as identified in the subnetwork list, so that there is a multicast connection path from each subnetwork leader node for each subnetwork and a subnetwork containing a network leader node.

2. The method according to claim 1, wherein the step of receiving a configuration file includes receiving a configuration file which identifies a weight number for electing a network leader node from the subnetwork leader nodes.

3. The method according to claim 2, further comprising the step of:

dynamically electing the network leader node utilizing the weight number in the configuration file.

4. The method according to claim 1, wherein the step of establishing a connection includes establishing a connection between each subnetwork leader node and a subnetwork containing a network leader node that has a minimum number of hops between each subnetwork leader node and the network leader node.

5. The method according to claim 1, wherein the step of receiving a configuration file includes receiving a configuration file that contains the permissible number of connections permitted by each subnetwork leader node including the network leader node;

and

wherein the step of establishing a connection includes establishing a connection between each subnetwork leader node and a subnetwork containing a network leader node up to the permissible number of connections permitted and if any subnetwork leader nodes are not connected to the network leader node after the permissible number of connections with the network leader node are established, connecting with subnetwork leader nodes already connected to the network leader node until the permissible number of connections permitted is met and until every subnetwork node is connected back to the network leader node with the minimum number of hops therebetween.

6. The method according to claim 1, wherein the step of receiving a configuration file includes receiving a configuration file containing a list of the subnetwork masks and the method further comprising the steps of:

masking the configuration file with the subnetwork mask to determine a sub-address range of each subnetwork; and

associating to a subnetwork leader node with one or more nodes with identical sub-address range.

7. A method on a node for building a hierarchical multicast communications network with one or more tiers of connection, the method comprising the steps of:

receiving a configuration file containing a list of all the network addresses and a subnetwork list containing a list of subnetwork addresses of the nodes in a network, wherein the configuration file does not include a preconfigured groupings of nodes for each subnetwork;

joining one or more other nodes with an identical subnetwork addresses to form a subnetwork, using multicast communications confined to the subnetwork;

monitoring if a node in the subnetwork is a subnetwork leader node and if after a predetermined period of time a node on the network is not identified as the subnetwork leader node, preforming the sub-steps of;

(a) becoming the subnetwork leader node for the subnetwork;

(b) querying the addresses of nodes outside the subnetwork to determine the connectivity status of the nodes outside the network; and

(c) connecting via multicast communications with each other subnetwork leader node outside the subnetwork so that the minimum number of hops exists between the network leader node and each subnetwork leader node associated therewith.

8. The method according to claim 7, wherein the step of receiving a configuration file includes receiving a configuration file that contains the permissible number of connections permitted by each subnetwork leader node including the network leader node;

and

wherein the step of connecting includes connecting via multicast communications with each other subnetwork leader node outside the subnetwork up to the permissible number of connections permitted so that the minimum number of hops exists between the network leader and each subnetwork leader node associated therewith and if any subnetwork leader nodes are not connected to the network leader after the permissible number of connections with the network leader node are established, connecting with subnetwork leader nodes already connected to the network leader until the permissible number of connections permitted are established until every subnetwork node is connected back to the network leader with a minimum number of hops therebetween.

9. A method for building a hierarchical multicast communications network with one or more tiers of connection, the method comprising the steps of:

associating one or more nodes in a first tier as a first tier subnetwork, using multicast communications confined to the first tier subnetwork;

receiving a configuration file containing a list of all the network addresses of the nodes in a network including a weight number for electing a network leader node from thc subnetwork leader nodes, wherein the configuration file does not include a preconfigured groupings of nodes for each first tier subnetwork;

electing a node in the first tier subnetwork as a network leader based upon the weight number; and

establishing a multicast connection between the network leader and one or more second tier subnetworks up to a predetermined permissible number of connections between the network leader node and a subnetwork leader for each second tier subnetwork such that the path of a newly connected subnetwork leader to the network leader results in the smallest number of hops.

10. A method for building a hierarchical multicast communications network with n tiers of connection, the method comprising the steps of:

associating one or more nodes to form n tier subnetworks, where n is a number from 1 to k and k is the total number of sub-addresses in a network, using multicast communications confined to each of the n tier subnetworks;

electing a subnetwork leader for each one of the n tier subnetworks;

receiving a configuration file containing a list of all the network addresses of the nodes in a network including a weight number for electing a network leader node from the subnetwork leader nodes, wherein the configuration file does not include a preconfigured groupings of nodes for each n tier subnetwork;

electing a node in the first tier subnetwork as a network leader based upon the weight number, and for each of the n tier subnetworks performing the following steps until all n tiers of the subnetworks are connected via multicast back to the network leader;

(a) establishing a multicast connection between the network leader and the subnetwork leader of each one of the n tiers if the number of predetermined permissible number of connections between the network leader node and a subnetwork leader for the n−

1 tier subnetwork has not been exceeded and;

(b) if the predetermined permissible number of connections has been exceed then establishing a connection between a subnetwork leader of a n−

1 tier subnetwork with one or more subnetwork leaders from a n tier subnetwork.

11. The method according to claim 10, wherein the step of electing a subnetwork leader node includes electing a subnetwork node with the highest IP address.

12. The method according to claim 10, wherein the step of receiving a configuration file includes receiving a configuration file on all nodes in the network.

13. The method according to claim 10, wherein the step of associating one or more nodes to form n tier subnetworks, includes the sub-step of:

masking the configuration file with a mask to determine the sub-network address for each node.

14. A computer readable medium containing programming instructions for building a hierarchical multicast tree which is centered around a specific node in an Internet Protocol (IP) communications network, the computer readable medium on a subnetwork the instructions comprising:

forming at least one subnetwork by joining one or more nodes with an identical subnetwork address using multicast communications confined to the subnetwork;

dynamically electing a subnetwork leader node for each subnetwork, using multicast communications confined to the subnetwork;

receiving a subnetwork list of all identified subnetwork leaders;

receiving a configuration file containing a list of all the network addresses of the nodes in a network, wherein the configuration file does not include a preconfigured groupings of nodes for each subnetwork;

receiving a number of permissible connections each subnetwork leader node in the network is permitted with other subnetwork leader nodes; and

establishing a multicast connection between each subnetwork leader node, as identified in the subnetwork list, so that there is a multicast connection path from each subnetwork leader node for each subnetwork and a subnetwork containing a network leader node.

15. The computer readable medium according to claim 14, wherein the programming instruction of receiving a configuration file includes receiving a configuration file which identifies a weight number for electing a network leader node from the subnetwork leader nodes.

16. The computer readable medium according to claim 15, further comprising the programming instruction of:

dynamically electing the network leader node utilizing the weight number in the configuration file.

17. The computer readable medium according to claim 14, wherein the programming instruction of establishing a connection includes establishing a connection between each subnetwork leader node and a subnetwork containing a network leader node that has a minimum number of hops between each subnetwork leader node and the network leader node.

18. The computer readable medium according to claim 14, wherein the programming instruction of receiving a configuration file includes receiving a configuration file that contains the permissible number of connections permitted by each subnetwork leader node including the network leader node;

and

wherein the programming instruction of establishing a connection includes establishing a connection between each subnetwork leader node and a subnetwork containing a network leader node up to the permissible number of connections permitted and if any subnetwork leader nodes are not connected to the network leader node after the permissible number of connections with the network leader node are established, connecting with subnetwork leader nodes already connected to the network leader node until the permissible number of connections permitted is met and until every subnetwork node is connected back to the network leader node with the minimum number of hops therebetween.

19. The computer readable medium according to claim 14, wherein the programming instruction of receiving a configuration file includes receiving a configuration file containing a list of the subnetwork masks and the computer readable medium further comprising the programming instructions of:

masking the configuration file with the subnetwork mask to determine a sub-address range of each subnetwork; and

associating to a subnetwork leader node with one or more nodes with identical sub-address range.

20. A computer readable medium containing programming instructions on a node for building a hierarchical multicast communications network with one or more tiers of connection, the computer readable medium comprising the programming instructions of:

receiving a configuration file containing a list of all the network addresses and a subnetwork list containing a list of subnetwork addresses of the nodes in a network, wherein the configuration file does not include a preconfigured groupings of nodes for each subnetwork;

joining one or more other nodes with an identical subnetwork addresses to form a subnetwork, using multicast communications confined to the subnetwork;

monitoring if a node in the subnetwork is a subnetwork leader node and if after a predetermined period of time a node on the network is not identified as the subnetwork leader node, preforming the sub-steps of;

(a) becoming the subnetwork leader node for the subnetwork;

(b) querying the addresses of nodes outside the subnetwork to determine the connectivity status of the nodes outside the network; and

(c) connecting via multicast communications with each other subnetwork leader node outside the subnetwork so that the minimum number of hops exists between the network leader node and each subnetwork leader node associated therewith.

21. The computer readable medium according to claim 20, wherein the programming instruction of receiving a configuration file includes receiving a configuration file that contains the permissible number of connections permitted by each subnetwork leader node including the network leader node;

and

wherein the programming instruction of connecting includes connecting via multicast communications with each other subnetwork leader node outside the subnetwork up to the permissible number of connections permitted so that the minimum number of hops exists between the network leader and each subnetwork leader node associated therewith and if any subnetwork leader nodes are not connected to the network leader after the permissible number of connections with the network leader node are established, connecting with subnetwork leader nodes already connected to the network leader until the permissible number of connections permitted are established until every subnetwork node is connected back to the network leader with a minimum number of hops therebetween.

22. A computer readable medium containing programming instructions for building a hierarchical multicast communications network with one or more tiers of connection, the computer readable medium comprising the programming instructions of:

associating one or more nodes in a first tier as a first tier subnetwork, using multicast communications confined to the first tier subnetwork;

receiving a configuration file containing a list of all the network addresses of the nodes in a network including a weight number for electing a network leader node from the subnetwork leader nodes, wherein the configuration file does not include a reconfigured groupings of nodes for each n tier subnetwork;

electing a node in the first tier subnetwork as a network leader based upon the weight number; and

establishing a multicast connection between the network leader and one or more second tier subnetworks up to a predetermined permissible number of connections between the network leader node and a subnetwork leader for each second tier subnetwork such that the path of a newly connected subnetwork leader to the network leader results in the smallest number of hops.

23. A computer readable medium containing programming instructions for building a hierarchical multicast communications network with n tiers of connection, the computer readable medium comprising the programming instructions of:

associating one or more nodes to form n tier subnetworks, where n is a number from 1 to k and k is the total number of sub-addresses in a network, using multicast communications confined to each of the n tier subnetworks;

electing a subnetwork leader for each one of the n tier subnetworks;

receiving a configuration file containing a list of all the network addresses of the nodes in a network including a weight number for electing a network leader node from the subnetwork leader nodes, wherein the configuration file does not include a preconfigured groupings of nodes for each n tier subnetwork;

electing a node in the first tier subnetwork as a network leader based upon the weight number; and

for each of the n tier subnetworks performing the following the programming instructions until all n tiers of the subnetworks are connected via multicast back to the network leader;

(a) establishing a multicast connection between the network leader and the subnetwork leader of each one of the n tiers if the number of predetermined permissible number of connections between the network leader node and a subnetwork leader for the n−

1 tier subnetwork has not been exceeded and;

(b) if the predetermined permissible number of connections has been exceed then establishing a connection between a subnetwork leader of a n−

1 tier subnetwork with one or more subnetwork leaders from a n tier subnetwork.

24. The computer readable medium according to claim 23, wherein the programming instruction of electing a subnetwork leader node includes electing a subnetwork node with the highest IP address.

25. The computer readable medium according to claim 23, wherein the programming instruction of receiving a configuration file includes receiving a configuration file on all nodes in the network.

26. The computer readable medium according to claim 23, wherein the programming instruction of associating one or more nodes to form n tier subnetworks, includes the programming instruction of:

masking the configuration file with a mask to determine the subnetwork address for each node.

27. A subnetwork for building a hierarchical multicast tree which is centered around a specific node in an Internet Protocol (IP) communications network, the subnetwork comprising:

at least one subnetwork formed by joining one or more other nodes with an identical subnetwork addresses using multicast communications confined to the subnetwork;

dynamically electing a subnetwork leader node for each subnetwork, using multicast communications confined to the subnetwork;

a transceiver for receiving a configuration file containing a list of all the network addresses of the nodes in a network and for receiving a subnetwork list of all identified subnetwork leaders, wherein the configuration file does not include a preconfigured groupings of nodes for each subnetwork, the transceiver receiving a number of permissible connections each subnetwork leader node in the network is permitted with other subnetwork leader nodes; and

the transceiver establishing a multicast connection between each subnetwork leader node as identified in the subnetwork list so that there is a multicast connection path from each subnetwork leader node for each subnetwork and a subnetwork containing a network leader node.

28. The subnetwork according to claim 27, wherein the configuration file further comprises an identifier for identifying a weight number for electing a network leader node from the subnetwork leader nodes.

29. The subnetwork according to claim 28, further comprising:

means for dynamically electing the network leader node utilizing the weight number in the configuration file.

30. The subnetwork according to claim 27, wherein the transceiver further comprises a means for establishing a connection between each subnetwork leader node and a subnetwork containing a network leader node that has a minimum number of hops between each subnetwork leader node and the network leader node.

31. The subnetwork according to claim 27, wherein the configuration file contains the permissible number of connections permitted by each subnetwork leader node including the network leader node;

and

wherein the transceiver for establishing a connection further comprises a means for establishing a connection between each subnetwork leader node and a subnetwork containing a network leader node up to the permissible number of connections permitted and if any subnetwork leader nodes are not connected to the network leader node after the permissible number of connections with the network leader node are established, connecting with subnetwork leader nodes already connected to the network leader node until the permissible number of connections permitted is met and until every subnetwork node is connected back to the network leader node with the minimum number of hops therebetween.

32. The subnetwork according to claim 27, wherein the configuration file contains a list of the subnetwork masks and further comprising:

means for masking the configuration file with the subnetwork mask to determine a sub-address range of each subnetwork; and

means for associating to a subnetwork leader node with one or more nodes with identical sub-address range.

33. A first tier subnetwork for building a hierarchical multicast communications network with one or more tiers of connection, comprising:

means for associating one or more nodes in a first tier as a first tier subnetwork, using multicast communications confined to the first tier subnetwork;

a transceiver for receiving a configuration file containing a list of all the network addresses and a subnetwork list containing a list of subnetwork addresses of the nodes in a network, wherein the configuration file does not include a preconfigured groupings of nodes for each subnetwork;

means for electing a node in the first tier subnetwork as a network leader based upon the weight number; and

means for establishing a multicast connection between the network leader and one or more second tier subnetworks up to a predetermined permissible number of connections between the network leader node and a subnetwork leader for each second tier subnetwork such that the path of a newly connected subnetwork leader to the network leader results in the smallest number of hops.