Method and apparatus for network topology discovery using closure approach

• US 7,821,966 B2
• Filed: 03/19/2007
• Issued: 10/26/2010
• Est. Priority Date: 03/19/2007
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: International Business Machines Corporation
• Inventors: Odintsova, Natalia, Guo, Shang Q., Rish, Irina, Beygelzimer, Alina, Ma, Sheng
• Primary Examiner(s): Ryman; Daniel J
• Assistant Examiner(s): OH, ANDREW CHUNG SUK
• Application Number:
  US11/687,750
• Publication Number:
  US 20080232262A1
• Time in Patent Office: 1,317 Days
• Field of Search: None
• US Class Current: 370/254
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

Improved network topology discovery techniques. For example, an automated method for discovering a topology of a network, having a plurality of nodes, includes the following steps. A first traceroute process is performed for a given source node and one or more destination nodes listed in a target list so as to discover one or more paths through one or more intermediate nodes between the given source node and the one or more destination nodes. The one or more intermediate nodes discovered during the first traceroute process are added to the target list. A second traceroute process is performed for the given source node and the one or more intermediate nodes discovered during the first traceroute process so as to discover one or more paths through one or more additional intermediate nodes between the given source node and the one or more intermediate nodes discovered during the first traceroute process.

Claims

1. An automated method for discovering a topology of a network comprising a plurality of nodes, the method comprising the steps of:

performing a first traceroute process for a given source node and one or more destination nodes listed in a target list so as to discover one or more paths through one or more intermediate nodes between the given source node and the one or more destination nodes;

adding the one or more intermediate nodes discovered during the first traceroute process to the target list; and

performing a second traceroute process for the given source node and the one or more intermediate nodes discovered during the first traceroute process so as to discover one or more paths through one or more additional intermediate nodes between the given source node and the one or more intermediate nodes discovered during the first traceroute process;

wherein;

(i) when one or more additional intermediate nodes are discovered as a result of performance of the second traceroute process, adding the one or more additional intermediate nodes to the target list and performing at least one subsequent traceroute process to determine the existence of any further intermediate nodes; and

(ii) when no new intermediate nodes are discovered as a result of performance of the second traceroute process or the at least one subsequent traceroute process, identifying the nodes in the target list as a target closure set for the given source node;

wherein the target closure set for the given source node is used as an initial target set for a next source node such that one or more traceroute processes can be performed to determine a target closure list for the next source node.

2. The method of claim 1, wherein a target closure set is generated for each subsequent source node selected in the network until the target closure set for a current source node is equal to the target closure set for a source node that is next with respect to the current source node.

3. The method of claim 2, wherein when the target closure set for the current source node is equal to the target closure set for a source node that is next with respect to the current source node, the target closure set for the current source node represents an overall closure set for the network.

4. The method of claim 3, wherein the overall closure set is usable to create a topology map of the network.

5. The method of claim 4, further comprising the step of displaying the topology map.

6. The method of claim 4, further comprising the step of updating the topology map as one or more target closure sets are updated.

7. An article of manufacture for discovering a topology of a network comprising a plurality of nodes, the article comprising a computer readable storage medium containing one or more computer programs, which when executed implement the steps of claim 1.

8. An automated method for discovering a topology of a network comprising a plurality of nodes, the method comprising the steps of:

sending an initial target set to a first source node such that the first source node runs a closure algorithm, beginning with the initial target set, which iteratively executes multiple traceroute processes until no new target nodes are discovered resulting in a closure target set for the first source node;

collecting the closure target set from the first source node;

sending the closure target set collected from the first source node to a second source node for use as an initial target set to be used to run the closure algorithm so as to generate a closure target set for the second source node;

collecting the closure target set from the second source node; and

continuing the sending and collecting steps to one or more other source nodes until the closure target set returned for a current source node is the same as the closure target set for a previous source node thus resulting in an overall target closure set.

9. The method of claim 8, further comprising a step of analyzing the overall target closure set.

10. The method of claim 8, further comprising a step of generating a topological representation of the network using the overall target closure set.

11. The method of claim 10, further comprising a step of displaying the topological representation of the network.

12. The method of claim 10, further comprising a step of updating the topological representation of the network when the overall target closure set changes.

13. Apparatus for use in a network node for discovering a topology of a network comprising a plurality of nodes, the apparatus comprising:

a memory; and

a processor coupled to the memory and operative to;

perform a first traceroute process for a given source node and one or more destination nodes listed in a target list so as to discover one or more paths through one or more intermediate nodes between the given source node and the one or more destination nodes;

add the one or more intermediate nodes discovered during the first traceroute process to the target list; and

perform a second traceroute process for the given source node and the one or more intermediate nodes discovered during the first traceroute process so as to discover one or more paths through one or more additional intermediate nodes between the given source node and the one or more intermediate nodes discovered during the first traceroute process;

wherein;

(i) when one or more additional intermediate nodes are discovered as a result of performance of the second traceroute process, adding the one or more additional intermediate nodes to the target list and performing at least one subsequent traceroute process to determine the existence of any further intermediate nodes; and

(ii) when no new intermediate nodes are discovered as a result of performance of the second traceroute process or the at least one subsequent traceroute process, identifying the nodes in the target list as a target closure set for the given source node;

wherein the target closure set for the given source node is used as an initial target set for a next source node such that one or more traceroute processes can be performed to determine a target closure list for the next source node.

14. The apparatus of claim 13, wherein a target closure set is generated for each subsequent source node selected in the network until the target closure set for a current source node is equal to the target closure set for a source node that is next with respect to the current source node.

15. The apparatus of claim 14, wherein when the target closure set for the current source node is equal to the target closure set for the source node that is next with respect to the current source node, the target closure set for the current source node represents an overall closure set for the network.

16. A system for discovering a topology of a network comprising a plurality of nodes, the system comprising:

a memory; and

a controller coupled to the memory and operative to;

send an initial target set to a first source node such that the first source node runs a closure algorithm, beginning with the initial target set, that iteratively executes multiple traceroute processes until no new target nodes are discovered resulting in a closure target set for the first source node;

collect the closure target set from the first source node;

send the closure target set collected from the first source node to a second source node for use as an initial target set to be used to run the closure algorithm so as to generate a closure target set for the second source node;

collect the closure target set from the second source node; and

continue the sending and collecting operations to one or more other source nodes until the closure target set returned for a current source node is the same as the closure target set for the a previous source node thus resulting in an overall target closure set.

17. The system of claim 16, wherein the controller is further operative to analyze the overall target closure set.

18. The system of claim 16, wherein the controller is further operative to generate a topological representation of the network using the overall target closure set.