Redo literature review & reduce #routing policy references

[SichangHe]

• Section 1, page 1, left, §2) Almost half of your submission's references (20+) come from routing policies reference. While I agree this is an important point that can be mentioned, 2--3 exemplary references would have been sufficient. In fact, most of the cited works in this block don't have anything to do with IRR data.

[SichangHe]

• Lack of references on very related work

[SichangHe]

• Starting from the 5 references in review D, please perform a thorough literature review and extent your related work section with the currently missing RPSL-specific work.

References

[1] Khan, Akmal, et al. "A comparative Study on IP Prefixes and their Origin ASes in BGP and the IRR." ACM SIGCOMM Computer Communication Review 43.3 (2013): 16-24.

[2] Chang, Hyunseok, et al. "Towards capturing representative AS-level Internet topologies." Computer Networks 44.6 (2004): 737-755.

[3] He, Yihua, et al. "Lord of the links: a framework for discovering missing links in the internet topology." IEEE/ACM Transactions On Networking 17.2 (2008): 391-404.

[4] Battista, Giuseppe Di, Tiziana Refice, and Massimo Rimondini. "How to extract BGP peering information from the internet routing registry." Proceedings of the 2006 SIGCOMM workshop on Mining network data. 2006.

[5] Siganos, Georgos, and Michalis Faloutsos. "Analyzing BGP policies: Methodology and tool." IEEE INFOCOM 2004. Vol. 3. IEEE, 2004.

[SichangHe]

• Drastically cut down on the number of routing policy inference references (especially those that only appear as part of the group-citation on page 1).

[SichangHe]

[1] Khan, Akmal, et al. "A comparative Study on IP Prefixes and their Origin ASes in BGP and the IRR." ACM SIGCOMM Computer Communication Review 43.3 (2013): 16-24.

On a first look, this one only checks "IP Prefix"-"origin AS" (PO) pairs and only deals with route objects. They do highlight the usefulness of PO pair data in IRRs, though. They say the reliability vary, and routers could apply heuristics to rely on some IRRs.

[SichangHe]

This is the most relevant one:

[5] Siganos, Georgos, and Michalis Faloutsos. "Analyzing BGP policies: Methodology and tool." IEEE INFOCOM 2004. Vol. 3. IEEE, 2004.

This Ph.D. student made "Nemecis" for RPSL configuration or operation. All the links are dead and the tool is nowhere to be found, but I did find his presentation: https://www.youtube.com/watch?v=ioJMm_LNNj8

They infer business relationships from RPSL (edit: and apparently more, see my next comment), and store them in SQL; that is a higher-level and coarser abstraction than our interpretation approach. When neighbors' policies disagree, they just mark it as an error, throwing away information. With that, they match RPSL against BGP tables, and get a match number of 28%, which is much less information than we get.

They make several arguments we make, especially the ones regarding benefiting interdomain operation.

@cunha, have you ever heard of Nemecis? UC Riverside people did this, so it is not the same thing as IRRToolSet, which says USC in its license.

[SichangHe]

They mention some findings that we may shorten (Edit: we cannot really shorten because we do not explain them anyway):

• Rules referring to objects not registered.
• Huge as-sets as directed graphs with deep depth.

Things they do not do:

• Expose raw, analyzable RPSL information. They derive link-level policies and AS relationships, write them to SQL, and throw away the RPSL.
• Verify full BGP routes against RPSL. They only used BGP routing tables in these ways: verifying the origin of routes, checking if "links" are defined in policies¹, comparing business relationships from Gao's inference algorithm.
• Optimize for speed. They say they use Python + PostgreSQL.

Footnotes

1. They claim to use this "link-level policy" approach, which seems curious for me. A link seems to be "AS1 imports route X and exports it to AS2" by their definition, but it does not make sense when they start talking about importing and exporting ASes right afterwards. What is a "route" here? ↩

[cunha]

Just one comment on the title, we don't need to reduce the number of refs. We can just complement with the additional ones. It doesn't hurt to keep the previous references.

[SichangHe]

Also, they are using inetnum, which does not seem to be a thing any more Edit: it still pretty much is a thing; we just don't care about them.

[cunha]

What do you mean we don't care about them? inetnum objects just identify prefix delegations, no? Can they contain rich information (say remarks or some other metadata that could be relevant to routing policies)?

[SichangHe]

Just one comment on the title, we don't need to reduce the number of refs. We can just complement with the additional ones. It doesn't hurt to keep the previous references.

I think the problem with the refs is they do not match the text well. I wrote a comment in the text.

[SichangHe]

From Public internet routing registries (IRR) evolution by Akmal Khan, Hyunchul Kim, Ted "Taekyoung" Kwon, Yanghee Choi:

IRR routing information has not been used to the same extent (as BGP) due to known/assumed limitations of inconsistent data 1) static/voluntary nature of IRR) 2) stale, overlapping 3) incomplete information [4, 9].Current research has helped raised the issues surrounding IRR data but there are limited open source tools available which can help extract useful data from IRR [9,10,11]. There currently exists no strict linkage between RIRs allocation and IRR with the exception of some Réseaux IP Européens (RIPE NCC) mechanisms [6], Nor does there exists any linkage between RIRs and the actual routing system itself. Network Service Providers mainly employs IRR for routing policy generation and filtering of customers and peers [22].

[4] Battista, G.Di., Refice,T., Rimondini,M. : How to extract BGP peering information from the internet routing registry, SIGCOMM workshop on Mining network data, p.317-322, September 11-15, 2006, Pisa, Italy
[9] Siganos,G. and Faloutsos,M. : Analyzing BGP Policies: Methodology and Tool. In IEEE INFOCOM, 2004.
[10] Siganos,G. and Faloutsos,M. : A Blueprint for Improving the Robustness of Internet Routing, Security ‘06, 2006
[11] Sriram,K.,Borchert,O.,Kim,O.,Gleichmann,P., Montgomery.D : A Comparative Analysis of BGP Anomaly Detection and Robustness Algorithms, Cybersecurity Applications & Technology Conference for Homeland Security(CATCH), p.25-38, March 03-04, 2009
[22] Worldwide Infrastructure Security Report Arbor Networks 2009 from http://arbornetworks.com

Definitely going to include these references.

There still are limited open-source tools available.

Nemecis was open-source?? Where is it now?

[SichangHe]

This one is more like what we have done:

A Blueprint for Improving the Robustness of Internet Routing, Georgos Siganos, Michalis Faloutsos:

We validate a path from the point of view of an AS in the path. It is reasonable to expect that the AS that wants to validates its paths knows its policy, and thus can easily detect all deviations. In our case, since we are not the administrator of an AS, we use the IRR registries to check the paths for a number of ASes. […] First, we need to be able to understand the registered policy and match the import and export filters. Second, the policy should be consistent when checked against Internet routing, with a minimum requirement to register import and export rules for its neighbors in the path. We consider an AS as having a good policy if we can match a certain percentage of its policy, and we can check a percentage of the paths for policy correctness. If an AS doesn’t have good policy we exclude it from our study.

It is not clear how they are able to match these filters, given RPSL's crazy semantics, but I guess it does not matter.

They just "exclude" bad ASes from their studies, which loses information.

[SichangHe]

I have gone through every paper on Google Scholar that references Nemecis and has at least 2 citations. They are at the bottom of our Bib file, @cunha.

This should probably be good enough.

[SichangHe]

Towards Capturing Representative AS-Level Internet Topologies, Hyunseok Chang, Ramesh Govindan, Sugih Jamin, Scott J. Shenker, Walter Willinger:

RouteView is incomplete. IRRs reveal much more AS links (AS topologies). IRR cleaning experiments.

Lord of the Links: A Framework for Discovering Missing Links in the Internet Topology, Yihua He, Georgos Siganos, Michalis Faloutsos, Srikanth Krishnamurthy:

BGP + IRR + IXP + traceroute for AS links & topologies. Much more links, especially p2p.

A Systematic Framework for Unearthing the Missing Links: Measurements and Impact, Yihua He, Georgos Siganos, Michalis Faloutsos, Srikanth Krishnamurthy:

Mostly the same as above.

The Internet Dark Matter – on the Missing Links in the AS Connectivity Map, Rami Cohen, Danny Raz:

Estimating how many AS links are still missing using multiple sources. Uses Nemecis as is and does the same thing except they only use exports and infer business relationships differently.

IRRegularities in the Internet Routing Registry, Ben Du, Katherine Izhikevich, Sumanth Rao, Gautam Akiwate, Cecilia Testart, Alex C. Snoeren, kc claffy:

Good overview of IRR functionalities and significance; funny; only touches route objects.

A BGP Hijacking Detection Method based on Multi-dimensional Historical Data Analysis, Man Zeng, Heyang Li, Junyu Lai, Xiaohong Huang:

Another prefix-{AS origin} pair verification.

AS Relationships Inference from the Internet Routing Registries, Akmal Khan, Hyun-chul Kim, Ted Kwon:

Another business relationship inference algorithm using ASN and as-set.

[SichangHe]

@cunha, I've pushed the changes in the text I made during the flights. Please have a look.