# US 2014/0229612 A1 · Network topology generation using traceroute data

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

- Number: US 2014/0229612 A1
- Document ID: US20140229612A1
- Status: Published application
- Kind: A1
- Application number: 14/176,644
- Filed: 2014-02-10
- Published: 2014-08-14
- Earliest claimed: 2013-02-11
- Assignees: Riverbed Technology, Inc.
- Applicants: Riverbed Technology, Inc.
- Inventors: Karthikeyan CHANDRASHEKAR; Majid RAISSI-DEHKORDI; Walt WHIMPENNY; Paul JANES
- Web page: https://patentgrep.com/patent/US20140229612A1

## CPC

- H04L 43/10: Active monitoring, e.g. heartbeat, ping or trace-route
- H04L 41/12: Discovery or management of network topologies
- H04L 43/0811: by checking connectivity
- H04L 61/103: across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP]
- H04L 61/4511: using domain name system [DNS]
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Embodiments provide systems, methods, and computer program products for inferring node and link information from traceroute data in order to generate topology information. A system receives traceroute data for a data packet that traverses a path from a source to a destination. The system infers port types for the addresses in the traceroute data and groups subsets of the addresses in the traceroute data into logical nodes based on neighbor relationships demonstrated in backward and forward neighbors sets. The system then generates node and link information based on the inferred and grouped information.

## Claims

### Claim 1

A method for generating a network topology, comprising:
receiving traceroute data corresponding to a data packet traversing a path from a source address to a destination address via a plurality of intermediate addresses;
inferring port types for the source address, the destination address, and each of the plurality of intermediate addresses based on the traceroute data;
grouping a subset of the source address, the destination address, and the plurality of intermediate addresses into a logical node based on generated backward and forward neighbors sets of the addresses, the logical node comprising grouped node information; and
generating node and link relationships between the source address, the destination address, and the plurality of intermediate addresses based on the inferred port types and the grouped node information.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
determining geographic locations for the source address, the destination address, and each of the plurality of intermediate addresses; and
generating the node and link relationships further based on the geographic locations.

### Claim 3 (depends on 1)

The method of claim 1, wherein the inferring further comprises:
determining a name for the source address, the destination address, and each of the plurality of intermediate addresses;
mapping the determined name for the source address, the destination address, and each of the plurality of intermediate addresses to an entry in a dictionary of port type information; and
assigning the source address, the destination address, and each of the plurality of intermediate addresses port type information corresponding to the mapped entry in the dictionary.

### Claim 4 (depends on 3)

The method of claim 3, wherein determining the name further comprises:
performing a reverse domain name system (DNS) lookup for the source address, the destination address, and each of the plurality of intermediate addresses.

### Claim 5 (depends on 1)

The method of claim 1, wherein grouping further comprises:
grouping addresses in each backward neighbors set as a separate logical node for each of the source address, the destination address, and the plurality of intermediate addresses.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
checking for a mismatch between node numbers assigned to addresses in one of the backward neighbors sets;
obtaining a geographic location for a mismatched address in the one of the backward neighbors sets in response to detecting the mismatched address; and
comparing the obtained geographic location to geographic locations of other backward neighbors sets.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
assigning the mismatched address a node number associated with another backward neighbors set in response to a match with the other backward neighbors set; and
assigning the mismatched address a node number associated with a majority of the addresses in the one of the backward neighbors sets in response to no match.

### Claim 8 (depends on 1)

The method of claim 1, wherein the source address, the destination address, and the plurality of intermediate addresses represent ingress ports, the method further comprising:
inferring an egress address for the logical node based on subnet information derived from an address in the forward neighbors set.

### Claim 9

A system for generating a network topology, comprising:
a node inference module configured to group a subset of a source address, a destination address, and a plurality of intermediate addresses from traceroute data into a logical node based on generated backward and forward neighbors sets of the addresses;
a node and link generation module configured to generate node and link relationships between the source address, the destination address, and the plurality of intermediate addresses based on the grouping; and
a processor configured to execute the node inference module and the node and link generation module.

### Claim 10 (depends on 9)

The system of claim 9, further comprising:
a transceiver configured to receive the traceroute data, the traceroute data corresponding to a data packet traversing a path from the source address to the destination address via the plurality of intermediate addresses.

### Claim 11 (depends on 9)

The system of claim 9, further comprising:
a port inference module configured to infer port types for the source address, the destination address, and the plurality of intermediate addresses from the traceroute data;
wherein the processor is further configured to execute the port inference module.

### Claim 12 (depends on 11)

The system of claim 11, wherein the port inference module is further configured to:
determine a name for the source address, the destination address, and each of the plurality of intermediate addresses;
map the determined name for the source address, the destination address, and each of the plurality of intermediate addresses to an entry in a dictionary of port type information; and
assign the source address, the destination address, and each of the plurality of intermediate addresses port type information corresponding to the mapped entry in the dictionary.

### Claim 13 (depends on 9)

The system of claim 9, wherein the node inference module is further configured to:
group addresses in each backward neighbors set as a separate logical node for each of the source address, the destination address, and the plurality of intermediate addresses.

### Claim 14 (depends on 13)

The system of claim 13, wherein the node inference module is further configured to:
check for a mismatch between node numbers assigned to addresses in one of the backward neighbors sets;
obtain a geographic location for a mismatched address in the one of the backward neighbors sets in response to detecting the mismatched address; and
compare the obtained geographic location to geographic locations of other backward neighbors sets.

### Claim 15 (depends on 14)

The system of claim 14, wherein the node inference module is further configured to:
assign the mismatched address a node number associated with another backward neighbors set in response to a match with the other backward neighbors set; and
assign the mismatched address a node number associated with a majority of the addresses in the one of the backward neighbors sets in response to no match.

### Claim 16

A method, comprising:
generating a backward neighbors set for each of a source address, a destination address, and a plurality of intermediate addresses;
generating a forward neighbors set for each of the source address, the destination address, and the plurality of intermediate addresses; and
grouping addresses in each backward neighbors set as a separate logical node for each of the source address, the destination address, and the plurality of intermediate addresses.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
checking for a mismatch between node numbers assigned to addresses in one of the backward neighbors sets;
obtaining a geographic location for a mismatched address in the one of the backward neighbors sets in response to detecting the mismatched address; and
comparing the obtained geographic location to geographic locations of other backward neighbors sets.

### Claim 18 (depends on 17)

The method of claim 17, further comprising:
assigning the mismatched address a node number associated with another backward neighbors set in response to a match with the other backward neighbors set; and
assigning the mismatched address a node number associated with a majority of the addresses in the one of the backward neighbors sets in response to no match.

### Claim 19 (depends on 16)

The method of claim 16, wherein the source address, the destination address, and the plurality of intermediate addresses represent ingress ports, the method further comprising:
inferring an egress address for the logical node based on subnet information derived from an address in the forward neighbors set.

### Claim 20 (depends on 16)

The method of claim 16, wherein the logical node comprises grouped node information, the method further comprising:
generating node and link relationships between the source address, the destination address, and the plurality of intermediate addresses based on the grouped node information.

### Claim 21

A non-transitory computer-readable storage medium having control logic recorded thereon that, when executed by a processor, causes the processor to perform a method for generating a network topology in a server, the method comprising:
generating a backward neighbors set for each of a source address, a destination address, and a plurality of intermediate addresses;
generating a forward neighbors set for each of the source address, the destination address, and the plurality of intermediate addresses; and
grouping addresses in each backward neighbors set as a separate logical node for each of the source address, the destination address, and the plurality of intermediate addresses.

### Claim 22 (depends on 21)

The non-transitory computer-readable storage medium of claim 21, the method further comprising:
checking for a mismatch between node numbers assigned to addresses in one of the backward neighbors sets;
obtaining a geographic location for a mismatched address in the one of the backward neighbors sets in response to detecting the mismatched address; and
comparing the obtained geographic location to geographic locations of other backward neighbors sets.

### Claim 23 (depends on 22)

The non-transitory computer-readable storage medium of claim 22, the method further comprising:
assigning the mismatched address a node number associated with another backward neighbors set in response to a match with the other backward neighbors set; and
assigning the mismatched address a node number associated with a majority of the addresses in the one of the backward neighbors sets in response to no match.

### Claim 24 (depends on 21)

The non-transitory computer-readable storage medium of claim 21, wherein the source address, the destination address, and the plurality of intermediate addresses represent ingress ports, the method further comprising:
inferring an egress address for the logical node based on subnet information derived from an address in the forward neighbors set.

### Claim 25 (depends on 21)

The non-transitory computer-readable storage medium of claim 21, wherein the logical node comprises grouped node information, the method further comprising:
generating node and link relationships between the source address, the destination address, and the plurality of intermediate addresses based on the grouped node information.