Chapter 5 - VINES Sequenced Routing Update Protocol
This chapter describes sequenced RTP. This RTP implementation makes use of sequence numbers, which allow routers to determine whether the routing table information they receive from neighbor routers is up to date.
This section provides an overview of the following implementation aspects of sequenced RTP:
![]()
Router implementation ![]()
Client node implementation ![]()
Non-sequenced RTP compatibility ![]()
Verifying routing information
In the sequenced RTP implementation, routers propagate routing information in these situations:
![]()
When network topology changes occur ![]()
When routers or client nodes specifically request routing table information
Routers transmit routing information in the form of sequenced updates and sequenced responses. Depending on the amount of information that is being transmitted, these updates or responses can consist of one or more sequenced update packets.
Sequenced updates and responses are similar to non-sequenced updates and responses, with one notable exception. In sequenced updates and responses, each update or response is identified by a sequence number, which is a 32-bit value ranging from 0x0 to 0xFFFFFFFF. Each router has its own sequence number, which it advertises to neighbor routers in the header of a sequenced update or response packet. The router's sequence number identifies the state of its routing tables.
Sequence numbers allow routers to propagate only new or specific information and discard any outdated information provided by other routers. Routers use sequence numbers to timestamp changes in the network topology. Their sequence numbers are processed in ascending order, so lower values indicate outdated information. This allows routers to use their sequence numbers to verify the validity of each other's routing information.
As in the non-sequenced routing implementation, routers that support sequenced RTP only advertise routing information to neighbors. Because routers use sequence numbers, constant full topology updates are no longer required.
Both routers and client nodes send null sequenced updates (that is, no tuples) to advertise their continued presence. Routers send full topology updates under the following conditions:
![]()
When requested ![]()
When they are new routers that have just come on the network ![]()
When they detect the presence of a new router
In all other cases, routers only provide routing information when their view of the topology changes or upon request from a router or client node.
Client nodes only exchange RTP packets with their routing servers. If routers that only support non-sequenced RTP, such as VINES 4.11 servers, are on the same LAN, client nodes continue to broadcast non-sequenced routing updates for the sake of compatibility under certain conditions, such as before an IPC broadcast.
Client nodes always create a neighbor entry and a network entry for their routing server. Client nodes create all other network entries purely on a need-to-communicate basis. Except for the routing server, client nodes create neighbor entries for neighbor routers. The entries are based solely on information provided in routing redirect packets generated by the routing server.
Client nodes will always attempt to acquire a routing server that supports sequenced RTP before attempting to acquire one that does not. See Chapter 3 for more information.
Since client nodes do not propagate routing information, their sequence numbers are static. Client nodes always have a sequence number of 0 (zero).
Non-Sequenced RTP Compatibility
In order to interoperate with routers and client nodes that support only non-sequenced RTP, such as VINES 4.11 servers, routers that support sequenced RTP must also support non-sequenced RTP. For example, if a router has VINES 4.11 neighbors, the router must broadcast non-sequenced routing update packets and must be able to receive and process non-sequenced routing update packets. See Chapter 4 for more information on non-sequenced RTP.
RTP entities use the sequence number to verify:
![]()
The validity of a router's overall routing information ![]()
The currentness of specific network information that any router advertises to its neighbor routers
The sections "Validating a Router's Overall Information" and "Validating Specific Network Information" explain these capabilities.
Validating a Router's Overall Information
A router keeps track of the sequence numbers of its neighbor routers. These sequence numbers are called router sequence numbers. When a router undergoes a fresh installation, it has a router sequence number of 0 (zero) and advertises this sequence number in each sequenced update packet header.
Each router stores its neighbors' sequence numbers in the neighbor table. Each entry in the neighbor table points to a list of neighbor path entries, which specify interfaces to the neighbor. The neighbor's router sequence number is stored in the neighbor path entry.
RTP uses the sequence number in the neighbor table to validate a neighbor router's overall routing information. It also stores sequence numbers in the network table to validate the network entries with which they are associated. See "Validating Specific Network Information" later in this chapter for more information on validating network entries.
Neighbor routers use the advertised router sequence number in the sequenced update packet header to validate the routing updates they exchange. See "Sequenced Update Packets" later in this chapter for more information on this header.
When one neighbor router receives a sequenced update packet from another, the receiving router performs the following comparison:
Is the router sequence number in the header of the sequenced update packet greater than, less than, or equal to the router sequence number for the sending router from the neighbor table?
Figure 5-1 shows a router comparing sequence numbers after receiving a sequenced routing update from another router.
In Figure 5-1, the router sequence number in Server A's packet is one greater than the router sequence number for Server A in the neighbor table. This tells Server B that Server A is advertising a valid change in the network. Server B updates its routing tables accordingly. When any router detects a network change, it increments its router sequence number by one and advertises the new router sequence number along with news of the change to neighbors.
The rules routers use to validate neighbor router sequence numbers are based on these factors:
![]()
The sequence number comparison ![]()
The current state of the neighbor from which the sequenced update packet is received ![]()
The contents of the sequenced update packet Note: Routers always check their neighbors' router sequence number before accepting sequenced updates or responses. However, if the sequenced update or response consists of multiple fragments, the router does not process the routing update or response until it is fully reassembled. See "Fragmentation and Reassembly" later in this chapter for an explanation of how RTP handles fragmentation.
The neighbor state is maintained in the neighbor path entry. Table 5-1 describes possible neighbor states.
Rules for Validating Router Sequence Numbers
Table 5-2 describes the rules for validating router sequence numbers.
Table Notes
Sequenced RTP assumes that it missed the sequenced update containing news of changes if these conditions are met:
![]()
The sequence number in the packet is greater than the sequence number in the neighbor table by one ![]()
The neighbor state is UP ![]()
The received packet contains a null update
The local router must request these changes from the neighbor that sent the null update. In the request packet, the local router furnishes the sequence number that it currently stores for this neighbor as the reference point in time.
The local router assumes that routing information is obsolete when the sequence number in the packet is lower than the sequence number in the neighbor table. In this case, the router ignores the neighbor's routing information.
The local router assumes that it missed some sequenced updates from the neighbor when these conditions are met:
![]()
The sequence number in the packet is greater than the sequence number in the neighbor table by more than one. ![]()
The sequenced update does not contain full topology information.
As a result, the local router must request the neighbor to provide news of any network changes that occurred since the local router received the last sequenced update or response from this neighbor. In the request packet, the local router furnishes the sequence number that it currently stores for this neighbor as the reference point in time. The local router only makes this request if the neighbor's state is UP and the local router is not currently reassembling a multipacket update from this neighbor.
Processing Accepted Routing Updates or Responses
As was described in "Rules for Validating Router Sequence Numbers" earlier in this chapter, a router performs a comparison when it receives a neighbor's router sequence number in an RTP packet. The receiving router compares the received number to the router sequence number that is stored for the neighbor in the neighbor table. If the received number equals the stored number, or is greater by one, the receiving router takes the following actions:
![]()
Resets the time-to-live timer (nbidle) in the entry. ![]()
Recalculates the routing metric (nbmetric) in the entry. ![]()
Recopies the neighbor's link address (nbdladdr) from the frame header. When a router can use multiple Token-Ring interfaces and multiple source routes to reach the neighbor, the action that the router takes depends on whether the neighbor supports sequenced RTP.
If the neighbor supports sequenced RTP, the router saves only the link address associated with the source route of the first update or response received based on the packet ID. See "Sequenced Update Packet Header Format" later in this chapter for more information on the packet ID.
If the neighbor does not support sequenced RTP, the router saves the link address associated with the source route with the lowest metric.
Note: Received router sequence numbers that are either lower than the stored router sequence number or are greater by more than one are never accepted.
When a router accepts a complete routing update or response, the router takes one of the following actions, depending on whether the router sequence number in the packet equals the router sequence number for the neighbor in the neighbor table, or is greater by one.
Equal Sequence Numbers - The router processes the routing information only if both of the following conditions are met:
![]()
The neighbor's state is not UP. ![]()
The routing update does not contain resynchronization information.
Because routers only update their own router sequence numbers when they detect changes in the network, sequence numbers of equal value indicate that no changes occurred since the last received routing update or response from the neighbor. In this case, the router that receives the duplicate information updates the corresponding neighbor path entry as follows:
![]()
Resets the time-to-live timer (nbidle) in the entry. ![]()
Recalculates the routing metric (nbmetric) in the entry. ![]()
Recopies the neighbor's link address (nbdladdr) from the frame header. ![]()
Recopies the neighbor's link address (nbdladdr) from the frame header. When a router can use multiple Token-Ring interfaces and multiple source routes to reach the neighbor, the router copies only the link address associated with the best source route to reach the neighbor. The best source route is the one with the lowest routing metric.
Sequence Number in Packet Is Greater by One - The router processes the routing information accordingly and stores the new router sequence number. Depending on the circumstances, the router also performs the following actions:
![]()
If applicable, recopies the source route to reach the neighbor into the neighbor path entry. ![]()
If the neighbor provides the best route to the destination network, the router updates the network sequence number, gateway pointer, and metric field in the entry for the destination network. If the neighbor supports non-sequenced RTP, the router updates the time-to-live timer.
Updating the Router Sequence Number
A router updates its router sequence number only if these conditions are met:
![]()
The router has detected changes in the network. These entries will be contained in a routing update broadcast. ![]()
The router broadcasts a routing update.
When a router detects a network change, it increments its router sequence number by one and advertises the new router sequence number along with news of the change to neighbors.
Validating Specific Network Information
Routers not only validate each other's overall knowledge of the network, they also validate each network entry that they receive from neighbor routers. For each network entry in its network table, a router stores two sequence numbers:
![]()
A network sequence number ![]()
A timestamp sequence number
The network sequence number is the actual router sequence number of the router associated with the network. The network sequence number is derived from one of the following sources:
![]()
If the network is associated with a neighbor router, the network sequence number is extracted from the sequenced update header of the update packet received from the neighbor. See "Sequenced Update Packets" later in this chapter for a description of this header. Thus, a router increments the network sequence number for a neighbor network only when the router associated with that network increments its router sequence number.
![]()
If the network is associated with a non-neighbor router, the network sequence number is extracted from a tuple for the network in the update packet. See the section "Sequenced Update Packets" later in this chapter for a description of this packet. A router increments the network sequence number for a non-neighbor network only when the router associated with that network is involved in a network change, such as a change in the metric for reaching the router's network.
Routers advertise the network sequence numbers in network entries in the data portion of sequenced update packets. The network sequence number in the network entry is updated whenever the gateway used to reach that network advertises a new network sequence number for it. See "Sequenced Update Packets" later in this chapter for information on the format of these packets.
Example Network Sequence Number
A router, Router A, comes on the network after rebooting, and its router sequence number is 1. The other routers in the network will also store 1 for Router A's network (the network sequence number).
If Router A's router sequence number increments to 2, neighbor routers will increment Router A's network sequence number from 1 to 2. Remember Router A will increment its router sequence number when it receives news of any network change, regardless of whether that change involves itself.
Non-neighbor routers will update Router A's network sequence number to 2 only when they receive an update with news of a change that involves Router A. Otherwise, non-neighbor routers will still store 1 for Router A's network sequence number.
The timestamp sequence number is a reference point based on the router sequence number when network information is stored.
After a router validates a neighbor's sequenced update or response, it extracts the network entries in the data portion of the packet. See "Validating a Router's Overall Information" earlier in this chapter for more information on validating sequenced updates or responses.
If a router detects a change for the network, the router timestamps the change by updating the network entry's timestamp sequence number by incrementing the router sequence number by 1. These kinds of changes can trigger this event:
![]()
A new network comes on line. ![]()
The metric for reaching a network increases. ![]()
A network becomes unreachable. ![]()
"Good news" concerning the network, such as a decreased metric, no longer needs to be suppressed and can be advertised.
The timestamp sequence number in a network entry is not updated if no changes to the associated network have taken place.
Example Timestamp Sequence Number
A router, Router A, comes on the network and the router sequence number of Router B at the time is 3. Router B will timestamp the network entry for Router A with 4.
Validating Network Sequence Numbers
Routers advertise the network sequence numbers in network entries in the data portion of sequenced update packets. See "Sequenced Update Packets" later in this chapter for information on the format of these packets.
After a router validates a neighbor's sequenced update or response, it extracts the network entries in the data portion of the packet. See "Validating a Router's Overall Information" earlier in this chapter for more information on validating sequenced updates or responses.
How a router validates a network entry depends on whether the network is associated with a neighbor router or a non-neighbor router.
Neighbor Network
If the network changes affect a neighbor router's network, the router that receives the news of the change compares the neighbor router's sequence number in the sequenced update header to the network sequence number in the network entry. If the neighbor router's sequence number is greater by one, the news of the change is valid.
Example Using the Router Sequence Number to Validate a Network Entry
Figure 5-2 shows the entry for a router, Server A, in the neighbor table and the network table of a neighbor router, Server B.
Notice the following characteristics in Figure 5-2:
![]()
The metric (netmetric and nbmetric) for the route between Server A and Server B is 4. ![]()
Server A's current router sequence number (nbseqno) is 3 and Server B's current router sequence number is 4. ![]()
The network sequence number in the network entry for Server A is 3, which matches Server A's current router sequence number. ![]()
Server B timestamped the network entry for Server A with a timestamp sequence number of 2. This means that Server B increased its router sequence number from 1 to 2 when it learned of Server A's existence.
In Figure 5-3, an Ethernet LAN is added to the network from Figure 5-2. Both the Ethernet LAN and the 4-Mbps Token-Ring LAN connect the two servers, resulting in a metric change. Server B validates the change in the network entry with the router sequence number in the RTP header received from Server A. Figure 5-3 shows Server B's updated neighbor table and network table.
Notice the following characteristics in Figure 5-3:
![]()
A new neighbor path entry is created for the Ethernet LAN. ![]()
The metric (netmetric) in the network table for the route between Server A and Server B changed from 4 to 2 because the higher throughput capacity of the 10 Mbps Ethernet LAN. ![]()
Server A's current router sequence number (nbseqno) changed from 3 to 4, and Server B's current router sequence number changed from 4 to 5. This happens because both servers detect the network change. ![]()
The network sequence number in the network entry for Server A (netownseqno) changed from 3 to 4, matching Server A's current router sequence number. ![]()
Server B timestamped the network entry for Server A with a timestamp sequence number of 5.
Non-Neighbor Network
If the network is not associated with a neighbor router, the router validates the entry with the updated network sequence number from the tuple in a routing update packet.
If the advertised network sequence number is equal to or greater than the network sequence number currently stored in the network entry, the router accepts the network information as valid. The stored network sequence number is updated with this latest value.
If the advertised network sequence number is less than the network sequence number currently stored in the network entry, the router ignores the network information because it is outdated. The router takes into account wrap around conditions. See "Detecting a Wrap Around Condition" later in this chapter for more information.
A similar validation occurs if the network is a neighbor; however, the neighbor's router sequence number is used (that is, the sequence number from the sequenced update header). On the other hand, when a change involving a non-neighbor network is validated, the network sequence number from a tuple is used.
Example Using the Network Sequence Number to Validate a Network Entry
Figure 5-4 shows the entry for Server A in the network table of a non-neighbor router, Server C, and also shows the entries for Server C's neighbor router, Server B, in Server C's neighbor and network table.
Notice the following characteristics in Figure 5-4:
![]()
The metric (netmetric) for the route between Server A and
Server C is 6, which is the sum of the 4-Mbps Token-Ring metric (4) and the 10 Mbps Ethernet metric (2). The metric for the route between Server B and Server C is 2.![]()
Server A's current router sequence number (nbseqno) is 3, Server B's current router sequence number is 4, and Server C's current router sequence number is 5. ![]()
The network sequence number in the network entry for Server A is 3. This means that Server A's current router sequence number was 3 when Server C learned of Server A. ![]()
The network sequence number in the network entry for Server B is 4, which matches Server B's current router sequence number. ![]()
Server C timestamped the network entry for Server A with a timestamp sequence number of 5. This means that Server C increased its router sequence number from 4 to 5 when it learned of Server A's existence. ![]()
Server C timestamped the network entry for Server B with a timestamp sequence number of 5. This means that Server C increased its router sequence number from 4 to 5 when news of network changes was received from Server B.
In Figure 5-5, a 10-Mbps Ethernet LAN is added to the network, connecting Server A and Server B and resulting in a metric change. Figure 5-5 shows Server C's updated neighbor table and network table.
In Figure 5-5, Server C does the following:
![]()
Validates Server B's knowledge of the network with the router sequence number in the RTP header ![]()
Validates Server A's network entry with the network sequence number in the data portion of the sequenced RTP packet
Notice the following characteristics in Figure 5-5:
![]()
The metric (netmetric) for the route between Server A and Server C changed from 6 to 4 because the higher throughput capacity of the 10 Mbps Token-Ring. ![]()
Server A's current router sequence number (nbseqno) changed from 3 to 4; Server B's current router sequence number changed from 4 to 5; and Server C's current router sequence number changed from 5 to 6. ![]()
The network sequence number in the network entry for Server A (netownseqno) changed from 3 to 4. The network sequence number was 3 because Server A's network number was 3 when Server C last received news of a change to Server A. ![]()
Server B advertised a network sequence number for Server A that was greater than the number that Server C stored for Server A. Server C accepted Server B's advertisement as a better metric to reach Server A. ![]()
Server C timestamped the network entry for Server A with a timestamp sequence number of 6. ![]()
Server C updated Server B's network sequence number, but did not modify the timestamp sequence number for Server B's network entry. Server C did not modify the timestamp because the news of the change did not involve Server B's logical network.
Each router timestamps the creation of a new network entry with its sequence number, which the router stores in the entry. This sequence number becomes the timestamp sequence number for the entry. The router timestamps any future changes affecting this network in the same way. The router timestamps the entry with a number that is one greater than its current sequence number. Using the incremented value ensures this network change is included in the next routing update.
Unless a router has to advertise network changes, it usually broadcasts null updates only. A null update contains just the RTP header and no data. When the router advertises network changes, only the network changes that have occurred since the last routing update are included.
To determine the network changes to advertise, the router compares its current router sequence number with the timestamp sequence numbers in the network entries in its network table. The router includes just the information from the network entries with timestamp sequence numbers greater than its current router sequence number.
Once the router has built the sequenced update packet and is ready to send it, the router increments its current router sequence number. The router includes the updated current router sequence number in the sequenced update header. See "Sequenced Update Packets" later in this chapter for more information on the sequenced update packet format.
A router also uses the timestamp sequence number to respond to requests from other routers. If a router requests information for network changes from a neighbor router, the following exchange takes place:
1. The requesting router looks at the current router sequence number for the neighbor router in its neighbor table, and furnishes that number in the request.
2. The neighbor router uses the furnished sequence number as a reference point. The neighbor router responds with just the network entries that have timestamp sequence numbers greater than the furnished sequence number. In the sequenced packet header, the neighbor router includes its current router sequence number.
RTP takes into account detection of a wrap around condition. See "Detecting a Wrap Around Condition" later in this chapter for more information.
Example Timestamp Sequence Numbers
A server's current router sequence number is 5. The server receives a routing update from another server indicating that the metrics for reaching two networks have changed. The server timestamps the entries for the two networks with 6 (current router sequence number + 1). The server then takes the following actions:
1. Compares its current router sequence number (5) to the timestamp sequence numbers in all of its network entries.
2. Determines that two entries have timestamp sequence numbers (6) greater than its current router sequence number.
3. Includes information from the two entries in its next routing update.
4. Increments its current router sequence number to 6, including incremented sequence number in the sequenced update header.
5. Broadcasts the packet.
Detecting a Wrap Around Condition
Because sequence numbers have a finite range ( 0x0 to 0xFFFFFFFF), it is possible that they can wrap around. Wrap around means that sequence numbers can increment from 0x0 to 0xFFFFFFFF and then wrap around to 0x0 again.
The initial value of each router sequence number is 0 (zero) during a fresh installation. Otherwise, the router extracts its sequence number from disk each time it reboots. See "Reconnecting to the Network" later in this chapter for more information.
Neighbor routers validate each other's routing information with their router sequence numbers. Consequently, a router must generate sequenced update packets with a router sequence number that is equal to or greater than the router sequence number that its neighbors may still associate with it (unless a wrap around is detected). Otherwise, the router is completely isolated because its routing updates are not accepted by neighbor routers. All neighbors ignore the router's sequenced update packets if the advertised router sequence number is invalid.
The following algorithm determines whether a sequence number has wrapped around:
1. When the router receives a router sequence number from a neighbor, the router checks to see if the received number is 1 greater than the sequence number stored for the neighbor in the router's neighbor table.
2. If the received router sequence number is not 1 greater than the sequence number stored for the neighbor, the router subtracts the stored sequence number from the received sequence number. The router stores the number resulting from this calculation in a signed long variable.
3. The action that the router takes depends on the number resulting from the calculation.
If the number is greater than 0 (zero), the router missed some routing updates from the neighbor.
If the number equals 0 (zero), the received sequence number equals the sequence number stored for the neighbor.
If the number is less than 0 (zero), the received sequence number is outdated.
To ensure that a known router can reconnect to the network after a reboot, each router stores a future sequence number in non-volatile memory, such as on disk.
The router stores this number with the assumption that the number is acceptable to neighbors when the router reboots to re-advertise its existence.
This future sequence number must be greater than the router's current router sequence number at the time the router stores it to disk. The stored sequence number must take into account the maximum number of possible topology changes that may occur between the time this value is stored and the router reboot. Since a router may be rebooted randomly, the router stores the future sequence number at consistent time intervals, called cache periods, to simplify the calculation. On VINES servers, the cache period is currently configured at 30 minutes.
The stored value may also be considered as the high-water mark for the sequence number within the cache period. The router calculates the high-water mark value, as follows:
current sequence number + max changes
---------------------------------------------------------------
stored sequence number
After broadcasting an update, sequenced RTP waits at least 2 seconds before broadcasting another. Assuming that a router broadcasts sequenced updates that contain only changes once every 2 seconds, a router sequence number would be updated once every 2 seconds in the worst case, as follows:
max. changes = cache period (in seconds) / 2 second intervals
= 1800/2
= 900
Once the router reboots and retrieves the router sequence number from disk, the router stores a new high-water mark for the sequence number based on the recently retrieved value.
If the router cannot retrieve the stored sequence number, the router uses the current system time instead. VINES servers use the current UNIX system time.
In many cases, the number derived from the UNIX time is greater than the last router sequence number. A greater sequence number prevents other routers from unnecessarily using sequenced re-initialization packets to flush entries from their network tables. See "Sequenced Re-initialization Packets" later in this chapter for information on sequenced re-initialization packets.
However, if the sequence number derived from the UNIX time is less than the sequence number that was lost, the server realizes that it is isolated and initiates re-initialization.
The fresh installation of a known router in the network forces the re-use of the sequence number of 0 (zero). Although neighbor routers can ignore this number, the knowledge of this router on the network will age out by the time the router is finally fresh-installed and reconnected to the network. This rule also applies to a server that is already known by the network and that is restored from a previous backup. The knowledge of this router will age out by the time the router has been fully backed up.
Note: This description of stored sequence numbers may not be correct on platforms that do not support native VINES, such as third-party routers. To accommodate these platforms, sequenced RTP implements sequenced re-initialization packets, which are described in "Sequenced Re-initialization Packets" later in this chapter.
Sample Use of Sequence Numbers
Figure 5-6 shows a network with three routers.
In Figure 5-7, a Token-Ring LAN is connected to Server B and another router, Server D, comes on the network. Server D broadcasts a null routing update to inform neighbors of its presence.
In Figure 5-8, Server B is the first router to learn of Server D, and broadcasts a full routing update on the Token-Ring LAN to build Server D's network table.
In Figure 5-8, Server B recognizes 0 (zero) as the sequence number for Server D. Server B recognizes 0 (zero) because Server D broadcasted 0 (zero) in its initial routing update. Also notice the following characteristics:
![]()
Server B has incremented its router sequence number to 3 and timestamped the entry for Server D with 3. ![]()
Server D stores 3 as the network sequence number for Server D.
In Figure 5-9, Server B broadcasts news of Server D's arrival on all of its interfaces. Server B broadcasts update packets containing news of Server D. Server A and Server C update Server B's network sequence number.
Server A and Server C update Server B's network sequence number, in addition to creating an entry for Server D. They update Server B's network sequence number based on the router sequence number from the sequenced update packet header received from Server B.
In Figure 5-10, all servers update their neighbors to ensure that their network tables are synchronized.
Notice the following characteristics in Figure 5-10:
![]()
Server A and Server C timestamp the network entry for Server D with the incremented sequence numbers and increment their router sequence numbers by 1. ![]()
Server B increments the network sequence numbers for all of the other servers (including Server D) because it received routing update broadcasts from the three other servers containing incremented sequence numbers. ![]()
Server A and Server C store a sequence number of 0 (zero) for Server D since 0 (zero) is the sequence number they received from Server B when they learned of Server D. ![]()
Server D updates its own router sequence number after broadcasting an update.
In Figure 5-11, the routing update process has completed.
VINES Sequenced RTP Specification
The following sections describe the sequenced RTP packet format and the types of sequenced RTP packets.
Sequenced RTP packets have a 6-byte header that follows the VINES IP header. In some sequenced RTP packet types, the RTP header is followed by other RTP information, such as additional headers or tuples.
Sequenced RTP packets are always sent with the destination VINES IP address set to the broadcast address. The destination data link address identifies a specific node, with the exception of these cases:
![]()
Sequenced update packet broadcast to LAN neighbors ![]()
Sequenced re-initialization packet broadcast to LAN neighbors
Figure 5-12 shows the sequenced RTP packet format.
The fields in the sequenced RTP header are as follows.
Version Number Field The version number field indicates the format of the RTP header according to the revision of the RTP implementation. Since no version number was previously associated with an RTP header, the current version number is 0x0001.
Since the high-ordered byte is 0, nodes that support only non-sequenced RTP will discard the sequenced RTP packet. To these nodes, the high-ordered byte appears as the operation type. These nodes do not recognize an operation type of 0 (zero).
See Chapter 4 for more information on non-sequenced RTP.
Operation Type Field The operation type field indicates the type of operation that the packet performs. Sequenced RTP supports four operations:
![]()
Sequenced requests ![]()
Sequenced updates ![]()
Sequenced redirects ![]()
Sequenced re-initialization
Routers use the sequenced update packet for both self-generated updates and responses to routing requests.
On LANs, client nodes use the packet for updates only.
On PC Dial-in or X.29 Dial-in connections, clients also use routing update packets to respond to requests from their routing servers.
The field contains one of the values described in Table 5-3.
The four sequenced RTP packet types are described in "Sequenced Request Packets," "Sequenced Update Packets," "Sequenced Redirect Packets," and "Sequenced Re-initialization Packets" later in this chapter.
Node Type Field The node type field indicates the type of node from which the sequenced RTP packet originated. The field contains one of the values described in Table 5-4.
Compatibility Flags Field The compatibility flags field filters out older versions of routing packets that are transmitted solely for backward compatibility. Routers also use them to inform clients of the presence of neighbor routers that support only non-sequenced RTP. Four flags are currently supported: 0x1, 0x2, 0x4, and 0x8. Remember multiple flags can be set. For example, both the 0x1 and the 0x2 flags can be set (00000011).
0x1 (00000001) - The 0x1 flag setting is reserved for future versions of sequenced RTP - it is not currently set. For backward compatibility purposes, a router can send a sequenced RTP packet indicating a version that precedes the sequenced RTP version currently running on the router.
The 0x1 compatibility flags setting allows the receiving router to determine whether it should accept and process the packet. If the packet indicates a version mismatch (0x1 setting) and the router supports an RTP version different from the one the packet specifies, the router discards the packet and waits for a packet that supports its RTP version.
Example Version Mismatch
A router may support version 2 of sequenced RTP, but may have to send version 1 RTP packets for backward compatibility reasons. In this case, the router sets the version number field in the RTP header to 0x1, but also sets the 0x1 compatibility flag to indicate a version mismatch. When a router that supports sequenced RTP version 2 receives an RTP packet with a version number of 1 and a compatibility flag of 0x1, the router discards the packet and waits for one with a version number of 2.
0x2 (00000010) - The 0x2 flag setting indicates neighbor routers that do not support sequenced RTP on the interface where the RTP packet is received. For backward compatibility, client nodes that support sequenced RTP must be aware of the existence of neighbor routers that support only non-sequenced RTP.
Clients that support sequenced RTP cannot adequately track neighbor routers that support non-sequenced RTP only. However, routers that support sequenced RTP have this capability, and they notify clients of the presence of routers that do not support sequenced RTP. The routers that support sequenced RTP set this flag in the sequenced RTP packets sent on the interface where the following nodes exist:
![]()
Routers that do not support sequenced RTP ![]()
Client nodes that do not support sequenced RTP
Example Neighbor Routers that Do Not Support Sequenced RTP
Server A supports sequenced RTP and is connected to an Ethernet LAN and a Token-Ring LAN. On the Token-Ring LAN, all of Server A's neighbors support sequenced RTP. However, on the Ethernet LAN, Server A has neighbor routers that do not support sequenced RTP. When Server A broadcasts sequenced RTP packets on the Ethernet LAN, it sets the 0x2 compatibility flag.
0x4 (00000100) - The 0x4 flag setting indicates that the neighbor router has the following characteristics:
![]()
The neighbor can only be reached across a non-VINES network, such as a TCP/IP network or NetWare network. ![]()
The connection to the neighbor router was automatically configured.
When a router has either the VINES 5.5 version of the Banyan TCP/IP Server-to-Server option or runs Banyan's IPX/SPX implementation, the router can only accept these connections from other routers that have been configured manually.
The 0x4 flag allows the router to avoid the automatic establishment of a connection when neither side has been configured manually. If this flag is set in a sequenced update received on a TCP/IP or IPX/SPX tunnel that was automatically configured, the RTP on the router takes the following actions:
![]()
Discards the packet ![]()
Informs the TCP/IP or IPX/SPX protocol of the invalid connection
Example Avoiding Automatic Connections
Two VINES 5.5 servers, Server A and Server B, have the TCP/IP Server-to-Server option. The administrator of Server A manually configures a connection to Server B. Server B has been configured to accept connections from other servers automatically. Server A and Server B can establish a TCP/IP server-to-server connection.
The administrator of Server A no longer wants Server A to communicate with Server B. The administrator removes Server B from Server A's configuration.
Server B will not know that the connection to Server A has been broken for a least 6 minutes. Until the 6-minute period expires, Server B continues to send null update packets to Server A with the 0x4 flag set in the RTP header. Server A does not accept the connection.
0x8 (00001000) - The 0x8 flag setting indicates that the neighbor router can accept packets encapsulated in UDP from a node that has been redirected to this node.
Reserved Field The last byte in the header is is reserved for future use and is always 0x0.
Sequenced request packets are always sent with these destination addresses:
![]()
The destination VINES internet address set to the VINES broadcast address ![]()
The destination data link layer address set to the address of the destination node
Client nodes send a sequenced request packet to their routing server in the following situations:
![]()
When they communicate with routers and other client nodes outside of their routing server's logical network. The request packet requests the routing server to send a sequenced update packet, which contains routing metric information used by the client node to communicate with the destination. ![]()
When they communicate with their routing server through a Token-Ring bridge. The request packet requests the routing server for the appropriate routing metric to reach it. Note: Routers that support sequenced RTP respond to client node routing requests differently than routers that support non-sequenced RTP. For example, while 5.0 servers reply with a routing response packet, 5.5 servers reply with a routing update packet. The RTP header indicates that the routing update packet is of the response type.
Routers also request routing table information from other routers in the following situations:
![]()
When they establish a WAN connection ![]()
When they detect the loss of a routing update ![]()
During the initial routing update exchange with a new neighbor that supports sequenced RTP ![]()
When they cannot reassemble a multipacket update or response
To verify that WAN neighbors that support non-sequenced RTP are still on the network, routers that support sequenced RTP transmit a non-sequenced RTP request once every hour. See Chapter 4 for information on non-sequenced RTP requests.
Client nodes do not keep full routing tables. They know only about their routing server (and its logical network) and the routers and client nodes with which they currently communicate. If the client node needs to communicate with any router or client node outside its routing server's logical network, the client node must send a routing request packet to its routing server.
Each sequenced request packet consists of a 4-byte header followed by the data associated with the type of request.
Sequenced Request Packet Header Format
Figure 5-13 shows the format of the sequenced request packet header.
The fields in the sequenced request header are as follows.
Requested Information Field The requested information field indicates the
type of information that is
being requested. The following values indicate the type of information
that may be requested:
0x1 Value - Requests routing information for a specified list of networks. Client nodes must request this information from their routing servers to communicate with logical networks outside their own. The response provides the real metric for reaching these networks, replacing the educated guess metric that the client node uses initially. The client node includes a desired list of the network IDs in the data portion of the request packet.
0x2 Value - Requests routing information on changes in the network topology that have occurred since a specific point in time. A router usually requests this type of information when it detects a loss of a routing update from a neighbor router. The router sends the request directly to the neighbor router. The router provides the sequence number from the last valid update or response received from the neighbor as the reference point. The router includes the sequence number in the data portion of the packet.
0x4 Value - Requests full topology information (that is, information about all known networks) from another router. A router can request this information for synchronization purposes or during the establishment of a WAN connection. The data portion of the request packet is empty.
0x8 Value - Requests a simple response from a routing server. A simple response consists of a routing update packet with just packet headers and no routing information in the data portion of the packet.
Client nodes that dial in to the network verify that the routing server is still reachable by sending these requests to it. The request packet includes the request packet header. The data portion is empty.
Clients with source routing enabled discover the correct metric for the source route to their routing servers across Token-Ring bridges by sending these requests. Client nodes must request this information because metric information about source routes to neighbors is not stored on client nodes. The request packet contains just the request packet header and no data. The source route in question is the one that the client node uses to reach its routing server, which the routing server extracts from the Token-Ring frame header containing this request. Clients request this type of information to use a different source route.
Reserved Field At this time, this reserved field is used to pack bytes on an even boundary due to compatibility issues with certain types of processors. Its value is always 0x0. This field may be used for other things in the future.
Sequenced Request Packet Data
The following types of routing request packets fill 0in the data portion of the request packet:
![]()
Requests for information on specific networks ![]()
Requests for routing information on changes in the network topology that have occurred since a specific point in time
In requests for information on specific networks, the data portion of the packet contains a list of 4-byte network numbers. See Chapter 3 for more information on network numbers.
In "changes-only" requests, the data portion of the packet contains the current router sequence number of the source router. The number can range from 0x0 to 0xFFFFFFFF.
Sequenced update packets serve three purposes:
![]()
Propagate news of network changes ![]()
Inform neighbors of each other's continued presence ![]()
Respond to routing request packets
Propagate News of Network Changes
When a router joins or leaves the network, or when the routing metric for reaching a router changes, other routers distribute news of these changes within 2 seconds. The changes in the network are contained in routing update packets. Like non-sequenced RTP, sequenced RTP does 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 transmissions, from router to router.
On LANs, routers broadcast routing update packets with a 0 (zero) hop count. These broadcasts are both data link layer and network layer broadcasts. The destination data link address is set to the broadcast data link address. The destination VINES internet address is set to the VINES broadcast address.
On WANs, routers send routing update packets that contain changes directly to the remote peer. The destination VINES internet address is set to the VINES broadcast address. The packets have a 0 (zero) hop count.
When a network change occurs, the routing update packets contain just the tuples that are affected by the change, thereby keeping network overhead to a minimum.
Remember a single routing update can contain multiple routing update packets, depending on the number of tuples transmitted in the update. If the total number of bytes in all the tuples exceeds the maximum VINES IP packet size, the routing update spans multiple routing update packets. See "Fragmentation and Reassembly" later in this chapter for more information.
Inform Neighbors of Continued Presence
Routers that are neighbors on LANs and WANs broadcast sequenced routing update packets to each other every 90 seconds. Routers broadcast these packets to inform neighbors that they are still on the network.
On LANs, routers broadcast null update packets with a 0 (zero) hop count. These broadcasts are both data link layer and network layer broadcasts. The destination data link address is set to the broadcast data link address. The destination VINES internet address is set to the VINES broadcast address.
On WANs, routers send null routing update packets directly to the remote peer. The destination VINES internet address is always set to the VINES broadcast address. The packets have a 0 (zero) hop count.
How client nodes inform their routing servers of their presence depends on how they are connected.
On LANs, client nodes send routing update packets to their routing server every 90 seconds. Client nodes perform this action to inform their routing servers that they are still on the network. The destination data link address is set to the data link address of the routing server. The destination VINES internet address is set to the VINES broadcast address.
On PC Dial-in or X.29 Dial-in lines, client nodes send routing update packets to their routing server (that is, the router that they dial in to) only when they initially dial in to the network. The destination VINES internet address is set to the VINES broadcast address. The packets have a 0 (zero) hop count.
The routing update packets that routers and client nodes send to announce their continued presence on the network are null update packets. This packet is small, containing no tuples. The packet just contains information about the router or client node.
Respond to Routing Request Packets
Routers respond to sequenced routing request packets with sequenced update packets (unlike non-sequenced RTP, which uses routing response packets to respond to these requests). The sequenced routing update packet indicates that the packet contains a response. Routers send routing update packets that contain responses directly to the requesting client node or router. The responses contain tuples needed by the requesting client node or router. How the router addresses the update packets depends on whether it sends the packets on LANs or WANs.
On LANs, the destination data link address is set to the data link address of the requesting neighbor. The destination VINES internet address is set to the VINES broadcast address.
On WANs, the update is sent directly to the neighbor. The destination VINES internet address is set to the VINES broadcast address.
Remember a single routing response can contain multiple routing update packets, depending on the number of tuples sent in the response. If the total number of bytes in all the tuples exceeds the maximum VINES IP packet size, the routing response spans multiple routing update packets. See "Fragmentation and Reassembly" later in this chapter for more information.
Each sequenced update packet consists of a 12-byte header, followed by a variable-length data field. Null update packets contain just the header. Routing update packets that contain news of network changes or responses to routing requests contain both the header and tuples in the variable-length data field.
Sequenced Update Packet Header Format
Figure 5-14 shows the format of the routing update packet header.
The fields in the sequenced update packet header are as follows.
Information Type Field The information type field indicates whether the packet is being used as an update or a response. The field contains one of the values described in Table 5-5.
Control Flags Field The control flags field contains the following bit flags:
0x0 (00000000) - The packet contains a null update.
0x1 (00000001) - The Beginning-of-Message (BOM) flag indicates that the packet begins a routing update or response. If the update or response consists of just one packet, both the BOM and the End-of-Message (EOM) flags are set (00000011). If the update or response consists of multiple packet fragments, the BOM flag is set in the first packet and the EOM flag is not set (00000001). If the EOM flag is set in the last packet, the BOM flag is not set (00000010). For any packet fragments in between, both the BOM and the EOM flags are not set (00000000).
0x2 (00000010) - The EOM flag indicates the packet ends a routing update or response. See the description of the BOM flag above for more information.
0x4 (00000100) - The packet has tuples that either contain specific network information requested by a client or router, or pertain only to networks that have undergone one or more of these changes:
![]()
The network has come on line. ![]()
The network is no longer reachable. ![]()
The network can be reached through a better route. ![]()
The network is no longer suppressed. See Chapter 4 for a description of suppression. ![]()
The router forced routing information to a neighbor. When a neighbor loses its direct path to a corresponding network and has a backup route through a router, this action tells the neighbor that the router can act as a gateway to the destination. See "When the "Help Thy Neighbor" Scenario Takes Place" later in this chapter for more information.
0x8 (00001000) - The packet is a part of an update that contains all of the tuples known to a given router (full topology update).
0x10 (00010000) - The packet is a part of an update that is designed to synchronize all of its neighbor routers'routing tables. Every 12 hours, routers broadcast a full routing update on all active interfaces. The packets in these updates all have the 0x10 flag set, forcing neighbor routers to process them even if network changes have occurred. The 0x8 flag is also set.
Example Control Flags Field
A router broadcasts a full update to its neighbors to ensure that routing tables are synchronized. The update consists of multiple packet fragments. In the first packet fragment of the update, the control flags field appears as follows:
0 0 0 1 1 0 0 1
Packet ID Field The packet ID field identifies each update or response. Routers primarily use this field for re-assembling updates and responses that consist of multiple packet fragments. The field identifies the fragments for a specific update or response.
The originator of the update or response assigns the packet ID. Each packet fragment in the update or response has the same packet ID. The router increments the packet ID value by 1 each time it sends a complete update or response.
Client nodes and routers also identify the best source route for a given packet with the packet ID. A node always uses the source route of the first update or response received with a new packet ID. The source route that a client node or router detects first provides the best path.
Example Packet ID Field
A VINES 5.5 server broadcasts a full update that contains 250 tuples. The update spans three packet fragments. Each packet fragment has a packet ID of 0x4.
After the full update is broadcast, the VINES 5.5 server broadcasts a null update. The packet ID of the null update packet is 0x5.
Data Offset Field The data offset field is designed for multipacket updates and responses. The field specifies the position of the packet fragment's tuples relative to the tuples provided in the first packet fragment. The first packet fragment of a multipacket update or response has a data offset of 0 (zero). For single-packet updates or responses, the data offset is also 0 (zero).
The data offset field is the sum of the tuples provided by the previous packet fragments. Each packet fragment can contain a maximum of 119 tuples.
Example Data Offset Field
A VINES 5.5 server broadcasts a full update that contains 250 tuples. The broadcast spans three packet fragments. The first two fragments contain 119 tuples each, and the third contains 12 tuples. The values of the data offset fields in the three packet fragments (in decimal) are as follows:
Router Sequence Number Field The router sequence number field specifies the router sequence number of the client node or router that sends the packet. See "Implementation Overview" earlier in this chapter for a description of sequence numbers.
Metric Field The metric field specifies the metric assigned to the interface where the packet's sender sent the packet. For example, if a router sends a packet on an Ethernet interface, the metric field specifies 2.
This metric field has these two uses:
![]()
To synchronize the metrics assigned to any WAN point-to-point connection when different line speeds are configured on each end. Examples of these connections include HDLC, block asynchronous, X.25 serial line, and TCP/IP server-to-server connections. Client nodes or routers use the slowest speed (that is, the highest metric value). ![]()
To deliver metric information on source routes to client nodes. Because client nodes do not store metric information for source routes across specific Token-Ring bridges, client nodes must request this information from their routing server. When the routing server receives the routing request from the client node, it calculates the metric for the source route in the received routing request packet's Token-Ring header. The routing server then returns this metric in the metric field of the routing response.
Example Synchronizing Routing Metrics
Two VINES servers, Server A and Server
B, are connected by an X.25 virtual circuit. The X.25 line that
connects Server A to the PDN is configured for 19.2 Kbps. The
X.25 line that connects Server B to the PDN is configured at
56 Kbps. After receiving a sequenced RTP packet with a header
containing the metric for a 19.2 line from Server A,
Server B uses the 19.2 Kbps metric for the virtual circuit.
Sequenced update packets may or may not contain tuples following the update packet header. Client nodes never include any tuples in their sequenced update packets. On the other hand, routers include tuples only if new routing information must be propagated or specific routing information has been explicitly requested by another node (client node or router).
The list of tuples in a sequenced update packet provide routing information. The tuples follow the update packet header. These tuples are extracted from the entries in the network table. Each tuple consists of 12 bytes.
Figure 5-15 illustrates the tuple format. In this figure, one router - a VINES 5.5 server - sends a sequenced update packet containing one tuple to another router.
Network ID Field The network ID field identifies a given network ID in the current topology. A router never includes its information on its own network in the data portion. Receiving nodes extract the originator's network information from both the VINES IP header and the RTP header.
See Chapter 3 for more information on network numbers and VINES network layer addressing in general.
Metric Field The metric field specifies the cost to reach the network that the network ID field specifies. This cost is relative to the originator's view of the network topology. A metric of -1 (0xFFFF) indicates the network cannot be reached.
Sequence Number Field The sequence number field specifies the network sequence number, which can range from 0x0 to 0xFFFFFFFF. This number is the router sequence number of the router associated with the network. See "Implementation Overview" earlier in this chapter for more information.
Network Flags Field The network flags field indicates the type of network specified by the network ID field. Routers that are direct neighbors of the router associated with the network determine the network type. The following flags are supported:
0x1 (00000001) - The neighbor accesses the router across a broadcast medium, such as a LAN. This flag is never set if the 0x2 or 0x4 flags are set.
0x2 (00000010) - The neighbor accesses the router across a point-to-point connection, such as an HDLC serial line, block asynchronous serial line, X.25 virtual circuit, T1 LAPD connection, or ISDN server-to-server connection.
0x4 (00000100) - The neighbor accesses the router on a point-to-point basis across a non-VINES network, such as a TCP/IP network, a NetWare network, and so on.
0x8 (00001000) - The destination network is associated with a router that supports non-sequenced RTP only, or is reached through a router that supports non-sequenced RTP only. Sequenced RTP uses this flag to determine if the network sequence number should be validated.
Reserved Field This field is reserved for future use. At this time, it is always 0x0.
The maximum size of a sequenced update packet is 1440 bytes. Because of this limitation, an update or response packet can contain a maximum of 119 tuples. If a router must advertise more than 119 networks in a single update or response, the routing information spans multiple sequenced update packets.
Routers use the BOM and EOM control flags, data offset field, and packet ID field in the sequenced update header to facilitate the fragmentation and re-assembly of multipacket updates and responses.
BOM and EOM In a self-contained update or response, all the tuples fit in one packet. In this case, both the BOM (0x1) and EOM (0x2) flags are set in the control flags field. In a multipacket update or response, the BOM flag is set in the first packet only, and the EOM flag is set in the last packet only. All packets in between have neither the BOM nor the EOM control flags set.
Data Offset Each packet has a data offset field in the sequenced update header. This field provides the sum of tuples in the previous fragments of a multipacket update or response. RTP calculates this number from the VINES IP header packet length field, as follows:
VINES IP packet length - (VINES IP header size + RTP header size + updt header size)
--------------------------------------------------------------------------------------------------------------------------------
update data size (in bytes)number of tuples = update data size in bytes / tuple size in bytes
If a router always packs the maximum number of tuples allowed in a sequenced update packet (119), the first packet fragment has an offset of 0 (zero); the second has an offset of 119; the third has an offset of 238, and so on. These offsets allow RTP to reassemble packets received out of order.
Packet ID The packet ID field identifies each sequenced update and response to avoid the risk of re-assembling packet fragments from different updates or responses. The packet ID identifies the complete update or response. The same packet ID number appears in each packet fragment of a multipacket update or response.
Example Fragmentation and Reassembly of a Multipacket Update
A VINES 5.5 server, Server A, broadcasts a full update on a LAN that has one other VINES 5.5 server, Server B. The update is for synchronization purposes, and is performed once every 12 hours. The update contains 250 tuples and spans three packet fragments. The first two fragments contain 119 tuples each, and the third contains 12 tuples. Figure 5-16 illustrates this update.