The paper by Lixin Gao, titled “On Inferring Autonomous System Relationships in the Internet,”[1] discusses an algorithm that her group has developed for determining the relationships of various ASs. Based on her account, there are no available public records specifying inter-AS relationships. What exist, though, are publicly available BGP routing tables and these served as their source of data for inferring relationships.
Their approach uses an annotated graph to represent ASs and their relationships. Nodes represent ASs and edges represent relationships, which they classified as provider-to-customer, customer-to-provider, peer-to-peer, and sibling-to-sibling.
Export Policies
Vital to the design of their algorithm are their derived BGP export policies [1]:
“Exporting to a provider: In exchanging routing information with a provider, an AS can export its routes and its customer routes, but usually does not export its provider or peer routes.
Exporting to a customer: In exchanging routing information with a customer, an AS can export its routes and its customer routes, and as well as its provider or peer routes.
Exporting to a peer: In exchanging routing information with a peer, an AS can export its routes and its customer routes, but usually does not export its provider or peer routes.
Exporting to a sibling: In exchanging routing information with a sibling, an AS can export its routes and routes of its customers, and as well as its provider or peer routes.”
From these export policies, they formulated what they consider as the selective export rule, which summarizes the above policies. I’d like to note that, as this paper and the previously discussed lecture on AS have also emphasized, policies regarding exporting and importing of routes are only privy to ASs involved in a deal. So what they have here are mere descriptions of what’s likely to be the case, as suggested by the phrase “but usually does not export,” and these hardly qualify as scientific. From my perspective, I find it hard to image that such assumptions are capable of producing accurate results. But as their experimental results suggest, my perception is the one that is inaccurate.
From here, I’ll go straight (I’ll skip their proving parts) to their algorithm.
Algorithm
Based from BGP routing tables, an augmented graph can be derived using the policies described by the paper. This graph will serve as the input for their algorithm. The first part of the algorithm simply determines the degree of each AS in a graph. A higher degree suggests that a node is likely a provider, since customers are connected to them.
The next phase of the algorithm is meant for reducing the inconsistencies that are possibly caused by misconfigured routers. In some cases, two AS pairs appear to have both provider-to-customer and customer-to-provider relationships in various routing table entries. This could lead to mislabeling in some AS paths. To correct this, they used a variable L to serve as a threshold for determining the dominant relationship. If a relationship of two pairs appear in more than L entries, then that is used as the correct relationship. But if both the provider-to-customer and customer-to-provider relationships both appear in less than L entries or more than L entries, then they are considered to provide transit to one another.
The third part of the algorithm is the labeling of edges. For each AS path, the AS with the highest degree is considered as the “top provider.” Once a top provider is determined, ASs with customer-to-provider and provider-to-customer relationships can be easily identified. All transits before the top provider are customer-to-provider edges, since providers are generally known to have higher degrees, while transits appearing after are provider-to-customer edges. If two pairs both provide transit to each other (i.e. they both appear before the top provider and also after it in a reversed order), then this pair is classified as a sibling-to-sibling edge. This part of the algorithm simply traverses all consecutive pairs in a path, which means it has an efficient linear run time (O(n)).
The last part of the algorithm is for determining peering relationships. In each AS path, the top provider can have a peering relationship with at most one of its neighbors. The heuristic considered for determining a top provider’s peer is the tendency of a top provider to peer with a neighbor with a higher degree. However, this could erroneously produce many peering relationships. To handle this, a variable R is introduced as measure for the similarity of two peers in terms of their degree. The author said, though, that this value still needs to be fine-tuned, though its effects are less influential if there are more routing tables used as references.
Experimental Results
Their experimental results, to say the least, are impressive. Here are some of their results that were confirmed by AT&T internal information: 100% of their inferred customers, 100% of their inferred peers, 20% of their inferred siblings. 98.9% of all their inference results were confirmed by AT&T internal information. For an algorithm that is based on simple heuristics, including some variables that may need further adjustment, it is really surprising to see that they were able to come up with accurate results concerning data that are meant to be confidential. Even better, they were able to accomplish this through a series of sequential data processing, resulting to quite an efficient algorithm.
Aside from confirming the correctness of their algorithms, their results also prove the validity of certain assumptions made on routing policies. Although these assumptions are based on what makes sense, there are still no hard evidences to prove these. But now that a well known ISP has confirmed their results based on these notions, then maybe it’s time for ISPs to make their routing policies and relationships open for research purposes, since they’re slowly being exposed anyway.
References:
[1] L. Gao. On Inferring Autonomous System Relationships in the Internet. IEEE/ACM Transactions on Networking, vol.9, no.6, p.733-745. December 2001
Friday, July 10, 2009
The Economics of the Internet
Karl Marx postulated that society, for the most part, is economically motivated. Apparently, the Internet (or what drives it) is not exempted from this.
The lecture “Interdomain Internet Routing”[1] presents the different entities that collectively form the Internet and their varying relationships with one another. These entities are known as “Autonomous Systems” (AS), and these include Internet Service Providers (ISPs) and their customers. One may prefer that these ASs cooperate in a symbiotic fashion for optimum global connectivity, but this is generally not the case. The authors noted that, since most of them belong to commercial enterprises, relationships are dictated by business decisions, resulting to selective routing. I think this is understandable, though, as providing Internet traffic is not cheap, so you want to make sure that your transmission facilities are being utilized towards your own advantage.
ASs use the Border Gateway Protocol (BGP) to exchange reachability information among one another, and this in turn serve as their guide for determining whether they would share their routes with another AS or not. The paper explained that the two most common forms of inter-AS relationships are transit and peering.
Inter-AS Relationships
Transit relationships are the ones shared between providers and customers. Largely a result of business transactions, this gives customers the benefit of being able to access most, if not all, of the destinations available from a provider. Peering, on the other hand, gives two ASs access to only a number of entries in each other’s routing tables. After all, this type of relationship is usually not settled financially (as the saying goes, we always get our money’s worth), and it is more of an agreement between two parties. The connectivity that peering provides may seem limited, but its real value lies in the semi-mutual benefit that involved ASs may reap. An AS on one side of a peering relationship save on transmission cost by being able to send their packets using their peer’s routes that are connected to their customers, thus preventing the need to transit with a higher-tiered ISP. This, of course, in exchange for doing the same thing for their peer. I described this as semi-mutual because, as the paper indicated, the common traffic ratio between peering ASs is 4:1, and that is already considered as not highly asymmetrical. Maybe this is because it’s hard to find two AS pairs that share almost similar amount of customers belonging on the other end. Still, one is getting 75% more than the other! Well, if it works for them, then it works for them (but one is luckier).
Exporting and Importing Routes
The paper also discussed the exporting and importing rules applied by an ISP to its neighbors. In either case, the customer is always the king, since customer traffics provide ISPs revenues. Other rules for exporting and importing are simply a matter of making sure that they provide routes for traffic that would benefit them and that they deny any route that would only make them carriers of packets that solely serve the interests of their neighboring ISPs.
BGP
The succeeding sections of the paper discussed the BGP in a fairly detailed manner. I won’t reiterate everything here since things are already explained (and it’s a long one), so I’ll just mention some parts where I can place my insights.
One interesting section there is the communication of BGP speaking routers within an AS. In this setting, iBGP is used by the communicating routers (as opposed to eBGP, which is used for speaking with routers belonging to other ASs) in order to disseminate among themselves routes learned from other ASs. The problem lies, though, in the seemingly trivial task of spreading information. The first solution they used is the linking of every eBGP router with all other routers in an AS through iBGP sessions, resulting to a full mesh topography. In graph theory lingo, you can think of this as something similar to a clique graph, which contains |v|(|v| - 1)/2 edges, where |v| is the number of vertices in the graph. In this representation alone, n routers would mean Θ(n2) iBGP sessions maintained within an AS. Worse, clique graph is not a very accurate representation because there are internal nodes inside the graph, resulting to a larger value of e(e - 1)/2 + ei iBGP sessions, where e is the number of eBGP routers and i is the number of iBGP routers. If you’re concerned with scaling, this is not a good sign.
Other possible solutions involve the use of confederations and route reflectors. Confederation is a form of clustering of routers in such a way that a cluster is considered as a single entity[2]. Actually, based on rfc3065, these are mainly applied on ASs, but this model fits well within an AS too, plus there wouldn’t be any problems with regards to the AS_PATH value. Route reflectors, on the other hand, are routers that are responsible for passing routing information for their whole domain (an AS or confederation). Combining these two concepts, what happens is that information is passed among confederations instead of individual routers, then each confederation may have its own reflector that would spread information within its domain. This represents a cascading effect, somewhat similar to a tree structure. Sounds like an interesting idea. But come to think of it, isn’t this also the same way the Internet is structured, just on a larger scale?
Another interesting issue about BGP is the MED attribute. It can be used either as a “magnet” or a “turn-off” (sorry, I couldn’t think of a better term) for traffic. What if two neighboring ASs both wanted or disliked to carry certain packets, and they kept on adjusting their MED values until they reached to a point where they have similar values, would this result to a stalemate? Of course, I’m sure there’s a provision for this, and this attribute is not even always used. But imagine the hypothetical scenario of two Tier-1 ISPs not being able to come up with an “agreement” on a certain data transmission because of their MED values (or even other attributes) and this caused the Internet to temporarily hang. That would be, um, strange.
References:
[1] H. Balakrishnan and N. Feamster. Lecture 4: Interdomain Internet Routing.
[2] http://tools.ietf.org/html/rfc3065
The lecture “Interdomain Internet Routing”[1] presents the different entities that collectively form the Internet and their varying relationships with one another. These entities are known as “Autonomous Systems” (AS), and these include Internet Service Providers (ISPs) and their customers. One may prefer that these ASs cooperate in a symbiotic fashion for optimum global connectivity, but this is generally not the case. The authors noted that, since most of them belong to commercial enterprises, relationships are dictated by business decisions, resulting to selective routing. I think this is understandable, though, as providing Internet traffic is not cheap, so you want to make sure that your transmission facilities are being utilized towards your own advantage.
ASs use the Border Gateway Protocol (BGP) to exchange reachability information among one another, and this in turn serve as their guide for determining whether they would share their routes with another AS or not. The paper explained that the two most common forms of inter-AS relationships are transit and peering.
Inter-AS Relationships
Transit relationships are the ones shared between providers and customers. Largely a result of business transactions, this gives customers the benefit of being able to access most, if not all, of the destinations available from a provider. Peering, on the other hand, gives two ASs access to only a number of entries in each other’s routing tables. After all, this type of relationship is usually not settled financially (as the saying goes, we always get our money’s worth), and it is more of an agreement between two parties. The connectivity that peering provides may seem limited, but its real value lies in the semi-mutual benefit that involved ASs may reap. An AS on one side of a peering relationship save on transmission cost by being able to send their packets using their peer’s routes that are connected to their customers, thus preventing the need to transit with a higher-tiered ISP. This, of course, in exchange for doing the same thing for their peer. I described this as semi-mutual because, as the paper indicated, the common traffic ratio between peering ASs is 4:1, and that is already considered as not highly asymmetrical. Maybe this is because it’s hard to find two AS pairs that share almost similar amount of customers belonging on the other end. Still, one is getting 75% more than the other! Well, if it works for them, then it works for them (but one is luckier).
Exporting and Importing Routes
The paper also discussed the exporting and importing rules applied by an ISP to its neighbors. In either case, the customer is always the king, since customer traffics provide ISPs revenues. Other rules for exporting and importing are simply a matter of making sure that they provide routes for traffic that would benefit them and that they deny any route that would only make them carriers of packets that solely serve the interests of their neighboring ISPs.
BGP
The succeeding sections of the paper discussed the BGP in a fairly detailed manner. I won’t reiterate everything here since things are already explained (and it’s a long one), so I’ll just mention some parts where I can place my insights.
One interesting section there is the communication of BGP speaking routers within an AS. In this setting, iBGP is used by the communicating routers (as opposed to eBGP, which is used for speaking with routers belonging to other ASs) in order to disseminate among themselves routes learned from other ASs. The problem lies, though, in the seemingly trivial task of spreading information. The first solution they used is the linking of every eBGP router with all other routers in an AS through iBGP sessions, resulting to a full mesh topography. In graph theory lingo, you can think of this as something similar to a clique graph, which contains |v|(|v| - 1)/2 edges, where |v| is the number of vertices in the graph. In this representation alone, n routers would mean Θ(n2) iBGP sessions maintained within an AS. Worse, clique graph is not a very accurate representation because there are internal nodes inside the graph, resulting to a larger value of e(e - 1)/2 + ei iBGP sessions, where e is the number of eBGP routers and i is the number of iBGP routers. If you’re concerned with scaling, this is not a good sign.
Other possible solutions involve the use of confederations and route reflectors. Confederation is a form of clustering of routers in such a way that a cluster is considered as a single entity[2]. Actually, based on rfc3065, these are mainly applied on ASs, but this model fits well within an AS too, plus there wouldn’t be any problems with regards to the AS_PATH value. Route reflectors, on the other hand, are routers that are responsible for passing routing information for their whole domain (an AS or confederation). Combining these two concepts, what happens is that information is passed among confederations instead of individual routers, then each confederation may have its own reflector that would spread information within its domain. This represents a cascading effect, somewhat similar to a tree structure. Sounds like an interesting idea. But come to think of it, isn’t this also the same way the Internet is structured, just on a larger scale?
Another interesting issue about BGP is the MED attribute. It can be used either as a “magnet” or a “turn-off” (sorry, I couldn’t think of a better term) for traffic. What if two neighboring ASs both wanted or disliked to carry certain packets, and they kept on adjusting their MED values until they reached to a point where they have similar values, would this result to a stalemate? Of course, I’m sure there’s a provision for this, and this attribute is not even always used. But imagine the hypothetical scenario of two Tier-1 ISPs not being able to come up with an “agreement” on a certain data transmission because of their MED values (or even other attributes) and this caused the Internet to temporarily hang. That would be, um, strange.
References:
[1] H. Balakrishnan and N. Feamster. Lecture 4: Interdomain Internet Routing.
[2] http://tools.ietf.org/html/rfc3065
Subscribe to:
Posts (Atom)