[ih] The story of BGP?

[Guy Almes]

Noel,
   Very good points.
   Sticking with Justine's original questions and with focus on the 
transition from the ARPAnet-centric EGP2 era to the early BGP era, what 
was important was not the ARPAnet being shut down in 1988, but the 
emergence of the *highly* multi-AS Internet.
   And the slightly subtle thing about it was that, not only was the 
number of ASes growing rapidly, but that their topology became 
distinctly non-hierarchical.
   My memory of the 1986-87 era is that all the stated intentions of 
official policy makers was to support the continuation of some kind of 
hierarchy.
   To speak positively, for example, the quite hierarchical NSFnet 
structure (with a single backbone connecting roughly two dozen regional 
networks, each connecting few => dozens of universities) was capable of 
rapid and somewhat orderly growth due to this hierarchy.
   And 1987-era talk of the Interagency Research Internet promoted the 
collegial notion of a kind of forest of such hierarchical structures and 
this, in principle, was sensible and important in keeping the Internet 
"whole" during this period.
   Thus forms of EGP2 successors that would have supported a tree or a 
forest or a directed acyclic graph of ASes or a forest of such DAGs 
(with a distinct up-down aspect to each AS-to-AS connection with the 
exception of major inter-agency exchange points) had a certain appeal.
   But evolving EGP2 to support such an "orderly" forest of DAGs was 
doomed, both because of the complexity of dealing with it and also 
because, "on the ground" cyclic/non-hierarchical interconnections of 
ASes were beginning to happen.

   In this context, BGP made several breakthroughs:
<> use of full AS path is the "metric"
<> cutting the Gordian knot of hierarchy by simply accepting a general 
topology
<> accepting variable-length fields within BGP messages (if only to 
support these full AS paths)
<> using TCP and thereby dramatically simplifying the protocol
   We've had BGP around for so long that we are tempted to underestimate 
these breakthroughs.  (I omit incremental updates only because it was 
present in the EGP3 draft and (purely personal opinion) it was less of a 
breakthrough than the others.)

   There's much to admire here.
   The key aspect of BGP that, even after the acceptance of BGP as the 
common exterior gateway protocol, was non-obvious was the messiness of 
interpreting/using these full AS paths as "metrics".  Yakov's emphasis 
was that when a given BGP-speaking router receives multiple alternate 
routes for a given prefix (with differing next-hop border routers and 
differing full AS paths), the decision of which of the alternate routes 
to use and propagate is a "local decision".  By insisting on its being a 
purely local decision, BGP itself was, of course, dramatically 
simplified and the nature of the inter-AS topology was allowed to grow 
in highly dynamic (viral?) ways.
   One can, however, imagine trying to work out a non-local way of 
interpreting these full AS paths.  In hindsight, that would have been a 
bit doomed, but it was not totally obvious at the time.
   *If* this had been done, there would have been several advantages:
<> better routes (usually),
<> simpler BGP configurations (by avoiding the often-byzantine tactics 
to explain the logic of your "local decision" to your border router, and
<> the possibility of a link-state successor to BGP.
And, of course, key disadvantages:
<> elevating local inter-AS routing decisions, which inevitably mixed 
technical, operational, and business aspects to being non-local / 
community / political decisions.

   Instead, of course, we have very messy BGP configurations.
   These stemmed, in part, from the early BGP implementations using the 
full AS path *length* as the de-facto "metric".
   That was implementable, but obviously resulted in weak selections of 
inter-AS routes.  The patches to BGP to ameliorate this weakness are 
perhaps both regrettable and inevitable.

	-- Guy

On 2/10/13 8:57 PM, Noel Chiappa wrote:
>      > From: Tony Li <tony.li at comcast.net>
>
>      >>> The transition was more in the '91-'93 window. The urgency to publish
>      >>> the RFC was far lower than the need to have working code and a
>      >>> working network.
>
>      >> Are you talking about the transition to BGP-4, or the transition to
>      >> BGP?
>
>      > The transition to BGP.
>
> Ah, OK. But the BGP-3 spec came out in October '91, so it seems the specs
> didn't lag as much as you seem to be indicating it did?
>
> (There was also a version of the BGP spec which came out in June 1990 -
> RFC-1163 - which doesn't have a number on it, but that must have been BGP-2,
> although I'm not sure that term was ever used.)
>
>
>      >>>> Was the shutdown of the ARPAnet a big factor?
>
>      >>> Absolutely.
>
>      >> I'm trying to see how this can be?
>
>      > Recall that with the ARPAnet, we were all directly homed to 14/8 (and =
>      > 10/8 for MILnet).
>
> ??? The ARPANET was 10/8, and the MILNET 26/8? 14.8 was the global X.25
> network?
>
>      > Shutting down the ARPAnet is what triggered the creation of NSFnet,
>      > which in turn resulted in the NSFnet regional networks.
>      > ...
>      > NSFnet would not have been necessary except for the planned
>      > decommissioning of ARPAnet.
>
> Ah, now I see what your reasoning is. However, I'm not sure this is what
> happened?
>
> The 56KB NSFNET was started in 1985 (I remember the Proteon/Cisco/Fuzzball
> selection meeting), and entered service early in 1986. However, the decision
> to shut down the ARPANET was made by Mark Pullen, who came to DARPA in 1987.
> Likewise, the first regionals were started before 1987. IIRC, NYSRENET and
> SURANET were both started before then.
>
> Yes, the availability of the NSFNET and regionals allowed Mark to 'pull the
> plug' on the ARPANET - but the evolution of the Internet to a
> 'multi-backbone' system was already underway when he did so - and, in fact,
> it was inevitable.
>
> Remember, use of the ARPANET was restricted to people with a DoD/DoE/NASA
> contract/connection, whereas NSF wanted to make their network accessible to
> everyone: that was the reason behind CSNET (in the early 1980s) and the
> 56K-phase NSFNET. In addition, as I indicated previously:
>
>      >> Simply speeding up the ARPANET, to avoid the growt of the alternate
>      >> backbones, was not an option. The ARPANET's whole architecture was
>      >> just not suitable for high speeds. In particular, the
>      >> 8-outstanding-packet limit [per 'link'] would have been a killer -
>      >> particularly as all IP traffic shared one 'link'.)
>
> So, again, I'm not sure the shutdown of the ARPANET was that important an
> influence in the evolution of the Internet.
>
>
> BTW, there's a nice site with a bunch of presentations on it:
>
>    http://www.nsfnet-legacy.org/
>
> about the background to, and the history of, the NSFNet, and also some of the
> regionals. One of the sessions:
>
>    http://www.nsfnet-legacy.org/archives/04--T1.pdf
>
> includes a presentation by Yakov giving the early history of BGP. (Maybe this
> is the same thing as the YouTube thingy?)
>
> 	Noel
>