[ih] Exterior Gateway Protocol

[Brian E Carpenter]

On 04-Sep-20 10:20, Vint Cerf via Internet-history wrote:
> 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

Interesting paper. It cites this paper as its immediate source:
D. B. Johnson. "Efficient algorithms for shortest paths in sparse networks",
J. Ass. Comput. Mach. vol. 24. pp. 1-13. Jan. 1977.
DOI: 10.1145/321992.321993

which of course cites both Dijkstra and Bellman & Ford as original sources.

   Brian

> 
> 
> 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
>>
> 
> 
>