BRIDGE

BRIDGE

A LAN or MAN is not an isolated entity. An organization may

have more than one type of LAN at a given site to satisfy a spectrum of needs.

An organization may have multiple LANs of the same type at a given site to

accommodate performance or security requirements. Furthermore, an organization

may have LANs and possibly MANS at various sites and may need them to be interconnected

for central control of distributed information exchange.

The simplest approach to extending the range of LAN coverage is the use of

bridges to interconnect a number of individual LANs. A more general solution,

which allows the interconnection of local and wide area networks, is the use of an

internetworking protocol and routers. This latter area is discussed in Lesson 16.

Here, we concentrate on the bridge.

The lesson begins with a discussion of the basic operation of bridges. Then,

we look at the most complex design issues associated with bridges, which is routing.

BRIDGE OPERATION

The early designs for bridges were intended for use between local area networks

(LANs) that use identical protocols for the physical and medium access layers (e.g.,

all conforming to IEEE 802.3 or all conforming to FDDI). Because the devices all

use the same protocols, the amount of processing required at the bridge is minimal.

In recent years, bridges that operate between LANs with different MAC protocols

have been developed. However, the bridge remains a much simpler device than the

router, which is discussed in Lesson 16.

Because the bridge is used in a situation in which all of the LANs have the

same characteristics, the reader may ask why one does not simply use one large

LAN. Depending on circumstance, there are several reasons for the use of multiple

LANs connected by bridges:

Reliability. The danger in connecting all data processing devices in an organization

to one network is that a fault on the network may disable communication

for all devices. By using bridges, the network can be partitioned into selfcontained

units.

Performance. In general, performance on a LAN or MAN declines with an

increase in the number of devices or with the length of the medium. A number

of smaller LANs will often give improved performance if devices can be

clustered so that intra-network traffic significantly exceeds inter-network

traffic.

Security. The establishment of multiple LANs may improve security of communications.

It is desirable to keep different types of traffic (e.g., accounting,

personnel, strategic planning) that have different security needs on physically

separate media. At the same time, the different types of users with different

levels of security need to communicate through controlled and monitored

mechanisms.

Geography. Clearly, two separate LANs are needed to support devices clustered

in two geographically distant locations. Even in the case of two buildings

separated by a highway, it may be far easier to use a microwave bridge

link than to attempt to string coaxial cable between the two buildings. In the

case of widely separated networks, two half bridges are needed (see Figure

14.3, below).

Functions of a Bridge

Figure 14.1 illustrates the operation of a bridge between two LANs, A and B. The

bridge performs the following functions:

* Reads all frames transmitted on A, and accepts those addressed to stations

on B.

* Using the medium access control protocol for B, retransmits the frames

onto B.

* Does the same for B-to-A traffic.

Several design aspects of a bridge are worth highlighting:

1. The bridge makes no modification to the content or format of the frames it

receives, nor does it encapsulate them with an additional header. Each frame

to be transferred is simply copied from one LAN and repeated with exactly

the same bit pattern as the other LAN. Because the two LANs use the same

LAN protocols, it is permissible to do this.

2. The bridge should contain enough buffer space to meet peak demands.

Over a short period of time, frames may arrive faster than they can be

retransmitted.

3. The bridge must contain addressing and routing intelligence. At a minimum,

the bridge must know which addresses are on each network in order to know

which frames to pass. Further, there may be more than two LANs interconnected

by a number of bridges. In that case, a frame may have to be routed

through several bridges in its journey from source to destination.

4. A bridge may connect more than two LANs.

The bridge provides an extension to the LAN that requires no modification to

the communications software in the stations attached to the LANs. It appears to all

stations on the two (or more) LANs that there is a single LAN on which each station

has a unique address. The station uses that unique address and need not explicitly

discriminate between stations on the same LAN and stations on other LANs;

the bridge takes care of that.

The description above has applied to the simplest sort of bridge. More sophisticated

bridges can be used in more complex collections of LANs. These constructions

would include additional functions, such as,

a Each bridge can maintain status information on other bridges, together with

the cost and number of bridge-to-bridge hops required to reach each network.

This information may be updated by periodic exchanges of information

among bridges; this allows the bridges to perform a dynamic routing function.

@ A control mechanism can manage frame buffers in each bridge to overcome

congestion. Under saturation conditions, the bridge can give precedence to en

route packets over new packets just entering the internet from an attached

LAN, thus preserving the investment in line bandwidth and processing time

already made in the en route frame.

Bridge Protocol Architecture

The IEEE 802.1D specification defines the protocol architecture for MAC bridges.

In addition, the standard suggests formats for a globally administered set of MAC

station addresses across multiple homogeneous LANs. In this sublesson, we examine

the protocol architecture of these bridges.

Within the 802 architecture, the endpoint or station address is designated at

the MAC level. Thus, it is at the MAC level that a bridge can function. Figure 14.2

shows the simplest case, which consists of two LANs connected by a single bridge.

The LANs employ the same MAC and LLC protocols. The bridge operates as previously

described. A MAC frame whose destination is not on the immediate LAN

is captured by the bridge, buffered briefly, and then transmitted on the other LAN.

As far as the LLC layer is concerned, there is a dialogue between peer LLC entities

in the two endpoint stations. The bridge need not contain an LLC layer, as it is

merely serving to relay the MAC frames.

Figure 14.2b indicates the way in which data is encapsulated using a bridge.

Data are provided by some user to LLC. The LLC entity appends a header and

passes the resulting data unit to the MAC entity, which appends a header and a

trailer to form a MAC frame. On the basis of the destination MAC address in the

frame, it is captured by the bridge. The bridge does not strip off the MAC fields; its

function is to relay the MAC frame intact to the destination LAN. Thus. the frame

is deposited on the destination LAN and captured by the destination station.

The concept of a MAC relay bridge is not limited to the use of a single bridge

to connect two nearby LANs. If the LANs are some distance apart, then they can

be connected by two bridges that are in turn connected by a communications facility.

For example, Figure 14.3 shows the case of two bridges connected by a point-topoint

link. In this case, when a bridge captures a MAC frame, it appends a link layer

(e.g., HDLC) header and trailer to transmit the MAC frame across the link to the

other bridge. The target bridge strips off these link fields and transmits the original,

unmodified MAC frame to the destination station.

The intervening communications facility can be a network, such as a widearea-

packet-switching network, as illustrated in Figure 14.4. In this case, the bridge

is somewhat more complicated, although it performs the same function of relaying

MAC frames. The connection between bridges is via an X.25 virtual circuit. Again,

the two LLC entities in the end systems have a direct logical relationship with no

intervening LLC entities. Thus, in this situation, the X.25 packet layer is operating

below an 802 LLC layer. As before, a MAC frame is passed intact between the endpoints.

When the bridge on the source LAN receives the frame, it appends an X.25

packet-layer header and an X.25 link-layer header and trailer and sends the data to

the DCE (packet-switching node) to which it attaches. The DCE strips off the linklayer

fields and sends the X.25 packet through the network to another DCE. The

target DCE appends the link-layer field and sends this to the target bridge. The target

bridge strips off all the X.25 fields and transmits the original unmodified MAC

frame to the destination endpoint.

ROUTING WITH BRIDGES

MAC-H

In the configuration of Figure 14.1, the bridge makes the decision to relay a frame

on the basis of destination MAC address. In a more complex configuration, the

bridge must also make a routing decision. Consider the configuration of Figure 14.5.

Suppose that station 1 transmits a frame on LAN A intended for station 5. The

frame will be read by both bridge 101 and bridge 102. For each bridge, the

addressed station is not on a LAN to which the bridge is attached. Therefore, each

bridge must make a decision of whether or not to retransmit the frame on its other

LAN, in order to move it closer to its intended destination. In this case, bridge 101

should repeat the frame on LAN B, whereas bridge 102 should refrain from retransmitting

the frame. Once the frame has been transmitted on LAN B, it will be picked

up by both bridges 103 and 104. Again, each must decide whether or not to forward

the frame. In this case, bridge 104 should retransmit the frame on LAN E, where it

will be received by the destination, station 5.

Thus, we see that, in the general case, the bridge must be equipped with a

routing capability. When a bridge receives a frame, it must decide whether or not to

forward it. If the bridge is attached to two or more networks, then it must decide

whether or not to forward the frame and, if so, on which LAN the frame should be

transmitted.

The routing decision may not always be a simple one. In Figure 14.6, bridge

107 is added to the previous configuration, directly linking LAN A and LAN E.

Such an addition may be made to provide for higher overall internet availability. In

this case, if Station 1 transmits a frame on LAN A intended for station 5 on LAN

E, then either bridge 101 or bridge 107 could forward the frame. It would appear

preferable for bridge 107 to forward the frame, as it will involve only one hop,

whereas if the frame travels through bridge 101, it must suffer two hops. Another

consideration is that there may be changes in the configuration. For example, bridge

107 may fail, in which case subsequent frames from station 1 to station 5 should go

through bridge 101. We can say, then, that the routing capability must take into

account the topology of the internet configuration and may need to be dynamically

altered.

Figure 14.6 suggests that a bridge knows the identity of each station on each

LAN. In a large configuration, such an arrangement is unwieldy. Furthermore, as

stations are added to and dropped from LANs, all directories of station location

must be updated. It would facilitate the development of a routing capability if all

MAC-level addresses were in the form of a network part and a station part. For

example, the IEEE 802.5 standard suggests that 16-bit MAC addresses consist of a

7-bit LAN number and an 8-bit station number, and that 48-bit addresses consist of

a 14-bit LAN number and a 32-bit station number.' In the remainder of this discussion,

we assume that all MAC addresses include a LAN number and that routing is

based on the use of that portion of the address only.

A variety of routing strategies have been proposed and implemented in recent

years. The simplest and most common strategy is fixed routing. This strategy is suitable

for small LAN collections and for interconnections that are relatively stable.

More recently, two groups within the IEEE 802 committee have developed specifications

for routing strategies. The IEEE 802.1 group has issued a standard for routing

based on the use of a spanning tree algorithm. The token ring committee, IEEE

802.5, has issued its own specification, referred to as source routing. We examine

these three strategies in turn.

Fixed Routing

Fixed routing was introduced in our discussion of routing for packet-switching networks.

For fixed routing with bridges, a route is selected for each source-destination

pair of LANs in the internet. If alternate routes are available between two LANs,

then typically the route with the least number of hops is selected. The routes are

fixed, or at least only change when there is a change in the topology of the internet.

Figure 14.7 shows a fixed-routing design for the configuration of Figure 14.6.

A central routing matrix shows, for each source-destination pair of LANs, the identity

of the first bridge on the route. So, for example, the route from LAN E to

LAN F begins by going through bridge 107 to LAN A. Again, consulting the matrix,

the route from LAN A to LAN F goes through bridge 102 to LAN C. Finally,

the route from LAN C to LAN F is directly through bridge 105. Thus, the

complete route from LAN E to LAN F is bridge 107, LAN A, bridge 102, LAN C,

bridge 105.

Only one column of this matrix is needed in each bridge for each LAN to

which it attaches. For example, bridge 105 has two tables, one for frames arriving

from LAN C and one for frames arriving from LAN F. The table shows, for each

possible destination MAC address, the identity of the LAN to which the bridge

should forward the frame. The table labeled "From LAN C" is derived from the

column labeled C in the routing matrix. Every entry in that column that contains

bridge number 105 results in an entry in the corresponding table in bridge 105.

Once the directories have been established, routing is a simple matter. A

bridge copies each incoming frame on each of its LANs. If the destination MAC

address corresponds to an entry in its routing table, the frame is retransmitted on

the appropriate LAN.

The fixed routing strategy is widely used in commercially available products;

it has the advantage of simplicity and minimal processing requirements. However,

in a complex internet, in which bridges may be dynamically added and in which failures

must be allowed for, this strategy is too limited. In the next two sublessons, we

cover more powerful alternatives.

Spanning Tree Routing

The spanning tree approach is a mechanism in which bridges automatically develop

a routing table and update that table in response to changing topology. The algorithm

consists of three mechanisms: frame forwarding, address learning, and loop

resolution.

Frame Forwarding

In this scheme, a bridge maintains a filtering database, which is based on MAC

address. Each entry consists of a MAC individual or group address, a port number,

and an aging time (described below); we can interpret this in the following fashion.

A station is listed with a given port number if it is on the same side of the bridge as

the port. For example, for bridge 102 of Figure 14.5, stations on LANs C, F, and G

are on the same side of the bridge as the LAN C port; and stations on LANs A, B,

D, and E are on the same side of the bridge as the LAN A port. When a frame is

received on any port, the bridge must decide whether that frame is to be forwarded

through the bridge and out through one of the bridge's other ports. Suppose that a

bridge receives a MAC frame on port x. The following rules are applied (Figure

14.8):

1. Search the forwarding database to determine if the MAC address is listed for

any port except port x.

2. If the destination MAC address is not found, flood the frame by sending it out

on all ports except the port by which it arrived.

3. If the destination address is in the forwarding database for some port y f x,

then determine whether port y is in a blocking or a forwarding state. For reasons

explained below, a port may sometimes be blocked, which prevents it

from receiving or transmitting frames.

4. If port y is not blocked, transmit the frame through port y onto the LAN to

which that port attaches.

Rule (2) is needed because of the dynamic nature of the filtering database.

When a bridge is initialized, the database is empty. Because the bridge does not

know where to send the frame, it floods the frame onto all of its LANs except the

LAN on which the frame arrives. As the bridge gains information, the flooding

activity subsides.

Address Learning

The above scheme is based on the use of a filtering database that indicates the direction,

from the bridge, of each destination station. This information can be preloaded

into the bridge, as in static routing. However, an effective automatic mechanism for

learning the direction of each station is desirable. A simple scheme for acquiring

this information is based on the use of the source address field in each MAC frame

(Figure 14.8).

When a frame arrives on a particular port, it clearly has come from the direction

of the incoming LAN. The source address field of the frame indicates the

source station. Thus, a bridge can update its filtering database for that MAC

address. To allow for changes in topology, each entry in the database is equipped

with an aging timer. When a new entry is added to the database, its timer is set; the

recommended default value is 300 seconds. If the timer expires, then the entry is

eliminated from the database, as the corresponding direction information may no

longer be valid. Each time a frame is received, its source address is checked against

the database. If the entry is already in the database, the entry is updated (the direction

may have changed) and the timer is reset. If the entry is not in the database, a

new entry is created, with its own timer.

The above discussion indicated that the individual entries in the database are

station addresses. If a two-level address structure (LAN number, station number) is

used, then only LAN addresses need to be entered in the database. Both schemes

work the same. The only difference is that the use of station addresses requires a

much larger database than the use of LAN addresses.

Note from Figure 14.8 that the bridge learning process is applied to all frames,

not just those that are forwarded.

Spanning Tree Algorithm

The address learning mechanism described above is effective if the topology of the

internet is a tree; that is, if there are no alternate routes in the network. The existence

of alternate routes means that there is a closed loop. For example in Figure

14.6, the following is a closed loop: LAN A, bridge 101, LAN B, bridge 104, LAN

E, bridge 107, LAN A.

frames on LAN X that will be picked up for retransmission on LAN Y. This process

repeats indefinitely.

To overcome the above problem, a simple result from graph theory is used:

For any connected graph, consisting of nodes and edges connecting pairs of nodes,

there is a spanning tree of edges that maintains the connectivity of the graph but

contains no closed loops. In terms of internets, each LAN corresponds to a graph

node, and each bridge corresponds to a graph edge. Thus, in Figure 14.6, the

removal of one (and only one) of bridges 107,101, or 104, results in a spanning tree.

What is desired is to develop a simple algorithm by which the bridges of the internet

can exchange sufficient information to automatically (without user intervention)

derive a spanning tree. The algorithm must be dynamic. That is, when a topology

change occurs, the bridges must be able to discover this fact and automatically

derive a new spanning tree.

The algorithm is based on the use of the following:

1. Each bridge is assigned a unique identifier; in essence, the identifier consists

of a MAC address for the bridge plus a priority level.

2. There is a special group MAC address that means "all bridges on this LAN."

When a MAC frame is transmitted with the group address in the destination

address field, all of the bridges on the LAN will capture that frame and interpret

it as a frame addressed to itself.

3. Each port of a bridge is uniquely identified within the bridge, with a port

identifier.

With this information established, the bridges are able to exchange routing

information in order to determine a spanning tree of the internet. We will explain

the operation of the algorithm using Figures 14.10 and 14.11 as an example. The following

concepts are needed in the creation of the spanning tree:

Root bridge. The bridge with the lowest value of bridge identifier is chosen to

be the root of the spanning tree.

Path cost. Associated with each port on each bridge is a path cost, which is the

cost of transmitting a frame onto a LAN through that port. A path between

two stations will pass through 0 or more bridges. At each bridge, the cost of

transmission is added to give a total cost for a particular path. In the simplest

case, all path costs would be assigned a value of 1; thus, the cost of a path

would simply be a count of the number of bridges along the path. Alternatively,

costs could be assigned in inverse proportion to the data rate of the corresponding

LAN, or any other criterion chosen by the network manager.

Root port. Each bridge discovers the first hop on the minimum-cost path to

the root bridge. The port used for that hop is labeled the root port. When the

cost is equal for two ports, the lower port number is selected so that a unique

spanning tree is constructed.

Root path cost. For each bridge, the cost of the path to the root bridge with

minimum cost (the path that starts at the root port) is the root path cost for

that bridge.

@ Designated bridge, designated port. On each LAN, one bridge is chosen to be

the designated bridge. This is the bridge on that LAN that provides the minimum

cost path to the root bridge. This is the only bridge allowed to forward

frames from the LAN for which it is the designated bridge toward the root

bridge. The port of the designated bridge that attaches the bridge to the LAN

is the designated port. For all LANs to which the root bridge is attached, the

root bridge is the designated bridge. All internet traffic to and from the LAN

passes through the designated port.

In general terms, the spanning tree is constructed in the following fashion:

I. Determine the root bridge.

2. Determine the root port on all other bridges.

3. Determine the designated port on each LAN. This will be the port with the

minimum root path cost. In the case of two or more bridges with the same root

path cost, the highest-priority bridge is chosen as the designated bridge. If the

designated bridge has two or more ports attached to this LAN, then the port

with the lowest value of port identifier is chosen.

By this process, when two LANs are directly connected by more than one

bridge, all of the bridges but one are eliminated. This cuts any loops that involve

two LANs. It can be demonstrated that this process also eliminates all loops involving

more than two LANs and that connectivity is preserved. Thus, this process discovers

a spanning tree for the given internet. In our example, the solid lines indicate

the bridge ports that participate in the spanning tree.

The steps outlined above require that the bridges exchange information. The

information is exchanged in the form of bridge protocol data units (BPDUs). A

BPDU transmitted by one bridge is addressed to and received by all of the other

bridges on the same LAN. Each BPDU contains the following information:

The identifier of this bridge and the port on this bridge

The identifier of the bridge that this bridge considers to be the root

The root path cost for this bridge

To begin, all bridges consider themselves to be the root bridge. Each bridge

will broadcast a BPDU on each of its LANs that asserts this fact. On any given

LAN, only one claimant will have the lowest-valued identifier and will maintain its

belief. Over time, as BPDUs propagate, the identity of the lowest-valued bridge

identifier throughout the internet will be known to all bridges. The root bridge will

regularly broadcast the fact that it is the root bridge on all of the LANs to which it

is attached; this allows the bridges on those LANs to determine their root port and

the fact that they are directly connected to the root bridge. Each of these bridges in

turn broadcasts a BPDU on the other LANs to which it is attached (all LANs

except the one on its root port), indicating that it is one hop away from the root

bridge. This activity is propagated throughout the internet. Every time that a bridge

receives a BPDU, it transmits BPDUs, indicating the identity of the root bridge and

the number of hops to reach the root bridge. On any LAN, the bridge claiming to

be the one that is closest to the root becomes the designated bridge.

We can trace some of this activity with the configuration in Figure 14.10. At

startup time, bridges 1,3, and 4 all transmit BPDUs on LAN 2, each claiming to be

the root bridge. When bridge 3 receives the transmission from bridge 1, it recognizes

a superior claimant and defers. Bridge 3 has also received a claiming BPDU

from bridge 5 via LAN 5. Bridge 3 recognizes that bridge 1 has a superior claim to

be the root bridge; it therefore assigns its LAN 2 port to be its root port, and sets

the root path cost to 10. By similar actions, bridge 4 ends up with a root path cost

of 5 via LAN 2; bridge 5 has a root path cost of 5 via LAN 1; and bridge 2 has a root

path cost of 10 via LAN 1.

Now consider the assignment of designated bridges. On LAN 5, all three

bridges transmit BPDUs, attempting to assert a claim to be designated bridge.

Bridge 3 defers because it receives BPDUs from the other bridges that have a lower

root path cost. Bridges 4 and 5 have the same root path cost, but bridge 4 has the

higher priority and therefore becomes the designated bridge.

The results of all this activity are shown in Figure 14.11. Only the designated

bridge on each LAN is allowed to forward frames. All of the ports on all of the

other bridges are placed in a blocking state. After the spanning tree is established,

bridges continue to periodically exchange BPDUs to be able to react to any change

in topology, cost assignments, or priority assignment. Anytime that a bridge

receives a BPDU on a port, it makes two assessments:

1. If the BPDU arrives on a port that is considered the designated port, does the

transmitting port have a better claim to be the designated port?

2. Should this port be my root port?

Source Routing

The IEEE 802.5 committee has developed a bridge routing approach referred to as

source routing. With this approach, the sending station determines the route that

the frame will follow and includes the routing information with the frame; bridges

read the routing information to determine if they should forward the frame.

Basic Operation

The basic operation of the algorithm can be described by making reference to the

configuration in Figure 14.12. A frame from station X can reach station Z by either

of the following routes:

* LAN 1, bridge B1, LAN 3, bridge B3, LAN 2

* LAN 1, bridge B2, LAN 4, bridge B4, LAN 2

Station X may choose one of these two routes and place the information, in the

form of a sequence of LAN and bridge identifiers, in the frame to be transmitted.

When a bridge receives a frame, it will forward that frame if the bridge is on the designated

route; all other frames are discarded. In this case, if the first route above is

specified, bridges B1 and B3 will forward the frame; if the second route is specified,

bridges B2 and B4 will forward the frame.

Note that with this scheme, bridges need not maintain routing tables. The

bridge makes the decision whether or not to forward a frame solely on the basis of

the routing information contained in that frame. All that is required is that the

bridge know its own unique identifier and the identifier of each LAN to which it is

attached. The responsibility for designing the route falls to the source station.

For this scheme to work, there must be a mechanism by which a station can

determine a route to any destination station. Before addressing this issue, we need

to discuss various types of routing directives.

Routing Directives and Addressing Modes

The source routing scheme developed by the IEEE 802.5 committee includes four

different types of routing directives. Each frame that is transmitted includes an indicator

of the type of routing desired. The four directive types are

0 Null. No routing is desired. In this case, the frame can only be delivered to

stations on the same LAN as the source station.

Nonbroadcast. The frame includes a route, consisting of a sequence of LAN

numbers and bridge numbers, that defines a unique route from the source station

to the destination station. Only bridges on that route forward the frame,

and only a single copy of the frame is delivered to the destination station.

All-routes broadcast. The frame will reach each LAN of the internet by all

possible routes. Thus, each bridge will forward each frame once to each of its

ports in a direction away from the source node, and multiple copies of the

frame may appear on a LAN. The destination station will receive one copy of

the frame for each possible route through the network.

Single-route broadcast. Regardless of the destination address of the frame,

the frame will appear once, and only once, on each LAN in the internet. For

this effect to be achieved, the frame is forwarded by all bridges that are on a

spanning tree (with the source node as the root) of the internet. The destination

station receives a single copy of the frame.

Let us first examine the potential application of each of these four types of

routing, and then examine the mechanisms that may be employed to achieve these

procedures. First, consider null routing. In this case the bridges that share the LAN

with the source station are told not to forward the frame; this will be done if the

intended destination is on the same LAN as the source station. Nonbroadcast routing

is used when the two stations are not on the same LAN and the source station

knows a route that can be used to reach the destination station. Only the bridges on

that route will forward the frame.

The remaining two types of routing can be used by the source to discover a

route to the destination. For example, the source station can use all-routes broadcasting

to send a request frame to the intended destination. The destination returns

a response frame on each of the routes, using nonbroadcast routing, followed by the

incoming request frame. The source station can pick one of these routes and send

future frames on that route. Alternatively, the source station could use single-route

broadcasting to send a single request frame to the destination station. The destination

station could send its response frame via all-routes broadcasting. The incoming

frames would reveal all of the possible routes to the destination station, and the

source station could pick one of these for future transmissions. Finally, single-route

broadcasting could be used for group addressing, as discussed below.

Now consider the mechanisms for implementing these various routing directives.

Each frame must include an indicator of which of the four types of routing is

required. For null routing, the frame is ignored by the bridge. For nonbroadcast

routing, the frame includes an ordered list of LAN numbers and bridge numbers.

When a bridge receives a nonbroadcast frame, it forwards the frame only if the

routing information contains the sequence LAN i, Bridge x, LAN j, where

LAN i = LAN from which the frame arrived

Bridge x = this bridge

LAN j = another LAN to which this bridge is attached

For all-routes broadcasting, the source station marks the frame, but includes

no routing information. Each bridge that forwards the frame will add its bridge

number and the outgoing LAN number to the frame's routing information field.

Thus, when the frame reaches its destination, it will include a sequenced list of all

LANs and bridges visited. To prevent the endless repetition and looping of frames,

a bridge obeys the following rule. When an all-routes broadcast frame is received,

the bridge examines the routing information field. If the field contains the number

of a LAN to which the bridge is attached, the bridge will refrain from forwarding

the frame on that LAN. Put the other way, the bridge will only forward the frame

to a LAN that the frame has not already visited.

Finally, for single-route broadcasting, a spanning tree of the internet must be

developed. This can either be done automatically, as in the 802.1 specification, or

manually. In either case, as with the 802.1 strategy, one bridge on each LAN is the

designated bridge for that LAN, and is the only one that forwards single-route

frames.

It is worth noting the relationship between addressing mode and routing

directive. There are three types of MAC addresses:

* Individual. The address specifies a unique destination station.

* Group. The address specifies a group of destination addresses; this is also

referred to as multicast.

e AM-stations. The address specifies all stations that are capable of receiving

this frame; this is also referred to as broadcast. We will refrain from using this

latter term as it is also used in the source routing terminology.

In the case of a single, isolated LAN, group and all-stations addresses refer to

stations on the same LAN as the source station. In an internet, it may be desirable

to transmit a frame to multiple stations on multiple LANs. Indeed, because a set of

LANs interconnected by bridges should appear to the user as a single LAN, the

ability to do group and all-stations addressing across the entire internet is

mandatory.

Table 14.1 summarizes the relationship between routing specification and

addressing mode. If no routing is specified, then all addresses refer only to the

immediate LAN. If nonbroadcast routing is specified, then addresses may refer to

any station on any LAN visited on the nonbroadcast route. From an addressing

point of view, this combination is not generally useful for group and all-stations

addressing. If either the all-routes or single-route specification is included in a

frame, then all stations on the internet can be addressed. Thus, the total internet

acts as a single network from the point of view of MAC addresses. Because less traffic

is generated by the single-route specification, this single-network characteristic

is to be preferred for group and all-stations addressing. Note also that the singleroute

mechanism in source routing is equivalent to the 802.1 spanning tree

approach. Thus, the spanning tree approach supports both group and all-stations

addressing.

Route Discovery and Selection

With source routing, bridges are relieved of the burden of storing and using routing

information. Thus, the burden falls on the stations that wish to transmit frames.

Clearly, some mechanism is needed by which the source stations can know the route

by which frames are to be sent. Three strategies suggest themselves:

1. Manually load the information into each station. This is simple and effective

but has several drawbacks. First, anytime that the configuration is changed,

the routing information at all stations must be updated. Secondly, this

approach does not provide for automatic adjustment in the face of the failure

of a bridge or LAN.

2. One station on a LAN can query other stations on the same LAN for routing

information about distant stations. This approach may reduce the overall

amount of routing messages that must be transmitted, compared to options

3 or 4, below. However, at least one station on each LAN must have the

needed routing information, so this is not a complete solution.

3. When a station needs to learn the route to a destination station, it engages in

a dynamic route discovery procedure.

Option 3 is the most flexible and the one that is specified by IEEE 802.5; as

was mentioned earlier, two approaches are possible. The source station can transmit

an all-routes request frame to the destination. Thus, all possible routes to the

destination are discovered. The destination station can then send back a nonbroadcast

response on each of the discovered routes, allowing the source to choose which

route to follow in subsequently transmitting the frame. This approach generates

quite a bit of both forward and backward traffic, and requires the destination station

to receive and transmit a number of frames. An alternative is for the source station

to transmit a single-route request frame. Only one copy of this frame will reach

the destination. The destination responds with an all-routes response frame, which

generates all possible routes back to the source. Again, the source can choose

among these alternative routes.

Figure 14.12 illustrates the latter approach. Assume that the spanning tree

that has been chosen for this internet consists of bridges B1, B3, and B4. In this

example, station X wishes to discover a route to station Z. Station X issues a singleroute

request frame. Bridge B2 is not on the spanning tree and so does not forward

the frame. The other bridges do forward the frame, and it reaches station Z. Note

that bridge B4 forwards the frame to LAN 4, although this is not necessary; it is simply

an effect of the spanning tree mechanism. When Z receives this frame, it

responds with an all-routes frame. Two messages reach X: one on the path LAN 2,

B3, LAN 3, El, LAN 1, and the other on the path LAN 2, B4, LAN 4, B2, LAN 1.

Note that a frame that arrived by the latter route is received by bridge B1 and forwarded

onto LAN 3. However, when bridge B3 receives this frame, it sees in the

routing information field that the frame has already visited LAN 2; therefore, it

does not forward the frame. A similar fate occurs for the frame that follows the first

route and is forwarded by bridge B2.

Once a collection of routes has been discovered, the source station needs to

select one of the routes. The obvious criterion would be to select the minimum-hop

route. Alternatively, a minimum-cost route could be selected, where the cost of a

network is inversely proportional to its data rate. In either case, if two or more

routes are equivalent by the chosen criterion, then there are two alternatives:

1. Choose the route corresponding to the response message that arrives first.

One may assume that that particular route is less congested than the others as

the frame on that route arrived earliest.

2. Choose randomly. This should have the effect, over time, of leveling the load

among the various bridges.

Another point to consider is how often to update a route. Routes should certainly

be changed in response to network failures and should perhaps be changed in

response to network congestion. If connection-oriented logical link control is used

(see Lesson 6). then one possibility is to rediscover the route with each new

connection. Another alternative, which works with either connection-oriented or

connectionless service, is to associate a timer with each selected route, and to rediscover

the route when its time expires.