[ih] Exterior Gateway Protocol
Guy Almes
galmes at tamu.edu
Wed Sep 2 17:24:38 PDT 2020
Hi Geoff,
You ask about how SPF (shortest path first) fits in.
I'll try to answer, keeping in mind that this is a history list (and
not a deep routing-technical list).
At the outset, the basic concept of an Autonomous System (AS) is so
important. I appreciate Jack Haverty's message describing how he and
Eric Rosen came up with it at BBN. An AS is a set of routers (fine
point: not a set of networks) under a single technical/administrative unit.
This naturally led to the distinction between routing protocols for
use within an AS (an Interior Gateway Protocol) and for use between
pairs of ASes (an Exterior Gateway Protocol).
While not strictly necessary, this has led to a variety of IGPs
(since each AS can make its own decision about this) vs uniformity of an
EGP (since all the ASes need to agree on them). Thus, there is usually
only one 'EGP' (EGPv2 during the period 1986 to 1990, BGP since about
1990, and an awkward period during the transition).
Within the world of IGPs of that era, most were distance-vector.
With history going back to the original ARPAnet routing protocol, these
included (in the 1986-1990 era):
<> RIP, using hop count as its metric,
<> Hello, from Dave Mills including in his Fuzzball routers, using delay
as its metric (sometimes measured delay, but more often configured
delay), and
<> IGRP, from Cisco, with an interesting combination of min-bandwidth
and sum-of-delay metrics.
These were relatively simple to implement and could exhibit nasty
"counting to infinity" problems.
And there were shortest-path-first (alias link-state) protocols.
With history going back to the second ARPAnet routing protocol, these
included:
<> ISIS, from the DECnet effort, and
<> OSPF, for Open Shortest Path First, from the IETF.
These were more sophisticated both in theory and practice, but converged
quickly and had other nice technical properties. A key challenge is
that the SPF algorithm is executed on all the routers within the AS in a
consistent way; if done correctly, this can result in nicely optimized
routes and rapid convergence times.
It's worth noting that BGP can be viewed as a distance-vector
protocol, with the entire AS-path as its metric. Note that BGP does
*not* dictate which of several possible routes a given AS will prefer
(and propagate). And, sure enough, it can exhibit a really nasty
version of the "counting to infinity" problem.
While I'm not aware of anyone actually doing this, it is interesting
to contemplate what an SPF-based *EGP*. This could have advantages
(e.g., more optimal inter-AS routing and rapid convergence times), but
having any Global agreement on which inter-AS routes will be preferred
would be very unlikely.
So, in practice, SPF technology is only used in IGPs.
Again, I focus on the late 1980s for historical focus. And also,
since, once a pretty good system, especially with BGP in the generic
EGP/inter-AS context, evolves, it's hard to make big changes.
Comments?
-- Guy
On 9/2/20 6:08 PM, the keyboard of geoff goodfellow wrote:
> gents, in the midst of this EGP/IGP/BGP recollectioning:
> where did/does SFP fit in with gateway protocol historying?
> geoff
>
> On Wed, Sep 2, 2020 at 11:10 AM Guy Almes via Internet-history
> <internet-history at elists.isoc.org
> <mailto:internet-history at elists.isoc.org>> wrote:
>
> Craig et al.,
> 1987 was an interesting year. The NSFnet-related regional networks
> were connecting new sites and had to solve interesting routing problems.
> EGP would tell you that a given network was reachable via a given
> gateway router / AS. But that network might be reachable via two
> different gateways.
> During that era, our "Sesquinet" regional network in Texas was
> connected to two different valuable "backbone" type networks: the
> Fuzzball-based proto-NSFnet via Boulder and the ARPAnet via Austin.
> Both were useful. Both had 56kb/s circuits. Both were congested.
> At that time, there were a few hundred networks, and I recall going
> through the whole list, one by one, figuring out whether, if they were
> reachable via both the ARPAnet and the proto-NSFnet, which should be
> preferred. I considered it worth doing, but it was of course Quixotic,
> given the rapidly growing number of connected networks.
>
> Phill Gross asked me to lead an "Interconnectivity Working Group"
> within the IETF and work to solve some of these problems. It was a
> great group, with members from the ARPAnet, NSFnet, NASA, ESnet, and
> other communities. Understanding the various "backbones", their
> differing technical and policy natures, and the limitations of EGP all
> made for fascinating discussions, which did allow us to make progress.
> One of our explicit marching orders was *not* to invent a new
> protocol.
> But we did discuss the problem of how to choose which of two
> exterior
> routes to use when both advertised a given network.
> One line of thought was to consider that the Internet, while not
> having a "tree topology", did have a notion of levels of hierarchy,
> e.g., campus, then regional, then national backbone, then international
> links. I am grateful that we fairly quickly realized that relying on
> that notion of hierarchy would be building on sand.
> But what kind of "metric" could be used to help make routing
> decisions?
> One idea, based on Cicso's IGRP protocol was to characterize each
> transit network with a bandwidth and a delay metric. Then minimum of
> bandwidth along a path and sum of delay along a path could be used.
> That did not get traction.
> I'd been teaching a computer scientist where an idea called the
> "zero, one, infinity rule" was discussed. As applied here, if a single
> scalar number would not suffice as a metric, then allow a metric of
> variable length. For example, a whole AS-path could be an interesting
> kind of metric could be used. But, particularly during that era,
> variable-length fields in protocols were not in favor, and we did not
> pursue this idea.
> Except that, at our next working group meeting (at the January 1989
> IETF meeting at UT-Austin), Kirk Lougheed (Cisco) and Yakov Rekhter
> (IBM) invented BGP in one of the Internet's most famous napkins. The
> complete AS-path, variable though it was, was a key idea.
> BGP solved several problems with EGP.
> I should emphasize that the AS-path was never exactly regarded as a
> "metric", but it provided valuable information. I'll avoid going
> further with the evolution of BGP, but it was so much better than its
> predecessor and came along at a very fortunate time.
>
> -- Guy
>
> On 9/2/20 3:57 PM, Craig Partridge via Internet-history wrote:
> > There was a SIGCOMM '87 paper by Mills and Hans-Werner Braun that
> discussed
> > what happened when you tried to break the tree topology.
> >
> > Craig
> >
> > On Wed, Sep 2, 2020 at 1:52 PM Scott O. Bradner via
> Internet-history <
> > internet-history at elists.isoc.org
> <mailto:internet-history at elists.isoc.org>> wrote:
> >
> >> I found a printout of my late 1990s notes which said that EGP
> was "limited
> >> to a tree structured Internet"
> >> although I recall that people were hacking it to expand its
> usefulness but
> >> the result was not pretty
> >>
> >> Scott
> >>
> >>
> >>> On Sep 2, 2020, at 3:45 PM, Barbara Denny <b_a_denny at yahoo.com
> <mailto:b_a_denny at yahoo.com>> wrote:
> >>>
> >>> That is my recollection too. EGP had topology constraints.
> >>>
> >>> barbara
> >>>
> >>> On Wednesday, September 2, 2020, 08:07:37 AM PDT, Scott O.
> Bradner via
> >> Internet-history <internet-history at elists.isoc.org
> <mailto:internet-history at elists.isoc.org>> wrote:
> >>>
> >>>
> >>> my recollection was that EGP could not be twisted enough to be
> able to
> >> deal with the actual
> >>> topology that was evolving on the Internet
> >>>
> >>> Scott
> >>>
> >>> ps - I tried to open an old powerpoint presentation (from the late
> >> 1990s) where I discussed EGP & BGP
> >>> but it seem like the oldest version of PowerPoint I have had
> evolved
> >> enough that it will no longer open
> >>> that version - I mention that because there is yet again a
> discussion
> >> on the IETF list about RFC formats
> >>> and some people have argued, as people have argued for at least 20
> >> years, that moving to MS Word
> >>> would be a good thing
> >>>
> >>>
> >>>
> >>>> On Sep 2, 2020, at 10:39 AM, Grant Taylor via Internet-history <
> >> internet-history at elists.isoc.org
> <mailto:internet-history at elists.isoc.org>> wrote:
> >>>>
> >>>> On 9/2/20 7:55 AM, Dan York via Internet-history wrote:
> >>>>> Grant,
> >>>>
> >>>> Hi,
> >>>>
> >>>>> It also needs more explanation that EGP was replaced by BGP. (The
> >> current sentence there says “essentially replaced” and is a bit
> vague with
> >> no references.)
> >>>>
> >>>> Hum.
> >>>>
> >>>>> If any of you all here know of any RFCs that explicitly
> indicate EGP
> >> was replaced/obsoleted, or if you know of any journal articles,
> academic
> >> papers, historical documents, etc., that could be useful, I
> would be glad
> >> to update the article a bit. Or if you can point me to any info
> about the
> >> creation of EGP (there’s a line that needs a source). Or any
> other info you
> >> think would be useful in this Wikipedia article, that would be
> great.
> >>>>
> >>>> I found a some information about EGP in and around the gated
> routing
> >> daemon. I wonder if there might be some more information that
> could help
> >> you.
> >>>>
> >>>>> (Note that for info to appear in the English version of
> Wikipedia, it
> >> needs to be backed up by a “reliable source” -
> >>
> https://urldefense.com/v3/__https://en.wikipedia.org/wiki/Wikipedia:Reliable_sources__;!!KwNVnqRv!VGbu8UR1ds9tLcdTmqj_BlSaJwdAR7VMX3YliVLEE7V0gQyXuH0Pp6ld3QEI5A$
> - which includes
> >> journal articles, academic papers, news articles, RFCs, etc.)
> >>>>
> >>>> I wonder if you can find any graphs on the number of Internet
> >> connections using BGP. If similar ever existed for EGP, you can
> probably
> >> compare / contrast the two.
> >>>>
> >>>> I also think that the lack of contemporary EGP implementations is
> >> evidence of BGP's replacement of EGP. As is the fact that BGP
> supports
> >> things that EGP does not. Things which are used all over the
> Internet,
> >> e.g. multipath.
> >>>>
> >>>>
> >>>>
> >>>> --
> >>>> Grant. . . .
> >>>> unix || die
> >>>>
> >>>> --
> >>>> Internet-history mailing list
> >>>> Internet-history at elists.isoc.org
> <mailto:Internet-history at elists.isoc.org>
> >>>>
> https://urldefense.com/v3/__https://elists.isoc.org/mailman/listinfo/internet-history__;!!KwNVnqRv!VGbu8UR1ds9tLcdTmqj_BlSaJwdAR7VMX3YliVLEE7V0gQyXuH0Pp6mWiH895w$
> >>>
> >>>
> >>> --
> >>> Internet-history mailing list
> >>> Internet-history at elists.isoc.org
> <mailto:Internet-history at elists.isoc.org>
> >>>
> https://urldefense.com/v3/__https://elists.isoc.org/mailman/listinfo/internet-history__;!!KwNVnqRv!VGbu8UR1ds9tLcdTmqj_BlSaJwdAR7VMX3YliVLEE7V0gQyXuH0Pp6mWiH895w$
> >>
> >> --
> >> Internet-history mailing list
> >> Internet-history at elists.isoc.org
> <mailto:Internet-history at elists.isoc.org>
> >>
> https://urldefense.com/v3/__https://elists.isoc.org/mailman/listinfo/internet-history__;!!KwNVnqRv!VGbu8UR1ds9tLcdTmqj_BlSaJwdAR7VMX3YliVLEE7V0gQyXuH0Pp6mWiH895w$
> >>
> >
> >
> --
> Internet-history mailing list
> Internet-history at elists.isoc.org
> <mailto:Internet-history at elists.isoc.org>
> https://elists.isoc.org/mailman/listinfo/internet-history
> <https://urldefense.com/v3/__https://elists.isoc.org/mailman/listinfo/internet-history__;!!KwNVnqRv!Rx8iR-iY9K1HbQVsgTrj6P0msEWI6yHEd-7xJLDubJxXOWVufwpWosUm6b_40A$>
>
>
>
> --
> Geoff.Goodfellow at iconia.com <mailto:Geoff.Goodfellow at iconia.com>
> living as The Truth is True
>
>
>
More information about the Internet-history
mailing list