TWI868310B - Best path computation offload in a network computing environment and non-transitory computer readable storage media - Google Patents

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.

Description

Optimal path computing offloading system and method for network computing environment and non-transient computer readable storage medium

The present disclosure relates to a network computing technology, and more particularly to a technology involving optimal path computing for communication between network devices.

Network computing is a method of communicating and coordinating with multiple computers or nodes over a network. There are types of so-called wide area networks and local area networks. Both allow computers to connect to each other internally. Local area networks are usually used for smaller, more regionalized networks such as homes, companies, and schools. Wide area networks cover larger areas such as cities and can even allow computers in different countries to connect to each other. Local area networks are generally faster and more secure than wide area networks, but wide area networks can provide widespread connectivity. A LAN is usually owned, controlled, and managed by the organization responsible for its deployment, while a WAN usually requires two or more LANs to be connected via the public Internet or a dedicated connection established by a telecommunications provider.

Local and wide area networks allow computers to connect to each other and transfer data and other information. In between, there must be a way to determine a path so that data can be quickly transferred from one compute instance to another. This is called routing. Routing is the process of selecting a path for traffic to take on a network or between two or more networks. This routing process is usually done by direct forwarding by maintaining routing records in a routing table that can lead to different network destinations. The routing table can be specified by the administrator, learned by observing network traffic, or established with the help of routing protocols.

Small networks may use manually configured routing tables to determine how information moves from one computer to another. Routing tables may include a table of "best paths" that indicate the most efficient or optimal path between a source computer and a final destination computer. Large networks, including those connected to the public Internet, may rely on rapidly changing and complex network topologies, making manual construction of routing tables impractical. Dynamic routing attempts to solve this problem by automatically constructing routing tables based on information from routing protocols. Dynamic routing allows the network to operate in a nearly autonomous manner to avoid network failures and blockages. There are several routing protocols that provide rules or instructions for determining the best paths between network devices. Examples of dynamic routing protocols and algorithms include Routing Information Protocol (RIP), Open Shortest Path First (OSPF), Intermediate System to 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 a single network path at a time. Multipath routing techniques allow the use of multiple alternative paths. In computer networks, routing algorithms are used to predict the best path between two computing entities. Routing algorithms may be based on a variety of factors, such as bandwidth, network latency, hop count, path cost, load, maximum transmission unit, reliability, and communication cost. A routing table stores a list of the best paths. A topology database may store a list of the best paths and may also store other information.

In some networks, routing is actually quite complex because no single entity is responsible for choosing the best path. Instead, many entities are used to choose the best path or event portions of a single path. In the context of computer networking via the Internet, the Internet is divided into multiple autonomous systems (AS) such as Internet service providers (ISPs). Each AS controls routing in its network. Autonomous system-level paths are selected based on BGP. Each AS-level path consists of a sequence of autonomous systems through which packets of a data flow can be sent from one computing entity to another. Each autonomous system may have multiple paths provided by neighboring autonomous systems that it can use to choose.

In the new era of software-defined networks, there is a growing need for greater control and customization of network behavior. BGP was designed to facilitate the use of policies that control the selection of best paths, attributes, and advertisements. However, the best path algorithms themselves are standardized and fixed in nature, so there is a need for more customizability on top of BGP.

In view of the foregoing, the present disclosure provides systems, methods, and apparatus for offloading optimal path decisions to an external entity that is free to implement custom algorithms to determine the most ideal path between one computing entity and another computing entity.

The present invention proposes an optimal path calculation offloading method for a network computing environment, comprising the following steps: storing a list of multiple paths learned by a device in a memory by an optimal path controller, wherein each of the multiple paths is a path used by the device to transmit data to a destination device; receiving a message from the device by the optimal path controller; performing an optimal path calculation by the optimal path controller to find one or more optimal paths based on the message, so that the execution of the optimal path calculation is offloaded from the device to the optimal path controller; and transmitting the one or more optimal paths to the device.

In addition, the present invention also proposes an optimal path computing offloading system for a network computing environment, comprising: a device in a network, wherein the device is configured to transmit data from the device to a destination device; an optimal path controller, communicating with the device, the optimal path controller comprising a processor, configured to execute a plurality of instructions stored in a non-transient computer-readable storage medium, the plurality of instructions comprising: using the optimal path controller to transfer a plurality of paths learned by the device to a destination device; A list is stored in a memory, wherein each of the plurality of paths is a path used by the device to transmit data to a destination device; a message from the device is received by the optimal path controller; a best path calculation is performed by the best path controller to find one or more best paths based on the message, so that the performance of the best path calculation is offloaded from the device to the best path controller; and the one or more best paths are transmitted to the device.

At the same time, the present invention proposes a non-transitory computer-readable storage medium that stores multiple instructions for providing one or more processors to execute, the multiple instructions including: storing a list of multiple paths learned by a device in a memory by an optimal path controller, wherein each of the multiple paths is a path used by the device to transmit data to a destination device; receiving a message from the device by the optimal path controller; performing an optimal path operation by the optimal path controller to find one or more optimal paths based on the message, so that the execution of the optimal path operation is offloaded from the device to the optimal path controller; and transmitting the one or more optimal paths to the device.

The device is either a router or a switch and runs the Border Gateway Protocol (BGP).

The best path operation is customized for the device and other devices in the network to which the device belongs.

The following drawings are provided to describe various non-limiting and non-exhaustive embodiments of the present disclosure, wherein the same reference numerals in different drawings refer to the same elements unless otherwise specified. The following description and drawings will help to understand the advantages of the present application disclosure:

The present disclosure is primarily about systems, methods, and apparatus for improving routing of data transmission. In the new era of software-defined networks, there is an increasing need for computer networks to have better control and the ability to customize their behavior. The disclosed systems, methods, and apparatus are used to offload optimal path decisions to an external entity. This external entity is free to implement custom algorithms to determine the most ideal path to send data from one computing entity to another computing entity over the Internet.

The disclosed embodiments may be deployed to determine the best path for transmitting data from a first router to a destination router through the Internet. In one disclosed embodiment, a best path controller is provided as a service to an external entity of the BGP standardized algorithm for determining routing paths. The best path controller may be located on the same host as the BGP is executed. Alternatively, the best path controller may be located on a different host and provide services to one or more BGP entities.

A BGP entity is a software daemon that routes information in a network. A BGP entity can run on a switch, a router, or a virtual environment that simulates a switch or router (for example, a virtual machine on a host device). At a high level, the BGP entity passes all the paths learned for a prefix to the best path controller. The best path controller responds with a set of best paths from these paths. The best path controller is allowed to modify the "next-hop" and attributes of any path. Once the best path is received, the BGP entity will update the local Routing Information Base (RIB) and broadcast the best path to its neighbors.

In one embodiment, a method is implemented by a best path controller. This method can offload best path calculations from individual devices (e.g., routers and switches) that execute BGP entities to the best path controller. The method includes storing, by the best path controller, a list of multiple paths learned by a device, which are routes for transmitting information from the device to a destination device. The method includes receiving, by the best path controller, a message from the device. In one embodiment, the message is a Network Layer Reachability Information message. The method includes performing, by the best path controller, a best path calculation based on the message to determine one or more best paths. The method includes transmitting the one or more paths to the device whereby processing of best path calculation is offloaded from the device to the best path controller.

A switch can be thought of as a switching hub, bridge hub, or MAC (Media Access Control) bridge that establishes a network. Most internal networks use switches to connect computers, printers, phones, cameras, lights, and servers within a building or campus. Switches provide services like controllers to allow network devices to communicate with each other efficiently. Switches connect devices on a computer network by switching packets to receive, process, and forward data to the destination device. A network switch is like a multi-port network bridge that uses hardware addresses to process and forward data in the data link layer (layer 2) of the Open Systems Interconnection model. Some switches can process data at the network layer (layer 3) by adding additional routing capabilities. These switches are commonly known as layer-3 switches or multilayer switches.

Routers connect networks. Switches and routers perform similar functions, but each has different unique functions in a network. A router is a network device used to forward data packets within a computer network. Routers perform traffic directing functions on the Internet. Data sent over the Internet, such as web pages, emails, or other forms of information, is sent in the form of data packets. Packets are usually sent from one router to another in a network that is built as an internetwork (such as the Internet) until the packet reaches the destination node. Routers usually connect two or more data lines from different networks. When a data packet comes in from one of the data lines, the router reads the network address information in the packet to determine its final destination. The router then uses information from its routing table or routing policy to direct the packet to the next network on its journey. A BGP interlocutor is a router that supports the Border Gateway Protocol.

Routing is a type of network management that helps improve Internet connectivity and reduce bandwidth costs and overall Internet operations. Some routing services include a set of hardware-based and software-based products and services that work together to improve overall Internet efficiency and properly tune the use of available Internet bandwidth at the lowest cost. Routing can be successful in scenarios where a network or autonomous system obtains Internet bandwidth from multiple providers. Routing can help choose the best path for data transmission.

Some Internet communication systems are very large, enterprise-grade networks with thousands of processing nodes. These thousands of processing nodes share bandwidth from multiple Internet Service Providers (ISPs) and are capable of handling significant Internet traffic. Such systems are very complex and must be configured appropriately to achieve acceptable Internet performance. If the system is not properly configured for optimal data transfer, Internet access speeds will be reduced and the system will experience high bandwidth consumption and traffic. To solve this problem, a series of services are used to remove or reduce these problem points. This series of services is called routing control.

An embodiment of a routing control mechanism is composed of hardware and software. The routing control mechanism monitors all outgoing traffic through the connection with the Internet service provider. The routing control mechanism helps to select the best path for efficient data transmission. The routing control mechanism can calculate the performance and efficiency of all network service providers and select the Internet service provider with the best performance in the application area. The routing control device can be configured according to defined parameters such as cost, performance and bandwidth.

An algorithm known to determine the best path for data transmission is called Border Gateway Protocol (BGP). BGP is a path-vector protocol that provides routing information for autonomous systems on the Internet. When BGP is configured incorrectly, it can cause disruptions in availability and security. Furthermore, modified BGP routing information can allow attackers to redirect large amounts of traffic to certain routers before reaching the originally intended destination. The BGP best path algorithm can be implemented to determine the best path and built into the IP routing table (Internet Protocol routing table) for traffic forwarding. BGP routers can be configured to accept multiple paths to the same destination.

The BGP Best Path Algorithm will first designate a first legal path as the current best path. The BGP Best Path Algorithm will then compare this best path to the next path in the list until all legal paths in the list are compared. The list provides the rules used to determine the best path. For example, the list may include indicators indicating the preferred path with the highest weight, the preferred path with no local preference, the preferred path that originates locally through the network or integrates BGP, the shortest preferred path, the preferred path with the lowest multi-exit discriminator, and so on. The BGP Best Path selection process can be customized.

In the context of BGP routing, each routing domain is called an autonomous system (AS). BGP helps choose a route to connect two routing domains through the Internet. BGP typically chooses the path that passes through the fewest autonomous systems, called the shortest AS path. In one implementation, once BGP is operational, a router will extract the Internet routing list from BGP neighbors (possibly ISPs). BGP will then check the routing list to find the shortest AS path. These routes may be entered into the router's routing table. Generally speaking, a router will choose the shortest path to an AS. BGP uses path attributes to decide how to route traffic to a specific network.

However, there are many known issues with BGP. In some cases, the growth of routing tables is a significant problem. For example, if a user decides to deaggregate a single /16 network, the user may begin advertising new routes. When this happens, every router on the Internet will receive each new route. Users may feel pressure to aggregate or merge multiple routes into a single advertisement. In addition, there is the concern that users will "broadcast the Internet." If a customer of a large Internet Service Provider (ISP) chooses to advertise everything, and the ISP accepts the route, all Internet traffic will be sent to this small customer. In addition, BGP has mechanisms to suppress unreliable routes. Routes that flap, or come and go, are defined as unreliable. If routes fluctuate too frequently, the load on all Internet routes will increase each time a route disappears and reappears.

Furthermore, in the age of software-defined networking, operators require greater ability to control and customize the behavior of the network. The BGP protocol is designed to facilitate the use of policies that control the selection of best paths, attributes, and advertisements. However, the best path algorithm itself is standardized and essentially fixed. In view of this, disclosed herein are systems, methods, apparatus, and means for BGP to offload best path decision making to an external entity that is free to implement a custom algorithm to achieve these goals. This external entity, referred to herein as a Best Path Controller (BPC), can be collocated on the same host that executes BGP, or on a different host that provides services to one or more BGP entities.

In one embodiment, the BGP entity can be implemented as a BGP speaker on a switch or router. At a high level, the BGP entity transmits all the paths learned for prefixes to the best path controller. The best path controller responds with a set of best paths from these paths. The best path controller is allowed to modify the "next-hop" and attributes in any path. Once the best path is received, the BGP entity will update the local Routing Information Base (RIB) and broadcast the best path to its neighbors.

In order to promote the understanding of the principles of the disclosed content, reference numbers will be used from now on in the embodiments described in the drawings and specific language will be used for description. It should be understood that there is no intention to limit the scope of the disclosure. As long as a person is familiar with the relevant technical field and can master the content of the disclosure, any selection or further modification of the inventive features described here, and any additional application of the disclosed principles described here, should be regarded as within the scope of the protection claimed by the disclosure.

Before disclosing the structures, systems and methods and descriptions, it should be understood that the present disclosure is not limited to the specific structures, configurations, processing steps and materials disclosed, as these structures, configurations, processing steps and materials may vary. It should also be understood that the terminology used herein is only for the purpose of describing specific embodiments and is not intended to be limiting, as the scope of the present disclosure will be limited only to the scope of the attached patents and their equivalents.

In describing and claiming the subject matter of this disclosure, the following terms will be used in accordance with the definitions below.

It should be noted that when used in the specification and the appended patent claims, the singular forms "a", "an", and "the" include plural referents unless the context clearly states otherwise.

When used, the terms “comprising,” “including,” “containing,” “characterized by,” and grammatical equivalents thereof are intended to be inclusive or open-ended terms and do not exclude additional, unrecited elements or method steps.

When used, "consisting of" and grammatically equivalent phrases exclude from the scope of the patent any elements or steps not expressly specified.

When used, the phrase “consisting essentially of” and grammatically equivalent phrases limit the scope of the patent to the specified materials or steps and to those materials or steps that do not materially affect the basic and novel characteristics of the claimed disclosure.

Now please refer to the drawings, "Figure 1" illustrates a system 100 for connecting devices to the Internet. System 100 includes multiple local area networks 110 connected through a switch 106. Each of the local area networks 110 can be connected to each other through the public Internet through a router 112. In the example system 100 illustrated in "Figure 1", there are two local area networks 110. However, it should be understood that there may be many local area networks 110 connected to each other through the public Internet. Each local area network 110 includes multiple computing devices 108 connected to each other through a switch 106. The computing devices 108 may include, for example: desktop computers, laptops, printers, servers, and the like. The local area network 110 can communicate with other networks through the public Internet through a router 112. The router 112 connects multiple networks to each other. The router 112 is connected to the Internet service provider 102. The Internet service provider 102 is further connected to one or more network service providers 104. The network service provider 104 communicates with other local network service providers 104 as shown in "Figure 1".

The switch 106 connects devices in the local area network 110 by receiving, processing, and forwarding data to a destination device through packet switching. The switch 106 can be configured, for example, to receive data from a computer to be provided to a printer. The switch 106 can receive data, process data, and transmit data to a printer. The switch 106 can be a layer-1 switch, a layer-2 switch, a layer-3 switch, a layer-4 switch, a layer-7 switch, and the like. A layer-1 network device is only responsible for transmitting data but is not responsible for managing any traffic passing through. An example of a layer-1 network device is an Ethernet hub. Layer 2 network devices are multi-port devices that use hardware addresses to process and forward data at the data link layer (Layer 2). Layer 3 switches can perform some or all of the functions of a typical router. However, some network switches are limited to supporting only a single type of physical network, usually Ethernet, while routers may support multiple physical network types on different ports.

The router 112 is a network device used to forward data packets between computer networks. In the system 100 shown in FIG. 1 , the router 112 is used to forward data packets between local area networks 110. However, the router 112 may not be used for forwarding data packets between local area networks 110, but may be used to forward data packets between wide area networks, etc. The router 112 performs traffic diversion functions on the Internet. The router 112 may have interfaces with different types of physical layer connections, such as copper cables, optical fibers, or wireless transmission. The router 112 may support different network layer transmission standards. Each network interface is used to enable data packets to be forwarded from one transmission system to another. Routers 112 can be used to connect two or more logical groups of computer devices, known as subdomains, each with a different network prefix. Routers 112 can provide connectivity in an enterprise, between an enterprise and the Internet, or in an Internet service provider's network as shown in FIG. 1. Some routers 112 are configured to interconnect different Internet service providers or are used in large enterprise networks. Smaller routers 112 generally provide connectivity between a home or office network and the Internet. The router 112 shown in "Figure 1" can represent any router suitable for network transmission, such as: an edge router, a subscriber edge router, an inter-provider border router, a core router, or an Internet backbone, a port forwarding, a voice/data/fax/video processing router, and the like.

An Internet service provider (ISP) 102 is an organization that provides access, use, or participation in Internet services. ISP 102 may have different forms of organization, such as commercial, community-owned, non-profit, or private. Internet services provided by ISP 102 include Internet access, Internet transit, domain name registration, web hosting, Usenet service, and colocation. ISP 102 shown in FIG. 1 may represent any suitable ISP, such as hosting ISPs, transit ISPs, virtual ISPs, free ISPs, wireless ISPs, and the like.

A network service provider (NSP) 104 is an organization that provides bandwidth or network access by providing access to the Internet backbone directly to Internet service providers. NSP 104 may provide access to network access points (NAPs). NSP 104 is sometimes referred to as a backbone provider or an Internet provider. NSP 104 may include telecommunication companies, data carriers, wireless communication providers, Internet service providers, and cable TV operators that provide high-speed Internet access. NSP 104 may also include information technology companies.

It should be understood that the system 100 shown in FIG. 1 is merely an example, and that there may be different configurations and systems that may be created to transfer data between networks and computing devices. Because there is a lot of customization involved in forming a network, there is a need to create greater customization in how to determine the best path for transferring data between computers or networks. In view of the above, the present disclosure is primarily directed to offloading the best path calculation to an external device, thereby creating a system, method, and device that is well suited for a particular computer group or a particular enterprise to have greater customization in determining the best path algorithm.

"Figure 2" illustrates a schematic diagram of a system 200 for determining the best path decision between devices. The system 200 includes multiple BGP entities R1, R2, and R3 for transmitting information. Each BGP entity R1, R2, and R3 can be a switch 106 or a router 112. Each BGP entity R1, R2, and R3 executes BGP to route traffic. Each BGP entity R1, R2, and R3 communicates with a best path controller 202. The best path controller 202 is configured to continuously receive multiple BGP NLRI messages from the BGP entity, perform best path calculation, and transmit an NLRI message containing the best path calculation result to each BGP entity R1, R2, and R3. In one disclosed embodiment, the best path controller 202 may be implemented on the switch 106 or the router 112. This may provide enhanced flexibility so that a single software package of the best path controller 202 may be implemented on various types of hardware.

FIG. 3 illustrates a schematic diagram of a state machine in a BGP device executing process 300. Process 300 includes multiple queues for routing processing. When received from an established neighbor, a BGP NLRI message is created and added to a best path queue for best path calculation. The BGP NLRI message may be moved to a Routing Information Base queue before entering the queue to be updated, established, and broadcasted.

In process 300, when BGP receives and processes an update message via NLRI (step 302), a decision is made in step 304 whether the best path controller (BPC) is enabled. If the best path controller is enabled, the BGP NLRI message is pushed to the out-queue 306 of the channel leading to the best path controller 324. The best path controller may require the assistance of next hop (NH) tracking (step 326). In next hop tracking, BGP uses the services provided by the RIB to track the reachability and metrics of each next hop. When these attributes change, the RIB will notify BGP. BGP can use the tracking results to recalculate a new set of best paths. When the best path calculation is completed, the best path controller pushes the BGP NLRI message and its respective best path back to the BGP entity via in-queue 328, and finally moves the NLRI to RIB queue 316 for subsequent processing.

If the decision in step 304 indicates that the best path controller is off, then in step 308 it is determined whether the next hop has been traced. If the next hop is unknown, the BGP NLRI message will be pushed to the best path queue 312 only after the next hop is traced using the RIB (step 310). If the decision in step 308 indicates that the next hop is known, the BGP NLRI message will be pushed directly to the best path queue 312 for best path calculation (step 314). The resulting best path will be pushed to the RIB queue 316.

Further, the items in the RIB queue 316 are RIB downloaded (step 318) before being sent to the update queue 320. Finally, the update creation operation is performed (step 322).

New queues can be introduced into process 300 to integrate with the best path controller. The best path out-queue sends BGP NLRI messages marked as best path pending to the best path controller. The best path result is returned to the BGP entity through the best path in-queue, at which time the NLRI is marked as best path completed.

The connection to the best path controller can be established through any reliable transport. Examples include: Remote Procedure Call (gRPC), HTTP, or custom inter-process communication (IPC). The streaming message format can use binary form such as: Protocol Buffers (Protobuf), Thrift protocol, or text form such as: JavaScript Object Notation (JSON) and eXtensible Markup Language (XML). In one embodiment, the implementation of the BGP entity and the best path controller must reach an agreement on the transport and format.

In one embodiment, a BGP entity learns NLRIs from BGP neighbors. Instead of calculating the best path for the NLRI locally, the BGP entity sends a message to a best path controller containing the NLRI and all paths and attributes learned so far. This message can be sent when the NLRI is first learned or when the path set for any NLRI changes. The best path controller is expected to send back the best path calculation results to allow the NLRI to determine one or more paths that can become the best path. In addition, the best path controller can use the result message to update the attributes or next hop in any path. While waiting for a response from the best path controller, the BGP entity will retain the NLRI in the best path queue. Upon receiving the result message from the best path controller, the BGP entity de-queues the NLRI from the best path queue and re-queues the NLRI to the RIB installation queue if the NLRI needs to be installed to the RIB, or re-queues the NLRI to the update creation queue to notify it to BGP neighbors.

To ensure high throughput, the BGP entity may send NLRI messages to the best path controller in any asynchronous manner. The BGP entity may send additional messages to the same NLRI without waiting for the result to be returned. In this way, it is possible for multiple messages to be sent to the same NLRI at the same time. Each NLRI message contains a version field that is used to ensure that all messages received from the same BGP entity are uniquely identified. In an example where the best path controller receives multiple messages from the same BGP entity for the NLRI in rapid succession, the best path controller may choose to return the result based on the latest NLRI message received. The NLRI message contains a version number that can be used to identify the latest message. The BGP entity expects the best path controller to return the result for the latest version of the NLRI. When such a message is received, the BGP entity shall retain its advertisement and other procedures for the pending NLRI.

The best path controller can also send the result message in an unsolicited form. In this embodiment, the best path controller sends the result message not in response to the NLRI message of the BGP entity. This can be useful in examples where a policy change request recalculates the best path and is pushed in an unsolicited form. In this example, the best path controller must include the latest NLRI version number in the result message.

In addition to best-path computation messages, the best-path controller can also act as a consumer of next-hop reachability changes. When the reachability parameters of the next-hop corresponding to the best-path change, the best-path controller can recalculate the new best-path and push the new best-path to the BGP entity. Next-hop tracking is generally a registration service provided by the RIB, and the best-path controller can use it to register one or more next-hops that the best-path controller is interested in.

In one embodiment, the best path functionality is implemented in a separate process. In such an embodiment, it is important to handle failures and restarts of both the best path controller and the BGP entity. To handle these scenarios, an implementation can be implemented through a graceful restart mechanism described herein. When the BGP entity restarts, the best path controller maintains the state previously learned from the peer. Until the BGP entity is detected to have restarted, either through a transmission loss or explicit signaling, the best path controller marks all information learned from the BGP entity as stale. Once a BGP entity relearns NLRIs from its neighboring BGP entities, it will retransmit the NLRIs to the best path controller. The best path controller returns the result message as usual. In addition, the best path controller marks the newly received routes as "fresh". Once the BGP entity transmits all NLRIs according to the explicit End-of-RIB (EoR) mark or timer indication, the best path controller will clear all NLRIs that are still marked as outdated.

The aforementioned embodiments can also be applied to the scenario where the best path controller crashes and restarts. In this scenario, the BGP entity maintains the best path previously calculated by the best path controller. Once the best path controller restarts, the BGP entity marks all best paths as outdated and retransmits NLRIs and their paths to the best path controller. Until the result of the best path is received, the BGP entity will update the corresponding item and mark it as "new". Once the BGP entity receives the results of all NLRIs, the BGP entity will clear all best paths that are still marked as outdated.

"Figure 4" is a schematic diagram of a system 400 for offloading optimal path calculations and routing storage to a data storage space 402. The system 400 includes a data storage space 402 that communicates with multiple BGP entities R1, R2, R3...Rn. The data storage space 402 includes an index server 404 that communicates with metadata 406. The metadata 406 provides an indication of the location of certain data in a shared disk storage 412. The shared disk storage 412 includes a plurality of data storage devices 412a, 412b, 412c...412n. The index server 404 communicates with a processing platform 408 and the processing platform 408 can access the shared disk storage 412. The index server 404 is configured to provide an indication to the processing platform 408 of the location of certain data in the shared disk storage 412. The index server 404 makes the determination based on the metadata 406. The data storage space 402 includes a host server 410 that communicates with the processing platform 408. The host server 410 enables the processing platform 408 to write to the shared disk storage 412 by updating, adding, and deleting information in the shared disk storage 412. The processing platform 408 may include a plurality of hosts, each of which includes a processor and cache storage. Each host may be configured to read and write in the shared disk storage 412.

FIG. 5 illustrates an embodiment where information is offloaded to data storage space 402 and data storage space 402 is located locally on a switch or router. The switch or router further includes hardware 516 and software stack 514. Hardware 516 provides a physical connection that enables data packets to be transmitted between computers or networks. Software stack 514 contains instructions implemented by processor or hardware 516 to determine the best path and forward the data packet along the best path to its destination device.

FIG. 6 illustrates an embodiment of a system 600 in which information is offloaded to a data storage space 402 and the data storage space 402 is accessible via a cloud network 614. In one embodiment, the data storage space 602 is a cloud-based database and is accessible by multiple BGP entities R1, R2, R3, ... Rn.

FIG. 7 is a schematic block diagram illustrating a method 700 for offloading best path calculations to a best path controller. The method 700 may be performed by the best path controller 202 discussed herein. The best path controller 2020 may communicate with one or more devices to transmit data to a destination device. These devices may be BGP entities such as routers 112 or switches 106. The best path controller 202 may be located locally on the one or more devices or the best path controller 202 may be external to each of the one or more devices.

Method 700 begins and best path controller 202 stores a list of a plurality of NLRIs learned from a device (step 702), wherein the NLRIs include paths for transmitting data from the device to a destination device. The list includes: all NLRIs learned by the device, all non-outdated NLRIs used by the device, NLRIs associated with the device and other devices, less than all NLRIs learned by the device, and the like. Method 700 continues and best path controller 202 receives an update message from the device (step 704). The update message may include an NLRI message exchanged between a BGP router and best path controller 202. The NLRI may include a length and a prefix. The method 700 continues and the best path controller 202 performs a best path calculation to find one or more best paths based on the update information, so that the best path calculation is offloaded from the device to the best path controller (step 706). The one or more best paths can be different or the same as the best paths stored in the list learned by the device. The method 700 continues and the best path controller 202 transmits the one or more best paths to the device (step 706).

See FIG. 8 , which is a block diagram of an exemplary computing device 800 . The computing device 800 can be used to execute various programs, such as those discussed. In one embodiment, the computing device 800 can execute various monitoring functions, such as those discussed herein, and can also execute one or more applications, such as the applications or functions discussed. The computing device 800 can be any of a wide variety of computing devices, such as a desktop computer, an in-dash computer, a vehicle control system, a laptop computer, a server computer, a handheld computer, a tablet computer, and the like.

The computing device 800 includes one or more processors 802, one or more memory devices 804, one or more interfaces 806, one or more mass storage devices 808, one or more input/output devices 810, and a display device 830, all coupled to a bus 812. The processor 802 includes one or more processors or controllers for executing instructions stored in the memory device 804 and/or the mass storage device 808. The processor 802 may include various types of computer-readable media, such as cache memory.

The memory device 804 includes different computer-readable media, such as volatile memory (e.g., random access memory 814) and/or non-volatile memory (e.g., read-only memory 816). The memory device 804 may also include rewritable read-only memory (ROM), such as flash memory.

The mass storage device 808 includes various computer readable media, such as magnetic tapes, magnetic strips, optical disks, solid state memory (e.g., flash memory), and the like. As shown in FIG. 8 , a particular mass storage device is a hard disk 824. Various drives may be included in the mass storage device 808 to enable reading from and/or writing to various computer readable media. The mass storage device 808 includes removable media 826 and/or non-removable media.

Input/output devices 810 include a variety of devices that can allow data and/or other information to be input to or output from computing device 800. Example input/output devices 810 include cursor control devices, keyboards, keypads, microphones, screens or other display devices, speakers, printers, network interface cards, modems, and the like.

Display device 830 includes any type of device that can display information to one or more users of computing device 800. Examples of display device 830 include a screen, a display terminal, a video projection device, and the like.

Interface 806 includes a variety of different interfaces that allow computing device 800 to interact with other systems, devices, or computing environments. Interface 806 in the example can include any number of different network interfaces 820, such as interfaces connecting to local area networks, wide area networks, wireless networks, and the Internet. Other interfaces include user interfaces 818 and peripheral device interfaces 822. Interface 806 can include one or more user interface elements 818. Interface 806 can include one or more peripheral interfaces, such as interfaces used by printers, pointing devices (mouse, touch pad or other suitable user interface currently known or later discovered by those familiar with the art), keyboards, and the like.

The bus 812 may allow the processor 802, the memory device 804, the interface 806, the mass storage device 808, and the input/output device 810 to communicate with each other and with other devices or components coupled to the bus 812. The bus 812 represents one or more of several bus structures, such as a system bus, a PCI bus, an IEEE bus, a USB bus, and the like.

For purposes of illustration, programs and other executable program components are represented as individual blocks, although it is understood that these programs or components may reside in different storage components of computing device 800 at different points in time. Executed by processor 802. Alternatively, the system and program described in the present disclosure can be implemented in hardware, or a combination of hardware, software and/or firmware. For example, one or more application specific integrated circuits (ASICs) may be programmed to execute one or more systems and processes described in this disclosure.

The foregoing description has been presented for purposes of illustration and description. It is not intended to exhaust or limit the present disclosure to the precise form disclosed. Many modifications and variations are possible from the above teachings. Furthermore, it should be understood that any or all of the aforementioned optional implementations may be used in any combination to form additional hybrid implementations of the present disclosure.

Furthermore, although the disclosure describes and illustrates specific implementations, it is not intended to be limited to the specific forms or arrangements of parts described. The scope of the disclosure is defined by the appended patents, and if possible, it should cover any future patents filed in this or a different application and their equivalents.

Example

The following examples relate to other further embodiments.

Example 1 is a best path calculation offloading method for a network computing environment, the method comprising storing, by a best path controller, a list of multiple paths learned by a device, wherein the multiple paths are paths used by the device to transmit data to a destination device. The method comprises receiving, by the best path controller, a message from the device. The message is a Network Layer Reachability Information (NLRI) message. The method comprises performing a best path calculation by the best path controller to find one or more best paths based on the message, so that the performance of the best path calculation is offloaded from the device to the best path controller.

Example 2 is the same as Example 1, where the device is a router or a switch.

Example 3 is a method similar to any of Examples 1-2, where the devices implement Border Gateway Protocol (BGP).

Example 4 is a method like any one of Examples 1-3, further comprising updating the next hops of any path in the plurality of paths in the list based on the one or more optimal paths calculated by the optimal path controller.

Example 5 is a method like any one of Examples 1-4, wherein receiving the message (which may be an NLRI message) from the device includes asynchronously receiving a plurality of messages from the device; and performing the optimal path calculation includes performing the optimal path calculation based on the plurality of messages for a latest version of network layer reachability information (NLRI).

Example 6 is a method as any one of Examples 1-5, wherein each of the plurality of messages includes a version number field, the version number field including a unique identification of all messages received by the device for a single NLRI.

Example 7 is a method like any one of Examples 1-6, further comprising: re-performing the optimal path calculation based on a strategy change; generating a result message including one or more optimal paths generated based on the re-performed optimal path calculation; and transmitting the one or more optimal paths to the device.

Example 8 is a method like any one of Examples 1-7, further comprising: receiving, by the best path controller, a next hop reachability update for one of the plurality of paths learned by the device in the list; re-calculating the best path in response to the received next hop reachability update; generating a result message including one or more best paths based on the re-calculation of the best path; and transmitting the result message to the device.

Example 9 is a method like any one of Examples 1-8, which further includes: determining that the device has been restarted; retaining the list of the multiple paths learned by the device by the optimal path controller; based on a response to determining that the device has been restarted, marking each of the multiple paths learned by the device in the list as obsolete; receiving an updated path from the device in response to the device relearning the path; and clearing the obsolete path corresponding to the updated path in the multiple paths in the list.

Example 10 is a method like any of Examples 1-9, wherein the best path operation is customized for the device and other devices in the network to which the device belongs.

Example 11 is an optimal path computing offloading system in a network computing environment, comprising: a device in a network, wherein the device is configured to transmit data from the device to a destination device; an optimal path controller, communicating with the device, the optimal path controller comprising a processor, configured to execute a plurality of instructions stored in a non-transient computer-readable storage medium, the plurality of instructions comprising: storing, by the optimal path controller, A list of multiple paths learned by the device is stored in a memory, wherein each of the multiple paths is a path used by the device to transmit data to a destination device; receiving a message from the device; performing an optimal path calculation to find one or more optimal paths based on the message, so that the performance of the optimal path calculation is offloaded from the device to the optimal path controller; and transmitting the one or more optimal paths to the device.

Example 12 is a system like any of Example 11, wherein the device is a router or a switch, and the device implements the border gateway protocol.

Example 13 is a system like any one of Examples 11-12, wherein the plurality of designations further comprises updating the next hops of any path in the plurality of paths in the list based on the one or more optimal paths calculated by the optimal path controller.

Example 14 is a system like any one of Examples 11-13, wherein the plurality of designations further include: receiving the message from the device, including asynchronously receiving the plurality of messages from the device; and performing the optimal path operation, including performing the optimal path operation on a most recent version of the plurality of messages.

Example 15 is a system like any one of Examples 11-14, wherein the plurality of designations further include: re-performing the optimal path calculation based on a policy change; generating a result message including one or more optimal paths generated based on the re-performed optimal path calculation; and returning the result message to the device.

Example 16 is a non-transitory computer-readable storage medium storing a plurality of instructions for providing one or more processors to execute, the plurality of instructions comprising: storing a list of a plurality of paths learned by a device in a memory, wherein each of the plurality of paths is a path used by the device to transmit data to a destination device; receiving a message from the device; performing an optimal path calculation to find one or more optimal paths based on the message, such that the performance of the optimal path calculation is offloaded from the device to the optimal path controller; and transmitting the one or more optimal paths to the device.

Example 17 is a non-transitory computer-readable storage medium like any one of Example 16, wherein the plurality of instructions further include: re-performing the optimal path calculation based on the policy change; generating a result message including one or more optimal paths generated based on the re-performed optimal path calculation; and returning the result message to the device.

Example 18 is a non-transitory computer-readable storage medium as any one of Examples 16-17, wherein the plurality of instructions further include: receiving, by the best path controller, a next-hop reachability update for one of the plurality of paths learned by the device in the list; re-performing the best path calculation in response to the received next-hop reachability update; generating a result message including one or more best paths based on the re-performing the best path calculation; and transmitting the result message to the device.

Example 19 is a non-transitory computer-readable storage medium as any one of Examples 16-18, wherein the plurality of specifications further include: determining that the device has been restarted; retaining, by the optimal path controller, the list of the plurality of paths learned by the device; marking each of the plurality of paths learned by the device in the list as obsolete in response to determining that the device has been restarted; receiving an updated path from the device in response to the device relearning the path; and clearing the obsolete path in the plurality of paths in the list that corresponds to the updated path.

Example 20 is a non-transitory computer-readable storage medium as any of Examples 16-19, wherein the best path operation is customized for the device and other devices in the network to which the device belongs.

It should be understood that any features of the foregoing arrangements, examples and embodiments may be combined in a single embodiment comprising combined features taken from any disclosed arrangements, examples and embodiments.

It is understood that the various features described in this disclosure provide significant advantages and advances in the relevant fields. The following patent scope is a partial example of those features.

In the detailed descriptions in the foregoing disclosure, different features of the disclosure are combined in a single embodiment to simplify the disclosure. Such disclosure method should not be interpreted as reflecting an intention that the disclosure claimed to be protected requires more features than those explicitly mentioned in each patent scope. On the contrary, the invention's advanced part lies in less than all the features in the foregoing single disclosed embodiment.

It should be understood that the above arrangement is only based on the explanation of the disclosure principle of the application. Many modifications and selective arrangements can be designed by those familiar with the relevant technical field without departing from the spirit and scope of the disclosure, and the attached patent scope should cover these modifications and arrangements.

Therefore, although the disclosure has been shown in the drawings and described in detail above, it will be apparent to those skilled in the art that many modifications, including but not limited to changes in size, material, shape, form, function, operation, assembly and use, can be made without departing from the principles and concepts described herein.

Furthermore, where appropriate, the functions described in the present disclosure may be performed by one or more of the following: hardware, software, firmware, digital components, or analog components. For example, one or more application specific integrated circuits or field programmable gate arrays (FPGAs) may be programmed to execute one or more systems and procedures described in the present disclosure. Certain terms are used throughout the description and in the following patent scope to represent specific system components. Those familiar with the relevant technical field should understand that components may be referred to by different names. This document does not intend to distinguish between components with the same functions but using different names.

The foregoing description has been presented for purposes of illustration and description. It is not intended to exhaust or limit the disclosure to the precise form disclosed. Numerous modifications and variations are possible in light of the above teachings. Furthermore, it should be appreciated that any or all of the aforementioned optional implementations may be used in any combination to form additional hybrid implementations of the disclosure.

Furthermore, although the disclosure describes and illustrates specific implementations, it is not intended to be limited to the specific forms or arrangements of parts described. The scope of the disclosure is defined by the appended patents, and if possible, it should cover any future patents filed in this or a different application and their equivalents.

100: System 102: Internet Service Provider 104: Network Service Provider 106: Switch 108: Computing Equipment 110: Local Area Network 112: Router R1, R2, R3, Rn: BGP Entity 200: System 202: Best Path Controller 300: Process 306: Dequeue 312: Best Path Queue 316: RIB Queue 320: Update Queue 324: Best Path Controller 328: Enqueue 400: System 402: Data Storage Space 404: Index Server 406: Metadata 408: Processing Platform 410: Host Server 412: shared disk storage 412a, 412b, 412c, 412n: data storage device 514: software stack 516: hardware 600: system 602: data storage space 604: index server 606: metadata 608: processing platform 610: host server 612: shared disk storage 612a, 612b, 612c, 612n: data storage device 614: cloud network 700: method 800: computing device 802: processor 804: memory device 806: interface 808: mass storage device 810: Input/output devices 812: Display devices 814: Random access memory 816: Read-only memory 818: User interface 820: Network interface 822: Peripheral device interface 824: Hard disk 826: Removable media 830: Display devices Step 302: Update process Step 304: Best path controller activated Step 308: Next hop known? Step 310: Use RIB to perform next hop tracking Step 314: Optimal path calculation Step 318: Perform RIB download Step 322: Perform update creation Step 326: Perform next hop tracking Step 702: Store in memory a list of multiple paths learned by the device, at least a portion of the multiple paths are used to transmit data from the device to a destination device Step 704: Receive an update message from the device Step 706: Performing an optimal path calculation to find one or more optimal paths based on the update message, so that the optimal path calculation is offloaded from the device to the optimal path controller Step 708: Transmitting the one or more optimal paths to the device

FIG. 1 is a schematic diagram of a system of networked devices communicating via the Internet. FIG. 2 is a schematic diagram of a system for offloading best path calculations from independent devices to a best path controller. FIG. 3 is a schematic diagram of a state machine execution process in a BGP execution device. FIG. 4 is a schematic diagram of a system for offloading storage of best path information to a data storage space. FIG. 5 is a schematic diagram of a system for offloading storage of best path information to a data storage space. FIG. 6 is a schematic diagram of a system for offloading storage of best path information to a data storage space. FIG. 7 is a flow block diagram of a method for offloading path calculations to a best path controller. Figure 8 is a schematic diagram illustrating components of an example computing device.

R1, R2, R3, Rn: BGP entities

200:System

202: Best path controller

Claims (14)

A method for offloading optimal path computation in a network computing environment comprises the following steps: storing in a memory a list of a plurality of paths learned by a device through an optimal path controller, wherein each of the plurality of paths is a path used by the device to transmit data to a destination device; receiving, through a Border Gateway Protocol (BGP) entity executed on the device, a network layer reachability information (NLR) from a neighbor of the device; Receive a NLRI (Non-Local Path Information) message from a device; retain, by the BGP entity, the NLRI message in a queue; forward, by the BGP entity, the NLRI message to the best path controller while retaining the NLRI message in the queue; receive, by the best path controller, the NLRI message from the device; perform, by the best path controller, a best path operation to find one or more best paths based on the NLRI message, such that the performance of the best path operation is offloaded from the device to the best path controller; transmit the one or more best paths to the device; and remove, by the BGP entity, the NLRI message from the queue in response to receiving the one or more best paths. The optimal path computing offloading method in a network computing environment as in claim 1, wherein the device is a router or a switch. The optimal path computing offloading method of the network computing environment as claimed in claim 1 further includes a step of updating the next hops of any path in the plurality of paths in the list based on the one or more optimal paths calculated by the optimal path controller. The best path calculation offloading method of the network computing environment as claimed in claim 1, wherein: the step of receiving the NLRI message from the device comprises asynchronously receiving a plurality of NLRI messages from the device, wherein the plurality of NLRI messages comprises the NLRI message; and the step of performing the best path calculation comprises performing the best path calculation for a latest version of network layer reachability information (NLRI) based on the plurality of messages. The optimal path computing offloading method for a network computing environment as claimed in claim 4, wherein each of the plurality of NLRI messages includes a version number field, the version number field including a unique identifier of all messages received by the device for a single NLRI in the plurality of NLRI messages. The optimal path calculation offloading method of the network computing environment as claimed in claim 1 further comprises the following steps: re-performing the optimal path calculation based on a policy change; generating a result message including one or more optimal paths generated based on the re-performed optimal path calculation; and returning the result message to the device. The best path calculation offloading method of the network computing environment of claim 1 further comprises the following steps: receiving, by the best path controller, a next hop reachability update of one of the plurality of paths learned by the device in the list; re-performing the best path calculation in response to the received next hop reachability update; generating a result message including one or more best paths based on the re-performing the best path calculation; and transmitting the result message to the device. The optimal path computing offloading method of the network computing environment of claim 1 further comprises the following steps: determining that the device has been restarted; retaining, by the optimal path controller, the list of the plurality of paths learned by the device; based on a response to the step of determining that the device has been restarted, marking each of the plurality of paths learned by the device in the list as obsolete; receiving an updated path from the device in response to the device relearning the path; and clearing an obsolete path corresponding to the updated path in the plurality of paths in the list. A method for offloading optimal path computing in a network computing environment as in claim 1, wherein the optimal path computing is customized for the device and other devices in the network to which the device belongs. An optimal path computing offloading system for a network computing environment includes: a device in a network, wherein the device is configured to: receive, via a Border Gateway Protocol (BGP) entity executed on the device, network layer reachability information from a neighbor of the device a best path controller, communicating with the device, the best path controller comprising a processor configured to execute a plurality of instructions stored in a non-transitory computer-readable storage medium, the plurality of instructions comprising: a list of a plurality of paths learned by a device by a best path controller, stored in a memory, wherein the plurality of paths each of which is a path used by the device to transmit data to a destination device; receiving, by the best path controller, the NLRI message from the device; performing, by the best path controller, a best path operation to find one or more best paths based on the NLRI message, such that the performance of the best path operation is offloaded from the device to the best path controller; and transmitting the one or more best paths to the device; wherein the device is further configured to remove the NLRI message from the queue as a response when the one or more best paths are received from the best path controller. An optimal path computing offloading system for a network computing environment as in claim 10, wherein the device is a router or a switch. The optimal path computing offloading system of the network computing environment as claimed in claim 10, wherein the plurality of designations further include updating the next hops of any path in the plurality of paths in the list based on the one or more optimal paths calculated by the optimal path controller. The optimal path calculation offloading system of the network computing environment as claimed in claim 10, wherein the plurality of designations further include: receiving the NLRI message from the device, including asynchronously receiving a plurality of NLRI messages from the device, wherein the plurality of NLRI messages include the NLRI message; and performing the optimal path calculation, including performing the optimal path calculation on a most recent version of the plurality of NLRI messages. The optimal path calculation offloading system of the network computing environment as claimed in claim 10, wherein the plurality of specifications further include: re-performing the optimal path calculation based on a policy change; generating a result message including one or more optimal paths generated based on the re-performed optimal path calculation; and returning the result message to the device.

Images