Bibliography

Architectural Issues for Identifiers and Locators by Dave Thaler @ IETF#68

IST RiNG Reading List

Proxying Approach to SHIM6 and HIP (PASH)

Identifier / Locator Separation: Exploration of the Design Space (ILSE)

Proxy Shim6 (P-Shim6)

NERD: A Not-so-novel EID to RLOC Database

http://www.sics.se/~bengta/papers/node-id-arch.pdf http://www.sics.se/openhouse2006/Presentations/NodeID.pdf http://www.sics.se/~bengta/papers/node-id-arch.pdf

Who are you? (by Geoff Huston)

---

''This is a selection of material available on the web that you might like to sample before attending the workshop. The organizers would like to recommend that you read the two IRTF drafts'' '''''(Analysis of IDR requirements and History''''' ''and'' '''''Requirements for Inter-Domain Routing)'''' plus the two documents listed under'' '''''Problem Statements''''' ''below as a basic preparation for the workshop. Some other material may be recommended for other sessions. The material to some extent represents the personal prejudices of the main compiler (Elwyn Davies). Additional suggestions are welcome if you have material that you think may be relevant.''

---

= 30 years on... =

'''o A Note on Inter-Network Naming, Addressing, and Routing''' [http://ana-3.lcs.mit.edu/~jnc/tech/ien/ien19.txt IEN 19] So what have we achieved since 1978? Includes a discussion of the effects of matching hierarchical addressing to hierarchical routing topology, and the impact of this on reliability (multihoming).

'''o Why the Internet Only Just Works''' [http://www.cs.ucl.ac.uk/staff/M.Handley/papers/only-just-works.pdf] The Internet is going to suffer growing pains as it progresses from providing 80% of the functionality to providing 90+% of the functionality, as called for by the new requirements. The track record is not at all good - the history of major changes that have been successful is one of changes implemented at the last minute. This should not be a surprise - there are always too many immediate issues to be concerned with to invest time and money on those that are not currently critical. And consensus for architectural change is very hard to reach unless faced with a specific and pressing problem.

---

= History =

= How we got to where we are =

'''o Analysis of IDR requirements and History''' [http://www.ietf.org/internet-drafts/draft-irtf-routing-history-03.txt draft-irtf-routing-history-03] This document which has been under construction for several years contains useful references to many of the developments that lead to the current state of play (including Nimrod and OSI) together with an analysis of the legacy of RFC1126.

= Noel Chiappa and Nimrod =

'''o Endpoints and Endpoint Names: A Proposed Enhancement to the Internet Architecture''' [http://users.exis.net/~jnc/tech/endpoints.txt (I-D)]

'''o Will The Real "End-End Principle" Please Stand Up?''' [http://users.exis.net/~jnc/tech/end_end.html (commentary)]

---

= Previous Sets of Requirements =

'''o Goals and functional requirements for inter-autonomous system routing''' [http://www.ietf.org/rfc/rfc1126.txt RFC1126] Developed in parallel with BGP but not necessarily the requirements fulfilled by BGP.

'''o Requirements for Inter-Domain Routing''' [http://www.ietf.org/internet-drafts/draft-irtf-routing-reqs-05.txt draft-irtf-routing-reqs-05] This covers the output from two groups of 'experts' back in 2001 looking at what might be required to improve Inter-Domain Routing. The first set was set up by the IRTF RRG and started from a potential clean sheet, whereas the other group was a self-appointed bunch organized by Loa Anderson under the 'Babylon' banner and endeavoured to propose an evolutional approach. You are invited to spot the differences!

---

= Problem Statements =

'''o Some Foundational Problems in Interdomain Routing''' [http://nms.lcs.mit.edu/papers/camera.pdf (paper)] Paper by Jennifer Rexford and others from late 2004 which attempts to answer the question 'Which problems and properties of interdomain routing stem from the particular vagaries of BGP, and which represent fundamental limitations and challenges of scalable policy-based routing?' As the question implies it particularly addresses issues of policy and scalability, which are, to my (Elwyn's) mind, particularly germane.

'''o Beyond Interdomain Reachability''' [http://www.net.informatik.tu-muenchen.de/wired/position/bonaventure-wired.pdf (paper)] Olivier Bonaventure's position paper for the WIRED 2003 workshop looks briefly at the problems with the BGP decision process and traffic engineering and cites a raft of papers that look at alternatives (and the status quo).

---

= Other Workshops =

= Earlier Workshops =

'''o Workshop on Internet Routing Evolution and Design 2003''' [http://www.net.informatik.tu-muenchen.de/wired/ WIRED] Invitational workshop in 2003. AFAICS there is no published overview of conclusions but the position papers are very interesting. Another workshop is being held this year more or less in parallel with the IAB session.

'''o Geoff Huston's Notes on Inter-Domain Routing Workshop 2004''' [http://www.potaroo.net/ispcol/2004-03/2004-03-isp.htm The State of Inter-Domain Routing] This describes a workshop held just prior to RIPE 48. The submissions to the workshop can be found [http://www.tm.uni-karlsruhe.de/idrws2/submissions.php?year=2004 here]. Allegedly they are thinking of holding another workshop this year.

=  Current Workshops =

'''o Report from the Clean Slate Network Research post­SIGCOMM 2006 Workshop''' [http://www.cl.cam.ac.uk/Research/SRG/netos/cleanslate/ccr-report.pdf CleanSlate^?] This contains a small section on Routing mainly talking about Tim Griffin's Meta-Routing (see below).

'''o Workshop on Internet Routing Evolution and Design 2006''' [http://wired2006.org/attendees.html WIRED 2] Position papers from the upcoming WIRED 2nd Edition.

---

= The State of the Routing World =

''Geoff Huston monitors the BGP world very closely. He maintains the [http://www.cidr-report.org/ CIDR Report] and the [http://bgp.potaroo.net/ BGP Report] which provide up to the minute statistics, and [http://www.potaroo.net his web site] contains many interesting articles on routing and other aspects of Internet technology. Other places to look for information about the state of the routing world include [http://www.caida.org/home/ CAIDA] which has recently started the [http://imdc.datcat.org/ Internet Measurement Data Catalog], and Merit Network Inc's [http://www.merit.edu/nrd/services/radb.html RADb (The Routing Assets Database)].''

'''o [http://www.potaroo.net/ispcol/2006-06/bgpupds.html The BGP Report for 2005]''' Geoff Huston's analysis of the state of the IDR system and predictions for the future. Essential reading.

'''o [http://www.apnic.net/meetings/21/docs/sigs/routing/routing-pres-huston-routing-update.pdf 2005 – A BGP Year in Review]''' Geoff Huston's presentation to APNIC 21 in March 2006. The [http://www.apnic.net/meetings/21/programme/audio-archive/routing/huston.mp3 audio from Geoff's talk] is also archived on the APNIC web site - without it the significance of many of the graphs is not too clear.

---

= 'New' Routing Schemes =

= GSE and Related Proposals for Solving Multihoming Scalability in IPv6 =

'''o GSE--An Alternate Addressing Architecture for IPv6''' [http://www.watersprings.org/pub/id/draft-ietf-ipngwg-gseaddr-00.txt draft-ietf-ipngwg-gseaddr-00.txt] Mike O'Dell, February 1997.

'''o The Map & Encap Scheme for scalable IPv4 routing with portable site prefixes''' [http://www.cs.ucla.edu/~lixia/map-n-encap.pdf map-n-encap] Steve Deering, March 1996 (presentation).

'''o New Scheme for Internet Routing and Addressing (ENCAPS) for IPNG''' [http://www.ietf.org/rfc/rfc1955.txt rfc1955.txt] Bob Hinden, June 1996, RFC1955.

'''o An Overview of Multihoming and Open Issues in GSE''' [http://www.cs.ucla.edu/~lixia/0609GSE_Overview.pdf GSE_Overview.pdf] Lixia Zhang, September 2006 (wrote for IETF Journal)

= More Recent Research Proposals =

'''o Meta-Routing''' [http://www.acm.org/sigs/sigcomm/sigcomm2005/paper-GriSob.pdf (paper)] '' Tim Griffin and Joao Luıs Sobrinho'' A note on a way to define routing protocols. Tim Griffin is (IMO) ''the'' theoretical expert on BGP. His web page at the University of Cambridge is [http://www.cl.cam.ac.uk/~tgg22/ here] and contains many interesting papers on the stability of BGP.

'''o HLP: A Next Generation Interdomain Routing Protocol''' [http://www.acm.org/sigs/sigcomm/sigcomm2005/paper-SubCae.pdf (paper)] Mark Handley and friends' take on a hybrid Inter-Domain Routing protocol that moves the BGP problem 'up a layer' and has various provably good properties as regards policies.

'''o DARPA NewArch^? Project''' [http://www.isi.edu/newarch/index.html (Project Home Page)] This project investigated various issues in network architecture. Several papers on this site are relevant including [http://www.isi.edu/newarch/DOCUMENTS/yang.nira.pdf NIRA: A New Internet Routing Architecture] and (maybe) [http://www.isi.edu/newarch/fara.html FARA: Reorganizing the Addressing Architecture].

---

= Overlay Networks and Policy Distribution Networks =

''Various solutions have been proposed which involve overlaying an extra (control) network layer on the existing BGP routing control system''

'''o Resilient Overlay Networks''' [http://nms.lcs.mit.edu/papers/ron-sosp2001.pdf (paper)] ''Andersen et al (2001)'' Looks at ways of providing resilient (multihomed) application level service through an overlay network that monitors connections and speeds up rerouting to seconds rather than minutes.

'' The next paper is part of the PlanetLab Routing Overlay Networks project. More papers related to this can be found at [http://www.planet-lab-jp.org/pluto/routingoverlay.html PlanetLab^? PLUTO Routing Overlay Networks Project web page].''

'''o Scalable Routing Overlay Networks''' [http://delivery.acm.org/10.1145/1120000/1113372/p49-nakao.pdf (paper)] ''Akiiro Nakao, Larry Peterson and Andy Bavier'' Routing overlays have become a viable approach to working around slow BGP convergence and sub-optimal path selection, as well as to deploy novel forwarding architectures. A common sub-component of a routing overlay is a routing mesh: This paper proposes and evaluates a low-cost approach to building a topology-aware routing mesh that eliminates virtual links that contain duplicate physical segments in the underlying network.

'''o Pagoda: A Dynamic Overlay Network for Data Mangement, Routing and Multicasting''' [http://www.cs.jhu.edu/~kishore/pagoda.ps (paper)] Not directly relevant but addresses routing in overlays as a critical feature.

'''o OPCA: Robust Interdomain Policy Routing and Traffic Control''' [http://sahara.cs.berkeley.edu/papers/ACK03.pdf (paper)] ''Sharad Agarwal, Chen-Nee Chuah and Randy H Katz'' Proposes a policy control architecture that runs as an overlay network on top of BGP. OPCA allows an AS to make route change requests at other, remote, ASs to achieve faster route fail-over and provide capabilities to control traffic entering the local AS. Whether this architecture would actually work given the commercial competition between ASs and secretiveness regarding actual policies is unclear. Opinions are welcome!

---

= Compact Routing - A Whole New Way to Route Traffic = '''o Toward Compact Interdomain Routing''' [http://arxiv.org/PS_cache/cs/pdf/0508/0508021.pdf (paper)] Dmitri Krioukov and kc claffy suggest that compact routing is a possible permanent solution to the scaling problems of inter-domain routing. This paper discusses the apparent failure of current routing algorithms and attributes it to the ever less hierarchical nature of the inter-AS graph which appears to be nearer to ''scale-free'', leading to low AS hop counts and making the analysis in Kleinrock and Kamoun's classic analysis (Elwyn has a machine readable copy of this paper if anybody wants to go back that far!) inapplicable.

'''o Compact Routing with Minimum Stretch''' [http://www.eecs.tufts.edu/~cowen/sodasap.ps (paper)]

'''o Compact Routing on Internet-Like Graphs (2003)''' [http://citeseer.ist.psu.edu/651100.html (paper)] We show the TZ scheme works very well on Internet inter-AS graph, both in terms of average stretch (~1.1) and table size for the Internet at approx 50 entries. This paper pre-dated the name-indepent work (see below).

'''o Compact Name-Independent Routing with Minimum Stretch (2004)''' [http://www.cs.huji.ac.il/~ittaia/papers/AGMNT04.pdf (paper)]

---

= Policy and Configuration Problems in BGP4 =

''I make no apology for including three papers by Nick Feamster and Hari Balakrishnan. These papers are an excellent introduction to ways of improving configuration of BGP. IMO this kind of approach would actually help solve both many of the practical problems we face with the larger routing tables and provide a stopgap until the architecture can be improved. Nick Feamster claims that he is working on the architecture also - see [http://www-static.cc.gatech.edu/~feamster/ Nick Feamster's Home Page] and the [http://www-static.cc.gatech.edu/~feamster/papers/cabo-tr.pdf Cabo paper] which recomends ''virtualization'' as a solution to the overall architecture. Whether virtualization with many 'concurrent internets' helps the routing scaling problem is not clear.''

'''o Towards a Logic for WideArea Internet Routing''' [http://www-static.cc.gatech.edu/~feamster/publications/logic-sigcomm2003.pdf (paper)] ''Nick Feamster and Hari Balakrishnan'' This paper proposes a set of rules - the ''routing logic'' of the title - that can be used to determine whether a routing protocol satisfies various properties.

'''o Verifying the Correctness of Wide-Area Internet Routing''' [http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-948.pdf (paper)] ''Nick Feamster and Hari Balakrishnan'' The theoretical basis for the analysis framework used in the '''''rcc''''' tool described in the next reference. Looks at what conditions represent 'correctness' in a BGP configuration. Correctness properties are Validity, Visibility, Information Flow Control, Determinism and Safety.

'''o Detecting BGP Configuration Faults with Static Analysis'''' [http://www-static.cc.gatech.edu/~feamster/publications/rcc-nsdi-camera.pdf (paper)] ''Nick Feamster and Hari Balakrishnan'' Description of the '''''rcc''''' tool designed to check the BGP configurations of routers across an AS. This paper also contains an analysis of about 75000 emails on the '''NANOG''' operational problem reporting mailing list, and identifies a number of key problems relating to misconfiguration both at the individual router and inter-router levels.

'''o BGP routing policies in ISP networks''' [http://www.cs.princeton.edu/~jrex/papers/policies.pdf (paper)] ''Matthew Caear and Jennifer Rexford'' Looks at the goals that operators have and their resulting routing policies, why BGP evolved the way it did and how common policies are implemented using BGP. Discusses recent work that aims to address problems that arise in applying and supporting routing policies.

'''o How large ISPs redistribute non-BGP customer routes into iBGP''' [http://www1.tools.ietf.org/group/iab/workshop/2006/routing/attachment/wiki/RawBibliography/bgp-internal.pdf?format=raw (book excerpt)] ''Iljitsch van Beijnum'' To keep their IGP such as OSPF or IS-IS lean and mean, large ISPs often put their customer routes (for non-BGP customers) in iBGP. These book pages explain how this is done with examples for Cisco IOS. Please don't distribute.

= The Effects on Routing Hardware =

'''o An Empirical Study of Router Response to Large BGP Routing Table Load''' [http://www.isi.edu/~johnh/PAPERS/Chang02a.pdf (paper)] ''Di-Fa Chang, Ramesh Govindan and John Heidemann'' Looks at the detailed mechanics of router response to getting a 'large' BGP routing table. Anecdotal evidence indicates that this happens from time to time because of miscobfiguration. Is this (2002) work still relevant in 2006?

---

= Proprietary Solutions =

''The comments are marketing 'blurb' taken from the companies' web sites. I have a little knowledge of Internap but none of Equinix and inclusion here does not represent endorsement or otherwise of the product''

'''o Internap Route Control Technology''' [http://www.internap.com/solutions/routecontrol/page1980.html (web page)] Claims to ''overcome the weaknesses of BGP'' in a multihoming situation. ''Continually monitors the available routes leading away from your network to the end destination and chooses the most appropraiate pathway in real time.''

'''o Equinix Direct''' [http://www.equinix.com/prod_serv/network/ed.htm (web page)] ''Equinix has developed a service, which automates provisioning, multi-homing and billing to multiple upstream networks through a single, easy-to-use, secure interface that is completely under customer control.''

---

[wiki:WikiStart Back to Routing and Addressing Workshop main page]

''Version 1.2, 6 October 2006''

-- ElwynDavies - 07 Jun 2007