How is BGP "AS_SET" used?

Question

RFC 1771 defines a path attribute type of AS_PATH as follows:

AS_PATH (Type Code 2):

AS_PATH is a well-known mandatory attribute that is composed
of a sequence of AS path segments. Each AS path segment is
represented by a triple <path segment type, path segment
length, path segment value>.

The path segment type is a 1-octet long field with the
following values defined:

Value Segment Type
1 AS_SET:      unordered set of ASs a route in the
               UPDATE message has traversed
2 AS_SEQUENCE: ordered set of ASs a route in
               the UPDATE message has traversed

Using a AS_PATH type of AS_SEQUENCE makes perfect sense to me: You end up with a reverse list of the ASN's you cross to get to a particular prefix.

However, I have no idea what purpose having an unordered list of ASN's between you and the prefix that would occur if you chose to use an AS_PATH of AS_SET.

The quote above is from the UPDATE message format, so presumably, an Admin has the option to send to BGP peers an ordered list or an unordered list. My question then is, what would the purpose be of sending an unordered list? In what cases would you be better off sending an unordered list as opposed to an ordered list?

Answer 1

My question then is, what would the purpose be of sending an unordered list? In what cases would you be better off sending an unordered list as opposed to an ordered list?

as-set is commonly used when aggregating routes downstream of an autonomous system; so the use case for an unordered list is bgp aggregation.

EXAMPLE:

In the example below, AS65500 aggregates the eBGP announcements from AS65000 and AS65001 into 10.1.0.0/23. After aggregating the announcements from AS65000 and AS65001, AS65500 sends NETWORK: 10.1.2.0/23 AS-PATH: 65500 and NETWORK: 10.1.0.0/23 AS-PATH: 65500 {65000, 65001} (the aggregate). Typically, an AS will aggregate when it has delegated portions of a larger address block to customers.

It doesn't make sense to build an ordered list when you aggregate space for multiple ASNs; for instance, an ordered AS-PATH for the aggregate below would be either 65500 [65000, 65001] or 65500 [65001, 65000]. However, both of those ordered lists are non-sense because ordering is irrelevant to the aggregate (i.e. both autonomous systems are directly connected to AS 65500). Ordering implies a sequence which is meaningless to the aggregate.

Unordered lists (i.e. mathematical sets) make the most sense for an AS_SET.

          _.------------.
      ,-''               `--.
    ,'                       `.
   (         AS65000           )
    `.       10.1.0.0/24     ,'
      `--.               _.-'
          `------------''
                    \          ------> NETWORK: 10.1.2.0/23   AS-PATH: 65500
                     \         ------> NETWORK: 10.1.0.0/23   AS-PATH: 65500 {65000, 65001}
           _.--------------.        router bgp 65500
       ,-''                 `--.     no sync
     ,'                         `.   no auto-summary
    (          AS65500             ) neighbor 10.1.0.2 remote-as 65000
     `.        10.1.2.0/23      ,'   neighbor 10.1.1.2 remote-as 65001
       --.                 _.-'      network 10.1.2.0 mask 255.255.254.0
           `--------------''         aggregate-add 10.1.0.0 255.255.254.0 summary-only as-set
                    /
                   /
          _.--------------.
      ,-''                 `--.
   ,'                         `.
  (           AS65001           )
   `.         10.1.1.0/24     ,'
     `--.                 _.-'
         `--------------''