Efficient machine learning for network optimization

Patent metadata

Field	Value
Publication number	US-10666547-B2
Application number	US-201816170218-A
Country	US
Kind code	B2
Filing date	Oct 25, 2018
Priority date	Oct 25, 2018
Publication date	May 26, 2020
Grant date	May 26, 2020

Abstract

An autonomous controller for SDN, virtual, and/or physical networks can be used to optimize a network automatically and determine new optimizations as a network scales. The controller trains models that can determine in real-time the optimal path for the flow of data from node A to B in an arbitrary network. The controller processes a network topology to determine relative importance of nodes in the network. The controller reduces a search space for a machine learning model by selecting pivotal nodes based on the determined relative importance. When a demand to transfer traffic between two hosts is detected, the controller utilizes an AI model to determine one or more of the pivotal nodes to be used in routing the traffic between the two hosts. The controller determines a path between the two hosts which comprises the selected pivotal nodes and deploys a routing configuration for the path to the network.

First claim

What is claimed is:

1. A method comprising:
processing a topology to generate a ranked list of nodes in a network;
selecting a set of pivotal nodes from the ranked list of nodes;
determining one or more pivotal nodes from the set of pivotal nodes to be utilized in transmitting network traffic from a first host to a second host;
generating a routing path between the first host and the second host that comprises the one or more pivotal nodes; and
deploying the routing path to the network
wherein determining the one or more pivotal nodes from the set of pivotal nodes to be utilized in transmitting the network traffic comprises:
providing, as input to a machine learning model, identifiers for the first host and the second host, a current amount of network traffic between the first host and the second host, and an additional amount of network traffic to be transmitted between the first host and the second host;
receiving, as output from the machine learning model, a weight for each of the set of pivotal nodes and combinations of the pivotal nodes; and
selecting the one or more pivotal nodes based, at least in part, on the weights.

2. The method of claim 1 , wherein generating the routing path between the first host and the second host that comprises the one or more pivotal nodes comprising:
identifying a shortest path between the first host and a first pivotal node of the one or more pivotal nodes, wherein the shortest path between the first host and the first pivotal node is a path in the topology which comprises a minimum number of nodes; and
identifying a shortest path between the first pivotal node and the second host in the topology.

3. The method of claim 2 further comprising, based on determining that there are multiple paths between the first host and the first pivotal node which qualify as the shortest path, selecting a path from the multiple paths based on at least one of random selection and performance metrics associated with each of the multiple paths.

4. The method of claim 1 , wherein the ranked list of nodes is based, at least in part, on at least one of a degree of each node in the topology, centrality of each node in the topology, and historical or projected traffic metrics for each node in the topology.

5. The method of claim 1 , wherein determining the one or more pivotal nodes from the set of pivotal nodes to be utilized in transmitting the network traffic is performed in response to detecting within the network a traffic demand from the first host.

6. The method of claim 1 , wherein processing the topology to generate the ranked list of nodes in the network comprises eliminating nodes from the topology which cannot be utilized for routing traffic.

7. The method of claim 1 , wherein the nodes in the network are routing devices, wherein deploying the routing path to the network comprises defining the routing path in a routing table and transmitting the routing table to the routing devices.

8. A non-transitory, computer-readable medium having instructions stored thereon that are executable by a computing device to perform operations comprising:
selecting a set of pivotal nodes from a topology for a network;
generating and training a machine learning model based, at least in part, on the topology and information related to performance and behaviors of the network;
providing, as input to the machine learning model, identifiers for a first host and a second host;
identifying one or more pivotal nodes from the set of pivotal nodes to be utilized in transmitting network traffic between the first host and the second host based, at least in part, on output from the machine learning model; and
generating a routing path between the first host and the second host that comprises the one or more pivotal nodes
wherein the instructions executable by a computing device to perform operations comprising providing, as input to the machine learning model, identifiers for the first host and the second host are performed in response to detecting within the network a traffic demand from the first host, wherein the input to the machine learning model further includes a current amount of traffic between the first host and the second host and an amount of traffic indicated in the traffic demand.

9. The computer-readable medium of claim 8 , wherein the instructions executable by a computing device to perform operations comprising selecting a set of pivotal nodes from a topology for a network comprise instructions executable by a computing device to perform operations comprising generating a ranking of nodes in the topology based, at least in part, on at least one of a degree of each node in the topology, centrality of each node in the topology, and historical or projected traffic metrics for each node in the topology.

10. The computer-readable medium of claim 8 , wherein the instructions executable by a computing device to perform operations comprising generating the routing path between the first host and the second host that comprises the one or more pivotal nodes comprises instructions executable by a computing device to perform operations comprising:
identifying a shortest path between the first host and a first pivotal node of the one or more pivotal nodes, wherein the shortest path between the first host and the first pivotal node is a path in the topology which comprises a minimum number of nodes; and
identifying a shortest path between the first pivotal node and the second host in the topology.

11. An apparatus comprising:
a processor; and
a computer-readable medium having instructions stored thereon that are executable by the processor to cause the apparatus to,
process a topology to generate a ranked list of nodes in a network; select a set of pivotal nodes from the ranked list of nodes;
determine one or more pivotal nodes from the set of pivotal nodes to be utilized in transmitting network traffic from a first host to a second host;
generate a routing path between the first host and the second host that comprises the one or more pivotal nodes; and
deploy the routing path to the network

wherein the instructions to determine the one or more pivotal nodes from the set of pivotal nodes to be utilized in transmitting the is-network traffic comprises instructions to:
provide, as input to a machine learning model, identifiers for the first host and the second host, a current amount of network traffic between the first host and the second host, and an additional amount of network traffic to be transmitted between the first host and the second host;
receive, as output from the machine learning model, a weight for each of the set of pivotal nodes and combinations of the pivotal nodes; and
select the one or more pivotal nodes based, at least in part, on the weights.

12. The apparatus of claim 11 , wherein the instructions to generate the routing path between the first host and the second host that comprises the one or more pivotal nodes comprises instructions to:
identify a shortest path between the first host and a first pivotal node of the one or more pivotal nodes, wherein the shortest path between the first host and the first pivotal node is a path in the topology which comprises a minimum number of nodes; and
identify a shortest path between the first pivotal node and the second host in the topology.

13. The apparatus of claim 12 further comprising instructions to, based on a determination that there are multiple paths between the first host and the first pivotal node which qualify as the shortest path, select a path from the multiple paths based on at least one of random selection and performance metrics associated with eac

Assignees

• Ca Inc

Inventors

• Sanchez Charles David
• Stampa Giorgio
• Muntés-Mulero Victor
• Arias Marta

Classifications

• H04L45/124

  using a combination of metrics · CPC title

• H04L45/14

  Routing performance; Theoretical aspects · CPC title

• H04L45/021

  Ensuring consistency of routing table updates, e.g. by using epoch numbers · CPC title

• H04L45/64

  using an overlay routing layer · CPC title

• H04L45/22

  Alternate routing · CPC title