[ih] The story of BGP?
galmes at tamu.edu
Fri Feb 8 15:42:45 PST 2013
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,
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.
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.
More information about the Internet-history