RSPF Specification - Acquisition of router-router adjacencies

II. Acquisition of router-router adjacencies

For RSPF to operate correctly, all routers must remain reasonably current as to the state of the network at large. This is handled by the propagation of "bulletin" messages among routers. End nodes need not concern themselves with this; they will normally communicate through one selected router at any given time, for all (non-adjacent) destinations (not seen by ARP or other lower-layer procedures). End nodes can also, of course, connect to each other directly, bypassing RSPF.
Each router maintains an adjacencies table. Each router's adjacency table lists the following information for all other nodes, both routers and end nodes, from which it directly receives packets over a subnetwork:

Adjacent node IP address (i.e., 44.56.4.44)
Adjacent node subnetwork (eg.,AX.25) address (eg., K1IO-0)
Subnet (hardware) used (i.e., AX0)
Subnet cost (i.e., 4)
Number of packets heard since last RRH update (i.e., 50)
Packet sequence number in last RRH update (i.e., 2593)
Time of last RRH update (i.e., 2130).
Link state (tentative, good, suspect, lost)
Type of service (connection-oriented, connectionless)

Table II.1. Adjacencies table.

II.1. Router-router hello

For the backbone to create its topology automatically, there must be a way for routers to discover each other with minimal overhead. For this purpose, a router-router hello (RRH) message is provided. Periodically, based upon the value of timer "rrhtimer", the router sends out the RRH message to the subnet multicast address and IP multicast address. RSPF makes no assumption of reciprocity (that links are bidirectional); receipt of an RRH packet provides the receiver with information about a potential one-way (received) adjacency.
It is noted, however, that while the route testing procedure does not require reciprocity of subnetworks for "ping" testing, some implementations will require a successful two-way ARP exchange before the ICMP Echo packet can be sent. This often results in some requirement for reciprocity in practice, even though it is not a characteristic of RSPF.

II.2. Connection-oriented procedure

If a router uses connection-oriented subnet procedures on a given interface, then when a router receives an RRH packet on such an interface, it checks to see if it already has a link to that packet's originator in its own adjacencies table. If not, and the interface is of a broadcast nature (reliable or unreliable), it waits a random period of time (example for AX.25: within the range of 0 to 10 times the link's value of T1, DWAIT or SLOTTIME, and in any case much longer than the timers used within a CSMA or Aloha subnet such as AX.25) and then attempts to establish a connection in the usual manner. For example, in an AX.25 subnet, the router initiates the connection with SABM; the distant router responds with the usual UA (link established) or DM (link rejected). Failure to initiate a connection (i.e., receive a UA) terminates this procedure; no adjacency is added.
If a two-way connection has been established, then both routers add the link to their adjacency tables. While the existence of this route is set reciprocally, the cost of each side of the route is set separately for each side of the connection. Cost is propagated in the routing update (link state) packet. Thus the adjacency between two routers is not actually used for real traffic until the first routing update packet exchange has taken place. (This may be useful in dealing with the situation where a UA is lost during link initiation; procedures for coping with this known LAP-B problem are for further study.)
Loss of an adjacency may then be noted by the loss of the subnet connection. When this occurs, the router removes the adjacency from its adjacency table and follows the "bad news" procedures outlined below for link state propagation. (If this cannot be determined by the implementation, then "ping" procedures as in 1.3.2 below may be useful.)

II.3. Connectionless procedure

If a router uses connectionless datalink procedures to its own adjacencies (most suitable to low-loss links such as broadcast-topology or reliable general-topology subnetworks), then when a router receives an RRH packet, it checks to see if this adjacency is already in its adjacency table.

II.3.1. Acquisition of connectionless adjacencies

In practice, reliable broadcast topology is unusual in the packet radio arena. Thus, the acquisition of a new adjacency begins by setting the link status to "tentative". A tentative-state adjacency is tested by attempting to exchange a packet (ICMP echo) with it, up to a settable "maxping" number of times. If successful, the link state is raised to "good". If unsuccessful, the adjacency is returned to null, ignored, and not added to any tables. If the destination is already reachable via a different route, then this prior route should not be discarded; it should be returned to use if the newly-tested adjacency fails, or if the new adjacency has a higher cost. (This may be implemented with a "don't route" function in IP, bypassing the existing IP route table, passing normally-hidden subnet information to and from RSPF.)

An alternative to ICMP echo for AX.25 and other broadcast and semi-broadcast subnets is to directly use ARP to test the adjacency. In practice, ICMP will require ARP anyway. This option raises questions of layering, but may solve other problems, such as the existence of a prior IP route when the available IP layer does not support "don't route".

II.3.2. Loss of connectionless adjacencies

Loss of an adjacency may be noted by timeout; if no RRH message is received, and no frames have been received from the adjacent router for a period of time "suspect timer" (initial suggestion: slightly over twice the maximum interval "rrhtimer" between RRH messages), then the adjacency state becomes "suspect". The router should attempt (a settable number of times "maxping") to exchange a packet (ICMP echo) with the suspect adjacency; if unsuccessful (after the usual number of retries), the adjacency is marked "lost". It may also be marked lost if other attempts to send data through that router fail, such that the implementation determines that there is a high probability that the link is lost. (However, no obvious means of doing this is noted. Thus the "ping" is more likely to be required.)

II.3.3. Link states

For purposes of route table generation and link state propagation, a link whose state is "tentative" or "lost" is "bad"; bad routes are not used in creating the routing table. Tentative routes are not propagated; newly bad ("lost") routes are propagated by the link state ("bad news") propagation procedure, and then dropped. Links whose state is "good" or "suspect" are used for route table generation and are propagated.

Note that if a link is connection-oriented, there may be no need for either a suspect or tentative state; these links are either "good", "lost", or "null".

Table II-1. State transition table for adjacencies.
(Null) ----------> Tentative -----------> Good <----\ traffic or RRH heard | ping succeeds \ \-----/ RRH heard \ \--------->Null \---| no RRH/tfc heard ping fails \ v \<-Lost<---Suspect ping fails

II.4. Manual procedure for general-topology subnetworks

A general-topology subnetwork may have adjacencies which cannot be detected by means of a broadcast-oriented (RRH) procedure. These links cannot be automatically added, and alternative procedures are required. These links may be connection-oriented or connectionless; the link state transition procedure is determined accordingly.
The most general way to handle this is to insert these adjacencies manually. The state of these adjacencies is determined the same way as with links that are created by hearing RRH messages. Note that when an adjacency is manually-initiated across a general-topology subnet, the initiating side of the link takes action, while the responding side should accept the incoming connection request, and both sides see the link. Thus only one side of the adjacency actually needs to have a manual entry. If a connection already exists to another node across a subnetwork, then there is no need to initiate a second connection simply because a manual entry exists.
In some cases (such as source-routed frame relay "digipeating" over AX.25), a manual route can be entered to a destination whose first hop, at least, crosses a broadcast-style subnetwork. This type of adjacency may require manual intervention in the ARP function as well.

II.4.1. Semi-automatic discovery

In addition to manually-created links across a subnetwork, there exist cases in which the RSPF router is also a subnet router, and is thus privy to routing exchange information generated by that subnetwork. (An example is a node which implements both RSPF and "TheNet".) If the subnetwork provides sufficient information such that support of RSPF by another node can be inferred (i.e., by a distinctive subnetwork address), then RSPF may sequentially initiate appropriate procedures to determine whether or not a useful adjacency exists.

Translation of routing metrics into an RSPF link metric is handled on a case-by-case basis. Specific convergence procedures for any such subnetwork require further study.

Table II-2. Coding of the RRH PDU.

		  1	 	  2
|0              |8              |6              |4              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RSPF Version #| Type (RRH)    | Checksum                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         Full IP Address of sending router                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  last packet sent seq. #      |  flags        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|        plaintext                                              |. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Parameters--

RSPF Version Number: Version number of this protocol "22". This packet format is identical with version 21; RSPF22 should accept "21" as valid. Future versions "30" and above may be incompatible. (Accept anything 2x on receive.)
Type: Value of 3 for RRH.
Checksum: IP-style checksum
Address: Full IP address of sending router
Last packet sent sequence number: An integer (mod 65536) incremented by 1 for every frame sent by the subnet across this interface. This value allows receiving entities using connectionless procedures to use the automatic link quality measurement technique described in SectionII.5.
Flags: The low-order bit is 1 if connectionless datalink is preferred on this interface; 0 if connection-oriented is preferred. (Set by system management based upon anticipated link quality.) Other bits are reserved (sent 0; ignored on receive). Note that some implementations do not support this; "preferred" does not mean "mandatory".
Plaintext: An optional text message (length may be up to maximum size remaining in datalink PDU). This might serve, for example, to "broadcast" the router's existence to persons who might be "reading the mail" (monitoring a radio channel promiscuously). It may be noted that a very short RRH message can be received intact across a subnetwork that otherwise might not be capable of supporting maximum-size packets with reasonable reliability. This should be taken into account when setting the value of Plaintext. An explicit minimum is not, however, stated.

II.5. Automatic link quality measurement

(This procedure was not tested in the implementation of RSPF 2.1, and is therefore considered highly experimental!) A connectionless link or subnetwork may have very reliable, or very sporadic, performance. Since there is no procedure for ensuring the reliability of packets sent over a connectionless link, a high rate of packet loss may occur without being detected by the routers. If this loss is high enough, another route may become a better choice; a high enough packet loss rate may be enough to mark a link as "down". The automatic link quality measurement procedure allows links which are not yet "down", but whose performance is substandard, to be noted.
Every router shall maintain, for each link, a count of all packets sent over each link. Every time an RRH message is sent, it includes the current value of this counter (modulo 65536). Every router also maintains, in its adjacency table, a count of the total number of packets received from said adjacency since the last RRH message, and the value of that counter as received in the last RRH message.
Upon receipt of an RRH message, the recipient router compares the value of the received packet counter with the last received value in the adjacency table. The difference (taking into account wrap-around at the modulus) is compared with the number of packets received since the last RRH message. (This works even if an RRH message is lost.) This packet loss ratio is then maintained as a guideline to determine link quality. If link quality falls below a settable threshhold, the link state is changed to suspect. Timestamp can also be used to compute packet arrival rate.
Connection-oriented data links presumably deliver 100% of attempted packets. A high-quality connectionless link, such as Ethernet/LLC1, will come close to this. However, single-frequency packet radio links are prone to packet loss for several reasons, including hidden transmitters, lack of collision detection, and rf interference. The packet loss ratio is useful in setting link cost, and may also be used to determine whether a link should use connectionless or connection-oriented procedures.
If a router reports, in its link update packets, that a given link has a cost of _n_, then its adjacencies (and only its adjacencies) may apply the packet loss ratio to adjust the cost which they maintain in their link state tables. These adjusted costs, rather than the received costs, may then be propagated to other routers.
Such procedures should be applied sparingly, as each change must be propagated and could, if used too frequently or inconsistently across a network, result in network-wide instability. A suggested (experimental) algorithm is as follows: A percentage threshhold x is set, as is a cost-adjustment factor y. If fewer than x% of packets are received during a measurement interval, the cost of that adjacency is multipled by y. For example, if x is 80 and y is 1.5, then an adjacency with a nominal assigned cost of 4 will be up-costed to 6 if only 70% of packets are received, but will be restored to 4 if 80% or more are received during the next measurement interval. The measurement interval is the time between RRH messages, which typically should precede routing update messages.