[ih] Exterior Gateway Protocol

[Noel Chiappa]

    > From: 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?

Yes, SPF is the design he came up with to replace the original 'old' ARPANET
routing architecture (which was a DV system). In the descriptive system I laid
out, it is exactly an SPF system (everyone runs the identical algorithm over a
map, and only computes the next hop from them).

A term often/usually used as a synonym for SPF is 'Link State'; the New
ARPANET SPF, OSPF, and IS-IS are all LS protocols.

His PhD thesis, done at the time (or perhaps slightly before) explores the
entire field of routing. Anyone who's really interested in routing should get
a copy; mine came from NTIS, but I imagine University Microfilms International
would also be a source.


Oh, one note: in the ARPANET, 'routing' (both old and new systems) was not
_just_ path selection, but also 'congestion avoidance'; i.e. it tried to
divert traffic around congested areas. This made the 'routing' problem much
harder (in terms of getting paths to stabilize); the constant changes in
delays with load were equivalent to constant connectivity changes in a network
like today's.

IIRC, one problem they saw was 'load chasing' oscillations: a part of the
network is loaded, so everyone starts avoiding it, and heads for an unloaded
part. Repeat! :-) IIRC they sorta 'cured' that with damping.

I think in a really large network, doing congestion avoidance in one
subsystem, long with path selection, is not workable. I think it should be
done separately (easy to pull them apart with an ER/MD system, _another_ advantage
of that architectural approach).

   Noel