Top Universities: Local Internetworking

The previous section dealt with the problems encountered in connecting two different IEEE 802
LANs via a single bridge. However, in large organizations with many LANs, just interconnecting
them all raises a variety of issues, even if they are all just Ethernet. Ideally, it should be
possible to go out and buy bridges designed to the IEEE standard,
plug the connectors into the
bridges, and everything should work perfectly, instantly. There should be no hardware changes
required, no software changes required, no setting of address switches, no downloading of
routing tables or parameters, nothing. Just plug in the cables and walk away. Furthermore, the
operation of the existing LANs should not be affected by the bridges at all. In other words, the
bridges should be completely transparent (invisible to all the hardware and software).
Surprisingly enough, this is actually possible. Let us now take a look at how this magic is
accomplished.

In its simplest form, a transparent bridge operates in promiscuous mode, accepting every
frame transmitted on all the LANs to which it is attached. As an example, consider the
configuration of Fig. 4-42. Bridge B1 is connected to LANs 1 and 2, and bridge B2 is connected to LANs 2, 3, and 4. A frame arriving at bridge B1 on LAN 1 destined for A can be discarded
immediately, because it is already on the correct LAN, but a frame arriving on LAN 1 for C or F must be forwarded.

When a frame arrives, a bridge must decide whether to discard or forward it, and if the latter, on which LAN to put the frame. This decision is made by looking up the destination address in a big (hash) table inside the bridge. The table can list each possible destination and tell which output line (LAN) it belongs on. For example, B2's table would list A as belonging to LAN 2, since all B2 has to know is which LAN to put frames for A on. That, in fact, more forwarding happens later is not of interest to it.

When the bridges are first plugged in, all the hash tables are empty. None of the bridges know
where any of the destinations are, so they use a flooding algorithm: every incoming frame for
an unknown destination is output on all the LANs to which the bridge is connected except the
one it arrived on. As time goes on, the bridges learn where destinations are, as described
below. Once a destination is known, frames destined for it are put on only the proper LAN and
are not flooded.

The algorithm used by the transparent bridges is backward learning.As mentioned above, the bridges operate in promiscuous mode, so they see every frame sent on any of their LANs. By looking at the source address, they can tell which machine is accessible on which LAN. For example, if bridge B1 in Fig. 4-42 sees a frame on LAN 2 coming from C, it knows that C must be reachable via LAN 2, so it makes an entry in its hash table noting that frames going to C should use LAN 2. Any subsequent frame addressed to C coming in on LAN 1 will be forwarded, but a frame for C coming in on LAN 2 will be discarded.

The topology can change as machines and bridges are powered up and down and moved
around. To handle dynamic topologies, whenever a hash table entry is made, the arrival time of the frame is noted in the entry. Whenever a frame whose source is already in the table arrives, its entry is updated with the current time. Thus, the time associated with every entry tells the last time a frame from that machine was seen.

Periodically, a process in the bridge scans the hash table and purges all entries more than a
few minutes old. In this way, if a computer is unplugged from its LAN, moved around the
building, and plugged in again somewhere else, within a few minutes it will be back in normal
operation, without any manual intervention. This algorithm also means that if a machine is
quiet for a few minutes, any traffic sent to it will have to be flooded until it next sends a frame
itself.

The routing procedure for an incoming frame depends on the LAN it arrives on (the source LAN) and the LAN its destination is on (the destination LAN), as follows:

1. If destination and source LANs are the same, discard the frame.
2. If the destination and source LANs are different, forward the frame.
3. If the destination LAN is unknown, use flooding.

As each frame arrives, this algorithm must be applied. Special-purpose VLSI chips do the lookup and update the table entry, all in a few microseconds.