Node merging process for network topology representation
View Patent ↗Node merging methods and apparatus are disclosed for generating simplified representations of network topology. A first topology representative of a given network is determined, and at least one pair of nodes of the first topology is merged into a single node based on measures associated with respective edges connecting the nodes of the node pair to at least one neighbor node common to that pair. The merging step is repeated for one or more additional pairs of nodes to produce a reduced network topology meeting one or more desired criteria, and a visualization or other representation of the reduced network topology is generated.
1. A method comprising:
transmitting, from a first network element to a second network element, one or more packets to obtain a first network topology;
identifying, at the first network element, a pair of nodes from the first network topology;
merging, at the first network element, the pair of nodes identified from the first network topology, wherein merging the pair of nodes is based, at least in part, on:
i. determining that an intermediary node connects a first node to a second node of the pair of nodes,
ii. determining that a first value of a first edge satisfies a threshold, wherein the first edge connects the first node to the intermediary node, and
iii. determining that a second value of a second edge satisfies the threshold, wherein the second edge connects the second node to the intermediary node;
wherein if:
i. the first value is greater than the second value, assigning the first value to a third edge that connects the intermediary node to the merged pair of nodes, and
ii. the first value is less than the second value, assigning the second value to the third edge that connects the intermediary node to the merged pair of nodes; and
generating, at the first network element, a representation of a second network topology based, at least in part, on merging the pair of nodes from the first topology.
2. The method of claim 1 , wherein generating the representation of the second network topology comprises generating a graphical representation of the second network topology, and, displaying the graphical representation of the second network topology on a display.
3. The method of claim 1 further comprising analyzing the second network topology, and, transmitting an indicator to a network administrator when a location of a performance problem is detected in the second network topology.
4. The method of claim 1 , wherein the one or more packets are transmitted based, at least in part, on executing a route tracing program at one or more network elements.
5. The method of claim 1 further comprising, merging the first node and the second node if the first node and the second node do not share at least one intermediary node.
6. The method of claim 1 , wherein the first value and the second value satisfies the threshold when:
i. the first value is less than the threshold, and
ii. the second value is less than the threshold.
7. The method of claim 1 , wherein the first node and the second node are not merged together when:
i. the first value is greater than or equal to the threshold, and
ii. the second value is greater than or equal to the threshold.
8. The method of claim 1 , wherein the threshold comprises a wide area network threshold, and, wherein the second network topology only represents a portion of the network that is associated with a wide area network.
9. The method of claim 1 , wherein merging the first node and the second node to obtain the second network topology comprises removing the first edge and the second edge to form the third edge.
10. The method of claim 1 , wherein the first value and the second value comprises at least one of a delay measurement, a loss measurement, and a jitter measurement.
11. The method of claim 1 further comprising analyzing the second network topology, and, altering operations of the network based, at least in part, on locating a performance problem in the second network topology.
12. The method of claim 1 , wherein the second network topology comprises less nodes and less edges than the first network topology.
13. A computer-readable storage medium containing software code for implementing the steps of the method of claim 1 .
14. An apparatus comprising:
a processing element comprising a processor and a memory, the memory being coupled to the processor;
wherein the processing element under control of the processor is operative to:
transmit one or more packets in a network to obtain a first network topology;
identify a pair of nodes in the first network topology, wherein the pair of nodes comprises a first node and a second node;
merge the pair of nodes to obtain a second network topology based, at least in part, on:
i. determining that an intermediary node connects the first node to the second node,
ii. determining that a first value of a first edge connecting the first node to the intermediary node satisfies a threshold, and
iii. determining that a second value of a second edge connecting the second node to the intermediary node satisfies the threshold;
wherein if:
i. the first value is greater than the second value, assigning the first value to a third edge that connects the intermediary node to the merged pair of nodes, and
ii. the first value is less than the second value, assigning the second value to the third edge that connects the intermediary node to the merged pair of nodes; and
generate a representation of the second network topology.
15. The apparatus of claim 14 , wherein the apparatus is implemented at least in part within a network analysis device coupled to a first network element.
16. The apparatus of claim 14 , wherein the apparatus is implemented at least in part within a first network element.
17. The apparatus of claim 16 , wherein the first network element comprises at least one of a router and a switch.
18. A network comprising:
a plurality of interconnected network elements; and
a processing element associated with at least one of the network elements;
wherein the processing element is operative to:
transmit one or more packets in a network to obtain a first network topology;
identify a pair of nodes in the first network topology, wherein the pair of nodes comprises a first node and a second node;
merge the pair of nodes to obtain a second network topology based, at least in part, on:
i. determining that an intermediary node connects the first node to the second node,
ii. determining that a first value of a first edge connecting the first node to the intermediary node satisfies a threshold, and
iii. determining that a second value of a second edge connecting the second node to the intermediary node satisfies the threshold;
wherein if:
i. the first value is greater than the second value, assigning the first value to a third edge that connects the intermediary node to the merged pair of nodes, and
ii. the first value is less than the second value, assigning the second value to the third edge that connects the intermediary node to the merged pair of nodes; and
generate a representation of the second network topology.
19. The network of claim 18 , wherein the processing element is implemented at least in part in a network analysis device coupled to one of the network elements.