# US 8,543,681 B2 · Network topology discovery systems and methods

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,543,681 B2
- Document ID: US8543681B2
- Status: Granted
- Kind: B2
- Application number: 10/270,335
- Filed: 2002-10-15
- Published: 2003-05-22
- Granted: 2013-09-24
- Earliest claimed: 2001-10-15
- Assignees: Volli Polymer GmbH LLC
- Applicants: Mark J. Bearden; Lorraine Denby; Bengi Karacali; Jean Meloche; David Thomas Stott
- Inventors: Mark J. Bearden; Lorraine Denby; Bengi Karacali; Jean Meloche; David Thomas Stott
- Web page: https://patentgrep.com/patent/US8543681B2

## CPC

- H04L 41/0213: Standardised network management protocols, e.g. simple network management protocol [SNMP]
- H04L 41/12: Discovery or management of network topologies
- H04L 41/22: comprising specially adapted graphical user interfaces [GUI]
- H04L 43/0811: by checking connectivity
- H04L 43/091: Measuring contribution of individual network components to actual service level
- H04L 43/50: Testing arrangements
- H04M 3/2236: {Quality of speech transmission monitoring}
- H04M 3/2254: {in networks}
- 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)}
- H04L 41/0663: Performing the actions predefined by failover planning, e.g. switching to standby network elements
- H04L 41/5051: Service on demand, e.g. definition and deployment of services in real time
- H04L 41/5087: {wherein the managed service relates to voice services (management of VoIP services H04M7/0081)}
- H04L 41/509: {wherein the managed service relates to media content delivery, e.g. audio, video or TV}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04M: TELEPHONIC COMMUNICATION (circuits for controlling other apparatus via a telephone cable and not involving telephone switching apparatus G08)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 3)

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

### Claim 5 (depends on 4)

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

### Claim 6 (depends on 5)

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

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 7)

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

### Claim 9 (depends on 1)

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

### Claim 10 (depends on 1)

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

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 11)

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

### Claim 13 (depends on 12)

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

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 1)

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

### Claim 16 (depends on 15)

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

### Claim 17 (depends on 16)

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

### Claim 18 (depends on 17)

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

### Claim 19 (depends on 1)

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

### Claim 20 (depends on 19)

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.

### Claim 21 (depends on 20)

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.

### Claim 22 (depends on 1)

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

### Claim 23 (depends on 22)

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.

### Claim 24 (depends on 23)

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.

### Claim 25 (depends on 24)

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.

### Claim 26 (depends on 25)

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

### Claim 27 (depends on 26)

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.

### Claim 28 (depends on 1)

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

### Claim 29 (depends on 28)

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

### Claim 30 (depends on 29)

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

### Claim 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.

### Claim 32 (depends on 31)

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

### Claim 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.

### Claim 34 (depends on 33)

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

### Claim 35 (depends on 1)

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

### Claim 36 (depends on 10)

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

### Claim 37 (depends on 22)

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.

### Claim 38 (depends on 1)

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.

### Claim 39 (depends on 1)

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

### Claim 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.

### Claim 41 (depends on 40)

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

### Claim 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.

### Claim 43 (depends on 42)

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

### Claim 44 (depends on 1)

The method according to claim 1, further comprising:
interleaving the layer-3 path with the layer-2 path to form a multi-path.

### Claim 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.