[ih] Exterior Gateway Protocol

[Noel Chiappa]

    > 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