Mechanism for determining actual physical topology of network based on gathered configuration information representing true neighboring devices

• US 6,377,987 B1
• Filed: 04/30/1999
• Issued: 04/23/2002
• Est. Priority Date: 04/30/1999
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kracht, James E.
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US09/302,531
• Time in Patent Office: 1,089 Days
• Field of Search: 709/220, 709/224, 709/228, 370/254, 370/401
• US Class Current: 709/220
• 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 mechanism for determining the actual physical topology of network devices in a network is disclosed. To determine a physical topology, a discovery mechanism determines a set of network addresses for identifying devices within a network. Based on the set of network addresses, the discovery mechanism identifies a group of devices that are associated with the network. Layer 2 and Layer 3 configuration information is gathered from the group of devices to identify possible neighboring devices within the network. The configuration information is then processed to generate topology information that identifies true neighboring devices and the actual links that exist between each of the neighboring devices. The mechanism eliminates misleading information and prevents generation of incorrect topologies.

Claims

1. A method for determining a physical topology of a network, the method comprising the computer-implemented steps of:

discovering a plurality of devices that are located in the network based on each address within a set of network addresses and creating and storing information representing the plurality of devices;

determining possible neighboring devices for each device in the plurality of devices;

processing the configuration information to eliminate, from among the possible neighboring devices, each device that is not actually a neighbor of the plurality of devices to create information representing true neighboring devices and each link between them; and

creating and storing information that represents the topology based on the information representing the plurality of devices and the information representing the true neighboring devices and each link.

2. A method as recited in claim 1, further comprising the step of eliminating, from among the information representing the plurality of devices, information associated with each device that is incorrectly identified as a known device.

3. A method as recited in claim 1, further comprising the step of receiving Layer 2 and Layer 3 configuration information from each device in the plurality of devices.

4. A method as recited in claim 1, wherein the step of determining possible neighboring devices includes the step of sending information requests to collect Layer 2 and Layer 3 configuration information from the plurality of devices.

5. A method as recited in claim 4, wherein the configuration information identifies what network addresses are received on what ports of each device among the plurality of devices.

6. A method as recited in claim 1, further comprising the step of receiving one or more ranges of network addresses.

7. A method as recited in claim 6, wherein the step of receiving one or more ranges of network addresses comprises the step of receiving one or more ranges of IP addresses, wherein the one or more ranges of IP addresses are associated with IP addresses that correspond to one or more local area networks.

8. A method as recited in claim 1, wherein the step of discovering comprises the steps of attempting to contact a device at each address within the set of network addresses.

9. A method as recited in claim 8, wherein the step of attempting to contact a device comprises the steps of pinging each address within the set of network addresses.

10. A method as recited in claim 1, wherein the step of discovering comprises the steps of:

dividing the set of network addresses into a plurality of network address subgroups;

assigning separate processes to each of the plurality of network address subgroups; and

executing each of the assigned processes in parallel to determine whether a device is associated with each address within a network address subgroup.

11. A method as recited in claim 8, further comprising the steps of:

in response to contacting a particular device at a particular address, contacting a Simple Network Management Protocol (SNMP) agent in the particular device to receive a device type value is associated with the particular device.

12. A method as recited in claim 11, wherein the step of contacting an SNMP agent comprises the steps of:

requesting identification information from the SNMP agent in the device;

comparing the identification information to a list of known device data; and

based on the comparison, determining whether the device is of a known device type.

13. A method as recited in claim 12, further comprising the steps of:

determining service layers for which the device operates when the device is not of a known device type; and

based on the service layers that are determined, inferring that the device is of a particular device type associated with the service layers.

14. A method as recited in claim 4, wherein the step of sending information requests to collect configuration information includes the steps of identifying devices within the plurality of devices that support Cisco Discovery Protocol (CDP) and retrieving CDP information from devices with the plurality of devices that support CDP.

15. A method as recited in claim 14, wherein the step of determining possible neighboring devices includes the step of determining possible neighboring devices based on the CDP information.

16. A method as recited in claim 4, wherein the step of sending information requests comprises the steps of obtaining Media Access Control (MAC) address information from devices within the plurality of devices, and identifying, based on the MAC address information, what MAC addresses are seen on what ports of the devices within the plurality of devices.

17. A method as recited in claim 16, wherein the step of obtaining MAC address information comprises the step of retrieving bridging table information from switch devices among the plurality of devices, wherein the bridging table information identifies which MAC addresses are seen on each interface of each of the switch devices.

18. A method as recited in claim 16, wherein the step of obtaining MAC address information comprises the step of retrieving repeater address tracking information from hub devices among the plurality of devices, wherein the repeater address tracking information identifies which MAC addresses are seen on each port of the hub devices.

19. A method as recited in claim 16, wherein the step of obtaining MAC address information comprises the step of retrieving address translation information from router devices among the plurality of devices, wherein the address translation information identifies which MAC addresses are seen on each interface of the router devices.

20. A method as recited in claim 16, further comprising the step of refreshing the MAC address information that is maintained by the plurality of devices by repeatedly attempting to contact devices at each of the addresses within the set of network addresses.

21. A method as recited in claim 16, further comprising the step of refreshing the MAC address information that is maintained by the plurality of devices by repeatedly attempting to contact each device in said plurality of devices.

22. A method as recited in claim 1, wherein the step of processing the configuration information comprises the steps of:

identifying devices within the plurality of devices that are not an actual device associated with the set of network addresses; and

bypassing the configuration information that is based on devices within the plurality of devices that are not actual devices associated with the set of network addresses.

23. A method as recited in claim 22, wherein the step of identifying devices within the plurality of devices that are not an actual device comprises the step of identifying any device within the plurality of devices that is associated with a broadcast address of the network.

24. A method as recited in claim 22, wherein the step of identifying devices within the plurality of devices that are not an actual device comprises the step of identifying multiple devices within the plurality of devices that are associated with a common IP address, wherein the common IP address indicates that the multiple devices are actually the same device.

25. A method as recited in claim 1, wherein the step of processing the configuration information includes the step of using Media Access Control (MAC) address information to eliminate the possible neighboring devices that are not actually neighbors of the plurality of devices.

26. A method as recited in claim 1, wherein the step of processing the configuration information further comprises the steps of:

identifying three or more potentially neighboring devices that have a single port that appears to be physically linked to multiple neighboring devices; and

using the configuration information to determine that the single port is actually physically linked to one or more unidentifiable devices that are in the network but are not among the plurality of devices.

27. A method as recited in claim 1, wherein the step of processing the configuration information further comprises the steps of:

identifying an apparent physical link between a first port of a first potentially neighboring device and a second port of a second potentially neighboring device, wherein the Media Access Control (MAC) address associated with the first port is observed at the second port and the MAC address associated with the second port is observed at the first port;

determining that a common MAC address is observed by both the first port and the second port; and

based on the common MAC address, determining that the first port and the second port of the first potentially neighboring device and the second potentially neighboring device are actually physically linked to one or more unidentifiable devices that are part of the network but are not included among the plurality of devices.

28. A method as recited in claim 1, wherein the step of processing the configuration information further comprises the steps of:

identifying a device within the plurality of devices that includes a port that observes more than one MAC address but has no neighboring device; and

in response to identifying the device, determining that the port is physically linked to one or more unidentifiable devices that are part of the network but not included among the plurality of devices.

29. A method as recited in claim 4, wherein the step of sending information requests to collect layer 2 and layer 3 configuration information includes the step of retrieving routing table information from devices within the plurality of devices that are of type router, wherein the routing table information identifies a port associated with default routing address for each router type device.

30. A method as recited in claim 29, further comprising the step of detecting an Internet link to said network by identifying the router type device whose default routing address is outside the set of network address.

31. A computer-readable medium carrying one or more sequences of instructions determining a physical topology of a network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

discovering a plurality of devices that are located in the network based on each address within a set of network addresses and creating and storing information representing the plurality of devices;

determining possible neighboring devices for each device in the plurality of devices;

processing the configuration information to eliminate, from among the possible neighboring devices, each device that is not actually a neighbor of the plurality of devices to create information representing true neighboring devices and each link between them; and

creating and storing information that represents the topology based on the information representing the plurality of devices and the information representing the true neighboring devices and each link.

32. A computer data signal embodied in a carrier wave, the computer data signal carrying one or more sequences of instructions for determining a physical topology of a network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

discovering a plurality of devices that are located in the network based on each address within a set of network addresses and creating and storing information representing the plurality of devices;

determining possible neighboring devices for each device in the plurality of devices;

processing the configuration information to eliminate, from among the possible neighboring devices, each device that is not actually a neighbor of the plurality of devices to create information representing true neighboring devices and each link between them; and

creating and storing information that represents the topology based on the information representing the plurality of devices and the information representing the true neighboring devices and each link.

33. A computer apparatus comprising:

a processor; and

a memory coupled to the processor, the memory containing one or more sequences of instructions for determining a physical topology of a network, wherein execution of the one or more sequences of instructions by the processor causes the processor to perform the steps of;

discovering a plurality of devices that are located in the network based on each address within a set of network addresses and creating and storing information representing the plurality of devices;

determining possible neighboring devices for each device in the plurality of devices;

processing the configuration information to eliminate, from among the possible neighboring devices, each device that is not actually a neighbor of the plurality of devices to create information representing true neighboring devices and each link between them; and

creating and storing information that represents the topology based on the information representing the plurality of devices and the information representing the true neighboring devices and each link.