Method, system and program product for automated topology formation in dynamic distributed environments

• US 20060080417A1
• Filed: 10/12/2004
• Published: 04/13/2006
• Est. Priority Date: 10/12/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zhou, Nianjun, Boutboul, Irwin, Meliksetian, Dikran S., Prost, Jean-Pierre
• Granted Patent: US 8,200,789 B2
• Time in Patent Office: Days
• US Class Current: 709/220
• CPC Class Codes: H04L 41/042 comprising distributed management centres cooperatively managing the network
• CPC Class Codes: H04L 41/044 comprising hierarchical management structures
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A method for automated topology formation in a dynamic distributed environment includes configuring a master node in an active topology having nodes and intercommunciation paths between the nodes. The master node includes an automated topology formation application including a predefined topology policy definition and a representation of the active topology. The master node receives a communication from an entity, the communication including a topology event notification indicating an event affecting the active topology. Using the automated topology formation application, it is determined that the topology event notification affects a topology portion of the active topology and, based on the topology event notification, the representation of the affected topology portion of the active topology is modified according to the predefined topology policy definition.

Claims

1. A method for automated topology formation in a dynamic distributed environment, the method comprising the steps of:

configuring a master node in an active topology wherein a topology comprises nodes and intercommunciation paths between the nodes, wherein the nodes comprise one or more leaf nodes having only incoming edges thereto, one or more prime nodes having both incoming and outgoing edges, and one or more root nodes having only outgoing edges, the master node comprising an automated topology formation application, the automated topology formation application comprising a predefined topology policy definition and a representation of the active topology;

receiving at the configured master node a communication from an entity, said communication including a topology event notification, the topology event notification indicating an event affecting the active topology;

determining with the automated topology formation application that the topology event notification affects a topology portion of the active topology; and

based on the topology event notification, modifying the representation of the affected topology portion of the active topology according to the predefined topology policy definition.

2. The method of claim 1, wherein the modifying step further comprises the steps of:

determining topology update information for corresponding affected nodes of the affected topology portion wherein the topology update information is determined based on the topology event notification; and

transmitting the topology update information to corresponding affected nodes of the affected topology portion.

3. The method of claim 1, wherein said event affecting the active topology comprises one or more of:

an inquiry from the entity with respect to adding the entity to the active topology as a new node;

the removal of an existing node from the active topology; and

an overload condition of an existing node within the active topology.

4. The method of claim 3, wherein for said event affecting the active topology of adding the entity to the topology as a new node, the master node selects a prime node for the entity, informs the selected prime of said entity, and informs the entity of the identity of the selected prime.

5. The method of claim 4, wherein said master node updates said topology by selecting one or more existing nodes in said topology to act as a prime for said entity.

6. The method of claim 4, wherein said master node updates said topology by promoting a leaf node to a prime node, and assigning said promoted prime node to said entity.

7. The method of claim 4, wherein said master node is further configured to reassign the relationship between nodes in a portion of said topology containing said entity.

8. The method of claim 4, wherein said master node is further configured to reconfigure said topology upon incorporating said entity therein.

9. The method of claim 3, wherein for said detected condition of the removal of an existing node from said topology, said master node updates said topology and informs affected primes and other entities of the updates.

10. The method of claim 9, wherein the removed node is a prime node, and said master node updates said topology by selecting one or more alternative prime nodes to perform the duties of said removed prime node.

11. The method of claim 9, wherein the removed node is a prime node, and said master node updates said topology by promoting a leaf node to a prime node to perform the duties of said removed prime node.

12. The method of claim 9, wherein said master node is further configured to reassign the relationship between nodes in a portion of said topology previously containing the removed node.

13. The method of claim 9, wherein said master node is further configured to reconfigure said topology to exclude the removed node.

14. The method of claim 3, wherein for said detected condition of an overload condition of an existing node within said topology, said master node updates said topology and informs affected primes and other entities of the updates.

15. The method of claim 14, wherein the overloaded node is a prime node, and said master node updates said topology by selecting one or more alternative prime nodes to share at least a portion of the duties of said overloaded prime node.

16. The method of claim 14, wherein the overloaded node is a prime node, and said master node updates the topology by promoting a leaf node to a prime node to share at least a portion of the duties of said overloaded prime node.

17. The method of claim 14, wherein said master node is further configured to reassign the relationship between nodes in a portion of said topology containing the overloaded node to reduce the load on the overloaded node.

18. The method of claim 14, wherein said master node is further configured to reconfigure said topology by balancing the load therein.

19. The method of claim 1, wherein said predefined topology policy is based on one or more of:

an expected set of tasks to be performed by a node, said node comprising a prime node;

services offered by a node, said node comprising any one of a not-a-node, leaf, prime or root node;

hardware features of a node, said node comprising any one of a not-a-node, leaf, prime or root node;

capabilities of one or more communication networks interconnecting nodes, said node comprising any one of a not-a-node, leaf, prime or root node;

a desired security of said topology;

a desired reliability of said topology; and

a desired performance of said topology.

20. The method of claim 1, wherein one or more nodes are configured with a prime management service that enables said nodes to function as prime nodes, and wherein said master node is capable of commanding a node to deploy said prime management service associated therewith.

21. The method of claim 20, wherein said master node is further capable of commanding a node to undeploy said prime management service associated therewith.

22. The method of claim 21, wherein said master node is configured to remove a designated prime node from said topology by initially reassigning one or more nodes reporting to said designated prime node to one or more other prime nodes.

23. The method of claim 1, wherein said master node is also a leaf node within said topology.

24. The method of claim 1, wherein the dynamic distributed environment comprises a grid computing environment.

25. The method of claim 24, wherein:

said master node comprises a root prime;

said one or more prime nodes comprise primes; and

said one or more leaf nodes comprise hosts.

26. The method of claim 2, comprising the further steps of:

receiving, by an application of a first entity having an initial topology role, the topology update information from the master node, wherein the first entity has an initial topology role of any one of not-a-node, root node, prime node or leaf node, and;

when the topology role of the first entity is to change, the received information comprises a new topology role that the first entity is to assume;

when the topology role of the first entity is to change and the new topology role is any one of a prime node or leaf node, the received information comprises any one of a complete list of parent entities or a list of changes of parent entities that are parents to the entity in the topology;

when the topology role of the first entity is to change and the new topology role is any one of a root node or a prime node, the received information comprises any one of a complete list of subordinate entities or a list of changes of subordinate entities that are subordinate to the entity in the topology;

deriving a local topology representation information from the received topology information wherein the local topology representation information comprises any one of;

a first entity topology role as any one of a not-a-node, root node, a prime node or a leaf node for the topology;

a list of entities that are parents of the first entity in the topology, or

a list of entities that are subordinates to the first entity in the topology; and

setting the local topology representation information at the first entity.

27. A computer program product for automated topology formation in a dynamic distributed environment, comprising:

a storage medium readable by a processing circuit, the storage medium comprising machine readable computer program code including instructions for causing the processing circuit to implement a method, the method further comprising;

configuring a master node in an active topology wherein a topology comprises nodes and intercommunciation paths between the nodes, wherein the nodes comprise one or more leaf nodes having only incoming edges thereto, one or more prime nodes having both incoming and outgoing edges, and one or more root nodes having only outgoing edges, the master node comprising an automated topology formation application, the automated topology formation application comprising a predefined topology policy definition and a representation of the active topology;

receiving at the configured master node a communication from an entity, said communication including a topology event notification, the topology event notification indicating an event affecting the active topology;

determining with the automated topology formation application that the topology event notification affects a topology portion of the active topology; and

based on the topology event notification, modifying the representation of the affected topology portion of the active topology according to the predefined topology policy definition.

28. The computer program product of claim 27, comprising the further step of:

determining topology update information for corresponding affected nodes of the affected topology portion wherein the topology update information is determined based on the topology event notification; and

transmitting the topology update information to corresponding affected nodes of the affected topology portion.

29. The computer program product of claim 27, wherein said event affecting the active topology comprises one or more of:

an inquiry from the entity with respect to adding the entity to the active topology as a new node;

the removal of an existing node from the active topology; and

an overload condition of an existing node within the active topology.

30. The computer program product of claim 29, wherein for said event affecting the active topology of adding the entity to the topology as a new node, the master node selects a prime node for the entity, informs the selected prime of said entity, and informs the entity of the identity of the selected prime.

31. The computer program product of claim 30, wherein said master node updates said topology by selecting one or more existing nodes in said topology to act as a prime for said entity.

32. The computer program product of claim 30, wherein said master node updates said topology by promoting a leaf node to a prime node, and assigning said promoted prime node to said entity.

33. The computer program product of claim 30, wherein said master node is further configured to reassign the relationship between nodes in a portion of said topology containing said entity.

34. The computer program product of claim 29, wherein for said detected condition of the removal of an existing node from said topology, said master node updates said topology and informs affected primes and other entities of the updates.

35. The computer program product of claim 34, wherein the removed node is a prime node, and said master node updates said topology by selecting one or more alternative prime nodes to perform the duties of said removed prime node.

36. The computer program product of claim 34, wherein the removed node is a prime node, and said master node updates said topology by promoting a leaf node to a prime node to perform the duties of said removed prime node.

37. The computer program product of claim 34, wherein said master node is further configured to reassign the relationship between nodes in a portion of said topology previously containing the removed node.

38. The computer program product of claim 34, wherein said master node is further configured to reconfigure said topology to exclude the removed node.

39. The computer program product of claim 29, wherein for said detected condition of an overload condition of an existing node within said topology, said master node updates said topology and informs affected primes and other entities of the updates.

40. The computer program product of claim 39, wherein the overloaded node is a prime node, and said master node updates said topology by selecting one or more alternative prime nodes to share at least a portion of the duties of said overloaded prime node.

41. The computer program product of claim 39, wherein the overloaded node is a prime node, and said master node updates the topology by promoting a leaf node to a prime node to share at least a portion of the duties of said overloaded prime node.

42. The computer program product of claim 39, wherein said master node is further configured to reassign the relationship between nodes in a portion of said topology containing the overloaded node to reduce the load on the overloaded node.

43. The computer program product of claim 39, wherein said master node is further configured to reconfigure said topology by balancing the load therein.

44. A system for automated topology formation in a dynamic distributed environment, comprising:

a network;

a first computer system in communication with the network, wherein the first computer system includes instructions for implementing a method, the method further comprising;

configuring a master node in an active topology wherein a topology comprises nodes and intercommunciation paths between the nodes, wherein the nodes comprise one or more leaf nodes having only incoming edges thereto, one or more prime nodes having both incoming and outgoing edges, and one or more root nodes having only outgoing edges, the master node comprising an automated topology formation application, the automated topology formation application comprising a predefined topology policy definition and a representation of the active topology;

receiving at the configured master node a communication from an entity, said communication including a topology event notification, the topology event notification indicating an event affecting the active topology;

determining with the automated topology formation application that the topology event notification affects a topology portion of the active topology; and

based on the topology event notification, modifying the representation of the affected topology portion of the active topology according to the predefined topology policy definition.

45. The system of claim 44, further comprising:

determining topology update information for corresponding affected nodes of the affected topology portion wherein the topology update information is determined based on the topology event notification; and

transmitting the topology update information to corresponding affected nodes of the affected topology portion.

46. The system of claim 44, wherein said event affecting the active topology comprises one or more of:

an inquiry from the entity with respect to adding the entity to the active topology as a new node;

the removal of an existing node from the active topology; and

an overload condition of an existing node within the active topology.

47. The system of claim 46, wherein for said event affecting the active topology of adding the entity to the topology as a new node, the master node selects a prime node for the entity, informs the selected prime of said entity, and informs the entity of the identity of the selected prime.

48. The system of claim 47, wherein said master node updates said topology by selecting one or more existing nodes in said topology to act as a prime for said entity.

49. The system of claim 47, wherein said master node updates said topology by promoting a leaf node to a prime node, and assigning said promoted prime node to said entity.

50. The system of claim 47, wherein said master node is further configured to reassign the relationship between nodes in a portion of said topology containing said entity.

51. The system of claim 47, wherein said master node is further configured to reconfigure said topology upon incorporating said entity therein.

52. The system of claim 46, wherein for said detected condition of the removal of an existing node from said topology, said master node updates said topology and informs affected primes and other entities of the updates.

53. The system of claim 52, wherein the removed node is a prime node, and said master node updates said topology by selecting one or more alternative prime nodes to perform the duties of said removed prime node.

54. The system of claim 52, wherein the removed node is a prime node, and said master node updates said topology by promoting a leaf node to a prime node to perform the duties of said removed prime node.

55. The system of claim 52, wherein said master node is further configured to reassign the relationship between nodes in a portion of said topology previously containing the removed node.

56. The system of claim 52, wherein said master node is further configured to reconfigure said topology to exclude the removed node.

57. The system of claim 56, wherein for said detected condition of an overload condition of an existing node within said topology, said master node updates said topology and informs affected primes and other entities of the updates.

58. The system of claim 57, wherein the overloaded node is a prime node, and said master node updates said topology by selecting one or more alternative prime nodes to share at least a portion of the duties of said overloaded prime node.

59. The system of claim 57, wherein the overloaded node is a prime node, and said master node updates the topology by promoting a leaf node to a prime node to share at least a portion of the duties of said overloaded prime node.

60. The system of claim 57, wherein said master node is further configured to reassign the relationship between nodes in a portion of said topology containing the overloaded node to reduce the load on the overloaded node.

61. The system of claim 57, wherein said master node is further configured to reconfigure said topology by balancing the load therein.

62. A method for automated topology formation in a dynamic distributed environment, the method comprising the steps of:

receiving, by an application of a first entity having an initial topology role, topology information from a master node, wherein first entity has an initial topology role of any one of not-a-node, root node, prime node or leaf node, and;

when the topology role of the first entity is to change, the received information comprises a new topology role that the first entity is to assume;

when the topology role of the first entity is to change and the new topology role is any one of a prime node or leaf node, the received information comprises any one of a complete list of parent entities or a list of changes of parent entities that are parents to the entity in the topology;

when the topology role of the first entity is to change and the new topology role is any one of a root node or a prime node, the received information comprises any one of a complete list of subordinate entities or a list of changes of subordinate entities that are subordinate to the entity in the topology;

deriving a local topology representation information from the received topology information wherein the local topology representation information comprises any one of;

a first entity topology role as any one of a not-a-node, root node, a prime node or a leaf node for the topology;

a list of entities that are parents of the first entity in the topology, or

a list of entities that are subordinates to the first entity in the topology; and

setting the local topology representation information at the first entity.

63. The method of claim 62, further comprising:

determining in a second topology application at a second entity that a potential topology affecting event has occurred; and

transmitting a notification of the potential topology affecting event to the master node, whereby the master node responds to the notification of the potential topology affecting event by transmitting the topology information to the first entity.

64. The method of claim 62, further comprising:

determining in the topology application at the first entity that a potential topology affecting event has occurred; and

transmitting a notification of the potential topology affecting event to the master node, whereby the master node responds to the notification of the potential topology affecting event by transmitting the topology information to the first entity.

65. The method of claim 62, wherein the list of entities comprises any one of a MAC address, an IP address, a URL, a fully qualified host name or an RFID.

66. A computer program product for automated topology formation in a dynamic distributed environment, comprising:

a storage medium readable by a processing circuit, the storage medium comprising machine readable computer program code including instructions for causing the processing circuit to implement a method, the method further comprising;

receiving, by an application of a first entity having an initial topology role, topology information from a master node, wherein first entity has an initial topology role of any one of not-a-node, root node, prime node or leaf node, and;

when the topology role of the first entity is to change, the received information comprises a new topology role that the first entity is to assume;

when the topology role of the first entity is to change and the new topology role is any one of a prime node or leaf node, the received information comprises any one of a complete list of parent entities or a list of changes of parent entities that are parents to the entity in the topology;

when the topology role of the first entity is to change and the new topology role is any one of a root node or a prime node, the received information comprises any one of a complete list of subordinate entities or a list of changes of subordinate entities that are subordinate to the entity in the topology;

deriving a local topology representation information from the received topology information wherein the local topology representation information comprises any one of;

a first entity topology role as any one of a not-a-node, root node, a prime node or a leaf node for the topology;

a list of entities that are parents of the first entity in the topology, or

a list of entities that are subordinates to the first entity in the topology; and

setting the local topology representation information at the first entity.

67. The computer program product of claim 66, further comprising:

determining in a second topology application at a second entity that a potential topology affecting event has occurred; and

transmitting a notification of the potential topology affecting event to the master node, whereby the master node responds to the notification of the potential topology affecting event by transmitting the topology information to the first entity.

68. The computer program product of claim 66, further comprising:

determining in the topology application at the first entity that a potential topology affecting event has occurred; and

transmitting a notification of the potential topology affecting event to the master node, whereby the master node responds to the notification of the potential topology affecting event by transmitting the topology information to the first entity.

69. The computer program product of claim 66, wherein the list of entities comprises any one of a MAC address, an IP address, a URL, a fully qualified host name or an RFID.

70. A system for automated topology formation in a dynamic distributed environment, comprising:

a network;

a first computer system in communication with the network, wherein the first computer system includes instructions for implementing a method, the method further comprising;

receiving, by an application of a first entity having an initial topology role, topology information from a master node, wherein first entity has an initial topology role of any one of not-a-node, root node, prime node or leaf node, and;

when the topology role of the first entity is to change, the received information comprises a new topology role that the first entity is to assume;

when the topology role of the first entity is to change and the new topology role is any one of a prime node or leaf node, the received information comprises any one of a complete list of parent entities or a list of changes of parent entities that are parents to the entity in the topology;

when the topology role of the first entity is to change and the new topology role is any one of a root node or a prime node, the received information comprises any one of a complete list of subordinate entities or a list of changes of subordinate entities that are subordinate to the entity in the topology;

deriving a local topology representation information from the received topology information wherein the local topology representation information comprises any one of;

a first entity topology role as any one of a not-a-node, root node, a prime node or a leaf node for the topology;

a list of entities that are parents of the first entity in the topology, or

a list of entities that are subordinates to the first entity in the topology; and

setting the local topology representation information at the first entity.

71. The system of claim 70, further comprising:

determining in a second topology application at a second entity that a potential topology affecting event has occurred; and

transmitting a notification of the potential topology affecting event to the master node, whereby the master node responds to the notification of the potential topology affecting event by transmitting the topology information to the first entity.

72. The system of claim 70, further comprising:

determining in the topology application at the first entity that a potential topology affecting event has occurred; and

transmitting a notification of the potential topology affecting event to the master node, whereby the master node responds to the notification of the potential topology affecting event by transmitting the topology information to the first entity.

73. The system of claim 70, wherein the list of entities comprises any one of a MAC address, an IP address, a URL, a fully qualified host name or an RFID.