Retro networking / WAN communities

[Paul Koning]

> On Apr 12, 2022, at 12:45 PM, Grant Taylor via cctalk <cctalk at classiccmp.org> wrote:
> 
> On 4/12/22 7:49 AM, Paul Koning via cctalk wrote:
>> ...
>> The concept of a repeater goes back to day 1 of Ethernet; you'll find them in the D/I/X Ethernet spec.  And they were part of the first batch of Ethernet products from DEC.
> 
> Repeaters existing from day 1 of Ethernet sort of surprises me.
> 
> I wonder if there is some difference in the original 3 Mbps Ethernet at Xerox PARC vs the 10 Mbps Ethernet (II?) that was commercialized.

I don't know anything about the 3 Mb/s prototype other than that it existed.  When I speak of Ethernet and its "day 1" I mean 10 Mb/s Ethernet as defined by the DEC/Intel/Xerox spec.  

Repeaters are a core part of that spec, and they were among the first wave of products delivered by DEC.

> ...
>> I first saw "structured wiring" -- the star wiring with a hierarchy of wiring closets and devices -- around 1986, in the new Littleton King Street DEC building.  It had distribution cabinets at the end of each row of cubicles.  These looked just like standard office supplies storage cabinets, with shelves; inside you'd find a bridge and a couple of DEMPR repeaters, connected to 10Base2 coax drops to each cubicle.
> 
> Interesting use case.  --  Now I'm wondering if each station run was standard 10Base2 with it's T connector and terminator.

I no longer remember.  That's possible, or perhaps they were a number of small segments each with a handful of stations on them.

>> ...
> 
> I now feel the need to call out what I think are two very distinct things that need to be differentiated:
> 
> 1)  Learning of which port a source MAC address is on for the purposes of not sending a frame out to a destination segment when the location of the destination is known.
> 2)  Spanning Tree / 802.1D learning the path to the root of the tree.
> 
> The former is a fairly easy algorithm that doesn't require anything other than passive listening for data collection.  The latter requires introduction of a new type of active traffic, namely BPDUs.

That's true but only part of the story.  For one thing, as I said, both mechanisms were part of bridges from the start (at least from the start of DEC's bridges, which may not be quite the very earliest ever but certainly are the earliest significant ones).

The learning part of bridging is actually the hard part.  It involves (a) extracting the SA of each received address, (b) looking it up, in very short time, in a large address table (8k entries in the original DECbridge-100), (c) timing out each one of those addresses.  And then also (d) looking up the DA of a received packet in that table and (e) if found, forwarding the packet only to the port for that address, or dropping it if output port == input port.  (a) is easy, (b) through (d) are not. And (d)/(e) are the purpose of the exercise, it is why bridged networks have better scaling properties than repeater based networks.  

If you consider a two port 10 Mb Ethernet bridge, steps (b) and (d) amount to two table lookups every 30 microseconds (minimum packet interval across two ports), and step (b) includes restarting the aging timer for that address.  With early 1980s technology this is a seriously hard problem; as I recall, in the DECbridge-100 it involved a hardware assist device to do the table lookup.  And (c) is not easy either, it required the invention of the "timer wheel" algorithm which has the properties that starting, stopping, and keeping N timers is O(1) i.e., independent of N.  (Expirationn of n timers is O(n), but most timers do not expire in this application.)

Later on it became possible, with great care, to do these things in software.  The DECbridge-900 (FDDI to 6 x 10M Ethernet) has its fast path in a 25 MHz 68040, very carefully handcrafted assembly code, with a bit of help from a 64-entry CAM acting as address cache.  It can handle around 60 k packets/second, which means it needs some additional specialized rules to ensure it won't miss BPDUs under overload since it can't do worst case packet arrival at all ports concurrently in the normal forwarding path.  We patented that.

Spanning tree is indeed another algorithm / protocol, but it's a control plane algorithm with relatively easy time constraints, so it's just SMOP.

>> ...
>> Does anyone still remember the other 100 Mb Ethernet-like proposal, I think from HP, which added various types of complexity instead of simply being a faster Ethernet?  I forgot what it was called, or what other things it added.  Something about isochronous mode, perhaps? Or maybe I'm confused with FDDI 2 -- another concept that never got anywhere, being much more complicated even than regular FDDI.
> 
> I vaguely remember there being multiple 100 Mbps Ethernet specifications.  I think one of them had "Any" in it's name.

That rings a bell.  Someone reminded me of 100Base-T4.  In any case, there were two proposed, one that made it.  The other might have gone as far as one or two shipping products, but no further than that.

	paul