The enhanced feasible-path uRPF (EFP-uRPF) method adds greater operational robustness and efficacy to existing uRPF methods discussed in
Section 2. That is because it avoids dropping legitimate data packets and compromising directionality. The method is based on the principle that if BGP updates for multiple prefixes with the same origin AS were received on different interfaces (at border routers), then incoming data packets with source addresses in any of those prefixes should be accepted on any of those interfaces. The EFP-uRPF method can be best explained with an example, as follows:
Let us say, in its Adj-RIBs-In [
RFC 4271], a border router of ISP-A has the set of prefixes {Q1, Q2, Q3}, each of which has AS-x as its origin and AS-x is in ISP-A's customer cone. In this set, the border router received the route for prefix Q1 over a customer-facing interface while it learned the routes for prefixes Q2 and Q3 from a lateral peer and an upstream transit provider, respectively. In this example scenario, the enhanced feasible-path uRPF method requires Q1, Q2, and Q3 be included in the RPF list for the customer interface under consideration.
Thus, the EFP-uRPF method gathers feasible paths for customer interfaces in a more precise way (as compared to the feasible-path uRPF) so that all legitimate packets are accepted while the directionality property is not compromised.
The above-described EFP-uRPF method is recommended to be applied on customer interfaces. It can also be extended to create the RPF lists for lateral peer interfaces. That is, the EFP-uRPF method can be applied (and loose uRPF avoided) on lateral peer interfaces. That will help to avoid compromising directionality for lateral peer interfaces (which is inevitable with loose uRPF; see
Section 2.4).
Looking back at Scenarios 1 and 2 (Figures [
1] and [
2]), the EFP-uRPF method works better than the other uRPF methods. Scenario 3 (
Figure 3) further illustrates the enhanced feasible-path uRPF method with a more concrete example. In this scenario, the focus is on operation of the EFP-uRPF at ISP4 (AS4). ISP4 learns a route for prefix P1 via a C2P interface from customer ISP2 (AS2). This route for P1 has origin AS1. ISP4 also learns a route for P2 via another C2P interface from customer ISP3 (AS3). Additionally, AS4 learns a route for P3 via a lateral P2P interface from ISP5 (AS5). Routes for all three prefixes have the same origin AS (i.e., AS1). Using the enhanced feasible-path uRPF scheme and given the commonality of the origin AS across the routes for P1, P2, and P3, AS4 includes all of these prefixes in the RPF list for the customer interfaces (from AS2 and AS3).
+----------+ P3[AS5 AS1] +------------+
| AS4(ISP4)|<---------------| AS5(ISP5) |
+----------+ (P2P) +------------+
/\ /\ /\
/ \ /
P1[AS2 AS1]/ \P2[AS3 AS1] /
(C2P)/ \(C2P) /
/ \ /
+----------+ +----------+ /
| AS2(ISP2)| | AS3(ISP3)| /
+----------+ +----------+ /
/\ /\ /
\ / /
P1[AS1]\ /P2[AS1] /P3[AS1]
(C2P)\ /(C2P) /(C2P)
\ / /
+----------------+ /
| AS1(customer) |/
+----------------+
P1, P2, P3 (prefixes originated)
Consider that data packets (sourced from AS1)
may be received at AS4 with a source address
in P1, P2, or P3 via any of the neighbors (AS2, AS3, AS5):
* Feasible-path uRPF fails
* Loose uRPF works (but not desirable)
* Enhanced feasible-path uRPF works best
The underlying algorithm in the solution method described above (
Section 3.1) can be specified as follows (to be implemented in a transit AS):
-
Create the set of unique origin ASes considering only the routes in the Adj-RIBs-In of customer interfaces. Call it Set A = {AS1, AS2, ..., ASn}.
-
Considering all routes in Adj-RIBs-In for all interfaces (customer, lateral peer, and transit provider), form the set of unique prefixes that have a common origin AS1. Call it Set X1.
-
Include Set X1 in the RPF list on all customer interfaces on which one or more of the prefixes in Set X1 were received.
-
Repeat Steps 2 and 3 for each of the remaining ASes in Set A (i.e., for ASi, where i = 2, ..., n).
The above algorithm can also be extended to apply the EFP-uRPF method to lateral peer interfaces. However, it is left up to the operator to decide whether they should apply the EFP-uRPF or loose uRPF method on lateral peer interfaces. The loose uRPF method is recommended to be applied on transit provider interfaces.
The following operational recommendations will make the operation of the enhanced feasible-path uRPF robust:
For multihomed stub AS:
-
A multihomed stub AS should announce at least one of the prefixes it originates to each of its transit provider ASes. (It is understood that a single-homed stub AS would announce all prefixes it originates to its sole transit provider AS.)
For non-stub AS:
-
A non-stub AS should also announce at least one of the prefixes it originates to each of its transit provider ASes.
-
Additionally, from the routes it has learned from customers, a non-stub AS SHOULD announce at least one route per origin AS to each of its transit provider ASes.
It should be observed that in the absence of ASes adhering to above recommendations, the following example scenario, which poses a challenge for the enhanced feasible-path uRPF (as well as for traditional feasible-path uRPF), may be constructed. In the scenario illustrated in
Figure 4, since routes for neither P1 nor P2 are propagated on the AS2-AS4 interface (due to the presence of NO_EXPORT Community), the enhanced feasible-path uRPF at AS4 will reject data packets received on that interface with source addresses in P1 or P2. (For a little more complex example scenario, see slide #10 in [
Sriram-URPF].)
+----------+
| AS4(ISP4)|
+----------+
/\ /\
/ \ P1[AS3 AS1]
P1 and P2 not / \ P2[AS3 AS1]
propagated / \ (C2P)
(C2P) / \
+----------+ +----------+
| AS2(ISP2)| | AS3(ISP3)|
+----------+ +----------+
/\ /\
\ / P1[AS1]
P1[AS1] NO_EXPORT \ / P2[AS1]
P2[AS1] NO_EXPORT \ / (C2P)
(C2P) \ /
+----------------+
| AS1(customer) |
+----------------+
P1, P2 (prefixes originated)
Consider that data packets (sourced from AS1)
may be received at AS4 with a source address
in P1 or P2 via AS2:
* Feasible-path uRPF fails
* Loose uRPF works (but not desirable)
* Enhanced feasible-path uRPF with Algorithm A fails
* Enhanced feasible-path uRPF with Algorithm B works best
Adding further flexibility to the enhanced feasible-path uRPF method can help address the potential limitation identified above using the scenario in
Figure 4 (
Section 3.3). In the following, "route" refers to a route currently existing in the Adj-RIBs-In. Including the additional degree of flexibility, the modified algorithm called Algorithm B (implemented in a transit AS) can be described as follows:
-
Create the set of all directly connected customer interfaces. Call it Set I = {I1, I2, ..., Ik}.
-
Create the set of all unique prefixes for which routes exist in Adj-RIBs-In for the interfaces in Set I. Call it Set P = {P1, P2, ..., Pm}.
-
Create the set of all unique origin ASes seen in the routes that exist in Adj-RIBs-In for the interfaces in Set I. Call it Set A = {AS1, AS2, ..., ASn}.
-
Create the set of all unique prefixes for which routes exist in Adj-RIBs-In of all lateral peer and transit provider interfaces such that each of the routes has its origin AS belonging in Set A. Call it Set Q = {Q1, Q2, ..., Qj}.
-
Then, Set Z = Union(P,Q) is the RPF list that is applied for every customer interface in Set I.
When Algorithm B (which is more flexible than Algorithm A) is employed on customer interfaces, the type of limitation identified in
Figure 4 (
Section 3.3) is overcome and the method works. The directionality property is minimally compromised, but the proposed EFP-uRPF method with Algorithm B is still a much better choice (for the scenario under consideration) than applying the loose uRPF method, which is oblivious to directionality.
So, applying the EFP-uRPF method with Algorithm B is recommended on customer interfaces for the challenging scenarios, such as those described in
Section 3.3.
It is worth emphasizing that an indirect part of the proposal in this document is that RPF filters may be augmented from secondary sources. Hence, the construction of RPF lists using a method proposed in this document (Algorithm A or B) can be augmented with data from Route Origin Authorization (ROA) [
RFC 6482], as well as Internet Routing Registry (IRR) data. Special care should be exercised when using IRR data because it is not always accurate or trusted. In the EFP-uRPF method with Algorithm A (see
Section 3.1.1), if a ROA includes prefix Pi and ASj, then augment the RPF list of each customer interface on which at least one route with origin ASj was received with prefix Pi. In the EFP-uRPF method with Algorithm B, if ASj belongs in Set A (see Step #3
Section 3.4) and if a ROA includes prefix Pi and ASj, then augment the RPF list Z in Step 5 of Algorithm B with prefix Pi. Similar procedures can be followed with reliable IRR data as well. This will help make the RPF lists more robust about source addresses that may be legitimately used by customers of the ISP.
The existing RPF checks in edge routers take advantage of existing line card implementations to perform the RPF functions. For implementation of the enhanced feasible-path uRPF, the general necessary feature would be to extend the line cards to take arbitrary RPF lists that are not necessarily the same as the existing FIB contents. In the algorithms (Sections [
3.1.1] and [
3.4]) described here, the RPF lists are constructed by applying a set of rules to all received BGP routes (not just those selected as best path and installed in the FIB). The concept of uRPF querying an RPF list (instead of the FIB) is similar to uRPF querying a VRF table (see
Section 2.5).
The techniques described in this document require that there should be additional memory (i.e., ternary content-addressable memory (TCAM)) available to store the RPF lists in line cards. For an ISP's AS, the RPF list size for each line card will roughly equal the total number of originated prefixes from ASes in its customer cone (assuming Algorithm B in
Section 3.4 is used). (Note: EFP-uRPF with Algorithm A (see
Section 3.1.1) requires much less memory than EFP-uRPF with Algorithm B.)
The following table shows the measured customer cone sizes in number of prefixes originated (from all ASes in the customer cone) for various types of ISPs [
Sriram-RIPE63]:
Type of ISP |
Measured Customer Cone Size in # Prefixes (in turn this is an estimate for RPF list size on the line card)
|
Very Large Global ISP #1 |
32393 |
Very Large Global ISP #2 |
29528 |
Large Global ISP |
20038 |
Mid-size Global ISP |
8661 |
Regional ISP (in Asia) |
1101 |
Table 1: Customer Cone Sizes (# Prefixes) for Various Types of ISPs
For some super large global ISPs that are at the core of the Internet, the customer cone size (# prefixes) can be as high as a few hundred thousand [
CAIDA], but uRPF is most effective when deployed at ASes at the edges of the Internet where the customer cone sizes are smaller, as shown in
Table 1.
A very large global ISP's router line card is likely to have a FIB size large enough to accommodate 2 million routes [
Cisco1]. Similarly, the line cards in routers corresponding to a large global ISP, a midsize global ISP, and a regional ISP are likely to have FIB sizes large enough to accommodate about 1 million, 0.5 million, and 100k routes, respectively [
Cisco2]. Comparing these FIB size numbers with the corresponding RPF list size numbers in
Table 1, it can be surmised that the conservatively estimated RPF list size is only a small fraction of the anticipated FIB memory size under relevant ISP scenarios. What is meant here by relevant ISP scenarios is that only smaller ISPs (and possibly some midsize and regional ISPs) are expected to implement the proposed EFP-uRPF method since it is most effective closer to the edges of the Internet.
BGP routing announcements can exhibit transient behavior. Routes may be withdrawn temporarily and then reannounced due to transient conditions, such as BGP session reset or link failure recovery. To cope with this, hysteresis should be introduced in the maintenance of the RPF lists. Deleting entries from the RPF lists
SHOULD be delayed by a predetermined amount (the value based on operational experience) when responding to route withdrawals. This should help suppress the effects due to the transients in BGP.
Depending on the scenario, an ISP or enterprise AS operator should follow one of the following recommendations concerning uRPF/SAV:
-
For directly connected networks, i.e., subnets directly connected to the AS, the AS under consideration SHOULD perform ACL-based SAV.
-
For a directly connected single-homed stub AS (customer), the AS under consideration SHOULD perform SAV based on the strict uRPF method.
-
For all other scenarios:
-
The EFP-uRPF method with Algorithm B (see Section 3.4) SHOULD be applied on customer interfaces.
-
The loose uRPF method SHOULD be applied on lateral peer and transit provider interfaces.
It is also recommended that prefixes from registered ROAs and IRR route objects that include ASes in an ISP's customer cone
SHOULD be used to augment the pertaining RPF lists (see
Section 3.5 for details).
The EFP-uRPF method with Algorithm A is not mentioned in the above set of recommendations. It is an alternative to EFP-uRPF with Algorithm B and can be used in limited circumstances. The EFP-uRPF method with Algorithm A is expected to work fine if an ISP deploying it has only multihomed stub customers. It is trivially equivalent to strict uRPF if an ISP deploys it for a single-homed stub customer. More generally, it is also expected to work fine when there is absence of limitations, such as those described in
Section 3.3. However, caution is required for use of EFP-uRPF with Algorithm A because even if the limitations are not expected at the time of deployment, the vulnerability to change in conditions exists. It may be difficult for an ISP to know or track the extent of use of NO_EXPORT (see
Section 3.3) on routes within its customer cone. If an ISP decides to use EFP-uRPF with Algorithm A, it should make its direct customers aware of the operational recommendations in
Section 3.2. This means that the ISP notifies direct customers that at least one prefix originated by each AS in the direct customer's customer cone must propagate to the ISP.
On a lateral peer interface, an ISP may choose to apply the EFP-uRPF method with Algorithm A (with appropriate modification of the algorithm). This is because stricter forms of uRPF (than the loose uRPF) may be considered applicable by some ISPs on interfaces with lateral peers.