[ih] Exterior Gateway Protocol

[Vint Cerf]

I seem to recall that we ran into a number of problem with the ARPANET
routing algorithms and John McQuillan was tasked to deal with them. Didn't
he come up with SPF as a solution?

<goog_1805810333>
https://www.cs.yale.edu/homes/lans/readings/routing/mcquillan-darpa_routing-1980.pdf


v


On Thu, Sep 3, 2020 at 6:14 PM Noel Chiappa via Internet-history <
internet-history at elists.isoc.org> wrote:

>     > From: Guy Almes
>
>     > 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.
>     > ...
>     > Comments?
>
> Tony already said something about this, but a few more notes.
>
>
> First, SPF is not the best term to use. To me, the fundamental division in
> routing architectures is between what I call 'Map Distribution' designs
> (named
> after the fundamental data passed around in them - map elements), and
> 'Destination Vector' (which pass around routing tables - arrays of
> destinations).
>
> SPF applies to a subset of MD, ones in which every node runs the same
> path-selection algorithm, in parallel, and each only makes a decision on
> the
> next hop from it (to any particular destination). (The algorithm outputs,
> from
> a given map input, have to be identical, as well as the maps, otherwise
> routing loops can result. So in theory one could have different algorithms,
> but in practise the algorithm is part of the protocol spec.)
>
> An orthogonal subset of MD uses what we called Explicit Routing' (a name
> due
> to Yakov Rekhter, with thanks), where _individual_ nodes (perhaps
> recursively)
> select the entire path (or sections thereof, in the recursive case). This
> has
> several advatanges; in addition to being less fragile, and far less
> suscpetible to loops, it _allows_ (but does _not_ mandate) individal nodes
> to make their own decisions about paths - aka policy routing.
>
> With that in hand, a couple of 'SPF' (actualy, mostly all MD) EGP designs.
>
>
> I started an early effort for an SPF (I think; I'd have to look)
> replacement
> for EGP, called 'FGP', just after John Moy joined Proteon; my concept was
> he
> could do the detailed design. Alas, John wasn't sure he had the technical
> chops for it (to which I just rolled my eyes, he clearly could handle it),
> but
> unfortunately Dave Clark (then a director at Proteon) also agreed that it
> wasn't a good move. Instead, Proteon started what turned into OSPF;
> originally
> a Proteon thing, we rapidly turned it over to the IETF. I have this vague
> memory that Scott Brim may have been at an FGP kick-off meeting - or is my
> memory playing false?
>
> Then there was the IDPR design, which was an MD EGP capable of supporting
> policy routing. It was the output of a long-running IETF WG, whose name now
> escapes me, which had been charged with coming up for a replacment for
> EGP. (This was before BGP - which initally was supposed to be a quick hack
> 'interim' EGP replacemt, when IDPR was late.)  I recall we wrote a draft
> requirements document, which a late joiner took over to 'edit', and he he
> entirely re-wrote it - the original version was left in as an appendix.
> Martha
> Steenstrup later came up with an actual design.
>
> Around then, I'd split off to work on Nimrod (the name is neither an
> acronym
> nor a backronym, but a private joke between me and John Lekashman, from
> whom I
> had hoped to get funding). The primary difference between IDPR and Nimrod
> was
> that I wanted to get rid of the EGP/IGP split - to me it was a blunt tool
> of
> limited capabilities. My idea was that Nimrod regions (which could nest)
> would
> have similar 'firewalls' to protect them, not just the single blunt IGP/EGP
> split. But the real reason was that I saw a unified routing architecture,
> from
> top to bottom, as more flexible and powerful. (And it would have been; some
> years later I remember discussing an optical network which could handle
> qbit
> traffic; Nimrod, off the shelf, could have handled the routing for it.)
>
> There was also IDRP (the name, I am convinced, was deliberately chosen to
> be
> confusing), from Yakov and someone else (Deborah Estrin?), which was a
> mashup
> of IDPR (to handle policy-routed traffic) and a BGP-ish DV system (to
> handle
> ordinary traffic).
>
> The ATM people used Nimrod ideas as the basis for the initial versions of
> PNNI, which was intended to be the routing system for a large, multi-vendor
> ATM network. (I gather the name was later applied to a simplified protocol,
> based on OSPF.)
>
>
>     > once a pretty good system, especially with BGP in the generic
>     > EGP/inter-AS context, evolves, it's hard to make big changes.
>
> As Tony mentioned, you can do it. We'd put a fair amont of work into
> thinking
> about the deployment path for Nimrod, you haqd to have an interoperation
> phase,
> duing which the part running the 'new' design would grow in size - very
> vaguely
> similar to how BGP was first deployed.
>
> Nimrd's flexibility and power was intended to make such a transition
> in the future unnecessaet (forever). Whether it could have net the business
> goalsTony alluded to - maybe (via the vietualization and information hiding
> mechanisms).
>
>         Noel
> --
> Internet-history mailing list
> Internet-history at elists.isoc.org
> https://elists.isoc.org/mailman/listinfo/internet-history
>


-- 
Please send any postal/overnight deliveries to:
Vint Cerf
1435 Woodhurst Blvd
McLean, VA 22102
703-448-0965

until further notice