Readings for Lecture Sep 4, 2008

Interdomain Internet Routing

Wide area routing architecture is divided into autonomous systems (ASes) that exchange reachability information. Each AS is owned and administered by a single commercial entity, implements a set of policies in deciding how to route its packet to the rest of the Internet as well as how to export it routes to other ASes. A unique 16-bit number identifies each AS.

Within each AS, different routing protocols operate called Interior Gateway Protocols (IGPs). Between ASes, Interdomain routing protocols like Border Gateway Protocol (BGP) are used and called Exterior Gateway Protocols (EGPs). BGP was designed based on three important needs: Scalability, Policy, and Cooperation under competitive circumstances.

There are two prevalent forms of AS-AS interconnection namely provider-customer transit and peering form in which to ASes (typically ISPs) provide mutual access to a subset of each others’ routing table. Each ISP exports a part of its routing table to other ISPs by filtering according to its policy such that it can gain benefit if the filtered routing paths.

Routes then imported by ASes in the following priority order: customer > peer > provider. This rule can be implemented in BGP using a special attribute that’s locally maintained by routers in an AS, called the LOCAL PREF attribute. There are two types of BGP sessions: beg sessions are between BGP-speaking routers in different ASes, while iBGP sessions are between BGP-speaking router within the same AS. eBGP routers after obtaining information about external world will send the information to BGP routers inside ASes via iBGP sessions. iBGP is different from IGPs like OSPF and RIP.

BGP is actually a rather simple protocol but its configuration flexibility makes it complex. Another issue would be that BGP was not designed for rapid fault detection and recovery, and furthermore, upon the detection of a fault, a router sends a withdrawal message to its neighbors, to avoid massive route oscillations, the further propagation of such route announcements damped. This damping can cause delay.

One interesting feature of BGP would be on policy like hot-potato routing. This paper does not discuss this issue in detail on how to allow cold-potato routing. Thus, future research would be related to policy, failover, scalability, configuration, and correctness.

On Inferring Autonomous System Relationships in the Internet
A pair of ASes is interconnected via dedicated links and/or public network access points, and routing between ASes is determined by the Interdomain routing protocol such as Border Gateway Protocol (BGP). The BGP is closely related to policy of ASes (ISPs).

Thus, the relationships between ASes would be an important aspect of Internet architecture. Each AS set up its own BGP export policies according to its relationships with other ASes. The paper proposes a heuristic algorithm to classify AS relationships basing on BGP routing tables. This work helps understand structural properties of the Internet.

The AS relationships is represented by an annotated AS graph. This graph is partially directed graph whose nodes represent ASes and whose edges are classified into provider-to-customer, customer-to-provider, peer-to-peer, and sibling-to-sibling edges.

An AS selectively provides transit services for its neighboring ASes and it sets up its BGP export policies according to selective export rule. The selective export rule ensures that BGP routing table entries only contain Valley-Free AS paths. The uphill (or downhill) top provider of an AS path to be the AS that has the highest degree among all ASes in its maximal uphill (or downhill) path.

The algorithm goes through the AS path in each routing table entry and finds the highest degree AS and lets the AS be the top provider of the AS path. From the top provider, the algorithm traces to infer the relationships between two consecutive ASes in the path.
However, the above algorithm does not identify peering relationships. An AS pair have a peering relationship if and only if the AS pair do not transit traffic for each other. This is the original idea of the heuristic algorithm.

This paper is interesting in the sense that ISPs or companies can use AS relationship information to plan for future contractual agreement.