Norm Al Dude and Professor N. Erd
on the subject of Transparent Bridges

Believe it or not, Nicky Erd has a human side, bless his soul. Occasionally, even poetry pops out from under his engineering strata, just like soda from a can under pressure. This morning I caught him staring at the endless sky and mumbling softly to himself:

"We are like two little Ethernet packets passing fleetingly from port to port, compressed but cute, stopping for a moment on a bridge, under the shadow of the spanning tree! A mere unexpired timeout seems like an eternity - then you are gone - and only emptiness remains in transmit buffers! Oh, Love!"

I think the guy went nuts. As I coughed to let him know I'm there, he jumped up startled, his face beet-red, and said:

"Ah, er, uh ... Al - I should lecture about bridges today - because today's routers all bridge protocols that can't be routed - everyone uses bridges, but they don't know what is the difference between bridging and routing!"

I said "Nicky, if you feel like it, do it to me - I will translate it for the simple-minded of the world. And, by the way, who's the lucky gal?"

"What girl?"

"Oh, come on -- under the shadow of the spanning tree, etc., etc.?"

"Oh, that! Er, she has a Ph.D. in Survival Skills Science from the Under Ground University of New York City. Let's talk about bridging."

I didn't want to press the issue, so I let him lecture me. Here's the story the way I see it.

A LAN is what N. Erd calls a 'statistically used network'. All stations (PCs, servers, printers, etc.) hang off a common cable and try to send messages (called frames) to each other just like people in the same room would try to talk in pairs. For this to be possible, only one could talk at a time -- otherwise it would be like someone and his/her mother-in-law in a shouting match.

Figure 1: Statistical LAN Performance

For example, an Ethernet has all stations connected in parallel to this cable that N. Erd keeps calling a 'bus'. I know it can't be, because I've seen busses, and they're not made of wire! Stations on an Ethernet are talking to each other using a bunch of rules (called media access control or MAC protocol) that some crazy named CSMA/CD (ugh!).

CS stands for carrier sense, and it means that the stations are listening politely and make sure the cable is silent before they transmit. Not like some of us people! If it's quiet, then all those stations that have something to transmit jump on the cable and send, just like the people in the room would start talking. That's 'MA', or multiple access. If more than one talks, It's like the mother and daughter-in-law arguing, and they call that a 'collision'. Stations are listening to hear if a collision occurs, and whoever detects this first is so happy that it starts screaming: 'collision detected, collision detected!". They call that 'CD' or, as you might have guessed, 'collision detection'. The two in-laws would continue to argue, but Ethernet stations are better behaved, and they stop transmitting and try again later.

With token passing, there is a device in the room (on the cable) that controls who can talk -- sort of a talking stick. N. Erd calls it a 'token', and unless a station has the stick, it can't transmit anything.

In token ring, for example, each station passes the token to its downstream neighbor, who passes it to the next one, and so on, until one of them, say station D, has something to say to another one, say G. Then what happens is D attaches the message to the token and sends it from station to station, downstream. When the message reaches G, G reads it and sends a return receipt back to D, using the cable in the same downstream direction as before. That's because the ring is round, just like the earth. D gets the receipt and then releases the token for somebody else to use it.

Well, guess what: If too many stations try to send at the same time on an Ethernet cable, the number of collisions goes through the roof, and just like one can't hear too much in a crowded bar, neither can a workstation hear or transmit too well on a crowded Ethernet. That's when the users get mad because their sessions start timing out. A busy token ring behaves the same way, because users start to wait longer and longer for their talking sticks -- their sessions will time out, too.

N. Erd says that "a 10 Mbps Ethernet collapses around 3 Mbps (megabits per second) attempted traffic." When I said "Huh? - what's that?" he mumbled something that I understood to be "Attempted traffic is made of all the bits that are queued in all the network interface buffers, trying to get out on the LAN cable within one second." Go figure.

Same thing happens with token ring: at 3 Mbps attempted traffic, boom! - the network blows up for 4 Mbps rings. Or, if the LAN operates at 16 Mbps, the same boom! happens at 12 Mbps attempted traffic.

In practical terms that could mean 30 PCs with moderate graphics, or 10 Macintosh PCs with laser printers, or 4-6 CAD-CAM workstations, or even 2 heavy-duty computers. Wow!

So, what's to do when all these and more stations need to talk over a network? That's when a bridge can really help.

Figure 2: Why Bridging

Let's say we take this Ethernet and split it into what N. Erd calls 'segments'. A segment is like one of many rooms with sound-proof doors between them. A guy at each door sits with a list of all stations on each segment. Stations have their own MAC (media access control) addresses, just like guys and gals would have names. Say station MACA wants to send a message to station MACB just like George would send a message to Michael. If they are both in the same room (segment), the doors remain closed; if at the same time Mary wants to send a message to Jenny and both of them are in the next room, they can talk all they want, because the door is closed and their conversation won't collide with George and Michael.

Later on, if George wants to invite Mary to dinner, he has to pass the invitation to the dude that guards the door. In turn, this fellow opens the door and passes (forwards) the invitation to Mary on the next segment. That's what a transparent bridge does. Just like the dude that guards the door, it 'learns' which station is on which segment or port, and 'filters' all data frames whose source and destination MAC addresses are both on the same segment; or, when it figures the source is on one segment and the destination is on another, forwards those frames from a segment to this other one.

This Mac fellow is a smart one! This bridge is called 'transparent' because it does all the work. George invites Mary to dinner as though they were in the same room!

Figure 3: Transparent Bridging

Folks, there is a committee of guys like N. Erd that started to meet and have fun in February of 1980. They call themselves the 802 committee of the IEEE. They wrote how the dude at the door has to behave in a standard called 802.1d -- transparent bridging. Here's what I understood:

Let's say there is this network made of 3 segments: West, South and East. There is a bridge-dude guarding doors between West and East and between West and South. There is no direct path between South and East.

On the West segment sits a station with the MAC address XX (Wanda), on the East segment sits VV (Ellen), and on the South segment sits AA (Stan). There are other folks on the segments, but we'll focus on these three. This time we'll let the bridge-dudes automatically learn who's on what segment. They are blindfolded and can learn only through listening, and only through association of the source MAC addresses with the segments (ports) over which the stations speak. Unless Wanda says something to anyone, nobody will know where she is, poor little one!

Figure 4: Learning

So, let's say Wanda (XX) sends a message to Stan (AA). Right away the West bridge-dude writes on his list: I heard Wanda on the West port, so Wanda is in the West segment. But since the dude does not know where Stan might be, he has a bit of a problem: how to send the message to Stan? He opens both doors - to South and East - and sends Wanda's message in both directions. This way for sure Stan will hear the message, if he's not deaf. This is what N. Erd and others like him call 'flooding'.

Now, the bridge-dude on the East segment hears the message and writes: I heard Wanda's message on my West port, which means from now on, whenever I hear someone sending to Wanda, I'll transmit the message over that port. In the same way the South bridge-dude writes: I'll deliver any message addressed to Wanda over my West port, because that's where I heard her.

Later on, when Stan bothers to answer Wanda, the South dude scribbles Stan's name on his 'local' South segment and sends the message as promised via the bridge's West port. The West dude writes Stan on his South port and from now on will deliver any packet to Stan over this port. Then he locates Wanda's name on his list on the West segment and gives her the message. In this way, eventually, all dudes will learn about everybody's location.

If there are too many stations to learn and locate on the lists, the dudes work so hard they hate it! So, what they do is they erase those names that are not heard in a while. N. Erd says that's 'address aging'. Then, if out of the blue a packet goes to someone whose name is no longer on the list, the bridge-dude has to flood the network again with that packet. That's why there is an 'adjustable aging timer' that keeps the bridge-dudes from erasing names from lists too quickly.

Since the bridge is transparent and the sun would shine too brightly through it, the 802 folks said that there is a need for a 'spanning tree' to throw some shadow around the network.

Just kidding! Really, there is a spanning tree, but here's why and how it works:

Let's say that we add a link between the South and East segments in the previous setup. This is what N. Erd calls a LAN loop.

Figure 5: Bridging Loop

Learning happens just as I told you, except now the South bridge-dude floods the message from Wanda to Stan on both his local side (the South port) and his remote side (East port). So the East dude writes Wanda's name as heard on this port too, not only on the South port like before. Wanda hasn't been heard on the East LAN, so the East bridge-dude forwards the message to the South network, continuing the flooding process. So the South dude hears Wanda's message from both his West port AND his East port -- what a mess!!! From now on, any one sending Wanda a message will make the bridge-dudes go crazy screaming the message on all their ports. The network is hit by what some call a 'broadcast storm' because when all bridge-dudes learn about all stations on all ports, nothing is working anymore. That's why the 802 folks drank their coffees and said that it's illegal to have a loop!

"The problem is, however, that loops are desirable because they offer redundancy." said N. Erd. (In other words, if, in the first example, the door between the South and West segments jams, the bridge-dude of the South segment can't relay any messages to or from poor Stan who may die with boredom!)

So, the elders in the committee allowed us poor folks to have our loops on the condition that one of the links will not be used to "transmit user messages". That link will remain in a "standby blocked condition" ready to be used only if another link fails. It's like keeping one of the doors shut but being ready to open it if another one jams.

Figure 6: Spanning Tree

To accomplish this, the bridge-dudes elect one of them as their boss -- it's called the 'root bridge'. Then they report what ports they are guarding to the boss. These ports have 'logical numbers and costs' assigned to them by a network manager. The root calculates path costs and sends commands to the other bridges to block some links and keep those with the smallest costs in use (active). When one looks at the resulting network now, one sees a network between LANs made of a tree of active paths (branches), with the root at the boss-dude and the LANs as leaves. That's what the 802 elders called 'the spanning tree'. Pretty slick, no?

Of course, the bridge-dudes, once in a while (every 2 seconds or so), test all the blocked doors to see if they're in good condition if needed. They do this by exchanging "hey dude" and "I heard you, dude" messages with each other. N. Erd calls these messages 'short BPDUs' (bridge protocol data units).

I am curious if anyone tried to make root beer out of the spanning tree.

For token ring, the Blue guys at IBM did something called source route bridging. About that and some other exciting things such as traffic analysis some other time. I've had enough for one day with N. Erd. And if I know you, you're sick of it too!

You're welcome to peruse a list of publications that offer more information on bridges and related topics.

So long,
Norm Al

P.S. Nicky told me her name: Digit! - figures!!!
- NA