Troubleshooting Outbound IP Traffic Flow Issues Because of BGP Policies
BGP’s real power is in managing IP traffic flows coming in and going out of the AS. BGP in general and Cisco IOS Software in particular offer a great deal of flexibility in manipulating BGP attributes LOCAL_PREFERENCE, MED, and so forth to control BGP best-path calculation. This best-path decision determines how traffic exits the AS. With the large size of BGP networks today, it is crucial that BGP operators understand how BGP attributes should be managed.
This section discusses what problems can arise while trying to manage traffic leaving the AS.
Here is the list of the most common problems encountered in managing outbound traffic flow:
- Multiple exit points exist, but traffic goes out through one or a few exit routers.
- Traffic takes a different interface from what is shown in the routing table.
- A multiple BGP connection exists to the same BGP neighbor, but traffic goes out through only one connection.
- Asymmetrical routing occurs and it causes a problem especially when NAT and time-sensitive applications are used.
Problem: Multiple Exit Points Exist but Traffic Goes Out Through One or Few Exit Routers—Cause: BGP Policy Definition Causes Traffic to Exit from One Place
This problem commonly is seen when an AS receives the same prefix announcements from mul-tiple EBGP connections but traffic destined to those prefixes prefers only one or two exit points.
As illustrated by Figure 15-34, AS 109 has multiple connections to other autonomous systems. AS 109 has three EBGP connections with AS 110, two with AS 111, and one with AS 112. AS 111 is peering with AS 110 and AS 112.
Prefixes P1, P2, and P3 are originated by AS 110 and are advertised to EBGP neighboring autonomous systems 109, 111, and 112. AS 109 receive updates for these prefixes from multiple locations—three updates from AS 110, two from AS 111, and one from AS 112. Even with such redundant BGP advertisements for Prefixes P1, P2, and P3, all the traffic for these prefixes from AS 110 might take only one or two exit points. The rest of the connections are underutilized. Such a scenario typically results in overutilized links because traffic tends to exit from one or two preferred paths, as governed by BGP policy of AS 109.
Figure 15-35 shows the flowchart to follow to resolve this problem.
AS 109 BGP installs its best path for Prefixes P1, P2, and P3 in the IP routing table, and traffic destined for these prefixes will look in the routing tables for routers in AS 109. It is crucial to understand how BGP selects the best path; to do this, BGP operators must understand how BGP path attributes work. These attributes include AS_PATH, LOCAL_PREFERENCE, MED, ORIGIN, and so on, as discussed in detail in Chapter 14.
This section discusses how AS_PATH affects traffic patterns in AS 109 for Prefixes P1, P2, and P3. It is assumed that AS 109 is not configured with any additional BGP policies.
Recall that AS_PATH contains a list of autonomous systems that an update has traversed.
This section shows the AS_PATH list of R1 and R4 as an example; you are encouraged to come up with the AS_PATH list for R2 and R3 as an exercise.
R1 has two updates for Prefixes P1, P2, and P3 and the AS_PATH would like the following:
- 110— Path from a direct connection between R1 and AS 110. This would be an EBGP path with an AS_PATH length of 1.
- 110— Path from R2. This would be an IBGP path with an AS_PATH length of 1.
Out of these two paths, the first one will be selected as best because, with the same AS_PATH length, the EBGP path is better than the IBGP path.
R4 AS_PATH would like the following:
- 112 111 110— Path from R4 and AS 112 connection. This is an EBGP path with an AS_PATH length of 3.
- 111 110— Path from R4 and AS 111 connection. This is an EBGP path with an AS_PATH length of 2.
- 110— Path from R1. This would be an IBGP path with an AS_PATH length of 1.
- 110— Path from R2. This would be an IBGP path with an AS_PATH length of 1.
- 110— Path from R3. This would be an IBGP path with an AS_PATH length of 1.
The AS_PATH length of the third, fourth, and fifth paths is 1, and best-path selection will be based on IBGP next-hop cost through the IGP. If you assume that the third path from R1 wins, all traffic from R4 destined for Prefixes P1, P2, and P3 will exit from R1 and the AS 110 connection, leaving path 1, 2, 4, and 5 links not used at all for Prefixes P1, P2, and P3.
Refer back to Chapter 14 for the full description of how the best-path calculation method works.
This example could be a real-life one in which AS 110 is a big Tier 1 ISP that peers BGP with just about all other ISPs, big or small. Chances are, AS 110 will provide AS 109 with most of the BGP prefixes (P1, P2, and P3) with the shortest AS_PATH. This will influence AS 109’s BGP best-path procedure to pick AS 110 as the first preference to carry traffic for P1, P2, and P3, which, in turn, results in clogging links that connect AS 109 to AS 110 directly. Because AS 109 has not made any BGP policy change for P1, P2, and P3, AS 109 is at the mercy of BGP neighbors and is left with no control of traffic flow from its AS 109 to P1, P2, and P3. The links from AS 109 to AS 111, 112, and so forth are used minimally, resulting in wasted high-cost bandwidth.
Solution
If a situation arises in which one BGP neighbor (AS 110, in this example) is attracting all the traffic from AS 109 to Prefixes P1, P2, and P3, AS 109 BGP operators should define local policies within AS 109 to overcome this behavior.
Using the BGP attribute LOCAL_PREFERENCE is done commonly to predictably control the traffic leaving the local AS (AS 109, in this example). AS 109 can choose to make AS 111 and AS 112 carry traffic for Prefix P2 and P3, respectively, and can leave the rest for AS 110.
Example 15-70 shows an example of how R2 in AS 109 can change LOCAL_PREFERENCE on a per-prefix basis with a neighbor in AS 111 to make AS 111 attract all the traffic for P2.
Example 15-70 Implementing the LOCAL_PREFERENCE Attribute to Control the Traffic Flow
R2# router bgp 109 neighbor 172.16.1.1 remote-as 11 neighbor 172.16.1.1 route-map influencing_traffic in access-list 1 permit P2 wild_card access-list 2 permit any route-map influencing_traffic permit 10 match ip address set local-preference 200 ! route-map influencing_traffic permit 20 match ip address 2 set local-preference 90
Access list 1 is permitting Prefix P2. The actual access list would have the real IP prefix; P2 is used just for illustration purposes. The first sequence 10 of route-map influencing_traffic allows P2 to be set with a LOCAL_PREFERENCE of 200, and sequence 20 of the same route map sets a LOCAL_PREFERENCE of 90 for the other prefixes (P1 and P3). This results in making P2’s LOCAL_PREF 200, thus making AS 111 path the best path for P2 only. Setting the P1 and P3 LOCAL_PREF attributes to 90 would have no effect because, in Cisco IOS Software, the default value for LOCAL_PREFERENCE is 100; AS 110 will be picked as the best path for P1 and P3.
With the size of the BGP routing table today, it is difficult to manage traffic on a prefix-by-prefix basis. Typically, BGP speakers change the LOCAL_PREFERENCE value based on the AS_PATH list. AS 109 might decide that all prefixes that come from AS 111 that have in the AS_PATH list either “111” or “111 and one more AS” should be selected as best paths through AS 111 neighbors. Therefore, AS 110 and AS 112 should not be the preferred carriers for prefixes that are originated by AS 111 or that are coming from an AS directly peering with AS 111.
Manipulating BGP attributes (LOCAL_PREFERENCE) based on AS_PATH list requires the use of the as_path access-list command, which uses UNIX-like regular expressions.
Example 15-71 shows a configuration example of Router R2 in AS 109 that changes the LOCAL_PREFERENCE of all the prefixes of those received from AS 111 that have in the AS_PATH list either “111” or “111 and one more AS.”
Example 15-71 LOCAL_PREFERENCE Manipulation Using AS_PATH List
R2# router bgp 109 neighbor 172.16.1.1 remote-as 111 neighbor 172.16.1.1 route-map influencing_traffic in ! ip as-path access-list 1 permit ^111$ ip as-path access-list 1 permit ^111 [0-9]+$ ip as-path access-list 2 permit .* route-map influencing_traffic permit 10 match as-path 1 set local-preference 200 ! route-map influencing_traffic permit 20 match as-path 2 set local-preference 90
The first sequence number, 10, of route-map influencing_traffic looks at AS path 1, which permits any prefix that has in its AS_PATH list either “111” or “111 and one more AS”; it then sets the LOCAL_PREFERENCE to 200, making links to AS 111 the preferred path from the AS 109 BGP view. The regular expression ^111$ means that AS_PATH should contain only one AS, and that is AS 111.
The expression ^111 [0-9]+$ means that AS_PATH should contain two autonomous systems, but the first one must be AS 111; the second one can be any AS. The expression .* means any AS.
The second sequence number, 20, of route-map influencing_traffic looks at AS path 2, which permits everything and makes the LOCAL_PREFERENCE lower than the default of 100 so that other carriers can pick the rest of the traffic.
BGP attribute manipulation based on AS_PATH is a fairly common practice among savvy BGP operators because wildcard operations allow covering a larger number of prefixes to be checked in fewer lines of configuration.
In essence, it is crucial that BGP operators manage their traffic flow by making necessary BGP attribute changes to influence the BGP path-selection process. This ensures predictable traffic management within an AS and allows future upgrades in bandwidth to easily be judged.
Problem: Traffic Takes a Different Interface from What Shows in Routing Table—Cause: Next Hop of the Route Is Reachable Through Another Path
In some scenarios, BGP and the routing table path to a certain destination prefix show Exit A, but actual traffic leaves through Exit B. Packet forwarding to a destination takes place from the routing table, and network operators do expect to see this behavior. However, in most cases, the next hops of prefixes in the routing table are not directly connected and packet forwarding eventually takes place based on the next-hop path. Figure 15-36 tries to explain one such simple case.
Figure 15-36 shows that R1 and R2 are two route reflectors, with R6 and R8 as their clients. R6 is advertising 100.100.100.0/24 to R2 and R1, and both reflect this advertisement to R8 with a next hop of 172.16.126.6. Now, assume that R8 has a BGP policy that chooses the path for 100.100.100.0/24 from R2 (the upper path) as the best path that it will install in its routing table. However, in the same router, R8, the best IGP path to reach 172.16.126.6 (next hop of 100.100.100.0/24) is through R1 (the bottom path).
All traffic destined from or through R8 to 100.100.100.0/24 will take the bottom path; even though the best BGP-selected path in the routing table is the upper path, it will not be used.
Therefore, forwarding of IP packets in a router eventually happens by looking at the path for the next hop (172.16.126.6) of the actual path (100.100.100.0/24). In Cisco IOS Software, recursive lookup is the term used for finding out the path based on the next hop and the actual prefix. In some cases, more than one recursive lookup must be done to figure out the actual physical path that packets take to reach the destination.
Figure 15-37 shows the flowchart to follow to resolve this problem.
Debugs and Verification
Example 15-72 shows the output of 100.100.100.0/24 in R8. The next hop is 172.16.126.6. When traffic is sent to 100.100.100.0/24, it actually is sent to the interface that provides a better route for 172.16.126.6.
Example 15-72 BGP and Routing Table Output for 100.100.100.0/24 Shows Best Path Through R2
R8#show ip bgp 100.100.100.0 BGP routing table entry for 100.100.100.0/24, version 5870 Paths: (1 available, best #1, table Default-IP-Routing-Table) Not advertised to any peer Local 172.16.126.6 (metric 20) from 172.16.126.2 (172.16.126.2) Origin IGP, metric 0, localpref 100, valid, internal, best
In R8, 172.16.126.6 is the next hop for 100.100.100.0/24 advertised by R2 and is considered the best route; therefore, it will be installed in the IP routing table.
Example 15-73 shows that the best way to reach 172.16.126.6, the next hop of 100.100.100.0/24, is through R1, not through R2.
Example 15-73 show ip route Command Output Shows the Best Route to Reach 172.16.126.6
R8#show ip route 172.16.126.6 Routing entry for 172.16.126.0/24 Known via "static", distance 1, metric 0 Routing Descriptor Blocks: * 172.16.18.1 Route metric is 0, traffic share count is 1
The highlighted 172.16.18.1 is the next hop for 172.16.126.6 (next hop of 100.100.100.0/24).
Therefore, all traffic from or through R8 destined for 100.100.100.0/24 will go through 172.16.18.1 (R1).
Example 15-74 shows the output of a traceroute done from R8 to 100.100.100.1. The traffic flows through 172.16.18.1, which is R1.
Example 15-74 traceroute Command Output Shows Traffic Going from R1 Instead of R2
R8#traceroute 100.100.100.1 Type escape sequence to abort. Tracing the route to 100.100.100.1 1 172.16.18.1 4 msec 4 msec 4 msec 2 172.16.126.6 4 msec 8 msec 8 msec 3 172.16.126.6 4 msec 8 msec 8 msec
Solution
A router might provide a route to BGP neighbor but might never be in a forwarding path to reach that route. This is because packets are forwarded to the next-hop address of the actual route, which might not be the same router that gave the route in the first place.
If routing and forwarding paths need to match, care must be taken in how next-hop addresses are learned through IGP. To fix the problem in Figure 15-36, R8 should have an IGP path for 172.16.126.6 (next hop of 100.100.100.0/24) through R2.
Problem: Multiple BGP Connections to the Same BGP Neighbor AS, but Traffic Goes Out Through Only One Connection—Cause: BGP Neighbor Is Influencing Outbound Traffic by Sending MED or Prepended AS_PATH
Typically, BGP networks are multihomed to different ISPs or the same ISP to provide redundancy or to load-share traffic. In some scenarios, the BGP network might be dual homed to the same ISP and might be running BGP with that ISP. Instead of load sharing traffic to the ISP over multiple connections, traffic might exit only from one connection.
These connections might be of equal bandwidth or might be different.
If the multiple EBGP connection links are of equal bandwidth and traffic exits from only one of those EBGP connections, this is not desirable and can lead to severe performance degradation because of packet loss and round-trip delays over the congested link. If the EBGP connections are of different bandwidth—say, T3 (45 Mbps) and T1 (1.5 Mbps)—it might be desirable for all traffic to go out through the T3 exit point. This section discusses the issue in which all EBGP connections going to the same ISP are of equal bandwidth but traffic goes out from only one of those links.
In the network illustrated in Figure 15-38, AS 109 has three EBGP peerings with AS 110, and AS 110 is advertising the same prefixes, P1, P2, P3, and so forth, at all peering points. However, all traffic from AS 109 destined for these prefixes uses a single exit point, X, with AS 110. This results in congestion at X and unnecessary usage of the AS 109 backbone.
Figure 15-39 shows the flowchart to follow to resolve this problem.
Typically, EBGP speakers agree on sending and accepting MEDs from each other. However, AS 110 might send a lower MED to AS 109 for all its prefixes at connection X. This would result in AS 109 choosing Exit X as a best path to reach Prefixes P1, P2, and P3. Throughout the BGP domain of AS 109, all BGP speakers install Exit X as a next hop for all routes, P1, P2, and P3. All traffic to these prefixes originating or traversing through AS 109 choose Exit X.
This results in clogging Exit X, and traffic uses available bandwidth in the AS 109 backbone. Notice that exit points Y and Z are left unused for traffic destined for Prefixes P1, P2, and P3.
Solution
You can address this problem a number of ways:
- Request AS 110 to send the proper MED for each prefix.
- Don’t accept MED from AS 110.
- Manually change LOCAL_PREFERENCE for P1, P2, and P3 at all the exit points, X, Y, and Z.
Request AS 110 to Send the Proper MED for Each Prefix
MED exchange with an EBGP peer is a tricky and bilateral game. Typically, BGP carriers accept MEDs only on a mutual basis in a process in which both carriers accept each other’s MED. Accepting MED means that BGP carriers carry each other’s traffic through the backbone and try to route the traffic in an optimal fashion.
If this mutual agreement takes place between AS 109 and AS 110, AS 109 can request AS 110 to send proper MEDs for prefixes announced. For example, if Prefix P1 is closer to Exit X, AS 110 should send a MED for P1 at X. A similar process should take place for P2 at Y and P3 at Z, if they are closer there. Traffic destined for Prefixes P1, P2, and P3 will ride the AS 109 backbone the most and enter AS 110 at the optimal exit from the AS 109 BGP speaker’s view.
Don’t Accept MED from AS 110
Request AS 110 either to not send the MED or to manually set the MED to 0 at peering points X, Y, and Z and for all prefixes from AS 110. This results in AS 109 picking the closest exit point, X, Y, or Z, for Prefixes P1, P2, and P3 through the lowest IGP (OSPF, IS-IS, and so on) cost to reach these exit points. Manually setting the MED to 0 can be done through a route map, as demonstrated in Example 15-75.
Example 15-75 Manually Setting the MED to 0 to Override Any Advertised MED from AS 110
route-map influencing_traffic permit 10 set metric 0 ! R1# router BGP 109 neighbor 4.4.4.4 remote-as 110 neighbor 4.4.4.4 route-map influencing_traffic in
This route map should be applied at all EBGP connections between AS 109 and AS 110. Example 15-75 shows this route map applied only between R1 and R4.
The configuration in Example 15-75 sets the MED value for all the prefixes from AS 110 to 0. Now, BGP speakers in AS 109 use the IGP cost as a tiebreaker in the BGP best-path selection process. This results in traffic destined to Prefixes P1, P2, and P3 choosing the closest exit point.
Manually Change LOCAL_PREFERENCE for P1, P2, and P3 at All the Exit Points X, Y, and Z
To use this solution, AS 109 must know which exit point is closer to which prefix.
For example, if Prefix P1 is closer to exit point X, AS 109 should make the LOCAL_PREFERENCE higher for Prefix P1 at X. This method can be used for P2 and P3 if they are closer to Y and Z, respectively.
Example 15-76 shows a sample configuration at exit point X to change the LOCAL_PREFERENCE higher for P1 than the default value of 100.
Example 15-76 Setting the LOCAL_PREFERENCE Value Higher to Select the Best Exit Point
R1# router BGP 109 neighbor 4.4.4.4 remote-as 110 neighbor 4.4.4.4 route-map influencing_traffic in route-map influencing_traffic permit 10 match ip address 1 set local-preference 200 ! route-map influencing_traffic permit 20 set local-preference 100
In Example 15-76, the route map influencing traffic is applied between R1 and R4. Access list 1, not shown, permits Prefix P1 only. Therefore, for P1, the LOCAL_PREF will be 200; for the rest of the prefixes, it will be the default, which is 100. A similar route map with proper prefix permitting in access list 1 needs to be applied at all EBGP connections between AS 109 and AS 110.
With the configuration addition in Example 15-76, Prefix P1 gets a LOCAL_PREF of 200 at R1, and all routers in AS 109 receive Prefix P1 with a LOCAL_PREF of 200. R1 and all routers in AS 109 select R1 as an exit point to reach P1 because of the higher LOCAL_PREFERENCE.
This method does not scale well in large BGP networks in which BGP speakers advertise and receive thousands of prefixes. Changing the LOCAL_PREFERENCE for each prefix could become cumbersome. A situation might arise in which AS 110 Prefixes P1, P2, and P3 also are advertised by another EBGP speaker—say, AS 111. AS 109 might set a higher LOCAL_PREFERENCE for AS 111 than from AS 110. In this situation, traffic from AS 109 destined for P1, P2, and P3 take AS 111 as an exit point, resulting in suboptimal routing. AS 109 must ensure that AS 110 Prefixes P1, P2, and P3 receive higher LOCAL_PREFERENCE from X, Y, and Z.
Problem: Asymmetrical Routing Occurs and Causes a Problem Especially When NAT and Time-Sensitive Applications Are Used—Cause: Outbound and Inbound Advertisement
Asymmetric routing means that packets flowing to a given destination don’t use the same exit point as the packets coming back from that same destination. This is not a problem in itself, but it can cause some issues when Network Address Translation (NAT) or a time-sensitive application is involved.
Symmetrical routing is probably one of hardest network policies to achieve. Figure 15-40 shows a network in which asymmetrical routing occurs.
shows a network setup composed of AS 109 and AS 110, and AS 110 has private IP addressing in the 10.0.0.0 network. AS 110 has two exit points, R1 and R2; however, R1 is the only router performing NAT for any packets sourcing from inside AS 110. In Figure 15-40, the 10.1.1.1 private IP address is translated to 131.108.1.1 at R1 when 10.1.1.1 is sending IP traffic to prefix P in AS 109. From the figure, it is obvious that this packet will enter AS 109 at Interface X of Router R3 and that this packet might exit from Interface Y of R4.
This might happen for multiple reasons and its results could be severe, the most common of which are listed here:
- AS 109 BGP policy might dictate that all AS 110 traffic should exit from Y.
- AS 110 might influence AS 109 by using MED or AS_PATH prepend to receive all traffic from AS 109 at Exit Y.
- AS 109 BGP policy might govern the closest exit policy for all AS 110 traffic. For Router R3 in AS 109, the closest exit is Y, regardless of where the destination, 131.108.1.1, is.
When R2 receives the returned packet destined for 131.108.1.1, it has no NAT entry to translate back to 10.1.1.1 and it simply drops this packet.
The link between R1 and R3 is of bigger bandwidth but the link between R2 and R4 has small bandwidth. The return traffic from R2 to R4 could add significant delays in the overall round-trip time of the packet from AS 109 to AS 110.
Debugs and Verification
Because packet drops and sluggish round-trip times are observed in AS 109, administrators in AS 109 must figure out a way to determine if asymmetrical routing is occurring. A simple ping from R1 to Prefix P in AS 110 will not help because reply packets will never arrive back at R1; instead, they will be coming back at R2. Administrators either would have to sniff the packets at R1 using sniffers or would run the debug ip packet command to observe whether the packets are going through R1 to reach Prefix P in AS 110 but are not coming back. Any debugs in Cisco IOS Software must be run with extreme caution because too much output can disturb the performance of the router. If such packet sniffing is done at R2 in AS 109, administrators can observe that packets are returning from Prefix P and are destined to addresses in AS 109. This can assure them that IP traffic is asymmetrical.
Another approach is to use traceroute; however, the problem with traceroute is that it provides the traffic path only in one direction—from source to destination (AS 109 to AS 110). In asymmetrical routing, administrators are more interested in the direction of traffic from destination to source (AS 110 to AS 109). This can be achieved only if AS 110 issues a traceroute to the destination in AS 109 and AS 109 administrators observe the output.
Solution
The asymmetrical routing issue is a fairly difficult problem to tackle and sometimes is un-avoidable. Asymmetrical routing might be an issue in cases of NAT when only one device maintains the NAT table; therefore, packets must come in and out of the same device. Time-sensitive applications also might face problems when the exit path offers good throughput but the entry path is sluggish, making the overall round-trip time (RTT) bad.
Asymmetrical routing is easy to tackle in small networks, such as the one shown in Figure 15-40. To illustrate how AS 109 can avoid asymmetrical routing when peering only with AS 110, the following condition must be met:
If a packet leaves from R1 to outside AS 109, it must come back into AS 109 at R1.
How can AS 109 achieve this? AS 110 must know that to reach destinations (131.108.1.0/24) in AS 109, it must use the R3–R1 peering link. The following are viable solutions:
- In the BGP configuration of AS 109, only R1 advertises 131.108.1.0/24 to R3 in AS 110. AS 110 will have only one way to reach 131.108.1.0/24, and that is through the R3–R1 link, ensuring symmetrical routing.
- Both R1 and R2 are running EBGP with R3 and R4, respectively. From R1, adver-tise 131.108.1.0/24 to R3 with a MED of 1; from R2, advertise 131.108.1.0/24 to R4 with a MED of 20. AS 110 will have two advertisements, but the path from the lower MED (R1) will win and, in case the R1–R3 BGP connection fails, the path from R2 to R4 will be used. The use of the MED is discussed in detail in previous sections.
- Using the as-path prepend option in Cisco IOS Software, R2 advertises 131.108.1.0/24 with the AS_PATH list containing AS 109 several times.
Example 15-77 shows the configuration of R2 to advertise 131.108.1.0/24 with a prepended AS.
Example 15-77 Prepending AS Number to Make an AS_PATH Longer
R2# router bgp 109 network 131.108.1.0 mask 255.255.255. neighbor 4.4.4.4 remote-as 110 neighbor 4.4.4.4 route-map SYMMETRICAL out route-map SYMMETRICAL permit 10 match ip address 1 set as-path prepend 109 109 109 route-map SYMMETRICAL permit 20 access-list 1 permit 131.108.1.0
In R2 using the route map SYMMETRICAL for neighbor R4, R2 is advertising 131.108.1.0/24 through access list 1 and adds in the AS_PATH AS 109 three additional times. When the advertisement goes to R4, the output of BGP is highlighted in Example 15-78.
Example 15-78 BGP Routing Table for R4
R4# show ip bgp 131.108.1.0 BGP routing table entry for 131.108.1.0/24, version 19 Paths: (2 available, best #1, table Default-IP-Routing-Table) 109 3.3.3.3 from 3.3.3.3 (3.3.3.3) Origin IGP, metric 0, localpref 100, valid, internal, best 109 109 109 109 2.2.2.2 from 2.2.2.2 (2.2.2.2) Origin IGP, metric 0, localpref 100, valid, external
The second path AS_PATH list contains AS 109 listed four times. One time is for the regular EBGP advertisement from R2, and the three additional paths to AS 109 are because of the AS_PATH prepend done in R2.
The best path is the first path, which came from R3 to R4. It is best because it has a shorter AS_PATH length.
R3 will have the regular single EBGP advertisement from R1, as shown in Example 15-79.
Example 15-79 EBGP Advertisement from R1 to R3
R3#show ip bgp 131.108.1.0 BGP routing table entry for 131.108.1.0/24, version 19 Paths: (1 available, best #1, table Default-IP-Routing-Table) Advertised to non peer-group peers: 4.4.4.4 109 1.1.1.1 from 1.1.1.1 (1.1.1.1) Origin IGP, metric 0, localpref 100, valid, external,best This best path is advertise to R4(4.4.4.4) by R3.
In short, proper BGP announcements must be made at exit points and routes must be learned at the right place of the AS. Smaller enterprise networks can achieve this rather easily with the prepended AS path solution, but larger enterprise and ISP networks face a bigger challenge to ensure symmetrical routing. This is because ISPs have a larger number of prefixes to advertise, a larger number of exit points, and a larger number of BGP peering relationships. Unless symmetrical routing is not a must, especially in the case of NAT, most networks today run fine with asymmetrical routing.