A few subtle complications can make the AS_PATH less accurate than we would like. [25] Route Aggregation allows an AS to advertise an aggregate route in which contiguous IP addresses can be collapsed to a single entry. The rules of BGP4 require that the aggregated route contain all of the AS numbers for any portion of the aggregation. This sometimes overstates the length of the AS_PATH. It is also possible to use an ATOMIC_AGGREGATE, thus effectively hiding some AS numbers from appearing in the AS_PATH.
Our algorithm also depends on the AS_PATH being an AS_SEQUENCE, an ordered list of the AS numbers traversed to deliver a packet to a given IP address range. The BGP4 specification allows an AS_PATH to be an unordered AS_SET, but requires that it become an AS_SEQUENCE before it is passed as a advertisement to a neighboring AS. In theory, this means that any BGP4 AS_PATH farther than 1 hop away from its ultimate destination must be an AS_SEQUENCE and our algorithm assumes this to be true.
Our algorithm creates a tree that sometimes makes an AS appear farther from the backbone than it really is. This most often occurs because the cluster with the least overhang over a subject cluster is preferred when the subject cluster picks a parent. The average depth of the cluster tree was 1.961, whereas the average number of hops to the backbone in the full graph was 1.595. The right-hand graph in Figure 2 shows how these two metrics compare.