Method and Apparatus for Concurrent Topology Discovery

• US 20090141659A1
• Filed: 12/03/2007
• Published: 06/04/2009
• Est. Priority Date: 12/03/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Verma, Dinesh C., Martin, Daniel Joseph
• Granted Patent: US 8,625,457 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/04 Network management architectures or arrangements
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A method, system and computer-usable medium are disclosed for discovering the topology of a network by using multiple discovery agents operating in parallel. A NodeList containing information about known nodes in a target network is received. The number (‘K’) of discovery agents to be used is determined, where 1<=K<=TotalNumberOfNodes). The nodes are partitioned into node groups, each of which has a group identifier respectively assigning it to a discovery agent ‘M’ where 1<=M<=K. A GraphList is created to hold information about known and discovered nodes. Each entry in the NodeList list is processed by its assigned discovery agent ‘M’, which sends probe messages to the target node to determine the node identifiers of discovered neighboring nodes. If the discovered nodes are not listed in the NodeList, then they are assigned to a node group for processing. If the connections between the target and the discovered neighboring node nodes are not listed in the GraphList, then they are added. Once all node and connection information is collected by the ‘K’ node discovery agents ‘M’ and listed in the GraphList, a network topology is generated.

Claims

1. A computer-implementable method for discovering the topology of a network, comprising:

receiving a first list of node entries, each of the node entries comprising a unique node identifier representing a known node;

performing operations on the unique node identifier of the node entries to partition the node entries into a plurality of node groups;

assigning a first node discovery agent to a first group of nodes and a second node discovery agent to a second group of nodes, the first and second node discovery agents operable to collect node information from a node;

collecting node information from a first node, the node information collected by the first node discovery agent and describing a connection between the first node and a second node;

appending the node information to a second list of node entries; and

processing the second list of node entries to generate a network topology.

2. The method of claim 1, further comprising:

determining if the node identifier of the second node is listed in the first list;

performing operations on the unique node identifier of the second node to determine its assignment to a node group if it is not;

appending the second node to the determined node group. collecting node information from the second node, the node information collected by the node discovery agent assigned to the determined node group and describing a connection between the second node and a third node.

3. The method of claim 1, wherein hash operations are performed on the unique node identifier to generate a hash value, the hash value operable to be used to partition the node entries into a plurality of node groups.

4. The method of claim 1, wherein the connection between the first node and a second node is physical.

5. The method of claim 1, wherein the connection between the first node and a second node is logical.

6. The method of claim 1, wherein a first connection between the first node and a second node is physical and a second connection is logical.

7. A system comprising:

a processor;

a data bus coupled to the processor; and

a computer-usable medium embodying computer program code, the computer-usable medium being coupled to the data bus, the computer program code discovering the topology of a network and comprising instructions executable by the processor and configured for;

receiving a first list of node entries, each of the node entries comprising a unique node identifier representing a known node;

performing operations on the unique node identifier of the node entries to partition the node entries into a plurality of node groups;

assigning a first node discovery agent to a first group of nodes and a second node discovery agent to a second group of nodes, the first and second node discovery agents operable to collect node information from a node;

collecting node information from a first node, the node information collected by the first node discovery agent and describing a connection between the first node and a second node;

appending the node information to a second list of node entries; and

processing the second list of node entries to generate a network topology.

8. The system of claim 7, further comprising:

determining if the node identifier of the second node is listed in the first list;

performing operations on the unique node identifier of the second node to determine its assignment to a node group if it is not;

appending the second node to the determined node group.

collecting node information from the second node, the node information collected by the node discovery agent assigned to the determined node group and describing a connection between the second node and a third node.

9. The system of claim 7, wherein hash operations are performed on the unique node identifier to generate a hash value, the hash value operable to be used to partition the node entries into a plurality of node groups.

10. The system of claim 7, wherein the connection between the first node and a second node is physical.

11. The system of claim 7, wherein the connection between the first node and a second node is logical.

12. The system of claim 7, wherein a first connection between the first node and a second node is physical and a second connection is logical.

13. A computer-usable medium embodying computer program code, the computer program code comprising computer executable instructions configured for:

receiving a first list of node entries, each of the node entries comprising a unique node identifier representing a known node;

performing operations on the unique node identifier of the node entries to partition the node entries into a plurality of node groups;

assigning a first node discovery agent to a first group of nodes and a second node discovery agent to a second group of nodes, the first and second node discovery agents operable to collect node information from a node;

collecting node information from a first node, the node information collected by the first node discovery agent and describing a connection between the first node and a second node;

appending the node information to a second list of node entries; and

processing the second list of node entries to generate a network topology.

14. The computer usable medium of claim 13, further comprising:

determining if the node identifier of the second node is listed in the first list;

performing operations on the unique node identifier of the second node to determine its assignment to a node group if it is not;

appending the second node to the determined node group.

collecting node information from the second node, the node information collected by the node discovery agent assigned to the determined node group and describing a connection between the second node and a third node.

15. The computer usable medium of claim 13, wherein hash operations are performed on the unique node identifier to generate a hash value, the hash value operable to be used to partition the node entries into a plurality of node groups.

16. The computer usable medium of claim 13, wherein the connection between the first node and a second node is physical.

17. The computer usable medium of claim 13, wherein the connection between the first node and a second node is logical.

18. The computer usable medium of claim 13, wherein a first connection between the first node and a second node is physical and a second connection is logical.

19. The computer usable medium of claim 13, wherein the computer executable instructions are deployable to a client computer from a server at a remote location.

20. The computer usable medium of claim 13, wherein the computer executable instructions are provided by a service provider to a customer on an on-demand basis.