[ih] Intel 4004 vs the IMP

[Craig Partridge]

On Mon, Nov 15, 2021 at 11:19 AM Dave Crocker via Internet-history <
internet-history at elists.isoc.org> wrote:

>
>
> I think your initial question could nicely translate into a similar
> exercise, with the constraint that the 'computing' part is required to
> be roughly the same.
>
> Your alternative exercise, is separately worth doing, since there were
> entirely adequate microprocessor-based routers by the latter 1980s.
> That one might need to distinguish between 'enterprise' routers vs.
> 'backbone' routers is worth keeping in mind, though.
>
>
Hidden in here is the fact that the algorithms in routers evolved over time.

But for the route lookup, the IP part of forwarding is really simple and
has a high degree of concurrency (e.g. you can do all the checks for format
validity in parallel and then check if any of them failed at one point).
That wasn't terribly useful when processors did single instructions, but by
the early 1990s, some could do two instructions or more per clock tick, it
was a win.  As a result, by the early 1990s, most of the instructions
executed to forward an IP packet were actually in the device driver (and
the layer 2 stuff the driver didn't do that you had to do in software).

Route lookup was also an area of tremendous innovation.  Key was splitting
the forwarding table/FIB from the master routing table.  It both allowed
efficient update of the forwarding table and made it possible to structure
the forwarding table for lookup, without worrying about how it was
structured for updating (whereas the master routing table needed to
efficiently update).  The result was route lookups became an O(log n) or
better operation.

Craig

Craig Partridge's email account for professional society activities and
mailing lists.