In BGP, each router informs its peers about the prefixes it knows. We say that it ``advertises'' routes to these prefixes. For each prefix, it provides a so-called AS-path, which is a sequence of ASNs indicating through which Autonomous Systems the route to the prefix goes. For example, in Figure 4.5 one of the routes that AS64003 advertises to AS64001 contains the AS-path 64003 64004 64005, which means that this route goes through ASes 64003 and 64004, and then ends in AS 64005.
The method of selecting the preferred route assumes that the shortest path indicates the minimal network distance, and thus the minimal cost of delivering a packet. In case a router has received several AS-paths for the same prefix from different peer routers, it chooses the one that offers the shortest AS-path. The chosen route is marked as best. In Figure 4.5 all routes in the BGP routing table are marked as best, except for one, for which a shorter alternative can be found. That is why AS64001 will decide to use AS64002 as the peer AS through which the traffic to the prefix 192.168.4.0/22 should be sent.
A BGP routing table contains a list of routes to prefixes, each of which is associated with the IP address of the peer router that has offered the route, and the AS-path for this route. Each route has also a defined ``origin'' attribute, informing where the route information comes from: whether it was learned using an internal routing protocol, an external one, or another way. The last situation typically occurs when at some point the route switches from BGP to some other routing protocol. The peer IP addresses and the route origins are omitted in the routing table in Figure 4.5, as they are not essential to understand how BGP works. We will need them later, however, when discussing the BGP details.
BGP routers are allowed to compress the data in their routing tables to reduce the amount of memory needed, and the size of routing messages they exchange. A popular technique of BGP data compression is called route aggregation. In this technique, a set of route specifications is replaced with a single, aggregated route specification. Route specifications can only be aggregated if they are associated with contiguous prefixes, which in turn form a single, bigger prefix. In other words, the set of target IP addresses covered by the prefixes from the original route specifications, and by the big prefix from the aggregated route specification must not change. For example, the four following prefixes:
Compressing prefixes implies compressing the associated AS-paths. The AS-path in the aggregated route specification consists of two parts. The first one, called AS-sequence, is the sequence of ASNs common to all the original AS-paths. Importantly, the ASNs enumerated in the AS-sequence are listed in the same order as in all the original AS-paths. The second part of the compressed AS-path is called AS-set. It is an unordered set of ASNs that occur in at least one original AS-path, but cannot be included in the AS-sequence, either because they do not occur in some of the original AS-paths, or because they occur in all of them, but in various places. Obviously, if all the original AS-paths are identical, the AS-set in the compressed AS-path is empty, and the entire compressed AS-path is simply a copy of one of the original AS-paths. In textual AS-path representations, AS-sets are delimited by the { and } brackets. For example, one may compress the two following AS-paths:
Route aggregation usually leads to information loss. Since ASNs included in AS-sets are unordered, it is impossible to derive the original AS-paths from a compressed one, as long as its AS-set is non-empty. Importantly, it is still possible to determine which peer router should be given a packet heading to a prefix associated with an aggregated route. Since the AS-sequence in the compressed AS-path contains the initial part of the real route, its first ASN denotes the next Autonomous System, to which the packet should be passed. Following this scheme the packet will eventually reach the AS where the aggregation was performed, and where unaggregated route specifications are still known. In our example, the BGP routers in AS 64011 will process the packet using the two original route specifications, and forward it accordingly, either to AS 64006 or to AS 64007.
![\includegraphics[width=14cm]{xfig-bgp.eps}](img17.png)