Understanding the AS path and AS path prepending

Understanding the AS path and AS path prepending

    as_pathIn earlier articles, we discussed the next hop and local preference attributes. Today we’ll be looking at the AS_PATH attribute as well as the AS4_PATH attribute.

    The AS path is a well-known mandatory attribute, which means that it’s present for all prefixes exchanged between BGP neighbors. When a BGP router sends out an update to a neighbor in a different autonomous system (i.e., an external or eBGP neighbor), it adds its own AS number to the front (left side) of the AS path. So the AS path lists all the ASes that need to be traversed to reach the location where the prefix that the path is attached to is advertised from. As such, a traceroute should encounter those same ASes.

    The main purpose of the AS path is to avoid loops. Without it, BGP would operate very similar to RIP, the Routing Information Protocol. Both RIP and BGP are distance vector routing protocols, where a router basically sends a copy of its own routing table to its neighbors, and the neighbors then use those routes if they’re better than the ones it previously knew.

    A problem with distance vector protocols is the count to infinity problem. Suppose routers A and C are both neighbors of router B. Router A advertises prefix 192.0.2.0/24 to router B. So B now knows it can reach 192.0.2.0/24 through A with a distance of one hop and advertises this to router C, which can then reach the prefix through B with a distance of two hops. But now A goes down, so B can no longer reach 192.0.2.0/24 through A. However, C advertises to its neighbors that it can reach the prefix over two hops, so B changes its routing table to have 192.0.2.0/24 point to C with three hops. C now sees this update from B and updates the distance to four hops. Which B sees so it updates the distance to five hops. To avoid this going on forever, RIP considers a destination unreachable as soon as the distance is 16 hops.

    BGP, on the other hand, would immediately see that the path from B through C towards A leads back to B because B’s AS number is present in the AS path. As a result, B ignores this update and never tries to use paths with loops in them. (However, BGP will still try to use longer and longer legitimate, non-looped paths, a situation called path hunting.)

    An important secondary use for the AS path is to help BGP select the best path. In the previous article, we started the BGP best path selection algorithm with the following seven paths:

    Network Next Hop Metric LocPrf Weight Path
    192.0.2.0/24 1.1.1.1 20 0 1010 1011 286 4040 i
    2.2.2.2 20 0 2020 1011 4040 i
    3.3.3.3 10 100 0 2020 702 4040 i
    4.4.4.4 0 90 0 4040 i
    5.5.5.5 2659 0 5050 1011 4040 i
    6.6.6.6 80 0 6060 4040 i
    7.7.7.7 10 100 0 7070 3356 3356 4040 i

     
    The fourth and sixth paths weren’t selected by the path selection algorithm during the local preference stage because they don’t share the highest local preference. As a result, these remaining five paths are input for the AS path compare stage of the algorithm:

    Network Next Hop Metric LocPrf Weight Path
    192.0.2.0/24 1.1.1.1 20 0 1010 1011 286 4040 i
    2.2.2.2 20 0 2020 1011 4040 i
    3.3.3.3 10 100 0 2020 702 4040 i
    5.5.5.5 2659 0 5050 1011 4040 i
    7.7.7.7 10 100 0 7070 3356 3356 4040 i

     

    At this stage, the path or paths with the shortest AS_PATH are selected. The path with next hop 3.3.3.3 looks to be the shortest, but that’s only because on AS number in the path is a three-digit number, while the paths with next hops 2.2.2.2 and 5.5.5.5 have AS paths with four-digit AS numbers. But what counts here is the number of AS hops, not the length of the text representation. So the middle three paths are all the same length as far as the BGP best path algorithm is concerned: three AS hops. The first and the last paths are four hops and are thus no longer considered and only the middle three paths progress to the next stage of the algorithm.

    Unlike most other attributes, changes to the AS path are propagated to downstream ASes. This makes it possible to use the AS path to do traffic engineering in ways that aren’t possible with other attributes. For instance, consider an AS (AS 1) that announces prefix P to two ISPs: AS 10 and AS 20. ASes 100, 200, 300 and 400 are behind both 10 and 20. Of these, three prefer to send their traffic through AS 10 and one through as 20 as indicated by the black arrows. The yellow arrows indicate the non-preferred path. As a result, three quarters of the traffic arrives through AS 10 and one quarter through as 20, as indicated by the width of the arrows:
    as_path1

    To ASes 100 – 400, the paths through 10 and 20 look equal, as the AS path length is the same. So selection of the best path comes down to the MED and the tie breakers in the BGP path selection algorithm.

    If AS 1 is unhappy with the 75%/25% traffic split, it can prepend its AS path towards AS 10 to make the path longer. Prepending means adding one or more AS numbers to the left side of the AS path. Normally this is done using one’s own AS number, using someone else’s AS number for this can have unintended side effects. Below, AS 1 prepends once towards AS 10, making the path through AS 10 longer for ASes 100 – 400:
    as_path2

    On a Cisco router, the configuration to accomplish this is as follows:

    !
    router bgp 65123
    neighbor 198.51.100.90 remote-as 65456
    neighbor 198.51.100.90 description IX peer
    neighbor 198.51.100.90 route-map prepend out
    !
    route-map prepend permit 10
    set as-path prepend 65123
    !

     
    Because the AS path through AS 20 is now shorter than the one through AS 10, each of ASes 100 – 400 send their traffic through AS 20, so all traffic arrives through AS 20 and none through AS 10. In practice, the result of prepending usually isn’t quite this severe, but it is fairly common for the results of AS path prepending to be stronger than desired.

    An alternative is to use a community on the announcements to one ISP that asks that ISP to selectively prepend towards some of their customers or peers or in some regions. The large carriers typically have such communities. Or, when advertising multiple prefixes, prepend only some but not all.

    AS path prepending is often done on outgoing BGP updates towards transit ISPs or peers so it can influence incoming traffic. However, it can also be used for incoming BGP updates and thus outgoing traffic. This can be useful when manipulating the local preference is too severe: with a higher local preference, a route with a very long AS path may still be preferred, while a single prepend will divert a good amount of traffic, but if the non-prepended path is really long, the prepended path will still be used.

    The AS numbers in the AS path were originally 16-bit values, which allows for about 64,000 globally unique AS numbers. Today, there are more than 70,000 autonomous systems. To accommodate this, BGP-4 was updated to support 32-bit (or 4-byte) AS numbers. When two BGP neighbors connect, first exchange capabilities. If they both support 32-bit AS numbers, those can be used. However, rather than putting 32-bit AS numbers in the AS_PATH attribute, those longer AS numbers are put in a separate, new attribute: the AS4_PATH.

    When two 32-bit capable routers communicate, they update both the AS_PATH and AS4_PATH as appropriate. 32-bit AS numbers (ones higher than 65,535) are replaced by “23456” in the 16-bit AS path. However, when a 16-bit capable router receives a BGP update, it will only update the 16-bit AS path. It will still include the AS4_PATH as-is in updates, because the BGP-4 designers had the foresight allow for this handling of unknown path attributes. When the update then arrives at a 32-bit capable router, it compares the AS_PATH and AS4_PATH and restores the missing information in the AS4_PATH with the information present in the AS_PATH.

    So the update to 32-bit AS numbers is completely transparent to old routers, which continue to function without issue. They’ll just see more and more paths with AS 23456 in them.

    In the next article, we’ll look at the Multi Exit Discriminator (MED) attribute.

    NO COMMENTS

    Leave a Reply