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

• US 6,516,345 B1
• Filed: 12/21/2001
• Issued: 02/04/2003
• 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:
  US10/029,548
• Time in Patent Office: 410 Days
• Field of Search: 709/220, 709/224, 709/228, 709/227, 709/249, 370/254
• 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

Approaches for determining the actual physical topology of network devices in a network are 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 approaches eliminate misleading information and prevent generation of incorrect topologies.

Claims

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

determining possible neighboring devices for each device in a plurality of devices that are located in the network;

creating and storing information representing the plurality of devices;

determining true neighboring devices based on the plurality of devices and the possible neighboring devices;

creating and storing information representing the true neighboring devices; and

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

2. A method as recited in claim 1, further comprising the step of discovering, prior to determining the possible neighboring devices, the plurality of devices based on each address within a set of network addresses.

3. A method as recited in claim 1, further comprising the step of creating information representing the plurality of devices;

wherein the step of determining the true neighboring devices includes the step of processing the information representing the plurality of devices 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 the true neighboring devices; and

wherein the step of creating and storing information that represents the physical topology of the network includes the step of creating and storing information that represents the physical topology of the network based on the information representing the plurality of devices and the information representing the true neighboring devices.

4. A method as recited in claim 1, further comprising the step of creating information representing the plurality of devices;

wherein the step of determining the true neighboring devices includes the step of processing the information representing the plurality of devices 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 the true neighboring devices and each link between them, and

wherein the step of creating and storing information that represents the physical topology of the network includes the step of creating and storing information that represents the physical topology of the network based on the information representing the plurality of devices, the information representing the true neighboring devices, and each link.

5. 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.

6. A method as recited in claim 5:

wherein the step of sending the 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 a default routing address for each router type device; and

further comprising the step of detecting an Internet link to the network by identifying a router type device whose default routing address is outside a set of network address.

7. A method as recited in claim 5, wherein the step of sending the information requests to collect Layer 2 and Layer 3 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 within the plurality of devices that support CDP; and

wherein the step of determining possible neighboring devices includes the step of determining possible neighboring devices based on the CDP information.

8. A method as recited in claim 1, further comprising 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.

9. A method as recited in claim 1, further comprising the steps of:

discovering the plurality of devices based on each address within a set of network addresses by attempting to contact a device at each address within the set of network addresses;

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;

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.

10. A method as recited in claim 1, wherein the step of determining the true neighboring devices comprises the steps of:

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

bypassing the devices within the plurality of devices that are not actual devices associated with the set of network addresses.

11. A method as recited in claim 1, wherein the step of determining the true neighboring devices 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 a first Media Access Control (MAC) address associated with the first port is observed at the second port and a second 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 of the first potentially neighboring device and the second port of 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.

12. A method as recited in claim 1, wherein the step of determining the true neighboring devices 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.

13. A computer-readable medium 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:

determining possible neighboring devices for each device in a plurality of devices that are located in the network;

creating and storing information representing the plurality of devices;

determining true neighboring devices based on the plurality of devices and the possible neighboring devices;

creating and storing information representing the true neighboring devices; and

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

14. A computer-readable medium as recited in claim 13, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to carry out the step of discovering, prior to the step of determining the possible neighboring devices, the plurality of devices based on each address within a set of network addresses.

15. A computer-readable medium as recited in claim 13, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to carry out the step of creating information representing the plurality of devices;

wherein the instructions for determining the true neighboring devices further comprise instructions which, when executed by one or more processors, cause the one or more processors to carry out the step of processing the information representing the plurality of devices 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 the true neighboring devices; and

wherein the instructions for creating and storing information that represents the physical topology of the network further comprise instructions which, when executed by one or more processors, cause the one or more processors to carry out the steps of creating and storing information that represents the physical topology of the network based on the information representing the plurality of devices and the information representing the true neighboring devices.

16. A computer-readable medium as recited in claim 13, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to carry out the step of creating information representing the plurality of devices;

wherein the instructions for determining the true neighboring devices further comprise instructions which, when executed by one or more processors, cause the one or more processors to carry out the steps of includes the step of processing the information representing the plurality of devices 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 the true neighboring devices and each link between them; and

wherein instructions for creating and storing information that represents the physical topology of the network further comprise instructions which, when executed by one or more processors, cause the one or more processors to carry out the steps of creating and storing information that represents the physical topology of the network based on the information representing the plurality of devices, the information representing the true neighboring devices, and each link.

17. A computer-readable medium as recited in claim 13, wherein the instructions for determining possible neighboring devices further comprise instructions which, when executed by one or more processors, cause the one or more processors to carry out the step of sending information requests to collect Layer 2 and Layer 3 configuration information from the plurality of devices.

18. A computer-readable medium as recited in claim 17:

wherein the instructions for sending information requests to collect Layer 2 and Layer 3 configuration information further comprise instructions which, when executed by one or more processors, cause the one or more processors to carry out 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 a default routing address for each router type device; and

further comprising instructions which, when executed by the one or more processors, cause the one or more processors to carry out the step of detecting an Internet link to the network by identifying a router type device whose default routing address is outside a set of network address.

19. A computer-readable medium as recited in claim 17, wherein the instructions for sending information requests to collect Layer 2 and Layer 3 configuration information further comprise instructions which, when executed by one or more processors, cause the one or more processors to carry out the steps of:

identifying devices within the plurality of devices that support Cisco Discovery Protocol (CDP); and

retrieving CDP information from devices within the plurality of devices that support CDP; and

wherein the instructions for determining possible neighboring devices further comprise instructions which, when executed by one or more processors, cause the one or more processors to carry out the step of determining possible neighboring devices based on the CDP information.

20. A computer-readable medium as recited in claim 13, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to carry out 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.

21. A computer-readable medium as recited in claim 13, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to carry out the steps of:

discovering the plurality of devices based on each address within a set of network addresses by attempting to contact a device at each address within the set of network addresses;

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;

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.

22. A computer-readable medium as recited in claim 13, wherein the instructions for determining the true neighboring devices further comprise instructions which, when executed by the one or more processors, cause the one or more processors to carry out the steps of:

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

bypassing the devices within the plurality of devices that are not actual devices associated with the set of network addresses.

23. A computer-readable medium as recited in claim 13, wherein the instructions for determining the true neighboring devices further comprise instructions which, when executed by one or more processors, cause the one or more processors to carry out 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 a first Media Access Control (MAC) address associated with the first port is observed at the second port and a second 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 of the first potentially neighboring device and the second port of 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.

24. A computer-readable medium as recited in claim 13, wherein the instructions for determining the true neighboring devices further comprise instructions which, when executed by one or more processors, cause the one or more processors to carry out 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.

25. An apparatus for determining a physical topology of a network, the apparatus comprising:

means for determining possible neighboring devices for each device in a plurality of devices that are located in the network;

means for creating and storing information representing the plurality of devices;

means for determining true neighboring devices based on the plurality of devices and the possible neighboring devices;

means for creating and storing information representing the true neighboring devices; and

means for creating and storing information that represents the physical topology of the network based on the information representing the plurality of devices and the information representing the neighboring devices.

26. An apparatus as recited in claim 25, further comprising means for discovering, prior to determining the possible neighboring devices, the plurality of devices based on each address within a set of network addresses.

27. An apparatus as recited in claim 25, further comprising means for creating information representing the plurality of devices;

wherein the means for determining the true neighboring devices includes means for processing the information representing the plurality of devices 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 the true neighboring devices; and

wherein the means for creating and storing information that represents the physical topology of the network includes means for creating and storing information that represents the physical topology of the network based on the information representing the plurality of devices and the information representing the true neighboring devices.

28. An apparatus as recited in claim 25, further comprising means for creating information representing the plurality of devices;

wherein the means for determining the true neighboring devices includes means for processing the information representing the plurality of devices 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 the true neighboring devices and each link between them; and

wherein the means for creating and storing information that represents the physical topology of the network includes means for creating and storing information that represents the physical topology of the network based on the information representing the plurality of devices, the information representing the true neighboring devices, and each link.

29. An apparatus as recited in claim 25, wherein the means for determining possible neighboring devices includes means for sending information requests to collect Layer 2 and Layer 3 configuration information from the plurality of devices.

30. An apparatus as recited in claim 29:

wherein the means for sending information requests to collect Layer 2 and Layer 3 configuration information includes means for 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 a default routing address for each router type device; and

further comprising means for detecting an Internet link to the network by identifying a router type device whose default routing address is outside a set of network address.

31. An apparatus as recited in claim 29, wherein the means for sending information requests to collect Layer 2 and Layer 3 configuration information comprises:

means for identifying devices within the plurality of devices that support Cisco Discovery Protocol (CDP); and

means for retrieving CDP information from devices within the plurality of devices that support CDP; and

wherein the means for determining possible neighboring devices includes means for determining possible neighboring devices based on the CDP information.

32. An apparatus as recited in claim 25, further comprising means for 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.

33. An apparatus as recited in claim 25, further comprising:

means for discovering the plurality of devices based on each address within a set of network addresses by attempting to contact a device at each address within the set of network addresses;

means for, 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;

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

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

34. An apparatus as recited in claim 25, wherein the means for determining the true neighboring devices comprises:

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

means for bypassing the devices within the plurality of devices that are not actual devices associated with the set of network addresses.

35. An apparatus as recited in claim 25, wherein the means for determining the true neighboring devices further comprises:

means for 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 a first Media Access Control (MAC) address associated with the first port is observed at the second port and a second MAC address associated with the second port is observed at the first port;

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

means for, based on the common MAC address, determining that the first port of the first potentially neighboring device and the second port of 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.

36. An apparatus as recited in claim 25, wherein the means for determining the true neighboring devices further comprises:

means for 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

means for 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.

37. 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;

determining possible neighboring devices for each device in a plurality of devices that are located in the network;

creating and storing information representing the plurality of devices;

determining true neighboring devices based on the plurality of devices and the possible neighboring devices;

creating and storing information representing the true neighboring devices; and

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

38. A computer apparatus as recited in claim 37, wherein the memory further contains one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the step of discovering, prior to the step of determining the possible neighboring devices, the plurality of devices based on each address within a set of network addresses.

39. A computer apparatus as recited in claim 37, wherein the memory further contains one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the step of creating information representing the plurality of devices;

wherein the instructions for determining the true neighboring devices further comprise instructions which, when executed by the processor, cause the processor to carry out the step of processing the information representing the plurality of devices 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 the true neighboring devices; and

wherein the instructions for creating and storing information that represents the physical topology of the network further comprise instructions which, when executed by the processor, cause the processor to carry out the steps of creating and storing information that represents the physical topology of the network based on the information representing the plurality of devices and the information representing the true neighboring devices.

40. A computer apparatus as recited in claim 37, wherein the memory further contains one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the step of creating information representing the plurality of devices;

wherein the instructions for determining the true neighboring devices further comprise instructions which, when executed by the processor, cause the processor to carry out the steps of processing the information representing the plurality of devices 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 the true neighboring devices and each link between them; and

wherein the instructions for creating and storing information that represents the physical topology of the network further comprise instructions which, when executed by the processor, cause the processor to carry out the steps of creating and storing information that represents the physical topology of the network based on the information representing the plurality of devices, the information representing the true neighboring devices, and each link.

41. A computer apparatus as recited in claim 37, wherein the instructions for determining possible neighboring devices further comprise instructions which, when executed by the processor, cause the processor to carry out the step of sending information requests to collect Layer 2 and Layer 3 configuration information from the plurality of devices.

42. A computer apparatus as recited in claim 41:

wherein the instructions for sending information requests to collect Layer 2 and Layer 3 configuration information further comprise instructions which, when executed by the processor, cause the processor to carry out 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 a default routing address for each router type device; and

wherein the memory further contains one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the step of detecting an Internet link to the network by identifying a router type device whose default routing address is outside a set of network address.

43. A computer apparatus as recited in claim 41, wherein the instructions for sending information requests to collect Layer 2 and Layer 3 configuration information further comprise instructions which, when executed by the processor, cause the processor to carry out the steps of:

identifying devices within the plurality of devices that support Cisco Discovery Protocol (CDP); and

retrieving CDP information from devices within the plurality of devices that support CDP; and

wherein the instructions for determining possible neighboring devices further comprise instructions which, when executed by the processor, cause the processor to carry out the step of determining possible neighboring devices includes the step of determining possible neighboring devices based on the CDP information.

44. A computer apparatus as recited in claim 37, wherein the memory further contains one or more sequences of instructions which, when executed by the processor, cause the processor to carry out 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.

45. A computer apparatus as recited in claim 37, wherein the memory further contains one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of:

discovering the plurality of devices based on each address within a set of network addresses by attempting to contact a device at each address within the set of network addresses;

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;

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.

46. A computer apparatus as recited in claim 37, wherein the instructions for determining the true neighboring devices further comprise instructions which, when executed by the processor, cause the processor to carry out the steps of:

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

bypassing the devices within the plurality of devices that are not actual devices associated with the set of network addresses.

47. A computer apparatus as recited in claim 37, wherein the instructions for determining the true neighboring devices further comprise instructions which, when executed by the processor, cause the processor to carry out 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 a first Media Access Control (MAC) address associated with the first port is observed at the second port and a second 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 of the first potentially neighboring device and the second port of 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.

48. A computer apparatus as recited in claim 37, wherein the instructions for determining the true neighboring devices further comprise instructions which, when executed by the processor, cause the processor to carry out 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.