BGP route aggregation exception systems and methods

Systems and methods for a Border Gateway Protocol (BGP) route aggregation exception include advertising, to BGP peers, of a plurality of prefixes using BGP route aggregation or summarization; detecting a failure that is local to the router affecting a prefix of the plurality of prefixes; and advertising an aggregation exception that identifies the prefix to all of the BGP peers. The systems and methods can also include detecting recovery of the failure; and sending a withdrawal of the aggregation exception to all of the BGP peers.

FIELD OF THE DISCLOSURE

The present disclosure generally relates to networking. More particularly, the present disclosure relates to systems and methods for a Border Gateway Protocol (BGP) route aggregation exception.

BACKGROUND OF THE DISCLOSURE

Border Gateway Protocol (BGP) is a standardized exterior gateway protocol designed to exchange routing and reachability information among Autonomous Systems (AS) on the Internet. BGP Route summarization (aggregation) is a very powerful tool that can summarize the routes in routing protocol and advertise only summarized prefixes to achieve scale. BGP allows the aggregation of specific routes into a single summarized route with a “BGP aggregate-address” command. Disadvantageously, BGP route-summarization can cause traffic blackholing and sub-optimal routing in some scenarios of network failures. One of the workarounds to address the problem is to remove the BGP route aggregation, which forces the individual updates to be sent to BGP peers. Basically, forcing administrators to remove the route summarization to handle to failures, losing all advantages of summarization. Decommissioning the BGP aggregation feature will be take away the benefits it brings to scalability and network performance. This leads to too many routes in the data plane consuming the hardware entries, depleting the valuable network forwarding chip resources. This slows down the data path lookup for selecting the destination route, slows down best path selection due to too many routes in the BGP routing table, and increases control plane (BGP) route advertisements in the network, increasing the BGP convergence timing in the network.

BRIEF SUMMARY OF THE DISCLOSURE

The present disclosure relates to systems and methods for a Border Gateway Protocol (BGP) route aggregation exception. The present disclosure includes a novel BGP update that contains a new path attribute—“Aggregate Exception.” This new path attribute helps in identifying a network failure and appropriately advertising to all BGP peers about the network failure through “Aggregate Exception” Network Layer Reachability Information (NLRI), which results in better path selection at the receiving BGP speakers (downstream routers). The present disclosure extends BGP NLRI updates to achieve resiliency in BGP network deployments, defines a new BGP path attribute (Aggregate-Exception) to be used in BGP updates, dynamically responds to network failures by advertising the Aggregate-Exception NLRI, dynamically withdraws the BGP update from other BGP peers upon the recovery of the network failures, and the like. The present disclosure allows addition and removal of the failed prefix with alternative next hop on the forwarding plane of the receiving BGP speaker. The present disclosure includes functionality at an aggregating BGP speaker and a receiving BGP speaker. Further, the present disclosure introduces a next-hop exclusion concept to the BGP routing protocol and provides an efficient approach to implement and deploy without compromising the benefits of route aggregation among BGP peers.

In an embodiment, a router includes a plurality of ports and switching circuitry configured to switch traffic between the plurality of ports; and circuitry configured to cause an advertisement, to Border Gateway Protocol (BGP) peers, of a first plurality of prefixes using BGP route aggregation or summarization, detect a failure that is local to the router affecting a prefix of the first plurality of prefixes, and cause an advertisement of an aggregation exception that identifies the prefix to all of the BGP peers. The circuitry can be further configured to detect recovery of the failure, and cause a withdrawal of the aggregation exception to all of the BGP peers. The circuitry can be further configured to receive an aggregation exception that identifies a second prefix that is part of a second plurality of prefixes that were advertised to the router using BGP aggregation, and find an alternate path for the second prefix and program a data plane accordingly. The circuitry can be further configured to receive a withdrawal of the aggregation exception for the second prefix, and delete the alternate path from a BGP routing table and from the data plane. The aggregation exception can be a path attribute in a BGP update message. The BGP can include one of internal BGP (iBGP) and external BGP (eBGP). The aggregation exception can be a route-advertisement of path-avoidance to a specific next-hop.

In additional embodiments, a method implemented by a router includes steps and a non-transitory computer-readable medium includes instructions that, when executed, cause one or more processors to perform the steps. The steps include advertising, to Border Gateway Protocol (BGP) peers, a first plurality of prefixes using BGP route aggregation or summarization; detecting a failure that is local to the router affecting a prefix of the first plurality of prefixes; and advertising an aggregation exception that identifies the prefix to all of the BGP peers. The steps can further include detecting recovery of the failure; and sending a withdrawal of the aggregation exception to all of the BGP peers. The steps can further include receiving an aggregation exception that identifies a second prefix that is part of a second plurality of prefixes that were advertised to the router using BGP aggregation; and finding an alternate path for the second prefix and programming a data plane accordingly. The steps can further include receiving a withdrawal of the aggregation exception for the second prefix; and deleting the alternate path from a BGP routing table and from the data plane. The aggregation exception can be a path attribute in a BGP update message. The BGP can include one of internal BGP (iBGP) and external BGP (eBGP). The aggregation exception can be a route-advertisement of path-avoidance to a specific next-hop.

DETAILED DESCRIPTION OF THE DISCLOSURE

Again, the present disclosure relates to systems and methods for a Border Gateway Protocol (BGP) route aggregation exception. The present disclosure includes a novel BGP update that contains a new path attribute—“Aggregate Exception.” This new path attribute helps in identifying a network failure and appropriately advertising to all BGP peers about the network failure through “Aggregate Exception” Network Layer Reachability Information (NLRI), which results in better path selection at the receiving BGP speakers (downstream routers). The present disclosure extends BGP NLRI updates to achieve resiliency in BGP network deployments, defines a new BGP path attribute (Aggregate-Exception) to be used in BGP updates, dynamically responds to network failures by advertising the Aggregate-Exception NLRI, dynamically withdraws the BGP update from other BGP peers upon the recovery of the network failures, and the like. The present disclosure allows addition and removal of the failed prefix with alternative next hop on the forwarding plane of the receiving BGP speaker. The present disclosure includes functionality at an aggregating BGP speaker and a receiving BGP speaker. Further, the present disclosure introduces a next-hop exclusion concept to the BGP routing protocol and provides an efficient approach to implement and deploy without compromising the benefits of route aggregation among BGP peers.

The present disclosure mitigates traffic blackholing and sub-optimal routing arising out of BGP route summarization. As is known in the art, “traffic blackholing” is a reference to a place in the network where incoming or outgoing traffic is silently discarded (or “dropped”) without informing the source that the data did not reach its intended recipient. With route summarization, BGP replaces a number of individual network advertisements with a single summarized advertisement and sends it to BGP peers. Unless all the individual networks go down, the aggregating node does not withdraw the summarized prefix from its peers. If one of the network's reachability is down, BGP peers will not be aware of the fact and continue to forward the traffic to the aggregating node where the traffic gets discarded. Note, the terms “route summarization” and “route aggregation” may be used interchangeably herein.

With the present disclosure, the aggregating node will have a mechanism to inform its BGP peers about the failed/unreachable networks due to link failures, temporary outages, etc. By knowing the aggregate exception route, BGP peers can look for an alternative next hop to forward the traffic. Upon the recovery of the failure, the aggregating node can withdraw the aggregate-exception BGP route it sent before. With this withdrawal, the receiving BGP peers will remove the aggregate-exception route from the control plane and data plane and fall back to the original summarized route to forward the traffic. By mitigating the problem arising out of route summarization in BGP, the solution helps to keep BGP route summarization in network deployments, improving network performance, scalability, etc. The present disclosure applies to both internal BGP (iBGP) and external BGP (eBGP).

BGP route summarization is a quite commonly used BGP feature to summarize specific prefixes into one summarized prefix with a shorter prefix-length. It is an effective way of enhancing the scalability requirements of iBGP and eBGP deployments. Some of the advantages are lowering the computation required by network elements by reducing the number of control plane (BGP) route advertisements in the network, conserving the hardware entries, and making the hardware lookup faster. On the flipside, BGP route summarization can cause sub-optimal routing and traffic blackholing in case of network failures, which is resolved herein.

FIGS.1and2are network diagrams of a network10illustrating internal BGP (iBGP) traffic blackholing. In this example, the network10includes three routers12A,12B,12C and five prefixes P1, P2, P3, P4, P5. The routers12A,12B are aggregating nodes and the router12C is a receiving node (or speakers), and in this example, a device14is configured to send traffic to the prefix P2. The prefixes P1-P5are each connected to each of the routers12A,12B and include common addresses of 10.10.X.X/24. BGP route aggregation is used here with all of prefixes aggregated in BGP. For example, both of the routers12A,12B provide a summarized route advertisement of 10.10.0.0/16 to the router12C. In the control plane, all of the prefixes are advertised for a “best” next hop (NH) to the router12A (address A.A.A.A) and next to the router12B (address B.B.B.B). The device14send the traffic to prefix P2to NH A.A.A.A based on the route aggregation.FIG.1illustrates an operational scenario with no failures. Also, for example, the network10is an Autonomous System (AS) with a label of AS100.

FIG.2includes a fault16between the router12A and the prefix P2. In this scenario with route aggregation, there is no new advertisement due to the fault16. Rather, the traffic from the device14destined to the prefix P2is discarded at the router12A, causing traffic blackholing without any recovery, and bandwidth being wasted on the links. If the router12A has a path to reach the router12B, then the router12A will forward to the router12B causing a “sub-optimal routing path here,” rather than the router12C itself directly sending to the router12B.

FIGS.3,4, and5are network diagrams of a network20illustrating external BGP (eBGP) traffic blackholing. In this example, there are five example autonomous systems AS100, AS200, AS300, AS400, AS500and example routers12A,12B,12C,12D,12G are illustrated in each one of the autonomous systems AS100, AS200, AS300, AS400, AS500, respectively. Again, the network20utilizes BGP route aggregation where advertisements22are shown for aggregated prefixes within each autonomous system AS100, AS200, AS300, AS200, AS400, AS500. In these examples, the device14is configured to send traffic to prefix P2which is in the autonomous system AS200, and the router12D in the autonomous system AS400is configured to send the traffic destined to the prefix P2via an NH to the router12C.

There is a fault24which causes the traffic from the device14to be blackholed at the router12C since there is no route to the router12B from the router12C. Similar toFIG.4, there is the fault24between the routers12B,12C. Here, the router12C has a default route and traffic is now sub-optimally routed, as shown inFIG.5.

BGP Aggregation Exception Path Attribute

In order to mitigate the problems of sub-optimal routing and traffic blackholing, the present disclosure includes a new path attribute that is referred to herein as a “BGP Aggregate-Exception.” Of course, other names can be given to this path attribute and are contemplated herewith. The aggregating BGP speaker encodes this attribute and the failed network in a BGP update to advertise to its peers about the network failures. Upon receiving the message, the peers look for the alternative next-hop in a BGP routing database and install the new route in the data plane in order to redirect the traffic. This approach makes use of the longest-prefix matching forwarding lookup idea and installs the longer prefix in the data plane in order to redirect traffic to a more specific route.

FIG.6is a network diagram of the network10illustrating an aggregation exception with a network failure for a specific route, which is part of aggregation in iBGP. This is the same as inFIG.2except there is a BGP aggregation exception that is advertised. Specifically, various steps S1-S6are described inFIG.6with the aggregating router12A performing the steps S1-S2and the receiving router12C performing the steps S3-S6. Also, flows30,32,34with arrows are used to show summarized route advertisements30, the new aggregation exception NLRI32, and the data traffic34.

First, at step S1, upon detecting the fault16, the aggregating router12A has to determine that it advertised the summarized prefix on behalf of the specific fault16. At step S2, if there is an advertised summarized prefix associated with the fault, the aggregating router12A has to encode a new path attribute (37) in the BGP update and advertises a failed prefix NLRI in the BGP update message to its peers. For example, this failed prefix in this case is 10.10.2.0/24, and there is a notation such as NH: ˜A to note the failure at the aggregating node12A. Also, this new path attribute can use an unassigned value for the path attribute, such as, for example, New path attribute: AGGREGATE_EXCEPTION using Unassigned value—37 or any other unique value.

For the receiving router12C, at step S3, on receiving the BGP update with the “Aggregation-Exception” NLRI therein, the receiving router12C understands the message that the network had failed on the aggregating router12A to the prefix P2(10.10.2.0/24). At step S4, the receiving router12C looks into the BGP routing table to find the alternative path to the failed network other than the BGP aggregating router12A, which advertised the failure. In this example, for the prefix P2, there is an alternative NH to A via the router12B (address B.B.B.B). At step S5, the router12C programs the data plane for the failed network prefix with the new next-hop. Finally, at step S6, data traffic for the prefix gets forwarded to alternative next-hop.

FIG.7is a network diagram of the network10illustrating an aggregation exception with a network recovery after the fault16inFIG.6. Once the network fault16inFIG.6recovers, the aggregating router12A withdraws the “Aggregation-Exception NLRI” that had earlier been advertised. The receiving router12C deletes the “Aggregation Exception route” from the control plane and data plane, and the traffic falls back to the original path. Specifically, various steps S11-S16are described inFIG.7with the aggregating router12A performing the steps S11-S12and the receiving router12C performing the steps S13-S16.

At step S11, the aggregating router12A detects the recovery of the previously available route to the prefix P2. At step S12, the aggregating router12A withdraws the previously advertised “Aggregation-Exception” NLRI from the peers, e.g., P2: (withdraw) 10.10.2.0/24 (NH: ˜A). At step S13, the receiving router12C, on receiving the route withdrawal for “Aggregation-Exception” NLRI, understands the message that the network has been recovered on the aggregating router12C. At step S14, the receiving router12C removes the aggregation exception NLRI route from the BGP routing table. At step S15, the receiving router12C uninstalls the data plane entry for the prefix (previously failed). Finally, at step S16, the data traffic gets forwarded back to the aggregating router12A as the next-hop.

FIG.8is a network diagram of the network20illustrating an aggregation exception with a network failure for a specific route, which is part of aggregation in eBGP. Also, this shows the same fault24as inFIGS.4-5.FIG.9is a network diagram of the network20illustrating an aggregation exception with a failed network after the fault24inFIG.8. InFIG.8, after detecting the fault24, the router12C sends a BGP update with an “Aggregation-Exception” NLRI therein, namely 160.30.0.0/16, NH: Not Router12C. The router12D receives this NLRI and installs an alternate NH for this prefix in the data plane. InFIG.9, the router12D detects the fault24has cleared and sends a route withdrawal for “Aggregation-Exception” NLRI, namely Withdraw 160.30.0.0/16 Aggregate-Exception. Once withdrawal is processed, the traffic falls back to original path as before.

This solution could be further fine-tuned using Command Line Interfaces (CLIs) with global and neighbor level to control the advertisement of the “Aggregation-Exception” BGP updates. For example, a new CLI command can be introduced to switch on/off the behavior—per neighbor/global level, such as

bgp neighbor aggregate-exception enable

This can also be applicable to other address families—IPv4 Unicast, IPv4 Labeled-Unicast, VPN-IPv4, etc. The present disclosure mitigates the blackholing and sub-optimal routing. Also, this approach is agnostic to iBGP or eBGP and can be used in both intra-AS and inter-AS scenarios, i.e., wherever BGP summarization is being deployed.

There are two parts to the present disclosure, namely functionality at the aggregating node and at the receiving node. Of note, third-party routers can be aggregating nodes or receiving nodes. For full implementation, both would need to be configured, and this could be implemented proprietary or via standards, e.g., RFCs.

FIG.10is a flowchart of a process50for functionality at an aggregating node during a network failure. The process50includes having the router advertise specific routes over a BGP session to neighbors (steps51-52). Route aggregation can be configured (step53). With route aggregation, the router advertises only aggregated routes, not specific routes (step54). If the aggregating node detects a specific route failure affecting one or more aggregated routes (step55), the aggregating node advertises the “Aggregation Exception NLRI” route to previously advertised neighbors (step56). Of note, the failure or fault must affect less than all of the aggregated routes and the Aggregation Exception NLRI includes identification of the affected aggregated routes. If there is no fault (step55), no operation is performed (step57).

FIG.11is a flowchart of a process60for functionality at a receiving node during a network failure. The receiving node receives BGP NLRI updates (step61). If there is no received aggregated exception NLRI (step62), there is no operation to the data plane (step63), and any BGP NLRI update is processed as normal. If the BGP NLRI update includes an aggregated exception NLRI (step63), the receiving node checks if there are any selected aggregated routes with the same NH (step64). If not, there is no operation (step65). If so, the receiving node searches for alternative NH to individual routes (step66). If there are alternative NH to the prefixes (step67), the receiving node programs the data plane with the prefix and its new NH (step68). Otherwise, there is no operation (step69). Here, the data plane can be programmed to discard such as with a NH as null0 for the failed prefix, causing a local discard.

FIG.12is a flowchart of a process70for functionality at the aggregating node during network recovery. After a network recovery (step71), when there was an aggregation exception NLRI advertised (step72), the aggregating node sends a withdrawal of the aggregation exception NLRI (step73). Otherwise, there is no operation (step74).

FIG.13is a flowchart of a process80for functionality at the receiving node during network recovery. The receiving node receives the withdrawal of the aggregation exception NLRI (step81). The receiving node deletes the aggregation exception NLRI from the BGP routing table (step82), and uninstalls the specific prefix from the data plane (step83).

FIG.14is a flowchart of a process90for BGP route aggregation exception. The process90is described with reference to one of the routers12. The process90can be implemented as a method that includes steps, via a router configured to execute the steps, and via a non-transitory computer-readable medium that includes instructions that cause one or more processors to implement the steps.

The process90includes advertising, to Border Gateway Protocol (BGP) peers, of a first plurality of prefixes using BGP route aggregation or summarization (step91); detecting a failure that is local to the router affecting a prefix of the first plurality of prefixes (step92); and advertising an aggregation exception that identifies the prefix to all of the BGP peers (step93). The process90can further include detecting recovery of the failure (step94); and sending a withdrawal of the aggregation exception to all of the BGP peers (step95).

The process90can further include receiving an aggregation exception that identifies a second prefix that is part of a second plurality of prefixes that were advertised to the router using BGP aggregation (step96); and finding an alternate path for the second prefix and programming a data plane accordingly (step97). The process90can further include receiving a withdrawal of the aggregation exception for the second prefix (step98); and deleting the alternate path from a BGP routing table and from the data plane (step99). The aggregation exception can be a path attribute in a BGP update message.

Example Router

FIG.15is a block diagram of an example implementation of a router12. Those of ordinary skill in the art will recognizeFIG.15is a functional diagram in an oversimplified manner, and a practical embodiment may include additional components and suitably configured processing logic to support known or conventional operating features that are not described in detail herein.

In an embodiment, the router12is a packet switch, but those of ordinary skill in the art will recognize the systems and methods described herein can operate with other types of network elements and other implementations that support BGP aggregation. In this embodiment, the router12includes a plurality of modules102,104interconnected via an interface106. The modules102,104are also known as blades, line cards, line modules, circuit packs, pluggable modules, etc. and generally refer to components mounted on a chassis, shelf, etc. of a data switching device, i.e., the router12. Each of the modules102,104can include numerous electronic devices and/or optical devices mounted on a circuit board along with various interconnects, including interfaces to the chassis, shelf, etc.

Two example modules are illustrated with line modules102and a control module104. The line modules102include ports108, such as a plurality of Ethernet ports. For example, the line module102can include a plurality of physical ports disposed on an exterior of the module102for receiving ingress/egress connections. Additionally, the line modules102can include switching components to form a switching fabric via the interface106between all of the ports108, allowing data traffic to be switched/forwarded between the ports108on the various line modules102. The switching fabric is a combination of hardware, software, firmware, etc. that moves data coming into the router12out by the correct port108to the next router12. “Switching fabric” includes switching units in a node; integrated circuits contained in the switching units; and programming that allows switching paths to be controlled. Note, the switching fabric can be distributed on the modules102,104, in a separate module (not shown), integrated on the line module102, or a combination thereof.

The control module104can include a microprocessor, memory, software, and a network interface. Specifically, the microprocessor, the memory, and the software can collectively control, configure, provision, monitor, etc. the router12. The network interface may be utilized to communicate with an element manager, a network management system, etc. Additionally, the control module104can include a database that tracks and maintains provisioning, configuration, operational data, and the like.

Again, those of ordinary skill in the art will recognize the router12can include other components which are omitted for illustration purposes, and that the systems and methods described herein are contemplated for use with a plurality of different network elements with the router12presented as an example type of network element. For example, in another embodiment, the router12may include corresponding functionality in a distributed fashion. In a further embodiment, the chassis and modules may be a single integrated unit, namely a rack-mounted shelf where the functionality of the modules102,104is built-in, i.e., a “pizza-box” configuration. That is,FIG.15is meant to provide a functional view, and those of ordinary skill in the art will recognize actual hardware implementations may vary.

Example Controller

FIG.16is a block diagram of an example controller200, which can form a controller for the router12. The controller200can be part of the router12or a stand-alone device communicatively coupled to the router12. Also, the controller200can be referred to in implementations as a control module, a shelf controller, a shelf processor, a system controller, etc. The controller200can include a processor202, which is a hardware device for executing software instructions. The processor202can be any custom made or commercially available processor, a central processing unit (CPU), an auxiliary processor among several processors associated with the controller200, a semiconductor-based microprocessor (in the form of a microchip or chipset), or generally any device for executing software instructions. When the controller200is in operation, the processor202is configured to execute software stored within the memory, to communicate data to and from the memory, and to generally control operations of the controller200pursuant to the software instructions. The controller200can also include a network interface204, a data store206, memory208, an I/O interface210, and the like, all of which are communicatively coupled to one another and to the processor202.

The network interface204can be used to enable the controller200to communicate on a data communication network, such as to communicate to a management system, to the nodes12,100, and the like. The network interface204can include, for example, an Ethernet module. The network interface204can include address, control, and/or data connections to enable appropriate communications on the network. The data store206can store data, such as control plane information, provisioning data, Operations, Administration, Maintenance, and Provisioning (OAM&P) data, etc. The data store206can include any of volatile memory elements (e.g., random access memory (RAM, such as DRAM, SRAM, SDRAM, and the like)), nonvolatile memory elements (e.g., ROM, hard drive, flash drive, CDROM, and the like), and combinations thereof. Moreover, the data store206can incorporate electronic, magnetic, optical, and/or other types of storage media. The memory208can include any of volatile memory elements (e.g., random access memory (RAM, such as DRAM, SRAM, SDRAM, etc.)), nonvolatile memory elements (e.g., ROM, hard drive, flash drive, CDROM, etc.), and combinations thereof. Moreover, the memory208may incorporate electronic, magnetic, optical, and/or other types of storage media. Note that the memory208can have a distributed architecture, where various components are situated remotely from one another, but may be accessed by the processor202. The I/O interface210includes components for the controller200to communicate with other devices.

Moreover, some embodiments may include a non-transitory computer-readable medium having instructions stored thereon for programming a computer, server, appliance, device, one or more processors, circuit, etc. to perform functions as described and claimed herein. Examples of such non-transitory computer-readable medium include, but are not limited to, a hard disk, an optical storage device, a magnetic storage device, a Read-Only Memory (ROM), a Programmable ROM (PROM), an Erasable PROM (EPROM), an Electrically EPROM (EEPROM), Flash memory, and the like. When stored in the non-transitory computer-readable medium, software can include instructions executable by one or more processors (e.g., any type of programmable circuitry or logic) that, in response to such execution, cause the one or more processors to perform a set of operations, steps, methods, processes, algorithms, functions, techniques, etc. as described herein for the various embodiments.