Network topology discovery systems and methods

• US 8,543,681 B2
• Filed: 10/15/2002
• Issued: 09/24/2013
• Est. Priority Date: 10/15/2001
• Status: Active Grant

• Current Assignee: TP-Link USA Corporation
• Original Assignee: Volli Polymer GmbH LLC (Intellectual Ventures LLC)
• Inventors: Bearden, Mark J., Denby, Lorraine, Karacali, Bengi, Meloche, Jean, Stott, David Thomas
• Primary Examiner(s): Pollack, Melvin H
• Application Number:
  US10/270,335
• Publication Number:
  US 20030097438A1
• Time in Patent Office: 3,997 Days
• Field of Search: 709/203, 709/216, 709/218, 709223-229, 709/238, 709/245, 709/250, 709/252, 709/236, 709/242, 709/249, 370/255, 370/389, 370/392, 370/399, 370/395.31, 370/395.52, 370/395.53, 370/409, 370/219, 370/220, 370/223, 370/246, 370/254, 370/395.5, 37039551-39554, 370/465, 370/466, 718/104, 707/10, 707/104.1
• US Class Current: 709/224
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0663 Performing the actions predefined by failover planning, e.g. switching to standby network elements
• 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]
• CPC Class Codes: H04L 41/5051 Service on demand, e.g. definition and deployment of services in real time
• CPC Class Codes: H04L 41/5087 wherein the managed service relates to voice services management of VoIP services H04M7/0081
• CPC Class Codes: H04L 41/509 wherein the managed service relates to media content delivery, e.g. audio, video or TV
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/091 Measuring contribution of individual network components to actual service level
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04M 3/2236 Quality of speech transmission monitoring
• CPC Class Codes: H04M 3/2254 in networks
• CPC Class Codes: H04M 7/006 Networks other than PSTN/ISDN providing telephone service, e.g. Voice over Internet Protocol (VoIP) , including next generation networks with a packet-switched transport layer H04L65/00 takes precedence; aspects not specific to the type of network H04M3/00; special services in those networks H04M3/42

Abstract

A system discovers the topology of devices in a network, such as all of the layer-2 and layer-3 devices, including routers and switches. The devices are mapped, as well as the links that join them. The devices are polled using SNMP requests. Route tables are derived from each router to determine addresses of the devices. A spanning tree process is used to discover layer-2 devices. Connections between layers are then discovered. Where information is incomplete, an undiscovered router cloud is recognized.

Claims

1. A method for discovery of topology of devices in a network, comprising:

discovering devices in the network;

discovering connections between the devices; and

discovering multi-layer paths between devices in the network along the connections, wherein a multi-layer path is defined as a layer-3 path interleaved with a layer-2 path on each layer-3 hop, wherein discovering a multi-layer path includes identifying the layer-3 path, identifying the layer-2 path for each hop on the layer-3 path, and combining the identified paths.

2. The method according to claim 1, wherein discovering devices includes probing addresses in the network and collecting responses to the probes.

3. The method according to claim 2, wherein discovering devices further includes determining a type of each device that responded to the probes.

4. The method according to claim 3, wherein discovering devices further includes identifying aliased addresses.

5. The method according to claim 4, wherein discovering devices further includes filtering responses from special addresses.

6. The method according to claim 5, wherein discovering devices further includes collecting router tables.

7. The method according to claim 6, wherein discovering devices further includes collecting switch tables.

8. The method according to claim 7, wherein discovering devices further includes storing the results in a data store.

9. The method according to claim 1, wherein discovering devices includes using SNMP procedures.

10. The method according to claim 1, wherein discovering connections includes discovering layer-3 connections.

11. The method according to claim 10, wherein discovering connections between devices in the network further includes discovering connections between layer-3 devices to an undiscovered router cloud.

12. The method according to claim 11, wherein discovering connections further includes discovering connections of layer-3 devices to subnets.

13. The method according to claim 12, wherein discovering connections further includes finding an interface used on each device on a connection.

14. The method according to claim 13, wherein discovering connections further includes finding a network address used by the devices on the ends of each connection.

15. The method according to claim 1, wherein discovering connections between devices in the network includes discovering layer-2 connections.

16. The method according to claim 15, wherein discovering connections further includes using switch tables pertaining to a spanning tree algorithm.

17. The method according to claim 16, wherein discovering connections further includes identifying interfaces used by the devices on ends of each connection.

18. The method according to claim 17, wherein discovering connections further includes finding connections for each virtual local area network (LAN) in networks.

19. The method according to claim 1, wherein discovering connections includes finding connections between layer-3 devices and layer-2 devices.

20. The method according to claim 19, wherein discovering connections further includes identifying a minimal region in a layer-2 topology where each layer-3 device may connect.

21. The method according to claim 20, wherein discovering connections further includes using switch table entries and a discovered layer-2 topology to identify the minimal region.

22. The method according to claim 1, wherein discovering multi-layer paths between devices in the network includes discovering interconnections of layer-3 devices.

23. The method according to claim 22, wherein discovering multi-layer paths further includes finding an ingress and egress address for each device along the path.

24. The method according to claim 23, wherein discovering multi-layer paths further includes finding an ingress and egress interface for each device along the path.

25. The method according to claim 24, wherein discovering multi-layer paths further includes combining partial paths in each direction when unable to find a complete path otherwise.

26. The method according to claim 25, wherein discovering multi-layer paths further includes using an undiscovered router cloud to combine partial paths.

27. The method according to claim 26, wherein discovering multi-layer paths further includes using router tables to find a connection from a host to its default router.

28. The method according to claim 1, wherein discovering multi-layer paths includes discovering interconnections of layer-2 devices.

29. The method according to claim 28, wherein discovering multi-layer paths further includes using switch tables.

30. The method according to claim 29, wherein discovering multi-layer paths further includes using locations of endpoints.

35. The method according to claim 1, wherein the topology of the network further includes representations of undiscovered regions in the network.

36. The method according to claim 10, wherein discovering connections further includes finding connections between layer-3 devices and representations of undiscovered regions.

37. The method according to claim 22, wherein discovering multi-layer paths between devices further includes finding connections between discovered devices and representations of undiscovered regions along layer-3 paths.

38. The method according to claim 1, wherein discovering multi-layer paths between devices further includes finding connections between discovered devices and representations of undiscovered regions along multilayer paths.

39. The method according to claim 1, further comprising enabling modifications to the topology by a user.

44. The method according to claim 1, further comprising:

interleaving the layer-3 path with the layer-2 path to form a multi-path.

31. A system for topological discovery of devices in a network, comprising:

a memory; and

a processor operatively coupled to the memory, wherein the processor is configured to;

identify connections between layer-3 devices;

identify connections between layer-2 devices;

identify a layer-3 path;

identify a layer-2 path for each hop on the layer-3 path; and

combine the identified paths to identify a multi-layer path.

32. The system according to claim 31, wherein the memory is configured to receive and store topological connection data of the network.

33. A system for topological path discovery through devices in a network, comprising:

a memory; and

a processor operatively coupled to the memory, wherein the processor is configured to;

identify a layer-3 path between a pair of layer-3 devices;

identify layer-2 path for each hop on the layer-3 path; and

combine the identified paths to identify a multi-layer path, wherein the multi-layer path is defined as a layer-3 path interleaved with a layer-2 path on each layer-3 hop.

34. The system according to claim 33, wherein the memory is configured to receive and store path data of the network.

40. A system for topological discovery of devices in a network, comprising:

a memory; and

a processor operatively coupled to the memory and configured to;

identify connections between layer-3 devices;

identify connections between layer-2 devices;

identify connections between the layer-3 devices and the layer-2 devices;

identify a layer-3 path;

identify a layer-2 path for each hop on the layer-3 path;

combine the identified paths to identify a multi-layer path;

identify connections between discovered devices and representations of undiscovered regions; and

reflect user input on interconnections between devices in the network.

41. The system according to claim 40, wherein the memory is configured to receive and store topological connection data of the network.

42. A system for topological path discovery through devices in a network, comprising:

a memory; and

a processor operatively coupled to the memory and configured to;

identify a layer-3 path between pairs of layer-3 devices;

identify a layer-2 path for each hop on the layer-3 path;

combine the identified paths to identify a multi-layer path between devices using both layer-3 and layer-2 devices, wherein a multi-layer path is defined as a layer-3 path interleaved with a layer-2 path on each layer-3 hop;

include representations of undiscovered regions and their connections to discovered devices along layer-3 and multi-layer paths; and

reflect user input on layer-3 and multilayer paths in the network.

43. The system according to claim 42, wherein the memory is configured to receive and store path data of the network.

45. A method for discovery of topology of devices, including level-2 devices and level-3 devices, in a network, comprising:

discovering layer-2 devices in the network;

discovering layer 3 devices in the network;

identifying a layer-3 path in the network;

identifying a layer-2 path for each hop on the layer-3 path; and

combining the identified paths to identify a multi-layer path.