[ih] The story of BGP?

[Guy Almes]

Scott et al.,
   The last few days have been busy, so I'm only now reviewing this 
*very interesting* thread.
   I'll focus one the first of the original questions that Justine 
asked: Where did it come from?

   In the late 1980s I was leading one of the NSFnet regional networks 
and becoming active in the IETF.  We had an Interconnectivity Working 
Group to sort out issues involving the interplay of the new (e.g. 
non-government) parts of the rapidly growing Internet.
   The situation in the early NSFnet days included the use of EGP2 as 
the common exterior gateway protocol.
   The motivations was captured well by several (including by Yakov on 
his Google tech talk):
<> EGP2 would exchange complete sets of routes and it was layered 
directly over IP, so as the number of network numbers increased, it 
could not keep up.
<> EGP2 presupposed a very flat AS interconnectivity graph, essentially 
ARPAnet-centric to a shocking degree.
   Our little Interconnectivity Working Group was told *not* to invent a 
new protocol, and we were asked in 1988 to comment on a then-draft spec 
for a successor to EGP2, viz. EGP3.  EGP3 was, in many ways, well done 
and it was incremental and thus might have scaled well with regard to 
the rapidly growing number of networks.
   But EGP3 remained 'flat' in the sense above.
   Although we could see many trends in the evolution of Internet AS 
topology, I was one of those who, attracted by the many advantages of 
the hierarchical NSFnet backbone-regional-campus structure, were 
attracted to retain a notion of hierarchy of ASes, while recognizing 
that each agency (thing of 'agency' in the broad sense of an 
organization with a 'backbone' of sorts) might have its own top-level. 
Thus we considered what it would take to support a kind of forest of 
ASes, i.e., a set of hierarchical tree-structures.
   Could you make a minimal change to EGP3 and capture this forest idea?
   Maybe, by keeping two or maybe three ASes to capture where a route 
came from, things would work.
   At one point in a break during a meeting at NASA Ames, we discussed a 
computer programming idea called the "zero one infinity" concept, where 
you should have either zero of something, exactly one of something, or 
an open-ended array of many of something.  If keeping more than one AS 
was needed, maybe we should keep the whole AS path for each route.
   This idea was discarded at the time, but obviously reemerged in BGP 
and it is one of the key good ideas of BGP.
   So we were reluctant to jettison the idea of hierarchy, and we were 
reluctant to entertain variable-length AS-paths in a protocol, and we'd 
been told not to do a protocol.  Clearly, in hindsight, we were too timid.
   This was the situation in late 1988 and at the Interconnectivity 
Working Group session at the January 1989 IETF meeting in Austin. 
During a break after that working group session, Yakov Rekhter and Kirk 
Lougheed wrote the three napkins that made key breakthroughs:
<> use of TCP to get rid of message length issue (and solve other problems),
<> incremental updates, and (to me most important)
<> use of a full AS path for each route.
   Yakhov does a great job describing this "three napkin" design and 
how, within a few months, there were multiple, well two at least, 
independent implementations.

   With BGP, any motivation for doing EGP3 evaporated.

   By the Hawaii IETF (October 1989), there was already the beginning of 
a version 2 BGP.  Practicality, implementability, and flexibility were 
so evident so quickly.

   I hope this is useful to Justine and others.

   And I'll leave to others the telling of the story post-1989.
   	-- Guy

On 2/8/13 2:02 PM, Scott Brim wrote:
> On Fri, Feb 8, 2013 at 2:41 PM, John Curran <jcurran at istaff.org> wrote:
>>> One of the most entertaining moments in my history of IETF involvement
>>> was when Hans-Werner Braun and I explained NSFNet and ARPAnet routing
>>> interworking.  Everything was still hierarchical so we did it all with
>>> RIP and a lot of following default routes.  Dave Clark slapped his
>>> forehead.  Jon Postel just shook his head.  Yes we needed something
>>> like BGP but that took a few years.
>>
>> Yes, it was RFC 1092/1093 that nicely documented the problem with strictly hierarchical
>> EGP routing when the topology actually wasn't hierarchical... EGP+IGRP combined with the
>> exceptions for the interesting lateral connections often resulted in breakage for anyone
>> at multiple NSFNET NSS connections (e.g. CSNET with NSS 8/JVNC, NSS 6/SDSC) unless some
>> real care was taken in configs.
>
> 1989 is the earliest we have for documenting that?  We knew it at least in 1986.
>