METHOD AND APPARATUS FOR NETWORK TOPOLOGY DISCOVERY USING CLOSURE APPROACH
First Claim
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 repeating the 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 a subsequent traceroute process, identifying the nodes in the target list as a target closure set for the given source node.
5 Assignments
0 Petitions
Accused Products
Abstract
Improved network topology discovery techniques are disclosed. 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. When one or more additional intermediate nodes are discovered as a result of performance of the second traceroute process, the one or more additional intermediate nodes are added to the target list and the traceroute process is repeated to determine the existence of any further intermediate nodes. When no new intermediate nodes are discovered as a result of performance of the second traceroute process or a subsequent traceroute process, the nodes in the target list are identified as a target closure set for the given source node.
-
Citations
20 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 repeating the 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 a subsequent traceroute process, identifying the nodes in the target list as a target closure set for the given source node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. 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 the current source node is the same as the closure target set for the previous source node thus resulting in an overall target closure set. - View Dependent Claims (10, 11, 12, 13)
-
-
14. 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 repeating the 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 a subsequent traceroute process, identifying the nodes in the target list as a target closure set for the given source node. - View Dependent Claims (15, 16, 17)
-
-
18. 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 the current source node is the same as the closure target set for the previous source node thus resulting in an overall target closure set. - View Dependent Claims (19, 20)
-
Specification