{"id":232,"date":"2014-10-10T09:36:29","date_gmt":"2014-10-09T22:36:29","guid":{"rendered":"http:\/\/new.radio-active.net.au\/web3\/?page_id=232"},"modified":"2014-10-10T09:36:52","modified_gmt":"2014-10-09T22:36:52","slug":"rspf-spec","status":"publish","type":"page","link":"http:\/\/www.radio-active.net.au\/web3\/80211\/Software\/Routing\/RSPF","title":{"rendered":"RSPF Spec"},"content":{"rendered":"<pre>\r\n\t\t\t\tFred Goldstein   k1io\r\n\t\t\t\tgoldstein@carafe.tay2.dec.com\r\n\t\t\t\tVersion 2.2  2-feb-1992\r\n\r\n\t The Radio Shortest Path First (RSPF) Routing Protocol\r\n\t    For Internet Protocol over Amateur Packet Radio\r\n\r\n\t\t** DRAFT ARCHITECTURE -- FOR COMMENT **\r\n\r\nCONTENTS\r\n\r\nI.   Introduction and Version Notes\r\nII.  Acquisition of router-router adjacencies\r\nIII. Acquisition of end node adjacencies\r\nIV.  Link state propagation\r\nV.   The Shortest Path First Spanning Tree\r\nAppendix A:  Router Parameters\r\nAppendix B:  Schematic Representation of RSPF Tables\r\n\r\n[note:  Significant changes to Version 2.1 are flagged in this text\r\nwith \"**\".]\r\n\r\nI.  Introduction\r\n\r\nThe packet radio environment is a very difficult one for TCP\/IP to run\r\non.  As typically implemented in the Amateur Service, it provides very\r\nlow bandwidths within severely constrained implementations.  The most\r\ncommon radio technology has been 1200 baud single-frequency operation,\r\nalthough higher speeds and some full-duplex operation are also found.\r\nVirtually all amateur packet radio TCP\/IP activity (the AMPRnet) makes\r\nuse of personal computers, most with severely constrained memory address\r\nspace.\r\n\r\nIn this environment, automatic routing of IP packets has not been the\r\nnorm.  Routing protocols designed for other environments are rarely\r\nsatisfactory.  Manual route tables are common.  Most amateur packet\r\nradio operation to date does not even make use of IP; instead, it\r\nconverges applications directly upon a source-routed frame relaying\r\nprotocol called AX.25.  Improved routing support will be an important\r\nfactor in the success of IP.\r\n\r\nMany IP and other wireline networks have implemented link state routing\r\nbased upon Dijkstra's \"SPF\" (shortest path first) spanning tree\r\nalgorithm.  A wireline implementation of SPF for IP is being\r\nstandardized as the Open SPF Interior Gateway Protocol (OSPF), and an\r\nSPF procedure has been accepted by ISO as the standard \"IS-IS\" routing\r\nprotocol for OSI connectionless networks [ISO10589].  A similar (and\r\nderivative) procedure can be applied to AMPRnet (Net 44) and perhaps to\r\nsimilarly-constrained packet radio networks.  It is called Radio\r\nShortest Path First (RSPF);  this document describes the RSPF protocol,\r\nversion 2.2.\r\n\r\nRSPF occupies the role traditionally referred to in TCP\/IP networks as\r\nan \"Interior Gateway Protocol\" (IGP), where \"Gateway\" means \"router\".\r\nIt makes use of the services of the Internet Protocol.  It is not\r\ninconceivable that a router could use both RSPF and another IGP, or\r\ncommunicate with another network using the Exterior Gateway Protocol\r\n(EGP).  However these scenarios are not described in this document.\r\n\r\nRSPF is intended to be implemented on nodes which serve as routers; its\r\nimplementation on end nodes is optional, and not required for the end\r\nnodes to take advantage of routing services.  Any IP station may be an\r\nend node giving no further consideration to routing.\r\n\r\n\r\nI.1. Elements of RSPF\r\n\r\nThe RSPF protocol is designed for use by Internet-layer routing nodes (IP\r\nGateways) in a packet radio network using the Internet Protocol.  It is\r\ncomprised of four major functions:\r\n\r\n\t1) Acquisition of router-router adjacencies\r\n\t2) Acquisition of end node adjacencies\r\n\t3) Link state propagation\r\n\t4) Spanning tree route decision making.\r\n\r\nIts net result is the automatic maintenance of a least-cost routing\r\ntable for use by IP Routing.  RSPF is optimized for the geographically\r\nheirarchical addressing used in AMPRnet, but does not depend upon it.\r\n\r\nRSPF is simpler than OSPF and IS-IS, as it is principally designed for\r\npersonal computer implementation within the Amateur Radio Service.  It\r\nalso adds procedures to take advantage of packet radio's\r\n\"semi-broadcast\" nature.\r\n\r\n\r\nI.2. Addressing convention\r\n\r\nWhen an RSPF router communicates with an end node, it will typically\r\ndeal with a 32 bit IP address.  Routers themselves, however, also\r\nsupport node group addressing (fewer than 32 bits need match).  This\r\nfollows the convention in the KA9Q NOS IP routing program, which permits\r\na crude form of heirarchical addressing as well as allowing portable\r\noperations to override the defaults.  RSPF looks for the match (node or\r\nnode group) with the greatest number of matching bits.  Only if the\r\nnumber of bits matched is equal, then the lower cost path will be used.\r\n\r\nThus a match to a full node address will override a \"cheaper\" path that\r\nmatches its \"subnet\" (node group) of 24 bits, which overrides a 16-bit\r\nnode group, etc., noting that AMPRnet node groups need not follow rigid\r\nIP subnetting rules, and that AMPRnet is a single Class A net.  In every\r\ncase, a greater number of bits matched is considered a superior path to\r\na destination than one that matches fewer bits, regardless of the value\r\nof the routing metric (\"cost\").\r\n\r\n**An extension of this is the handling of manual routes, which are\r\nroutes defined by a manual entry into a table.  Manual routes provide a\r\nuseful starting point during the RSPF convergence, and are required when\r\nRSPF implementation in a given area is limited.  As an order of\r\nprecedence, whether a route is manual or RSPF-generated should only be\r\nused to break ties equal in both subnet size and cost; RSPF-generated\r\nroutes then take precedence.\r\n\r\n\r\nI.3  Subnetworks\r\n\r\nThe generic term used herein for the layer directly beneath IP, creating\r\nthe adjacency between two IP nodes, is subnetwork.  A routing protocol\r\ngains efficiency by recognizing the nature of all subnetworks that it\r\nsupports.  RSPF is intended to work across a specific set of subnetworks\r\nthat occur in packet radio.  (Note that this use of \"subnetwork\" is\r\nconsistent with OSI terminology; the function of the IP \"subnet mask\" in\r\nother IP routing protocols is herein referred to as \"node group\".)\r\n\r\nI.3.1.  Classification by topology\r\n\r\nAll subnworks may be classified according to topology.  An initial\r\ndivision is made between broadcast-topology subnetworks and\r\ngeneral-topology subnetworks.\r\n\r\nI.3.1.1  Broadcast topology.  A broadcast-topology subnetwork is one in\r\nwhich a node may send a single packet which is propagated to all other\r\nnodes, which receive it with high probability.  Ethernet and FDDI are\r\nexamples of broadcast-topology subnetworks.\r\n\r\nI.3.1.2.  General topology.  A general-topology subnetwork is any that\r\ndoes not offer a reasonably reliable broadcast service.  Within this\r\nclassification, an extreme case is a point-to-point subnetwork, with\r\nonly two nodes.  Examples of point-to-point subnetwork protocols are\r\nPPP, SLIP and LAP-B.\r\n\r\nPacket-switched networks are typically general-topology, with wireline\r\nnetworks conforming to CCITT Recommendation X.25 being one example.\r\n\r\nAnother general-topology subnetwork found in packet radio is the type\r\nimplemented by \"TheNet\" (from NordLink) and its clones.  Its network\r\nlayer offers a datagram service to an addressed point, not a useful\r\nbroadcast service, and again with no guarantee of delivery.\r\n\r\nI.3.1.3.  Topologies found in packet radio.  Within the amateur packet\r\nradio world, an example of a broadcast-topology subnetwork might be a\r\npacket \"LAN\" implemented using a full-duplex RF repeater.  However,\r\nthese are relatively rare; the typical single-frequency radio \"LAN\"\r\nusing CSMA or Aloha operation, typified by AX.25 subnetworks, fails the\r\ntest of broadcast topology.  It loses too many packets for routing to be\r\nable to trust unacknowledged delivery.  This is often due to the \"hidden\r\ntransmitter syndrome\" (HTS), the details of which are beyond the scope\r\nof this document.  However, some steps may be taken in order to make use\r\nof the near-broadcast nature of these \"LANs\".  These are \"semi-\r\nbroadcast\" subnetworks.\r\n\r\nI.3.2.  Adjacencies and Subnetwork Access Points\r\n\r\nThe purpose of any subnetwork is to create adjacencies between IP nodes.\r\nEach IP node is identified at the IP layer by its IP address.  Each node\r\nin turn identifies each of its adjacencies as a Subnetwork Access Point\r\n(SNAcP).  A SNAcP is identified within the router by the 2-tuple\r\n{Subnetwork address, Hardware port}.  In the case of a point-to-point\r\nsubnetwork, the subnetwork address component is null.  In the case of\r\nsome other subnetworks, it may be almost arbitrarily complex.  For\r\nexample, an AX.25 \"address\" may consist of a string of addresses by\r\nwhich the AX.25 subnetwork performs source-routed frame relaying.\r\n\r\nThus the actual routing information includes 3-tuples consisting of the\r\nIP destination address or node group as the key, followed by the two\r\nelements of the SNAcP.  The output of RSPF is this routing table.\r\n\r\n\r\nI.3.3. Connection-oriented vs. connectionless subnetworks\r\n\r\nIP is a connectionless (datagram) network protocol, and supports both\r\nconnection-oriented (virtual circuit) and connectionless (datagram)\r\nlower layers (subnets).  In a network with a high packet loss rate, the\r\nlocal retransmission provided by a connection-oriented datalink may\r\nsubstantially improve overall throughput.  However, in a high-speed\r\ndedicated backbone, particularly one implemented using full-duplex radio\r\nor wireline links, connectionless links may provide better overall\r\nperformance.  The choice of which to use is a local matter; RSPF will\r\nwork with both.\r\n\r\n**Connection-oriented subnetworks are assumed here to operate in assured\r\nmode, as is provided with LAP-B.  No connection-oriented non-assured\r\nsubnets, such as wireline Frame Relay, are contemplated for packet radio\r\nRSPF use at this time.\r\n\r\nThe reliability of the routing information, however, may be somewhat\r\ngreater with connection-oriented datalink procedures.  This occurs\r\nboth because the link will have more reliable propagation of network\r\nstate information, and because these will give more rapid indication of\r\na physical link failure.  In a true broadcast-topology subnetwork,\r\nconnectionless operation should suffice.   Much of RSPF's uniqueness\r\ncomes from permitting connectionless operation over unreliable media, a\r\ncombination that appears to be in much demand within the AMPRnet\r\ncommunity.\r\n\r\n\r\nI.4. Relationship to other protocols\r\n\r\nAll packets specific to RSPF shall be exchanged inside IP packets using\r\na protocol identifier which, pending formal assignment of one, shall be\r\n73.  Such IP packets shall be sent with a time to live (TTL) value of 1.\r\nIf broadcast procedures are used over AX.25, connectionless AX.25 UI\r\nframes shall be sent, with a broadcast address \"QST-0\" in the AX.25\r\naddress and **an IP address ending in [.255], indicating multicast.\r\nThis permits different ports on a router to have different broadcast\r\naddresses.  (A router can also \"read the mail\" on passing radio packets\r\nnot addressed to it; such procedures are for further study.)  Equivalent\r\nprocedures may be developed for other subnetworks.\r\n\r\nNote that in this document, \"subnetwork\" and \"data link\" are synonymous,\r\nand refer to the layer over which IP packets are exchanged.\r\n\r\nI.5.  Change history\r\n\r\nI.5.1.  Changes for Version 2.1. (October, 1989)\r\n\r\nRSPF draft 2.0 was released in June, 1988, as the first nearly-\r\nimplementable version.  It was first implemented in September, 1989 by\r\nAnders Klemets.  Version 2.1 reflects changes whose need was discovered\r\nduring this implementation.  These changes are both editorial and, in a\r\nfew cases, substantive.\r\n\r\nThe format of the Routing Update packet was slightly modified.  In order\r\nto prevent fragments of two or more different routing update messages\r\nfrom being erroneously merged, an Envelope ID was added to each such\r\npacket, with the same Envelope ID on all fragments of a multi-packet\r\nmessage.  The term for such a message is now \"envelope\";  it contains\r\none or more \"bulletins\", each of which originated from a single router.\r\n\r\nThere are no longer separate packet types for Full Routing Update and\r\nPartial Routing Update.  Instead, they are distinguished by the value of\r\nthe subsequence number, which is always 0 for Full Routing Updates and\r\nis never 0 for Partial Routing Updates.  A given envelope may contain\r\nboth types of bulletin.\r\n\r\nCost is now set on the basis of receiver instead of transmitter.  This\r\npermits the automatic link quality adjustment to operate on the basis\r\nof locally-received traffic.\r\n\r\nIt is explicitly stated that upon creation of a new router-router\r\nadjacency, the routers exchage full routing information.  This allows\r\nrouters to initialize themselves with a reasonably complete map of the\r\nnetwork.\r\n\r\n1.5.2.  Changes for Version 2.2 (January, 1992)\r\n\r\nVersion 2.1 was actually implemented and deployed in several locations,\r\nproviding a useful input to this version.  The changes in Version 2.2\r\nare intended to be compatible, at the message level, with Version 2.1;\r\nhowever, the internal organization is different.  This should preserve\r\ninteroperability in the face of several changes.  Some descriptive\r\nchanges were made in this document in order to make it less dependent\r\nupon any one implementation or network.\r\n\r\nThe major change is the generalization of the subnetwork and the SNAcP;\r\nthis allows arbitrary subnetworks to be converged under RSPF.  Behavior\r\nof \"private\" and \"manual\" routes is also now explicitly described.\r\n\r\nThe behavior of RSPF in acquiring new adjacencies is also clarified with\r\na new state machine.  A connectionless adjacency is never put into\r\ngeneral use until it is successfully tested.  This fixes an ambiguity in\r\nVersion 2.1 which led to the immediate creation of a \"suspect\" route\r\nupon receipt of a Router-Router Hello message, even if it failed\r\nsuccessive pings.\r\n\r\nSequence number behavior for bulletins is also clarified, with a new\r\ninitialization procedure.  The number space is now linear and finite.\r\n\r\n\r\nII.  Acquisition of router-router adjacencies\r\n\r\nFor RSPF to operate correctly, all routers must remain reasonably\r\ncurrent as to the state of the network at large.  This is handled by the\r\npropagation of \"bulletin\" messages among routers.  End nodes need not\r\nconcern themselves with this; they will normally communicate through one\r\nselected router at any given time, for all (non-adjacent) destinations\r\n(not seen by ARP or other lower-layer procedures).  End nodes can also,\r\nof course, connect to each other directly, bypassing RSPF.\r\n\r\nEach router maintains an adjacencies table.  Each router's adjacency\r\ntable lists the following information for all other nodes, both routers\r\nand end nodes, from which it directly receives packets over a\r\nsubnetwork:\r\n\r\n\tAdjacent node IP address (i.e., 44.56.4.44)\r\n\tAdjacent node subnetwork (eg.,AX.25) address (eg., K1IO-0)\r\n\tSubnet (hardware) used (i.e., AX0)\r\n\tSubnet cost (i.e., 4)\r\n\tNumber of packets heard since last RRH update (i.e., 50)\r\n\tPacket sequence number in last RRH update (i.e., 2593)\r\n\tTime of last RRH update (i.e., 2130).\r\n        **Link state (tentative, good, suspect, lost)\r\n        **Type of service (connection-oriented, connectionless)\r\n\r\n           Table II.1.  Adjacencies table.\r\n\r\nII.1.  Router-router hello\r\n\r\nFor the backbone to create its topology automatically, there must be a\r\nway for routers to discover each other with minimal overhead.  For this\r\npurpose, a router-router hello (RRH) message is provided.  Periodically,\r\nbased upon the value of timer \"rrhtimer\", the router sends out the RRH\r\nmessage to the subnet multicast address and IP multicast address.  RSPF\r\nmakes no assumption of reciprocity (that links are bidirectional);\r\nreceipt of an RRH packet provides the receiver with information about a\r\npotential one-way (received) adjacency.\r\n\r\nIt is noted, however, that while the route testing procedure does not\r\nrequire reciprocity of subnetworks for \"ping\" testing, some\r\nimplementations will require a successful two-way ARP exchange before\r\nthe ICMP Echo packet can be sent.  This often results in some\r\nrequirement for reciprocity in practice, even though it is not a\r\ncharacteristic of RSPF.\r\n\r\n\r\nII.2.  Connection-oriented procedure\r\n\r\nIf a router uses connection-oriented subnet procedures on a given\r\ninterface, then when a router receives an RRH packet on such an\r\ninterface, it checks to see if it already has a link to that packet's\r\noriginator in its own **adjacencies table.  If not, and the interface is\r\nof a broadcast nature (reliable or unreliable), it waits a random\r\nperiod of time (example for AX.25:  within the range of 0 to 10 times\r\nthe link's value of T1, DWAIT or SLOTTIME, and in any case much longer\r\nthan the timers used within a CSMA or Aloha subnet such as AX.25) and\r\nthen attempts to establish a connection in the usual manner.  For\r\nexample, in an AX.25 subnet, the router initiates the connection with\r\nSABM; the distant router responds with the usual UA (link established)\r\nor DM (link rejected).  Failure to initiate a connection (i.e., receive\r\na UA) terminates this procedure; no adjacency is added.\r\n\r\nIf a two-way connection has been established, then both routers add the\r\nlink to their adjacency tables.  While the existence of this route is\r\nset reciprocally, the cost of each side of the route is set separately\r\nfor each side of the connection.  Cost is propagated in the routing\r\nupdate (link state) packet.  Thus the adjacency between two routers is\r\nnot actually used for real traffic until the first routing update packet\r\nexchange has taken place.  (This may be useful in dealing with the\r\nsituation where a UA is lost during link initiation; procedures for\r\ncoping with this known LAP-B problem are for further study.)\r\n\r\nLoss of an adjacency may then be noted by the loss of the subnet\r\nconnection.  When this occurs, the router removes the adjacency from its\r\nadjacency table and follows the \"bad news\" procedures outlined below for\r\nlink state propagation.  (If this cannot be determined by the\r\nimplementation, then \"ping\" procedures as in 1.3.2 below may be useful.)\r\n\r\n\r\nII.3.  Connectionless procedure\r\n\r\nIf a router uses connectionless datalink procedures to its own\r\nadjacencies (most suitable to low-loss links such as broadcast-topology\r\nor reliable general-topology subnetworks), then when a router receives\r\nan RRH packet, it checks to see if this adjacency is already in its\r\nadjacency table.\r\n\r\nII.3.1.  Acquisition of connectionless adjacencies\r\n\r\n**In practice, reliable broadcast topology is unusual in the packet\r\nradio arena.  Thus, the acquisition of a new adjacency begins by setting\r\nthe link status to \"**tentative\".  A tentative-state adjacency is tested\r\nby attempting to exchange a packet (ICMP echo) with it, up to a settable\r\n\"maxping\" number of times.  If successful, the link state is raised to\r\n\"good\".  If unsuccessful, the adjacency is returned to null, ignored,\r\nand not added to any tables.  **If the destination is already reachable\r\nvia a different route, then this prior route should not be discarded; it\r\nshould be returned to use if the newly-tested adjacency fails, or if the\r\nnew adjacency has a higher cost.  (This may be implemented with a \"don't\r\nroute\" function in IP, bypassing the existing IP route table, passing\r\nnormally-hidden subnet information to and from RSPF.)\r\n\r\n**An alternative to ICMP echo for AX.25 and other broadcast and\r\nsemi-broadcast subnets is to directly use ARP to test the adjacency.  In\r\npractice, ICMP will require ARP anyway.  This option raises questions of\r\nlayering, but may solve other problems, such as the existence of a prior\r\nIP route when the available IP layer does not support \"don't route\".\r\n\r\nII.3.2.  Loss of connectionless adjacencies\r\n\r\nLoss of an adjacency may be noted by timeout; if no RRH message is\r\nreceived, and no frames have been received from the adjacent router for\r\na period of time \"suspect timer\" (initial suggestion:  slightly over\r\ntwice the maximum interval \"rrhtimer\" between RRH messages), then the\r\nadjacency state becomes \"suspect\".  The router should attempt (a\r\nsettable number of times \"maxping\") to exchange a packet (ICMP echo)\r\nwith the suspect adjacency;  if unsuccessful (after the usual number of\r\nretries), the adjacency is marked \"lost\".  It may also be marked lost if\r\nother attempts to send data through that router fail, such that the\r\nimplementation determines that there is a high probability that the link\r\nis lost.  (However, no obvious means of doing this is noted.  Thus the\r\n\"ping\" is more likely to be required.)\r\n\r\nII.3.3.  Link states\r\n\r\nFor purposes of route table generation and link state propagation, a\r\nlink whose state is \"tentative\" or \"lost\" is \"bad\";  bad routes are not\r\nused in creating the routing table.  Tentative routes are not\r\npropagated;  newly bad (\"lost\") routes are propagated by the link state\r\n(\"bad news\") propagation procedure, and then dropped.  Links whose state\r\nis \"good\" or \"suspect\" are used for route table generation and are\r\npropagated.\r\n\r\nNote that if a link is connection-oriented, there may be no need for\r\neither a suspect or tentative state; these links are either \"good\",\r\n\"lost\", or \"null\".\r\n\r\n**Table II-1.  State transition table for adjacencies.\r\n\r\n   (Null) ----------> Tentative -----------> Good <----\\ traffic or\r\n           RRH heard     |   ping succeeds    \\  \\-----\/ RRH heard\r\n                          \\                    \\--------->Null      \\---| no RRH\/tfc heard\r\n                           ping fails  \\            v\r\n                                        \\<-Lost<---Suspect\r\n                                               ping\r\n                                               fails\r\n\r\n\r\nII.4.  Manual procedure for general-topology subnetworks\r\n\r\nA general-topology subnetwork may have adjacencies which cannot be\r\ndetected by means of a broadcast-oriented (RRH) procedure.  These links\r\ncannot be automatically added, and alternative procedures are required.\r\nThese links may be connection-oriented or connectionless; the link state\r\ntransition procedure is determined accordingly.\r\n\r\nThe most general way to handle this is to insert these adjacencies\r\nmanually.  The state of these adjacencies is determined the same way as\r\nwith links that are created by hearing RRH messages.  Note that when an\r\nadjacency is manually-initiated across a general-topology subnet, the\r\ninitiating side of the link takes action, while the responding side\r\nshould accept the incoming connection request, and both sides see the\r\nlink.  Thus only one side of the adjacency actually needs to have a\r\nmanual entry.  If a connection already exists to another node across a\r\nsubnetwork, then there is no need to initiate a second connection simply\r\nbecause a manual entry exists.\r\n\r\n**In some cases (such as source-routed frame relay \"digipeating\" over\r\nAX.25), a manual route can be entered to a destination whose first hop,\r\nat least, crosses a broadcast-style subnetwork.  This type of adjacency\r\nmay require manual intervention in the ARP function as well.\r\n\r\nII.4.1.  Semi-automatic discovery\r\n\r\nIn addition to manually-created links across a subnetwork, there exist\r\ncases in which the RSPF router is also a subnet router, and is thus\r\nprivy to routing exchange information generated by that subnetwork.  (An\r\nexample is a node which implements both RSPF and \"TheNet\".)  If the\r\nsubnetwork provides sufficient information such that support of RSPF by\r\nanother node can be inferred (i.e., by a distinctive subnetwork\r\naddress), then RSPF may sequentially initiate appropriate procedures to\r\ndetermine whether or not a useful adjacency exists.\r\n\r\nTranslation of routing metrics into an RSPF link metric is handled on a\r\ncase-by-case basis.  Specific convergence procedures for any such\r\nsubnetwork require further study.\r\n\r\n\r\nTable II-2.  Coding of the RRH PDU.\r\n\r\n\t\t\t\t  1\t \t  2\r\n |0              |8              |6              |4              |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n | RSPF Version #| Type (RRH)    | Checksum                      |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |         Full IP Address of sending router                     |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |  last packet sent seq. #      |  flags        |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |        plaintext                                              |...\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n\r\n\r\nParameters--\r\n\r\n  An RSPF Router-Router Hello packet is sent within IP with a protocol\r\n  ID of <tbd-- 73 suggested>.  Each RRH packet contains the following\r\n  fields:\r\n\r\n   RSPF Version Number:  Version number of this protocol \"22\".\r\n** This packet format is identical with version 21; RSPF22 should\r\n   accept \"21\" as valid.  Future versions \"30\" and above may be\r\n   incompatible.  (Accept anything 2x on receive.)\r\n\r\n    Type:  Value of 3 for RRH.\r\n\r\n    Checksum:  IP-style checksum\r\n\r\n    Address:  Full IP address of sending router\r\n\r\n    Last packet sent sequence number:  An integer (mod 65536)\r\n    incremented by 1 for every frame sent by the subnet across\r\n    this interface.  This value allows receiving entities using\r\n    connectionless procedures to use the automatic link quality\r\n    measurement technique described in II.5.\r\n\r\n    Flags:  The low-order bit is 1 if connectionless datalink is\r\n    preferred on this interface; 0 if connection-oriented is preferred.\r\n    (Set by system management based upon anticipated link quality.)\r\n    Other bits are reserved (sent 0; ignored on receive).  Note that\r\n    some implementations do not support this; \"preferred\" does not\r\n    mean \"mandatory\".\r\n\r\n    Plaintext:  An optional text message (length may be up to maximum\r\n    size remaining in datalink PDU).  This might serve, for example,\r\n    to \"broadcast\" the router's existence to persons who might be\r\n    \"reading the mail\" (monitoring a radio channel promiscuously).\r\n    **It may be noted that a very short RRH message can be received\r\n    intact across a subnetwork that otherwise might not be capable of\r\n    supporting maximum-size packets with reasonable reliability.  This\r\n    should be taken into account when setting the value of Plaintext.\r\n    An explicit minimum is not, however, stated.\r\n\r\n\r\nII.5.  Automatic link quality measurement\r\n \r\n(This procedure was not tested in the implementation of RSPF 2.1, and is\r\ntherefore considered highly experimental!)\r\nA connectionless link or subnetwork may have very reliable, or very\r\nsporadic, performance.  Since there is no procedure for ensuring the\r\nreliability of packets sent over a connectionless link, a high rate of\r\npacket loss may occur without being detected by the routers.  If this\r\nloss is high enough, another route may become a better choice; a high\r\nenough packet loss rate may be enough to mark a link as \"down\".  The\r\nautomatic link quality measurement procedure allows links which are not\r\nyet \"down\", but whose performance is substandard, to be noted.\r\n\r\nEvery router shall maintain, for each link, a count of all packets sent\r\nover each link.  Every time an RRH message is sent, it includes the\r\ncurrent value of this counter (modulo 65536).  Every router also\r\nmaintains, in its adjacency table, a count of the total number of\r\npackets received from said adjacency since the last RRH message, and the\r\nvalue of that counter as received in the last RRH message.\r\n\r\nUpon receipt of an RRH message, the recipient router compares the value\r\nof the received packet counter with the last received value in the\r\nadjacency table.  The difference (taking into account wrap-around at the\r\nmodulus) is compared with the number of packets received since the last\r\nRRH message.  (This works even if an RRH message is lost.)  This packet\r\nloss ratio is then maintained as a guideline to determine link quality.\r\nIf link quality falls below a settable threshhold, the link state is\r\nchanged to suspect.  Timestamp can also be used to compute packet\r\narrival rate.\r\n\r\nConnection-oriented data links presumably deliver 100% of attempted\r\npackets.  A high-quality connectionless link, such as Ethernet\/LLC1,\r\nwill come close to this.  However, single-frequency packet radio links\r\nare prone to packet loss for several reasons, including hidden\r\ntransmitters, lack of collision detection, and rf interference.  The\r\npacket loss ratio is useful in setting link cost, and may also be used\r\nto determine whether a link should use connectionless or\r\nconnection-oriented procedures.\r\n\r\nIf a router reports, in its link update packets, that a given link has a\r\ncost of _n_, then its adjacencies (and only its adjacencies) may apply\r\nthe packet loss ratio to adjust the cost which they maintain in their\r\nlink state tables.  These adjusted costs, rather than the received\r\ncosts, may then be propagated to other routers.\r\n\r\nSuch procedures should be applied sparingly, as each change must be\r\npropagated and could, if used too frequently **or inconsistently across\r\na network, result in network-wide instability.  A suggested\r\n(experimental) algorithm is as follows:  A percentage threshhold x is\r\nset, as is a cost-adjustment factor y.  If fewer than x% of packets are\r\nreceived during a measurement interval, the cost of that adjacency is\r\nmultipled by y.  For example, if x is 80 and y is 1.5, then an adjacency\r\nwith a nominal assigned cost of 4 will be up-costed to 6 if only 70% of\r\npackets are received, but will be restored to 4 if 80% or more are\r\nreceived during the next measurement interval.  The measurement interval\r\nis the time between RRH messages, which typically should precede routing\r\nupdate messages.\r\n\r\n\r\n\r\nIII. Acquisition of end node adjacencies\r\n\r\nFour possible means of automatically determining adjacencies to end\r\nnodes are the inclusion of RSPF in end nodes, the use of connected-mode\r\nsubnet links, the use of ARP, and the use of a \"wiretap\" algorithm (see\r\nRFC981).  Unless a connection mode Data Link layer or subnetwork (with\r\nkeepalive timers) is used, adjacent nodes may need to send each other\r\nmessages at regular intervals (ping) to ensure that the link is still\r\nusable.  A procedure is outlined below for routers and end nodes to\r\nacquire knowledge of each other.\r\n\r\n**Adjacencies may also be set manually.  RSPF maintains a manual routes\r\ntable which may list both individual nodes and node groups that this\r\nrouter will route to absent any other information.  (This is required\r\nfor creating node group support of end nodes.)  Manual adjacencies are\r\ndetermined from the manual routes table.  An entry in the manual route\r\ntable not flagged as private should be propagated as a known adjacency.\r\nPrivate entries are not propagated.  **In the event that a private route\r\nprovides connectivity to a general-topology subnetwork which notifies\r\nthe router of a potential adjacency, this indirect adjacency may be\r\npropagated.  (This latter detail is unproven and may warrant a flag to\r\ndisable, on a system or per-manual-route basis.)\r\n\r\n\r\nIII.1.  RSPF optional in end nodes\r\n\r\nRSPF need not be activated in end nodes; this permits them to use a\r\nsimple version of the TCP\/IP software.  A node that has RSPF support in\r\nits software but operates as an end node can also use the router-router\r\nconnection procedures and simply broadcast its adjacency to the router\r\nin a one-entry bulletin with a **low horizon.  Such a node may also be\r\nsimultaneously homed on two or more other routers, unlike true end nodes\r\nwhose traffic either bypasses RSPF (using ARP) or arrives by way of its\r\nassociated router.\r\n\r\nThere is no \"redirect\" function provided in RSPF.  Since radio does not\r\ngenerally provide a true \"broadcast\" topology subnetwork, a router\r\ncannot presume that if both end nodes can hear it, that both end nodes\r\ncan hear each other.  If an RSPF-equipped end node hears the destination\r\ndirectly, it may test adjacency to that node, via ARP.  If that\r\nsucceeds, then it should choose on its own to route packets there\r\ndirectly, since that one-hop link on an interface will cost less than a\r\ntwo-hop link across the same interface.\r\n\r\n\r\nIII.2  End node subnet connection\r\n\r\nIf an end node knows the IP address of the router which will connect\r\nit to the network at large, it may establish a connected-mode AX.25\r\nor other subnet connection to the router; the presence of this\r\nconnection indicates that the node is reachable from that router,\r\nwhich then adds it to its links table and subsequent bulletins.  This\r\nmay, of course, require an ARP exchange in order to acquire the subnet\r\naddress (eg., the AX.25 address).\r\n\r\n\r\nIII.3.  Connectionless using Address Resolution Protocol\r\n\r\nAlternately, the end node can simply use ARP and use connectionless\r\nlink procedures. In this case the router should assume that the end node\r\nis available until either a rather lengthy timer expires, or the router\r\nis unable to make an ARP contact after the ARP timer expires.  (A loss\r\nof reachability should not be inferred from the ARP timeout.)\r\n\r\nRouters may periodically broadcast their availability (suggested\r\ninterval:  every 15 minutes) with a broadcast frame sent to the\r\nbroadcast address.  In AX.25, this is a UI frame sent to \"QST-0\".  A\r\nhuman-readable (\"unproto\") message may go here, allowing individual\r\noperators to recognize routers and connect as appropriate.  (No specific\r\nPDU coding is provided, as the end nodes do not use RSPF, and thus this\r\nis not really an RSPF packet.  However, the RRH frame may double for\r\nthis function, since its plaintext will generally be readable.)\r\n\r\n\r\nIII.3.1.  Promiscuous ARP\r\n\r\nA router may also choose to use \"Promiscuous ARP\" to provide service to\r\nan end node which is attempting to connect with an IP address reachable\r\nby the router.  In such a case the router should wait an extra interval\r\nafter receiving the ARP request because the desired destination may\r\nactually be directly reachable; ARP procedures may need to be modified\r\nto provide this.\r\n\r\n\r\nIII.4.  Wiretap\r\n\r\nAnother potential approach is for routers to simply listen to AX.25\r\ntraffic on the link and determine who is adjacent to whom.  This is the\r\ngist of the \"wiretap\" algorithm in RFC981, which also finds non-adjacent\r\nnodes by taking advantage of the source routing found in AX.25 frames.\r\nIntegration of wiretap into RSPF is for further study.  (It is not part\r\nof RSPF 2.2.)\r\n\r\n\r\n\r\nIV.  Link state propagation\r\n\r\nLink state information is propagated between routers within bulletin\r\nenvelopes, which are sequences of packets containing partial or full\r\ncopies of the sending node's link state table.  Both point-to-point and\r\nbroadcast procedures are provided.\r\n\r\n\r\nIV.1.  Optional multicast\/broadcast\r\n\r\nPacket radio is inherently a broadcast medium.  Packet radio networks,\r\nhowever, do not necessarily offer a reliable broadcast service, even if\r\nthey happen to use a broadcast physical medium.  It is still possible to\r\nexploit the broadcast nature of the medium.  RSPF link state propagation\r\nprocedures allow but do not require such multicasting.\r\n\r\nIf the link uses connectionless procedures for user data packet\r\nexchange, then broadcast procedures should be used for link state packet\r\nexchange.  The converse may not necessarily be true:  The threshhold of\r\nloss that militates against connectionless transmission of user data may\r\nbe more stringent than that which call for non-broadcast transmission of\r\nlink state packets.  Note that RSPF specifically permits its broadcast\r\nprocedures to be used over subnetworks that do not have the reliability\r\nof true broadcast-topology subnetworks.  This reduces the channel\r\nutilization on radio links.\r\n\r\n\r\nIV.2.  Routing update bulletins\r\n\r\nRouting updates are passed along from router to router via routing\r\nupdate bulletins, which are broadcast within routing update envelopes.\r\nBulletin propagation is designed to make it highly likely that every\r\nnode within a given \"horizon\" eventually receives every routing update\r\nmessage sent out by a given node.\r\n\r\nIV.2.1.  Sequence numbers\r\n\r\nEvery router originates information about changes in its own\r\nadjacencies, as well as periodic retranmissions of its entire list of\r\nadjacencies.  These bulletins are then propagated among other routers.\r\nThe router whose adjacency information is being broadcast is called the\r\n_reporting router_; this may be some hops away from the routers which\r\nforward it to their own adjacencies.  Each reporting router's bulletins\r\n(adjacency updates) contain sequence numbers (and in some cases, a\r\nsubsequence number).  These sequence and subsequence numbers are\r\ngenerated by the reporting router and propagated; they are not changed\r\nwhen a bulletin is relayed.  They are incrememted by 1 every time a new\r\none is generated.\r\n\r\nIV.2.1.1.  Restored sequence numbers\r\n\r\n**If RPSF is restarted, after having been run previously run (i.e., in the\r\nevent of a system restart) before all knowledge of that router has timed\r\nout of the network, then sequence numbers beginning with 1 could cause\r\nthe network to fail to converge, as these bulletins will always appear\r\nobsolete.  A procedure is needed for routers to \"catch up\" with its\r\nprevious sequence number if it is still in the network.\r\n\r\n**When a router first goes into service, its sequence number is\r\ninitialized at 1 (or another low nonzero number).  The router sends RRH\r\nbefore it sends its first bulletin.  This enables it to first receive an\r\nupdate from its own adjacencies.  Even if it sends a bulletin before\r\nreceiving one from its adjacencies, sending a bulletin with a sequence\r\nnumber of 1 will prompt the adjacency to update it.\r\n\r\nWhenever a router receives a bulletin, it examines the contents to see\r\nif its own router number is included as a reporting router.  If so, then\r\nit resets its own sequence number to 1 greater than the sequence number\r\nreceived.  This enables the router to resume its sequence number\r\ngeneration at a higher number than where it left off.  A value of 0 is\r\nnever used for reporting.  However, a router shall respond to receipt of\r\na bulletin with a sequence number of 0 with an update containing the\r\ncurrent sequence number.  (The 0 is thus reserved for use as a \"poll\".)\r\n\r\nIV.2.1.2.  Sequence number exhaust\r\n\r\n**Modular (circular) numbers are not used in RPSF Version 2.2.  Thus a\r\nrouter may eventually exhaust its 16-bit number space, if it is in\r\ncontinuous operation long enough (nearly two years, given 15-minute\r\nupdates).  Should this occur, the router may reinitialize itself by\r\nhalting all bulletin origination for a period long enough for the entire\r\nnetwork to \"forget\" about that router's existence.  Pending further\r\nstudy, a period of two hours is recommended for RSPF in a typical packet\r\nradio environment.\r\n\r\nIV.2.2  Subsequence numbers\r\n\r\nBulletins may also carry change information incremental to previous\r\nbulletins.  These carry the same sequence number as the full routing\r\nupdate bulletin to which they are reporting incremental changes; each\r\nsuch partial routing update bulletin has a subsequence number.  The\r\nsubsequence number is zero for a full routing update bulletin.\r\n\r\nIV.2.3.  Horizon\r\n\r\nEvery bulletin also has a horizon value, set by the reporting router,\r\nassociated with each of its constituent links.  (A given reporting\r\nrouter may have more than one constituent link, if it is a multi-port\r\nrouter.)  Every time a bulletin is propagated, each horizon value is\r\ndecremented by 1.  When it hits zero, the bulletin is not propagated\r\nfurther.  Note that for horizon purposes, a bulletin's individual\r\nconstituent links may have separate horizons; when a link's horizon hits\r\nzero, other links' adjacency information from the same reporting router\r\nmay continue to be propogated.\r\n\r\nIt should also be noted that if a given link has adjacencies with\r\ndifferent horizons, these must be treated as separate links, since\r\nhorizon is reported as a characteristic of a link.  Such a circumstance\r\nmay occur, for example, when a router serves a node group.  Adjacencies\r\nwithin the node group are typically propagated with short horizons,\r\nsince they are only of local interest (i.e., to other nodes in or near\r\nthat node group).  Similarly, the node group itself is propagated with a\r\nlong horizon, across a backbone.  However, adjacencies outside the node\r\ngroup may be propagated with long horizons, as they would not otherwise\r\nbe reached across a backbone dependent upon node groups for long-haul\r\nrouting.\r\n\r\nIV.2.4  Routers table\r\n\r\nEvery router maintains within memory a routers table containing one\r\ntuple for every other router on the network, excepting those which are\r\nunseen because of a horizon.  (An extreme case of this exception is an\r\nend node running RSPF with a horizon of 1, whose existence is only known\r\nto its own adjacencies.)  This tuple contains the following elements:\r\n\r\n\tIP Address (router number)\r\n\tLast received bulletin sequence number\r\n\tLast received bulletin subsequence number\r\n\tTimestamp for when the data was received.\r\n\tHorizon remaining in bulletin when received\r\n\r\nThis table is used to coordinate the receipt and transmission of\r\nbulletins, using either broadcast or non-broadcast procedures.  **If a\r\nrouter chooses to use multiple IP addresses (as is commonplace on the\r\nInternet where different interfaces may use different addresses), only\r\none IP address is used by each router for propagating link state\r\ninformation.   This is used as the router number.\r\n\r\n\r\nIV.3.  Flooding without congestion\r\n\r\nA procedure is used to \"flood\" the network with link state information.\r\nThis is designed to minimize the total amount of information\r\ntransmitted, while maintaining an up-to-date data base on each router.\r\n\r\nIV.3.1.  Upon initialization of adjacencies\r\n\r\nBulletins are forwarded in a routing update envelope which may contain\r\none or more reporting routers' bulletins (adjacency lists), which are\r\nflooded to the network.  A bulletin envelope may actually concatenate\r\nmultiple reporting routers' bulletins; this is in fact the typical case,\r\nwhen routing update packets are exchanged on schedule, and when a given\r\nrouter acquires a new adjacency.  However, partial routing updates (good\r\nnews and bad news) may be sent at any time.\r\n\r\nThe first time an adjacency is acquired, the two routers perform a full\r\nrouting update with each other, exchanging their complete link lists.\r\nOnce this is complete, the routers perform the SPF algorithm and compute\r\nnew routing tables.\r\n\r\nIV.3.2.  Preventing loops and retransmissions\r\n\r\nA bulletin from reporting router X (which lists all of X's adjacencies)\r\nis sent, initially by X, to every adjacent (to X) router A.  This router\r\nA passes it along to all of its own adjacencies B, etc.  This flooding\r\nis controlled such that no reporting router's adjacency update is sent\r\nmore than once between the same pair of routers.\r\n\r\nAfter router A sends its bulletin envelope to B, the recipient router B\r\nthen looks at the sequence number of each reporting router X's adjacency\r\nbulletin within that envelope, and for each reporting router's bulletin,\r\ncompares the sequence number of the just-received adjacency bulletin\r\nwith the highest sequence number previously originated from X.  If the\r\njust-received bulletin is newer (higher number), then it [**for further\r\nstudy: sends a positive acknowledgement to A, and] joins in the flooding\r\nto its own adjacencies.  The horizon is, of course, decremented.\r\n\r\nIf the bulletin from X has the same number as was stored in B, B checks\r\nthe horizon left in the received bulletin against the horizon left when\r\nit previously received the bulletin.  In the event that the latest\r\nbulletin received had a shorter (lower number) horizon left than the\r\nearlier one, it simply ignores [and acknowledges] the (redundant)\r\nmessage.  But if the reporting router X's horizon left is greater for\r\nthe new copy of the bulletin, router B propagates it as if it were a new\r\nbulletin. This way, if the bulletin happened to first arrive via a\r\nroundabout path, it won't accidentally fail to reach the intended end of\r\nits range. (Summary:  Newer or longer-horizon bulletins are both passed\r\nalong.  Same age or older (by sequence number) or same or lower horizon\r\nwill not be propagated.)\r\n\r\nIf any router B receives from router A a bulletin (from any reporting\r\nrouter X) that contains a lower sequence number than one that had\r\npreviously arrived at B from said X, then it can be presumed that A has\r\n\"obsolete\" information.  B replies by sending a bulletin to A with the\r\nlatest link state information for that node X.  As a corollary, a router\r\nmay poll for information about a given reporting router by sending a\r\nrouting update bulletin for that reporting router with a sequence number\r\n**of 0.  Said bulletin may contain zero links' information.\r\n\r\n\r\nIV.4.  Point-to-point bulletin envelope exchange\r\n\r\nA router may acquire routing information from adjacent routers via\r\npoint-to-point procedures which treat every adjacency as a separate\r\nlogical data link.  (Such a procedure also works, of course, over\r\npoint-to-point links such as wirelines.)  This tends to have the highest\r\nreliability, since connection-oriented data link control procedures can\r\nbe used to ensure the accuracy and completeness of the data passed over\r\nthe link.  It has the disadvantage of requiring separate transmission of\r\nthe same data to different adjacent nodes on the same radio channel.\r\n\r\nBulletin envelopes are thus exchanged (when connection-oriented is\r\nselected) periodically (based upon timers) and when new information is\r\nreceived (over a new adjacency, and when good and bad news arrive).\r\nDelivery of these bulletins is considered to be generally reliable.\r\n\r\n\r\nIV.5.  Broadcast bulletin propagation\r\n\r\nWhen a router is adjacent to several other routers via the same\r\nbroadcast (i.e., packet radio) channel, retransmission of routing\r\nbulletins to each adjacency makes additional use of bandwidth, which may\r\nbe a scarce resource.  A broadcast procedure may be used to pass the\r\nbulletin along that link.  Note that broadcast propagation of bulletins\r\nmay be combined with non-broadcast propagation, on a link by link basis.\r\nAlthough packet radio is a broadcast medium, it is not a perfect one:\r\nThe reliability of multicast packets is not as high as for wireline\r\nLANs.  This leads to the need for a unique broadcast \"flooding\"\r\ntechnique.  Note that in a true broadcast-topology subnetwork, these\r\nprocedures add little channel overhead, so these procedures are\r\napplicable there as well.\r\n\r\nIV.5.1.  AX.25 subnetworks\r\n\r\n**At this time, only the AX.25 subnetwork is widely used in AMPRnet\r\nwhile providing a multicast\/broadcast service.  Similar procedures may\r\nbe adapted for use elsewhere.\r\n\r\nA routing update bulletin is broadcast to the Layer 2 multicast AX.25\r\naddress using the IP multicast address.  Individual recipient routers\r\nmay or may not receive the entire bulletin, since there is no\r\nacknowledgement provided.\r\n\r\nIn the previously described case of a non-broadcast message sent via a\r\nconnection-oriented datalink, the entire routing update bulletin can\r\nbe assumed to have been received intact.  Thus, if a given reporting\r\nrouter has originated a new complete list of its adjacencies (new\r\nsequence numbers, subsequence numbers are 0), then any adjacency not\r\nincluded is presumed to have ceased to exist.  Such a presumption is\r\nnot always possible when a bulletin was received via unacknowledged\r\nbroadcast, as the message might have been received in part.  This\r\nshould not make the partially received bulletin unusable.\r\n\r\nA bulletin envelope is transmitted in one or more packets, each of\r\nwhich constitutes a numbered fragment of the whole bulletin envelope.\r\nWithin the transmitted bulletin envelope, each individual reporting\r\nrouter's bulletin begins with a node-header which contains the number\r\nof links being reported on.  Within each bulletin, each link is\r\nidentified by a link header, each of which specifies the number of\r\nadjacencies being reported on (for that link).  Since each IP packet\r\nthat makes up a bulletin contains a fragment number, it is also\r\npossible to determine whether or not a fragment was lost.  Each packet\r\nalso contains an envelope-ID, which prevents accidental mis-assembly\r\nof different bulletins that may arrive close in time.\r\n\r\nIn connection-oriented non-broadcast procedures, a routing update\r\nbulletin (not a partial one with a subsequence numbers>0) provides a\r\ncomplete list of adjacencies known to the sending node, except where the\r\nhorizon is exceeded.  Absence of a previouly-known adjacency then\r\nimplies that the adjacency has been lost.  However, that assumption does\r\nnot apply to fragmented bulletins received in part, which can occur with\r\nbroadcast procedures: If a fragment was lost before reaching the end of\r\na given reporting router's bulletin within the bulletin envelope, then\r\nthe absence of a previously-known adjacency in the received bulletin\r\ndoes not mean that the adjacency was lost.\r\n\r\nRSPF procedures dictate that routing update bulletins with a subsequence\r\nnumber of zero are presumed to be complete lists of adjacencies from\r\ntheir originators; higher subsequence numbers represent incremental\r\nchanges only.  In the broadcast procedures, a routing update bulletin\r\nwith a subsequence number of zero, if received only in part, is\r\ntreated as a partial routing update bulletin.  If it received in full,\r\nit is treated as a full routing update bulletin.\r\n\r\nThus, the recipient compares the sequence number with the previously\r\nreceived sequence number from that reporting router.  If it is higher\r\nthan the previously received one, then its adjacencies are used.  If\r\nit was received in full, and had a subsequence number of 0, then its\r\nprevious adjacencies are replaced (removed if not contained in the\r\nlatest full routing update bulletin).  If it was not received in full,\r\nor if its subsequence number was not zero, then its previous adjacencies\r\nare left intact unless explicitly changed by the received bulletin.\r\n\r\nIf a bulletin is received in full, then the routers table is updated\r\nwith the latest sequence and\/or subsequence number, horizon, and\r\ntimestamp.  If it is received in part, then these entries are not\r\nupdated.  After the bulletin has been completely transmitted, a\r\nrecipient node which has received a partial update from a reporting node\r\nmay poll for that node's latest information, by **originating a bulletin\r\nnaming the reporting router in question, specifying sequence number 0,\r\nwith zero links for that reporting router.  (This is the same polling\r\nprocedure used for non-broadcast links.)\r\n\r\nNote that if a fragment is lost, a reporting router whose node-header is\r\nin the lost fragment will of course remain unchanged in the recipient's\r\ndata base.  Furthermore, any data received in subsequent fragments,\r\nprior to a node-header, will also be meaningless.  The last adjacency\r\nof the last link in a reporting router's bulletin will have the Last\r\nflag set to 1, signaling that following the address, a node header\r\nfollows.  Note also that the first node-header within an envelope is\r\npointed to by the sync byte in the envelope header.  The last flag and\r\nsync byte should match or an error should be noted.\r\n\r\n**IV.5.2.  Reconstructing bulletins from multiple fragments\r\n\r\nIf the resent bulletin is the same one as previously received in part,\r\nand it too is received in part, then if all of the previously received\r\nfragments were stored, the receiving router may attempt to reconstruct\r\nthe entire bulletin from the two (or more) fragmented transmissions.\r\nOnce an entire bulletin has been reconstructed, the receiving router may\r\ntreat this as a complete update.  (This procedure is optional.)\r\n\r\n**IV.5.3.  Non-broadcast unreliable subnets\r\n\r\nIf an adjacency is established across a general-topology subnet that\r\ndoes not offer reliable packet delivery (eg., TheNet packet level), then\r\nbroadcast procedures should be used to exchange routing information\r\nacross the subnet between the two adjacencies.  If the entire bulletin\r\nis received intact, then it should be used; if it is received in part,\r\nthe received portions may be used, and the recipient may poll for a\r\nretransmission as in IV.5.1 and IV.5.2 above.\r\n\r\n\r\nIV.6.  Routing update bulletin packets\r\n\r\nA routing update bulletin envelope (Table IV.1) may contain several\r\ndifferent reporting routers' updated link state information,\r\nconcatenated into one message, with a different sequence number for each\r\nsource (reporting router).  One of the sources, of course, may be the\r\nlocal router.  Each router's link state information is further broken\r\ndown by link, which allows its backbone routing information to be\r\npropogated separately from its local end node adjacency information.\r\n\r\nIV.6.1.  Node group reduction of adjacency list\r\n\r\nIf an end node establishes a connection with a router whose node group\r\ndefault addresses (based on the significant bit count) already include\r\nthat end station, no bulletin need mention that adjacency, as packets to\r\nthat end station will already be routed correctly.  Node groups are\r\ndefined manually.\r\n\r\nIV.6.2.  Incremental changes (good news and bad news)\r\n\r\nBulletins that only report changes in state come in two flavors.  Good\r\nnews bulletins inform other routers that an adjacency has been noted.\r\nbad news bulletins inform them that an adjacency has been lost.\r\nTheoretically, a router could send out a new full routing update\r\nbulletin every time it gained or lost an adjacency. However, the use of\r\nshorter good news and bad news packets, which do not contain a full\r\nrouting update, allow the network to remain relatively current with less\r\ntransmitted traffic.\r\n\r\nGood news and bad news packets are propogated like other packets, but\r\nare not originated by the same rules.  While full routing bulletins are\r\noriginated based upon a timer (rspftimer), good news packets are\r\ntransmitted immediately upon receipt and initiated immediately after an\r\nadjacency is initialized.  This enables new links to be useful quickly.\r\nBad news, however, should not travel as fast:  A node should cache any\r\nbad news message for a time (**recommendation for this timer:\r\nrspftimer\/16) while waiting for the link to come back up.  This helps\r\nkeep the network stable; if the node receives a packet destined for the\r\nlost destination, it may send an ICMP \"host unreachable\" message to the\r\noriginator of the packet, unless it can reroute the packet itself (as\r\nmay happen with the loss of a backbone link when others still exist).\r\n\r\nBecause good news and bad news messages represent changes to the last\r\nfull link state bulletin propogated, but do not purport to completely\r\nrepresent a node's link states, they carry bulletin subsequence\r\nnumbers.  These use the last bulletin sequence number originated by the\r\nreporting router, but the sub-sequence value increments from 1. (A full\r\nlink state packet has a sub-sequence value of 0, and resets the\r\nsubsequence counter.)\r\n\r\nIV.6.3.  Routes to nearby destinations\r\n\r\nSometimes more than one router will serve the same area (determined by\r\nthe significant bits' matching), and they will need to know which one has\r\nthe better path to a given station.  These adjacency messages may only\r\nrequire a short horizon, as will good news and bad news packets which\r\nrefer to end nodes going on and off the air.   Higher horizons are\r\nneeded for backbone routers.\r\n\r\n**This distinction allows routers to define their service area and role\r\nwithin a network by appropriate horizon adjustment.  A router that only\r\nuses short horizons may be useful for providing connectivity within a\r\nconstrained geographic area, typically encompassing one or a small\r\nnumber of node groups, in which not all end users have full connectivity\r\nto a single router.  Such a router will set its horizon_link, reporting\r\non other routers, to a low value.  A router that serves as a backbone\r\nnode, propagating node groups across a wider horizon, will have a high\r\nhorizon_group, reporting node groups, value.  (**Horizon_link and\r\nhorizon_group values are usually set the same.  Horizon_portable is\r\nusually set to the same value as horizon_group and horizon_link;\r\nhorizon_local is set to a low value, so that even a backbone router will\r\nnot propagate intra-node group information across the backbone.)\r\n \r\n\r\nTable IV.1.  Routing update (link state packet) bulletin envelope:\r\n\r\n\t\t\t\t  1\t \t  2\r\n |0              |8              |6              |4              |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----\r\n | RSPF Version #| Type          | fragment #    | fragment total| packet\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -hdr\r\n |       Checksum                | sync byte     | # nodes below |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |  Envelope-ID                  |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----\r\n |         Reporting node #1 full IP Router-Address              | node\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -hdr\r\n |  Node 1 bulletin  sequence #  | sub-sequence #| # links       |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ----\r\n | horizon left   |  ERP factor  |  link cost    |  #adjacencies | link\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ _-hdr_\r\n |significant bits|\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |              Adjacent node(s) 1,1,1 IP address                | adj.\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---\r\n |significant bits|\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |             Adjacent node(s) 1,1,2 IP address                 | adj.\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---\r\n                       ...\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |significant bits|\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |             Adjacent node(s) 1,1,n IP address                 |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---\r\n | horizon left   |  ERP factor  |  link cost    |  #adjacencies | link\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---\r\n |significant bits|\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |             Adjacent node(s) 1,2,1 IP address                 | adj.\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---\r\n                        ...\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |significant bits|\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |             Adjacent node(s) 1,2,n IP address                 | adj.\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---\r\n |         Reporting node #2 full IP Address                     | node\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |  Node 2 bulletin sequence #   | sub-sequence #|  # links      |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---\r\n | horizon left  |  ERP factor   |  link cost    |  #adjacencies | link\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---\r\n |significant bits|\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ adj.\r\n |             Adjacent node(s) 2,1,1 IP address                 |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ---\r\n |significant bits|\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |             Adjacent node(s) 2,1,2 IP address                 |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n                       ...\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n | horizon left    |  ERP factor |  link cost    |  #adjacencies |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |significant bits|\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |             Adjacent node(s) 2,2,1 IP address                 |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n                        ...\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |significant bits|\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |             Adjacent node(s) 2,2,n IP address                 |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n                        ...\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |         Reporting node #n full IP address                     |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n |  Node n bulletin sequence #   | sub-sequence #|   # links     |\r\n +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+\r\n\tetc.\r\n\r\nParameters--\r\n\r\n  An RSPF bulletin packet is sent within IP with a type of <tbd - use 73\r\n  until an official value is assigned>.  Each routing update envelope\r\n  contains an envelope packet header that contains:\r\n\r\n    RSPF Version Number:  Version number of the protocol (22).\r\n\r\n    Type:  (Value 1 for Routing Update Bulletin Envelope)\r\n\r\n    Fragment Number:  States which fragment, in a segmented message,\r\n    this is, beginning at 1.  Non-fragmented messages use 1.\r\n    \r\n    Fragment total:  Total number of fragments in message; 1 if not\r\n    fragmented.\r\n\r\n    Checksum:  IP-style checksum.\r\n\r\n    Sync byte:  Which octet in this packet (counting from this\r\n    byte as byte 0) is the beginning of the first node-header.  If 0,\r\n    this fragment has no node-header.  Non-fragmented messages\r\n    use a value of 4 (because 3 bytes follow in packet header).\r\n\r\n    Number of nodes reporting:  The number of reporting routers in the\r\n    messages that follows (this packet or a sequence of packets forming\r\n    the envelope).\r\n\r\n\r\n  The node-header (for each reporting router) contains 8 octets:\r\n\r\n    Reporting router #n full IP router address:  The IP address of\r\n    the router whose adjacencies are being reported below.  (Note\r\n    that if a router uses separate IP addresses on its links, it\r\n    should still adopt a single one as its router address.)\r\n\r\n    Bulletin sequence number:  When a bulletin is passed along, this\r\n    number is NOT changed; every new bulletin from a given Reporting\r\n    router has a value 1 higher than the previous bulletin from that\r\n    reporting router.\r\n    \r\n    Sub-sequence number:  Good news and bad news packets representing\r\n    incremental changes from the last full report increment this value\r\n    by 1; it is 0 for full bulletins.\r\n\r\n    but not necessarily, representing different types of link in a\r\n    mulitiport gateway) being reported below; the following four octets\r\n    are the header for each link.\r\n\r\n [For each reporting router, adjacencies are reported separately by\r\n  link cost.  This is the received cost value for that data link, after\r\n  any adjustment that may be based upon packet loss ratio.  Adjacencies\r\n  are also reported separately by horizon, even if the cost is the same.\r\n  It does not matter at this point if there are multiple RF or other\r\n  links if their cost and horizon are the same.  Likewise, separate\r\n  received costs or horizons on one link will be treated separately\r\n  and such adjacencies will be grouped under separate link headers\r\n\r\n    Horizon left:  This number is decremented every time a routing update\r\n    bulletin is passed along; when it reaches 0, it is not passed further.\r\n\r\n    Link cost:  A \"figure of merit\" for each link, rising with\r\n    slower\/poorer links.  This is the number whose total is minimized\r\n    by SPF.  The range is 1-127.  As a starting point, a 56000 bps fdx\r\n    backbone link might have a value of 2, a 4800bps hdx link a value\r\n    of 5, a 1200bps hdx link a value of 10 and a 300 bps hf \"wormhole\"\r\n    a value of 20.  An Ethernet or high-speed (1 Mbps+) link might\r\n    then have a value of 1.  A value of 255 denotes the loss of a\r\n    link; this is found in Bad News packets.  These values should be\r\n    coordinated network-wide;  adjusting them will change the way\r\n    packets are routed by RSPF.\r\n\r\n    Number of adjacencies:  The number of adjacencies to be listed for that\r\n    reporting node.\r\n\r\n    ERP Factor:  Used for \"approximating\" a route; contains the number of\r\n    significant bits for which a given node can be presumed to be a valid\r\n    router, even if it doesn't report in detail.  A low factor = wider\r\n    coverage area; thus ERP of 16 means that if NO other match is found for\r\n    a given address, this router will try to handle it if it matches 16\r\n    bits.  Basically a handle for future enhancements; its use will not\r\n    be required in this release of RSPF.\r\n\r\n  For each adjacency of the given link cost, the following is provided:\r\n\r\n    Significant bits: The number of bits used for node group routing\r\n    purposes.  Usually 32 but may be lower if a given link purports to\r\n    serve all end nodes in an area defined using the most-matched-bits\r\n    node group convention.  Higher numbers of bits matched take a higher\r\n    priority than least cost.  This uses the low-order 5 bits of the\r\n    octet.\r\n\r\n    Last-flag:  If this is the last adjacency in the list for this\r\n    reporting router, this value is 1; otherwise it is 0.  (This\r\n    occupies the high-order bit of the significant bits octet.)\r\n\r\n    Full IP address: The full IP address for this node.\r\n\r\nNote that the n,n,n vector within the bulletin has three fields in the\r\nabove representation: Reporting router within bulletin envelope, link\r\ncost\/horizon within reporting router's bulletin, and reporting adjacency\r\nwith that link cost\/horizon.\r\n\r\n\r\nIV.7.  Fragmentation\r\n\r\nIn a moderate to large network, a full routing update can easily exceed\r\nthe maximum size of an AX.25 frame or IP packet.  The RSPF Routing\r\nUpdate message, however, may be sent in fragments.  The IP fragmentation\r\nfunction is not used for this; bulletins are not assumed to be\r\nterminated by a packet boundary.  Each fragment is, however, numbered in\r\nthe packet header, along with an indication of the number of the total\r\nnumber of fragments in that envelope.\r\n\r\nIn order to permit parsing of the incoming fragments by routers who\r\nare using unacknowledged broadcast information (with the high\r\nlikelihood of lost fragments), every bulletin's packet header contains a\r\nsync byte indicator.  This indicates which byte, where the next byte in\r\nthe header is byte 1, is the beginning of a node header.  If a previous\r\nfragment was lost, the receiver should ignore the number of bytes\r\nindicated in the sync byte before resuming parsing of the packet.  (If\r\nthe fragment does not exceed 255 bytes, this will always be sufficient.\r\nIt is recognized that long packets may not be able to use this mechanism\r\nreliably, and a value of \"0\" should be used to indicate that no sync is\r\npossible within this fragment.)\r\n\r\nEach routing update bulletin envelope takes the form of a three-\r\ndimensional list, with the dimensions being reporting router, link and\r\nadjacency. A given bulletin envelope may report on link state from one\r\nor more remote nodes, as well as from the sending node.  Each node may\r\nhave one or more links; each link may have one or more adjacencies.\r\n\r\nPackets may not be fragmented within adjacencies, but may be\r\nfragmented after an adjacency's address and before the next adjacency's\r\nsignificant bits field.  (This presents a 5-octet field that should\r\nnot be fragmented.)  The next fragment, in a new packet, simply begins\r\nwhere the last one left off; the receiver knows how much more to\r\nexpect based upon the node and link count in the respective\r\nnode-header and link-header.\r\n\r\nA router may not start sending a new Routing Update message of any kind\r\nto any given IP address until all fragments of a previous message to\r\nthat address have been transmitted.  This applies both to point to\r\npoint (non-multicast address) and multicast procedures.\r\n\r\n\r\nIV.8.  Bulletin Timers\r\n\r\nThe timers used for bulletin updates must be a compromise between\r\nmaintaing the network's current state and the traffic required to do\r\nso.  An initial suggestion:  Good news messages should be initiated\r\nwithin a few seconds and bad news should wait at least **rspftimer\/16,\r\nwith relatively short horizons on the bulletins (i.e., the routers\r\nwithin the region).  Full routing updates with normal horizons should be\r\nsent out every rspftimer interval (typically 30 minutes).  If the\r\nnetwork is small, more frequent updates may be possible; too frequent\r\nupdates risk choking the network with update traffic.\r\n\r\n\r\n\r\nV.  The Shortest Path First spanning tree algorithm\r\n\r\nAs a routing node comes onto the network, it acquires over time a\r\ncomplete list of adjacencies between other nodes on the network except\r\nas limited by the \"horizon\".  Each adjacency (point to point link)\r\nwithin the entire known network has a \"cost\" associated with it.  It\r\nshould be noted that adjacencies, for the purposes of this algorithm,\r\nare \"logical\" and not necessarily physical;  if a subnetwork link\r\noccurs below IP (as in AX.25 digipieating or TheNet), the two ends of\r\nthe link are still adjacent.  (Adjacency at the IP internet layer is\r\nbased upon subnetworks, which may contain their own links.)\r\n\r\nCost is set for the receive side of each link.  If the receiver and\r\ntransmitter do not agree on cost, the network shall apply different\r\nroutes for packets going in opposite directions between the same two\r\nend nodes.  (This is not a problem.  In a radio environment, one\r\nshould NOT assume reciprocity across a link.)\r\n\r\n\r\nV.1.  Tables\r\n\r\nV.1.1.  Link State Table\r\n\r\nEach router builds a _link state table_ (or links table) that lists, for\r\nevery known link in the network (from every reporting router), the two\r\nends and the cost of that end of the link.  The ends are listed by an IP\r\nrouter address and, for the destination IP router address, a number of\r\nsignificant bits.  This is what is updated by the bulletins and by good\r\nnews\/bad news messages.  Adjacent links also are merged in from the\r\nadjacencies table.\r\n\r\n\tSource IP address\tDest. IP addr\/bits\tCost\r\n\r\n\t44.56.4.44\t\t44.56.4.128\/32\t\t5\r\n\t44.56.4.44\t\t44.56.4.12\/25\t\t10\r\n\r\nV.1.2.  Paths table\r\n\r\nThe goal of the SPF algorithm within RSPF is to build a _paths table_\r\nwhich lists, for every reachable node (or node group approximation of\r\nfewer than 32 bits) on the network, that node address (or node group\r\naddress and number of significant bits), the adjacent node used to get\r\nthere (i.e., where you blast the packets to next), and the total cost of\r\nthe path.  This is done by building a spanning tree with the router doing\r\nthe computation (the home router) as the root of the tree.  The paths\r\ntable thus lists the best way across the tree from the home router to all\r\nknown destinations.\r\n\r\nV.1.2.1.  Route table\r\n\r\n**It should be noted that the only implementation of RSPF to date is\r\nwithin the KA9Q NOS package.  This includes a route table which roughly\r\ncorresponds to the paths table, trusting ARP to provide subnetwork\r\ninformation.  However, RSPF routing makes nominal use of a logical route\r\ntable which includes both the paths table entries and the subnetwork\r\naddress required to reach the first adjacency.  The structure of this\r\ntable's implementation need not be defined here.  It may, for example, be\r\na logical union of the paths table relation (providing IP addresses) with\r\nARP and related subnetwork table relations, using IP address as the\r\ncommon key.  (Thus there is no RSPF route table per se.  This corresponds\r\nto the logical route table in RSPF 2.1.) Or RSPF may supersede these\r\ntables with a separate route table including required hardware and\r\nsubnetwork address information.\r\n\r\nEntries in the route table include:\r\n\r\n        Destination IP Address\r\n        Destination IP Address number of bits (0-32)\r\n        Selected adjacency hardware interface\r\n        Selected adjacency subnetwork address string\r\n        Adjacency IP address\r\n        Cost\r\n\r\nV.1.3.  Trial table\r\n\r\nEvery router contains, for the purposes of building the tree, a\r\n_trial table_ that has three entries:  Destination address\/bits,\r\nadjacent node, and cost of this path.  The paths table additionally\r\nhas one more entry, the _parent_ node, which is the last hop\r\nbefore the destination.  Thus in a path A -> B -> C -> D -> E, home\r\nrouter A views E as the destination, D as the parent, and B as the\r\nadjacency.  Note that in the path from A to B, A is the parent node.\r\n\r\nV.2.  Building the paths table\r\n\r\nBegin building the paths table by using the home router as the first\r\nnode on the paths table.  The cost to reach yourself is always 0, so\r\nmake the first entry on the paths table as follows:  Source=self,\r\ndestination=self, parent=self, and cost=0.  From here on in, parent\r\nis always (by definition of the SPF spanning tree) the node most\r\nrecently added to the paths table.\r\n\r\n\tDestination\tAdjacent \tParent\t\tCost\r\n\r\n\t44.56.0.128\t44.56.0.128\t44.56.4.44\t5\r\n\t44.56.0.131\t44.56.0.128\t44.56.0.128\t10\r\n\t44.56.0.200\t44.56.0.128\t44.56.0.131\t15\r\n\r\n\t\tPaths Table showing relationship between\r\n\tdestination, parent and adjacent nodes, where the home\r\n\tnode is 44.56.4.44 and 44.56.0.200 is three hops away;\r\n\tall hops here have a cost of 5.\r\n\r\n\r\nV.2.1.  Scanning the links\r\n\r\nThe home router now scans its links table looking for all nodes (routers\r\nand end nodes) that are adjacent to the current parent node, except\r\nfor links to nodes which are already on the paths table.  (It is\r\ngenerally fastest to build the paths table by scanning the links table\r\nin order of increasing link cost.)  Each of these new nodes is added\r\nto the trial table, except for the parent node (which is already on\r\nthe paths table, so it can't possibly have a shorter path).  The value\r\nof cost placed on the trial table is the cost of the link from the\r\nparent to the destination plus the cost from home to the parent node\r\n(which value is already on the paths table).\r\n\r\nA node may only appear once in the trial table at any given time.  If\r\nan adjacency is found to a node that is already on the trial table, a\r\nnew entry replaces the existing entry if and only if the new total\r\ncost is lower.  If the cost is higher, it is ignored.  (If the costs\r\nare equal, then a \"tiebreaker\" is determined by treating the\r\nlower-numbered IP address as the lower cost.  This will simply make\r\nthe spanning tree more deterministic in case of tie.)  Thus the trial\r\ntable always contains the lowest cost path to each destination found so\r\nfar.\r\n\r\nOnce all of the links from the parent node have had their chance to go\r\nonto the trial table, scan the entire trial table for the _one_ entry\r\nwith the lowest total cost.  This not need be a link from that parent\r\nnode!  In case of tie, pick the lower IP address (again just to be\r\ndeterministic).  Move this node to the paths table;  guaranteed,\r\nthere'll be no cheaper path to that node!  The adjacency used for that\r\nnode in the paths table is the adjacency to its parent node.  Note\r\nthat the parent _must_ already be on the paths table since that's the\r\nsource of the parent; you're working your way outward.\r\n\r\nThis new addition to the paths table becomes the new parent node.  Repeat\r\nthe procedure above (from the beginning of V.2.1) until there are no\r\nnodes left on the trial table.  This means you've completed the spanning\r\ntree and have found the least-cost path to every other node.\r\n\r\nOne of the router parameters is maximum_cost.  If the cost to a given\r\nparent node exceeds this value, the procedure stops, since all subsequent\r\nentries in the route table will have a higher cost.  This value has some\r\nsemblane to the time-to-live parameter of the IP packet:  It makes little\r\nsense to compute a routing table to nodes that cannot be reached within\r\ntime-to-live.  (Ideally, ttl will be implemented using a timer rather\r\nthan a node counter, but this is difficult to do with some of the packet\r\nradio data link controller implementations; vis., TNCs.)\r\n\r\nA router should recalculate its routes periodically based upon the\r\ncurrent links table.  How frequently depends upon the CPU load involved.\r\nInitial estimates are that it should be recalculated after receipt of\r\nevery routing update bulletin:  Partial calculations do not save\r\nenough CPU time to make them worthwhile.\r\n\r\n\r\nV.3.  Filling in the routing table\r\n\r\n**The route table in NOS (the KA9Q et al implementations of IP)\r\ncontains, for each entry, the destination address, number of bits,\r\ninterface, gateway and metric.  RSPF 2.2 conceptually replaces this with\r\na manual route table (essentially what exists in NOS without RSPF) and a\r\nroute table which RSPF generates itself; when RSPF is activated, this\r\nlatter table is used for packet routing.\r\n\r\n**The route table is filled in from the paths table after each time the\r\nSPF algorithm has finished.  It takes entries from both the paths table\r\nand the manual route table.  Order of precedence is important here.\r\nManual routes have lower precedence than routes taken from the paths\r\ntable, given an equal cost, but a lower cost manual route will override a\r\nhigher-cost paths table entry.\r\n\r\nSince the routing table will be periodically recalculated from\r\nscratch, implementation **requires two separate route tables, one \"in\r\nprogress\" and one \"in service\".  When the route calculation is\r\ncomplete, the \"in progress\" table becomes \"in service\" and the old one\r\nis cleared for reuse.  This allows packet forwarding to continue while\r\nthe completed paths table is being converted into the route table.\r\n**Calculation of the paths table and route table can require substantial\r\nCPU resources, and should not take precedence over packet forwarding.\r\n\r\n\r\nV.4.  Manual routes\r\n\r\nA manual route table may also be maintained.  This takes second\r\nprecedence to RSPF-generated entries in generating the route table.\r\nManual routes are useful defaults before RSPF generates routing entries,\r\nfor destinations not reported on by RSPF, for creating node group\r\nadjacencies, and for interworking with other routing protocols.  **Note\r\nthat manual routes in RSPF 2.2 are (at least logically) not simply\r\nentries in the initial routing table, but are permanent (until changed\r\nmanually) entries in a separate manual route table which is merged into\r\nthe RSPF-generated route table as the last stage of each calculation of\r\nthe route table.  (As an implementation option, the manual route table\r\ncould conceivably be interleaved with the route table, with a \"manual\"\r\nflag on these entries, but the manual entries behave differently.)\r\n\r\n**Note that all manual routes are considered as adjacencies.  This is\r\nobviously wrong at times, but cannot be determined automatically.  Thus\r\nthe private flag is provided.\r\n\r\nEntries in the manual route table include:\r\n\r\n        Destination IP Address\r\n        Destination IP Address number of bits (0-32)\r\n        Selected adjacency hardware interface\r\n        Selected adjacency subnetwork address string\r\n        Adjacency IP address\r\n        Cost\r\n        Flag:  Private\/non-private\r\n\r\n\r\nV.4.1.  Private routes\r\n\r\nAny manual route may be flagged as private.  These routes are used in\r\ncalculating the route table, but are never propagated to other nodes.\r\nDefault routes should always be defined as private, as they do not denote\r\nknown adjacencies, only values that this node will use absent better\r\ninformation.\r\n\r\n\r\n**V.5.  Secondary storage of routing information\r\n\r\nThis section is for study.  It may be unnecessary because adjacencies\r\nwill provide a full report to a router upon initialization of an\r\nadjacency.\r\n\r\nReal implementations of RSPF, especially under single-tasking operating\r\nsystems (such as MS\/PC\/DR-DOS), will not always run continuously without\r\ninterruption.  Nor will all end systems.  When RPSF starts running, it\r\nhas an empty links table, and depends upon manual routes until receiving\r\nlinks information from its adjacencies.  On a packet radio network,\r\ngiven the low bandwidths, this convergence may take excessively long.\r\n\r\nAn implementation may work around this by storing, in non-volatile media\r\n(eg., hard disk) the information needed to quickly resume operation.\r\nThis file (whose internal format is a local matter) should contain a\r\ntimestamp and the last sequence number and subsequence number originated\r\nby this node, followed by the contents of the links table.  This file\r\nshould be stored after a new bulletin (with sequence or subsequence number)\r\nis transmitted.  Only one copy of this file need be stored.  Other tables\r\nmay be optionally stored, for diagnostic purposes, but only the links\r\ntable is required.\r\n\r\nWhen RSPF begins to run, it looks for this file.  If present, it checks\r\nthe timestamp.   If the timestamp is recent (suggested maximum age:  no\r\nolder than twice the rspftimer), then the file should be read into the\r\npaths table.\r\n\r\n\r\nAcknowledgments\r\n\r\nThe author would like the thank the participants in the Internet\r\ntcp-group for their assistance in preparing this, and to the various\r\nradio amateurs who have tested RSPF 2.1 on the air, for their\r\nassistance.  Special thanks to Anders Klemets SM0RGV for drafting the\r\nfirst implementation of RSPF2.1, and to Mike Bilow N1BEE for creating a\r\nstable implementation as well as for his assitance in editing this\r\nrevision.\r\n\r\n\r\nAppendix A.  Router parameters\r\n\r\nEvery router must set a number of parameters in order to properly\r\noperate.  While RSPF builds its routing matrix automatically, overall\r\nnetwork efficiency and stability may require some fine-tuning based\r\nupon experience.  These include parameters set for each data link\r\nor subnetwork layer entity (i.e., each radio channel) and for the\r\nrouter in general.  Commands given below are not necessarily the\r\nstatements used in real implementations.\r\n\r\nLink\/subnet settings:\r\n\r\n   Set Link cost:  This is the cost parameter based upon the link speed\r\n    and type.  Since the overall cost of the end-to-end path is\r\n    minimized by the RSPF spanning tree, link cost should be set to\r\n    arrive at the best overall network performance.  The legal range\r\n    is 1-127.  This is sent in routing update bulletins.\r\n\r\nNode settings:\r\n\r\n  Add\/Delete Node group: [IPaddr]\/bits {cost}.  This allows a node to\r\n   announce its ability to serve a group of nodes, identified using\r\n   the standard NOS convention of address\/significant bits.  Thus a\r\n   node group setting of [44.56.4.1]\/25 will match all nodes from\r\n   [44.56.4.1] to [44.56.4.127].  Cost is optional; if set, this\r\n   cost to will be propogated to reach such nodes; otherwise, the\r\n   link's default is used.  This is fed into the manual route table.\r\n   **A given router may support multiple node groups; this\r\n   facilitatates operation near the boundary of address-subnet\r\n   regions.  Such a router may use a lower node group cost for its own\r\n   node group than for adjacent (or nearby) ones, so that it is not a\r\n   favored route to other groups.  High costs for other node groups are\r\n   still useful because they define whether an adjacency is governed by\r\n   horizon local or horizon portable.  (Use of a Private flag for this\r\n   function, instead of propagating a higher cost, is for further\r\n   study.)\r\n\r\n  Set horizon link:   This sets the horizon value for the node's\r\n   routing bulletins apropos 32-bit addresses of other adjacent\r\n   routers.  This should be high enough to propogate across the\r\n   backbone, if a backbone router.\r\n\r\n  Set horizon group:  This sets the horizon value for the node's\r\n   routing bulletins apropos node group addresses (fewer than 32\r\n   bits matched) nominally served (providing end user adjacencies) by\r\n   this router.  Usually matches the horizon link value.\r\n\r\n  Set horizon local:  This sets the horizon vaue for the node's\r\n   routing bulletins apropos full link addresses (32 bits) to\r\n   non-routers within the router's node group area.  This is set to\r\n   a low value so that only other routers serving the same or\r\n   overlapping node group(s) will receive these messages.\r\n\r\n  Set horizon portable:  This sets the horizon value for the\r\n   node's routing bulletins apropos full link addresses (32 bits)\r\n   to non-router adjacencies not within a supported node group.  This\r\n   allows portable end nodes to have their location in the network\r\n   propogated farther than the local horizon; this is usually set the\r\n   same as horizon group.\r\n\r\n  Set RRH timer:  This sets the time, in seconds, between\r\n   router-router hello (RRH) broadcasts.  Initial suggestion:  900.\r\n\r\n  Set RSPF timer:  This sets the time, in seconds, between newly\r\n   originated link state bulletins.  Initial suggestion:  900.\r\n\r\n  Set suspect timer:  This sets the time, in seconds, after which\r\n   a  connectionless adjacency is \"suspect\" if no packets are\r\n   received from it.  The route is then tested (e.g., pinged).  Initial\r\n   suggestion:  2000.\r\n\r\n  Set suspect count (maxping):  This sets the number of times an ICMP\r\n   echo (ping) should be sent after a node is suspect, before it is\r\n   removed from the adjacency list.  Initial suggestion:  3.\r\n\r\n\r\nAPPENDIX B.  Schematic representation of RSPF tables.\r\n\r\n             ---------------------------------------------------\/ ADJAC.        LINKS                     PATHS     | (SNAcP)\r\n    SUBNETS-->+----+       +------+   [SPF]          +-----+    |\r\n              |II. |------>|V.1.1 |              --->|V.1.2|    |\r\n    RRH IN--->|    |       |      |    TRIAL    \/    |     |    |\r\n              +----+       |      |-->+-----+  \/     +-----+    |\r\n       BULLETINS<--------->+------+   |V.1.3|-\/least    |       |\r\n        |                   ^         |     |  cost     V       |\r\n      +------+        non-  |         +-----+       +-------+   |\r\n      |IV.2.4|      private |                       |V.1.2.1|  \/\r\n      |      |  +-------+--\/                        |       |<-\r\n      +------+  | V.4   |-------------------------->|       |\r\n      ROUTERS   |       |    all manual routes      +-------+\r\n                +-------+                             ROUTE\r\n               MANUAL ROUTE\r\n\r\n        Figure B.  Information flow showing relationship between\r\n        tables.  Numbers in tables refer to sections above which\r\n        introduce each table.\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Fred Goldstein k1io goldstein@carafe.tay2.dec.com Version 2.2 2-feb-1992 The Radio Shortest Path First (RSPF) Routing Protocol For Internet Protocol over Amateur Packet Radio ** DRAFT ARCHITECTURE &#8212; FOR COMMENT ** CONTENTS I. Introduction and Version Notes II. Acquisition of router-router adjacencies &hellip;<\/p>\n<p class=\"read-more\"> <a class=\"more-link\" href=\"http:\/\/www.radio-active.net.au\/web3\/80211\/Software\/Routing\/RSPF\"> <span class=\"screen-reader-text\">RSPF Spec<\/span> Read More &raquo;<\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"parent":230,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"jetpack_post_was_ever_published":false,"footnotes":""},"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/P5cfmK-3K","_links":{"self":[{"href":"http:\/\/www.radio-active.net.au\/web3\/wp-json\/wp\/v2\/pages\/232"}],"collection":[{"href":"http:\/\/www.radio-active.net.au\/web3\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/www.radio-active.net.au\/web3\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/www.radio-active.net.au\/web3\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"http:\/\/www.radio-active.net.au\/web3\/wp-json\/wp\/v2\/comments?post=232"}],"version-history":[{"count":1,"href":"http:\/\/www.radio-active.net.au\/web3\/wp-json\/wp\/v2\/pages\/232\/revisions"}],"predecessor-version":[{"id":233,"href":"http:\/\/www.radio-active.net.au\/web3\/wp-json\/wp\/v2\/pages\/232\/revisions\/233"}],"up":[{"embeddable":true,"href":"http:\/\/www.radio-active.net.au\/web3\/wp-json\/wp\/v2\/pages\/230"}],"wp:attachment":[{"href":"http:\/\/www.radio-active.net.au\/web3\/wp-json\/wp\/v2\/media?parent=232"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}