On BGP and on Inferring Autonomous System Relationships

Today’s set of readings involve a tutorial about the Border Gateway Protocol (BGP) and a paper describing Autonomous System (AS) relationships. The tutorial Interdomain Internet Routing describes the transit and peering relationships between ASs while detailing the protocol description of BGP. In line with some of the earlier discussions on the design goals of the Internet, BGP has similar goals such as scalability and decentralized management (AS flexibility in implementing policy) as well as the promotion of cooperation in a market environment. The tutorial also hints on the complex interactions between ASs resulting in a number of challenging research problems.

Perhaps providing a prelude to these challenging problems is the paper entitled On Inferring Autonomous System Relationships in the Internet by Lixin Gao. This paper provides an instrument to evaluate AS relationships. Using formal graph notation to represent three types of AS relationships, Gao proposes heuristic algorithms to infer these relationships from the BGP routing tables. The validation of the results was significantly high and provides what is claimed as the first quantifiable view of these relationships.

Some implications of this paper that may not have been explicitly articulated are the effects to both the ASs implementing their networks and to researchers working on and designing routing protocols. In addition to assessing contractual relationships, knowing the policies employed by neighboring AS could provide insights on how an AS can possibly dimension and manage traffic in their networks to achieve service commitments. This assessment could span several time scales depending on the granularity of management required. To be able to achieve this and as noted in the paper, tools need to be developed to accomplish the necessary accounting and inferencing. For the researcher, the assumption that one can use connectivity to determine shortest paths needs to revisited as policy may not necessarily allow a path to be traversed. This results in path lengths that may be deeper than what is expected. Simulations or design studies having this premise would have results that may not necessarily be valid in practice.