Understanding AS relationships in the Internet can be useful to provide a deep understanding of traffic flow and also aiding ASes to make policy changes for improvement. Unfortunately these relationships are not known. The paper proposes generating an augmented AS graph that will represent the relation between ASes as customer-provider, provider-customer, peering and sibling relationship. Gao suggests that these relationships can be inferred from BGP routing table entries.
The author says that export policies depict the kind of relationship between ASes (export policies are explained in the previous post on interdomain routing). Based on the export policies the author explains a selective export rule and says that if the export policies adhere to the selective rule then the AS path of a routing table entry is Valley-Free. Valley free property states that after traversing a provider-to-customer or peer-to-peer edge the AS path cannot traverse a customer-to-provider or peer-to-peer edge. Routing table entry patterns have been classified as downhill path, uphill path, maximal uphill path and maximal downhill path.
The heuristic algorithm proposed in the paper rely on the assumption that a provider is larger in size than its customer and the size of an AS is proportional to its degree in the AS graph. In the AS graph, top provider of an AS path is the AS that has the highest degree among all ASes in the path.
The background needed for this paper requires a good understanding of BGP and the export and import policies. The Interdomain Internet Routing lecture reading is perfect to read before reading this paper.
The results provided in the paper are very promising with an accuracy of almost 99.1%. I was not very happy with the way the paper was written. It was little difficult to follow the proofs. Moreover I am curious to see how this method worked on other data. I have a feeling that the refined algorithm that handles misconfiguration by setting a value L may cherry pick a value.
I think it will be nice to discuss some other algorithms that were designed after this paper since this paper was the first one in this area of research . Also, how this research has benefited ASes, customers or providers in the real world. Overall the paper was an interesting read and is nice to have in the syllabus because it ties very well with the routing policies of BGP.
The author says that export policies depict the kind of relationship between ASes (export policies are explained in the previous post on interdomain routing). Based on the export policies the author explains a selective export rule and says that if the export policies adhere to the selective rule then the AS path of a routing table entry is Valley-Free. Valley free property states that after traversing a provider-to-customer or peer-to-peer edge the AS path cannot traverse a customer-to-provider or peer-to-peer edge. Routing table entry patterns have been classified as downhill path, uphill path, maximal uphill path and maximal downhill path.
The heuristic algorithm proposed in the paper rely on the assumption that a provider is larger in size than its customer and the size of an AS is proportional to its degree in the AS graph. In the AS graph, top provider of an AS path is the AS that has the highest degree among all ASes in the path.
The background needed for this paper requires a good understanding of BGP and the export and import policies. The Interdomain Internet Routing lecture reading is perfect to read before reading this paper.
The results provided in the paper are very promising with an accuracy of almost 99.1%. I was not very happy with the way the paper was written. It was little difficult to follow the proofs. Moreover I am curious to see how this method worked on other data. I have a feeling that the refined algorithm that handles misconfiguration by setting a value L may cherry pick a value.
I think it will be nice to discuss some other algorithms that were designed after this paper since this paper was the first one in this area of research . Also, how this research has benefited ASes, customers or providers in the real world. Overall the paper was an interesting read and is nice to have in the syllabus because it ties very well with the routing policies of BGP.
No comments:
Post a Comment