12.2 Basics

   


As was mentioned above, a bridge is a coupling element that links several local area networks on the data link layer [BaHK94]. For this purpose, a bridge has two or more network adapters (ports), which are used to connect to a local area network. In contrast to a repeater, which can merely extend the distance of a LAN, and which simply forwards packets as it received them, a bridge can evaluate certain information in a packet and decide whether that packet should be forwarded.

Bridges come in different variants and with various properties, which will be briefly introduced below:

  • Local or remote bridges: Local bridges connect two or more neighboring local area networks see Figure 12-1. These local area networks are normally linked on the MAC layer.

    Remote bridges connect two local area networks physically separated by another network, normally a Wide Area Network (WAN). This bridge type interconnects local area networks on the LLC layer. [BaHK94] includes a detailed description of local and remote bridges. This chapter considers only local bridges.

  • Translation or nontranslation bridges: A translation bridge is capable of connecting several local area networks over different media-access protocols (e.g., Ethernet and token ring). Linux is limited in supporting this property, because there could be problems during the transition from one standard to another one. For example, 802.3 supports a limited maximum frame size of 1,500 bytes, but 802.5 supports a much bigger size. For this reason, we cannot feed large 802.5 packets into an 802.3 network.

  • Source-routing or transparent bridges: Source-routing bridges represent an extension of the token-ring standard and must be used in token-ring networks only. We will not consider them any further.

    In contrast, transparent bridges can be used in all 802.x networks. They mainly handle the transparent interconnection of different 802.x LANs, where the participating stations do not know that there is a bridge in the LAN. In other words, the bridge is not visible to the stations in the interconnected LANs it is transparent. The bridge functionality under Linux corresponds exactly to the type of a transparent bridge.

Figure 12-1. A Linux computer acts as a transparent bridge, connecting several local area networks.

graphics/12fig01.gif


12.2.1 Properties of Transparent Bridges

bridges: In accord with the definition in Section 12.2, a Linux system can be used to implement a local transparent translation[1] bridge, which can interconnect different 802.x LANs. Figure 12-1 shows an example in which the Linux computer acts as a bridge, connecting three LANs of different types: one Ethernet (IEEE 802.3), one Fast Ethernet (IEEE 802.3u), and one wireless LAN (IEEE 802.11).

[1] ... however, with the limitation that the 802.x networks be compatible, mainly with regard to their maximum frame lengths. For example, 802.3 and 802.11 can easily be combined, but problems could arise when you use 802.5 LANs.

When we use a translation bridge to link different 802.x LANs, then the properties of the different sets of protocols have to be adapted. For example, the bridge should consider the different access methods of the interconnected LANs; it should also consider and convert different packet formats. In addition, we have to consider that properties could be lost during the transition from one LAN type to another type. Examples include priorities or acknowledgments in 802.5 networks, which are lost in 802.3 networks, because the latter don't have anything comparable. Linux currently supports only the interconnection of local area networks that use an Ethernet-compatible frame format on MAC level.

The transparent bridge in Figure 12-1 is responsible for switching data packets between the three networks used in this example to allow the stations in these three networks to communicate. Data packets (which are also called frames on layer 2) with their destination within one local area network are not transported to the other two LANs internetwork and intranetwork traffic is separate.

The bridge need forward only those data packets intended for another LAN. This translates into a considerable reduction of the network load, because internal traffic loads remain within the LANs and parallel communication is possible internally in each of these LANs. If a computer in one LAN wants to send data to another LAN, then only those LANs required for the transport are used. In addition, the bridge ensures that faulty data packets are filtered and prevented from being transported to the other networks. The filtering concept supported by bridges will be described in Section 12.2.2.

Transparent bridges are characterized mainly by the fact that they are hidden from the stations in the network. In addition, they forward frames from one LAN into another LAN independently. To both the inside and the outside, it seems like there is one large local IEEE-802-compatible network. The bridge does not consider protocols used on the network layer; you can select arbitrary protocols.

To achieve transparency, each bridge maintains a table (forwarding database) that stores the output line used to reach a station for each layer-2 address. We will see in Section 12.4.2 how this forwarding table is implemented in Linux.

The properties of a Linux bridge introduced above will be discussed in more detail in the next sections.

12.2.2 Forwarding Function

The main task of a bridge is its filter function to separate the traffic between local area networks from the traffic within one local area network. For this function, the bridge is not addressed explicitly; it is transparent for the communication partners. None of the computers in the local area networks knows that the bridge is present. For this reason, the bridge receives each data packet as it passes each network adapter, interprets its destination address, and uses the filter criterion to decide whether the packet should be forwarded to another LAN or not be handled. In the latter case, the addressed station is in the LAN that received the data packet. The bridge can assume that the destination station has already received the packet, so that it does not have to forward it.

As mentioned earlier, a transparent bridge uses a forwarding table which stores forwarding information. It also uses positive filters, which are entered as a result of the learning function. (See Section 12.2.3.) The forwarding table provides general information how each computer can be reached over the outputs. If only one LAN is connected to each bridge adapter, then the decision about the LAN on which a computer resides is obvious. If this is not the case, then the LAN and an output adapter are specified to reach the LAN of a computer (the so-called next hop).

The example in Figure 12-2 shows how the forwarding function of a bridge works. Station A sends a data packet to station B. Though the bridge was not addressed directly, it receives the packet and searches the forwarding table for destination address B. It finds an entry that refers to LAN2, and eventually sends the packet to this LAN. Packets addressed to computers within the same LAN are not forwarded by the bridge. (See Figure 12-3.)

Figure 12-2. A transparent bridge forwards a packet.

graphics/12fig02.gif


Figure 12-3. Filtering a packet.

graphics/12fig03.gif


If the bridge cannot find a destination address in the forwarding table (i.e., if the bridge does not know to which LAN the destination station is connected), then it sends the packet over all of its outputs, except the input port (flooding). Figure 12-4 shows this process. Flooding means that the bridge can reach all stations, including those with yet unknown location.

Figure 12-4. Forwarding a packet to all outputs.

graphics/12fig04.gif


MAC addresses are not structured hierarchically and hence cannot provide information about the LAN of a destination station, so packets would have to be sent to all outputs of a bridge in a group of interconnected LANs. Unfortunately, flooding packets when the destination network is not known shouldn't be done often. For this reason, transparent bridges have a way to learn the location or direction of an unknown station.

12.2.3 Learning Function

One major problem of transparent bridges relates to how the bridge is structured and how it maintains its forwarding table. Though the system administrator could simply use a static data configuration, this is not desirable for the following reason: A static configuration of the forwarding table cannot respond to changes in the network topology all tables in all bridges would have to be changed manually as soon as a new station is added to one of the LANs. In addition, there would be consistency problems if one station moves from one LAN to another LAN. For this reason, transparent bridges use a learning algorithm, allowing a bridge to learn the location of an unknown station and to be able to respond to a change in location (i.e., forget the old location and learn the new one).

For this purpose, a bridge follows the entire traffic in all LANs connected to it. For each data packet sent to one LAN, the bridge stores its sender MAC address and the LAN that transported the packet in its forwarding table. The bridge assumes that the LAN that received the packet is the home network of the sending station or at least the best path to reach its home network. The method used to learn routing information by looking at the sender address and the input network is also called backward learning in the literature [Tane97].

Backward learning allows a bridge to learn the location of each station that sent a packet. If the bridge receives a packet for a currently unknown station, then it has to use flooding; but it is assumed that a response or acknowledgment will follow from this packet, so the destination address can be found from this reply packet. This means that flooding is normally done only once for each destination address.

functions used to display a topology change: To keep the entries in the forwarding table of a bridge up to date, they are extended by a time stamp (activity time). This time value states how long this entry will be valid. This activity time is updated each time that the bridge receives a packet with a sender MAC address it had previously learned. When the activity time of an entry expires, then this entry is deleted (aging mechanism). It is also assumed that the station was either disconnected from the network or no longer exists. On the other hand, if a packet with a previously unknown source address arrives, then the bridge assumes that this station is new to the network. The address of this system and the network adapter that received the packet are added to the forwarding table, and the activity time is initialized.

12.2.4 Spanning-Tree Protocol

There are often redundant connections in a large local internetwork. For example, there could be several bridges running in parallel to connect two LANs, for load-distribution and failure-safety reasons. Figure 12-5 shows an example with redundant connected networks. In this example, if station A in LAN 2 sends a packet to computer B in LAN 5, then bridge 1 floods this packet to LAN 1, and bridge 3 floods it to LANs 3 and 5. Bridge 3 learns that it can reach station A in LAN 2. In the meantime, bridge 2 receives the packet in LAN 1 and floods it to LANs 3 and 4. This means that bridge 3 receives the same packet again, only this time over a different network adapter. Using its learning function, this bridge changes that entry in the forwarding table and floods the packet to the other networks. We could continue this example endlessly to see that, with this network topology, the forwarding tables of all stations would change continuously, and packets would be duplicated and travel around in the network. The bridges have no way to recognize and destroy duplicate packets.

Figure 12-5. The effect of cycles.

graphics/12fig05.gif


Transparent bridges uses the so-called spanning-tree protocol to solve this problem. This protocol should detect redundant connections in a cyclic topology and build a tree structure that does not include any more cycles. Redundant connections are made inactive and can be reactivated when needed. This means that the LAN internetwork maintains its redundancy. Special messages are used by the bridges in the internetwork to work out the tree structure and to build this structure in a decentralized way.

The spanning-tree method is known from graph theory [OTWi96]. Normally, a spanning tree with minimum total cost can be constructed with an undirected connected graph, where the edges are used as weights to allocate costs. Several algorithms have been introduced as minimum spanning tree (MST) methods to handle this task. The spanning-tree method described here and the MST method have in common that a connected graph is used to form a tree structure. However, the spanning tree in a LAN internetwork is not always the minimum spanning tree from the MST method. This is shown by the example in Figure 12-6.

Figure 12-6. Spanning-tree protocol versus the MST method.

graphics/12fig06.gif


Under the spanning-tree protocol, the root of the tree topology is not determined by the least total cost; instead, the bridge with the smallest bridge identifier is selected. The reason is that the spanning-tree algorithm operates in a decentralized way it is not calculated centrally in one station. This means that, first of all, all bridges have to agree on the bridge to be selected as the root of the tree. Subsequently, working from the root, the branches of the tree with "minimum" path cost are calculated. These minimum-cost paths do not necessarily have to correspond to the tree structure with the least total cost.

Prerequisites and Terminology

Bridges need certain parameters and values to be able to run the spanning-tree algorithm. These values are then used to manipulate the resulting spanning tree. The following parameters are required by the spanning-tree algorithm:

  • Each bridge requires a unique 6-byte identifier, the bridge ID.

  • Each network adapter (port) of a bridge obtains a unique identifier, the port ID.

  • Port cost is assigned to each network adapter. This cost influences the structure of the tree topology, because the total cost should be minimized by the spanning-tree algorithm. For example, the port cost can reflect the load on or speed of a local area network.

  • When two LANs can be reached over several paths, then a priority for each network adapter (port priority) can be considered when selecting a path. The spanning-tree algorithm will then select the adapter with higher priority and equal path cost.

The following are other important terms:

  • Root bridge: This is the bridge representing the root of the tree topology.

  • Root port: This is the port of a bridge with the least transmission cost to the root bridge.

  • Root-path cost: This is the sum of the cost of all root ports on the path from a LAN within the internetwork to the root bridge. The objective is to find the path with the least root-path cost.

Figure 12-7 shows these terms in an example of the topology described above, where Bridge1 is the root of the tree structure shown in Figure 12-8.

Figure 12-7. Topology after running the spanning-tree protocol.

graphics/12fig07.gif


Figure 12-8. Tree topology of the LAN internetwork.

graphics/12fig08.gif


Special packets in the form of so-called Bridge Protocol Data Units (BPDUs) are exchanged to determine the root bridge and distribute path or port cost. There are two types of BPDUs:

  • Configuration BPDUs are also called hello packets or configuration messages. They are used to announce the root-bridge identifier, the cost currently accumulated, and certain timer values. Section 12.4.5 will describe the format of this configuration BPDU.

  • Topology change notification BPDUs (TCN BPDUs): These packets are exchanged when changes occur in the topology. This can happen when a component has failed and when the execution of the spanning-tree method causes certain network adapters of bridges to move into the blocking state.

Bridge PDUs are sent with a special group MAC address. This means that each bridge that receives such a packet can identify a bridge PDU.

Running the Spanning-Tree Algorithm

The spanning-tree algorithm is defined in IEEE standard 802.1d. It specifies the principle used to build a noncyclic topology from a partly meshed or cyclic LAN internetwork. This method operates in an absolutely decentralized way.

The spanning-tree algorithm runs in three steps:

  1. Select the root bridge: The root bridge is the root of the tree topology we want to build. The problem is now to select one of the bridges as the root bridge. To this end, we use a principle similar to the one used in token-ring networks: The bridge with the smallest identifier (bridge ID) is selected as the root bridge.

    At the beginning, the bridges in the LAN internetwork send configuration BPDUs periodically with their own identifiers as root ID to all other bridges. When a bridge receives a BPDU, it is immediately compared with its own bridge ID. If the received root ID is smaller, then the BPDU is forwarded. In contrast, if the own bridge ID is smaller, then it is registered as the root ID and distributed to the other bridges. Eventually, the bridge with the smallest identifier becomes the root bridge.

    One major benefit of this principle is its decentralized property. This means that no central management unit is required. However, the path cost in a LAN internetwork does not play any role in determining the root bridge. This means that you won't necessarily select the best topology, such as in the Minimal Spanning Tree method.

  2. Determine the root port of each bridge: Each bridge selects the network adapter with the smallest path cost on the path to the root bridge as its root port (root-path cost, RPC). If several paths have the same cost, then the port with the highest priority or (if no priorities are set) the port with the smallest port ID is selected as the root port.

  3. Select the designated bridge for a LAN: When one subnetwork within the LAN internetwork is connected to several bridges, so that at least one route over each of these bridges leads to the root bridge, then one of these bridges has to be selected for traffic forwarding to the root bridge. This is the only way to create a tree topology. In a local area network, the bridge with the smallest path cost to the root bridge (the so-called root-path cost) is normally selected. The network adapter used to connect this designated bridge to the local area network is called the designated port. Consequently, there is only one single designated port for each LAN. All adapters of the root bridge are designated ports.

    All output adapters that were not selected as root ports or designated ports are locked (i.e., they take the blocking state). Though no payload packets will be transported over these ports, they can continue receiving BPDUs. This means that a deactivated adapter can detect a component failure and reactivate itself when needed.

Behavior When a Component Fails

When an active bridge (i.e., a root bridge or a designated bridge or an active port) fails, then this can be discovered by a message-age mechanism. To this end, each bridge manages a max age value. If the message age value of a BPDU (see Section 12.4.5) exceeds this value, then the spanning-tree algorithm is reactivated to check for which bridges should be active in the new topology. More specifically, bridges where network adapters change states send the topology-change notification BPDUs described above over the path to the root bridge. This means that all other bridges are informed about a change in topology, so that they can respond accordingly.

The message-age value of a bridge PDU is incremented after each forwarding action. If a failure or the adding of a new bridge causes a cycle, then the message-age value increases continually as the packet cycles, eventually reaching the threshold that triggers the spanning-tree algorithm (to reconfigure the LAN internetwork).

Figure 12-9 shows the topology from Figure 12-7, but with a change: Bridge 3 has failed. This means that the connection from LAN 3 to the root bridge over bridge 2 has to be restored, and LAN 5 is reached over bridge 4. The blocked ports of bridge 4, eth0 and eth1, are activated in this situation, allowing proper communication, even though bridge 3 failed.

Figure 12-9. Topology of Figure 12-7 after bridge 3 has failed.

graphics/12fig09.gif


Avoiding Temporary Loops

The decentralized operation of the spanning tree algorithm makes it possible that some bridges have not stored the globally correct information (i.e., they have only local knowledge). For this reason, the interfaces could be in a "wrong" state, causing loops that can be removed during the further procedure.

For example, if one interface is the designated port, and if no configuration message from a higher-order bridge has arrived in this bridge yet, then data packets would be forwarded on the basis of their local information. Globally, this would cause a loop and the wrong behavior described earlier.

To solve this problem, the standard includes two intermediate states between the blocking and the forwarding states. The transition from one state to another occurs when the so-called forward delay timer expires. In the listening state, a bridge must neither learn addresses nor forward packets. It receives configuration messages only if these messages reset the interface into the blocking state. The next state allows the bridge to enter addresses in the forwarding table (learning function); this state is called the learning state. In the forwarding state, which is reached after another expiry of the forward delay timer, data packets can be forwarded. Figure 12-10 shows the state transitions of a network adapter.

Figure 12-10. State automaton of a bridge port.

graphics/12fig10.gif



       


    Linux Network Architecture
    Linux Network Architecture
    ISBN: 131777203
    EAN: N/A
    Year: 2004
    Pages: 187

    flylib.com © 2008-2017.
    If you may any questions please contact us: flylib@qtcs.net