Assigning routing paths based on interior gateway protocol metric optimization

Patent metadata

Field	Value
Publication number	US-11601336-B2
Application number	US-202117323464-A
Country	US
Kind code	B2
Filing date	May 18, 2021
Priority date	May 18, 2021
Publication date	Mar 7, 2023
Grant date	Mar 7, 2023

Abstract

Methods, systems, and apparatus, including computer-readable storage media, optimizing interior gateway protocol (IGP) metrics using reinforcement learning (RL) for a network domain. The system can receive a topology (G) of a network domain, a set of flows (F), and an objective function. The system can optimize, using reinforcement learning, the objective function based on the received topology and the one or more flows F. The system can determine updated IGP metrics based on the optimization of the objective function. The IGP metrics for the metric domain may be updated with the updated IGP metrics.

First claim

The invention claimed is:

1. A method for tuning IGP metrics for a network domain, comprising:
receiving, by one or more processors, a topology (G) of a network and a set of flows (F);
receiving, by the one or more processors, an objective function;
optimizing, by the one or more processors using reinforcement learning, the objective function based on the received topology and the one or more flows F;
determining, by the one or more processors, updated IGP metrics based on the optimization of the objective function; and
assigning, by the one or more processors, routing paths between nodes on the network based on the updated IGP metrics.

2. The method of claim 1 , wherein the topology G equals (V, E), where V is a set of nodes on the domain network and E is the set of edges between each node in the set of nodes on the domain network.

3. The method of claim 1 , wherein each of one or more flows F equals {fj}, j=1 . . . |F|, where j is the index of the flow and each flow fj is a tuple comprising (src_j, dst_j, demand_j, SLO_j), where src_j and dst_j are the source and destination node, respectively, demand_j is the size of the flow, and SLO_j is the service level objective (SLO) requirement for the flow.

4. The method of claim 1 , further comprising:
determining, by a routing simulator, a network utility for each failure state in the set of edges E.

5. The method of claim 4 , wherein optimizing the objective function is further based on the network utility of each failure state determined by the routing simulator.

6. The method of claim 1 , further comprising updating the IGP metrics for the network domain with the updated IGP metrics.

7. A system comprising:
one or more processors configured to:
receive a topology (G) of a network domain and a set of flows (F);
receive an objective function;
optimize, using reinforcement learning, the objective function based on the received topology and the one or more flows F;
determine updated IGP metrics based on the optimization of the objective function; and
assign routing paths between nodes on the network based on the updated IGP metrics.

8. The system of claim 7 , wherein the topology G equals (V, E), where V is a set of nodes on the network domain and E is the set of edges between each node in the set of nodes on the network domain.

9. The system of claim 7 , wherein each of one or more flows F equals {fj}, j=1 . . . |F↑, where j is the index of the flow and each flow fj is a tuple comprising (src_j, dst_j, demand_j, SLO_j), where src_j and dst_j are the source and destination node, respectively, demand_j is the size of the flow, and SLO_j is the service level objective (SLO) requirement for the flow.

10. The system of claim 7 , wherein the one or more processors are further configured to:
determine a network utility for each failure state.

11. The system of claim 10 , wherein optimizing the objective function is further based on the determined network utility of each failure state.

12. The system of claim 10 , wherein the one or more processors are further configured to update the IGP metrics for the network domain with the updated IGP metrics.

13. A non-transitory computer readable medium storing instruction, that when executed by one or more processors, cause the one or more processors to:
receive a topology (G) of a network domain and a set of flows (F);
receive an objective function;
optimize, using reinforcement learning, the objective function based on the received topology and the one or more flows F
determine updated IGP metrics based on the optimization of the objective function; and
assign routing paths between nodes on the network based on the updated IGP metrics.

14. The non-transitory computer readable medium of claim 13 , wherein the topology G equals (V, E), where V is a set of nodes on the network domain and E is the set of edges between each node in the set of nodes on the network domain.

15. The non-transitory computer readable medium of claim 13 , wherein each of one or more flows F equals {fj}, j=1 . . . |F↑, where j is the index of the flow and each flow f_j is a tuple comprising (src_j, dst_j, demand_j, SLO_j), where src_j and dst_j are the source and destination node, respectively, demand_j is the size of the flow, and SLO_j is the service level objective (SLO) requirement for the flow.

16. The non-transitory computer readable medium of claim 13 , wherein the instructions further cause the one or more processors to determine a network utility for each failure state.

17. The non-transitory computer readable medium of claim 16 , wherein optimizing the objective function is further based on the network utility of each failure state by the routing simulator.

18. The non-transitory computer readable medium of claim 1 , wherein the instructions further cause the one or more processors to:
update the IGP metrics for the network domain with the updated IGP metrics.

Assignees

• Google Llc

Inventors

• Wen Min
• Jiang Wenjie
• Sharma Anurag
• Johnston Matthew
• Alvizu Gomez Rodolfo Enrique

Classifications

• H04L45/08

  Learning-based routing, e.g. using neural networks or artificial intelligence · CPC title

• H04L41/12 Primary

  Discovery or management of network topologies · CPC title

• H04L45/02 Primary

  Topology update or discovery · CPC title

• H04L41/14

  Network analysis or design · CPC title

• H04L45/036

  Updating the topology between route computation elements, e.g. between OpenFlow controllers · CPC title