home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / hamradio / docs106.zip / RSPF.DOC < prev    next >
Text File  |  1992-10-21  |  60KB  |  1,177 lines

  1.                 Fred Goldstein   k1io
  2.                 goldstein@carafe.enet.dec.com
  3.                 Version 2.1  2-oct-1989
  4.  
  5.      The Radio Shortest Path First (RSPF) Routing Protocol 
  6.       For DDN Internet Protocol over Amateur Packet Radio 
  7.  
  8.         ** DRAFT ARCHITECTURE -- FOR COMMENT **
  9.                 ** changes in V2.1 are noted by "**" and
  10.                    should be edited out before final release**
  11.  
  12. CONTENTS
  13.  
  14. I.   Introduction and Version Notes
  15. II.  Acquisition of router-router adjacencies
  16. III. Acquisition of end node adjacencies
  17. IV.  Link state propagation
  18. V.   The Shortest Path First Spanning Tree 
  19. Appendix:  Router Parameters
  20.  
  21.  
  22. I.  Introduction
  23.  
  24. Amateur packet radio use of the Internet Protocol does not yet provide 
  25. all of the capabilities of other IP networks.  One particular example
  26. of this is IP packet routing.  Most existing versions of the AMPR IP code
  27. make use of a static routing table.  This requires human intervention
  28. every time a new backbone path is added, and adds geographic constraints
  29. to address assignment which do not exist on the ARPA Internet. Some
  30. implementations make use of automatic routing protocols (interior
  31. gateway protocols, or IGPs) using distance vector routing.  These IGPs
  32. were originally written for wireline networks and tend to scale poorly
  33. to the amateur packet radio environment.
  34.  
  35. Many IP and other networks have implemented link state routing based upon
  36. Dijkstra's "SPF" (shortest path first) spanning tree algorithm.  A
  37. wireline implementation of SPF for IP is being standardized as the
  38. Open SPF Interior Gateway Protocol (OSPF), and an SPF procedure is
  39. being considered by ISO as the standard "IS-IS" routing protocol for
  40. OSI connectionless networks.  A similar (and derivative) procedure can
  41. be applied to AMPRnet (Net 44).  It is called Radio Shortest Packet
  42. First (RSPF); this document outlines the RSPF protocol.
  43.  
  44. RSPF occupies the role traditionally referred to in TCP/IP networks as
  45. an "Interior Gateway Protocol" (IGP), where "Gateway" means "router".
  46. It makes use of the services of the Internet Protocol.  It is not
  47. inconceivable that a router could use both RSPF and another IGP, or
  48. communicate with another network using the Exterior Gateway Protocol
  49. (EGP).  However these are not described in this document.
  50.  
  51. RSPF is intended to be implemented on routers, and need not be
  52. implemented on end nodes for the end nodes to take advantage of
  53. routing services.  Any IP station may be an end node giving no further
  54. consideration to routing.
  55.  
  56.  
  57. I.1. Elements of RSPF
  58.  
  59. The RSPF protocol is designed for use by internet-layer routing nodes (IP 
  60. Gateways) in a packet radio network using the DDN Internet Protocol.
  61. It is comprised of four major functions:
  62.  
  63.     1) Acquisition of router-router adjacencies
  64.     2) Acquisition of end node adjacencies
  65.     3) Link state propogation
  66.     4) Spanning tree route decision making.
  67.  
  68. Its net result is the automatic maintenance of a least-cost routing 
  69. table for use by IP Routing.  RSPF is optimized for the geographically
  70. heirarchical addressing used in AMPRnet, but does not depend upon it. 
  71.  
  72. RSPF is simpler than OSPF and IS-IS, as it is designed for PC
  73. implementation within the Amateur Radio Service.  It also adds
  74. procedures to take advantage of packet radio's "semi-broadcast"
  75. nature.
  76.  
  77.  
  78. I.2. Addressing convention
  79.  
  80. When an RSPF router communicates with an end node, it will typically
  81. deal with a 32 bit IP address.  Routers themselves, however, also
  82. support node group addressing (fewer than 32 bits need match).  This
  83. follows the convention in the KA9Q IP routing program, which permits a
  84. crude form of heirarchical addressing as well as allowing portable
  85. operations to override the defaults.  RSPF looks for the match (node or
  86. node group) with the greatest number of matching bits.  Only if the
  87. number of bits matched is equal, then the lower cost path will be used.
  88.  
  89. Thus a match to a full node address will override a "cheaper" path that
  90. matches its "class C net" of 24 bits, which overrides a "class B net",
  91. etc., noting that AMPRnet does not follow strict 8-bit address
  92. classification, and is a single Class A net.  In every case, a greater
  93. number of bits matched is considered a superior path to a destination
  94. than one that matches fewer bits, regardless of the value of the routing
  95. metric ("cost").
  96.  
  97.  
  98. I.3. Connection-oriented vs. connectionless lower layers
  99.  
  100. IP is a datagram network protocol, and supports both connection-
  101. oriented and connectionless lower layers (subnets).  In a network with
  102. a high packet loss rate, the local retransmission provided by a
  103. connection-oriented datalink will substantially improve overall
  104. throughput.  However, in a high-speed dedicated backbone, particularly
  105. one implemented using full-duplex radio or wireline links,
  106. connectionless links may provide better overall performance.  The
  107. choice of which to use is a local matter; RSPF will work with both.
  108. The reliability of the routing information, however, may be somewhat
  109. greater with connection-oriented datalink procedures, since these will
  110. give more rapid indication of a physical link failure.
  111.  
  112.  
  113. I.4. Relationship to other protocols
  114.  
  115. The reliability of the network depends upon reasonably reliable
  116. transmission of the routing update; hence, for non-broadcast procedures, 
  117. it is recommended that routers communicate with one another using
  118. connected-mode AX.25, or another reliable data link layer.  (In any case
  119. connected-AX.25 may be more useful than connectionless for backbone 
  120. links due to its local error correction ability.)  
  121.  
  122. **CHECK THIS OUT FOR VALIDITY WITH ANDERS**
  123. All packets specific to RSPF shall be exchanged inside IP packets using
  124. a protocol identifier which, pending formal assignment of one, shall
  125. be 73.  (How is this formally assigned?)  Such IP packets shall be
  126. sent with a time to live (TTL) value of 1.  If broadcast procedures
  127. are used, connectionless AX.25 UI frames shall be sent, with a
  128. multicast address "QST-0" in the AX.25 address and an IP address of
  129. 44.255.255.255. (A router can also "read the mail" on passing radio 
  130. packets not addressed to it; such procedures are for further study.) 
  131.  
  132. Note that in this document, "subnetwork" and "data link" are synonymous, 
  133. and refer to the layer over which IP packets are exchanged.
  134.  
  135.  
  136. I.5.  Version 2.1 changes.
  137.  
  138. RSPF draft 2.0 was released in June, 1988, as the first nearly-
  139. implementable version.  It was first implemented in September, 1989 by
  140. Anders Klemets.  This version 2.1 reflects changes whose need was
  141. discovered during this implementation.  These changes are both
  142. editorial and, in a few cases, substantive.
  143.  
  144. The format of the Routing Update packet has been slightly modified.
  145. In order to prevent fragments of two or more different routing update
  146. messages from being erroneously merged, an Envelope ID is added to
  147. each such packet, with the same Envelope ID on all fragments of a
  148. multi-packet message.  The term for such a message is now "envelope";
  149. it contains one or more "bulletins", each of which originated from a
  150. single router.
  151.  
  152. There are no longer separate packet types for Full Routing Update and
  153. Partial Routing Update.  Instead, they are distinguished by the value
  154. of the subsequence number, which is always 0 for Full Routing Updates
  155. and is never 0 for Partial Routing Updates.  A given envelope may
  156. contain both types of bulletin.
  157.  
  158. Cost is now set on the basis of receiver instead of transmitter.  This
  159. permits the automatic link quality adjustment to operate on the basis
  160. of locally-received traffic.
  161.  
  162. The remaining horizon is stored in the links table.  This is needed
  163. for consistency within the specification and was erroneously left out
  164. of 2.0.
  165.  
  166. It is now explicitly stated that upon creation of a new router-router
  167. adjacency, the routers exchage full routing information.  This allows
  168. routers to initialize themselves with a reasonably complete map of the
  169. network.
  170.  
  171.  
  172. II.  Acquisition of router-router adjacencies
  173.  
  174. For RSPF to operate correctly, all routers must remain reasonably
  175. current as to the state of the network at large.  This is handled by
  176. the propagation of "bulletin" messages among routers.  End nodes need
  177. not concern themselves with this; they will normally communicate
  178. through one "designated" router at any given time, for all
  179. (non-adjacent) destinations (not seen by ARP or other lower-layer 
  180. procedures).  End nodes can also, of course, connect to each other
  181. directly, bypassing RSPF.
  182.  
  183. Each router maintains an adjacencies table.  Each router's adjacency
  184. table lists the following information for all other nodes, both
  185. routers and end nodes, from which it directly receives packets over a
  186. subnetwork:
  187.  
  188.     Adjacent node IP address (i.e., 44.56.0.44)
  189.     Adjacent node datalink (AX.25) address (i.e., K1IO-0)
  190.     Datalink used (i.e., AX0)
  191.     Datalink cost (i.e., 4)
  192.     Number of packets heard since last RRH update (i.e., 50)
  193.     Packet sequence number in last RRH update (i.e., 12593)
  194.     Time of last RRH update (i.e., 2130).
  195.  
  196.  
  197. II.1.  Router-router hello
  198.  
  199. For the backbone to create its topology automatically, there must be a
  200. way for routers to discover each other with minimal overhead.  For
  201. this purpose, a router-router hello (RRH) message is provided.
  202. Periodically (as an initial suggestion, shortly before beginning to
  203. propogate the periodic links state bulletin to known adjacencies), the
  204. router sends out the RRH message to the layer 2 multicast address and IP
  205. multicast address.  RSPF makes no assumption of reciprocity (that
  206. links are bidirectional), so receipt of an RRH packet provides the
  207. receiver with information about a one-way (received) adjacency. 
  208.  
  209.  
  210. II.2.  Connection-oriented procedure
  211.  
  212. If a router uses connection-oriented subnet procedures to its own 
  213. adjacencies, then when a router receives this RRH packet, it checks to
  214. see if it already has a link to that packet's originator in its own
  215. links table.  If not, it waits a random period of time (initial
  216. suggestion:  within the range of 0 to 10 times the link's value of T1,
  217. DWAIT or SLOTTIME, and in any case much longer than the timers used
  218. within a CSMA or Aloha subnet such as AX.25) and then attempts to
  219. establish an AX.25 connection with the usual SABM; the router responds
  220. with the usual UA (link established) or DM (link rejected). 
  221.  
  222. If a two-way connection has been established, then both routers add the 
  223. link to their adjacency tables.  While the existence of this route is
  224. set reciprocally, the cost of each side of the route is set separately
  225. for each side of the connection.  Cost is propagated in the routing
  226. update (link state) packet.  Thus the adjacency between two routers is
  227. not actually used for real traffic until the first routing update
  228. packet exchange has taken place.
  229.  
  230. Loss of an adjacency may then be noted by the loss of the subnet
  231. connection.  When this occurs, the router removes the adjacency from
  232. its adjacency table and follows the "bad news" procedures outlined
  233. below for link state propagation.
  234.  
  235.  
  236. II.3.  Connectionless procedure
  237.  
  238. If a router uses connectionless datalink procedures to its own 
  239. adjacencies (suitable to low-loss links), then when a router receives an 
  240. RRH packet, it checks to see if this adjacency is already in its 
  241. adjacency table.  If not, then it is added.  It also sends RRH packets
  242. with the same frequency as with connection-oriented subnets.
  243.  
  244. Loss of an adjacency may be noted by timeout; if no RRH message is 
  245. received, and no frames have been received from the adjacent router for 
  246. a period of time (initial suggestion:  slightly over twice the maximum 
  247. interval between RRH messages), then the adjacency becomes suspect.
  248. The router should attempt (**a settable number of times**) to exchange a
  249. packet (ICMP echo) with the suspect adjacency; if unsuccessful (after
  250. the usual number of retries), the route is marked lost.  It may also
  251. be marked lost if other attempts to send data through that router
  252. fail, such that the implementation determines that there is a high
  253. probability that the link is lost.  
  254.  
  255.  
  256. Table II-1.  Coding of the RRH PDU.
  257.  
  258.                   1           2
  259.  |0              |8              |6              |4              |
  260.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
  261.  | RSPF Version #| Type (RRH)    | Checksum                      |
  262.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
  263.  |         Full IP Address of sending router                     |
  264.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
  265.  |  last packet sent seq. #      |  flags        |
  266.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  267.  |        plaintext                                              |...
  268.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  269.  
  270.  
  271. Parameters--
  272.  
  273.   An RSPF Router-Router Hello packet is sent within IP with a type
  274.   of <tbd-- 73 suggested>.  Each RRH packet contains the following
  275.   fields:
  276.  
  277.     RSPF Version Number:  Version number of this protocol (initially 1).
  278.  
  279.     Type:  Value of 3 for RRH.
  280.  
  281.     Checksum:  IP-style checksum
  282.  
  283.     Address:  Full IP address of sending router
  284.  
  285.     Last packet sent sequence number:  An integer (mod 65535) 
  286.     incremented by 1 for every frame sent by the datalink layer across 
  287.     this interface.  This value allows receiving entities using 
  288.     connectionless procedures to use the automatic link quality 
  289.     measurement technique described in II.4. 
  290.  
  291.     Flags:  The low-order bit is 1 if connectionless datalink is
  292.     preferred; 0 if connection-oriented is preferred.  (Set by
  293.     system management based upon anticipated link quality.)
  294.     Other bits are reserved (sent 0).
  295.  
  296.     Plaintext:  An optional text message (length may be up to maximum
  297.     size remaining in datalink PDU).  This might serve, for example,
  298.     to "broadcast" the router's existence to persons who might be
  299.     "reading the mail" (monitoring a radio channel promiscuously).
  300.  
  301.  
  302. II.4.  Automatic link quality measurement
  303.  
  304. A connectionless link or subnetwork may have very reliable, or very
  305. sporadic, performance.  Since there is no procedure for ensuring the
  306. reliability of packets sent over a connectionless link, a high rate of 
  307. packet loss may occur without being detected by the routers.  If this 
  308. loss is high enough, another route may become a better choice; a high 
  309. enough packet loss rate may be enough to mark a link as "down".  The
  310. automatic link quality measurement procedure allows links which are
  311. not yet "down", but whose performance is substandard, to be noted.
  312.  
  313. Every router shall maintain, for each link, a count of all packets
  314. sent over each link.  Every time an RRH message is sent, it includes
  315. the current value of this counter (modulo 65536).  Every router also
  316. maintains, in its adjacency table, a count of the total number of
  317. packets received from said adjacency since the last RRH message, and
  318. the value of that counter as received in the last RRH message.
  319.  
  320. Upon receipt of an RRH message, the recipient router compares the value 
  321. of the received packet counter with the last received value in the 
  322. adjacency table.  The difference (taking into account wrap-around at the 
  323. modulus) is compared with the number of packets received since the last 
  324. RRH message.  (This works even if an RRH message is lost.)  This packet 
  325. loss ratio is then maintained as a guideline to determine link quality.  
  326. If link quality falls below a settable threshhold, the link is
  327. suspect.  Timestamp can also be used to compute packet arrival rate.
  328.  
  329. Connection-oriented data links presumably deliver 100% of attempted 
  330. packets.  A high-quality connectionless link, such as Ethernet/LLC1, will 
  331. come close to this.  However, single-frequency packet radio links are 
  332. prone to packet loss for several reasons, including hidden transmitters, 
  333. lack of collision detection, and rf interference.  The packet loss ratio
  334. is useful in setting link cost, and may also be used to determine
  335. whether a link should use connectionless or connection-oriented 
  336. procedures.
  337.  
  338. If a router reports, in its link update packets, that a given link has a 
  339. cost of _n_, then its adjacencies (and only its adjacencies) may apply 
  340. the packet loss ratio to adjust the cost which they maintain in their 
  341. link state tables.  These adjusted costs, rather than the received 
  342. costs, may then be propagated to other routers.  
  343.  
  344. Such procedures should be applied sparingly, as each change must be
  345. propagated and could, if used too frequently, result in network-wide
  346. instability.  A suggested (experimental) algorithm is as follows:  A
  347. percentage threshhold x is set, as is a cost-adjustment factor y.  If
  348. fewer than x% of packets are received during a measurement interval,
  349. the cost of that adjacency is multipled by y.  For example, if x is 80 and
  350. y is 1.5, then an adjacency with a nominal assigned cost of 4 will be
  351. up-costed to 6 if only 70% of packets are received, but will be
  352. restored to 4 if 80% or more are received during the next measurement
  353. interval.  The measurement interval is the time between RRH messages,
  354. which precede routing update messages.
  355.  
  356.  
  357. III. Acquisition of end node adjacencies
  358.  
  359. Three possible means of determining adjacencies to end nodes are the use
  360. of connected-mode AX.25 links, the use of ARP, and the use of a 
  361. "wiretap" algorithm (see RFC981).  Unless a connection mode Data Link
  362. layer (with keepalive timers) is used, adjacent nodes may need to send
  363. each other messages at regular intervals (ping) to ensure that the
  364. link is still usable.  A procedure is outlined below for routers and
  365. end nodes to acquire knowledge of each other. 
  366.  
  367. It is assumed that RSPF will not be activated in end nodes; this
  368. permits them to use simple version of the IP software.  A node that
  369. has RSPF support in its software but operates as an end node can also
  370. use the router-router connection procedures and simply broadcast its
  371. adjacency to the router in a one-entry bulletin with a horizon of one.
  372. Such a node may also be simultaneously homed on two or more other
  373. routers, unlike true end nodes whose traffic either bypasses RSPF
  374. (using ARP) or arrives by way of its associated router.
  375.  
  376. There is no "redirect" function provided in RSPF.  Since radio does
  377. not provide a true "broadcast" topology subnetwork, a router cannot
  378. presume that if both end nodes can hear it, that both end nodes can
  379. hear each other.
  380.  
  381. If an end node knows the IP address of the router which will connect
  382. it to the network at large, it may establish a connected-mode AX.25
  383. (or other subnet) connection to the router; the presence of this
  384. connection indicates that the node is reachable from that router,
  385. which then adds it to its links table and subsequent bulletins.  This
  386. may, of course, require an ARP exchange in order to acquire the AX.25
  387. (or other data link layer or subnet) address.  
  388.  
  389. Alternately, the end node can simply use ARP and use connectionless 
  390. link procedures. In this case the router should assume that the end node
  391. is available until either a rather lengthy timer expires, or the router
  392. is unable to make an ARP contact after the ARP timer expires.  (A loss
  393. of reachability should not be inferred from the ARP timeout.) 
  394.  
  395. Routers should periodically broadcast their availability (suggested 
  396. interval:  every 15 minutes) with an AX.25 UI frame sent to QST-0 (the 
  397. AX.25 broadcast address).  A human-readable "unproto" message may go 
  398. here, allowing individual operators to recognize routers and connect
  399. as appropriate.  (No specific PDU coding is provided, as the end
  400. nodes do not use RSPF, and thus this is not really an RSPF packet.)
  401.  
  402. A router may also choose to use "Promiscuous ARP" to provide service to 
  403. an end node which is attempting to connect with an IP address reachable 
  404. by the router.  In such a case the router should wait an extra interval 
  405. after receiving the ARP request because the desired destination may 
  406. actually be directly reachable; ARP procedures may need to be modified
  407. to provide this. 
  408.  
  409. Another potential approach is for routers to simply listen to AX.25 
  410. traffic on the link and determine who is adjacent to whom.  This is the 
  411. gist of the "wiretap" algorithm in RFC981, which also finds non-adjacent 
  412. nodes by taking advantage of the source routing found in AX.25 frames.
  413. Integration of wiretap into RSPF is for further study.
  414.  
  415.  
  416.  
  417. IV.  Link state propagation
  418.  
  419. Link state information is propagated between routers within bulletin
  420. envelopes, which are sequences of packets containing partial or full
  421. copies of the sending node's link state table.  Both point-to-point
  422. and broadcast procedures are provided.
  423.  
  424. IV.1.  Optional multicast/broadcast
  425.  
  426. Packet radio is inherently a broadcast medium.  Packet radio networks, 
  427. however, may be viewed as a collection of individual links which happen 
  428. to use a broadcast physical medium.  It is also possible to exploit the
  429. broadcast nature of the medium.  RSPF link state propagation procedures
  430. allow but do not require such multicasting.  If the link uses
  431. connectionless procedures for user data packet exchange, then broadcast
  432. procedures should be used for link state packet exchange.  The converse
  433. may not necessarily be true:  The threshhold of loss that militates
  434. against connectionless transmission of user data may be more stringent
  435. than that which call for non-broadcast transmission of link state
  436. packets.  (Optimal parameters are for further study.) 
  437.  
  438.  
  439. IV.2.  Routing update bulletins
  440.  
  441. Routing updates are passed along from router to router via routing
  442. update bulletins, which are broadcast within routing update envelopes.
  443. Bulletin propagation is designed to make it extremely likely that
  444. every node within a given "horizon" receives every routing update
  445. message sent out by a given node. 
  446.  
  447. Every router originates information about changes in its own adjacencies, 
  448. as well as periodic retranmissions of its entire list of adjacencies.  
  449. These bulletins are then propagated among other routers. The router whose
  450. adjacency information is being broadcast is called the _reporting
  451. router_; this may be some hops away from the routers which forward it to
  452. their own adjacencies.  Each reporting router's bulletins (adjacency
  453. updates) contain a sequence number (and in some cases, a subsequence
  454. number).  These sequence and subsequence numbers are generated by the
  455. reporting router and propagated; they are not changed when a bulletin
  456. is relayed.  They are incrememted by 1 (modulo 65536) every time a new
  457. one is generated. 
  458.  
  459. Bulletins may also carry change information incremental to previous
  460. bulletins.  These carry the same sequence number as the full routing
  461. update bulletin to which they are reporting incremental changes; each
  462. such partial routing update bulletin has a subsequence number.  The
  463. subsequence number is zero for a full routing update bulletin.
  464.  
  465. Every bulletin also has a horizon value, set by the reporting router,
  466. associated with each of its constituent links.  (A given reporting
  467. router may have more than one constituent link, if it is a multi-port
  468. router.)  Every time a bulletin is propagated, each horizon value is
  469. decremented by 1.  When it hits zero, the bulletin is not propagated
  470. further.  Note that for horizon purposes, a bulletin's individual
  471. constituent links may have separate horizons; when a link's horizon hits
  472. zero, other links' adjacency information from the same reporting router 
  473. may continue to be propogated.  
  474.  
  475. It should also be noted that if a given link has adjacencies with
  476. different horizons, these must be treated as separate links, since
  477. horizon is reported as a characteristic of link.  Such a circumstance
  478. may occur, for example, when a router serves a node group.
  479. Adjacencies within the node group are typically propagated with short
  480. horizons, since they are only of local interest (i.e., to other nodes
  481. in or near that node group).  Similarly, the node group itself is
  482. propagated with a long horizon, across a backbone.  However,
  483. adjacencies outside the node group may be propagated with long
  484. horizons, as they would not otherwise be reached across a backbone
  485. dependent upon node groups for long-haul routing.
  486.  
  487. Every router maintains within memory a routers table containing one
  488. tuple for every other router on the network.  This tuple contains the
  489. following elements:  
  490.  
  491.     IP Address 
  492.     Last received bulletin sequence number 
  493.     Last received bulletin subsequence number 
  494.     Timestamp for when the data was received.  
  495.     Horizon remaining in bulletin when received **NEW IN 2.1**
  496.  
  497. This table is used to coordinate the receipt and transmission of
  498. bulletins, using either broadcast or non-broadcast procedures. 
  499.  
  500.  
  501. IV.3.  Flooding without congestion 
  502.  
  503. Upon initialization of adjacencies
  504.  
  505. Bulletins are forwarded in a routing update envelope which may contain
  506. one or more reporting routers' bulletins (adjacency lists), which are 
  507. flooded to the network.  A bulletin envelope may actually concatenate
  508. multiple reporting routers' bulletins; this is in fact the typical
  509. case, when routing update packets are exchange on schedule, **and when a
  510. given router acquires a new adjacency**.  However, partial routing
  511. updates (good news and bad news) may be sent at any time.
  512.  
  513. The first time an adjacency is acquired, the two routers perform a
  514. full routing update with each other, exchanging their complete link
  515. lists.  Once this is complete, the routers perform the SPF algorithm
  516. and compute new routing tables.
  517.  
  518. Preventing loops and retransmissions
  519.  
  520. A bulletin from reporting router X (which lists all of X's
  521. adjacencies) is sent, initially by X, to every adjacent (to X) router
  522. A.  This router A passes it along to all of its own adjacencies B,
  523. etc..  This flooding is controlled such that no reporting router's
  524. adjacency update is sent more than once between the same pair of
  525. routers.  
  526.  
  527. After router A sends its bulletin envelope to B, the recipient router
  528. B then looks at the sequence number of each reporting router X's
  529. adjacency bulletin within that envelope, and for each reporting
  530. router's bulletin, compares the sequence number of the just-received
  531. adjacency bulletin with the highest sequence number previously
  532. originated from X.  If the just-received bulletin is newer (higher
  533. number), then it sends a positive acknowledgement to A, and joins in
  534. the flooding to its own adjacencies.  The horizon is, of course,
  535. decremented.  ** HOW IS IT POSITIVELY ACKED?  NEED WE? **
  536.  
  537. If the bulletin from X has the same number as was stored in B, B checks 
  538. the horizon left in the received bulletin against the horizon left
  539. when it previously received the bulletin.  In the event that the
  540. latest bulletin received had a shorter (lower number) horizon left
  541. than the earlier one, it simply acknowledges the (redundant) message.
  542. But if the reporting router X's horizon left is greater for the new
  543. copy of the bulletin, router B propagates it as if it were a new
  544. bulletin. This way, if the bulletin happened to first arrive via a
  545. roundabout path, it won't accidentally fail to reach the intended end
  546. of its range. (Summary:  Newer or longer-horizon bulletins are both
  547. passed along.  Same age or older (by sequence number) or same or lower
  548. horizon will not be propagated.)
  549.  
  550. If any router B receives from router A a bulletin (from any reporting 
  551. router X) that contains a lower sequence number than one that had 
  552. previously arrived at B from said X, then it can be presumed that A
  553. has "obsolete" information.  B replies by sending a bulletin to A with
  554. the latest link state information for that node X.  As a corrolary, a
  555. router may poll for information about a given reporting router by
  556. sending a routing update bulletin for that reporting router with a
  557. sequence number that is lower than the latest one it actually has
  558. received.  Said bulletin may contain zero links' information.  (Note
  559. that since the sequence number is modular, a value of 0 is not correct
  560. for this function as 0 is higher than 65535; the "poll" number should
  561. be only slightly lower.)
  562.  
  563.  
  564. IV.4.  Non-broadcast bulletin envelope exchange
  565.  
  566. A router may acquire routing information from adjacent routers via 
  567. point-to-point procedures which treat every adjacency as a separate 
  568. logical data link.  (Such a procedure also works, of course, over 
  569. point-to-point links such as wirelines.)  This tends to have the highest
  570. reliability, since connection-oriented data link control procedures can
  571. be used to ensure the accuracy and completeness of the data passed over
  572. the link.  It has the disadvantage of requiring separate transmission of
  573. the same data to different adjacent nodes on the same radio channel. 
  574.  
  575. Bulletin envelopes are thus exchanged (when connection-oriented is
  576. selected) periodically (based upon timers) and when new information is
  577. received (over a new adjacency, and when good and bad news arrive).
  578. Delivery of these bulletins is considered to be gnerally reliable.
  579.  
  580.  
  581. IV.5.  Broadcast bulletin propagation
  582.  
  583. When a router is adjacent to several other routers via the same 
  584. broadcast (i.e., packet radio) channel, retransmission of routing
  585. bulletins to each adjacency makes additional use of bandwidth, which may
  586. be a scarce resource.  A broadcast procedure may be used to pass the
  587. bulletin along that link.  Note that broadcast propagation of bulletins
  588. may be combined with non-broadcast propagation, on a link by link basis.
  589. Although packet radio is a broadcast medium, it is not a perfect one:
  590. The reliability of multicast packets is not as high as for wireline LANs.
  591. This leads to the need for a unique broadcast "flooding" technique.
  592.  
  593. A routing update bulletin is broadcast to the Layer 2 multicast AX.25
  594. address using the IP multicast address.  Individual recipient routers
  595. may or may not receive the entire bulletin, since there is no
  596. acknowledgement provided. 
  597.  
  598. In the previously described case of a non-broadcast message sent via a
  599. connection-oriented datalink, the entire routing update bulletin can
  600. be assumed to have been received intact.  Thus, if a given reporting
  601. router has originated a new complete list of its adjacencies (new
  602. sequence numbers, subsequence numbers are 0), then any adjacency not
  603. included is presumed to have ceased to exist.  Such a presumption is
  604. not always possible when a bulletin was received via unacknowledged
  605. broadcast, as the message might have been received in part.  This
  606. should not make the partially received bulletin unusable. 
  607.  
  608. A bulletin envelope is transmitted in one or more packets, each of
  609. which constitutes a numbered fragment of the whole bulletin envelope.
  610. Within the transmitted bulletin envelope, each individual reporting
  611. router's bulletin begins with a node-header which contains the number
  612. of links being reported on.  Within each bulletin, each link is
  613. identified by a link header, each of which specifies the number of
  614. adjacencies being reported on (for that link).  Since each IP packet
  615. that makes up a bulletin contains a fragment number, it is also
  616. possible to determine whether or not a fragment was lost.  Each packet
  617. also contains an envelope-ID, which prevents accidental mis-assembly
  618. of different bulletins that may arrive close in time. **NEW IN 2.1**
  619.  
  620. In connection-oriented non-broadcast procedures, a routing update 
  621. bulletin (not a partial one with a subsequence numbers >0) provides a 
  622. complete list of adjacencies known to the sending node, except where the 
  623. horizon is exceeded.  Absence of a previouly-known adjacency then 
  624. implies that the adjacency has been lost.  However, that assumption does 
  625. not apply to fragmented bulletins received in part, which can occur with 
  626. broadcast procedures: If a fragment was lost before reaching the end of
  627. a given reporting router's bulletin within the bulletin envelope, then
  628. the absence of a previously-known adjacency in the received bulletin
  629. does not mean that the adjacency was lost. 
  630.  
  631. RSPF procedures dictate that routing update bulletins with a subsequence 
  632. number of zero are presumed to be complete lists of adjacencies from 
  633. their originators; higher subsequence numbers represent incremental
  634. changes only.  In the broadcast procedures, a routing update bulletin 
  635. with a subsequence number of zero, if received only in part, is
  636. treated as a partial routing update bulletin.  If it received in full,
  637. it is treated as a full routing update bulletin.
  638.  
  639. Thus, the recipient compares the sequence number with the previously
  640. received sequence number from that reporting router.  If it is higher
  641. than the previously received one, then its adjacencies are used.  If
  642. it was received in full, and had a subsequence number of 0, then its
  643. previous adjacencies are replaced (removed if not contained in the
  644. latest full routing update bulletin).  If it was not received in full,
  645. or if its subsequence number was not zero, then its previous
  646. adjacencies are left intact unless explicitly changed by the received
  647. bulletin.
  648.  
  649. If a bulletin is received in full, then the routers table is updated 
  650. with the latest sequence and/or subsequence number, horizon **NEW 2.1**
  651. and timestamp.  If it is received in part, then these entries are not
  652. updated.  After the bulletin has been completely transmitted, a
  653. recipient node which has received a partial update from a reporting
  654. node may poll for that node's latest information, by using the (now
  655. known to be obsolete) sequence number for that router in its router
  656. table in a bulletin, with zero links for that reporting router.  (This
  657. is the same polling procedure used for non-broadcast links.)
  658.  
  659. Note that if a fragment is lost, a reporting router whose node-header is 
  660. in the lost fragment will of course remain unchanged in the recipient's 
  661. data base.  Furthermore, any data received in subsequent fragments, 
  662. prior to a node-header, will also be meaningless.  The last adjacency 
  663. of the last link in a reporting router's bulletin will have the Last 
  664. flag set to 1, signaling that following the address, a node header 
  665. follows.  Note also that the first node-header within an envelope is
  666. pointed to by the sync byte in the envelope header.  The last flag and
  667. sync byte should match or an error should be noted.
  668.  
  669.  
  670. IV.6.  Routing update bulletin packets 
  671.  
  672. A routing update bulletin envelope (Table IV.1) may contain several
  673. different reporting routers' updated link state information,
  674. concatenated into one message, with a different sequence number for each
  675. source (reporting router).  One of the sources, of course, may be the
  676. local router.  Each router's link state information is further broken
  677. down by link, which allows its backbone routing information to be
  678. propogated separately from its local end node adjacency information. 
  679.  
  680. Incremental changes (good news and bad news)
  681.  
  682. Bulletins that only report changes in state come in two flavors.  Good
  683. News bulletins inform other routers that an adjacency has been noted.
  684. Bad News bulletins inform them that an adjacency has been lost.  If an
  685. end node establishes a connection with a router whose node group default
  686. addresses (based on the significant bit count) already include that end
  687. station, however, no bulletin need be sent out, as packets to that end 
  688. station will already be routed correctly.  Theoretically, a router could
  689. send out a new full routing update bulletin every time it gained or lost
  690. an adjacency. However, the use of shorter Good News and Bad News
  691. packets, which do not contain a full routing update, allow the network
  692. to remain relatively current with less transmitted traffic. 
  693.  
  694. Good news and bad news packets are propogated like other packets,
  695. but are not originated by the same rules.  While full routing bulletins
  696. are originated based upon a timer, good news packets are transmitted
  697. immediately upon receipt and initiated immediately after an adjacency
  698. is initialized.  This enables new links to be useful quickly.  Bad news,
  699. however, should not travel as fast:  A node should cache any bad
  700. news message for a time (initial recommendation for this timer: 60 
  701. seconds) while waiting for the link to come back up.  This helps keep
  702. the network stable; if the node receives a packet destined for the 
  703. lost destination, it may send an ICMP "host unreachable" message
  704. to the originator of the packet, unless it can reroute the packet
  705. itself (as may happen with the loss of a backbone link when others
  706. still exist).
  707.  
  708. Because good news and bad news messages represent changes to the last
  709. full link state bulletin propogated, but do not purport to completely
  710. represent a node's link states, they carry bulletin subsequence
  711. numbers.  These use the last bulletin sequence number originated by the
  712. reporting router, but the sub-sequence value increments from 1. (A full 
  713. link state packet has a sub-sequence value of 0, and resets the 
  714. subsequence counter.) 
  715.  
  716. Routes to nearby destinations
  717.  
  718. Sometimes more than one router will serve the same area (determined by 
  719. the significant bits' matching), and they will need to know which one has 
  720. the better path to a given station.  These adjacency messages may only 
  721. require a short horizon, as will Good News and Bad News packets which 
  722. refer to end nodes going on and off the air.   Higher horizons are 
  723. needed for backbone routers.
  724.  
  725.  
  726. Table IV.1.  Routing update (link state packet) bulletin envelope:
  727.  
  728.                   1           2
  729.  |0              |8              |6              |4              |
  730.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----
  731.  | RSPF Version #| Type          | fragment #    | fragment total| packet
  732.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -hdr
  733.  |       Checksum                | sync byte     | # nodes below |
  734.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
  735.  |  Envelope-ID                  |
  736.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----
  737.  |         Reporting node #1 full IP Router-Address              | node
  738.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -hdr
  739.  |  Node 1 bulletin  sequence #  | sub-sequence #| # links       |
  740.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----
  741.  | horizon left   |  ERP factor  |  link cost    |  #adjacencies | link
  742.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ _-hdr_
  743.  |significant bits|
  744.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  745.  |              Adjacent node(s) 1,1,1 IP address                | adj.
  746.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---
  747.  |significant bits|
  748.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  749.  |             Adjacent node(s) 1,1,2 IP address                 | adj.
  750.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---
  751.                        ...
  752.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  753.  |significant bits|
  754.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  755.  |             Adjacent node(s) 1,1,n IP address                 |
  756.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---
  757.  | horizon left   |  ERP factor  |  link cost    |  #adjacencies | link
  758.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---
  759.  |significant bits|
  760.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  761.  |             Adjacent node(s) 1,2,1 IP address                 | adj.
  762.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---
  763.                         ...
  764.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  765.  |significant bits|
  766.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  767.  |             Adjacent node(s) 1,2,n IP address                 | adj.
  768.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---
  769.  |         Reporting node #2 full IP Address                     | node
  770.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  771.  |  Node 2 bulletin sequence #   | sub-sequence #|  # links      |
  772.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---
  773.  | horizon left  |  ERP factor   |  link cost    |  #adjacencies | link
  774.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---
  775.  |significant bits|
  776.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ adj.
  777.  |             Adjacent node(s) 2,1,1 IP address                 |
  778.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---
  779.  |significant bits|
  780.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  781.  |             Adjacent node(s) 2,1,2 IP address                 |
  782.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  783.                        ...
  784.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  785.  | horizon left    |  ERP factor |  link cost    |  #adjacencies | 
  786.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  787.  |significant bits|
  788.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  789.  |             Adjacent node(s) 2,2,1 IP address                 |
  790.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  791.                         ...
  792.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  793.  |significant bits|
  794.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  795.  |             Adjacent node(s) 2,2,n IP address                 |
  796.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  797.                         ...
  798.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  799.  |         Reporting node #n full IP address                     |
  800.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  801.  |  Node n bulletin sequence #   | sub-sequence #|   # links     |
  802.  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  803.     etc.
  804.  
  805. Parameters--
  806.  
  807.   An RSPF bulletin packet is sent within IP with a type of <tbd - use 73
  808.   until an official value is assigned>.  Each routing update envelope
  809.   contains an envelope packet header that contains:
  810.  
  811.     RSPF Version Number:  Version number of the protocol (initially 1).
  812.  
  813.     Type:  (Value 1 for Routing Update Bulletin Envelope)
  814.  
  815.     Fragment Number:  States which fragment, in a segmented message,
  816.     this is, beginning at 1.  Non-fragmented messages use 1.
  817.     
  818.     Fragment total:  Total number of fragments in message; 1 if not 
  819.     fragmented.
  820.  
  821.     Checksum:  IP-style checksum.
  822.  
  823.     Sync byte:  Which octet in this packet (counting from this 
  824.     byte as byte 0) is the beginning of the first node-header.  If 0,
  825.     this fragment has no node-header.  Non-fragmented messages
  826.     use a value of 4 (because 3 bytes follow in packet header).
  827.     **NOTE CHANGE IN 2.1**
  828.  
  829.     Number of nodes reporting:  The number of reporting routers in the 
  830.     messages that follows (this packet or a sequence of packets forming
  831.     the envelope).
  832.  
  833.  
  834.   The node-header (for each reporting router) contains 8 octets:
  835.  
  836.     Reporting router #n full IP router address:  The IP address of 
  837.     the router whose adjacencies are being reported below.  (Note
  838.     that if a router uses separate IP addresses on its links, it
  839.     should still adopt a single one as its router address.)
  840.  
  841.     Bulletin sequence number:  When a bulletin is passed along, this 
  842.     number is NOT changed; every new bulletin from a given Reporting 
  843.     router has a value 1 higher than the previous bulletin from that
  844.     reporting router.  (Note:  This is modulo 65536, so implementations
  845.     must cope with the "wrap around" and consider values below, say,
  846.     100, to be "higher" than values above, say, 65400.  Between 100
  847.     and 65400, modular arithmetic is NOT used.)
  848.  
  849.     Sub-sequence number:  Good news and bad news packets representing
  850.     incremental changes from the last full report increment this value
  851.     by 1; it is 0 for full bulletins.
  852.  
  853.     # links:  The number of different cost-horizon values (typically, 
  854.     but not necessarily, representing different types of link in a 
  855.     mulitiport gateway) being reported below; the following four octets 
  856.     are the header for each link.
  857.  
  858.  [For each reporting router, adjacencies are reported separately by
  859.   link cost.  This is the received cost value for that data link, after
  860.   any adjustment that may be based upon packet loss ratio.  Adjacencies
  861.   are also reported separately by horizon, even if the cost is the same. 
  862.   It does not matter at this point if there are multiple RF or other 
  863.   links if their cost and horizon are the same.  Likewise, separate
  864.   received costs or horizons on one link will be treated separately
  865.   and such adjacencies will be grouped under separate link headers:]
  866.  
  867.     Horizon left:  This number is decremented every time a routing update 
  868.     bulletin is passed along; when it reaches 0, it is not passed further.
  869.  
  870.     Link cost:  A "figure of merit" for each link, rising with
  871.     slower/poorer links.  This is the number whose total is minimized
  872.     by SPF.  The range is 1-127.  As a starting point, a 56000 bps fdx
  873.     backbone link might have a value of 2, a 4800bps hdx link a value
  874.     of 5, a 1200bps hdx link a value of 10 and a 300 bps hf "wormhole"
  875.     a value of 20.  An Ethernet or high-speed (1 Mbps+) link might
  876.     then have a value of 1.  A value of 255 denotes the loss of a
  877.     link; this is found in Bad News packets.  These values should be
  878.     coordinated network-wide;  adjusting them will change the way
  879.     packets are routed by RSPF.
  880.  
  881.     Number of adjacencies:  The number of adjacencies to be listed for that 
  882.     reporting node.
  883.  
  884.     ERP Factor:  Used for "approximating" a route; contains the number of 
  885.     significant bits for which a given node can be presumed to be a valid 
  886.     router, even if it doesn't report in detail.  A low factor = wider 
  887.     coverage area; thus ERP of 16 means that if NO other match is found for 
  888.     a given address, this router will try to handle it if it matches 16 
  889.     bits.  Basically a handle for future enhancements; its use will not
  890.     be required in the initial release of RSPF.
  891.  
  892.   For each adjacency of the given link cost, the following is provided:
  893.  
  894.     Significant bits: The number of bits used for node group routing 
  895.     purposes.  Usually 32 but may be lower if a given link purports to 
  896.     serve all end nodes in an area defined using the most-matched-bits 
  897.     node group convention.  Higher numbers of bits matched take a higher 
  898.     priority than least cost.  This uses the low-order 5 bits of the 
  899.     octet.
  900.  
  901.     Last-flag:  If this is the last adjacency in the list for this 
  902.     reporting router, this value is 1; otherwise it is 0.  (This 
  903.     occupies the high-order bit of the significant bits octet.)
  904.  
  905.     Full IP address: The full IP address for this node.  
  906.  
  907. Note that the n,n,n vector within the bulletin has three fields in the
  908. above representation: Reporting router within bulletin envelope, link 
  909. cost/horizon within reporting router's bulletin, and reporting adjacency
  910. with that link cost/horizon.
  911.  
  912.  
  913. IV.7.  Fragmentation
  914.  
  915. In a moderate to large network, a full routing update can easily exceed 
  916. the maximum size of an AX.25 frame or IP packet.  The RSPF Routing
  917. Update message, however, may be sent in fragments.  The IP
  918. fragmentation function is not used for this; bulletins are not assumed
  919. to be terminated by a packet boundary.  Each fragment is, however,
  920. numbered in the packet header, along with an indication of the number
  921. of the total number of fragments in that envelope.
  922.  
  923. In order to permit parsing of the incoming fragments by routers who
  924. are using unacknowledged broadcast information (with the high 
  925. likelihood of lost fragments), every bulletin's packet header contains a 
  926. sync byte indicator.  This indicates which byte, where the next byte in 
  927. the header is byte 1, is the beginning of a node header.  If a previous 
  928. fragment was lost, the receiver should ignore the number of bytes 
  929. indicated in the sync byte before resuming parsing of the packet.  (If 
  930. the fragment does not exceed 255 bytes, this will always be sufficient.  
  931. It is recognized that long packets may not be able to use this mechanism 
  932. reliably, and a value of "0" should be used to indicate that no sync is 
  933. possible within this fragment.)
  934.  
  935. Each routing update bulletin envelope takes the form of a three-
  936. dimensional list, with the dimensions being reporting router, link and
  937. adjacency. A given bulletin envelope may report on link state from one
  938. or more remote nodes, as well as from the sending node.  Each node may
  939. have one or more links; each link may have one or more adjacencies. 
  940.  
  941. Packets may not be fragmented within adjacencies, but may be
  942. fragmented after an adjacency's address and before the next adjacency's
  943. significant bits field.  (This presents a 5-octet field that should
  944. not be fragmented.)  The next fragment, in a new packet, simply begins
  945. where the last one left off; the receiver knows how much more to
  946. expect based upon the node and link count in the respective
  947. node-header and link-header. 
  948.  
  949. A router may not start sending a new Routing Update message of any kind 
  950. to any given IP address until all fragments of a previous message to
  951. that address have been transmitted.  This applies both to point to
  952. point (non-multicast address) and multicast procedures.
  953.  
  954.  
  955. IV.8.  Bulletin Timers
  956.  
  957. The timers used for bulletin updates must be a compromise between
  958. maintaing the network's current state and the traffic required to do
  959. so.  An initial suggestion:  Good news messages should be initiated
  960. within a few seconds and bad news messages should be initiated within
  961. one minute, with relatively short horizons on the bulletins (i.e., the
  962. routers within the region).  Full routing updates with normal horizons
  963. should be sent out every 30 minutes.  If the network is small, more
  964. frequent updates may be possible; too frequent updates risk choking
  965. the network with update traffic.
  966.  
  967.  
  968.  
  969.  
  970. V.  The Shortest Path First spanning tree algorithm
  971.  
  972. As a routing node comes onto the network, it acquires over time a
  973. complete list of adjacencies between other nodes on the network except
  974. as limited by the "horizon".  Each adjacency (point to point link)
  975. within the entire known network has a "cost" associated with it.  It
  976. should be noted that adjacencies, for the purposes of this algorithm,
  977. are "logical" and not necessarily physical;  if a subnetwork link
  978. occurs below IP (as in AX.25 digipieating or NET/ROM), the two ends of
  979. the link are still adjacent.  (Adjacency at the IP internet layer is
  980. based upon subnetworks, which may contain their own links.)  
  981.  
  982. Cost is set for the receive (** Changed in 2.1 to facilitate automatic
  983. link quality adjustment **) side of each link.  If the receiver and
  984. transmitter do not agree on cost, the network shall apply different
  985. routes for packets going in opposite directions between the same two
  986. end nodes.  (This is not a problem.  In a radio environment, one
  987. should NOT assume reciprocity across a link.) 
  988.  
  989. V.1.  Tables
  990.  
  991. Each router builds a _link state table_ that lists, for every known
  992. link in the network (from every reporting router), the two ends and
  993. the cost of that end of the link.  The ends are listed by an IP router
  994. address and, for the destination IP router address, a number of
  995. significant bits.  This is what's updated by the bulletins and by good
  996. news/bad news messages. 
  997.  
  998.     Source IP address    Dest. IP addr/bits    Cost
  999.  
  1000.     44.56.0.44        44.56.0.128/32        5
  1001.     44.56.0.44        44.56.0.12/25        10
  1002.  
  1003. The goal of the SPF algorithm is to build a _paths table_ which lists,
  1004. for every reachable node (or node group approximation of fewer than 32
  1005. bits) on the network, that node address (or node group address and
  1006. number of significant bits), the adjacent node used to get there
  1007. (i.e., where you blast the packets to next), and the total cost of the
  1008. path.  (This feeds the Route table in the IP Route module in NET.)
  1009. This is done by building a spanning tree with the router doing the
  1010. computation (the home router) as the root of the tree.  The paths
  1011. table thus lists the best way across the tree from the home router to
  1012. all known destinations.
  1013.  
  1014. Every router contains, for the purposes of building the tree, a 
  1015. _trial table_ that has three entries:  Destination address/bits,
  1016. adjacent node, and cost of this path.  The paths table additionally 
  1017. has one more entry, the _parent_ node, which is the last hop
  1018. before the destination.  Thus in a path A -> B -> C -> D -> E, home 
  1019. router A views E as the destination, D as the parent, and B as the
  1020. adjacency.  Note that in the path from A to B, A is the parent node. 
  1021.  
  1022. Begin building the paths table by using the home router as the first 
  1023. node on the paths table.  The cost to reach yourself is always 0, so 
  1024. make the first entry on the paths table as follows:  Source=self,
  1025. destination=self, parent=self, and cost=0.  From here on in, parent 
  1026. is always (by definition of the SPF spanning tree) the node most 
  1027. recently added to the paths table.
  1028.  
  1029.     Destination    Adjacent     Parent        Cost
  1030.  
  1031.     44.56.0.128    44.56.0.128    44.56.0.44    5
  1032.     44.56.0.131    44.56.0.128    44.56.0.128    10
  1033.     44.56.0.200    44.56.0.128    44.56.0.131    15
  1034.  
  1035.         Paths Table showing relationship between 
  1036.     destination, parent and adjacent nodes, where the home
  1037.     node is 44.56.0.44 and 44.56.0.200 is three hops away;
  1038.     all hops here have a cost of 5.
  1039.  
  1040. V.2.  Scanning the links
  1041.  
  1042. The home router now scans its links table looking for all nodes (routers 
  1043. and end nodes) that are adjacent to the current parent node, except
  1044. for links to nodes which are already on the paths table.  (It is
  1045. generally fastest to build the paths table by scanning the links table
  1046. in order of increasing link cost.)  Each of these new nodes is added
  1047. to the trial table, except for the parent node (which is already on
  1048. the paths table, so it can't possibly have a shorter path).  The value
  1049. of cost placed on the trial table is the cost of the link from the
  1050. parent to the destination plus the cost from home to the parent node
  1051. (which value is already on the paths table).  
  1052.  
  1053. A node may only appear once in the trial table at any given time.  If
  1054. an adjacency is found to a node that is already on the trial table, a
  1055. new entry replaces the existing entry if and only if the new total
  1056. cost is lower.  If the cost is higher, it is ignored.  (If the costs
  1057. are equal, then a "tiebreaker" is determined by treating the
  1058. lower-numbered IP address as the lower cost.  This will simply make
  1059. the spanning tree more deterministic in case of tie.)  Thus the trial
  1060. table always contains the lowest cost path to each destination found so
  1061. far.
  1062.  
  1063. Once all of the links from the parent node have had their chance to go 
  1064. onto the trial table, scan the entire trial table for the _one_ entry
  1065. with the lowest total cost.  This not need be a link from that parent
  1066. node!  In case of tie, pick the lower IP address (again just to be
  1067. deterministic).  Move this node to the paths table;  guaranteed,
  1068. there'll be no cheaper path to that node!  The adjacency used for that
  1069. node in the paths table is the adjacency to its parent node.  Note
  1070. that the parent _must_ already be on the paths table since that's the
  1071. source of the parent; you're working your way outward. 
  1072.  
  1073. This new addition to the paths table becomes the new parent node.  
  1074. Repeat the procedure above (from the beginning of V.2) until there are
  1075. no nodes left on the trial table.  This means you've completed the
  1076. spanning tree and have found the least-cost path to every other node.
  1077.  
  1078. One of the router parameters is maximum_cost.  If the cost to a given 
  1079. parent node exceeds this value, the procedure stops, since all 
  1080. subsequent entries in the route table will have a higher cost.  This 
  1081. value has some semblane to the time-to-live parameter of the IP
  1082. packet:  It makes little sense to compute a routing table to nodes
  1083. that cannot be reached within time-to-live.  (Ideally, ttl will be
  1084. implemented using a timer rather than a node counter, but this is
  1085. difficult to do with some of the packet radio data link controller
  1086. implementations; vis., TNCs.)
  1087.  
  1088. A router should recalculate its routes periodically based upon the 
  1089. current links table.  How frequently depends upon the CPU load involved.
  1090. Initial estimates are that it should be recalculated after receipt of
  1091. every routing update bulletin:  Partial calculations do not save
  1092. enough CPU time to make them worthwhile.
  1093.  
  1094.  
  1095. V.3.  Filling in the routing table
  1096.  
  1097. The route table in NOS and NET (the KA9Q et al implementations of IP)
  1098. contains, for each entry, the destination address, number of bits,
  1099. interface, gateway and metric.  This is essentially left intact,
  1100. except that metric is filled in by cost and the routing decision looks
  1101. for the least cost of all matches.  The route table is filled in from
  1102. the paths table.
  1103.  
  1104. Since the routing table will be periodically recalculated from
  1105. scratch, implementation may require two route tables, one "in
  1106. progress" and one "in service".  When the route calculation is
  1107. complete, the "in progress" table becomes "in service" and the old one
  1108. is cleared for reuse.  This allows packet forwarding to continue while
  1109. the completed paths table is being converted into the route table.
  1110.  
  1111. A manual route table may also be maintained.  This should be overriden
  1112. by RSPF-generated entries.  Manual routes are useful defaults before
  1113. RSPF generates routing entries, for destinations not reported on by
  1114. RSPF, and for interworking with other routing protocols.
  1115.  
  1116.  
  1117.  
  1118.  
  1119. Appendix I.  Router parameters
  1120.  
  1121. Every router must set a number of parameters in order to properly
  1122. operate.  While RSPF builds its routing matrix automatically, overall
  1123. network efficiency and stability may require some fine-tuning based
  1124. upon experience.  These include parameters set for each data link
  1125. or subnetwork layer entity (i.e., each radio channel) and for the
  1126. router in general.
  1127.  
  1128. Link/subnet settings:
  1129.  
  1130.    Set Link cost:  This is the cost parameter based upon the link speed
  1131.     and type.  Since the overall cost of the end-to-end path is
  1132.     minimized by the RSPF spanning tree, link cost should be set to
  1133.     arrive at the best overall network performance.  The legal range
  1134.     is 1-127.  This is sent in routing update bulletins.
  1135.  
  1136. Node settings: 
  1137.  
  1138.   Add/Delete Node group: [IPaddr]/bits {cost}.  This allows a node to 
  1139.    announce its ability to serve a group of nodes, identified using 
  1140.    the standard NET convention of address/significant bits.  Thus a 
  1141.    node group setting of [44.56.0.1]/25 will match all nodes from
  1142.    [44.56.0.1] to [44.56.0.127].  Cost is optional; if set, this
  1143.    cost to will be propogated to reach such nodes; otherwise, the 
  1144.    link's default is used. 
  1145.  
  1146.   Set horizon link:   This sets the horizon value for the node's
  1147.    routing bulletins apropos 32-bit addresses of other connected 
  1148.    routers.  This should be high enough to propogate across the 
  1149.    backbone.
  1150.  
  1151.   Set horizon group:  This sets the horizon value for the node's
  1152.    routing bulletins apropos node group addresses (fewer than 32
  1153.    bits matched).  Usually matches the horizon link value.
  1154.  
  1155.   Set horizon local:  This sets the horizon vaue for the node's
  1156.    routing bulletins apropos full link addresses (32 bits) **to
  1157.    non-routers** within the router's node group area.  This is set to
  1158.    a low value so that only other routers serving the same or overlapping
  1159.    node group(s) will receive these messages.
  1160.  
  1161.   Set horizon portable:  This sets the horizon value for the 
  1162.    node's routing bulletins apropos full link addresses (32 bits)
  1163.    not within a node group.  This allows portable end nodes to 
  1164.    have their location in the network propogated farther than
  1165.    the local horizon; this is usually set the same as horizon group.
  1166.  
  1167.   Set broadcast timer:  This sets the time, in seconds, between 
  1168.    router-router hello (RRH) broadcasts.  Initial suggestion:  900.
  1169.  
  1170.   Set suspect timer:  This sets the time, in seconds, after which
  1171.    an adjacency is "suspect" if no packets are received from it.
  1172.    An ICMP echo is then issued.  Initial suggestion:  900.
  1173.  
  1174.   Set suspect count:  This sets the number of times an ICMP echo 
  1175.    (ping) should be sent after a node is suspect, before it is
  1176.    removed from the adjacency list.
  1177.