The Extent of AS Path Inflation Caused by Routing Policies
by Lixin Gao, Feng Wang
url show details
Details
| type: | misc | | abstract: | Border Gateway Protocol (BGP) is an interdomain routing protocol that allows Autonomous Systems (ASes) to apply local policies for selecting routes and propagating routing information. These routing policies are typically constrained by the contractual commercial agreements between administrative domains. For example, an AS sets its routing policy so that it does not provide transit services between two of its providers. As a result, a route in the Internet may take a longer AS path than the shortest AS path. In this paper, we systematically analyze AS paths and quantify the extent that routing policies inflate AS paths in the Internet. Our results show that AS path inflation in the Internet are more prevalent than expected. We first present the extent of AS path inflation observed from the Route View routing tables. We find that from an ISP, at least 67% of AS paths are inflated by at least one AS hop and AS paths can be inflated by as long as 5 AS hops. We then employ two typical routing policies to show the extent of AS path inflation for all AS pairs. We find that at least one AS hop and AS paths can be inflated by as long as 9 AS hops given a typical routing policy model. Quantifying AS path inflation in the Internet has important implications on the extent of routing policies and traffic engineering performed on the Internet, and BGP convergence speed. |
|
|
You need to log in to add tags and post comments.
I think we can also think of the first problem (different extent of inflation with different levels of ISPs) in terms of different relationships that each ISP has. For example, tier-1 ISPs are mostly connected to customers that they are serving and are peering with a few other tier-1 ISPs. It might mean that their biggest concern is to establish their routing tables for providing their customers with better performance (like less hops to the destination). However, ISPs on lower levels also need to think about ways to avoid additional financial burden that they have to pay to their service providers, which sometimes leads to route inflation.
The authors conclude that their results "show that AS path inflation in the Internet is more prevalent than expected." I'm curious that what is the previous expectation of AS path inflation? Also, if 1 AS-hop inflation degrades performance more when the length of the shortest path is 6 rather than 2, we can derive another measurement for AS path inflation.
Figure 15 could be more readable if only curves for 0,1,3,5,7,9 AS-hop inflation are shown.
The graphs compare the absolute path length, but I think that a more important measure may be the percentage increase in path length. For example, if a packet can be routed in 2 hops, but is actually routed using a path that has two 'extra' hops (for a total of 4 hops), then the path length (in hops) has doubled; but if the shortest path is 10 hops, then an 'extra' two hops would only increase the path length by 20%.
The paper also does not discuss drawbacks of using different policies that achieve shorter paths. IMHO, the business considerations and the need for additional accounting overhead would dwarf any improvements resulting from shorter paths.
So far, the paper tell us that because of some "routing policies" the AS paths chosen wouldn't be the shortest one but the other that, to some degree, was inflated. However, another question that I 'd like to know the answer is that "what are impacts on this AS path inflation on the performance of overall network?" or "Would a few additional AS hops incur significant effect on the network?"
About the inconsistency between the chosen AS paths and the inferred AS paths based on no-valley-and-prefer-customer routing policy, as of table 1 in the paper, I think the paper didn't explain well what's really happened. "The reason is that tier-1 and tier-2 ASes may violate prefer-customer routing policies" doesn't explained anything much because the high inconsistency, between the AS paths chosen and the inferred paths, already told us that in reality inter-domain routing doesn't follow prefer-customer routing policies.
I was interested in the AS Path inflation due to the two routing policies, mainly the effect due to inclusion of prefer-customer routing policy. I think it make sense that the AS Path inflation is so dramatic when prefer-customer is added to the routing policy. People do things when they have an incentive but not necessarily because it benefits an operation. In this case, the incentive is including prefer-customer in routing policy and the operation is the internet, specifically the AS path. I would like to know what solutions we could give to counteract this incentive if at all possible. Maybe, some sort of subsidy for those who rely less or go against prefer-customer routing policy. That might not work but I think it is one of many solutions that should be looked at if AS path inflation is (or becomes) a serious issue.
The claims this paper makes are
1. from the limited data, there seems to be a lot of inflation
2. their two routing policies produce some inflation, and
2.1 no-valley: little inflation but similar to real world based on routes produced (70%)
2.2 no-valley-prefer-customer: more inflation but less similar to real world
I don't quite understand how from the second part they can conclude that there is a lot of inflation in the real networks based on this "simulation". I think this is what the second question in the public review is addressing and while the comparisons to real world routes are interesting, it leads to no obvious conclusions and is confusing. Does anyone understand this part of the study better?
I will start off by saying that I’m not very familiar with Interdomain Internet Routing and that this was my first paper on this subject. I found the MIT Lecture notes to be very interesting, mostly because the concepts explained where new to me.
My thoughts on the paper are somewhat similar to Cody’s (Comment #6). This paper seems to imply that choosing the shortest AS path is always the best solution. Based on this assumption it measures how much AS paths deviate from this optimal solution. However I’m not necessarily convinced that the shortest path is always the best one. Is path length the only and most important metric to be used when establishing AS paths? What about link bandwidth, latency, stability or congestion? It could very well be that an AS chose a path that is slightly longer than the shortest one, because it offered higher bandwidth and was less congested. This paper seems to suggest that most AS paths are chosen based purely on business relationships among ASs.
On the other hand I do realize that it would be very hard to devise an accurate formula (that considers more factors than simply path length) for ranking the different available paths and picking the optimal one.
This paper has two parts, and, as pointed out by previous commenters, it isn't clear how well the second part(simulation) substantiates the claims of the first part(measurement).
1) The measurements: I agree with William on his comment that it would have been really useful to see additional graphs that showed the inflation as a function of its path length.
2) The simulations: These show that one "typical" routing policy has low inflation. Since this disagrees with *their* measurements, they try another routing policy which shows more inflation. However, as the authors themselves show, this isn't completely realistic. Therefore, they can only conclude that the routing policies at the AS level are not shortest-path.
This could have been inferred from part 1 itself, therefore the utility of the second part of the paper is not clear.
On a related note, while they do cite previous work(citation 11), it would have been very useful to see a more thorough description of their simulations and how they arrive at their simulated graphs. Clearly the topology of the graphs they use in their simulations have a strong bearing on their results. For example, a plot showing distribution of path lengths on real and simulated graphs would have been very useful.
This paper quantifies the degradation in performance in interdomain routing due to routing policies and the contractual obligations constraining those policies. I agree with some of the above comments that the measure of degradation was odd -- surely the number of additional hops is not the important measure. If not measuring some sort of total latency, at the very least, the percentage increase in length must be the important quantity.
However, since the issue here seems to be that selfish behavior on the part of the AS's (making beneficial contracts and trying to minimize cost) leads to a degradation in internet performance, I would have liked to see some sort of analysis of the incentives involved. Why are these contracts and routing policies chosen? Could it be that the aggregate solution reached, while locally optimal for everyone is not globally optimal for anyone? (i.e. could everyone improve their welfare if only they were all to cooperate?) Such an analysis would lead to suggestions for how to fix the problem, which this paper does not present. Simply suggesting more efficient routing policies does not alleviate the problem unless it can be shown that the adoption of these policies is in the individual interests of the AS's.
Has there been any work done in modeling routing policy selection as a game?