RSPF Specification - The Shortest Path First spanning tree algorithm

V. The Shortest Path First spanning tree algorithm

As a routing node comes onto the network, it acquires over time a complete list of adjacencies between other nodes on the network except as limited by the "horizon". Each adjacency (point to point link) within the entire known network has a "cost" associated with it. It should be noted that adjacencies, for the purposes of this algorithm, are "logical" and not necessarily physical; if a subnetwork link occurs below IP (as in AX.25 digipieating or TheNet), the two ends of the link are still adjacent. (Adjacency at the IP internet layer is based upon subnetworks, which may contain their own links.)
Cost is set for the receive side of each link. If the receiver and transmitter do not agree on cost, the network shall apply different routes for packets going in opposite directions between the same two end nodes. (This is not a problem. In a radio environment, one should NOT assume reciprocity across a link.)

V.1. Tables

V.1.1. Link State Table

Each router builds a _link state table_ (or links table) that lists, for every known link in the network (from every reporting router), the two ends and the cost of that end of the link. The ends are listed by an IP router address and, for the destination IP router address, a number of significant bits. This is what is updated by the bulletins and by good news/bad news messages. Adjacent links also are merged in from the adjacencies table.

Source IP address	Dest. IP addr/bits	Cost
44.56.4.44	44.56.4.128/32	5
44.56.4.44	44.56.4.12/25	10

V.1.2. Paths table

The goal of the SPF algorithm within RSPF is to build a _paths table_ which lists, for every reachable node (or node group approximation of fewer than 32 bits) on the network, that node address (or node group address and number of significant bits), the adjacent node used to get there (i.e., where you blast the packets to next), and the total cost of the path. This is done by building a spanning tree with the router doing the computation (the home router) as the root of the tree. The paths table thus lists the best way across the tree from the home router to all known destinations.

V.1.2.1. Route table

It should be noted that the only implementation of RSPF to date is within the KA9Q NOS package. This includes a route table which roughly corresponds to the paths table, trusting ARP to provide subnetwork information. However, RSPF routing makes nominal use of a logical route table which includes both the paths table entries and the subnetwork address required to reach the first adjacency. The structure of this table's implementation need not be defined here. It may, for example, be a logical union of the paths table relation (providing IP addresses) with ARP and related subnetwork table relations, using IP address as the common key. (Thus there is no RSPF route table per se. This corresponds to the logical route table in RSPF 2.1.) Or RSPF may supersede these tables with a separate route table including required hardware and subnetwork address information.

Entries in the route table include:

Destination IP Address
Destination IP Address number of bits (0-32)
Selected adjacency hardware interface
Selected adjacency subnetwork address string
Adjacency IP address
Cost

V.1.3. Trial table

Every router contains, for the purposes of building the tree, a _trial table_ that has three entries: Destination address/bits, adjacent node, and cost of this path. The paths table additionally has one more entry, the _parent_ node, which is the last hop before the destination. Thus in a path A -> B -> C -> D -> E, home router A views E as the destination, D as the parent, and B as the adjacency. Note that in the path from A to B, A is the parent node.

V.2. Building the paths table

Begin building the paths table by using the home router as the first node on the paths table. The cost to reach yourself is always 0, so make the first entry on the paths table as follows: Source=self, destination=self, parent=self, and cost=0. From here on in, parent is always (by definition of the SPF spanning tree) the node most recently added to the paths table.

Destination Adjacent Parent Cost

44.56.0.128 44.56.0.128 44.56.4.44 5

44.56.0.131 44.56.0.128 44.56.0.128 10

44.56.0.200 44.56.0.128 44.56.0.131 15

Paths Table showing relationship between destination, parent and adjacent nodes, where the home node is 44.56.4.44 and 44.56.0.200 is three hops away; all hops here have a cost of 5.

Paths Table showing relationship between destination, parent and adjacent nodes, where the home node is 44.56.4.44 and 44.56.0.200 is three hops away; all hops here have a cost of 5.
Destination	Adjacent	Parent	Cost
44.56.0.128	44.56.0.128	44.56.4.44	5
44.56.0.131	44.56.0.128	44.56.0.128	10
44.56.0.200	44.56.0.128	44.56.0.131	15

V.2.1. Scanning the links

The home router now scans its links table looking for all nodes (routers and end nodes) that are adjacent to the current parent node, except for links to nodes which are already on the paths table. (It is generally fastest to build the paths table by scanning the links table in order of increasing link cost.) Each of these new nodes is added to the trial table, except for the parent node (which is already on the paths table, so it can't possibly have a shorter path). The value of cost placed on the trial table is the cost of the link from the parent to the destination plus the cost from home to the parent node (which value is already on the paths table).

A node may only appear once in the trial table at any given time. If an adjacency is found to a node that is already on the trial table, a new entry replaces the existing entry if and only if the new total cost is lower. If the cost is higher, it is ignored. (If the costs are equal, then a "tiebreaker" is determined by treating the lower-numbered IP address as the lower cost. This will simply make the spanning tree more deterministic in case of tie.) Thus the trial table always contains the lowest cost path to each destination found so far.

Once all of the links from the parent node have had their chance to go onto the trial table, scan the entire trial table for the _one_ entry with the lowest total cost. This not need be a link from that parent node! In case of tie, pick the lower IP address (again just to be deterministic). Move this node to the paths table; guaranteed, there'll be no cheaper path to that node! The adjacency used for that node in the paths table is the adjacency to its parent node. Note that the parent _must_ already be on the paths table since that's the source of the parent; you're working your way outward.

This new addition to the paths table becomes the new parent node. Repeat the procedure above (from the beginning of V.2.1) until there are no nodes left on the trial table. This means you've completed the spanning tree and have found the least-cost path to every other node.

One of the router parameters is maximum_cost. If the cost to a given parent node exceeds this value, the procedure stops, since all subsequent entries in the route table will have a higher cost. This value has some semblane to the time-to-live parameter of the IP packet: It makes little sense to compute a routing table to nodes that cannot be reached within time-to-live. (Ideally, ttl will be implemented using a timer rather than a node counter, but this is difficult to do with some of the packet radio data link controller implementations; vis., TNCs.)

A router should recalculate its routes periodically based upon the current links table. How frequently depends upon the CPU load involved. Initial estimates are that it should be recalculated after receipt of every routing update bulletin: Partial calculations do not save enough CPU time to make them worthwhile.

V.3. Filling in the routing table

The route table in NOS (the KA9Q et al implementations of IP) contains, for each entry, the destination address, number of bits, interface, gateway and metric. RSPF 2.2 conceptually replaces this with a manual route table (essentially what exists in NOS without RSPF) and a route table which RSPF generates itself; when RSPF is activated, this latter table is used for packet routing.
The route table is filled in from the paths table after each time the SPF algorithm has finished. It takes entries from both the paths table and the manual route table. Order of precedence is important here. Manual routes have lower precedence than routes taken from the paths table, given an equal cost, but a lower cost manual route will override a higher-cost paths table entry.
Since the routing table will be periodically recalculated from scratch, implementation requires two separate route tables, one "in progress" and one "in service". When the route calculation is complete, the "in progress" table becomes "in service" and the old one is cleared for reuse. This allows packet forwarding to continue while the completed paths table is being converted into the route table. Calculation of the paths table and route table can require substantial CPU resources, and should not take precedence over packet forwarding.

V.4. Manual routes

A manual route table may also be maintained. This takes second precedence to RSPF-generated entries in generating the route table. Manual routes are useful defaults before RSPF generates routing entries, for destinations not reported on by RSPF, for creating node group adjacencies, and for interworking with other routing protocols. **Note that manual routes in RSPF 2.2 are (at least logically) not simply entries in the initial routing table, but are permanent (until changed manually) entries in a separate manual route table which is merged into the RSPF-generated route table as the last stage of each calculation of the route table. (As an implementation option, the manual route table could conceivably be interleaved with the route table, with a "manual" flag on these entries, but the manual entries behave differently.)
Note that all manual routes are considered as adjacencies. This is obviously wrong at times, but cannot be determined automatically. Thus the private flag is provided.

Entries in the manual route table include:

Destination IP Address
Destination IP Address number of bits (0-32)
Selected adjacency hardware interface
Selected adjacency subnetwork address string
Adjacency IP address
Cost
Flag: Private/non-private

V.4.1. Private routes

Any manual route may be flagged as private. These routes are used in calculating the route table, but are never propagated to other nodes. Default routes should always be defined as private, as they do not denote known adjacencies, only values that this node will use absent better information.

V.5. Secondary storage of routing information

This section is for study. It may be unnecessary because adjacencies will provide a full report to a router upon initialization of an adjacency.
Real implementations of RSPF, especially under single-tasking operating systems (such as MS/PC/DR-DOS), will not always run continuously without interruption. Nor will all end systems. When RPSF starts running, it has an empty links table, and depends upon manual routes until receiving links information from its adjacencies. On a packet radio network, given the low bandwidths, this convergence may take excessively long.
An implementation may work around this by storing, in non-volatile media (eg., hard disk) the information needed to quickly resume operation. This file (whose internal format is a local matter) should contain a timestamp and the last sequence number and subsequence number originated by this node, followed by the contents of the links table. This file should be stored after a new bulletin (with sequence or subsequence number) is transmitted. Only one copy of this file need be stored. Other tables may be optionally stored, for diagnostic purposes, but only the links table is required.
When RSPF begins to run, it looks for this file. If present, it checks the timestamp. If the timestamp is recent (suggested maximum age: no older than twice the rspftimer), then the file should be read into the paths table.