Back to results
US 11,108,816 B2Granted
Constructible automata for internet routes
OwnerJohann Schlampinventor
Life of this patent
Estimating the term…
Abstract
In an example method, a computer system retrieves a plurality of data items. Each data item indicates a respective network route on the network. The computer system determines a route automaton based on the plurality of data items. The route automaton includes a representation of the network routes. The computer system determines one or more routing policies on the network based on the route automaton. The method can be used to detect one or more routing policies on a network.
Claims14
A method of detecting one or more routing policies in use in a network including a plurality of network devices, the method comprising:
- identifying, by a computer system, a plurality of network routes, wherein each network route indicates a path by which data packets can traverse the network, the path including a subset of the plurality of network devices;
- determining, by the computer system, a route automaton based on the plurality of network routes, wherein the route automaton is a finite-state machine that defines one or more states and one or more transitions between the states, wherein the route automaton represents network routes along inter-domain routing, and wherein determining the route automaton comprises:
- determining a deterministic finite-state automaton based on the plurality of network routes, wherein the deterministic finite-state automaton comprises a plurality of states and a plurality of paths between the states, and wherein each state is associated with a routing policy associated with a particular network device on the network;
- performing a minimization operation with respect to the deterministic finite-state automaton, including combining two or more states associated with a similar routing policy, and reducing a number of states of the deterministic finite-state automaton such that the deterministic finite-state automaton includes a minimum number of unique states necessary to represent each of the network routes;
- determining, by the computer system, one or more routing policies on the network based on said route automaton;
- identifying, by the computer system, a routing anomaly occurring on the network based on the one or more routing policies, wherein the routing anomaly is associated with one or more affected devices from the plurality of network devices, and wherein identifying the routing anomaly occurring on the network comprises identifying, by a software implementation of the route automaton executed by a processor of the computer system, non-uniform routing decisions on the network;
- and
- providing, by the computer system, an identification of the routing anomaly and the affected devices to an administrative entity associated with the network.
5 more elements
A system, comprising:
- one or more processors;
- and
- non-transitory computer readable medium storing instructions operable to cause one or more processors to perform operations comprising:
- identifying, by a computer system, a plurality of network routes, wherein each network route indicates a path by which data packets can traverse the network, the path including a subset of the plurality of network devices;
- determining, by the computer system, a route automaton based on the plurality of network routes, wherein the route automaton is a finite-state machine that defines one or more states and one or more transitions between the states, wherein the route automaton represents network routes along inter-domain routing, and wherein determining the route automaton comprises:
- determining a deterministic finite-state automaton based on the plurality of network routes, wherein the deterministic finite-state automaton comprises a plurality of states and a plurality of paths between the states, and wherein each state is associated with a routing policy associated with a particular network device on the network;
- performing a minimization operation with respect to the deterministic finite-state automaton, including combining two or more states associated with a similar routing policy, and reducing a number of states of the deterministic finite-state automaton such that the deterministic finite-state automaton includes a minimum number of unique states necessary to represent each of the network routes;
- determining, by the computer system, one or more routing policies on the network based on said route automaton;
- identifying, by the computer system, a routing anomaly occurring on the network based on the one or more routing policies, wherein the routing anomaly is associated with one or more affected devices from the plurality of network devices, and wherein identifying the routing anomaly occurring on the network comprises identifying, by a software implementation of the route automaton executed by a processor of the computer system, non-uniform routing decisions on the network;
- and
- providing, by the computer system, an identification of the routing anomaly and the affected devices to an administrative entity associated with the network.
8 more elements
Dependencies are inferred from the claim text.