RSPF Specification - Introduction and Version Notes

I. Introduction

The packet radio environment is a very difficult one for TCP/IP to run on. As typically implemented in the Amateur Service, it provides very low bandwidths within severely constrained implementations. The most common radio technology has been 1200 baud single-frequency operation, although higher speeds and some full-duplex operation are also found. Virtually all amateur packet radio TCP/IP activity (the AMPRnet) makes use of personal computers, most with severely constrained memory address space.
In this environment, automatic routing of IP packets has not been the norm. Routing protocols designed for other environments are rarely satisfactory. Manual route tables are common. Most amateur packet radio operation to date does not even make use of IP; instead, it converges applications directly upon a source-routed frame relaying protocol called AX.25. Improved routing support will be an important factor in the success of IP.
Many IP and other wireline networks have implemented link state routing based upon Dijkstra's "SPF" (shortest path first) spanning tree algorithm. A wireline implementation of SPF for IP is being standardized as the Open SPF Interior Gateway Protocol (OSPF), and an SPF procedure has been accepted by ISO as the standard "IS-IS" routing protocol for OSI connectionless networks [ISO10589]. A similar (and derivative) procedure can be applied to AMPRnet (Net 44) and perhaps to similarly-constrained packet radio networks. It is called Radio Shortest Path First (RSPF); this document describes the RSPF protocol, version 2.2.
RSPF occupies the role traditionally referred to in TCP/IP networks as an "Interior Gateway Protocol" (IGP), where "Gateway" means "router". It makes use of the services of the Internet Protocol. It is not inconceivable that a router could use both RSPF and another IGP, or communicate with another network using the Exterior Gateway Protocol (EGP). However these scenarios are not described in this document.
RSPF is intended to be implemented on nodes which serve as routers; its implementation on end nodes is optional, and not required for the end nodes to take advantage of routing services. Any IP station may be an end node giving no further consideration to routing.

I.1. Elements of RSPF

The RSPF protocol is designed for use by Internet-layer routing nodes (IP Gateways) in a packet radio network using the Internet Protocol. It is comprised of four major functions:

Acquisition of router-router adjacencies

Acquisition of end node adjacencies

Link state propagation

Spanning tree route decision making.

Its net result is the automatic maintenance of a least-cost routing table for use by IP Routing. RSPF is optimized for the geographically heirarchical addressing used in AMPRnet, but does not depend upon it.

RSPF is simpler than OSPF and IS-IS, as it is principally designed for personal computer implementation within the Amateur Radio Service. It also adds procedures to take advantage of packet radio's "semi-broadcast" nature.

I.2. Addressing convention

When an RSPF router communicates with an end node, it will typically deal with a 32 bit IP address. Routers themselves, however, also support node group addressing (fewer than 32 bits need match). This follows the convention in the KA9Q NOS IP routing program, which permits a crude form of heirarchical addressing as well as allowing portable operations to override the defaults. RSPF looks for the match (node or node group) with the greatest number of matching bits. Only if the number of bits matched is equal, then the lower cost path will be used.
Thus a match to a full node address will override a "cheaper" path that matches its "subnet" (node group) of 24 bits, which overrides a 16-bit node group, etc., noting that AMPRnet node groups need not follow rigid IP subnetting rules, and that AMPRnet is a single Class A net. In every case, a greater number of bits matched is considered a superior path to a destination than one that matches fewer bits, regardless of the value of the routing metric ("cost").
An extension of this is the handling of manual routes, which are routes defined by a manual entry into a table. Manual routes provide a useful starting point during the RSPF convergence, and are required when RSPF implementation in a given area is limited. As an order of precedence, whether a route is manual or RSPF-generated should only be used to break ties equal in both subnet size and cost; RSPF-generated routes then take precedence.

I.3 Subnetworks

The generic term used herein for the layer directly beneath IP, creating the adjacency between two IP nodes, is subnetwork. A routing protocol gains efficiency by recognizing the nature of all subnetworks that it supports. RSPF is intended to work across a specific set of subnetworks that occur in packet radio. (Note that this use of "subnetwork" is consistent with OSI terminology; the function of the IP "subnet mask" in other IP routing protocols is herein referred to as "node group".)

I.3.1. Classification by topology

All subnetworks may be classified according to topology. An initial division is made between broadcast-topology subnetworks and general-topology subnetworks.

I.3.1.1 Broadcast topology

A broadcast-topology subnetwork is one in which a node may send a single packet which is propagated to all other nodes, which receive it with high probability. Ethernet and FDDI are examples of broadcast-topology subnetworks.

I.3.1.2. General topology

A general-topology subnetwork is any that does not offer a reasonably reliable broadcast service. Within this classification, an extreme case is a point-to-point subnetwork, with only two nodes. Examples of point-to-point subnetwork protocols are PPP, SLIP and LAP-B.

Packet-switched networks are typically general-topology, with wireline networks conforming to CCITT Recommendation X.25 being one example.

Another general-topology subnetwork found in packet radio is the type implemented by "TheNet" (from NordLink) and its clones. Its network layer offers a datagram service to an addressed point, not a useful broadcast service, and again with no guarantee of delivery.

I.3.1.3. Topologies found in packet radio

Within the amateur packet radio world, an example of a broadcast-topology subnetwork might be a packet "LAN" implemented using a full-duplex RF repeater. However, these are relatively rare; the typical single-frequency radio "LAN" using CSMA or Aloha operation, typified by AX.25 subnetworks, fails the test of broadcast topology. It loses too many packets for routing to be able to trust unacknowledged delivery. This is often due to the "hidden transmitter syndrome" (HTS), the details of which are beyond the scope of this document. However, some steps may be taken in order to make use of the near-broadcast nature of these "LANs". These are "semi- broadcast" subnetworks.

I.3.2. Adjacencies and Subnetwork Access Points

The purpose of any subnetwork is to create adjacencies between IP nodes. Each IP node is identified at the IP layer by its IP address. Each node in turn identifies each of its adjacencies as a Subnetwork Access Point (SNAcP). A SNAcP is identified within the router by the 2-tuple {Subnetwork address, Hardware port}. In the case of a point-to-point subnetwork, the subnetwork address component is null. In the case of some other subnetworks, it may be almost arbitrarily complex. For example, an AX.25 "address" may consist of a string of addresses by which the AX.25 subnetwork performs source-routed frame relaying.

Thus the actual routing information includes 3-tuples consisting of the IP destination address or node group as the key, followed by the two elements of the SNAcP. The output of RSPF is this routing table.

I.3.3. Connection-oriented vs. connectionless subnetworks

IP is a connectionless (datagram) network protocol, and supports both connection-oriented (virtual circuit) and connectionless (datagram) lower layers (subnets). In a network with a high packet loss rate, the local retransmission provided by a connection-oriented datalink may substantially improve overall throughput. However, in a high-speed dedicated backbone, particularly one implemented using full-duplex radio or wireline links, connectionless links may provide better overall performance. The choice of which to use is a local matter; RSPF will work with both.

Connection-oriented subnetworks are assumed here to operate in assured mode, as is provided with LAP-B. No connection-oriented non-assured subnets, such as wireline Frame Relay, are contemplated for packet radio RSPF use at this time.

The reliability of the routing information, however, may be somewhat greater with connection-oriented datalink procedures. This occurs both because the link will have more reliable propagation of network state information, and because these will give more rapid indication of a physical link failure. In a true broadcast-topology subnetwork, connectionless operation should suffice. Much of RSPF's uniqueness comes from permitting connectionless operation over unreliable media, a combination that appears to be in much demand within the AMPRnet community.

I.4. Relationship to other protocols

All packets specific to RSPF shall be exchanged inside IP packets using a protocol identifier which, pending formal assignment of one, shall be 73. Such IP packets shall be sent with a time to live (TTL) value of 1. If broadcast procedures are used over AX.25, connectionless AX.25 UI frames shall be sent, with a broadcast address "QST-0" in the AX.25 address and an IP address ending in [.255], indicating multicast.
This permits different ports on a router to have different broadcast addresses. (A router can also "read the mail" on passing radio packets not addressed to it; such procedures are for further study.) Equivalent procedures may be developed for other subnetworks.
Note that in this document, "subnetwork" and "data link" are synonymous, and refer to the layer over which IP packets are exchanged.

I.5. Change history

I.5.1. Changes for Version 2.1. (October, 1989)

RSPF draft 2.0 was released in June, 1988, as the first nearly- implementable version. It was first implemented in September, 1989 by Anders Klemets. Version 2.1 reflects changes whose need was discovered during this implementation. These changes are both editorial and, in a few cases, substantive.

The format of the Routing Update packet was slightly modified. In order to prevent fragments of two or more different routing update messages from being erroneously merged, an Envelope ID was added to each such packet, with the same Envelope ID on all fragments of a multi-packet message. The term for such a message is now "envelope"; it contains one or more "bulletins", each of which originated from a single router.

There are no longer separate packet types for Full Routing Update and Partial Routing Update. Instead, they are distinguished by the value of the subsequence number, which is always 0 for Full Routing Updates and is never 0 for Partial Routing Updates. A given envelope may contain both types of bulletin.

Cost is now set on the basis of receiver instead of transmitter. This permits the automatic link quality adjustment to operate on the basis of locally-received traffic.

It is explicitly stated that upon creation of a new router-router adjacency, the routers exchage full routing information. This allows routers to initialize themselves with a reasonably complete map of the network.

1.5.2. Changes for Version 2.2 (January, 1992)

Version 2.1 was actually implemented and deployed in several locations, providing a useful input to this version. The changes in Version 2.2 are intended to be compatible, at the message level, with Version 2.1; however, the internal organization is different. This should preserve interoperability in the face of several changes. Some descriptive changes were made in this document in order to make it less dependent upon any one implementation or network.

The major change is the generalization of the subnetwork and the SNAcP; this allows arbitrary subnetworks to be converged under RSPF. Behavior of "private" and "manual" routes is also now explicitly described.

The behavior of RSPF in acquiring new adjacencies is also clarified with a new state machine. A connectionless adjacency is never put into general use until it is successfully tested. This fixes an ambiguity in Version 2.1 which led to the immediate creation of a "suspect" route upon receipt of a Router-Router Hello message, even if it failed successive pings.

Sequence number behavior for bulletins is also clarified, with a new initialization procedure. The number space is now linear and finite.