Network path visualization using node grouping and pagination

• US 10,567,249 B1
• Filed: 03/18/2019
• Issued: 02/18/2020
• Est. Priority Date: 03/18/2019
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: ThousandEyes, Inc. (Cisco Systems, Inc.)
• Inventors: Bauan, John Moeses Ercia, Bandla, Sunil, Oliveira, Ricardo V.
• Primary Examiner(s): Chang, Tom Y
• Application Number:
  US16/356,677
• Time in Patent Office: 337 Days
• CPC Class Codes: G06F 3/0483 Interaction with page-structured environments, e.g. book metaphor
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters

Abstract

A method and system are described. The method and system include determining a grouping characteristic for a plurality of nodes and a corresponding plurality of links. The nodes and the links correspond to components of a network and are associated with network performance information. The grouping characteristic includes at least one of partitionability into pages and a hop distance. The method and system also include generating a graphical visualization based on the grouping characteristic, the nodes and the links.

Claims

1. A method, comprising:

determining a grouping characteristic for a plurality of nodes and a plurality of links, the plurality of nodes and the plurality of links corresponding to components of a network and having associated network performance information, the grouping characteristic includes at least one of partitionability into a plurality of pages and a hop distance; and

generating a graphical visualization based on the grouping characteristic, the plurality of nodes and the plurality of links, for the grouping characteristic including the hop distance, the generating the graphical visualization including

providing a group node in place of a subset of a portion of the plurality of nodes, the subset of the portion of the plurality of nodes having a particular hop distance;

providing a link reference for the group node in place of a portion of the plurality of links between the subset of the portion of the plurality of nodes replaced by the group node; and

providing replacement links to the group node in place of links to the subset of the portion of the plurality of nodes having the particular hop distance from nodes not replaced by the group node; and

for the grouping characteristic including the partitionability into a plurality of pages, the generating the graphical visualization including

determining a number of pivot nodes per page, the number of pivot nodes being static or dynamic, the number of pivot nodes being a maximum number of pivot nodes if the number of pivot nodes is dynamic; and

generating a plurality of pages having the number of pivot nodes per page.

2. The method of claim 1, wherein the grouping characteristic is the partitionability into the plurality of pages and the plurality of nodes includes a plurality of pivot nodes, the generating the plurality of pages further comprising:

sorting the plurality of pivot nodes based on at least one criterion;

dividing the plurality of nodes into a plurality of sections such that each section of the plurality of sections includes not more than the number of pivot nodes, each section including a portion of the plurality of nodes and a portion of the plurality of links, each section corresponding to a page of the plurality of pages;

filtering the page for the portion of the plurality of nodes and the portion of the plurality of links; and

displaying the page including the portion of the plurality of nodes and the portion of the plurality of links for a corresponding section and at least one navigation tool for navigating to at least one other page, a remaining portion of the plurality of nodes and a remaining portion of the plurality of links being omitted from the page.

3. The method of claim 2, wherein the at least one criterion is selected from packet loss, average latency, a pivot node group number.

4. The method of claim 2, further comprising:

receiving a navigation selection of the at least one navigational for an additional page; and

providing the additional page including an additional section of the plurality of sections, the additional page including an additional portion of the plurality of nodes and an additional portion of the plurality of links for an additional corresponding section and at least one additional navigation tool for navigating to at least one additional page.

5. The method of claim 2, wherein the grouping characteristic further includes a group type and wherein the generating the graphical visualization further comprises:

partitioning the plurality of nodes into a plurality of partitions based on the group type, a first partition including a first portion of the plurality of nodes having the group type;

generating at least one node group based on group properties for the first portion of the plurality of nodes, each of the at least one node group including a particular subset of the first portion of the plurality of nodes;

substituting a particular group node for each particular subset of the first portion of the plurality of nodes, a first portion of the plurality of links within the particular subset of the first portion of the plurality of nodes being replaced by at least one link reference; and

merging a second portion of the plurality of links to each particular subset of the first portion of the plurality of nodes such that the second portion of the plurality of links terminate at the group node for each subset.

6. The method of claim 5, wherein the grouping characteristic is selected from hop distance, agent, interface, destination and location.

7. The method of claim 1, wherein the grouping characteristic is the hop distance, wherein the plurality of links and the plurality of nodes correspond to a plurality of paths and wherein the providing the group node further comprises:

partitioning the plurality of nodes into a plurality of partitions based on a group type, a first partition including the portion of the plurality of nodes, the portion of the plurality of nodes having the group type;

generating at least one node group based on group properties for the portion of the plurality of nodes, a node group of the at least one node group including the subset of the portion of the plurality of nodes corresponding to the particular hop distance; and

substituting the group node for the subset of the portion of the plurality of nodes, the providing the link reference further including replacing a first portion of the plurality of links within the subset of the portion of the plurality of nodes with at least one link reference;

the providing the replacement links further including

merging a second portion of the plurality of links to each subset such that the second portion of the plurality of links terminate at the group node for each subset and form the replacement links;

determining a plurality of paths for a remaining portion of the plurality of nodes and each group node;

determining the hop distance from a destination node for each node of the remaining portion of the plurality of nodes and each group node in each of the plurality of paths; and

disambiguating any group node for a subset having a looped path based on the hop distance.

8. The method of claim 7, wherein the disambiguating further includes:

determining whether a first group property for a first node matches a second group property of an adjacent node in each of the plurality of paths;

in response to determining the first group property matches the second group property, placing the first node in a first group with the adjacent node;

in response to determining the first group property does not match the second group property, determining whether a first hop distance for the first node matches a second hop distance for a second node;

in response to determining the first hop distance matches the second hop distance, adding the first node to a second node group; and

in response to determining the first hop distance does not match the second hop distance, creating a new group including the first node.

9. The method of claim 1, wherein the generating the graphical visualization further includes:

replacing a previous graphical visualization including additional with the graphical visualization.

10. A system, comprising:

a processor configured to;

determining a grouping characteristic for a plurality of nodes and a corresponding plurality of links, the plurality of nodes and the plurality of links corresponding to components of a network and having associated network performance information, the grouping characteristic includes at least one of partitionability into a plurality of pages and a hop distance; and

generating a graphical visualization based on the grouping characteristic, the plurality of nodes and the plurality of links, for the grouping characteristic including the hop distance, the generating the graphical visualization including

providing a group node in place of a subset of a portion of the plurality of nodes, the subset of the portion of the plurality of nodes having a particular hop distance;

providing a link reference for the group node in place of a portion of the plurality of links between the subset of the portion of the plurality of nodes replaced by the group node; and

providing replacement links to the group node in place of links to the subset of the portion of the plurality of nodes having the particular hop distance from nodes not replaced by the group node; and

for the grouping characteristic including the partitionability into a plurality of pages, the generating the graphical visualization including

determining a number of pivot nodes per page, the number of pivot nodes being static or dynamic, the number of pivot nodes being a maximum number of pivot nodes if the number of pivot nodes is dynamic; and

generating a plurality of pages having the number of pivot nodes per page; and

a memory coupled to the processor and configured to provide the processor with instructions.

11. The system of claim 10, wherein the grouping characteristic is the partitionability into the plurality of pages and the plurality of nodes includes a plurality of pivot nodes, and wherein the processor is further configured to:

sort the plurality of pivot nodes based on at least one criterion;

divide the plurality of nodes into a plurality of sections such that each section of the plurality of sections includes not more than the number of pivot nodes, each section including a portion of the plurality of nodes and a portion of the plurality of links, each section corresponding to a page of the plurality of pages, wherein the graphical visualization corresponds to the page;

filter the page for the portion of the plurality of nodes and the portion of the plurality of links; and

display the page including the portion of the plurality of nodes and the portion of the plurality of links for a corresponding section and at least one navigation tool for navigating to at least one other page, a remaining portion of the plurality of nodes and a remaining portion of the plurality of links being omitted from the page.

12. The system of claim 11, wherein the at least one criterion is selected from packet loss, average latency, a pivot node group number.

13. The system of claim 11, wherein the processor is further configured to:

receive a navigation selection of the at least one navigational for an additional page; and

provide the additional page including an additional section of the plurality of sections, the additional page including an additional portion of the plurality of nodes and an additional portion of the plurality of links for an additional corresponding section and at least one additional navigation tool for navigating to at least one additional page.

14. The system of claim 11, wherein the grouping characteristic further includes a group type and wherein to generate the graphical visualization, the processor is further configured to:

partition the plurality of nodes into a plurality of partitions based on the group type, a first partition including a first portion of the plurality of nodes having the group type;

generate at least one node group based on group properties for the first portion of the plurality of nodes, each of the at least one node group including a particular subset of the first portion of the plurality of nodes; and

substitute a particular group node for each particular subset of the first portion of the plurality of nodes, a first portion of the plurality of links within the particular subset of the first portion of the plurality of nodes being replaced by at least one link reference;

merge a second portion of the plurality of links to each particular subset of the first portion of the plurality of nodes such that the second portion of the plurality of links terminate at the group node for each subset.

15. The system of claim 14, wherein the grouping characteristic is selected from hop distance, agent, interface, destination and location.

16. The system of claim 10, wherein the grouping characteristic is hop distance, wherein the plurality of links and the plurality of nodes correspond to a plurality of paths and wherein to provide the group node, the processor is further configured to:

partition the plurality of nodes into a plurality of partitions based on a group type, a first partition including the portion of the plurality of nodes, the portion of the plurality of nodes having the group type;

generate at least one node group based on group properties for the portion of the plurality of nodes, a node group of the at least one node group including the subset of the portion of the plurality of nodes corresponding to the particular hop distance; and

substitute the group node for the subset of the portion of the plurality of nodes, to provide the link reference, the processor further being configured to replace a first portion of the plurality of links within the subset of the portion of the plurality of nodes with at least one link reference;

to provide the link reference, the processor further being configured to

merge a second portion of the plurality of links to each subset such that the second portion of the plurality of links terminate at the group node for each subset and form the replacement links;

determine a plurality of paths for a remaining portion of the plurality of nodes and each group node;

determine the hop distance from a destination node for each node of the remaining portion of the plurality of nodes and each group node in each of the plurality of paths; and

disambiguate any group node for a subset having a looped path based on the hop distance.

17. The system of claim 16, wherein to disambiguate, the processor is further configured to:

determine whether a first group property for a first node matches a second group property of an adjacent node in each of the plurality of paths;

in response to a first determination that the first group property matches the second group property, place the first node in a first group with the adjacent node;

in response to a second determination the first group property does not match the second group property, determine whether a first hop distance for the first node matches a second hop distance for a second node;

in response to a third determination that the first hop distance matches the second hop distance, adding the first node to a second node group; and

in response to a fourth determination that the first hop distance does not match the second hop distance, creating a new group including the first node.

18. A computer program product embodied in a non-transitory tangible computer readable storage medium and comprising computer instructions for:

determining a grouping characteristic for a plurality of nodes and a corresponding plurality of links, the plurality of nodes and the plurality of links corresponding to components of a network and having associated network performance information, the grouping characteristic includes at least one of partitionability into a plurality of pages and a hop distance; and

generating a graphical visualization based on the grouping characteristic, the plurality of nodes and the plurality of links, for the grouping characteristic including the hop distance, the generating the graphical visualization including

providing a group node in place of a subset of a portion of the plurality of nodes, the subset of the portion of the plurality of nodes having a particular hop distance;

providing a link reference for the group node in place of a portion of the plurality of links between the subset of the portion of the plurality of nodes replaced by the group node; and

providing replacement links to the group node in place of links to the subset of the portion of the plurality of nodes having the particular hop distance from nodes not replaced by the group node; and

for the grouping characteristic including the partitionability into a plurality of pages, the generating the graphical visualization including

determining a number of pivot nodes per page, the number of pivot nodes being static or dynamic, the number of pivot nodes being a maximum number of pivot nodes if the number of pivot nodes is dynamic; and

generating a plurality of pages having the number of pivot nodes per page.

19. The computer program product of claim 18, wherein the grouping characteristic is the partitionability into the plurality of pages and the plurality of nodes includes a plurality of pivot nodes, instructions for the generating the plurality of pages further comprising instructions for:

sorting the plurality of pivot nodes based on at least one criterion;

dividing the plurality of nodes into a plurality of sections such that each section of the plurality of sections includes not more than the number of pivot nodes, each section including a portion of the plurality of nodes and a portion of the plurality of links, each section corresponding to a page of the plurality of pages, wherein the graphical visualization corresponds to the page;

filtering the page for the portion of the plurality of nodes and the portion of the plurality of links; and

displaying the page including the portion of the plurality of nodes and the portion of the plurality of links for a corresponding section and at least one navigation tool for navigating to at least one other page, a remaining portion of the plurality of nodes and a remaining portion of the plurality of links being omitted from the page.

20. The computer program product of claim 19, wherein the grouping characteristic further includes a group type and wherein the generating the graphical visualization further comprises:

partitioning the plurality of nodes into a plurality of partitions based on the group type, a first partition including a first portion of the plurality of nodes having the group type;

generating at least one node group based on group properties for the first portion of the plurality of nodes, each of the at least one node group including a particular subset of the first portion of the plurality of nodes;

substituting a particular group node for each particular subset of the first portion of the plurality of nodes, a first portion of the plurality of links within the particular subset of the first portion of the plurality of nodes being replaced by at least one link reference; and

merging a second portion of the plurality of links to each particular subset of the first portion of the plurality of nodes such that the second portion of the plurality of links terminate at the group node for each subset.

21. The computer program product of claim 18, wherein the grouping characteristic is the hop distance, wherein the plurality of links and the plurality of nodes correspond to a plurality of paths and wherein the providing the group node further comprises:

partitioning the plurality of nodes into a plurality of partitions based on a group type, a first partition including the portion of the plurality of nodes, the portion of the plurality of nodes having the group type;

generating at least one node group based on group properties for the portion of the plurality of nodes, a node group of the at least one node group including the subset of the portion of the plurality of nodes corresponding to the particular hop distance; and

substituting the group node for the subset of the portion of the plurality of nodes, the providing the link reference further including replacing a first portion of the plurality of links within the subset of the portion of the plurality of nodes with at least one link reference;

the providing the replacement links further including

merging a second portion of the plurality of links to each subset such that the second portion of the plurality of links terminate at the group node for each subset and form the replacement links;

determining a plurality of paths for a remaining portion of the plurality of nodes and each group node;

determining the hop distance from a destination node for each node of the remaining portion of the plurality of nodes and each group node in each of the plurality of paths; and

disambiguating any group node for a subset having a looped path based on the hop distance.

22. The computer program product of claim 21, wherein the disambiguating further includes:

determining whether a first group property for a first node matches a second group property of an adjacent node in each of the plurality of paths;

in response to determining the first group property matches the second group property, placing the first node in a first group with the adjacent node;

in response to determining the first group property does not match the second group property, determining whether a first hop distance for the first node matches a second hop distance for a second node;

in response to determining the first hop distance matches the second hop distance, adding the first node to a second node group; and

in response to determining the first hop distance does not match the second hop distance, creating a new group including the first node.