Chapter 2 - Dynamic Routing in Banyan Networks
Introduction to Dynamic Routing in Banyan Networks
Banyan networks are specifically designed to adapt to changes in network topology and to changes in network resources without requiring administrator intervention. Typical changes in network topology include the addition or removal of servers and data links.
This ability to automatically adapt to the dynamics of a network ensures that if one Banyan server becomes unavailable, it disrupts as few network users and network operations as possible. Two Banyan features, the VINES network layer protocols and the StreetTalk global directory service, work together automatically to make this adaptation possible.
The VINES network layer protocols include a set of network routing procedures that allow other servers on the network to:
Discover the absence or presence of a server or workstation Make appropriate adjustments to changes in the network
The procedures make these adjustments by building and updating routing tables. The routing tables contain the topological information workstations and servers require to communicate.
The information maintained by the StreetTalk global directory service is distributed among many servers in a network. If a particular server becomes temporarily or permanently unavailable, users currently relying on that server for a connection to VINES Files or for access to the network are not necessarily affected.
This chapter provides an overview of dynamic routing and StreetTalk operations and discusses how they work when:
New workstations get on the network Workstations communicate with nodes on other LANs New servers get on the network Current workstations and servers exchange routing updates Workstations and servers adjust to unavailable servers Groups are added and deleted Servers exchange routing updates over transient links The Banyan networking software routes data in heterogeneous environments
How the Banyan Networking Software Performs Dynamic Routing
This section provides an overview of how the Banyan networking software network layer protocols perform dynamic routing.
The VINES network layer protocols are responsible for the following tasks:
Moving packets through the network Establishing the fastest available route between any given source node and its destination node Distributing current network topology information throughout the network
The protocols that make up the Network Layer Protocols are:
VINES Internet Protocol (IP) VINES Routing Update Protocol (RTP) VINES Address Resolution Protocol (ARP) VINES Internet Control Protocol (ICP)
These protocols are defined in the VINES Protocol Definition and discussed later in this chapter as necessary.
Procedures in the VINES network layer protocols perform dynamic system routing. All servers and workstations continually learn the current state of a network and store this information in routing tables. The procedures in VINES IP use these routing tables to make routing decisions when they move VINES IP packets through the network. The routing tables are built when workstations and servers come on the network, and are updated as network changes occur.
Each server and workstation maintains two routing tables: the table of networks and the table of neighbors. Both tables are kept in RAM on the server or workstation.
The following two sections describe the routing tables maintained on servers.
Table of Networks
On servers, the table of networks contains an entry for each known logical network. In this scheme, each server in the network forms a logical network identified by the server's serial number. Figure 2-1 shows this relationship. For more information on logical networks, see the VINES Protocol Definition.
Each entry in the table of networks contains the following information:
Network Number - The serial number of the network server.
Routing Metric - An estimated, round-trip delay time associated with the route that maximum-sized VINES IP packets take to the service node within the specified network. For more information on routing metrics, see Monitoring and Optimizing Servers.
Time-to-Live Timer - A feature that ages out entries for networks that cannot be reached or are disconnected from the network. For more information on this feature, see Monitoring and Optimizing Servers.
Flags - Bit fields that provide information on the state of the routing table entry, such as whether the network is reachable. For more information on this feature, see Monitoring and Optimizing Servers.
Gateway ID - The network ID of the gateway to the destination network.
Preferred Gateway ID - The network ID of the preferred gateway to the destination network.
Table of Neighbors
The table of neighbors contains entries for each of the following:
Servers that are physically connected to a server's communications card (this definition includes the gateway servers of WANs using protocols like TCP/IP). DOS, OS/2, Windows 95, or Windows NT workstations for which the server acts as a routing server. (See "Workstation Routing Tables" later in this chapter for a description of routing servers.)
Each table of neighbors entry contains the following information:
Network Number - The network number in the VINES internet address of the server or workstation. It is the serial number of the logical network's server.
Medium - The medium, such as an Ethernet LAN segment, used to reach the neighbor server or workstation.
LAN Address - If the medium that connects the neighbor is a LAN, the entry contains the node's LAN address.
Neighbor Metric - An estimated, round-trip delay time associated with the medium that maximum-sized VINES IP packets take to the neighbor. This value is specified in 200-millisecond ticks.
Every server keeps full network and neighbor tables.
Example Table of Neighbors on a Server
Figure 2-2 shows a server with two communications cards. One is connected by an Ethernet backbone to other servers while the other is connected to workstations by a Token-Ring LAN.
All of the workstations on the ring are neighbors of the server, and all of the servers on the backbone are neighbors of the server. However the servers on the backbone are not neighbors of the Token-Ring workstations because each LAN uses a different communications card or physical connection.
Workstations do not keep a full table of neighbors and a full table of networks. Workstations track only the following network nodes:
The workstation's routing server Servers and workstations with which the workstation is currently communicating
When a workstation needs to communicate with another workstation or server outside the routing server's logical network, the workstation sends a request to its routing server for information on how to reach the particular destination. Routing servers not only provide workstations with routing information, they also provide workstations with their VINES internet addresses when the workstations come on the network.
Building and Updating Routing Tables
Servers and workstations use the Routing Update Protocol to build and update each other's routing tables. Most of this routing update information is exchanged in the form of routing update packets.
Workstations exchange routing update packets with their routing servers only, unless a workstation is attempting to find a service. In this case, a workstation broadcasts an update packet.
Neighbor servers exchange routing update packets as part of data link broadcasts. When network topology changes need to be propagated throughout the entire network, the servers initially detecting the change include the change in the next routing update packets they broadcast. For more information on the contents of the packet, see the VINES Protocol Definition (Chapter 4 and Chapter 5) or Monitoring and Optimizing Servers.
When neighboring servers that act as routers receive RTP update packets containing news of network changes, they propagate the news to their neighbors on all of their interfaces. This process, shown in Figure 2-3, continues from router to router until the news reaches all the servers in the network.
When a new server comes on the network, the following events occur:
The new server broadcasts the RTP packets to neighbor servers to announce its arrival. A neighboring server acting as a router includes the appropriate entries for the new server in its routing tables. The neighboring server includes an entry for the new server in the next routing update packets that it broadcasts.
This broadcast occurs on all interfaces. Other routers in the network propagate the news of the new server's arrival throughout the network in the same manner. A server propagates news of network changes on all of its network interfaces, including the interface on which it receives the news.
News of other network changes, such as servers going off the network or path changes, is propagated in the same way.
Servers do not perform a network-wide broadcast when network changes occur. Instead, the news of network changes is propagated across the network as a series of controlled data link broadcasts, from router to router.
If no changes have occurred, such as a new server coming on-line, a server sends a null update packet every 90 seconds informing neighbors to keep the server in their routing tables. A null update packet is a packet containing only an RTP header. No information is included about the network. Unlike versions of VINES prior to 5.50, in VINES 5.50 or greater, servers send full update packets only when a new neighbor comes on-line. This routing exchange is the same whether the routing is across a LAN or a WAN.
Workstations create routing table entries for their routing servers and for servers and workstations with which they currently communicate. Entries for networks that are not directly connected are created only when that network is needed. Workstations do not broadcast full topology information; instead, they broadcast null update packets to let neighbors know that they are still on the network. For more information on the format of RTP packets, see the VINES Protocol Definition (Chapter 4 and Chapter 5).
The following sections describe routing updates:
Between neighbors on LANs Between neighbors on WANs Over unrestricted transient links Over restricted and secure links
Between Neighbors on LANs
Neighbor servers on LANs regularly exchange routing update packets. If a neighbor has no activity after a certain period, its entry is automatically aged and the following events occur:
The entry for the neighbor is removed from the table of neighbors. Figure 2-4 shows this process. If the neighbor acted as a router, the next action depends on whether or not backup routes are available. (Entries for backup routers in the table of neighbors indicate the availability of backup routes.) - If no backup paths are available to the destinations reached through the router, the entries for the destinations in the table of networks are marked as unreachable and removed.
- If backup paths are available, the path with the lowest cost (that is, the entry for the neighbor router associated with the lowest cost) is activated after the entry for the unavailable router is removed from the table of neighbors.
Between Neighbors on WANs
Routing packet exchange for neighbor servers on WANs is the same as for neighbors on LANs. With neighbors on WANs, however, entries from the routing tables can also be removed by any of the following actions:
The serial line is either shut down from the server console or is de-assigned. Either the X.25 permanent virtual circuit is cleared, or the X.25 line is de-assigned. When tunneling VINES IP packets through foreign protocols such as TCP/IP, the entry for the neighbor is removed using the protocol configuration program.
Over Unrestricted Transient Links
Merging two Banyan networks over unrestricted, transient links such as a dial-up HDLC link, is handled by the RTP as though many new servers suddenly came on line. The servers in both networks update their routing tables by creating entries in the table of networks for each server in the other network.
When networks merge over unrestricted links, the following events occur:
The two servers that provide the physical connection between the networks exchange routing update packets. These packets contain entries for each server in their respective networks and metrics for reaching them. When one server receives the routing update packet from the other, the receiving server updates its routing tables. The receiving server then broadcasts routing updates to neighbors in its own network. The neighbors, in turn, update their routing tables and broadcast to their neighbors, and so on until all the servers in each network receive the news of the availability of new servers.
Figure 2-5 shows the exchange of RTP packets over a transient link.
Performance on unrestricted transient links might slow down until this burst of activity ends. The amount of time it takes for the activity to dissipate depends on the number of servers, StreetTalk groups, users, and so forth in the two merging networks. Allow at least several minutes for a burst of activity to dissipate.
Other network traffic, such as StreetTalk updates and mail, that was waiting for transmission between the two networks is also exchanged across the transient link when the merge occurs.
Over Restricted and Secure Links
Servers connected by restricted or secure links exchange routing table information, but other Banyan traffic is limited, having the following implications:
Intelligent Messaging must be force-routed across restricted links. The To field in the mail message must specify the names of the servers at the receiving end on the restricted link. Only those file services servers on the restricted link are available throughout the network.
For more information on secure links, see the section on levels of access in Managing VINES Security.
How Workstations and Servers Adjust to Unavailable Servers
When a server goes off the network, its neighbor servers on the LANs flush the entries for the server from their table of networks and table of neighbors. The neighbor servers acting as routers then propagate news of the server's departure in the next routing update packets the servers broadcast.
Workstations flush entries for servers and workstations with which they are communicating if these destinations become unreachable.
When a server goes off the network, the following events occur:
All the resources on the server become unavailable. All the users whose StreetTalk names are maintained on the server can no longer access network resources. If the server is a router, all of the server's neighbors are cut off from the rest of the network unless backup routers are available. Therefore, a server can continue to act as a router as long as the kernel is running. For example, if the services on a server stop or are stopped by an administrator but the kernel stays running, the server still acts as a router. All the workstations that received internet addresses from the server become orphan workstations. An orphan workstation is one that loses its routing server. Remember that a server can still act as a routing server as long as the kernel is running. The user must reboot the workstation and load BAN again to pick up another routing server, if one is available. If the workstation loses its routing server but does not reboot, the workstation can still use the routing server when it returns to the network. For example, if a server temporarily goes off the network and then quickly returns, a workstation connected to the server does not have to reboot. In this situation, allow a few minutes to elapse so that the workstation and server can exchange routing update packets. Routing update packets refresh the neighbor entry for the routing server in the workstation's list of neighbors.
How New Workstations Connect to the Network
DOS and OS/2 clients activate VINES software when a user enters the BAN command. Windows 95 and Windows NT clients activate VINES software automatically during login.
When VINES software is activated, the workstation performs the following actions:
Finds a routing server Announces the workstation's arrival to neighbors Establishes a session with a VINES Files service
After these actions are performed, the workstation periodically informs its neighbors of its presence on the LAN. The workstation also requests routing updates from its routing server when it has to communicate with servers that are off the LAN.
Workstations use the Address Resolution Protocol (ARP) to find routing servers. Workstations need routing servers to perform the following activities:
Obtain an internet address when necessary. Obtain routing updates when workstations need to communicate outside their logical network. Act as references for network nodes off the LAN that want to talk to the workstation. If a routing server goes down, these nodes cannot send data to the workstation once the entry for the routing server is removed from their table of networks. The amount of time it takes to remove the entry depends on many factors, such as throughput capacity of the data links between these nodes and the routing server and the number of intermediate hops.
Note that a workstation does not always use its routing server to route off-LAN traffic. Any neighbor server may route off-LAN traffic from the workstation if it is the least costly route.
If the routing server temporarily goes off the network, a workstation does not have to reboot to pick up a new routing server. When the routing server returns to the network, the workstation user should allow for a short period of time for the workstation's routing tables to become updated before attempting to communicate off the logical network.
Announcing Their Arrival to Neighbors
The workstation uses the RTP to announce its arrival to neighbors. Neighbor servers add the new workstation to their table of neighbors. Neighbor workstations ignore the RTP broadcasts.
The VINES Files connection is established prior to user login. Once the workstation receives a VINES internet address, the workstation software is ready to establish a session with a drive Z. Drive Z can be any VINES Files that matches the software version of the user's Banyan workstation software. Because drive Z is logically mapped to VINES Files, VINES Files is not tied to a particular server location.
The version of the Banyan networking software on the user's Banyan workstation does not have to match the version on the user's routing server. The user's VINES Files server, however, must run a version of the Banyan networking software that matches the user's workstation software. (Remember that one server can act as a user's routing server, and another server can act as a user's VINES Files server.)
To establish a session with a VINES Files server, the redirector in the workstation issues a zero hop broadcast to all neighbor servers. The broadcast messages indicate what version of the Banyan networking software the redirector is looking for. The version must be one that matches the workstation version in the following ways:
Version number (for example, 8.50) Language (English, French, German, and so on) Workstation type (DOS, OS/2) Note: For Windows NT workstations, the version number can be 5.30 or greater; it does not have to be an exact match.
The broadcast issued by the redirector travels over LANs only. The server acting as the router for the LAN on which the workstation resides filters the VINES Files broadcasts so that they do not travel over any of the following:
Serial lines TCP/IP server-to-server connections SNA server-to-server connections Networks using IPX/SPX protocols
If a server with the appropriate version responds, the redirector establishes a connection with that VINES Files service. Figure 2-6 shows this process.
If more than one neighbor server has the appropriate version, the redirector chooses the first one that responds. The factors that determine which server responds first depend on the relative processor speeds of the servers and the amount of network traffic between the servers and the workstation.
If no neighbor server with the appropriate version responds, the redirector issues another broadcast to all servers one hop beyond and repeats the process of choosing the fastest server with the appropriate version of the Banyan networking software.
If a server with the appropriate version responds, the redirector establishes a connection with that VINES Files service. If more than one server has the appropriate version, the redirector chooses the first one that responds.
If a server with the appropriate version does not respond, this time the redirector notifies the user that an appropriate VINES Files version could not be found and automatically invokes the NEWREV program.
Note: For DOS and OS/2 workstations only, if a workstation user issues the BAN command with the /NC switch either at the DOS prompt or in the AUTOEXEC.BAT file, the NEWREV program is not automatically invoked. Instead, a 25th line message appears informing the user to run NEWREV.
If the redirector loses its connection to VINES Files, it repeats this algorithm. Losing a VINES Files connection can result from network failures, server crashes, and so forth.
How Workstations Communicate with Other Nodes
Workstations track only their routing server and other workstations and servers with which they are currently communicating. Therefore, workstations must know quickly how to reach new networks and workstations with which they want to communicate.
When workstations need to know how to reach new networks, the following events occur:
The Banyan networking software in the workstation requests a routing update from its routing server. The routing server supplies the workstation with the routing information it needs to reach the destination, providing a routing redirect if necessary.
How New Servers Connect to the Network
When a new Banyan server comes on to the network, the following events occur:
The server broadcasts routing updates to and receives routing updates from its neighbors. Neighbors receive the broadcast and include the server in their routing tables and build the server's routing tables. Neighbor routers propagate news of the server's arrival. The new server issues StreetTalk broadcasts and asks responding neighbors for a full StreetTalk update. If the server was recently on the network, the server already knows of the existing StreetTalk databases. Therefore, the server broadcasts only to let its neighbors know it has returned.
The StreetTalk database on a server contains the following information:
Information on all the items in the groups and organizations maintained on the server The names of groups and organizations maintained on other servers The names of servers and their VINES internet addresses
When the StreetTalk service on a server receives a request for information on an item in a group maintained on another server, the service redirects the request to the server where the group is maintained.
The StreetTalk services in the network maintain a collective database through network broadcasts. If a server stops, only users and resources whose names are maintained on the server (and the resources themselves) are affected.
A StreetTalk database must be built from scratch by neighbor servers when a server undergoes a full installation or an upgrade. It is updated by other servers when changes occur, such as when new groups and servers are added to the network.
