378 Routing in Data Networks Chap.5 The routing information includes the node sequence of the routing path,and some flags in- dicating circuit class.When a needle enters a TYMNET II node,its contents are checked. If the circuit terminates at this node,it is assigned to the port connected with the appro- priate external site.Otherwise,the next node on the route is checked.If it is unknown (because of a recent link failure or some other error),the circuit is zapped back to its ori- gin.Otherwise,the routing tables are updated and the needle is passed to the next node. The TYMNET algorithm is well thought out and has performed well over the years.Several of its ideas were implemented in the Codex network,which is a similarly structured network (see Section 5.8).The Codex algorithm,however,is distributed and more sophisticated.A potential concern with the TYMNET algorithm is its vulnerability to failure of the supervisor node.In TYMNET,this is handled by using backup supervisor nodes.A distributed alternative,used in the Codex network,is to broadcast all link lengths to all nodes (as in the ARPANET),and to let each node choose the routing path for each circuit originating at that node.This path may be established by updating the routing tables of the nodes on the path,just as in TYMNET.Another possibility is to let the originating node include the routing path on each packet.This makes the packets longer but may save substantially in processing time at the nodes,when special switching hardware are used.For high-speed networks where the packet volume handled by the nodes is very large,it is essential to use such special hardware and to trade communication efficiency for reduced computation. Routing in SNA.Routing in IBM's SNA is somewhat unusual in that the method for choosing routes is left partially to the user.SNA provides instead a frame- work within which a number of routing algorithm choices can be made.Specifically,for every origin-destination pair,SNA provides several paths along which virtual circuits can be built.The rule for assignment of virtual circuits to paths is subject to certain restrictions but is otherwise left unspecified.The preceding oversimplified description is couched in the general terminology of paths and virtual circuits used in this book.SNA uses a different terminology,which we now review. The architecture of SNA does not fully conform to the OSI seven-layer architecture used as our primary model.The closest counterpart in SNA of the OSI network layer, called the path control layer,provides virtual circuit service to the immediately higher layer,called the transmission control layer.The path control layer has three functions: transmission group control,explicit route control,and virtual route control.The first fits most appropriately in the data link control layer of the OSI model,whereas the second and third correspond to the routing and flow control functions,respectively,of the network layer in the OSI model. A transmission group in SNA terminology is a set of one or more physical commu- nication lines between two neighboring nodes of the network.The transmission group control function makes the transmission group appear to higher layers as a single physical link.There may be more than one transmission group connecting a pair of nodes.The protocol places incoming packets on a queue,sends them out on the next available physi- cal link,and sequences them if they arrive out of order.Resequencing of packets is done at every node,unlike the ARPANET,which resequences only at the destination node
378 Routing in Data Networks Chap. 5 The routing infonnation includes the node sequence of the routing path, and some flags indicating circuit class. When a needle enters a TYMNET II node, its contents are checked. If the circuit tenninates at this node, it is assigned to the port connected with the appropriate external site. Otherwise, the next node on the route is checked. If it is unknown (because of a recent link failure or some other error), the circuit is zapped back to its origin. Otherwise, the routing tables are updated and the needle is passed to the next node. The TYMNET algorithm is well thought out and has perfonned well over the years. Several of its ideas were implemented in the Codex network, which is a similarly structured network (see Section 5.8). The Codex algorithm, however, is distributed and more sophisticated. A potential concern with the TYMNET algorithm is its vulnerability to failure of the supervisor node. In TYMNET, this is handled by using backup supervisor nodes. A distributed alternative, used in the Codex network, is to broadcast all link lengths to all nodes (as in the ARPANET), and to let each node choose the routing path for each circuit originating at that node. This path may be established by updating the routing tables of the nodes on the path, just as in TYMNET. Another possibility is to let the originating node include the routing path on each packet. This makes the packets longer but may save substantially in processing time at the nodes, when special switching hardware are used. For high-speed networks where the packet volume handled by the nodes is very large, it is essential to use such special hardware and to trade communication efficiency for reduced computation. Routing in SNA. Routing in IBM's SNA is somewhat unusual in that the method for choosing routes is left partially to the user. SNA provides instead a framework within which a number of routing algorithm choices can be made. Specifically, for every origin-destination pair, SNA provides several paths along which virtual circuits can be built. The rule for assignment of virtual circuits to paths is subject to certain restrictions but is otherwise left unspecified. The preceding oversimplified description is couched in the general tenninology of paths and virtual circuits used in this book. SNA uses a different tenninology, which we now review. The architecture of SNA does not fully confonn to the OSI seven-layer architecture used as our primary model. The closest counterpart in SNA of the OSI network layer, called the path control layer, provides virtual circuit service to the immediately higher layer, called the transmission control layer. The path control layer has three functions: transmission group control, explicit route control, and virtual route control. The first fits most appropriately in the data link control layer of the OSI model, whereas the second and third correspond to the routing and flow control functions, respectively, of the network layer in the OSI model. A transmission group in SNA tenninology is a set of one or more physical communication lines between two neighboring nodes of the network. The transmission group control function makes the transmission group appear to higher layers as a single physical link. There may be more than one transmission group connecting a pair of nodes. The protocol places incoming packets on a queue, sends them out on the next available physical link, and sequences them if they arrive out of order. Resequencing of packets is done at every node, unlike the ARPANET, which resequences only at the destination node
Sec.5.1 Introduction 379 An explicit route in SNA terminology is what we have been referring to as a path within a subnet.Thus,an explicit route is simply a sequence of transmission groups providing a physical path between an origin and a destination node.There are several explicit routes provided (up to eight in SNA 4.2)for each origin-destination pair,which can be modified only under supervisory control.The method for choosing these explicit routes is left to the network manager.Each node stores the next node for each explicit route in its routing tables,and each packet carries an explicit route number.Therefore, when a packet arrives at a node,the next node on the packet's path (if any)is determined by a simple table lookup. A virtual route in SNA terminology is essentially what we have been calling a virtual circuit.A user pair conversation (or session)uses only one virtual route.However. a virtual route can carry multiple sessions.Each virtual route belongs to a priority (or service)class.Each transmission group can serve up to three service classes,each with up to eight virtual routes,for a maximum of 24 virtual routes.When a user requests a session through a subnet entry node,a service class is specified on the basis of which the entry node will attempt to establish the session over one of its virtual routes.If all the communication lines of a transmission group fail,every session using that transmission group must be rerouted.If no alternative virtual route can be found,the session is aborted. When new transmission groups are established,all nodes are notified via special control packets,so each node has a copy of the network topology and knows which explicit routes are available and which are not. Routing in circuit switching networks.Routing in circuit switching net- works is conceptually not much different than routing in virtual circuit networks.In both cases a path is established at the time the circuit is set up,and all subsequent communi- cation follows that path.In both cases the circuit will be blocked when the number of existing circuits on some link of the path reaches a certain threshold,although the choice of threshold may be based on different considerations in each case. Despite these similarities,in practice,telephone networks have used quite different routing methods than virtual circuit networks.A common routing method in circuit switching networks,known as hierarchical routing,has been to use a fixed first-choice route,and to provide for one or more alternative routes,to be tried in a hierarchical order,for the case where the first-choice route is blocked.However,the differences in routing philosophy between circuit switching and virtual circuit networks have narrowed recently.In particular,there have been implementations of adaptive routing in telephone networks,whereby the path used by a call is chosen from several alternative paths on the basis of a measure of congestion (e.g.,the number of circuits these paths carry).We refer to [Ash90].[KeC90],[Kri90],[ReC90],and [WaO90]for detailed descriptions and discussion of such implementations. 5.1.3 Interconnected Network Routing:An Overview As networks started to proliferate,it became necessary to interconnect them using various interface devices.In the case of wide-area networks,the interfaces are called gateways
Sec. 5.1 Introduction 379 An explicit route in SNA tenninology is what we have been referring to as a path within a subnet. Thus, an explicit route is simply a sequence of transmission groups providing a physical path between an origin and a destination node. There are several explicit routes provided (up to eight in SNA 4.2) for each origin-destination pair, which can be modified only under supervisory control. The method for choosing these explicit routes is left to the network manager. Each node stores the next node for each explicit route in its routing tables, and each packet carries an explicit route number. Therefore, when a packet arrives at a node, the next node on the packet's path (if any) is determined by a simple table lookup. A virtual route in SNA tenninology is essentially what we have been calling a virtual circuit. A user pair conversation (or session) uses only one virtual route. However, a virtual route can carry multiple sessions. Each virtual route belongs to a priority (or service) class. Each transmission group can serve up to three service classes, each with up to eight virtual routes, for a maximum of 24 virtual routes. When a user requests a session through a subnet entry node, a service class is specified on the basis of which the entry node will attempt to establish the session over one of its virtual routes. If all the communication lines of a transmission group fail, every session using that transmission group must be rerouted. If no alternative virtual route can be found, the session is aborted. When new transmission groups are established, all nodes are notified via special control packets, so each node has a copy of the network topology and knows which explicit routes are available and which are not. Routing in circuit switching networks. Routing in circuit switching networks is conceptually not much different than routing in virtual circuit networks. In both cases a path is established at the time the circuit is set up, and all subsequent communication follows that path. In both cases the circuit will be blocked when the number of existing circuits on some link of the path reaches a certain threshold, although the choice of threshold may be based on different considerations in each case. Despite these similarities, in practice, telephone networks have used quite different routing methods than virtual circuit networks. A common routing method in circuit switching networks, known as hierarchical routing, has been to use a fixed first-choice route, and to provide for one or more alternative routes, to be tried in a hierarchical order, for the case where the first-choice route is blocked. However, the differences in routing philosophy between circuit switching and virtual circuit networks have narrowed recently. In particular, there have been implementations of adaptive routing in telephone networks, whereby the path used by a call is chosen from several alternative paths on the basis of a measure of congestion (e.g., the number of circuits these paths carry). We refer to [Ash90], [KeC90], [Kri90], [ReC90], and [Wa090] for detailed descriptions and discussion of such implementations. 5.1.3 Interconnected Network Routing: An Overview As networks started to proliferate, it became necessary to interconnect them using various interface devices. In the case of wide-area networks, the interfaces are called gateways
380 Routing in Data Networks Chap.5 and usually perform fairly sophisticated network layer tasks,including routing.Gateways typically operate at the internet sublayer of the network layer.A number of engineering and economic factors,to be discussed shortly,motivated the interconnection of local area networks (LANs)at the MAC sublayer.The devices used for interconnection,known as bridges,perform a primitive form of routing.LANs can also be connected with each other or with wide-area networks using more sophisticated devices called routers. These provide fairly advanced routing functions at the network layer,possibly including adaptive and multiple-path routing.In this section we survey various routing schemes for interconnected networks,with a special emphasis on bridged LANs. Conceptually,one may view an interconnected network of subnetworks as a single large network,where the interfaces (gateways,bridges,or routers)are additional nodes, each connected to two or more of the constituent subnetworks (see Fig.5.14).Routing based on this conceptual model is called nonhierarchical and is similar to routing in a wide area network. It is also possible to adopt a coarser-grain view of an interconnected network of subnetworks,whereby each subnetwork is considered to be a single node connected to interface nodes.Routing based on this model is called hierarchical,and consists of two levels.At the lower level,there is a separate routing algorithm for each subnetwork that handles local subnetwork traffic and also directs internetwork traffic to the subnetwork's interfaces with other subnetworks.At the higher level,there is a routing algorithm that determines the sequence of subnetworks and interface nodes that each internetwork packet must follow (see Fig.5.15).Basically,the low-level algorithms handle"local" packets,and the high-level algorithm delivers "long-distance"packets to the appropriate low-level algorithm.An example of a hierarchical network is the Internet discussed in Section 2.8.4.Hierarchical routing is generally recommended for large internetworks; for example,telephone networks are typically organized hierarchically.We contrast the two approaches to internetworking by means of an example. Example 5.3 Hierarchical versus Nonhierarchical Routing Consider a country with several cities each having its own data network,and suppose that the city networks are connected into a national network using gateways.Each packet must have an internetwork destination address,consisting of a city address (or city ID number) and a local address (an ID number for the destination node within the destination city). Assume for concreteness that we want to use an ARPANET-like algorithm,where each 9998 Bridge T.R Ethernet c Bridge Bridge Bridge Figure 5.14 Conceptual view of an interconnected network of subnetworks.In Bridge a nonhierarchical approach to routing the internetwork is viewed as a single large Ethernet Ethernet network
380 Routing in Data Networks Chap. 5 and usually perfonn fairly sophisticated network layer tasks, including routing. Gateways typically operate at the internet sublayer of the network layer. A number of engineering and economic factors, to be discussed shortly, motivated the interconnection of local area networks (LANs) at the MAC sublayer. The devices used for interconnection, known as hridges, perfonn a primitive fonn of routing. LANs can also be connected with each other or with wide-area networks using more sophisticated devices called routers. These provide fairly advanced routing functions at the network layer, possibly including adaptive and multiple-path routing. In this section we survey various routing schemes for interconnected networks, with a special emphasis on bridged LANs. Conceptually, one may view an interconnected network of subnetworks as a single large network, where the interfaces (gateways, bridges, or routers) are additional nodes, each connected to two or more of the constituent subnetworks (see Fig. 5.14). Routing based on this conceptual model is called nonhierarchical and is similar to routing in a wide area network. It is also possible to adopt a coarser-grain view of an interconnected network of subnetworks, whereby each subnetwork is considered to be a single node connected to interface nodes. Routing based on this model is called hierarchical, and consists of two levels. At the lower level, there is a separate routing algorithm for each subnetwork that handles local subnetwork traffic and also directs internetwork traffic to the subnetwork's interfaces with other subnetworks. At the higher level, there is a routing algorithm that detennines the sequence of subnetworks and interface nodes that each internetwork packet must follow (see Fig. 5.15). Basically, the low-level algorithms handle "local" packets, and the high-level algorithm delivers "long-distance" packets to the appropriate low-level algorithm. An example of a hierarchical network is the Internet discussed in Section 2.8.4. Hierarchical routing is generally recommended for large internetworks; for example, telephone networks are typically organized hierarchically. We contrast the two approaches to internetworking by means of an example. Example 5.3 Hierarchical versus Nonhierarchical Routing Consider a country with several cities each having its own data network, and suppose that the city networks are connected into a national network using gateways. Each packet must have an internetwork destination address, consisting of a city address (or city ID number) and a local address (an ID number for the destination node within the destination city). Assume for concreteness that we want to use an ARPANET-like algorithm, where each Figure 5.14 Conceptual view of an interconnected network of subnetworks. In a nonhierarchical approach to routing the internetwork is viewed as a single large network
Sec.5.1 Introduction 381 9999 Ethernet Router Router Gateway WAN WAN Gateway WAN Gateway Gateway Higher-level network Nodes:gateways and routers Hierarchical internetwork Links (multiaccess):WANs and LANs Figure 5.15 Conceptual view of hierarchical routing in an interconnceted network of subnetworks.There is a lower-level algorithm that handles routing within cach subnet- work and a higher-level algorithm that handles routing between subnetworks. node has a unique entry in its routing tables for every destination (the next outgoing link on its shortest path to the destination). In a nonhierachical routing approach.there is no distinction between the city networks: each node of each city must have a separate entry in its routing tables for every node in every other city.Thus the size of the routing tables is equal to the total number of nodes in the national network.Furthermore.a shortest path calculation to update the routing tables must be performed for the entire national network.Thus we see the main drawbacks of the nonhierarchical approach:the size of the routing tables and the calculations to update them may become excessive. In a hierarchical approach.there is a lower-level (locul)ARPANET-like routing algo- rithm within each city.and a higher-level ARPANET-like routing algorithm between cities. The local routing algorithm of a city operates only at the nodes of that city.Every node of a city has a routing table entry for every node of the same city and a routing table entry for every other city.The higher-level algorithm provides for routing between cities and operates only at the gateways.Each gateway has a routing table entry for every destination city.The latter entry is the next city network to which an internetwork packet must be routed on its way to its destination. To see how this algorithm works.consider a packet generated at a node of some city A and destined for a node of a different city.The origin node checks the packet's address. consults its routing table entry for the packet's destination city.and sends the packet on the corresponding outgoing link.Each node of city .4 subsequently visited hy the packet does the same,until the packet arrives at an appropriate gateway.At this point.the higher-level routing algorithm takes over and determines (based on the gateway's routing table)the next city network within which the packet will travel.The packet is then guided by the latter network's local routing algorithm,and the process is repeated until the packet arrives at the destination city's network.Then the packet is routed to its destination node by the local routing algorithm of the destination city
Sec. 5.1 Introduction 381 Hierarchical internetwork Higher-level network Nodes: gateways and routers Links (multiaccess): WANs and LANs Figure 5.15 Conceptual view of hierarchical routing in an interconnected nctwork of subnetworks. Therc is a lower-level algorithm that handles routing within each subnctwork and a higher-level algorithm that handles routing betwecn suhnctworks. node has a unique entry in its routing tables for every destination (the next outgoing link on its shortest path to the destination). In a nonhierachical routing approach, there is no distinction between the city networks: each node of each city must have a separate entry in its routing tables for every node in every other city. Thus the size of the routing tables is equal to the total number of nodes in the national network. Furthermore, a shortest path calculation to update the routing tables must be performed for the entire national network. Thus we see the main drawbacks of the nonhierarchical approach: the size of the routing tables and the calculations to update them may become excessive. In a hierarchical approach. there is a lower-level (local) ARPA:--JET-like routing algorithm within each city, and a higher-level ARPANET-like routing algorithm between cities. The local routing algorithm of a city operates only at the nodes of that city. Every node of a city has a routing table entry for every node of the same city and a routing table entry for every other city. The higher-level algorithm provides for routing between cities and operates only at the gateways. Each gateway has a routing table entry for every destination city. The latter entry is the next city network to which an internetwork packet must be routed on its way to its destination. To see how this algorithm works. consider a packet generated at a node of some city A and destined for a node of a different city. The origin node checks the packet's address. consults its routing table entry for the packet's destination city. and sends the packet on the corresponding outgoing link. Each node of city A subsequently visited by the packet does the same, until the packet arrives at an appropriate gateway. At this point. the higher-level routing algorithm takes over and determines (based on the gateway's routing table) the next city network within which the packet will travel. The packet is then guided by the latter network's local routing algorithm, and the process is repeated until the packet arrives at the destination city's network. Then the packet is routed to its destination node by the local routing algorithm of the destination city
382 Routing in Data Networks Chap.5 The routing tables of a city network algorithm may be generated or updated using an adaptive shortest-path algorithm such as the ARPANET SPF algorithm.To do this,the nodes of the city network must have a destination gateway for every other city (the gateway connected to the city network to which packets destined for the other city will be guided by the local routing algorithm).This information must be provided by the higher-level algorithm that operates at the gateways.The higher-level algorithm may itself be static or adaptive,adjusting its intercity routes to temporary congestion patterns. It can be seen from the preceding example that in the hierarchical approach,the size of the routing tables and the calculations to update them are considerably reduced over the nonhierarchical approach.In fact,the hierarchical approach may be recommended for a single large network (no internetworking)to reduce the routing algorithm's overhead and storage.The disadvantage of the hierarchical approach is that it may not result in routing that is optimal for the entire internetwork with respect to a shortest path or some other criterion. Note that hierarchical networks may be organized in more than two levels.For example.consider an international network interconnecting several national networks. In a three-level hierarchy,there could be a routing algorithm between countries at the highest level,a routing algorithm between cities of each country at the middle level,and a routing algorithm within each city at the lowest level. Bridged local area networks.As we discussed in Chapter 4,the performance of a local area network tends to degrade as its number of users increases.In the case of Ethernet-based LANs the performance also degrades as the ratio of propagation delay to transmission capacity increases.A remedy is to connect several LANs so that a large geographical area with many users can be covered without a severe performance penalty. Routing for interconnected LANs has a special character because LANs operate in a "promiscuous mode,"whereby all nodes,including the interface nodes connected to a LAN,hear all the traffic broadcast within the LAN.Furthermore,in a LAN internetwork, interface nodes must be fast and inexpensive,consistent with the characteristics of the LANs connected.This has motivated the use of simple,fast,and relatively inexpensive bridges.A bridge listens to all the packets transmitted within two or more LANs through connections known as porrs.It also selectively relays some packets from one LAN to another.In this way,packets can travel from one user to another,going through a sequence of LANs and bridges. An important characteristic of bridges is that they connect LANs at the MAC sublayer.The resulting internetwork is,by necessity,nonhierarchical;it may be viewed as a single network,referred to as the extended LAN.To alleviate the disadvantages of nonhierarchical routing mentioned earlier,bridges use some special routing techniques, the two most prominent of which are known as spanning tree routing and source routing. Both of these schemes assume that each station in the extended LAN has a unique ID number known through a directory that can be accessed by all stations.A station's ID number need not provide information regarding the LAN to which the station is connected.Also,the location of a station is not assumed known,thus allowing stations to be turned on and off and to be moved from one LAN to another at will.To appreciate
382 Routing in Data Networks Chap. 5 The routing tables of a city network algorithm may be generated or updated using an adaptive shortest-path algorithm such as the ARPANET SPF algorithm. To do this, the nodes of the city network must have a destination gateway for every other city (the gateway connected to the city network to which packets destined for the other city will be guided by the local routing algorithm). This infonnation must be provided by the higher-level algorithm that operates at the gateways. The higher-level algorithm may itself be static or adaptive, adjusting its intercity routes to temporary congestion patterns. It can be seen from the preceding example that in the hierarchical approach, the size of the routing tables and the calculations to update them are considerably reduced over the nonhierarchical approach. In fact, the hierarchical approach may be recommended for a single large network (no internetworking) to reduce the routing algorithm's overhead and storage. The disadvantage of the hierarchical approach is that it may not result in routing that is optimal for the entire internetwork with respect to a shortest path or some other criterion. Note that hierarchical networks may be organized in more than two levels. For example, consider an international network interconnecting several national networks. In a three-level hierarchy, there could be a routing algorithm between countries at the highest level, a routing algorithm between cities of each country at the middle level, and a routing algorithm within each city at the lowest level. Bridged local area networks. As we discussed in Chapter 4, the performance of a local area network tends to degrade as its number of users increases. In the case of Ethernet-based LANs the performance also degrades as the ratio of propagation delay to transmission capacity increases. A remedy is to connect several LANs so that a large geographical area with many users can be covered without a severe performance penalty. Routing for interconnected LANs has a special character because LANs operate in a "promiscuous mode," whereby all nodes, including the interface nodes connected to a LAN, hear all the traffic broadcast within the LAN. Furthermore, in a LAN internetwork, interface nodes must be fast and inexpensive, consistent with the characteristics of the LANs connected. This has motivated the use of simple, fast, and relatively inexpensive bridges. A bridge listens to all the packets transmitted within two or more LANs through connections known as ports. It also selectively relays some packets from one LAN to another. In this way, packets can travel from one user to another, going through a sequence of LANs and bridges. An important characteristic of bridges is that they connect LANs at the MAC sublayer. The resulting internetwork is, by necessity, nonhierarchical; it may be viewed as a single network, referred to as the extended LAN. To alleviate the disadvantages of nonhierarchical routing mentioned earlier, bridges use some special routing techniques, the two most prominent of which are known as spanning tree routing and source routing. Both of these schemes assume that each station in the extended LAN has a unique ID number known through a directory that can be accessed by all stations. A station's ID number need not provide illformation regarding the LAN to which the station is connected. Also, the location of a station is not assumed known, thus allowing stations to be turned on and off and to be moved from one LAN to another at will. To appreciate