Summary
Global connectivity of millions of end-hosts worldwide is possible through interdomain routing in the Internet coordinated by BGP. BGP allows each AS to set its own routing policies. Oftentimes, contractual commercial agreements between administrative domains poses constraint on these routing policies e.g. A customer must not provide transit services between its providers. Indeed, policies like this shows that AS relationships stand as important features in Internet architecture.
“On Inferring Autonomous System Relationships in the Internet” by Lixin Gao [1] proposes an augmented graph representation that infers AS relationships classified as customer-provider, peering or sibling relationships. The author also presents heuristic algorithms for inferring these relationships. But first, the concept of an annotated AS graph and the theorems regarding the selective export rule (and the routing table entry patterns derived from it) are formally discussed. The author presents algorithms for the mentioned AS relationships based on the patterns. For inferring the first two relationships, the author constructed two algorithms: Basic and Refined. The difference of the two is that the first assumes that all BGP routers are configured correctly while the last perceives possible misconfigured BGP routers. For inferring peering relationships, the author presents the Final algorithm that simply checks if an AS pair does not transit traffic for each other. To test the accuracy of these algorithms, an experimental study of AS relationships in the Internet was done using BGP routing tables retrieved from the Route Views server in Oregon. Based from the results, more than 90.5% of the AS pairs have customer-provider relationships, less than 1.5% of the AS pairs have sibling relationships and less than 8% of the AS pairs have peering relationships. AT&T internal information checked the inference results and confirmed 100% of the inferred customers and peers and 20% of the inferred siblings. As a whole, 98.9% of all the inference results are confirmed by AT&T internal information. The inferred sibling results are also verified from WHOIS lookup service and more than half are confirmed. At the end of the paper, the author discussed the possible causes of unconfirmed siblings and these are: router configuration typo, misconfiguration of small ISPs, unusual AS relationships, and inaccuracy of the heuristic.
Evaluation
I think that this is a good study that must be continued rather updated since the Internet has experienced a huge increase in its size and complexity since it was commercialized and since the date that this paper was published. An example of updating would be to check the constants used for each algorithms like the constant R indicated in the Final Algorithm. Would it still be applicable today? Would it produce better results if it would increase its value?
A further study that must follow this research could be looking for solutions on the possible causes of unconfirmed cases. With the current technology, these misconfigurations may be lessened by improving the physical devices used for interdomain routing which could in turn improve also inferring AS relationships.
Reference:
[1] Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001
Global connectivity of millions of end-hosts worldwide is possible through interdomain routing in the Internet coordinated by BGP. BGP allows each AS to set its own routing policies. Oftentimes, contractual commercial agreements between administrative domains poses constraint on these routing policies e.g. A customer must not provide transit services between its providers. Indeed, policies like this shows that AS relationships stand as important features in Internet architecture.
“On Inferring Autonomous System Relationships in the Internet” by Lixin Gao [1] proposes an augmented graph representation that infers AS relationships classified as customer-provider, peering or sibling relationships. The author also presents heuristic algorithms for inferring these relationships. But first, the concept of an annotated AS graph and the theorems regarding the selective export rule (and the routing table entry patterns derived from it) are formally discussed. The author presents algorithms for the mentioned AS relationships based on the patterns. For inferring the first two relationships, the author constructed two algorithms: Basic and Refined. The difference of the two is that the first assumes that all BGP routers are configured correctly while the last perceives possible misconfigured BGP routers. For inferring peering relationships, the author presents the Final algorithm that simply checks if an AS pair does not transit traffic for each other. To test the accuracy of these algorithms, an experimental study of AS relationships in the Internet was done using BGP routing tables retrieved from the Route Views server in Oregon. Based from the results, more than 90.5% of the AS pairs have customer-provider relationships, less than 1.5% of the AS pairs have sibling relationships and less than 8% of the AS pairs have peering relationships. AT&T internal information checked the inference results and confirmed 100% of the inferred customers and peers and 20% of the inferred siblings. As a whole, 98.9% of all the inference results are confirmed by AT&T internal information. The inferred sibling results are also verified from WHOIS lookup service and more than half are confirmed. At the end of the paper, the author discussed the possible causes of unconfirmed siblings and these are: router configuration typo, misconfiguration of small ISPs, unusual AS relationships, and inaccuracy of the heuristic.
Evaluation
I think that this is a good study that must be continued rather updated since the Internet has experienced a huge increase in its size and complexity since it was commercialized and since the date that this paper was published. An example of updating would be to check the constants used for each algorithms like the constant R indicated in the Final Algorithm. Would it still be applicable today? Would it produce better results if it would increase its value?
A further study that must follow this research could be looking for solutions on the possible causes of unconfirmed cases. With the current technology, these misconfigurations may be lessened by improving the physical devices used for interdomain routing which could in turn improve also inferring AS relationships.
Reference:
[1] Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001
No comments:
Post a Comment