EP-4289117-B1 - BEST PATH COMPUTATION OFFLOAD IN A NETWORK COMPUTING ENVIRONMENT

Inventors

• PAI, NALINAKSH
• XU, FENG
• ARIES, Ebben
• AYYANGAR, ARTHI
• PATEL, KEYUR

Dates

Publication Date

20260513

Application Date

20210203

Claims (9)

1. A method comprising: 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; receiving, by a border gateway protocol, BGP, instance executing on the device, a Network Layer Reachability Information, NLRI, from a neighbor of the device; holding, by the BGP instance, the NLRI in a queue; while holding the NLRI in the queue, forwarding, by the BGP instance, a message containing the NLRI and all paths learnt so far and their attributes to the best path controller; receiving, by the best path controller, the message containing the NLRI and all paths learnt so far from the device; processing, by the best path controller, a best path computation to identify one or more best paths based on the message containing the NLRI and all paths learnt so far and their attributes such that processing of the best path computation is offloaded from the device to the best path controller; sending, by the best path controller the NLRI and its respective one or more best paths to the device; and in response to receiving the NLRI and its respective the one or more best paths, dequeuing, by the BGP instance, the NLRI from the queue and re-queuing, by the BGP instance, the NLRI to either a Routing Information Base, RIB installation queue if the NLRI needs to be installed in a RIB or to an update generation queue for announcing it to BGP neighbors.
2. The method of claim 1, wherein the device is a router or a switch.
3. The method of claim 1, further comprising 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.
4. The method of claim 1, wherein: receiving the message containing the NLRI and all paths learnt so far and their attributes from the device comprises asynchronously receiving a plurality of messages from the device, the plurality of messages including the message containing the NLRI and all paths learnt so far and their attributes; and performing the best path computation comprises performing the best path computation on a most recent version of Network Layer Reachability Information, NLRI, based on the plurality of messages.
5. The method of claim 4, wherein each of the plurality of messages comprises a version number field comprising a unique identification across all messages received from the device for a single message of the plurality of messages.
6. A system comprising: a device in a network, wherein the device is configured to: receive, by a border gateway protocol, BGP, instance executing on the device, a Network Layer Reachability Information, NLRI, from a neighbor of the device; hold, by the BGP instance, the NLRI in a queue; and while holding the NLRI in the queue, forward, by the BGP instance, a message containing the NLRI and all paths learnt so far and their attributes to a best path controller in communication with the device; and the best path controller in communication with the device, the best path controller comprising a processor configurable to execute instructions stored in non-transitory computer readable storage media, the instructions comprising: storing in memory a listing of a plurality of paths learnt by the device, wherein each of the plurality of paths is a route for transmitting data from the device to a destination device; receiving the message containing the NLRI and all paths learnt so far and their attributes from the device; processing a best path computation to identify one or more best paths based on the message containing the NLRI and all paths learnt so far and their attributes such that processing of the best path computation is offloaded from the device to the best path controller; and sending the NLRI and its respective one or more best paths to the device; wherein the device is further configured to, in response to receiving the NLRI and its respective the one or more best paths, dequeue, by the BGP instance, the NLRI from the queue and re-queue, by the BGP instance, the NLRI to either a Routing Information Base, RIB, installation queue if the NLRI needs to be installed in a RIB or to an update generation queue for announcing the NLRI to BGP neighbors.
7. The system of claim 6, wherein the device is a router or a switch.
8. The system of claim 6, 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.
9. The system of claim 6, wherein the instructions are such that: receiving the message containing the NLRI and all paths learnt so far and their attributes from the device comprises asynchronously receiving a plurality of messages from the device, the plurality of messages including the message containing the NLRI and all paths learnt so far and their attributes; and performing the best path computation comprises performing the best path computation on a most recent version of the plurality of messages.

Description

TECHNICAL FIELD The disclosure relates to computing networks and particularly relates to best path computations for communications between networked devices. BACKGROUND Network computing is a means for multiple computers or nodes to work together and communicate with one another over a network. There exist wide area networks (WAN) and local area networks (LAN). Both wide and local area networks allow for interconnectivity between computers. Local area networks are commonly used for smaller, more localized networks that may be used in a home, business, school, and so forth. Wide area networks cover larger areas such as cities and can even allow computers in different nations to connect. Local area networks are typically faster and more secure than wide area networks, but wide area networks enable widespread connectivity. Local area networks are typically owned, controlled, and managed in-house by the organization where they are deployed, while wide area networks typically require two or more constituent local area networks to be connection over the public Internet or by way of a private connection established by a telecommunications provider. Local and wide area networks enable computers to be connected to one another and transfer data and other information. For both local and wide area networks, there must be a means to determine a path by which data is passed from one compute instance to another compute instance. This is referred to as routing. Routing is the process of selecting a path for traffic in a network or between or across multiple networks. The routing process usually directs forwarding on the basis of routing tables which maintain a record of the routes to various network destinations. Routing tables may be specified by an administrator, learned by observing network traffic, or built with the assistance of routing protocols. Small networks may use manually configured routing tables to determine how information should travel from one computer to another computer. A routing table may include a listing of "best paths" indicating the most efficient or most desirable paths between a starting computer and a final destination computer. Larger networks, including networks connected to the public Internet, may rely on complex topologies that can change rapidly such that the manual construction of routing tables is unfeasible. Dynamic routing attempts to solve this problem by constructing routing tables automatically based on information carried by routing protocols. Dynamic routing enables a network to act nearly autonomously in avoiding network failures and blockages. There exist multiple routing protocols that provide rules or instructions for determining best paths between networked device. Examples of dynamic routing protocols and algorithms include Routing Information Protocol (RIP), Open Shortest Path First (OSPF), Intermediate System - Intermediate System (IS-IS), and Border Gateway Protocol (BGP). In some instances, path selection involves applying a routing metric to multiple routes to select or predict the best route. Most routing algorithms use only one network path at a time. Multiple path routing techniques enable the use of multiple alternative paths. In computer networks, a routing algorithm may be used to predict the best path between two compute instances. The routing algorithm may be based on multiple factors such as bandwidth, network delay, hop count, path cost, load, maximum transfer unit, reliability, and communication cost. The routing table stores a listing of the best paths. A topological database may store a list of the best paths and may further store additional information. In some networks, routing is complicated by the fact that no single entity is responsible for selecting best paths. Instead, multiple entities are involved in selecting best paths or event portions of a single path. In the context of computer networking over the Internet, the Internet is partitioned into autonomous systems (AS) such as Internet Service Providers (ISPs). Each autonomous system controls routes involving its network. Autonomous system-level paths are selected based on the Border Gateway Protocol (BGP). Each autonomous system-level path includes a sequence of autonomous systems through which packets of information flow to travel from one compute instance to another compute instance. Each autonomous system may have multiple paths from which to choose that are offered by neighboring autonomous systems. In the new age of software-defined networks, there is an increased demand for greater ability to control and customize behaviors within a network. The BGP was designed to facilitate the use of policies to control selection of best paths, attributes, and advertisements. However, the best path algorithm itself is standardized and fixed in nature and there remains a demand to implement further customizability on top of the BGP. In light of the foregoing, disclosed herein are systems, methods, and devi