Previous PageNext Page

Chapter 4 - VINES Non-Sequenced Routing Update Protocol

Introduction

Note: This chapter discusses non-sequenced RTP only. This chapter does not discuss compatibility with sequenced RTP. Compatibility information appears in Chapter 5.

Assume that the client nodes and routers that appear in the examples in this chapter run product versions that support non-sequenced RTP, such as VINES 4.11.

VINES Non-Sequenced RTP Specification

Non-Sequenced RTP Packet Format

Figure 4-1. Non-Sequenced RTP Packet Format

Table 4-1. Operation Type Field Values

Table 4-2. Node Type Field Values

Table 4-3. Controller Type Field Values

Note: The 0x0 and 0x1 values specify how non-sequenced RTP treats LAN cards, and do not really reflect whether the card is single buffer or multibuffer. For example, non-sequenced RTP treats some multibuffer cards as single buffer cards, and as a result, uses 0x0 in the controller type field.

When VINES 5.5 (or greater) client nodes implement non-sequenced RTP, the controller type is always 0x1.

Table 4-4. Machine Type Field Values

Routing Request Packets

Figure 4-2. Sample Routing Request Packet

Routing Response Packets

Figure 4-3. Sample Routing Response Packet

Routing Redirect Packets

Figure 4-4. Sample Routing Redirect Packet

Figure 4-5. Sample Routing Redirect Message

Figure 4-6. Routing Redirect in a Source Routing Environment

Table 4-5. Routing Redirect Message Fields

Rules for Generating and Processing Routing Redirect Packets

The router must forward a non-broadcast packet on the same interface where it was received from the last forwarding node.
The second high-order bit of the transport control field in the VINES IP header of the non-broadcast packet is set, giving this field a value of 0x40. This setting indicates that the last forwarding node supports redirects.

The router uses different source routes to reach both the last forwarding node and the preferred gateway. This means that the last forwarding node, the router that sends the redirect, and the preferred gateway are all on different rings.
The source routes do not traverse the same rings or bridges.

Figure 4-7. Router Does Not Generate a Redirect Packet

Processing Redirect Packets that Contain Source Routes

1. The last forwarding node checks the redirect packet to see if source routing information is included.

2. If source routing information is included in the redirect packet, the last forwarding node takes the following actions:

- If the last forwarding node uses a source route to reach the router that sent the redirect packet, the last forwarding node assumes the preferred gateway is on the same ring as itself and ignores the source routing information in the redirect packet.

- If the last forwarding node does not need the received source route to reach the server that sent the redirect packet, the last forwarding node saves the source routing information in the neighbor path entry for the preferred gateway.

3. If no source route is included in the received redirect packet, the last forwarding node does one of the following actions, depending on whether a source route is needed to reach the router that sent the redirect packet:

- If a source route is needed to reach the router that sent the redirect packet (that is, the packet was received over Token-Ring bridges), the last forwarding node concludes that the preferred gateway and the router sending the redirect are on the same ring. The last forwarding node copies the source route that it uses to reach the router that sent the redirect packet into the neighbor path entry for the preferred gateway.

- If a source route is not needed to reach the router that sent the redirect packet, the last forwarding node assumes that the preferred gateway and the router sending the redirect packet are on the same ring as the last forwarding node.

Example Redirect Packets in a Source Routing Environment

Figure 4-8. Last Forwarding Node and Router Sending the Redirect are on the Same Ring

Length of the source route that it uses to reach the preferred gateway
Source route that it uses to reach the preferred gateway

Verifies that the router that sends the redirect is on the same ring (that is, no source route needed to reach this router)
Copies the source route and its length in the redirect packet into the neighbor path entry of the preferred gateway

Example Redirect Packets in a Source Routing Environment

Figure 4-9. Last Forwarding Node and Preferred Gateway Are on the Same Ring

Length of the source route that it uses to reach the preferred gateway
Source route that it uses to reach the preferred gateway

Verifies that the router sending the redirect is on another ring (that is, a source route is needed to reach this router)
Ignores the source routing information in the redirect packet because it knows that the preferred gateway is on the same ring

Example Redirect Packets in a Source Routing Environment

Figure 4-10. Preferred Gateway and Router that Sends the Redirect Are on the Same Ring

Verifies that the router sending the redirect is on another ring (that is, a source route is needed to reach this router)
Concludes that the preferred gateway and the router sending the redirect are on the same ring
Assumes that the same source route that it uses to reach the router sending the redirect packet can also be used to reach the preferred gateway
Copies the source route used to reach the router that sends the redirect into the neighbor path entry of the preferred gateway

Routing Update Packets

They inform neighbors that the client or router transmitting the packet is still on the network. If a neighbor on a LAN is not "heard from" for 6 minutes, the remaining client and routers on the LAN remove the neighbor from their routing tables.
They propagate news of network changes through the network. When neighbors that act as routers receive RTP update packets containing news of network changes, they propagate the news to their neighbors on all of their interfaces (including the interface on which they received the news). This process continues, from router to router, until the news reaches all the routers in the network.

Figure 4-11. Sample Routing Update Packet

VINES Non-Sequenced RTP Implementation Notes

Neighbor table
Network table
Routing metrics
Routing table flags
Routing table timers
Information exchange algorithms

Neighbor Table Implementation

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.

Table 4-6. Neighbor Table Fields

Table 4-7. Neighbor Path Fields

Table 4-8. Interface Metrics

T1 LAPD Metric

46 - (number of DS0s)

Source Route Metric

(number of intermediate bridges * 5) + local interface metric

(2 * 5) + 4 = 14 ticks

Figure 4-12. Sample Metric for a Source Route

NetWare Metric

2 * IPX/SPX metric

2 * 6 = 12

Figure 4-13. Example of Routing Metrics with NetWare Connections

Network Table Implementation

Table 4-9. Network Table Fields

Selecting Neighbor Paths and Routes

One route to a neighbor destination stored in the network table
Multiple neighbor path entries to the same destination stored in the neighbor table

If the router supports non-sequenced RTP only, the router favors any VINES route over any route that uses a non-VINES protocol, such as a route with a TCP/IP server-to-server link.
If the router supports sequenced RTP, the router chooses equal-cost routes at random, regardless of whether non-VINES protocol stacks are involved.
The router chooses the route at random if all routes to the destination have equal cost and are VINES-only (that is, no other protocol stacks such as TCP/IP are involved).

Routing Table Flags

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

First Route Suppression Period

Example Unreachable, Non-Neighbor or Router

Second Route Suppression Period

Routing Table Timers

Table 4-10. Routing Table Timers

Example RTS_AGE Timer

4 (6 minutes to 71/2 minutes) - The destination is a neighbor on a LAN or is reached by way of a gateway that is a LAN neighbor.

0xFFFF (-1) - The destination is a neighbor on a WAN or is reached by way of a gateway that is a WAN neighbor.

Example RTS_CAGE Timer

How Routing Tables Are Maintained by Non-Sequenced RTP

When no network changes take place
When a router comes on line or goes off line
When a client node comes on line or goes off line
When a client node communicates outside its logical network
When the "help thy neighbor" scenario takes place
When routers initialize WAN connections
When a routing metric changes
When an equal cost metric is received from a new gateway

When No Network Changes Take Place

Note: Third-party routers may allocate a buffer that exceeds 1200 bytes. In this case, VINES, ENS, and ENS for UNIX servers will be able to receive topological data that exceeds 1200 bytes, but will not transmit topological data in excess of 1200 bytes.

When a Router Comes On Line

1. The new router announces its arrival by broadcasting routing update packets to neighbors.

2. Neighbor client nodes and routers perform the algorithm for processing received routing update packets and add this router to their neighbor tables. Routers also add this router to the network table.

Neighbors use the source address in the VINES IP header and the metric for the interface where the routing update packet was received to create the table entries.

3. The routing update packets from neighbor routers and client nodes "build" the new router's routing tables.

Routing update packets from neighbor routers contain the network ID of each router in the network and metrics for reaching them. The routing update packets increase in size as the number of routers in the network increases.

Routing update packets from client nodes just contain the RTP header.

4. News of the new router's arrival is propagated through the network. Neighbors of the new router broadcast routing updates to their neighbors, which in turn broadcast updates to their neighbors, and so on.

Neighbors of the new router
Non-neighbors of the new router

1 . The neighbor checks the neighbor table to see if an entry exists for the new router.

2. Because no entry for the new router exists, the neighbor must create one. The neighbor extracts the LAN address (if applicable) from the data link header and the source VINES internet address from the VINES IP header.

3. The neighbor uses the LAN address, VINES internet address, and metric for the interface where the routing update packet was received to create an entry for the new router in the neighbor table, and a corresponding neighbor path entry. The router sets these entry elements:

- The RTS_AGE timer in the neighbor path entry for the new router

- NBFLAGS in the neighbor path entry to indicate that the new node is a router

- NBMTYPE and NBCTYPE in the neighbor path entry to 0x1 to indicate fast processor and multibuffer controller respectively

4. Routers also use the VINES internet address and interface metric to create an entry for the new router in the network table.

The router initializes the NETGATE pointer to point to the entry for the new router in the neighbor table.

If the neighbor has no WAN neighbors, the neighbor sets the RTS_AGE timer and the RTF_UP and RTF_GATEWAY flags.

If the neighbor has WAN neighbors, the neighbor sets the RTS_CAGE timer and the RTF_UP, RTF_GATEWAY and RTF_CHANGE flags.

On WAN interfaces, the router broadcasts as soon as it receives news of the change. The router broadcasts routing update packets that contain only the changed tuples from the network table. The router broadcasts routing update packets that contain news of the change five times on WAN interfaces, after which the RTF_CHANGE flag is turned off.

5. Routers include the VINES internet address and metric for the new router in a tuple in the next routing update broadcast. Routers that act as routers broadcast on all interfaces, propagating news of the network change.

Example Neighbor of a New Router

Figure 4-14. New Router Announcing Itself to a Neighbor

1. The router checks the neighbor table and the network table to see if the appropriate entries exist for the router where the routing update packet is received.

2. The router compares the tuples in the received routing update packet to the corresponding entries in its network table. The router sees that a tuple exists in the routing update packet that does not have a corresponding entry in the network table.

3. The router uses the VINES internet address and metric in the new tuple to create an entry for the new router in the network table.

The VINES internet address becomes the destination address.

To calculate the total metric to the destination, the router adds the metric in the tuple to the metric for the interface where it received the routing update packet. If the router has multiple interfaces to the router that sent the tuple, the router adds the metric for the fastest interface. For example, if a router receives a tuple from another router, and the two routers are connected by both a 4-Mbps Token-Ring LAN and an Ethernet LAN, the router receiving the tuple adds the metric for the Ethernet LAN.

The router initializes the netgate pointer to point to the entry in the neighbor table for the router that sent the routing update packet. This means that the router sending the routing update packet becomes the gateway to the new router.

If the neighbor has no WAN neighbors, the neighbor sets the RTS_AGE timer and the RTF_UP and RTF_GATEWAY flags.

If the neighbor has WAN neighbors, the neighbor sets the RTS_CAGE timer and the RTF_UP, RTF_GATEWAY and RTF_CHANGE flags.

4. Routers include the VINES internet address and metric for the new router in a tuple in the next routing update broadcast. Routers broadcast on all interfaces, propagating news of the network change. When they receive news of a network change, routers broadcast news of the change immediately on all LAN and WAN interfaces.

On LAN interfaces, routers broadcast full routing updates.

On WAN interfaces, the router broadcasts routing update packets that contain only the changed tuples from the network table. The router broadcasts routing update packets that contain news of the change five times on WAN interfaces, after which the RTF_CHANGE flag is turned off.

Routers that receive the changed tuples on WAN interfaces turn the RTF_PERMANENT flag on for the network entries that are created from these tuples.

Example Non-Neighbor of a New Router

Figure 4-15. Router Receiving News of a New Non-Neighbor

When a Router Goes Off Line

LAN neighbors
WAN neighbors

1. When a routing update packet is not received from another router on a LAN interface for six minutes (RTS_AGE expires), the neighbor routers turn off the RTF_UP flag and sets the metric to 0xFFFF in the network entries for the following nodes:

- The router that left the network

- All destinations for which the router acted as a gateway

The neighbor routers also delete the entry for the router that left the network from the neighbor table.

If the neighbor router has WAN interfaces, the router sets the RTF_CHANGE flag in the changed network entries.

2. The router immediately broadcasts news of the change to all of its remaining neighbors. The 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 VINES internet address and a metric of 0xFFFF.

On LAN interfaces, the router broadcasts full routing updates with tuples for both unreachable routers and reachable routers.

On WAN interfaces, the router broadcasts routing update packets with only the tuples for the router that left the network and destinations reached through it.

1. The neighbor routers turn off the RTF_UP flag and set the metric to 0xFFFF in the network entries for:

- The router that left the network

- All destinations for which the router that left the network acted as a gateway

2. The router sets the RTF_CHANGE flag in the changed network entries. The router also deletes the entry for the neighbor that left the network from the neighbor table.

3. The router immediately broadcasts news of the change to all of its remaining neighbors. For the router that left the network and for each destination for which it previously acted as a gateway, neighbor routers include a tuple in the routing update packet. The tuple contains the VINES internet address and a metric of 0xFFFF. This metric tells other nodes that the router has left the network and destinations reached by way of it are now unreachable.

On LAN interfaces, the neighbor broadcasts full updates that contain news of the change.

On WAN interfaces, the router broadcasts routing update packets that contain only the changed tuples from the network table.

When a Client Node Comes On Line

The routing server's data link address in the data link header
The routing server's source VINES internet address in the VINES IP header
The interface metric of the interface on which the assignment response packet was received

A LAN
A dial-in line

1. The client node broadcasts a routing update to all neighbor client nodes and routers on the LAN. The broadcast packets contain an RTP header only and no tuples. If the client node has source routing enabled, it only sends updates directly to the routing server.

The neighbor client nodes and routers use the following information in the incoming routing update packets to add the new client node to their neighbor table:

- The client node's data link address in the data link header

- The client node's source VINES internet address in the VINES IP header

- The client node's machine type, node type and controller type in the VINES RTP header

2. All neighbors respond with routing update packets, which build the new client node's neighbor table.

When a Client Node Goes Off Line

When a Client Node Communicates Outside Its Logical Network

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.

2. The client node sets the RTF_TRANSIENT flag and the RTF_METRIC flag to indicate that the entry needs a better metric.

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.

3. After 200 milliseconds, the client node sends a routing request packet to the routing server. If the client node does not receive a response, it continues to send a routing request packet every 5 seconds.

4. Routing server replies with a routing response packet that contains a full routing update. The client node just uses the entry for reaching the destination it wants to communicate with, and discards the rest.

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.

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. The timer that controls the transmission of the routing request packet is called the mtimer.

5. If there is a better route for reaching the destination, the routing server will send a redirect packet to the client node, telling the workstation about the better route.

When Routers Initialize WAN Connections

On HDLC serial lines and X.25 virtual circuits, the router that initiates the connection sends a routing request packet every 30 seconds until the router on the other end responds with a routing response or update packet.
On permanent X.25 virtual circuits only, the router that initiates the connection must send a routing request packet to force the router on the other end of the connection to send a routing update packet. This insurance measure is designed for situations in which the router on the other end of the connection was already up from a previous instance of this circuit.
On block asynchronous serial lines, the routers on each end of the line send a routing request packet every 20 seconds until a response or update packet is received.

When the "Help Thy Neighbor" Scenario Takes Place

A WAN neighbor advertises that a network is unreachable.
The router can reach the advertised network through another gateway. If the router reaches the advertised network through the WAN 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 WAN neighbor.
The router can provide an alternate route to the network that its WAN neighbor can no longer reach.

1. Marks the network entries that are advertised as unreachable with the RTF_CHANGE flag

2. Includes these entries in the "changes only" routing update that is sent to the WAN neighbor

3. Advertises these entries in the next scheduled routing update

Figure 4-16. Help Thy Neighbor

When a Routing Metric Changes

A cheaper cost (that is, the metric is less than the one used previously)
A greater cost

Sets the RTF_SUPPRESS1 flag to begin the first suppression period, followed 1 minute later by the setting of the RTF_SUPPRESS2 flag
Sets the metric for reaching the destination to 0xFFFF
Sets the RTF_CHANGE flag if it has WAN neighbors

Sets the destination to unreachable (-1)
Sets the RTF_CHANGE flag if it has WAN neighbors

When an Equal Cost Metric Is Received from a New Gateway

Previous PageTop Of PageNext Page