3. Interdomain Internet Routing

This paper is about how routing information is exchanged between service providers such as Border Gateway Protocol (BGP) as well as failures and shortcomings of the routing system.

In a more realistic view of the Internet structure, Internet Service Providers (ISPs) can be put into three categories, Tier-3 (small, local), Tier-2 (large, region-wide), and Tier-1 (really huge, "default free," only 10 as of 2009). Routing infomation is exchanged between these autonomous systems (ASes) with each assigned a unique 16-bit number address through BGP, while within the ASes, Interior Gateway Protocols (IGPs) were used. The difference between BGP and IGP is that the former implement autonomous routing policies, whereas the latter are usually non-concerned with optimizing a path metric.

There are two kinds of Inter-AS relationships, "transit" and "peering". "Transit" is the customer-ISP data traffic, in which customer is usually charged for the serive. "Peering" is the ISP-ISP traffic, in which may not involve financial settlement if the traffic radio is not highly asymmetric (4:1).

Reasons for peering relationships: 1) Tier-1 peering acts as an alliance of a certain size Tier-1 providers. Peering between Tier-1 ISPs ensures that they have default-free routing information to all Internet nodes. 2) Tier-2 and Tier-3 ISPs usually have to pay their upper tiers for asymmetric traffic, but if they could settle a new link between themselves, while generating roughly symmetric data flow, to save money, and to increase end-to-end performance.

ISPs charger customers for transit links and import/export routing tables to make or save money by peering in order to make profit. Since routing traffic to customers always generate income, ISPs tend to put customer traffic on top priority (local preference) and try to avoid a distant peering that cost them.

BGP sessions can be divided into two types, eBGP (between ASes), and iBGP (within ASes). They use the same protocol for different purposes. Two important goals have to be met when disseminating the routes, namely, loop-free forwarding, and complete visibility.

The lack of origin authentications weakens the BGP by letting network administrators hijack the routes by mistake (the YouTube example) or for profit (the spam example). A solution called secure-BGP (s-BGP) is proposed, but not yet implemented for a variety of reasons.

Comment:

1. It is interesting to learn how the money actually flows for the Internet Service from customer to ISPs and upper-tier ISPs, since everything is inter-connected in some ways.
2. A bit of googling shows that s-BGP uses Public Key Infrastructure (PKI) to authenticate the routing updates. It should make sense that s-BGP would replace BGP a.s.ap., but in this paper it says one of the reasons it isn't deployed is because of existing routing table errors! :-O