Best path computation offload in a network computing environment

Patent metadata

Field	Value
Publication number	US-11121963-B2
Application number	US-201916672964-A
Country	US
Kind code	B2
Filing date	Nov 4, 2019
Priority date	Nov 4, 2019
Publication date	Sep 14, 2021
Grant date	Sep 14, 2021

Abstract

Systems, methods, and devices for offloading best path computations in a networked computing environment. A method includes storing in memory, by a best path controller, a listing of a plurality of paths learnt by a device, wherein each of the plurality of paths is a route for transmitting data from the device to a destination device. The method includes receiving, by the best path controller, a message from the device. The method includes processing, by the best path controller, a best path computation to identify one or more best paths based on the message such that processing of the best path computation is offloaded from the device to the best path controller. The method includes sending the one or more best paths to the device.

First claim

What is claimed is:

1. A method comprising:
storing in memory, by a best path controller, a listing of a plurality of paths learnt by a plurality of devices in communication with the best path controller, wherein each of the plurality of devices is a switch or router, and wherein each of the plurality of paths is a route for transmitting data from one device of the plurality of devices to a destination device;
asynchronously receiving, by the best path controller, a plurality of Network Layer Reachability Information (NLRI) messages from a first device of the plurality of devices, wherein each of the plurality of NLRI messages comprises a version number;
processing, by the best path controller, a best path computation to identify one or more best paths based on the plurality of NLRI messages such that processing of the best path computation is offloaded from each of the plurality of devices to the best path controller; and
sending, by the best path controller, the one or more best paths to the first device with a latest version number associated with an NLRI;
wherein the best path controller comprises a single software package for optimizing the best path computation for each of the plurality of devices.

2. The method of claim 1 , wherein the best path controller comprises a router or a switch executing the single software package for optimizing the best path computation for each of the plurality of devices.

3. The method of claim 1 , wherein each of the plurality of devices in communication with the best path controller is running the Border Gateway Protocol (BGP).

4. The method of claim 1 , further comprising updating, by the best path controller, next hops for any of the paths in the listing of the plurality of paths based on the one or more best paths calculated by the best path controller.

5. The method of claim 1 , wherein
processing the best path computation comprises processing a most recent version of an NLRI prefix associated with the plurality of NLRI messages received from the first device.

6. The method of claim 5 , wherein each of the plurality of NLRI messages comprises a version number field comprising a unique identification across all messages received from the first device for a single NLRI.

7. The method of claim 1 , further comprising,
reperforming the best path computation in response to a policy change;
generating a result message comprising one or more best paths based on the reperforming the best path computation; and
returning the result message to the first device.

8. The method of claim 1 , further comprising:
receiving, by the best path controller, a next hop reachability update to a path within the listing of the plurality of paths learnt by the device;
reperforming the best path computation in response to receiving the next hop reachability update;
generating a result message comprising one or more best paths based on the reperforming the best path computation; and
sending the result message to the first device.

9. The method of claim 1 , further comprising:
determining the first device has restarted;
retaining, by the best path controller, the listing of the plurality of paths learnt by the first device;
marking each path within the listing of the plurality of paths learnt by the first device as stale in response to determining the first device has restarted;
receiving a refreshed path from the first device in response to the first device relearning that path; and
purging from the listing of the plurality of paths a stale path corresponding with the refreshed path.

10. The method of claim 1 , wherein the best path computation is customized for the first device and other devices within the first device's network.

11. A system comprising:
a first device in a network comprising a plurality of devices, wherein each of the plurality of devices is a switch or router;
a best path controller in communication with each of the plurality of devices, wherein the best path controller comprises one or more processors for executing configurable to execute instructions stored in non-transitory computer readable storage media, wherein the instructions comprise a single software package for optimizing best path computations for each of the plurality of devices in the network, wherein the instructions comprise:
storing in memory a listing of a plurality of paths learnt by the plurality of devices in communication with the best path controller, wherein each of the plurality of paths is a route for transmitting data from one device of the plurality of devices to a destination device;
asynchronously receiving a plurality of Network Layer Reachability Information (NLRI) messages from the first device of the plurality of devices, wherein each of the plurality of NLRI messages comprises a version number;
processing a best path computation to identify one or more best paths based on the plurality of NLRI messages such that processing of the best path computation is offloaded from each of the plurality of devices to the best path controller; and
sending the one or more best paths to the first device with a latest version number associated with an NLRI.

12. The system of claim 11 , wherein the best path controller comprises a router or a switch executing the single software package for optimizing the best path computation for each of the plurality of devices in the network.

13. The system of claim 11 , wherein the instructions further comprise updating next hops for any of the paths in the listing of the plurality of paths based on the one or more best paths calculated by the best path controller.

14. The system of claim 11 , wherein the instructions are such that
processing the best path computation comprises processing a most recent version of an NLRI prefix associated with the plurality of NLRI messages received from the first device.

15. The system of claim 11 , wherein the instructions further comprise:
reperforming the best path computation in response to a policy change;
generating a result message comprising one or more best paths based on the reperforming the best path computation; and
returning the result message to the first device.

16. Non-transitory computer readable storage media storing instructions for execution by one or more processors, the instructions comprising:
storing in memory a listing of a plurality of paths learnt by a plurality of devices in communication with a best path controller, wherein each of the plurality of devices is a switch or a router, and wherein each of the plurality of paths is a route for transmitting data from one device of the plurality of devices to a destination device;
asynchronously receiving a plurality of Network Layer Reachability Information (NLRI) messages from a first device of the plurality of devices, wherein each of the plurality of NLRI messages comprise a version number;
processing a best path computation to identify one or more best paths based on the plurality of NLRI messages such that processing of the best path computation is offloaded from each of the plurality of devices to the best path controller; and
sending the one or more best paths to the first device with a latest version number associated with an NLRI;
wherein the best path controller comprises a single software package for optimizing the best path computation for each of the plurality of devices.

17. The non-transitory computer readable storage media of claim 16 , wherein the instructions further comprise:
reperforming the best path computation in response to a policy change;
generating a result mes

Assignees

• Arrcus Inc

Inventors

• Pai Nalinaksh
• Xu Feng
• Aries Ebben
• Ayyangar Arthi
• Patel Keyur

Classifications

• H04L45/24 Primary

  Multipath · CPC title

• H04L45/70

  Routing based on monitoring results · CPC title

• H04L45/122 Primary

  by minimising distances, e.g. by selecting a route with minimum of number of hops · CPC title

• H04L45/58

  Association of routers · CPC title

• H04L45/42

  Centralised routing · CPC title