Figure
1: A source routing LAN segment.
date 02/26/95
2. Bridge Routing Requirements
4. Transparent Spaning Tree Bridges
Both the physical distance that Local Area Networks (LAN) can cover and the number of hosts that can be attached to it are limited. To overcome this limitation, bridges are introduced as devices which connect LANs at the MAC layer. The purpose of bridges is to allow hosts attached to different LANs to communicate as if they were located on the same LAN. In contrast to repeaters, that act at the physical layer and allow all traffic to cross LAN segments, bridges are more intelligent and limit the traffic to the section of the network on which it is relevant. To accomplish this, bridges must make a forwarding decision with each received frame regarding where to send the frame so that it reaches its destination. There are two different bridge standards: Source-Routing (SR), which is common in 802.5 (Token Ring) environment, and Transparent Spanning Tree (TST), which is common in 802.3/Ethernet environment. The IEEE standard for MAC bridges is ANSI/IEEE 802.1D: MAC Sublayer Interconnection.
In general, LANs are low-cost, low-delay, high-bandwidth (e.g., 1 - 10 Mbps) broadcast channels. A bridged LAN environment preserves the low-delay and high-bandwidth features but its topology may be more dynamic than in a single LAN due to possible bridge or LAN failures and hosts being moved around.
Bridge routing algorithms should meet the following requirements:
Source-Routing is mostly used to interconnect token ring LANs. In Source-Routing, the source station must determine, in advance, the route to the LAN of the destination station, and include this route in the header of each frame. To determine the routing information, the source station first issues a search frame, which is generally an LLC TEST command, on its ring. If a response is received from the desired destination station, it indicates that both source and destination stations are on the same ring and that no routing information is required. However, if no response is received, the source station issues a route discovery frame, which fans-out on every ring in the LAN segment. As the frame is forwarded from one ring to another, each bridge updates the routing information in the search frame. When the search frame reaches the destination, it contains the route between the source and destination stations. The destination station then sends a response frame to the source station, with the routing information. Both stations then use the routing information in each subsequent frame sent to each other.
Source-Routing uses two key parameters to identify a route between a source station and a destination station. These parameters are ring numbers and bridge numbers. Each ring is assigned a unique number. These numbers generally range between 1 and FFF (hex). Each bridge is assigned a bridge number, ranging between 0 and F (hex). The only restriction when assigning bridge numbers is that parallel bridges, connecting identical rings, must have different bridge numbers. The route between the source and the destination stations consists of LAN numbers and bridge numbers. The route is obtained by that each bridge which receives the route discovery frame adds to the existing route, its number and the ring number that it forwards this frame to.
An example may be helpful in illustrating how a route discovery frame is used to obtain the route between the source and destination stations and how this route is used by the source routing bridges to route frames. Consider figure 1 in which the Source station wants to send a frame to the Destination station.
Figure
1: A source routing LAN segment.
Note: In the next paragraph we use underscore to denote subscript.
First the source issues a route discovery frame that is broadcasted to all the rings in the segment. The routing information field is initialized to {ring_1}. Bridge B_1 which receives the frame forwards it to all the rings that it is connected to unless they are already in the route. The latter is in order to avoid a circular route. Thus B_1 forwards the frame on ring_2 with the route {ring_1, B_1, ring_2}. B_3 forwards the frame on ring_3 with the route {ring_1, B_1, ring_2, B_3, ring_3} and B_2 forwards the frame on ring_3 with the route {ring_1, B_1, ring_2, B_2, ring_3} and on ring_4 with the route {ring_1, B_1, ring_2, B_2, ring_4}. A loop in the route does not occur because B_3 and B_2 will not forward the frame back to ring_2 since it is already in the route. The destination station receives, in this case, two frames with two different routes: {ring_1, B_1, ring_2, B_2, ring_3} and {ring_1, B_1, ring_2, B_3, ring_3}. The destination uses one of these routes in a reverse order to send its response to the source station. Suppose the the route {ring_3, B_3, ring_2, B_1, ring_1} is used. The destination sends a response frame with this route on ring_3. B_3 examines the routing information field and realizes that it has to forward this frame on ring_2. Similarly B_2 forwards this frame on ring_1 and it reaches the source station.
In Transparent Spanning Tree, the TST-bridges create a spanning tree. Routing information is not needed to be determined by the source station, and all the routing is done by the bridges. Therefor, stations from different LANs connected with TST-bridges, can communicate as though both stations are on the same LAN. By maintaining a tree structure routing becomes very simple and frame circling in the network is avoided. Transparent bridges require that bridges dynamically maintain a station address database, referred to as a forwarding database. Each entry in the database has a station address, age, and port identifier. The age is used to remove stations after a specified period of inactivity. The port identifier is used to identify the bridge port on which the bridge should forward frames destined to the station. The forwarding database is built by observing frames that pass through the bridge, and learning from them the station's location. Thus a TST-bridge has two functions: learning and forwarding.
The flowchart in figure 2 summarizes the forwarding and learning process for a frame received on a bridge port.
Figure
2:Bridge Forwarding And Learning.
When a frame is received on a bridge port, the destination address contained in the frame header is compared to the information contained in the forwarding database. If the destination address is not found in the forwarding database, the frame is transmitted on all bridge ports, except the one on which it was received. If the destination address is found in the forwarding database, and the port identifier kept along with this address is the same as the identifier of the bridge port on which that frame was received; the frame is not forwarded to any bridge port. If the port identifiers are different, the frame is forwarded on the bridge port identified in the forwarding database.
Figure 3 shows a simple topology of bridges and end stations. In this configuration frames from station A to station B are discarded by Bridge 1. Frames from station A to station C are forwarded by Bridge 1 and discarded by Bridge 2. Frames between any stations on LAN 1 and LAN 3 are forwarded by both bridge 1 and bridge 2.
Figure
3: TST LAN Segment.
The source address of all frames received is compared against the information in the forwarding database. If the source address is not found in the forwarding database, it is added along with the port identifier it received on. The age value of this database entry is reset to indicate that this is a "fresh" entry. If the source address already exists in the forwarding database, and the database indicates that the station was last seen on a different bridge port, then the port identifier for the entry is changed to the port identifier on which the frame was received, and the age value of this entry is reset. If the frame is received on the same port as the port in the database entry, then only the age value of this entry is reset.