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:
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.
(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.
1 2 |0 |8 |6 |4 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RSPF Version #| Type (RRH) | Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Full IP Address of sending router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | last packet sent seq. # | flags | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | plaintext |. . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Parameters--
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.
Last Modified: Wed, 22 Nov 2000
Copyright © 2000 Craig Small