EFFICIENT MACHINE LEARNING FOR NETWORK OPTIMIZATION

• US 20200136957A1
• Filed: 10/25/2018
• Published: 04/30/2020
• Est. Priority Date: 10/25/2018
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Inventors: Sanchez Charles, David, Stampa, Giorgio, Muntes-Mulero, Victor, Arias, Marta
• Granted Patent: US 10,666,547 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence
• CPC Class Codes: H04L 41/342 between virtual entities, e.g. orchestrators, SDN or NFV entities
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/021 Ensuring consistency of routing table updates, e.g. by using epoch numbers
• CPC Class Codes: H04L 45/08 Learning-based routing, e.g. using neural networks or artificial intelligence
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer

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.

Claims

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.

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 determining the one or more pivotal nodes from the set of pivotal nodes to be utilized in transmitting the first 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.

5. 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.

6. 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 first network traffic is performed in response to detecting within the network a traffic demand from the first host.

7. 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.

8. 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.

9. 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.

10. The computer-readable medium of claim 9, 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.

11. The computer-readable medium of claim 9, 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.

12. The computer-readable medium of claim 9, 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.

13. 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,

processing 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.

14. The apparatus of claim 13, 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.

15. The apparatus of claim 14 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 each of the multiple paths.

16. The apparatus of claim 13, wherein the instructions to determine the one or more pivotal nodes from the set of pivotal nodes to be utilized in transmitting the first 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.

17. The apparatus of claim 13, 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.

18. The apparatus of claim 13, wherein the instructions to determine the one or more pivotal nodes from the set of pivotal nodes to be utilized in transmitting the first network traffic are performed in response to detecting within the network a traffic demand from the first host.

19. The apparatus of claim 13, wherein the instructions to process the topology to generate the ranked list of nodes in the network comprises instructions to eliminate nodes from the topology which cannot be utilized for routing traffic.

20. The apparatus of claim 13, wherein the nodes in the network are routing devices, wherein the instructions to deploy the routing path to the network comprises instructions to define the routing path in a routing table and transmit the routing table to the routing devices.