IV. Link state propagation
Link state information is propagated between routers within bulletin
envelopes, which are sequences of packets containing partial or full
copies of the sending node's link state table. Both point-to-point and
broadcast procedures are provided.
IV.1. Optional multicast/broadcast
Packet radio is inherently a broadcast medium. Packet radio networks,
however, do not necessarily offer a reliable broadcast service, even if
they happen to use a broadcast physical medium. It is still possible to
exploit the broadcast nature of the medium. RSPF link state propagation
procedures allow but do not require such multicasting.
If the link uses connectionless procedures for user data packet
exchange, then broadcast procedures should be used for link state packet
exchange. The converse may not necessarily be true: The threshhold of
loss that militates against connectionless transmission of user data may
be more stringent than that which call for non-broadcast transmission of
link state packets. Note that RSPF specifically permits its broadcast
procedures to be used over subnetworks that do not have the reliability
of true broadcast-topology subnetworks. This reduces the channel
utilization on radio links.
IV.2. Routing update bulletins
Routing updates are passed along from router to router via routing
update bulletins, which are broadcast within routing update envelopes.
Bulletin propagation is designed to make it highly likely that every
node within a given "horizon" eventually receives every routing update
message sent out by a given node.
IV.2.1. Sequence numbers
Every router originates information about changes in its own
adjacencies, as well as periodic retranmissions of its entire list of
adjacencies. These bulletins are then propagated among other routers.
The router whose adjacency information is being broadcast is called the
_reporting router_; this may be some hops away from the routers which
forward it to their own adjacencies. Each reporting router's bulletins
(adjacency updates) contain sequence numbers (and in some cases, a
subsequence number). These sequence and subsequence numbers are
generated by the reporting router and propagated; they are not changed
when a bulletin is relayed. They are incrememted by 1 every time a new
one is generated.
IV.2.1.1. Restored sequence numbers
If RPSF is restarted, after having been run previously run (i.e., in
event of a system restart) before all knowledge of that router has timed
out of the network, then sequence numbers beginning with 1 could cause
the network to fail to converge, as these bulletins will always appear
obsolete. A procedure is needed for routers to "catch up" with its
previous sequence number if it is still in the network.
When a router first goes into service, its sequence number is
initialized at 1 (or another low nonzero number). The router sends RRH
before it sends its first bulletin. This enables it to first receive an
update from its own adjacencies. Even if it sends a bulletin before
receiving one from its adjacencies, sending a bulletin with a sequence
number of 1 will prompt the adjacency to update it.
Whenever a router receives a bulletin, it examines the contents to see
if its own router number is included as a reporting router. If so, then
it resets its own sequence number to 1 greater than the sequence number
received. This enables the router to resume its sequence number
generation at a higher number than where it left off. A value of 0 is
never used for reporting. However, a router shall respond to receipt of
a bulletin with a sequence number of 0 with an update containing the
current sequence number. (The 0 is thus reserved for use as a "poll".)
IV.2.1.2. Sequence number exhaust
Modular (circular) numbers are not used in RPSF Version 2.2. Thus a
router may eventually exhaust its 16-bit number space, if it is in
continuous operation long enough (nearly two years, given 15-minute
updates). Should this occur, the router may reinitialize itself by
halting all bulletin origination for a period long enough for the entire
network to "forget" about that router's existence. Pending further
study, a period of two hours is recommended for RSPF in a typical packet
IV.2.2 Subsequence numbers
Bulletins may also carry change information incremental to previous
bulletins. These carry the same sequence number as the full routing
update bulletin to which they are reporting incremental changes; each
such partial routing update bulletin has a subsequence number. The
subsequence number is zero for a full routing update bulletin.
Every bulletin also has a horizon value, set by the reporting router,
associated with each of its constituent links. (A given reporting
router may have more than one constituent link, if it is a multi-port
router.) Every time a bulletin is propagated, each horizon value is
decremented by 1. When it hits zero, the bulletin is not propagated
further. Note that for horizon purposes, a bulletin's individual
constituent links may have separate horizons; when a link's horizon hits
zero, other links' adjacency information from the same reporting router
may continue to be propogated.
It should also be noted that if a given link has adjacencies with
different horizons, these must be treated as separate links, since
horizon is reported as a characteristic of a link. Such a circumstance
may occur, for example, when a router serves a node group. Adjacencies
within the node group are typically propagated with short horizons,
since they are only of local interest (i.e., to other nodes in or near
that node group). Similarly, the node group itself is propagated with a
long horizon, across a backbone. However, adjacencies outside the node
group may be propagated with long horizons, as they would not otherwise
be reached across a backbone dependent upon node groups for long-haul
IV.2.4 Routers table
Every router maintains within memory a routers table containing one
tuple for every other router on the network, excepting those which are
unseen because of a horizon. (An extreme case of this exception is an
end node running RSPF with a horizon of 1, whose existence is only known
to its own adjacencies.) This tuple contains the following elements:
- IP Address (router number)
- Last received bulletin sequence number
- Last received bulletin subsequence number
- Timestamp for when the data was received.
- Horizon remaining in bulletin when received
This table is used to coordinate the receipt and transmission of
bulletins, using either broadcast or non-broadcast procedures. If a
router chooses to use multiple IP addresses (as is commonplace on the
Internet where different interfaces may use different addresses), only
one IP address is used by each router for propagating link state
information. This is used as the router number.
IV.3. Flooding without congestion
A procedure is used to "flood" the network with link state information.
This is designed to minimize the total amount of information
transmitted, while maintaining an up-to-date data base on each router.
IV.3.1. Upon initialization of adjacencies
Bulletins are forwarded in a routing update envelope which may contain
one or more reporting routers' bulletins (adjacency lists), which are
flooded to the network. A bulletin envelope may actually concatenate
multiple reporting routers' bulletins; this is in fact the typical case,
when routing update packets are exchanged on schedule, and when a given
router acquires a new adjacency. However, partial routing updates (good
news and bad news) may be sent at any time.
The first time an adjacency is acquired, the two routers perform a full
routing update with each other, exchanging their complete link lists.
Once this is complete, the routers perform the SPF algorithm and compute
new routing tables.
IV.3.2. Preventing loops and retransmissions
A bulletin from reporting router X (which lists all of X's adjacencies)
is sent, initially by X, to every adjacent (to X) router A. This router
A passes it along to all of its own adjacencies B, etc. This flooding
is controlled such that no reporting router's adjacency update is sent
more than once between the same pair of routers.
After router A sends its bulletin envelope to B, the recipient router B
then looks at the sequence number of each reporting router X's adjacency
bulletin within that envelope, and for each reporting router's bulletin,
compares the sequence number of the just-received adjacency bulletin
with the highest sequence number previously originated from X. If the
just-received bulletin is newer (higher number), then it for further
study: sends a positive acknowledgement to A, and joins in the
to its own adjacencies. The horizon is, of course, decremented.
If the bulletin from X has the same number as was stored in B, B checks
the horizon left in the received bulletin against the horizon left when
it previously received the bulletin. In the event that the latest
bulletin received had a shorter (lower number) horizon left than the
earlier one, it simply ignores [and acknowledges] the (redundant)
message. But if the reporting router X's horizon left is greater for
the new copy of the bulletin, router B propagates it as if it were a new
bulletin. This way, if the bulletin happened to first arrive via a
roundabout path, it won't accidentally fail to reach the intended end of
its range. (Summary: Newer or longer-horizon bulletins are both passed
along. Same age or older (by sequence number) or same or lower horizon
will not be propagated.)
If any router B receives from router A a bulletin (from any reporting
router X) that contains a lower sequence number than one that had
previously arrived at B from said X, then it can be presumed that A has
"obsolete" information. B replies by sending a bulletin to A with the
latest link state information for that node X. As a corollary, a router
may poll for information about a given reporting router by sending a
routing update bulletin for that reporting router with a sequence number
of 0. Said bulletin may contain zero links' information.
IV.4. Point-to-point bulletin envelope
A router may acquire routing information from adjacent routers via
point-to-point procedures which treat every adjacency as a separate
logical data link. (Such a procedure also works, of course, over
point-to-point links such as wirelines.) This tends to have the highest
reliability, since connection-oriented data link control procedures can
be used to ensure the accuracy and completeness of the data passed over
the link. It has the disadvantage of requiring separate transmission of
the same data to different adjacent nodes on the same radio channel.
Bulletin envelopes are thus exchanged (when connection-oriented is
selected) periodically (based upon timers) and when new information is
received (over a new adjacency, and when good and bad news arrive).
Delivery of these bulletins is considered to be generally reliable.
IV.5. Broadcast bulletin propagation
When a router is adjacent to several other routers via the same
broadcast (i.e., packet radio) channel, retransmission of routing
bulletins to each adjacency makes additional use of bandwidth, which may
be a scarce resource. A broadcast procedure may be used to pass the
bulletin along that link. Note that broadcast propagation of bulletins
may be combined with non-broadcast propagation, on a link by link basis.
Although packet radio is a broadcast medium, it is not a perfect one:
The reliability of multicast packets is not as high as for wireline
LANs. This leads to the need for a unique broadcast "flooding"
technique. Note that in a true broadcast-topology subnetwork, these
procedures add little channel overhead, so these procedures are
applicable there as well.
IV.5.1. AX.25 subnetworks
At this time, only the AX.25 subnetwork is widely used in AMPRnet
while providing a multicast/broadcast service. Similar procedures may
be adapted for use elsewhere.
A routing update bulletin is broadcast to the Layer 2 multicast AX.25
address using the IP multicast address. Individual recipient routers
may or may not receive the entire bulletin, since there is no
In the previously described case of a non-broadcast message sent via a
connection-oriented datalink, the entire routing update bulletin can
be assumed to have been received intact. Thus, if a given reporting
router has originated a new complete list of its adjacencies (new
sequence numbers, subsequence numbers are 0), then any adjacency not
included is presumed to have ceased to exist. Such a presumption is
not always possible when a bulletin was received via unacknowledged
broadcast, as the message might have been received in part. This
should not make the partially received bulletin unusable.
A bulletin envelope is transmitted in one or more packets, each of
which constitutes a numbered fragment of the whole bulletin envelope.
Within the transmitted bulletin envelope, each individual reporting
router's bulletin begins with a node-header which contains the number
of links being reported on. Within each bulletin, each link is
identified by a link header, each of which specifies the number of
adjacencies being reported on (for that link). Since each IP packet
that makes up a bulletin contains a fragment number, it is also
possible to determine whether or not a fragment was lost. Each packet
also contains an envelope-ID, which prevents accidental mis-assembly
of different bulletins that may arrive close in time.
In connection-oriented non-broadcast procedures, a routing update
bulletin (not a partial one with a subsequence numbers >0) provides a
complete list of adjacencies known to the sending node, except where the
horizon is exceeded. Absence of a previouly-known adjacency then
implies that the adjacency has been lost. However, that assumption does
not apply to fragmented bulletins received in part, which can occur with
broadcast procedures: If a fragment was lost before reaching the end of
a given reporting router's bulletin within the bulletin envelope, then
the absence of a previously-known adjacency in the received bulletin
does not mean that the adjacency was lost.
RSPF procedures dictate that routing update bulletins with a subsequence
number of zero are presumed to be complete lists of adjacencies from
their originators; higher subsequence numbers represent incremental
changes only. In the broadcast procedures, a routing update bulletin
with a subsequence number of zero, if received only in part, is
treated as a partial routing update bulletin. If it received in full,
it is treated as a full routing update bulletin.
Thus, the recipient compares the sequence number with the previously
received sequence number from that reporting router. If it is higher
than the previously received one, then its adjacencies are used. If
it was received in full, and had a subsequence number of 0, then its
previous adjacencies are replaced (removed if not contained in the
latest full routing update bulletin). If it was not received in full,
or if its subsequence number was not zero, then its previous adjacencies
are left intact unless explicitly changed by the received bulletin.
If a bulletin is received in full, then the routers table is updated
with the latest sequence and/or subsequence number, horizon, and
timestamp. If it is received in part, then these entries are not
updated. After the bulletin has been completely transmitted, a
recipient node which has received a partial update from a reporting node
may poll for that node's latest information, by originating a
naming the reporting router in question, specifying sequence number 0,
with zero links for that reporting router. (This is the same
procedure used for non-broadcast links.)
Note that if a fragment is lost, a reporting router whose node-header is
in the lost fragment will of course remain unchanged in the recipient's
data base. Furthermore, any data received in subsequent fragments,
prior to a node-header, will also be meaningless. The last adjacency
of the last link in a reporting router's bulletin will have the Last
flag set to 1, signaling that following the address, a node header
follows. Note also that the first node-header within an envelope is
pointed to by the sync byte in the envelope header. The last flag and
sync byte should match or an error should be noted.
IV.5.2. Reconstructing bulletins from multiple fragments
If the resent bulletin is the same one as previously received in part,
and it too is received in part, then if all of the previously received
fragments were stored, the receiving router may attempt to reconstruct
the entire bulletin from the two (or more) fragmented transmissions.
Once an entire bulletin has been reconstructed, the receiving router may
treat this as a complete update. (This procedure is optional.)
IV.5.3. Non-broadcast unreliable subnets
If an adjacency is established across a general-topology subnet that
does not offer reliable packet delivery (eg., TheNet packet level), then
broadcast procedures should be used to exchange routing information
across the subnet between the two adjacencies. If the entire bulletin
is received intact, then it should be used; if it is received in part,
the received portions may be used, and the recipient may poll for a
retransmission as in IV.5.1 and IV.5.2 above.
IV.6. Routing update bulletin packets
A routing update bulletin envelope (Table IV.1)
may contain several
different reporting routers' updated link state information,
concatenated into one message, with a different sequence number for each
source (reporting router). One of the sources, of course, may be the
local router. Each router's link state information is further broken
down by link, which allows its backbone routing information to be
propogated separately from its local end node adjacency information.
IV.6.1. Node group reduction of adjacency list
If an end node establishes a connection with a router whose node group
default addresses (based on the significant bit count) already include
that end station, no bulletin need mention that adjacency, as packets to
that end station will already be routed correctly. Node groups are
IV.6.2. Incremental changes (good news and bad news)
Bulletins that only report changes in state come in two flavors. Good
news bulletins inform other routers that an adjacency has been noted.
bad news bulletins inform them that an adjacency has been lost.
Theoretically, a router could send out a new full routing update
bulletin every time it gained or lost an adjacency. However, the use of
shorter good news and bad news packets, which do not contain a full
routing update, allow the network to remain relatively current with less
Good news and bad news packets are propogated like other packets, but
are not originated by the same rules. While full routing bulletins are
originated based upon a timer (rspftimer), good news packets are
transmitted immediately upon receipt and initiated immediately after an
adjacency is initialized. This enables new links to be useful quickly.
Bad news, however, should not travel as fast: A node should cache any
bad news message for a time (recommendation for this timer:
rspftimer/16) while waiting for the link to come back up. This
keep the network stable; if the node receives a packet destined for the
lost destination, it may send an ICMP "host unreachable" message to the
originator of the packet, unless it can reroute the packet itself (as
may happen with the loss of a backbone link when others still exist).
Because good news and bad news messages represent changes to the last
full link state bulletin propogated, but do not purport to completely
represent a node's link states, they carry bulletin subsequence
numbers. These use the last bulletin sequence number originated by the
reporting router, but the sub-sequence value increments from 1. (A full
link state packet has a sub-sequence value of 0, and resets the
IV.6.3. Routes to nearby destinations
Sometimes more than one router will serve the same area (determined by
the significant bits' matching), and they will need to know which one
the better path to a given station. These adjacency messages may only
require a short horizon, as will good news and bad news packets which
refer to end nodes going on and off the air. Higher horizons are
needed for backbone routers.
This distinction allows routers to define their service area and
within a network by appropriate horizon adjustment. A router that
uses short horizons may be useful for providing connectivity within a
constrained geographic area, typically encompassing one or a small
number of node groups, in which not all end users have full connectivity
to a single router. Such a router will set its horizon_link, reporting
on other routers, to a low value. A router that serves as a backbone
node, propagating node groups across a wider horizon, will have a high
horizon_group, reporting node groups, value. (Horizon_link and
horizon_group values are usually set the same. Horizon_portable is
usually set to the same value as horizon_group and horizon_link;
horizon_local is set to a low value, so that even a backbone router will
not propagate intra-node group information across the backbone.)
Table IV.1. Routing update (link state packet)
|0 |8 |6 |4 |
| RSPF Version #| Type | fragment # | fragment total|
| Checksum | sync byte | # nodes below |
| Envelope-ID |
| Reporting node #1 full IP Router-Address | node
| Node 1 bulletin sequence # | sub-sequence #| # links |
| horizon left | ERP factor | link cost | #adjacencies | link
| Adjacent node(s) 1,1,1 IP address | adj.
| Adjacent node(s) 1,1,2 IP address | adj.
. . .
| Adjacent node(s) 1,1,n IP address |
| horizon left | ERP factor | link cost | #adjacencies | link
| Adjacent node(s) 1,2,1 IP address | adj.
. . .
| Adjacent node(s) 1,2,n IP address | adj.
| Reporting node #2 full IP Address | node
| Node 2 bulletin sequence # | sub-sequence #| # links |
| horizon left | ERP factor | link cost | #adjacencies | link
| Adjacent node(s) 2,1,1 IP address |
| Adjacent node(s) 2,1,2 IP address |
. . .
| horizon left | ERP factor | link cost | #adjacencies |
| Adjacent node(s) 2,2,1 IP address |
. . .
| Adjacent node(s) 2,2,n IP address |
. . .
| Reporting node #n full IP address |
| Node n bulletin sequence # | sub-sequence #| # links |
An RSPF bulletin packet is sent within IP with a type of >tbd - use
until an official value is assigned<. Each routing update envelope
contains an envelope packet header that contains:
- RSPF Version Number
- Version number of the protocol
- (Value 1 for Routing Update Bulletin Envelope)
- Fragment Number
- States which fragment, in a segmented
this is, beginning at 1. Non-fragmented messages use 1.
- Fragment total
- Total number of fragments in message; 1 if
- IP-style checksum.
- Sync byte
- Which octet in this packet (counting from this
byte as byte 0) is the beginning of the first node-header. If 0,
this fragment has no node-header. Non-fragmented messages
use a value of 4 (because 3 bytes follow in packet header).
- Number of nodes reporting
- The number of reporting routers
messages that follows (this packet or a sequence of packets forming
The node-header (for each reporting router) contains 8 octets:
- Reporting router #n full IP router address:
- The IP address of
the router whose adjacencies are being reported below. (Note
that if a router uses separate IP addresses on its links, it
should still adopt a single one as its router address.)
Bulletin sequence number
- When a bulletin is passed along, this
number is NOT changed; every new bulletin from a given Reporting
router has a value 1 higher than the previous bulletin from that
- Good news and bad news packets representing
incremental changes from the last full report increment this value
by 1; it is 0 for full bulletins.
- The number of different cost-horizon values (typically,
but not necessarily, representing different types of link in a
mulitiport gateway) being reported below; the following four octets
are the header for each link.
[For each reporting router, adjacencies are reported separately by
link cost. This is the received cost value for that data link, after
any adjustment that may be based upon packet loss ratio. Adjacencies
are also reported separately by horizon, even if the cost is the same.
It does not matter at this point if there are multiple RF or other
links if their cost and horizon are the same. Likewise, separate
received costs or horizons on one link will be treated separately
and such adjacencies will be grouped under separate link
- This number is decremented every time a routing update
bulletin is passed along; when it reaches 0, it is not passed
- A "figure of merit" for each link, rising with
slower/poorer links. This is the number whose total is minimized
by SPF. The range is 1-127. As a starting point, a 56000 bps fdx
backbone link might have a value of 2, a 4800bps hdx link a value
of 5, a 1200bps hdx link a value of 10 and a 300 bps hf "wormhole"
a value of 20. An Ethernet or high-speed (1 Mbps+) link might
then have a value of 1. A value of 255 denotes the loss of a
link; this is found in Bad News packets. These values should be
coordinated network-wide; adjusting them will change the way
packets are routed by RSPF.
Number of adjacencies
- The number of adjacencies to be listed for that
- Used for "approximating" a route; contains the number of
significant bits for which a given node can be presumed to be a
router, even if it doesn't report in detail. A low factor = wider
coverage area; thus ERP of 16 means that if NO other match is found
a given address, this router will try to handle it if it matches 16
bits. Basically a handle for future enhancements; its use will not
be required in this release of RSPF.
For each adjacency of the given link cost, the following is provided:
Note that the n,n,n vector within the bulletin has three fields in the
above representation: Reporting router within bulletin envelope, link
cost/horizon within reporting router's bulletin, and reporting adjacency
with that link cost/horizon.
- The number of bits used for node group
purposes. Usually 32 but may be lower if a given link purports to
serve all end nodes in an area defined using the most-matched-bits
node group convention. Higher numbers of bits matched take a higher
priority than least cost. This uses the low-order 5 bits of the
- If this is the last adjacency in the list for
reporting router, this value is 1; otherwise it is 0. (This
occupies the high-order bit of the significant bits octet.)
Full IP address
- The full IP address for this node.
In a moderate to large network, a full routing update can easily exceed
the maximum size of an AX.25 frame or IP packet. The RSPF Routing
Update message, however, may be sent in fragments. The IP fragmentation
function is not used for this; bulletins are not assumed to be
terminated by a packet boundary. Each fragment is, however, numbered in
the packet header, along with an indication of the number of the total
number of fragments in that envelope.
In order to permit parsing of the incoming fragments by routers who
are using unacknowledged broadcast information (with the high
likelihood of lost fragments), every bulletin's packet header contains a
sync byte indicator. This indicates which byte, where the next byte in
the header is byte 1, is the beginning of a node header. If a previous
fragment was lost, the receiver should ignore the number of bytes
indicated in the sync byte before resuming parsing of the packet. (If
the fragment does not exceed 255 bytes, this will always be sufficient.
It is recognized that long packets may not be able to use this mechanism
reliably, and a value of "0" should be used to indicate that no sync is
possible within this fragment.)
Each routing update bulletin envelope takes the form of a three-
dimensional list, with the dimensions being reporting router, link and
adjacency. A given bulletin envelope may report on link state from one
or more remote nodes, as well as from the sending node. Each node may
have one or more links; each link may have one or more adjacencies.
Packets may not be fragmented within adjacencies, but may be
fragmented after an adjacency's address and before the next adjacency's
significant bits field. (This presents a 5-octet field that should
not be fragmented.) The next fragment, in a new packet, simply begins
where the last one left off; the receiver knows how much more to
expect based upon the node and link count in the respective
node-header and link-header.
A router may not start sending a new Routing Update message of any kind
to any given IP address until all fragments of a previous message to
that address have been transmitted. This applies both to point to
point (non-multicast address) and multicast procedures.
IV.8. Bulletin Timers
The timers used for bulletin updates must be a compromise between
maintaing the network's current state and the traffic required to do
so. An initial suggestion: Good news messages should be initiated
within a few seconds and bad news should wait at least
with relatively short horizons on the bulletins (i.e., the routers
within the region). Full routing updates with normal horizons should be
sent out every rspftimer interval (typically 30 minutes). If the
network is small, more frequent updates may be possible; too frequent
updates risk choking the network with update traffic.
Last Modified: Wed, 22 Nov 2000
Copyright © 2000 Craig Small