Systems and methods for constructing multi-layer topological models of computer networks

• US 7,752,024 B2
• Filed: 10/29/2002
• Issued: 07/06/2010
• Est. Priority Date: 05/05/2000
• Status: Active Grant

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: He, Jun, Caron, Jonathan P., Taylor, David K., Buia, Christopher, Ball, Scott, Greenwald, Joseph
• Primary Examiner(s): PROCTOR, JASON SCOTT
• Application Number:
  US10/282,869
• Publication Number:
  US 20030046390A1
• Time in Patent Office: 2,807 Days
• Field of Search: 703/21, 703/22, 703/6, 703/13, 714/1, 714/15, 709/220, 709/225, 709/226, 707/203
• US Class Current: 703/13
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/0631 using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A network management system includes a fault diagnosis engine, a topology mapper, an impact analyzer and a help desk system. The topology mapper includes a discovery module, a memory, and a presentation module. The discovery module is constructed and arranged to discover network elements in a communications network. The memory constructed and arranged to store topology data received from the discovery module. The presentation module constructed and arranged to present data related to topology of the communication network.

Claims

1. A method for constructing a multi-layer topological model of a computer network, comprising:

discovering a plurality of routers in the computer network, wherein discovering the plurality of routers further includes nominating the plurality of routers for placement in a multiple layer topology of the computer network;

discovering a Border Gateway Protocol (BGP) confederation topology in the computer network in response to determining that one or more network protocols discovered in the computer network organize the plurality of routers into a plurality of autonomous systems, wherein discovering the BGP confederation topology includes;

discovering a first subset of the plurality of routers in the plurality of autonomous systems that have external BGP (EBGP) peers, wherein discovering the first subset of the plurality of routers that have the EBGP peers defines one or more adjacencies between the plurality of autonomous systems;

discovering a second subset of the plurality of routers in the plurality of autonomous systems that have internal BGP (IBGP) peers, wherein discovering the second subset of the plurality of routers that have the IBGP peers defines one or more clusters within the plurality of autonomous systems; and

determining the BGP confederation topology in response to discovering the first subset of the plurality of routers and the second subset of the plurality of routers, wherein the BGP confederation topology includes the one or more adjacencies between the plurality of autonomous systems and the one or more clusters within the plurality of autonomous systems;

determining the multiple layer topology of the computer network, wherein the multiple layer topology includes physical dependencies that represent physical connections between the plurality of routers and logical dependencies that represent the one or more adjacencies and the one or more clusters in the BGP confederation topology; and

displaying a model of the multiple layer topology that includes the physical connections between the plurality of routers, the one or more adjacencies between the plurality of autonomous systems, and the one or more clusters within the plurality of autonomous systems, wherein the displayed model of the multiple layer topology represents interdependencies between different layers of the computer network.

2. The method of claim 1, further comprising:

monitoring a representative one of the plurality of routers to determine whether the BGP confederation topology or the multiple layer topology has changed; and

updating the model of the multiple layer topology in response to the representative router indicating that the BGP confederation topology or the multiple layer topology has changed.

3. The method of claim 2, wherein updating the model of the multiple layer topology includes:

determining a compartment where the BGP confederation topology or the multiple layer topology changed, wherein the compartment includes at least one of a hierarchical domain or a hierarchical region of the computer network; and

updating the model of the multiple layer topology within the compartment where the BGP confederation topology or the multiple layer topology changed.

4. The method of claim 1, further comprising:

maintaining multiple versions of the model of the multiple layer topology, wherein each of the multiple versions includes a start date and an end date indicating a period of time during which the respective version existed; and

displaying relationships between two or more of the multiple versions of the model.

5. The method of claim 4, wherein the multiple versions of the model include a current version of the multiple layer topology and at least one of a historical version of the multiple layer topology or an intended version of the multiple layer topology.

6. The method of claim 5, further comprising reconstructing the historical version of the multiple layer topology from the current version of the multiple layer topology using a record of one or more changes to the multiple layer topology of the computer network, wherein the historical version of the multiple layer topology is reconstructed at a particular time using one or more timestamps in the record of the one or more changes to the multiple layer topology.

7. The method of claim 1, wherein the

first subset of the plurality of routers that have the EBGP peers define border nodes within the plurality of autonomous systems, and wherein

the displayed model of the multiple layer topology further includes the border nodes within the plurality of autonomous systems.

8. The method of claim 1, wherein discovering the second subset of the plurality of routers that have the IBGP peers further includes:

discovering at least one of the plurality of routers in the second subset that has three or more IBGP peers; and

defining at least one of the one or more clusters in response to determining that the three or more IBGP peers for the at least one router each have three or more IBGP peers, wherein the at least one cluster includes the at least one router, the three or more IBGP peers for the at least one router, and the three or more IBGP peers for each of the three or more IBGP peers of the at least one router.

9. The method of claim 1, further comprising:

discovering a third subset of the plurality of routers that use a Routing Information Protocol to route data packets within the BGP confederation, wherein discovering the third subset of the plurality of routers defines one or more neighbors and one or more interfaces in one or more routing domains within the BGP confederation; and

displaying the one or more routing domains, the one or more neighbors, and the one or more interfaces within the displayed model of the multiple layer topology.

10. The method of claim 9, further comprising:

discovering a fourth subset of the plurality of routers that use an Open Shortest Path First Protocol to transport the data packets within the BGP confederation, wherein discovering the fourth subset of the plurality of routers defines one or more data paths between one or more sub-domains within the one or more routing domains; and

displaying the one or more sub-domains and the one or more data paths within the displayed model of the multiple layer topology.

11. The method of claim 10, further comprising:

discovering one or more subnets within the one or more sub-domains, wherein discovering the one or more subnets defines one or more addressing spaces for the fourth subset of the routers; and

displaying the one or more subnets and one or more addressing spaces within the displayed model of the multiple layer topology.

12. The method of claim 11, further comprising:

discovering a fifth subset of the plurality of routers that run a Spanning Tree Protocol within the BGP confederation, wherein discovering the fifth subset of the plurality of routers defines one or more spanning tree topologies within the one or more subnets that include one or more spanning tree regions and one or more spanning tree links; and

displaying the one or more spanning tree topologies, the one or more spanning tree regions, and the one or more spanning tree links within the displayed model of the multiple layer topology.

13. The method of claim 11, further comprising:

discovering a fifth subset of the plurality of routers that run a Transparent Bridging Protocol within the BGP confederation, wherein discovering the fifth subset of the plurality of routers defines one or more transparent bridging topologies within the one or more subnets that include a plurality of physically connected ports in one or more bridged local area networks; and

displaying the one or more transparent bridging topologies and the ports physically connected in the one or more bridged local area networks within the displayed model of the multiple layer topology.

14. The method of claim 1, wherein discovering the second subset of the plurality of routers that have the IBGP peers further includes:

discovering at least one of the plurality of routers in the second subset that has an IBGP peer within at least one of the one or more clusters; and

adding the at least one router to the at least one cluster that includes the IBGP peer for the at least one router.

15. The method of claim 1, wherein discovering the second subset of the plurality of routers that have the IBGP peers further includes:

discovering at least one of the plurality of routers in the second subset that has two IBGP peers that further have three or more IBGP peers;

adding the at least one router to at least one of the one or more clusters in response to determining that the at least one cluster includes the two IBGP peers for the at least one router; and

creating the at least one cluster in response to determining that none of the one or more clusters includes the two IBGP peers for the at least one router, wherein the created cluster includes the at least one router, the two IBGP peers for the at least one router, and the three or more IBGP peers for each of the two IBGP peers of the at least one router.

16. A device readable storage medium having computer executable instructions recorded thereon, wherein executing the instructions on a computer causes the computer to perform a method for constructing a multi-layer topological model of a computer network, the method comprising:

discovering a plurality of routers in the computer network, wherein discovering the plurality of routers further includes nominating the plurality of routers for placement in a multiple layer topology of the computer network;

discovering a Border Gateway Protocol (BGP) confederation topology in the computer network in response to determining that one or more network protocols discovered in the computer network organize the plurality of routers into a plurality of autonomous systems, wherein discovering the BGP confederation topology includes;

discovering a first subset of the plurality of routers in the plurality of autonomous systems that have external BGP (EBGP) peers, wherein discovering the first subset of the plurality of routers that have the EBGP peers defines one or more adjacencies between the plurality of autonomous systems;

discovering a second subset of the plurality of routers in the plurality of autonomous systems that have internal BGP (IBGP) peers, wherein discovering the second subset of the plurality of routers that have the IBGP peers defines one or more clusters within the plurality of autonomous systems; and

determining the BGP confederation topology in response to discovering the first subset of the plurality of routers and the second subset of the plurality of routers, wherein the BGP confederation topology includes the one or more adjacencies between the plurality of autonomous systems and the one or more clusters within the plurality of autonomous systems;

determining the multiple layer topology of the computer network, wherein the multiple layer topology includes physical dependencies that represent physical connections between the plurality of routers and logical dependencies that represent the one or more adjacencies and the one or more clusters in the BGP confederation topology; and

displaying a model of the multiple layer topology that includes the physical connections between the plurality of routers, the one or more adjacencies between the plurality of autonomous systems, and the one or more clusters within the plurality of autonomous systems, wherein the displayed model of the multiple layer topology represents interdependencies between different layers of the computer network.

17. The device readable storage medium of claim 16, wherein the method further comprises:

monitoring a representative one of the plurality of routers to determine whether the BGP confederation topology or the multiple layer topology has changed; and

updating the model of the multiple layer topology in response to the representative router indicating that the BGP confederation topology or the multiple layer topology has changed.

18. The device readable storage medium of claim 16, wherein the method further comprises:

maintaining multiple versions of the model of the multiple layer topology, wherein each of the multiple versions includes a start date and an end date indicating a period of time during which the respective version existed; and

displaying relationships between two or more of the multiple versions of the model.

19. The device readable storage medium of claim 18, wherein the multiple versions of the model include a current version of the multiple layer topology and at least one of a historical version of the multiple layer topology or an intended version of the multiple layer topology.

20. The device readable storage medium of claim 19, wherein the method further comprises reconstructing the historical version of the multiple layer topology from the current version of the multiple layer topology using a record of one or more changes to the multiple layer topology of the computer network, wherein the historical version of the multiple layer topology is reconstructed at a particular time using one or more timestamps in the record of the one or more changes to the multiple layer topology.

21. A network management system for constructing a multi-layer topological model of a computer network, the system comprising:

a computer network that includes a plurality of routers;

a topology mapper configured to;

discover the plurality of routers in the computer network, wherein the topology mapper is further configured to nominate the plurality of routers for placement in a multiple layer topology of the computer network;

discover a Border Gateway Protocol (BGP) confederation topology in the computer network in response to determining that one or more network protocols discovered in the computer network organize the plurality of routers into a plurality of autonomous systems, wherein to discover the BGP confederation topology, the topology mapper is further configured to;

discover a first subset of the plurality of routers in the plurality of autonomous systems that have external BGP (EBGP) peers, wherein discovering the first subset of the plurality of routers that have the EBGP peers defines one or more adjacencies between the plurality of autonomous systems;

discover a second subset of the plurality of routers in the plurality of autonomous systems that have internal BGP (IBGP) peers, wherein discovering the second subset of the plurality of routers that have the IBGP peers defines one or more clusters within the plurality of autonomous systems;

determine the BGP confederation topology in response to discovering the first subset of the plurality of routers and the second subset of the plurality of routers, wherein the BGP confederation topology includes the one or more adjacencies between the plurality of autonomous systems and the one or more clusters within the plurality of autonomous systems; and

determine the multiple layer topology of the computer network, wherein the multiple layer topology includes physical dependencies that represent physical connections between the plurality of routers and logical dependencies that represent the one or more adjacencies and the one or more clusters in the BGP confederation topology; and

a presentation module that receives the multiple layer topology of the computer network from the topology mapper, wherein the presentation module is configured to;

display a model of the multiple layer topology that includes the physical connections between the plurality of routers, the one or more adjacencies between the plurality of autonomous systems, and the one or more clusters within the plurality of autonomous systems, wherein the displayed model of the multiple layer topology represents interdependencies between different layers of the computer network.

22. The system of claim 21, further comprising a network topology server configured to:

monitor a representative one of the plurality of routers to determine whether the BGP confederation topology or the multiple layer topology has changed; and

update the model of the multiple layer topology in response to the representative router indicating that the BGP confederation topology or the multiple layer topology has changed.

23. The system of claim 21, wherein the topology mapper is further configured to maintain multiple versions of the model of the multiple layer topology, wherein each of the multiple versions includes a start date and an end date indicating a period of time during which the respective version existed, and wherein the presentation module is further configured to display relationships between two or more of the multiple versions of the model.