Structured schema for temporal graph storage and retrieval

Patent metadata

Field	Value
Publication number	US-10846339-B2
Application number	US-201715828316-A
Country	US
Kind code	B2
Filing date	Nov 30, 2017
Priority date	Jun 20, 2017
Publication date	Nov 24, 2020
Grant date	Nov 24, 2020

Abstract

A method for performing network analysis comprising: receiving telemetry information for a computer network, the telemetry information comprising network device state information for internetworking devices in the computer network and network traffic flow information for data packet flows through the computer network; transforming the telemetry information into a temporal graph that is digitally stored in computer memory, wherein the temporal graph comprises a plurality of graph elements include a plurality of vertices and a plurality of edges, each of the vertices representing an internetworking device, each of the edges representing one or more portions of a data packet flow; digitally storing graph element metadata corresponding to the plurality of graph elements in a structured format, the graph element metadata comprising temporal data for each graph element of the plurality of graph elements, the temporal data comprising a modification time value specifying a modification time that is associated with each graph element.

First claim

What is claimed is:

1. A method comprising:
receiving telemetry information for a computer network, the telemetry information comprising network device state information for internetworking devices in the computer network and network traffic flow information for data packet flows through the computer network;
transforming the telemetry information into a temporal graph that is digitally stored in computer memory, wherein the temporal graph comprises a plurality of graph elements include a plurality of vertices and a plurality of edges, each of the vertices representing an internetworking device in the computer network, each of the edges representing one or more portions of a data packet flow through the computer network; and
digitally storing graph element metadata corresponding to the plurality of graph elements in a structured format, the graph element metadata comprising temporal data for each graph element of the plurality of graph elements, the temporal data comprising a modification time value specifying a modification time that is associated with each graph element, wherein digitally storing the graph element metadata comprises digitally storing temporal links to at least one of the following: a previous version if the previous version exist or a subsequent version if the subsequent version exist of the plurality of graph elements, and wherein the temporal links are traversed to retrieve at least one of the following: the previous version or the subsequent version of a graph element of the plurality of graph elements.

2. The method of claim 1 wherein the graph element metadata comprises vertex metadata corresponding to each vertex of the plurality of vertices and edge metadata corresponding to each edge of the plurality of edges.

3. The method of claim 1 wherein the temporal data for each graph element further comprises a subsequent modification time value specifying a modification time that is associated with the subsequent version of the graph element.

4. The method of claim 3 further comprising:
in response to receiving a request to modify a particular graph element:
generating a new graph element that is a second version of the particular graph element, wherein the new graph element is associated with a particular modification time, and storing graph element metadata corresponding to the new graph element, the new graph element metadata including a modification to the particular graph element; and
updating the temporal data of the particular graph element to include a subsequent modification time value that specifies the particular modification time.

5. The method of claim 3 further comprising:
in response to receiving a request to delete a particular graph element:
generating a new graph element that is a second version of the particular graph element, wherein the new graph element is associated with a particular modification time, and storing graph element metadata corresponding to the new graph element, the new graph element metadata including metadata indicating that the new graph element is a deleted graph element; and
updating the temporal data of the particular graph element to include a subsequent modification time value that specifies the particular modification time.

6. The method of claim 1 further comprising, in response to receiving a request for a snapshot of the temporal graph, generating a snapshot vertex, wherein the snapshot vertex is connected to a first set of one or more vertices, of the plurality of vertices, that are associated with the request for the snapshot.

7. The method of claim 6 further comprising:
in response to receiving a request to temporally traverse the snapshot of the temporal graph, generating an updated snapshot vertex, wherein the updated snapshot vertex is connected to a second set of one or more vertices, of the plurality of vertices, that are associated with the temporal traversal of the snapshot.

8. The method of claim 1 further comprising:
in response to receiving a request for temporal graph data, wherein the request includes one or more request criteria, identifying a set of one or more graph elements that satisfy the one or more request criteria;
retrieving graph element metadata corresponding to the set of one or more graph elements.

9. The method of claim 8 wherein identifying the set of one or more graph elements is based at least in part on the temporal data associated with each graph element of the set of one or more graph elements.

10. The method of claim 9 wherein the request includes temporal traversal of one or more particular graph elements, the method further comprising modifying the one or more request criteria to include the temporal traversal.

11. A non-transitory computer medium storing instructions which when executed perform a method comprising:
receiving telemetry information for a computer network, the telemetry information comprising network device state information for internetworking devices in the computer network and network traffic flow information for data packet flows through the computer network;
transforming the telemetry information into a temporal graph that is digitally stored in computer memory, wherein the temporal graph comprises a plurality of graph elements comprising a plurality of vertices and a plurality of edges, each of the plurality of vertices representing an internetworking device in the computer network, each of the plurality of edges representing one or more portions of a data packet flow through the computer network; and
digitally storing graph element metadata corresponding to the plurality of graph elements in a structured format, the graph element metadata comprising temporal data for each graph element of the plurality of graph elements, the temporal data comprising a modification time value specifying a modification time that is associated with each graph element, wherein digitally storing the graph element metadata comprises digitally storing temporal links to at least one of the following: a previous version if the previous version exist or a subsequent version if the subsequent version exist of the plurality of graph elements, and wherein the temporal links are traversed to retrieve at least one of the following: the previous version or the subsequent version of a graph element of the plurality of graph elements.

12. The non-transitory computer readable medium of claim 11 wherein the graph element metadata comprises vertex metadata corresponding to each vertex of the plurality of vertices and edge metadata corresponding to each edge of the plurality of edges.

13. The non-transitory computer readable medium of claim 11 wherein the temporal data for each graph element further comprises a subsequent modification time value specifying a modification time that is associated with the subsequent version of the graph element.

14. The non-transitory computer readable medium of claim 13 , further comprising:
in response to receiving a request to modify a particular graph element:
generating a new graph element that is a second version of the particular graph element, wherein the new graph element is associated with a particular modification time, and storing graph element metadata corresponding to the new graph element, the new graph element metadata including a modification to the particular graph element;
updating the temporal data of the particular graph element to include a subsequent modification time value that specifies the particular modification time.

15. The non-transitory computer readable medium of claim 13 , further comprising:
in response to receiving a request to delete a pa

Assignees

• Cisco Tech Inc

Inventors

• Raghavendra Arun Kumar
• NARAYANAN Bhalaji

Classifications

• G06T11/26

  Drawing of charts or graphs · CPC title

• H04L41/14

  Network analysis or design · CPC title

• H04L43/08

  Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters · CPC title

• H04L43/0817

  by checking functioning · CPC title

• G06F16/2477

  Temporal data queries · CPC title