Method and apparatus for determining and resolving missing topology features of a network for improved topology accuracy

• US 7,076,564 B2
• Filed: 09/17/2001
• Issued: 07/11/2006
• Est. Priority Date: 09/17/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: Micromuse Ltd (International Business Machines Corporation)
• Inventors: To, Hing Wing, Appleton, Christopher
• Primary Examiner(s): DINH, KHANH Q
• Application Number:
  US09/955,472
• Publication Number:
  US 20040193705A1
• Time in Patent Office: 1,758 Days
• Field of Search: 709/238, 709/242, 709/224, 709/227, 709/225, 709/248, 709/251, 370/422, 370/254, 370/392, 370/389, 714/707
• US Class Current: 709/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/586 of virtual routers

Abstract

The present invention describes a method and apparatus for resolving anomalies within a network topology map that typically occur when a derived topology map fails, for a variety of reasons, to include devices resident on the network. The method of the present invention discovers missing devices by identifying a conflicting link within a received topology map, the conflicting link comprising a source and one or more conflicting destinations. The conflicting link is resolved through the use of one or more virtual devices within the topology map. The conflicting link is replaced with a link to a virtual device based upon the resolution of the conflicting link, thereby eliminating the anomaly in the topology map. The step of resolving the conflicting link may also comprise the steps of determining a number of conflicting destinations from the source of the conflicting link, resolving the source of the conflicting link, and resolving the conflicting destination. In order to reduce the number of virtual devices inserted to the topology, the method may further include identifying a link between two virtual devices and merging the virtual devices.

Claims

1. A method for resolving anomalies within a network topology map, the method comprising:

identifying an anomaly including a conflicting link within a received topology map, the conflicting link comprising a source port on a network device and one or more conflicting destination ports on one or more other network devices;

resolving the conflicting link by inserting one or more virtual devices within the topology map, the one or more virtual devices being representative of one or more of the network devices not identified in the received topology map as linked to the source or destination ports wherein resolving the conflicting link comprises first determining whether the source or a destination in the conflicting link is linked to a first virtual device;

replacing the conflicting link with a resolved link to the one or more virtual devices based upon the resolution of the conflicting link wherein replacing the conflicting link with a link to a virtual device only if neither the source nor a destination is linked to the first virtual device; and

wherein if a destination in the conflicting link is linked to a first virtual device, creating a link from the source to the first virtual device if the source in the conflicting link is not a virtual device.

2. The method of claim 1, wherein resolving the conflicting link comprises:

determining a number of conflicting destinations from the source of the conflicting link;

resolving the source of the conflicting link;

resolving the conflicting destination.

3. The method of claim 1, comprising identifying a link between two virtual devices;

and merging the virtual devices.

4. The method of claim 1, wherein identifying the conflicting link comprises locating two or more entries in a link table showing the source to be linked to two or more different destinations.

5. The method of claim 4, comprising grouping together entries in the link table having the source into a conflict group.

6. The method of claim 4, wherein replacing the conflicting link with a link to the virtual device comprises removing the conflicting link from the link table and inserting the link to the virtual device in a virtual link table.

7. The method of claim 6, comprising generating a virtual link table for storing one or more links to virtual devices.

8. The method of claim 1 wherein determining whether the source or destination is linked to a virtual device comprising first determining whether the source is linked to a virtual device then determining whether a destination in the conflicting link is linked to a virtual device.

9. The method of claim 1, comprising, if the source is linked to a first virtual device, replacing the source with the first virtual device.

10. A computer readable medium storing a data structure representing a virtual link table, the data structure comprising:

one or more entries showing a link between a source device in a network and a first virtual device, the source device being identified in a received topology map of a network and the first virtual device not being identified in the received topology map;

one or more entries showing a link between a destination device in the network and the first virtual device, the destination device being identified in the received topology map;

the virtual link table data structure being used by an executable program to display an improved topology map of the network;

wherein the first virtual device is representative of one or more network devices not identified in the received topology map as linked to the source or destination ports;

wherein resolving the conflicting link comprises first determining whether the source or a destination in the conflicting link is linked to a first virtual device and replacing the conflicting link with a link to a virtual device only if neither the source nor a destination is linked to the first virtual device; and

wherein if a destination in the conflicting link is linked to a first virtual device, creating a link from the source to the first virtual device if the source in the conflicting link is not a virtual device.

11. A system, comprising:

a processor;

at least one arrangement configured to communicate with the processor via a computer network;

a computer-readable storing medium storing a set oî

instructions, the set of instructions capable of being executed by the processor to implement a method for resolving anomalies within a network topology map, the set of instructions effective to perform the steps of;

identifying an anomaly including a conflicting link within a received topology map, the conflicting link comprising a source port on a network device and one or more conflicting destination ports on one or more other network devices;

resolving the conflicting link by inserting one or more virtual devices within the topology map, the one or more virtual devices being representative of one or more of the network devices not identified in the received topology map as linked to the source or destination ports wherein resolving the conflicting link comprises first determining whether the source or a destination in the conflicting link is linked to a first virtual device;

replacing the conflicting link with a resolved link to the one or more virtual devices based upon the resolution of the conflicting link wherein replacing the conflicting link with a link to a virtual device only if neither the source nor a destination is linked to the first virtual device; and

wherein if a destination in the conflicting link is linked to a first virtual device, creating a link from the source to the first virtual device if the source in the conflicting link is not a virtual device.

12. An apparatus for resolving anomalies within a network topology map, the apparatus comprising:

a first arrangement effective to identify an anomaly including a conflicting link within a received topology map, the conflicting link comprising a source port on a network device and one or more conflicting destination ports on one or more other network devices;

a second arrangement effective to resolve the conflicting link by inserting one or more virtual devices within the topology map, the one or more virtual devices being representative of one or more network devices not identified in the received topology map as linked to the source or destination ports wherein resolving the conflicting link comprises first determining whether the source or a destination in the conflicting link is linked to a first virtual device; and

a third arrangement effective to replace the conflicting link with a resolved link to the one or more virtual devices based upon the resolution of the conflicting link wherein replacing the conflicting link with a link to a virtual device only if neither the source nor a destination is linked to the first virtual device; and

wherein if a destination in the conflicting link is linked to a first virtual device, creating a link from the source to the first virtual device if the source in the conflicting link is not a virtual device.