Chapter 5 - VINES Sequenced Routing Update Protocol (continued)
Routers inform client nodes and other routers of better routes with redirect packets. The destination VINES internet address is always set to the VINES broadcast address. The destination data link address is set to the data link address of the neighbor.
Redirect packets contain topological entries that allow nodes to select the best paths to destinations. When a router should not forward packets between two nodes, it sends a redirect packet to the originator of the forwarded packet, called the last forwarding node. The better path is through a preferred gateway, which is the appropriate gateway for communications between the destination and the last forwarding node.
Routers generate redirect packets if they forward non-broadcast packets on the same interface where the packets were received. Routers send redirect packets directly to the last forwarding node, which is either the source of the packet or a router of the packet.
The destination and the preferred gateway can be the same node. This occurs when two neighbor nodes attempt to communicate with each other through a third neighbor node.
In the sequenced RTP implementation, redirect packets help neighbor routers and client nodes communicate as follows:
![]()
Because a client node only stores a neighbor entry for its routing server, the routing information in redirect packets help a client node communicate directly with neighbor routers that are not its routing server. ![]()
Because a router only stores neighbor entries for client nodes for which it is a routing server, a router needs a mechanism to create transient neighbor entries for client nodes.
For a client node to communicate with a neighbor router that is not its routing server, the routing server sends redirect packets to both the client node and the other router, informing them that they can communicate directly.
Routers do not send redirect packets using different Token-Ring bridges to reach the preferred gateway and the last forwarding node.
In sequenced redirect packets, the redirect message follows the RTP header. Unlike sequenced request and update packets, no header follows the RTP header that is specific to sequenced redirect packets. Figure 5-17 shows a sample sequenced redirect packet.
The redirect message contains several fields of information. Figure 5-18 shows the format of a sample redirect message.
Figure 5-19 shows the network environment where the redirect message in Figure 5-18 is sent. In Figure 5-19, a client node initially attempts to communicate with a server, Server B, through another server, Server A. Server A informs the client node to communicate directly with Server B. Server B is both the destination and the preferred gateway.
The message in Figure 5-18 is sent by a router to inform the client node to communicate directly with another router. The other router is both the destination and the preferred gateway.
Table 5-6 describes the fields in the redirect message.
See "Tuples" earlier in this chapter for more information on the Destination and Preferred Gateway flags.
See "Implementation Overview" earlier in this chapter for more information on the Destination and Preferred Gateway sequence numbers.
Rules for Generating and Processing Sequenced Redirect Packets
The rules for generating and processing sequenced redirect packets are the same as the rules for generating routing redirect packets in the non-sequenced RTP implementation, except for some additional checks that routers perform. A received sequenced redirect packet is discarded if any of the following checks fail:
![]()
The network entry for the destination must exist in the network table. ![]()
An existing network entry for the destination must be valid (that is, the network must be reachable and not in suppression). ![]()
The router that sent the redirect packet must be the current gateway for reaching the destination.
See "Rules for Generating and Processing Routing Redirect Packets" in Chapter 4 for more information.
Redirect Compatibility with Non-Sequenced RTP
Routers that support sequenced RTP generate a non-sequenced routing redirect packet only if nodes that support non-sequenced RTP reside on the same media where a sequenced redirect packet has been sent. In other words, routers that support sequenced RTP send a sequenced redirect packet first and then a non-sequenced routing redirect packet.
Processing Sequenced Redirect Packets that Contain Source Routes
The rules for processing sequenced redirect packets containing source routes are the same as the rules for processing routing redirect packets containing source routes in the non-sequenced RTP implementation. See "Processing Redirect Packets that Contain Source Routes" in Chapter 4 for more information.
Processing Backup Source Routes
When multiple source routes exist, client nodes and routers always use the one with the lowest routing metric. However, if the source route with the lowest cost becomes unavailable, a transition to a backup source route must take place.
To ensure a smooth transition to a backup source route, sequenced RTP uses the nbslrtimer field in the neighbor table. Each time a client node or router processes the best source route from the receipt of a sequenced update or response, the timer is refreshed to one 90-second interval. If a higher-cost source route is received and the timer has expired, the currently stored source route is considered unavailable and is replaced with the most recently received source route.
See "Sequenced Neighbor Table Implementation" later in this chapter for more information on nbslrtimer.
Sequenced Re-initialization Packets
A router broadcasts sequenced re-initialization packets on all of its interfaces when it detects neighbor routers without the most up-to-date routing information about it. The destination VINES internet address is set to the VINES broadcast address. How the packets are sent depends on whether LANs or WANs are involved.
On LANs, the destination data link address is set to the data link broadcast address for the medium.
On WANs, the packets are sent directly to the neighbor.
Re-initialization packets force the neighbor routers to remove all of the old routing information on the router that sent the broadcast, or information associated with the router, such as entries for networks that are reached through the router. After approximately 3 minutes, the router that sent the broadcast sends routing update packets that contain the latest routing information.
A full update from its neighbors may be needed if a router finds itself completely isolated after a reboot, even though the router is aware of the existence of these neighbors. This isolation occurs if the sequence number retrieved from disk after the reboot is somehow outdated. This may happen when the router is restored from an old backup tape or the router is fresh-installed but its serial key is not new. See "Reconnecting to the Network" earlier in this chapter for more information.
In most cases, a restoration or an installation will take more than 6 minutes, which is long enough for neighbors to age out the old router's neighbor entry from their routing tables. However, this assumption may not be true on platforms other than native VINES. In addition, future routing implementations may not age out their neighbor entries at all (for example, link-state routing). This situation would cause these routers to be isolated if their sequence numbers are outdated after a reboot.
Sequenced re-initialization packets have no other header or data except the RTP header. Figure 5-20 illustrates the format of the sequenced re-initialization packet.
VINES Sequenced RTP Implementation Notes
This section provides implementation notes on the following sequenced RTP subjects:
![]()
Neighbor table ![]()
Network table ![]()
Routing metrics ![]()
Routing table timers ![]()
Routing table flags ![]()
Information exchange algorithms
Sequenced Neighbor Table Implementation
Every RTP entity maintains two tables containing routing information. The neighbor table contains path information about neighbors. The network table contains route information about known networks. See "Sequenced Network Table Implementation" later in this chapter for more information about the network table.
Neighbors are nodes that are directly connected. In VINES, neighbors are considered to be directly connected by the following topologies:
![]()
A LAN, which can consist of a single segment or multiple segments linked by bridges. These bridges can either link segments directly, or over some other medium, such as serial lines. For example, all VINES nodes on Token-Ring LANs connected by Token-Ring bridges, are neighbors. As another example, all VINES nodes on a Token-Ring LAN that consists of local and remote IBM Token-Ring bridges are neighbors.
![]()
A point-to-point connection, which includes X.25 virtual circuits, HDLC or block asynchronous lines, ISDN B-Channels, and T1 LAPD connections. ![]()
A non-VINES network, such as a NetWare, TCP/IP, or SNA network.
The neighbor table consists of entries, each storing information about a neighbor.
On client nodes, this table contains just one permanent entry for its routing server. The client node creates other neighbor entries as needed based on the contents of sequenced redirect packets.
On routers, there is one entry per neighbor, uniquely identified by the neighbor's network ID and subnetwork ID.
The fields in the entry are described in Table 5-7.
Each neighbor entry contains a list of available paths to reach the neighbor. Each neighbor path is itself an entry that is chained to the destination field in the neighbor entry.
Each neighbor entry has at least one neighbor path. If an existing neighbor is reachable through multiple interfaces, a neighbor path is created for each interface and inserted at the beginning of the corresponding route list. Each neighbor path is uniquely identified by its interface, such as an Ethernet card or X.25 virtual circuit.
Routers can have multiple neighbor path entries per neighbor entry. Since client nodes can have only one active interface, only one neighbor path entry can exist per neighbor entry.
The route entry is specified by the rthentry structure, whose fields are described in Table 5-8.
Some interfaces use formulas to calculate the routing metric instead of fixed values. These formulas are described in Chapter 4.
Sequenced Network Table Implementation
The network table consists of network entries, each of which stores information about a route to a logical network. The entry is identified by the network's ID. There is one entry per route as follows:
![]()
On client nodes, there is one entry for the routing server's logical network and one entry for each logical network with which the client node currently communicates. ![]()
On routers, there is one entry for each router in the network. The fields in the entry are described in Table 5-9.
Sequenced RTP Route and Neighbor Path Selection Algorithm
The sequenced RTP algorithm for selecting routes and neighbor paths does not differ significantly from the non-sequenced algorithm. See "Selecting Neighbor Paths and Routes" in Chapter 4 for more information.
The non-sequenced RTP implementation bases the cost of any route on the throughput capacity of the intermediate LAN and WAN interfaces. Non-sequenced RTP measures this cost in 200 millisecond ticks and interprets it as a 16-bit value. The fastest interfaces are currently a 10-Mbps Ethernet LAN and a 16-Mbps Token-Ring LAN. RTP assigns these interfaces a metric of 2. For more information on how non-sequenced RTP calculates metrics, see Chapter 4.
The metric 1 (200 milliseconds) is the only remaining value that sequenced RTP can use for data links that are faster than 10-Mbps Ethernet and 16-Mbps Token-Ring LAN. Sequenced RTP can use this value for future high speed link implementations, but it is not appropriate for distinguishing the potential wide differences in speed (for example, 100 Mbps vs. 500 Mbps).
Calculating Actual Metrics
The sequenced RTP implementation supports a different way to interpret metric values. To overcome the shortcomings of determining metrics in the non-sequenced RTP implementation, this way of calculating metrics has more granularity than non-sequenced RTP. Sequenced RTP splits the current 16-bit metric value into two parts:
![]()
The 12 low-order bits indicate metric values based on 200 millisecond ticks. ![]()
The four high-order bits provide better granularity based on fractions of 200 millisecond ticks.
If the fastest data links in the network are 10-Mbps Ethernet or 16-Mbps Token-Ring data links, all metrics will be in 200-millisecond ticks.
Using binary notation, sequenced RTP interprets a 16-bit metric value as follows:
RTP calculates the actual metric by adding together each bit's value based on the binary notation above. The value 0xF for the 4 high-ordered bits is reserved - these bits would be set if the metric indicated that the destination was unreachable.
Example Calculating the Actual Metric
Suppose that the metric field for reaching a destination was 0x9014. In binary, 0x9014 appears as follows:
RTP calculates the actual metric as follows:
Using Actual Metrics
Sequenced RTP determines the best route based on the stored 16-bit metric value advertised in routing update packets. The lower of two metric values indicates the cheaper cost. However, with the new way of interpreting metric values, the 16-bit metric value before the RTP calculation may be inversely proportional to the actual speed of the link before its calculation. The 16-bit metric value for a high-speed link may be greater than the value for a slow-speed line.
For example, sequenced RTP could store metrics for a 100-Mbps FDDI link and a 56-Kbps link as follows:
If just a simple comparison were performed, sequenced RTP would consider the 56-Kbps serial line to be the cheaper path over the FDDI link (0x4000 is greater than 0x002d).
To avoid this discrepancy, sequenced RTP handles the metric that it advertises in the routing update packets differently when it uses them to calculate the cheaper cost. Sequenced RTP transposes the 16-bit advertised metric to reflect the cost of the link correctly. Sequenced RTP performs the transposition by rotating the first 4 high-ordered bits so they become the first 4 low-ordered bits. RTP uses the following algorithm:
x = advertised metric value shifted left by 4 bits
y = advertised metric value shifted right by 12 bits
cost = x | y
Example Using Actual Metrics
This section provides examples of interfaces and their corresponding metric values based on the new metric interpretation.
The first example simply lists the following informational items:
![]()
The interfaces ![]()
The actual metric cost of each interface ![]()
The 16-bit value (in both hexadecimal and binary) that the router advertises in routing update packets (netadvcost)
Using the same interfaces, the second example shows the metric values in both hexadecimal and binary that routers store in neighbor and network entries for timeout calculations (nbmetric and netmetric) and for selecting the best route (nbcost and netcost).
Metric Compatibility with Non-Sequenced RTP
To interoperate with non-sequenced RTP, sequenced RTP uses a new metric so nodes that do not support sequenced RTP can handle metrics that reflect new high-speed data links correctly. When a node that supports sequenced RTP advertises a metric to a node that does not, the advertising node masks out the 4 high-order bits and only advertises the 12 low-order bits.
Remember the 12 low-order bits specify the metric in 200-millisecond ticks, which non-sequenced RTP can handle. Only sequenced RTP can understand the 4 high-order bits, which provide the granularity needed for metrics for new high-speed data links.
Routing table entries have flags that provide
internal routing software with descriptive information about
the entry, such as whether the destination network is reachable.
A flag is a bit that is set to either 1
or 0.
Each routing table entry has a 16-bit field that RTP uses for setting flags. For example, bits 0 (zero) and 1 can be set:
15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
In this case, the route's destination is reachable, and the destination is a router.
The individual bits and their meanings when set are described in this section. A bit is set when its value is 1. The hexadecimal values in parentheses mean that just the specified bit is set.
Unless noted, the flags are used by both client nodes and routers, and they can be applied to both neighbor path and network entries.
RTF_UP (0x1) The route is usable.
RTF_GATEWAY (0x2) The destination is a router.
RTF_HOST (0x4) If this flag is set, the entry is a neighbor path entry. Otherwise, it is a network entry in the network table.
RTF_KILL (0x8) The network entry can be removed. This flag applies to network entries only. The flag is set when all network entries must be removed.
RTF_TRANSIENT (0x10) The network entry is transient. This flag applies to network entries on client nodes only. When a client node attempts to communicate with an unknown logical network, the client creates a temporary network entry with the RTF_TRANSIENT and the RTF_METRIC flags set. The client then sends a request to its routing server, which responds with a routing response packet containing an entry with the correct metric for reaching the logical network. The correct metric replaces the temporary one.
RTF_PERMANENT (0x20) The entry is permanent and cannot be aged out. This flag applies to neighbor path entries associated with WAN neighbors that do not support sequenced RTP only, such as VINES 4.11 servers. It indicates that a permanent route to the neighbor exists. A permanent route is a WAN connection, such as serial lines, X.25 virtual circuits, ISDN B-Channels, TCP/IP networks, NetWare networks, and SNA networks.
RTF_CHANGE (0x40) The network entry has been updated due to a change in the network, such as a new router coming on line. This flag is set only when the following conditions are met:
![]()
A change in the network has occurred. ![]()
The router has WAN neighbors that do not support sequenced RTP. ![]()
The neighbors are connected to the router by WAN connections, such as serial lines, X.25 virtual circuits, ISDN B-Channels, TCP/IP networks, NetWare networks, SNA networks, or other WAN connections as they become available.
The flag indicates that the entry must be in the routing update packet sent across the WAN. When changes in the network take place, routers send on WAN connections only those network entries that have been modified (that is, entries which have this flag set). The entries are contained in routing update packets.
RTF_METRIC (0x80) The metric in this entry must be updated with the correct metric, which is received in a routing response packet from the client's routing server. This flag applies to transient network entries on client nodes only.
RTF_NVIP (0x100) A neighbor is reached over a non-VINES network, such as a TCP/IP network, an SNA network, or a NetWare network. This flag applies to neighbor path entries on routers only.
RTF_REDIRECT (0x200) The neighbor path entry was created when processing a redirect packet. This flag applies to neighbor path entries only.
RTF_SUPPRESS2 (0x800) This flag indicates that the routing entry is in the second suppression period, which takes 1 minute on routers that support non-sequenced RTP, such as VINES 5.0 servers, and up to 2 minutes on routers that support sequenced RTP, such as VINES 5.5 servers. See "First Route Suppression Period" and "Second Route Suppression Period" in Chapter 4 for more information.
Note: The RTF_SUPPRESS1 flag (0x400) is not used with the sequenced RTP implementation.
This flag applies to routers only.
RTF_ADJSLRCOST (0x800) This flag appears only in the client node's entry in the neighbor table for its routing server. The flag is set only when these conditions are met:
![]()
The client node is connected to the routing server in a Token-Ring bridge environment by a source route. ![]()
The routing server adjusted the metric that the client uses to reach it.
RTF_PNTTOPNT (0x1000) This flag indicates that the connection between the last hop to the destination router and the destination router itself is a point-to-point connection, such as HDLC and asynchronous lines, X.25 VCs, and ISDN B-Channels. The last hop is the final gateway along a route to a destination. Neighbor routers act as last hops to each other.
RTF_BCAST (0x2000) This flag indicates that the connection between the last hop and the destination is a LAN.
RTF_MODIFIED (0x4000) This flag indicates that the routing table entry has been modified by an RTP redirect packet.
RTF_OLDREV (0x8000) If this flag is set, and RTF_BCAST, RTF_PNTTOPNT,
or RTF_NVIP is
also set, then both of these conditions exist:
![]()
The destination is a router that does not support sequenced RTP, such as an ENS for UNIX 1.0, VINES 4.x, VINES 5.0, or ENS 1.0 server. ![]()
All the gateways along the route to the destination support sequenced RTP, such as VINES 5.5 servers.
If the RTF_PNTTOPNT flag is set, a WAN, such as an HDLC line or TCP/IP network, connects the last hop and the destination. If the RTF_BCAST flag is set, a LAN connects the last hop and the destination.
If RTF_OLDREV is set and RTF_BCAST or RTF_PNTTOPNT and RTF_NVIP are not set, one of the gateways along the route to the destination is a router that does not support sequenced RTP, such as an ENS for UNIX 1.0, VINES 4.x, VINES 5.0, or ENS 1.0 server.
RTF_FULLUPDT (0x10000) The network entry was updated based on the receipt
of a full topology
update. This flag does not apply to client nodes.
RTF_UDPREDIR (0x20000) The neighbor supports receiving UDP encapsulated packets from a node that has been redirected to send directly to the neighbor.
Sequenced Routing Table Timers
VINES routing software in the sequenced RTP implementation uses timers for a variety of purposes, such as to remove neighbor path and network entries for destinations that are unreachable or are no longer in existence. Timers are measured in, approximately, 90-second units of time. For example, a timer of 4 is 6 minutes to 71/2 minutes.
Table 5-10 lists and describes timers in both neighbor path entries and network entries, and timers that are used for other purposes.
The following examples illustrate how some of these timers are used. Examples for some of the other timers can be found in Chapter 4.
Example RTS_AGELESS Timer
A new router comes on line, and news of its existence is propagated through the network. All the other routers in the network allow the netidle timer to reach RTS_AGELESS (0xFFFF). This timer remains in effect until the router becomes unreachable. On routers that support sequenced RTP, the netidle timer in entries for networks reached through another router that supports sequenced RTP automatically go to 0xFFFF.
Example RTS_DEMISE Timer
A router, Server A, suddenly becomes unreachable due to a data link failure. When other routers first learn that it has become unreachable, they allow the netidle timer to reach RTS_DEMISE. This timer allows the other routers to wait at least 90 seconds for further confirmation that Server A is still unreachable.
At this point, one of the following things can happen:
![]()
If the other routers learn that Server A has suddenly become reachable before the timer expires, the other routers allow netidle to reach RTS_AGELESS again in the entry for Server A. ![]()
If the other routers receive a subsequent routing update indicating Server A is unreachable before the RTS_DEMISE timer expires, the other routers remove the entry for Server A. ![]()
If the other routers do not receive a subsequent routing update indicating Server A is unreachable before RTS_DEMISE expires, the other routers remove the entry for Server A once the timer expires.
How Routing Tables Are Maintained by Sequenced RTP
This section describes these scenarios to illustrate how routing tables on client nodes and routers are maintained:
When No Network Changes Take Place
This section describes the actions that routers and client nodes perform when no network changes take place.
Routers - On LANs and WANs, a router broadcasts null routing update packets every 90 seconds, regardless of whether any changes in the network occur. This broadcast informs neighbor routers that they are still on the network.
On LANs, the null update packets are transmitted as a 0 (zero) hop data link and network layer broadcast.
On WANs, the null update packet is transmitted directly to the neighbor.
Every 12 hours, routers broadcast a full routing update on all active interfaces to ensure that all of their network tables are synchronized.
Client Nodes - On LANs and WANs, a client node informs its routing server that it is still on the network by sending it a null update every 90 seconds.
Client nodes that dial in to the network verify that their routing server is reachable by sending routing request packets to it. The request packet includes the request packet header. The data portion is empty. Routers respond with a null update packet.
Because routers filter broadcasts, clients must broadcast null updates whenever they send a non-routing network broadcast without sending a routing broadcast (such as a null update) for 4.5 minutes. A non-routing broadcast originates from a higher-level entity, such as an application program. Routers filter broadcasts to detect broadcast loops. They filter broadcasts received on interfaces that are not associated with the best route to reach the originator of the broadcast.
By broadcasting their presence before sending a non-routing network broadcast, clients ensure that routers are aware of the direct path connecting them.
Routers on the network learn about new routers in one of the following ways:
![]() |
By receiving a sequenced update packet from another router |
![]() |
By receiving a redirect packet containing information about a neighbor router from which a sequenced update packet has not yet been received |
In most cases, other routers learn of a new router's existence through sequenced update packets.
When a router comes on to the network, the following packet exchange takes place between the router and its neighbors:
1. The new router announces its arrival by broadcasting null routing update packets to neighbors.
2. Neighbor routers add this router to their neighbor table and their network table.
Neighbors use the source address in the VINES IP header and the sequence number and metric fields in the sequenced update header to create the table entries. In the sequenced update header, the metric is derived from the interface where the new router sends the broadcast.
3. The actions that neighbor routers take depend on the number of routers on the data link that connects the existing routers and the new router.
If the new router is only the second router on the data link (that is, there is only one existing router), both the new router and the existing router broadcast full routing updates on that interface.
If the new router is the third (or greater) router on the data link, the existing routers send full topology updates directly to the new router. In this case, the updates are not sent as broadcasts; rather, they are sent directly to the new router. The new router broadcasts its routing update.
4. News of the new router's arrival is propagated through the network. Within 2 seconds, neighbors of the new router broadcast routing updates on all interfaces containing only the news of the router's arrival. These neighbors in turn broadcast updates to their neighbors, and so on.
Within 2 seconds after neighbor routers receive sequenced update packets containing news of network changes, they propagate the news to their neighbors on all of their interfaces (including the interface that they received the news on). This process continues, from router to router, until the news reaches all the routers in the network. See "Propagation of Network Topology Changes" in Chapter 3 for more information.
When routers receive news of a new network, routers perform an algorithm that depends on whether they are:
![]()
Neighbors of the new router ![]()
Non-neighbors of the new router
Algorithm for New Neighbor Routers - When a new router comes on the network, it must exchange a full update with its neighbor routers. This exchange ensures that all of the routers' topology information in both routing tables is synchronized. When processing a received null update packet from a new router, neighbor routers follow this basic algorithm:
1. The neighbor checks the neighbor table for an entry for the new router.
2. Because no entry for the new router exists, the neighbor must create one. The neighbor extracts the following information from the null update packet:
- The LAN address (if applicable) from the data link header
- The source route (if applicable) from the data link header
- The source VINES internet address from the VINES IP header
- The sequence number from the sequenced update header
- The metric from the sequenced update header
3. The neighbor creates an entry for the new router in the neighbor table with the information from step 2. Some of the parameters that the router sets are as follows:
- The time-to-live timer to RTS_RESPONSE in the neighbor path entry for the new router. This gives the new router a chance to send a full routing update. If the new router does not send the update, the neighbor can issue up to three requests for full routing updates to the neighbor.
- Flags in the neighbor path entry to indicate that the new node is a router. If the neighbor is connected by a WAN and does not support sequenced RTP, such as a VINES 4.11 server, the router sets the RTF_PERMANENT flag.
- Metric and cost parameters using the metric from the received null update packet.
- State to INIT.
- Router sequence number to the sequence number received in the null update packet.
- Data link address (such as the LAN address) to the neighbor's data link address.
In addition to setting parameters, the router stores a neighbor path entry for the interface that connects the new router, and stores the packet ID extracted from the sequenced update header.
4. In the network table, routers create an entry for the new router with the received VINES internet address, sequence number and interface metric. Some of the parameters that the router sets are as follows:
- Destination to the source network number in the VINES internet address from the VINES IP header.
- The gateway to the destination to the new router.
- The metric and cost parameters using the metric from the received null update packet.
- Time-to-live timer to RTS_AGE.
- The neighbor sets only the RTF_UP and RTF_GATEWAY flags unless the neighbor, in turn, has WAN neighbors that do not support sequenced RTP, such as VINES 4.11 servers. In this case, the neighbor sets the RTF_UP, RTF_GATEWAY, and RTF_CHANGE flags.
In addition to setting parameters, the router stores the network sequence number that is extracted from the sequenced update header.
5. Within 2 seconds of receiving the null update from the new router, the receiving router broadcasts a routing update containing just news of the change on all of its interfaces. For example, when one new router comes on the network, the routing update contains just one tuple.
6. The neighbor waits for the new router to send it a full topology update. The new router increments its sequence number by 1. Once the update is received, the neighbor changes the state of the new router from INIT to UP and updates the new router's sequence number based on the one that the router advertised.
Since multiple new neighbor routers can come on line at the same time, the routers delay the broadcast of the full update so that most of the new neighbors can participate in the exchange. The routers broadcast the full update whenever normal null updates are broadcast (that is, once every 90 seconds) or the required changes-only update is broadcast (that is, after 2 seconds).
Example Neighbor of a New Router
Figure 5-21 shows a new router announcing itself to a neighbor on an Ethernet LAN. Subsets of the fields in the neighbor, neighbor path, and network entries on the router that receives the routing update packet are also shown. Note that the current router sequence number of the router that receives the routing update is 4 at the start of the exchange, and timestamps the entry for the new router with 5.
Algorithm for New Non-Neighbor Routers - As news of the new router spreads throughout the network, routers that are not neighbors of the new router process routing update packets according to this algorithm:
1. Each router checks the router sequence number of the neighbor where the router receives news of the network change. When the neighbor sees that the sequence number has increased, the neighbor knows that it can accept the news.
2. The router changes the neighbor's router sequence number in the neighbor entry.
3. In the network table, each router creates an entry for the new router with information in the new router's tuple.
Some of the parameters that each router sets are as follows:
- Destination to the network number in the tuple.
- The network sequence number in the entry to the sequence number in the tuple.
- Timestamps the network change with a value that is one greater than the router's current sequence number.
- A pointer to the neighbor entry for the gateway from which the news was received.
- Metric and cost parameters using the metric from the tuple.
- The time-to-live timer to RTS_AGELESS.
- Only the RTF_UP and RTF_GATEWAY flags unless the router, in turn, has WAN neighbors that do not support sequenced RTP, such as VINES 4.11 servers. In this case, the router sets the RTF_UP, RTF_GATEWAY, and RTF_CHANGE flags.
4. The router increments its current router sequence number by one and broadcasts news of the change.
Example Non-Neighbor of a New Router
Figure 5-22 shows a router receiving news of a new router that is not a neighbor. Subsets of the fields in the neighbor, neighbor path, and network entries on the router that receives the routing update packet are also shown.
When a routing update packet (null or otherwise) is not received from another router within the time of the RTS_AGE period, each neighbor router performs these steps:
1. Timestamps the network change with a value that is one greater than the current router sequence number.
2. Sets the time-to-live timer to RTS_AGE, turns off the RTF_UP flag and marks as unreachable the network entries for the following nodes:
- The router that left the network
- All destinations for which the router acted as a gateway
If the routers that remain on the network have neighbors that do not support sequenced RTP on WAN interfaces, these routers set the RTF_CHANGE flag in the changed network entries.
3. Increments the current router sequence number by 1 and broadcasts news of the change to all remaining neighbors within two seconds after detecting the change. Each router includes a tuple in the routing update packet for the router that left the network and destinations reached through it. Each tuple contains a metric of 0xFFFF.
4. Deletes the entry for the network associated with the router that has left.
When a Client Node Comes On Line
When a client node receives its VINES internet address, it creates a neighbor entry and a corresponding neighbor path entry for its routing server with information in the ARP assignment response packet. The client node creates the entries with the following information from this packet:
![]()
The routing server's data link address from the data link header ![]()
The routing server's source VINES internet address from the VINES IP header ![]()
The metric from the assignment response packet header ![]()
The sequence number from the assignment response packet header
See Chapter 3 for more information on the address assignment process.
After receiving its VINES internet address, the client node is ready to communicate.
Client nodes only exchange RTP packets with their routing server. Client nodes ignore RTP packets from other nodes except for redirect packets from neighbor routers. Any initial communication with other networks is through the routing server.
To discover the existence of a better route to any destination, client nodes depend on sequenced redirect packets from their routing server. In turn, to discover that a client node is a neighbor, routers other than the client node's routing server depend on redirect packets from the routing server.
When a Client Node Goes Off Line
When a client node on a LAN goes off the network, its routing server removes the entry for the node from its neighbor table. The routing server removes the entry if it does not receive a null update from the node for 4.5 minutes to 6 minutes.
If the client node dials in to the network, the client node's routing server removes the entry for the node from its neighbor table when the dial-in connection terminates.
When a Client Node Communicates Outside Its Logical Network
Since a client node only keeps track of its routing server's network and the networks with which it is currently communicating, the client node must be able to quickly learn how to reach new networks. To do this, the client node performs the following algorithm:
1. The client node finds out the destination VINES internet address of the router through StreetTalk and creates a transient entry in the network table. The client node indicates that the entry needs a better metric by setting the RTF_TRANSIENT flag and the RTF_METRIC flag.
The routing server is used as the temporary router.
A temporary, "best guess" metric is used to reach the destination. See "Client Node Request for Routes" in Chapter 3 for more information on the "best guess" metric.
2. The client node waits 5 seconds before requesting metric information from its routing server:
- In most cases, the redirect packet arrives before the client node is forced to send a routing request packet.
- If the client is forced to send a routing request packet, the routing server responds with a routing response packet containing the correct metric for reaching the destination. If the routing server does not respond initially, the client node continues to send a routing request packet every 5 seconds until a routing response packet containing the correct metric is received.
3. The client node replaces the "best guess" metric with the correct metric for reaching the destination. The client node disables the RTF_METRIC flag for the entry.
Transient entries are aged out of the network table within RTS_TAGE minutes. Entries that are created in the neighbor table by redirect packets are aged out within RTS_RAGE minutes.
When Routers Initialize WAN Connections
When routers initialize WAN connections, the information exchange is similar to the exchange that takes place when a new router comes on the network. See "When a Router Comes On Line" earlier in this chapter for more information.
When a router that supports sequenced RTP initializes a WAN connection, it sends a non-sequenced routing request and a sequenced null update. The router sends the non-sequenced request every 30 seconds and the sequenced null update every 90 seconds until it receives one of these replies from the other end of the connection:
![]()
A sequenced null update indicating that the router on the other end of the connection supports sequenced RTP ![]()
A non-sequenced response or update indicating that the router on the other end of the connection only supports non-sequenced RTP
How a WAN connection initializes depend on whether both routers support sequenced RTP, or one supports sequenced RTP and one does not.
Both Routers Support Sequenced RTP - The initialization of a WAN connection between two routers that support sequenced RTP have the following characteristics:
![]()
The two routers create a neighbor path entry for each other. If necessary, they also create the neighbor entry. The state of the neighbor path entry is set to UP. ![]()
Routers send sequenced routing request packets to each other, requesting a full routing update as part of the initial routing exchange to synchronize routing tables. ![]()
Each router notifies its VINES Security Service to assign the correct level of access (unrestricted, restricted, or secure) on the WAN connection.
One Router Supports Sequenced RTP - Except for TCP/IP connections, the router that supports sequenced RTP sends three full routing updates after determining that the router on the other end of the connection does not support sequenced RTP. This ensures against the possibility of losing packets.
After the connection is established, the router that supports sequenced RTP determines if the neighbor is still connected by sending a routing update and up to three routing requests every hour. If the neighbor does not reply, the router that supports sequenced RTP assumes that the connection has been broken.
When the "Help Thy Neighbor" Scenario Takes Place
When a topology change takes place that makes networks unreachable, a router forces a routing update to "help its neighbors," if all of the following conditions are met:
![]()
Any neighbor that supports sequenced RTP advertises that a network is unreachable, or any WAN neighbor that supports only non-sequenced RTP, such as a VINES 4.11 server, advertises that a network is unreachable. This condition differs from the non-sequenced RTP implementation where only WAN neighbors are helped. ![]()
The router can reach the advertised network through another gateway. If the router reaches the advertised network through the neighbor that advertises it as unreachable, the router does not help its neighbor. ![]()
The change in the network topology did not alter the router's view of the network that became unreachable to its neighbor. ![]()
The router can provide an alternate route to the network that its neighbor can no longer reach.
When a router determines that it can help its neighbors that support sequenced RTP, it timestamps the network entries that are advertised as unreachable by incrementing the router's current router sequence number by 1. This action forces the entries to be included in the next scheduled sequenced routing update.
When a router determines that it can help its neighbors that support only non-sequenced RTP, it performs the following actions:
![]()
Marks the network entries that are advertised as unreachable with the RTF_CHANGE flag ![]()
Includes these entries in the "changes only" routing update that is sent to the WAN neighbor ![]()
Advertises these entries in the next scheduled routing update
Figure 5-23 illustrates the "help thy neighbor" scenario for sequenced RTP neighbors.
In Figure 5-23, Router C's Ethernet connection is broken, but its Token-Ring connection is still active. Router C previously used its Ethernet connection to reach Router A but now thinks that Router A is unreachable. Router C does not know it can reach Router A with its Token-Ring connection.
When Router C advertises that Router A is unreachable, Router B forces a routing update to Router C. The update tells Router C that it can reach Router A over the Token-Ring connection and through Router B.
RTP adjusts to changes in the cost of reaching a destination. How RTP adjusts to these changes depends on whether the received metric is:
![]()
Cheaper ![]()
Equal ![]()
Greater
Cheaper Cost - When a received tuple contains a metric for reaching a neighbor that is less than the previous metric and the router validates the network sequence number, the router stores and advertises the metric immediately unless one of the following conditions is met:
![]()
The current metric indicates that the destination is unreachable (metric of -1). ![]()
The network entry is currently suppressed and a new gateway to the destination is advertised.
If one of these sets of conditions is met, the router performs the following actions:
![]()
Sets the RTF_SUPPRESS2 flag to begin the suppression period ![]()
Sets the RTF_CHANGE flag if it has WAN neighbors that do not support sequenced RTP ![]()
Sets the suppression timer to RTS_SUPPRESS ![]()
Timestamps the network entry
Although the destination may be reachable, the router advertises that the destination is unreachable for the suppression period.
As news of the metric change propagates through the network, other routers perform the same actions as the routers that initially detect the change.
After the suppression period, the routers that initially detect the metric change turn off the RTF_SUPPRESS2 flag and advertise the correct metric for reaching the destination. The correct metric propagates through the network so other routers can reach the destination.
This procedure eliminates circular paths and readjusts network path selection as quickly as possible. When a router either adjusts a routing metric in a network entry or creates a new entry, the router broadcasts a new routing update packet. This lets RTP update the entire network rapidly any time a new router appears or a new communications line is enabled.
Equal Cost - If the router validates the network sequence number, the router accepts the same network as the one stored in the network entry, as long as the entry is not currently in suppression.
Greater Cost - A router accepts a greater metric only if the neighbor router that advertises it is the original router for reaching the destination. If the metric is accepted (assuming sequence number validation) and is not -1 (0xFFFF), a router takes the following actions:
![]()
Sets the destination to unreachable (-1) ![]()
Sets the RTF_CHANGE flag if it has WAN neighbors that do not support sequenced RTP ![]()
Timestamps the entry
The router advertises that the destination is unreachable before it removes the entry.
If the new metric indicates that the destination is unreachable (-1), routers advertise it immediately.
When a router reboots and it receives its first routing update from a neighbor router, it sets the initialization timer to RTS_INIT. This timer allows enough time for neighbor routers to acknowledge the router's presence. If routers accept this router's updates, the router should be processing one or more of the following RTP operations:
![]()
Requests for full topology information ![]()
Updates (full or changes-only) that advertise the router's existence with the correct sequence number (one that matches the router's current value) ![]()
Full response to an initial routing request
If the router does not detect any acknowledgment within the given time limit, the router assumes that its initial sequence number is not up-to-date. It broadcasts sequenced re-initialization packets on all its interfaces so that all neighbor routers remove their current knowledge of the rebooted router. During the RTS_REINIT time period, the router does not broadcast any sequenced updates. Once this time period elapses, the router broadcasts a full sequenced topology update. Thereafter, it broadcasts updates as usual.
Routers that process the incoming re-initialization packets simply remove the neighbor entry corresponding to the originator. Removing this neighbor entry ages out any network entry that specifies this neighbor as the gateway.
See "Reconnecting to the Network" and "Sequenced Re-initialization Packets" earlier in this chapter for more information on re-initialization packets.