System and method for determining probable network paths between nodes in a network topology

• US 7,003,559 B1
• Filed: 10/23/2000
• Issued: 02/21/2006
• Est. Priority Date: 10/23/2000
• Status: Expired due to Term

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Smith, Darren D., Nataraian, Srikanth
• Primary Examiner(s): Thompson, Marc D.
• Assistant Examiner(s): REILLY, SEAN M
• Application Number:
  US09/694,843
• Time in Patent Office: 1,947 Days
• Field of Search: 709/223, 709/224, 709/238, 703/21, 370/357
• US Class Current: 709/223
• 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
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]

Abstract

A preferred system includes a processor, a discovery mechanism and a layout mechanism. The discovery mechanism is configured to generate and store topology data specifying connectors and segments of a communication network. The layout mechanism, which interfaces with the discovery mechanism, is configured to receive topology data from the discovery mechanism and drive a display based upon the topology data. Additionally, the discovery mechanism is configured to determine a path between a start node and an end node based upon the topology data. For instance, such a path(s) may be based upon information corresponding to a type of path of interest and/or information corresponding to a type of connector of interest. Methods and computer readable media also are provided.

Claims

1. A method for determining paths between a start node and an end node of a communication network, the communication network being formed of sub-networks, the sub-networks having connectors and segments, the segments interconnecting various ones of the connectors, the start node corresponding to one of the connectors and the end node corresponding to another of the connectors, said method comprising:

storing, in a topology database, information corresponding to connectors and segments of the communication network;

receiving, from an operator, information corresponding to the start node and the end node;

receiving, from the operator, information corresponding to a type of connector of interest; and

in response to the information received, automatically determining a shortest path between the start node and the end node based upon the type of connector of interest by using only the information stored in the topology database;

wherein, in determining a shortest path between the start node and the end node, a path with a lowest hop count between the start node and the end node is designated as the shortest path;

wherein each of the sub-networks has at least one level 2 connector, each of the sub-networks being configured to intercommunicate with another of the sub-networks via a level 3 connector;

wherein receiving information corresponding to a type of connector of interest comprises receiving information corresponding to at least one of;

level 2 and level 3 connectors, and level 3 connectors; and

wherein, when the type of connectors of interest are level 3 connectors, determining a path between the start node and the end node comprises;

identifying sub-networks associated with the start node; and

determining whether the end node is associated with at least one of the identified sub-networks.

2. The method of claim 1, further comprising:

if the end node is not associated with at least one of the identified sub-networks, recursively identifying sub-networks associated with the each of the previously identified sub-networks; and

determining whether the end node is associated with at least one of the sub-networks associated with the each of the previously identified sub-networks.

3. The method of claim 1, wherein determining a path between the start node and the end node comprises:

storing a shortest path between the start node and the end node in memory as a current shortest path; and

recursively determining paths between the start node and the end node based upon the type of connector of interest such that, when a newly determined path between the start node and the end node is shorter than the current shortest path, the current shortest path is replaced with the newly determined path.

4. A computer readable medium having a computer program for determining paths between a start node and an end node of a communication network, the communication network being formed of sub-networks, the sub-networks having connectors and segments, the segments interconnecting various ones of the connectors, the start node corresponding to one of the connectors and the end node corresponding to another of the connectors, said computer readable medium comprising:

logic configured to store information corresponding to a topology of the communication network;

logic configured to receive, from an operator, information corresponding to the start node and the end node;

logic configured to receive, from the operator, information corresponding to a type of connector of interest; and

logic configured to determine, automatically and in response to the information received, a shortest probable path between the start node and the end node based upon the type of connector of interest by using only the information corresponding to the topology of the communication network;

wherein, in determining a shortest path between the start node and the end node, a path with a lowest hop count between the start node and the end node is designated as the shortest path;

wherein each of the sub-networks has at least one level 2 connector, each of the sub-networks being configured to intercommunicate with another of the sub-networks via a level 3 connector;

wherein the information corresponding to a type of connector of interest comprises at least one of;

level 2 and level 3 connectors, and level 3 connectors; and

wherein, when the type of connectors of interest are level 3 connectors, the logic configured to determine a path between the start node and the end node is operative to;

identify sub-networks associated with the start node; and

determine whether the end node is associated with at least one of the identified sub-networks.

5. The computer readable medium of claim 4, wherein the logic configured to determine a shortest probable path between the start node and the end node comprises:

logic configured to identify segments associated with the start node; and

logic configured to determine whether the end node is associated with at least one of the identified segments.

6. A method for determining paths between a start node and an end node of a communication network, the communication network being formed of sub-networks, the sub-networks having connectors and segments, the segments interconnecting various ones of the connectors, the start node corresponding to one of the connectors and the end node corresponding to another of the connectors, said method comprising:

storing, in a topology database, information corresponding to connectors and segments of the communication network;

receiving, from an operator, information corresponding to the start node and the end node;

receiving, from the operator, information corresponding to a type of connector of interest; and

in response to the information received, automatically determining a shortest path between the start node and the end node based upon the type of connector of interest by using only the information stored in the topology database;

wherein, in determining a shortest path between the start node and the end node, a path with a lowest hop count between the start node and the end node is designated as the shortest path;

wherein each of the sub-networks has at least one level 2 connector, each of the sub-networks being configured to intercommunicate with another of the sub-networks via a level 3 connector, and wherein receiving information corresponding to a type of connector of interest comprises receiving information corresponding to at least one of;

level 2 and level 3 connectors, and level 3 connectors; and

wherein, when the type of connectors of interest are level 2 and level 3 connectors, determining a path between the start node and the end node comprises;

identifying segments associated with the start node; and

determining whether the end node is associated with at least one of the identified segments.

7. The method of claim 6, further comprising:

if the end node is not associated with at least one of the identified segments, recursively identifying segments associated with the each of the previously identified segments; and

determining whether the end node is associated with at least one of the segments associated with the each of the previously identified segments.

8. The method of claim 6, wherein determining a path between the start node and the end node comprises:

storing a shortest path between the start node and the end node in memory as a current shortest path; and

recursively determining paths between the start node and the end node based upon the type of connector of interest such that, when a newly determined path between the start node and the end node is shorter than the current shortest path, the current shortest path is replaced with the newly determined path.