Summary and Critique: Interdomain Internet Routing

The paper started by identifying questions that would need to be answered. These are: How do the relationships between ASs affect the routing information they share with each other? What are these relationships? How does this affect the technical research agenda of internet routing?


The internet is composed of ASs (Autonomous Systems) that exchange reachability / routing information. These ASs are operated by a commercial entity (such as ISPs, companies, schools), which define the routing policies that map out the rules for exporting and importing routes. The policies to import, export, and select routes depend on the relationship between ASs, if it is provider-to-customer, customer-to-provider, peer-to-peer, or sibling-to sibling.


Within each AS, different Interior Gateway Protocols (IGPs) operate. These protocols are concerned with optimizing a path metric. The paper did not discuss IGPs, but was focused on inter-AS relationships and features of BGP (Border Gateway Protocol), the current wide-area routing protocol on the internet.


There are two main classifications of AS relationships. These are: transit and peering. Simply put, a transit relationship is one where financial settlement is involved. For example, the provider provides access to all/ most of the destinations in its routing tables. Meanwhile, a peering relationship involves providing mutual access to routing tables. This is also a business deal, but there is no financial settlement.


So why can’t all relationships just be peering?


There are 2 main reasons: First, peering relationships do not generate revenue. Second, peering relationships need to be renegotiated often.


Also, import and export policies are determined based on AS relationships. Export policies are important and should be determined with care because an ISP does not want to be providing transit to packets it will not be earning from. On the other hand, the most important consideration in import policies is knowing who advertised the route. As such, routes are typically imported in the following order of priority: customer > peer > provider.


The next part of the paper discussed in detail the route selection process of BGP. In essence the write-up explained how the BGP routers are configured to implement policies which are dependent on the relationships between ASs.


So what do I think about all this?


The author was thorough enough in explaining the technical details of how interdomain internet routing worked. After reading the article, I had a better appreciation of how flexible yet complicated BGP can be. And the configurations get more complex because of ‘economic relationship’ considerations. Still, it would be interesting if somebody could figure out how to make things simpler, or the business model that would do away with the transit relationship constraints and allow for sharing of the best routes with each and every AS.


Reference:

Balakrishnan,H. Feamster,N. 2001-2005. Interdomain Internet Routing

Summary and Critique: On Inferring Autonomous System relationships in the Internet

The paper by Lixin Gao studies the structure of the internet, its components, and the rules which determine the routing of information across the internet. The internet is composed of Autonomous Systems (ASs) that determines it own routing policies in selecting the best route, and exporting and importing routes. Administrative domains such as ISPs, companies, and universities operate these ASs. The routing policies implemented by each AS are based on the contractual commercial agreements in effect between the administrative domains which operate it. Thus, these contractual agreements have a great influence on how the internet is structured and affect its end-to-end performance

Relationships between ASs can be classified into: peer-to-peer, provider-to-customer, customer-to-provider, or sibling-to-sibling relationship. These relationships are the basis for the import and export policies that an administrative domain can implement on its ASs. Also, there are patterns in the BGP routing entries, and these entries can potentially show what the relationship between ASs are.

Wait, what’s BGP? According to Kurose and Ross (2003), the Border Gateway Protocol (BGP) is the de facto standard interdomain routing protocol of the internet. Neighboring BGP routers exchange path information about routes to destinations. That is, the information propagates in an AS-by-AS manner.
Given these patterns and knowing that import and export policies rely on AS relationships, the author of the paper proceeded to present a heuristic that would determine the relationship between ASs.

There were algorithms presented that would determine provider-to-customer, sibling-to-sibling, and peer-to-peer relationships. When the solutions were tested and compared with AT&T internal information, the Refined algorithm (L=1) and Final algorithm (R=60) showed the best results, with 99.1% of the inference results confirmed. Tweaking of R (ratio between the degrees of two peering ASs) from the original value of ∞ to 60 gave better results. Results were also verified using the WHOIS Server, but only 54.3% of the inferred sibling relationships were confirmed. It was noted that the WHOIS database might also be out of date.
Lastly, the author identified some reasons why some inferred sibling relationships were not confirmed by AT&T or the WHOIS lookup service. These are router configuration typo, misconfiguration of small ISPs, unusual AS relationships, and inaccuracy of the heuristic (the assumption that the top provider has the highest degree may not be true).

But beyond the algorithms and academic exercise why are all these things important?
According to the author, the routing policies are manually configured and prone to error. These errors can affect other ASs and spread throughout the network and may cause outages. It is thus important to monitor routing announcements and filter out erroneous ones. The routing tables may also be checked periodically and the AS that propagated the error can be informed. Thus, these heuristics are aimed to build tools that would improve the reliability of internet routing. The relationship information can also be used by ISPs/ administrative in determining the terms of their contractual commercial agreements.

The article was an extremely long read, but very informative. The author explains the nitty-gritty of the algorithms, and provided ample introduction at the beginning to explain the basis of the calculations. I thought at first that the contractual commercial agreements between ASs was being suggested by the author as a negative constraint. However, I’ve come to realize by the end of reading that these commercial agreements are necessary for the whole thing to work – in a business/ economic point of view. There will always be providers and customers – and each has to protect their own interests. That is, I can’t think of an alternative model/ set-up. It would be good if I can learn more about that in our advanced networking class.

References:
Gao, Lixin. 2001. On Inferring System Relationships in the Internet. IEEE/ ACM Transactions on Networking, Vol 9 No 6
Kurose, J., Ross, K. 2003. Computer Networking: A Top-Down Approach Featuring the Internet