Sec.5.1 Introduction 383 the difficulties of this,think of a telephone company trying to operate a network where customers can change their residence without notifying the company,while maintaining their phone numbers.We now describe the two major routing appoaches. Spanning tree routing in bridged local area networks.In the spanning tree method,the key data structure is a spanning tree,which is used by a bridge to determine whether and to which LAN it should relay a packet (see Fig.5.16).The spanning tree consists of a subset of ports that connect all LANs into a network with no cycles.An important property of a spanning tree is that each of its links separates the tree in two parts;that is,each node of the tree lies on exactly one "side"of the link. From this it is seen that there is a unique path from every LAN to every other LAN on the spanning tree.This path is used for communication of all packets between the LANs. The ports lying on the spanning tree are called designated or active ports.The spanning tree may need to be modified due to bridge failures,but we postpone a discussion of this issue for later,assuming for the time being that the spanning tree is fixed. To understand how routing works,note that each bridge can communicate with any given station through a unique active port (see Fig.5.16).Therefore,to implement spanning tree routing,it is sufficient to maintain for each active port a list of the stations with which the port communicates;this is known as the forwarding database (FDB)of the port.Assuming that the FDBs at each bridge are complete(they contain all stations), routing would be implemented as follows:If a packet is heard on the LAN corresponding to an active port A of a bridge,then if the destination ID of the packet is included in the FDB of an active bridge port B different from A,the packet is transmitted on the LAN connected to B;otherwise,the packet is discarded by the bridge (see Fig.5.17). Unfortunately,the routing method just described does not quite work because the FDBs of the active ports are not complete at all times.The reason is that stations may be turned on and off or change location,and also the spanning tree may change. LANA LAN B P9PRLANF T.R Bridge T.R Ethernet Bridge Bridge Bridge Active ports Active ports Active ports LANC Bridge T.R P LANE Ethernet LAN D Ethernet Active port Figure 5.16 Illustration of spanning tree in a network of LANs interconnected with bridges.The spanning tree consists of a set of bridge ports (called active),which connect all LANs into a network without cycles.Only active ports are used for routing packets and thus there is a unique route connecting a pair of LANs.For example.a packet of a station connected to LAN C will go to a station in LAN E through LANs A and B
Sec. 5.1 Introduction 383 the difficulties of this, think of a telephone company trying to operate a network where customers can change their residence without notifying the company, while maintaining their phone numbers. We now describe the two major routing appoaches. Spanning tree routing in bridged local area networks. In the spanning tree method, the key data structure is a spanning tree, which is used by a bridge to determine whether and to which LAN it should relay a packet (see Fig. 5.16). The spanning tree consists of a subset of ports that connect all LANs into a network with no cycles. An important property of a spanning tree is that each of its links separates the tree in two parts; that is, each node of the tree lies on exactly one "side" of the link. From this it is seen that there is a unique path from every LAN to every other LAN on the spanning tree. This path is used for communication of all packets between the LANs. The ports lying on the spanning tree are called designated or active ports. The spanning tree may need to be modified due to bridge failures, but we postpone a discussion of this issue for later, assuming for the time being that the spanning tree is fixed. To understand how routing works, note that each bridge can communicate with any given station through a unique active port (see Fig. 5.16). Therefore, to implement spanning tree routing, it is sufficient to maintain for each active port a list of the stations with which the port communicates; this is known as the fOlwarding database (FDB) of the port. Assuming that the FDBs at each bridge are complete (they contain all stations), routing would be implemented as follows: If a packet is heard on the LAN corresponding to an active port A of a bridge, then if the destination ID of the packet is included in the FDB of an active bridge port B different from A, the packet is transmitted on the LAN connected to B; otherwise, the packet is discarded by the bridge (see Fig. 5.17). Unfortunately, the routing method just described does not quite work because the FDBs of the active ports are not complete at all times. The reason is that stations may be turned on and off or change location, and also the spanning tree may change. LANA .J.....---'-.-L~LAN F Brid~ Active ports LAN E Figure 5.16 Illustration of spanning tree in a network of LANs interconnected with bridges. The spanning tree consists of a set of bridge ports (called active), which connect all LANs into a network without cycles. Only active ports are used for routing packets and thus there is a unique route connecting a pair of LANs. For example, a packet of a station connected to LAN C will go to a station in LAN E through LANs A and B
384 Routing in Data Networks Chap.5 FDB FDB 36 59 To:5 Active port A Active port B To:5 To:5 Bridge 0 LAN To:5 To:5 LAN To:5 FDB 2 ⑨ 78 Each station must be on some active Active port C port FDB of each bridge Bridge 8 LAN Figure 5.17 Using forwarding databases (FDBs)to effect spanning tree routing.Each active port maintains an FDB,that is.a list of the stations with which it communicates. An active port,say A.checks the destination of each packet transmitted within its associated LAN.If the destination appears in the FDB of another active port of the same bridge.say B.the bridge broadcasts the packet on the LAN connected with port B. For this reason,the FDBs are constantly being updated through a process known as bridge learning.Each active port adds to its FDB the source ID numbers of the packets transmitted on the corresponding LAN.Also each active port deletes from its FDB the ID numbers of stations whose packets have not been transmitted on the corresponding LAN for a certain period of time:this helps to deal with situations where a station is disconnected with one LAN and is connected to another,and also cleans up automatically the FDBs when the spanning tree changes.When a port first becomes active its FDB is initialized to empty. Since not all station IDs will become known through bridge learning,the routing method includes a search feature.If the destination ID of an incoming packet at some active port is unknown at each of the bridge's FDBs,the bridge relays the packet on all the other active ports.An illustration of the algorithm's operation in this case is shown in Fig.5.18.Here station I sends a packet P to station 2,but because 2 has not yet transmitted any packet.its ID number does not appear on any FDB.Then P is broadcast on the entire spanning tree,eventually reaching the destination 2.When 2 answers P with a packet R of its own,this packet will follow the unique spanning tree route to I (because 1's ID number was entered in all of the appropriate FDBs of active ports of the spanning tree when P was broadcast through the spanning tree).As a result,2's ID number will be entered in the FDBs of the active ports along the route that connects 2 with 1,and a subsequent packet from I to 2 will follow this route
384 Routing in Data Networks Chap. 5 -~ ITJOB 2 9 Each station must be on some active port FDB of each bridge Bridge Active port B r---..... Active port C Active port A Figure 5.17 Using forwarding databases (FOBs) to effect spanning tree routing. Each active port maintains an FOB. that is. a list of the stations with which it communicates. An active port. say A, checks the destination of each packet transmitted within its associated LAN. If the destination appears in the FOB of another active port of the same bridge. say B. the bridge broadcasts the packet on the LAN connected with port B. For this reason, the FDBs are constantly being updated through a process known as bridge learning. Each active port adds to its FOB the source IO numbers of the packets transmitted on the corresponding LAN. Also each active port deletes from its FOB the ID numbers of stations whose packets have not been transmitted on the corresponding LAN for a certain period of time; this helps to deal with situations where a station is disconnected with one LAN and is connected to another, and also cleans up automatically the FDBs when the spanning tree changes. When a port first becomes active its FOB is initialized to empty. Since not all station IDs will become known through bridge learning, the routing method includes a search feature. If the destination IO of an incoming packet at some active port is unknown at each of the bridge's FOBs, the bridge relays the packet on all the other active ports. An illustration of the algorithm's operation in this case is shown in Fig. 5.18. Here station I sends a packet P to station 2, but because 2 has not yet transmitted any packet, its ID number does not appear on any FOB. Then P is broadcast on the entire spanning tree, eventually reaching the destination 2. When 2 answers P with a packet R of its own, this packet will follow the unique spanning tree route to I (because l's 10 number was entered in all of the appropriate FOBs of active ports of the spanning tree when P was broadcast through the spanning tree). As a result, 2's ID number will be entered in the FOBs of the active ports along the route that connects 2 with I, and a subsequent packet from I to 2 will follow this route
Sec.5.1 Introduction 385 Station 1 Station 2 2 R R R R R LAN A Bridge 1 LAN C Bridge 2 LAN E Bridge 3 LAN B LAN D Figure 5.18 Illustration of bridge learning and FDB updating.Station I sends a packet P to station 2.but the ID of station 2 does not appear in the FDB of any active port of bridge 1(because.for example.station 2 has not transmitted any packet for a long time). Packet p is broadcast into LANs B and C by bridge 1.and then it is broadcast into LANs D and E by bridge 2.In the process the ID of node I is entered in the left-side FDBs of bridges I and 2 (if not already there).Station 2 replies with a packet 1.which goes directly to its destination station I through bridges 2 and I.because the ID number of station I appears in the left-side FDBs of these bridges. The method by which the spanning tree is updated in the event of a bridge or LAN failure or repair remains to be discussed.There are several algorithms for constructing spanning trees,some of which are discussed in Section 5.2.What is needed here. however,is a distributed algorithm that can work in the face of multiple and unpredictable failures and repairs.A relatively simple possibility is to use a spanning tree of shortest paths from every LAN and bridge to a particular destination (or root).We will see in Section 5.2 that the Bellman-Ford algorithm is particularly well suited for this purpose. There is still,however,an extra difficulty,namely how to get all bridges to agree on the root and what to do when the root itself fails.Such issues involve subtle difficulties, which are unfortunately generic in distributed algorithms dealing with component failures. The difficulty can be resolved by numbering the bridges and by designating as root of the tree the bridge with the smallest ID number.Each bridge keeps track of the smallest bridge ID number that it knows of.A bridge must periodically initiate a spanning tree construction algorithm if it views itself as the root based on its own ID number and the ID numbers of other bridges it is aware of.Also,each bridge ignores messages from bridges other than its current root.To cope with the situation where the root fails.bridges may broadcast periodically special"hello"messages to other bridges.These messages may also carry additional information relating to the spanning tree construction and updating algorithm.(See [Bac88]for a description of the corresponding IEEE 802.1 MAC Bridge Draft Standard.) Source routing in bridged local area networks.Source routing is an al- ternative to the spanning tree method for bridged LANs.The idea is to discover a route between two stations A and B wishing to communicate and then to include the route on the header of each packet exchanged between A and B.There are two phases here:
Sec. 5.1 Introduction 385 Station 1 R ~~--..... Bridge 2 Station 2 Figure 5.18 Illustration of bridge learning and FOB updating. Station I sends a packet P to station 2. but the 10 of station 2 does not appear in the FOB of any active port of bridge I (because. for example. station 2 has not transmitted any packet for a long time). Packet P is broadcast into LANs Band C by bridge I. and then it is broadcast into LANs D and E by bridge 2. In the process the 10 of node I is entered in the left-side FOBs of bridges I and 2 (if not already there). Station 2 replies with a packet H. which goes directly to its destination station 1 through bridges 2 and 1. because the ID number of station I appears in the left-side FOBs of these bridges. The method by which the spanning tree is updated in the event of a bridge or LAI\ failure or repair remains to be discussed. There are several algorithms for constructing spanning trees, some of which are discussed in Section 5.2. What is needed here. however, is a distributed algorithm that can work in the face of multiple and unpredictable failures and repairs. A relatively simple possibility is to use a spanning tree of shortest paths from every LAN and bridge to a particular destination (or root). We will see in Section 5.2 that the Bellman-Ford algorithm is particularly well suited for this purpose. There is still, however, an extra difficulty, namely how to get all bridges to agree on the root and what to do when the root itself fails. Such issues involve subtle difficulties, which are unfortunately generic in distributed algorithms dealing with component failures. The difficulty can be resolved by numbering the bridges and by designating as root of the tree the bridge with the smallest ID number. Each bridge keeps track of the smallest bridge ID number that it knows of. A bridge must periodically initiate a spanning tree construction algorithm if it views itself as the root based on its own ID number and the ID numbers of other bridges it is aware of. Also, each bridge ignores messages from bridges other than its current root. To cope with the situation where the root fails, bridges may broadcast periodically special "hello" messages to other bridges. These messages may also carry additional information relating to the spanning tree construction and updating algorithm. (See [Bac88] for a description of the corresponding IEEE 802.1 MAC Bridge Draft Standard.) Source routing in bridged local area networks. Source routing is an alternative to the spanning tree method for bridged LANs. The idea is to discover a route between two stations A and B wishing to communicate and then to include the route on the header of each packet exchanged between A and B. There are two phases here:
386 Routing in Data Networks Chap.5 1.Locating B through the extended LAN.This can be done by broadcasting an exploratory packet from A through the extended LAN(either flooding or a spanning tree can be used for this). 2.Selecting a route out of the many possible that connect A and B.One way of doing this is to send a packet from B to A along each possible loop-free route. The sequence of LANs and bridges is recorded on the packet as it travels along its route.Thus A gets to know all possible routes to B and can select one of these routes using,for example,a shortest path criterion. Note the similarity of source routing with virtual circuit routing;in both cases,all packets of a user pair follow the same path. The main advantage of the spanning tree method is that it does not require any cooperation of the user/stations in the routing algorithm.By contrast,in source routing, the origin station must select a route along which to establish a virtual circuit.Thus the software of the stations must provide for this capability.This is unnecessary in spanning tree routing,where the routing process is transparent to the stations. The main advantage of source routing is that with each packet having its route stamped on it,there is no need for routing table lookup at the bridges.This simplifies packet processing and may result in bridges with higher packet throughput.Another advantage of source routing is that it may use the available network transmission capacity more efficiently.While spanning tree routing uses a single possibly nonshortest path for each origin-destination pair,with source routing,shortest path and multiple-path routing can be used.Figure 5.19 shows an example where spanning tree-based routing is inefficient. We finally mention that both spanning tree and source routing suffer from a common disadvantage.They must often broadcast packets throughout the network either to update FDBs or to establish new connections between user pairs.These broadcasts are needed LAN B LAN B Figure 5.19 Example of inefficient spanning tree routing.The routing paths are good for origin LANs near the bottom 8 LAN of the figure but poor for origin and destination LANs near the top of the figure
386 Routing in Data Networks Chap. 5 1. Locating B through the extended LAN. This can be done by broadcasting an exploratory packet from A through the extended LAN (either flooding or a spanning tree can be used for this). 2. Selecting a route out of the many possible that connect A and B. One way of doing this is to send a packet from B to A along each possible loop-free route. The sequence of LANs and bridges is recorded on the packet as it travels along its route. Thus A gets to know all possible routes to B and can select one of these routes using, for example, a shortest path criterion. Note the similarity of source routing with virtual circuit routing; in both cases, all packets of a user pair follow the same path. The main advantage of the spanning tree method is that it does not require any cooperation of the user/stations in the routing algorithm. By contrast, in source routing, the origin station must select a route along which to establish a virtual circuit. Thus the software of the stations must provide for this capability. This is unnecessary in spanning tree routing, where the routing process is transparent to the stations. The main advantage of source routing is that with each packet having its route stamped on it, there is no need for routing table lookup at the bridges. This simplifies packet processing and may result in bridges with higher packet throughput. Another advantage of source routing is that it may use the available network transmission capacity more efficiently. While spanning tree routing uses a single possibly nonshortest path for each origin-destination pair, with source routing, shortest path and multiple-path routing can be used. Figure 5.19 shows an example where spanning tree-based routing is inefficient. We finally mention that both spanning tree and source routing suffer from a common disadvantage. They must often broadcast packets throughout the network either to update FDBs or to establish new connections between user pairs. These broadcasts are needed Figure 5.19 Example of inefficient spanning tree routing. The routing paths are good for origin LANs near the bottom of the figure but poor for origin and destination LANs near the lOp of the figure
Sec.5.2 Network Algorithms and Shortest Path Routing 387 to allow dynamic relocation of the stations while keeping the bridge hardware simple. They may,however,become a source of congestion. 5.2 NETWORK ALGORITHMS AND SHORTEST PATH ROUTING Routing methods involve the use of a number of simple graph-theoretic problems such as the shortest path problem,discussed in the preceding section.In this section we consider shortest path routing in detail together with related problems of interest.We start by introducing some basic graph-theoretic notions. 5.2.1 Undirected Graphs We define a graph,G=(N,A),to be a finite nonempty set N of nodes and a collection A of pairs of distinct nodes from A.Each pair of nodes in A is called an arc.Several examples of graphs are given in Fig.5.20.The major purpose of the formal definition G=(,A)is to stress that the location of the nodes and the shapes of the arcs in a pic- torial representation are totally irrelevant.If n and n2 are nodes in a graph and (n.n2) is an arc,this arc is said to be incident on n and n2.Some authors define graphs so as to allow arcs to have both ends incident on the same node,but we have intentionally disal- lowed such loops.We have also disallowed multiple arcs between the same pair of nodes. A walk in a graph G is a scquence of nodes (n,n2....,ne)of nodes such that each of the pairs (n,n2),(n2,n3).....(n-1,r)are arcs of G.A walk with no repeated nodes is a path.A walk (n1,...,ne)with n=n,e>3,and no repeated nodes other than n=ne is called a cycle.These definitions are illustrated in Fig.5.21. We say that a graph is connected if for each node i there is a path (i=n.n2..... me=j)to each other node j.Note that the graphs in Fig.5.20(a)and (c)are connected. whereas the graph in Fig.5.20(b)is not connected.We spot an absence of connectivity in a graph by seeing two sets of nodes with no arcs between them.The following lemma captures this insight.The proof is almost immediate and is left as an exercise. (a) (b) (e) N={1,2,3,4 N={1,2,3} N={1} A={(1,2),(2,3),(4,1),(2,4)} A={(1,2)} A={} Figure 5.20 Examples of graphs with a set of nodes A and a set of ares A
Sec. 5.2 Network Algorithms and Shortest Path Routing 387 to allow dynamic relocation of the stations while keeping the bridge hardware simple. They may, however, become a source of congestion. 5.2 NETWORK ALGORITHMS AND SHORTEST PATH ROUTING Routing methods involve the use of a number of simple graph-theoretic problems such as the shortest path problem, discussed in the preceding section. In this section we consider shortest path routing in detail together with related problems of interest. We start by introducing some basic graph-theoretic notions. 5.2.1 Undirected Graphs We define a graph, G = (N, A), to be a finite nonempty set N of nodes and a collection A of pairs of distinct nodes from .lV. Each pair of nodes in A is called an arc. Several examples of graphs are given in Fig. 5.20. The major purpose of the formal definition G = (N, A) is to stress that the location of the nodes and the shapes of the arcs in a pictorial representation are totally irrelevant. If 711 and 712 are nodes in a graph and (nl. /)2) is an arc, this arc is said to be incident on 71 I and 712. Some authors define graphs so as to allow arcs to have both ends incident on the same node, but we have intentionally disallowed such loops. We have also disallowed multiple arcs between the same pair of nodes. A walk in a graph G is a sequence of nodes (711,712, ... , ne) of nodes such that each of the pairs (711,712), (712,713), ..., (ne-1, he) are arcs of G. A walk with no repeated nodes is a path. A walk (711, ... , nt) with 711 = nt, e> 3, and no repeated nodes other than 711 = nt is called a cycle. These definitions are illustrated in Fig. 5.21. We say that a graph is connected if for each node i there is a path (i = 711.712 •.... ne = j) to each other node j. Note that the graphs in Fig. 5.20(a) and (c) are connected, whereas the graph in Fig. 5.20(b) is not connected. We spot an absence of connectivity in a graph by seeing two sets of nodes with no arcs between them. The following lemma captures this insight. The proof is almost immediate and is left as an exercise. 2 (al J.I = {1,2,3,4} A = {(1,2),(2,3),(4,1),(2,4)} 3 2 ,/ 0 (b) J.I = {1,2,3} A = {(1,2)} 1 o (e) J.I = {I} A = { } Figure 5.20 Examples of graphs with a set of nodes /if and a set of arcs A