Dynamic evaluation and implementation of network mutations

Patent metadata

Field	Value
Publication number	US-11936558-B1
Application number	US-202117643774-A
Country	US
Kind code	B1
Filing date	Dec 10, 2021
Priority date	Dec 10, 2021
Publication date	Mar 19, 2024
Grant date	Mar 19, 2024

Abstract

Systems and methods are provided for evaluation of networks and changes thereto using automated analysis of network models. The automated analysis can be used to determine how to implement and mutate networks efficiently and effectively, to determine whether and why network resources are unable to communicate with each other, and the like. Automated analysis can allow users (e.g., network administrators) to define networks and pose changes to networks using high-level policies (e.g., written in a declarative language), have those polices automatically translated to lower-level implementation operations for analysis, and in some cases have results of the analysis presented back to the users in an easy-to-understand form.

First claim

What is claimed is:

1. A computer-implemented method comprising:
under control of a computing system of a cloud provider network, the computing system comprising memory and one or more computer processors configured to execute specific instructions:
obtaining policy data regarding a change to be implemented to a private network deployed on the cloud provider network;
determining a plurality of sequences of implementation operations, wherein individual implementation operations of the plurality of sequences of implementation operations comprise modifying at least one of a set of routes or a set of attachments associated with communication connections of the private network, wherein individual sequences of the plurality of sequences of implementation operations are configured to implement the change to the private network, and wherein each respective implementation operation of a first sequence of implementation operations of the plurality of sequences of implementation operations is associated with an expected time for the respective implementation operation to transition from a first state of the private network before performance of the respective implementation operation to a second state of the private network after performance of the respective implementation operation;
determining, based at least partly on a model of the private network representing application of a first implementation operation of the first sequence of implementation operations, that an intermediate state of the private network, between an initial state of the private network prior to performance of any implementation operation of the first sequence of implementation operations and an end state of the private network after performing a final implementation operation of the first sequence of implementation operations, satisfies one or more routing criteria; and
causing performance of the first sequence of implementation operations based at least partly on a total time, calculated by adding the expected time of each respective implementation operation of the first sequence of implementation operations, being lower than a total time of another sequence of implementation operations of the plurality of sequences of implementation operations, and on determining that the intermediate state satisfies the one or more routing criteria.

2. The computer-implemented method of claim 1 , further comprising deploying the private network as a virtual private cloud-based wide area network connecting two or more client on-premise networks to each other via the cloud provider network.

3. The computer-implemented method of claim 1 , further comprising determining that in the end state of the first sequence of implementation operations, the private network satisfies the one or more routing criteria.

4. The computer-implemented method of claim 1 , further comprising determining a weight based at least partly on a security constraint associated with the first implementation operation.

5. The computer-implemented method of claim 1 , further comprising generating a graph-based representation of the plurality of sequences of implementation operations.

6. The computer-implemented method of claim 5 , further comprising:
performing a weighted topological sort of the graph-based representation of the plurality of sequences of implementation operations; and
selecting the first sequence of implementation operations based at least partly on results of the weighted topological sort.

7. The computer-implemented method of claim 1 , further comprising:
causing presentation of a user interface representing the first sequence of implementation operations and a second sequence of implementation operations; and
receiving interaction data representing selection of the first sequence of implementation operations, wherein causing performance of the first sequence of implementation operations is performed in response to receiving the interaction data.

8. The computer-implemented method of claim 1 , wherein determining the plurality of sequences of implementation operations is based at least partly on dependency data regarding implementation operations to implement the change to the private network.

9. The computer-implemented method of claim 1 , wherein obtaining the policy data regarding the change comprises obtaining policy data regarding one of: addition of a segment, removal of a segment, modification to a segment property, addition of a route filter, or removal of a route filter.

10. A system comprising:
computer-readable memory storing executable instructions; and
one or more processors in communication with the computer-readable memory and programmed by the executable instructions to at least:
obtain policy data regarding a change to be implemented to a private network deployed on a cloud provider network;
determine a plurality of sequences of implementation operations, wherein individual implementation operations of the plurality of sequences of implementation operations comprise modifying at least one of a set of routes or a set of attachments associated with communication connections of the private network, wherein individual sequences of the plurality of sequences of implementation operations are configured to implement the change to the private network, and wherein each respective implementation operation of a first sequence of implementation operations of the plurality of sequences of implementation operations is associated with an expected time for the respective implementation operation to transition from a first state of the private network before performance of the respective implementation operation to a second state of the private network after performance of the respective implementation operation;
determine, based at least partly on a model of the private network representing application of a first implementation operation of the first sequence of implementation operations, that an intermediate state of the private network, between an initial state of the private network prior to performance of any implementation operation of the first sequence of implementation operations and an end state of the private network after performing a final implementation operation of the first sequence of implementation operations, satisfies one or more routing criteria; and
cause performance of the first sequence of implementation operations based at least partly on a total time, calculated by adding the expected time of each respective implementation operation of the first sequence of implementation operations, being lower than a total time of another sequence of implementation operations of the plurality of sequences of implementation operations, and on determining that the intermediate state satisfies of the one or more routing criteria.

11. The system of claim 10 , wherein the one or more processors are programmed by further executable instructions to determine a weight based on at least one of: the expected amount of time to perform the first implementation operation, or a security constraint associated with the first implementation operation.

12. The system of claim 10 , wherein the change to be implemented to the private network comprises one of: addition of a segment, removal of a segment, modification to a segment property, addition of a route filter, or removal of a route filter.

13. The system of claim 10 , wherein the one or more processors are programmed by further executable instructions to:
generate a graph-based representation of the plurality of sequences of implementation operations;
perform a weighted topological sort of the graph-based representation of the plurality of sequences of implementation op

Assignees

• Amazon Tech Inc

Inventors

• Qian Baihu
• Deb Bashuman
• Hsieh Justin Lin
• Dacosta Daniel William
• Matthews Nick
• Dawani Anoop
• Hashmi Omer
• Spendley Thomas Nguyen
• Heorhiadi Viktor

Classifications

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L45/42 Primary

  Centralised routing · CPC title

• H04L45/22 Primary

  Alternate routing · CPC title

• H04L12/4641

  Virtual LANs, VLANs, e.g. virtual private networks [VPN] (LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272) · CPC title

• H04L45/123

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title