tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Gloss.     Arch.     IMS     UICC    |    Misc.    |    search     info

RFC 6693

 
 
 

Probabilistic Routing Protocol for Intermittently Connected Networks

Part 3 of 4, p. 55 to 93
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 55 
5.  Detailed Operation

   In this section, some more details on the operation of PRoPHET are
   given along with state tables to help in implementing the protocol.

   As explained in Section 1.2, it is RECOMMENDED that "Success"
   responses should not be requested or sent when operating over a
   reliable, in-order transport protocol such as TCP.  If in the future
   PRoPHET were operated over an unreliable transport protocol, positive
   acknowledgements would be necessary to signal successful delivery of
   (sub)messages.  In this section, the phrase "send a message" should
   be read as *successful* sending of a message, signaled by receipt of
   the appropriate "Success" response if running over an unreliable
   protocol, but guaranteed by TCP or another reliable protocol
   otherwise.  Hence, the state descriptions below do not explicitly
   mention positive acknowledgements, whether they are being sent or
   not.

Top      Up      ToC       Page 56 
5.1.  High-Level State Tables

   This section gives high-level state tables for the operation of
   PRoPHET.  The following sections will describe each part of the
   operation in more detail (including state tables for the internal
   states of those procedures).

   The following main or high-level states are used in the state tables:

   WAIT_NB  This is the state all nodes start in.  Nodes remain in this
         state until they are notified that a new neighbor is available.
         At that point, the Hello procedure should be started with the
         new neighbor, and the node transitions into the HELLO state.
         Nodes SHOULD be able to handle multiple neighbors in parallel,
         maintaining separate state machines for each neighbor.  This
         could be handled by creating a new thread or process during the
         transition to the HELLO state that then takes care of the
         communication with the new neighbor while the parent remains in
         state WAIT_NB waiting for additional neighbors to communicate.
         In this case, when the neighbor can no longer be communicated
         with (described as "Neighbor Gone" in the tables below), the
         thread or process created is destroyed and, when a connection-
         oriented protocol is being used to communicate with the
         neighbor, the connection is closed.  The current version of the
         protocol is specified to use TCP for neighbor connections so
         that these will be closed when the neighbor is no longer
         accessible.

   HELLO Nodes are in the HELLO state from when a new neighbor is
         detected until the Hello procedure is completed and a link is
         established (which happens when the Hello procedure enters the
         ESTAB state as described in Section 5.2; during this procedure,
         the states ESTAB, SYNSENT, and SYNRCVD will be used, but these
         are internal to the Hello procedure and are not listed here).
         If the node is notified that the neighbor is no longer in range
         before a link has been established, it returns to the WAIT_NB
         state, and, if appropriate, any additional process or thread
         created to handle the neighbor MAY be destroyed.

   INFO_EXCH  After a link has been set up by the Hello procedure, the
         node transitions to the INFO_EXCH state in which the
         Information Exchange Phase is done.  The node remains in this
         state as long as Information Exchange Phase TLVs (Routing RIB,
         Routing RIB Dictionary, Bundle Offer, Bundle Response) are
         being received.  If the node is notified that the neighbor is
         no longer in range before all information and bundles have been
         exchanged, any associated connection is closed and the node

Top      Up      ToC       Page 57 
         returns to the WAIT_NB state to await new neighbors.  The
         Timer(keep_alive) is used to ensure that the connection remains
         active.

         In the INFO_EXCH state, the nodes at both ends of the
         established link are able to update their delivery
         predictability information using data from the connected peer
         and then make offers of bundles for exchange which may be
         accepted or not by the peer.  To manage these processes, each
         node acts both as an Initiator and a Listener for the
         Information Exchange Phase processes, maintaining subsidiary
         state machines for the two roles.  The Initiator and Listener
         terms refer to the sending of the Routing RIB information: it
         is perhaps counterintuitive that the Listener becomes the
         bundle offeror and the Initiator the bundle acceptor during the
         bundling passing part.

         The protocol is designed so that the two exchanges MAY be
         carried out independently but concurrently, with the messages
         multiplexed onto on a single bidirectional link (such as is
         provided by the TCP connection).  Alternatively, the exchanges
         MAY be carried out partially or wholly sequentially if
         appropriate for the implementation.  The Information Exchange
         Phase is explained in more detail in Section 3.2.

         When an empty Bundle Response TLV (i.e., no more bundles to
         send) is received, the node starts the Timer(next_exchange).
         When this timer expires, assuming that the neighbor is still
         connected, the Initiator reruns the Information Exchange Phase.
         If there is only one neighbor connected at this time, this will
         have the effect of further increasing the delivery
         predictability for this node in the neighbor, and changing the
         delivery predictabilities as a result of the transitive
         property (Equation 3).  If there is more than one neighbor
         connected or other communication opportunities have happened
         since the previous information exchange occurred, then the
         changes resulting from these other encounters will be passed on
         to the connected neighbor.  The next_exchange timer is
         restarted once the information exchange has completed again.

         If one or more new bundles are received by this node while
         waiting for the Timer(next_exchange) to expire and the delivery
         predictabilities indicate that it would be appropriate to
         forward some or all of the bundles to the connected node, the
         bundles SHOULD be immediately offered to the connected neighbor
         and transferred if accepted.

Top      Up      ToC       Page 58 
    State: WAIT_NB

    +==================================================================+
    |     Condition    |               Action              | New State |
    +==================+===================================+===========+
    |   New Neighbor   | Start Hello procedure for neighbor|   HELLO   |
    |                  |  Keep waiting for more neighbors  |  WAIT_NB  |
    +==================================================================+



    State: HELLO

    +==================================================================+
    |    Condition     |               Action              | New State |
    +==================+===================================+===========+
    |  Hello TLV rcvd  |                                   |   HELLO   |
    +------------------+-----------------------------------+-----------+
    | Enter ESTAB state|  Start Information Exchange Phase | INFO_EXCH |
    +------------------+-----------------------------------+-----------+
    |  Neighbor Gone   |                                   |  WAIT_NB  |
    +==================================================================+



    State: INFO_EXCH

    +==================================================================+
    |    Condition     |               Action              | New State |
    +==================+===================================+===========+
    |     On entry     |     Start Timer(keep-alive)       |           |
    |                  |        Uses Hello Timer interval  | INFO_EXCH |
    +------------------+-----------------------------------+-----------+
    |Info Exch TLV rcvd| (processed by subsidiary state    |           |
    |                  |                         machines) | INFO_EXCH |
    +------------------+-----------------------------------+-----------+
    | No more bundles  |     Start Timer(next_exchange)    | INFO_EXCH |
    +------------------+-----------------------------------+-----------+
    | Keep-alive expiry|     Send Hello SYN message        | INFO_EXCH |
    +------------------+-----------------------------------+-----------+
    |  Hello SYN rcvd  |     Record reception              |           |
    |                  |     Restart Timer(keep-alive)     | INFO_EXCH |
    +------------------+-----------------------------------+-----------+
    |  Neighbor Gone   |                                   |  WAIT_NB  |
    +==================================================================+

Top      Up      ToC       Page 59 
   The keep-alive messages (messages with Hello SYN TLV) are processed
   by the high-level state machine in the INFO_EXCH state.  All other
   messages are delegated to the subsidiary state machines of the
   Information Exchange Phase described in Section 5.3.  The receipt of
   keep-alive messages is recorded and may be used by the subsidiary
   machines to check if the peer is still functioning.  The connection
   will be aborted (as described in Section 4.3.1) if several keep-alive
   messages are not received.

5.2.  Hello Procedure

   The Hello procedure is described by the following rules and state
   tables.  In this section, the messages sent consist of the PRoPHET
   header and a single Hello TLV (see Figure 4 and Section 4.3.1) with
   the HF (Hello Function) field set to the specified value (SYN,
   SYNACK, ACK or RSTACK).

   The state of the L flag in the latest SYN or SYNACK message is
   recorded in the node that receives the message.  If the L flag is set
   (value 1), the receiving node MUST send the payload length for each
   bundle that it offers to the peer during the Information Exchange
   Phase.

   The rules and state tables use the following operations:

   o  The "Update Peer Verifier" operation is defined as storing the
      values of the Sender Instance and Sender Local Address fields from
      a Hello SYN or Hello SYNACK function message received from the
      entity at the far end of the link.

   o  The procedure "Reset the link" is defined as:

      When using TCP or other reliable connection-oriented transport:
           Close the connection and terminate any separate thread or
           process managing the connection.

      Otherwise:

           1.   Generate a new instance number for the link.

           2.   Delete the peer verifier (set to zero the values of
                Sender Instance and Sender Local Address previously
                stored by the Update Peer Verifier operation).

           3.   Send a SYN message.

           4.   Transition to the SYNSENT state.

Top      Up      ToC       Page 60 
   o  The state tables use the following Boolean terms and operators:

      A    The Sender Instance in the incoming message matches the value
           stored from a previous message by the "Update Peer Verifier"
           operation.

      B    The Sender Instance and Sender Local Address fields in the
           incoming message match the values stored from a previous
           message by the "Update Peer Verifier" operation.

      C    The Receiver Instance and Receiver Local Address fields in
           the incoming message match the values of the Sender Instance
           and Sender Local Address used in outgoing Hello SYN, Hello
           SYNACK, and Hello ACK messages.

      SYN    A Hello SYN message has been received.

      SYNACK A Hello SYNACK message has been received.

      ACK    A Hello ACK message has been received.

      &&     Represents the logical AND operation

      ||     Represents the logical OR operation

      !      Represents the logical negation (NOT) operation.

   o  A timer is required for the periodic generation of Hello SYN,
      Hello SYNACK, and Hello ACK messages.  The value of the timer is
      announced in the Timer field.  To avoid synchronization effects,
      uniformly distributed random jitter of +/-5% of the Timer field
      SHOULD be added to the actual interval used for the timer.

      There are two independent events: the timer expires, and a packet
      arrives.  The processing rules for these events are:

             Timer Expires:  Reset Timer
                             If state = SYNSENT Send SYN message
                             If state = SYNRCVD Send SYNACK message
                             If state = ESTAB   Send ACK message

Top      Up      ToC       Page 61 
             Packet Arrives:
                 If incoming message is an RSTACK message:
                     If (A && C && !SYNSENT) Reset the link
                     Else discard the message.
                 If incoming message is a SYN, SYNACK, or ACK message:
                     Response defined by the following State Tables.
                 If incoming message is any other PRoPHET TLV and
                     state != ESTAB:
                     Discard incoming message.
                     If state = SYNSENT Send SYN message(Note 1)
                     If state = SYNRCVD Send SYNACK message(Note 1)

            Note 1: No more than two SYN or SYNACK messages should be
            sent within any time period of length defined by the timer.

   o  A connection across a link is considered to be achieved when the
      protocol reaches the ESTAB state.  All TLVs, other than Hello
      TLVs, that are received before synchronization is achieved will be
      discarded.

5.2.1.  Hello Procedure State Tables

    State: SYNSENT

    +==================================================================+
    |     Condition    |               Action              | New State |
    +==================+===================================+===========+
    |   SYNACK && C    |       Update Peer Verifier;       |   ESTAB   |
    |                  |       Send ACK message            |           |
    +------------------+-----------------------------------+-----------+
    |   SYNACK && !C   |       Send RSTACK message         |  SYNSENT  |
    +------------------+-----------------------------------+-----------+
    |       SYN        |       Update Peer Verifier;       |  SYNRCVD  |
    |                  |       Send SYNACK message         |           |
    +------------------+-----------------------------------+-----------+
    |       ACK        |       Send RSTACK message         |  SYNSENT  |
    +==================================================================+

Top      Up      ToC       Page 62 
    State: SYNRCVD

    +==================================================================+
    |    Condition     |               Action              | New State |
    +==================+===================================+===========+
    |   SYNACK && C    |       Update Peer Verifier;       |   ESTAB   |
    |                  |       Send ACK message            |           |
    +------------------+-----------------------------------+-----------+
    |   SYNACK && !C   |       Send RSTACK message         |  SYNRCVD  |
    +------------------+-----------------------------------+-----------+
    |       SYN        |       Update Peer Verifier;       |  SYNRCVD  |
    |                  |       Send SYNACK message         |           |
    +------------------+-----------------------------------+-----------+
    |  ACK && B && C   |       Send ACK message            |   ESTAB   |
    +------------------+-----------------------------------+-----------+
    | ACK && !(B && C) |       Send RSTACK message         |  SYNRCVD  |
    +==================================================================+



    State: ESTAB

    +==================================================================+
    |    Condition    |               Action               | New State |
    +=================+====================================+===========+
    |  SYN || SYNACK  | Send ACK message (notes 2 and 3)  |   ESTAB   |
    +-----------------+------------------------------------+-----------+
    |  ACK && B && C  | Send ACK message (note 3)          |   ESTAB   |
    +-----------------+------------------------------------+-----------+
    | ACK && !(B && C)|          Send RSTACK message       |   ESTAB   |
    +==================================================================+

      Note 2: No more than two ACK messages should be sent within any
      time period of length defined by the timer.  Thus, one ACK message
      MUST be sent every time the timer expires.  In addition, one
      further ACK message may be sent between timer expirations if the
      incoming message is a SYN or SYNACK.  This additional ACK allows
      the Hello functions to reach synchronization more quickly.

      Note 3: No more than one ACK message should be sent within any
      time period of length defined by the timer.

5.3.  Information Exchange Phase

   After the Hello messages have been exchanged, and the nodes are in
   the ESTAB state, the Information Exchange Phase, consisting of the
   RIB Exchange and Bundle Passing Sub-Phases, is initiated.  This
   section describes the procedure and shows the state transitions

Top      Up      ToC       Page 63 
   necessary in these sub-phases; the following sections describe in
   detail the various TLVs passed in these phases.  On reaching the
   ESTAB state in the high-level HELLO state, there is an automatic
   transition to the INFO_EXCH high-level state.

   PRoPHET runs over a bidirectional transport as documented in
   Section 1.2 so that when a pair of nodes (A and B) have reached the
   ESTAB state, they are able to perform the Information Exchange Phase
   processes for both the A-to-B and B-to-A directions over the link
   that has just been established.  In principle, these two processes
   are independent of each other and can be performed concurrently.
   However, complete concurrency may not be the most efficient way to
   implement the complete process.  As explained in Section 3.2.1, the
   Routing Information Base Dictionary is a shared resource assembled
   from a combination of information generated locally on each node and
   information passed from the peer node.  Overlaps in this information,
   and hence the amount of information that has to be passed between the
   nodes, can be minimized by sequential rather than concurrent
   operation of the dictionary generation and update processes.  It may
   also be possible to reduce the number of bundles that need to be
   offered by the second offeror by examining the offers received from
   the first offeror -- there is no need for the second offeror to offer
   a bundle that is already present in the first offeror's offer list,
   as it will inevitably be refused.

   All implementations MUST be capable of operating in a fully
   concurrent manner.  Each implementation needs to define a policy,
   which SHOULD be configurable, as to whether it will operate in a
   concurrent or sequential manner during the Information Exchange
   Phase.  If it is to operate sequentially, then further choices can be
   made as to whether to interleave dictionary, offer, and response
   exchange parts, or to complete all parts in one direction before
   initiating the other direction.

   Sequential operation will generally minimize the amount of data
   transferred across the PRoPHET link and is especially appropriate if
   the link is half-duplex.  However it is probably not desirable to
   postpone starting the information exchange in the second direction
   until the exchange of bundles has completed.  If the contact between
   the nodes ends before all possible bundles have been exchanged, it is
   possible that postponing the start of bundle exchange in the second
   direction can lead to bundle exchange being skewed in favor of one
   direction over the other.  It may be preferable to share the
   available contact time and bandwidth between directions by
   overlapping the Information Exchange Phases and running the actual
   bundle exchanges concurrently if possible.  Also, if encounters
   expected in the current PRoPHET zone are expected to be relatively
   short, it MAY not be appropriate to use sequential operation.

Top      Up      ToC       Page 64 
   One possible interleaving strategy is to alternate between sending
   from the two nodes.  For example, if the Hello SYN node sends its
   initial dictionary entries while the Hello SYNACK node waits until
   this is complete, the Hello SYNACK node can then prune its proposed
   dictionary entries before sending in order to avoid duplication.
   This approach can be repeated for the second tranche of dictionary
   entries needed for the Bundle Offers and Responses, and also for the
   Bundle Offers, where any bundles that are offered by the Hello SYN
   node that are already present in the Hello SYNACK node need not be
   offered to the Hello SYN node.  This approach is well suited to a
   transport protocol and physical medium that is effectively half-
   duplex.

   At present, the decision to operate concurrently or sequentially is
   purely a matter of local policy in each node.  If nodes have
   inconsistent policies, the behavior at each encounter will depend on
   which node takes the SYN role; this is a matter of chance depending
   on random timing of the start of communications during the encounter.

   To manage the information transfer, two subsidiary state machines are
   created in each node to control the stages of the RIB Exchange Sub-
   Phase and Bundle Passing Sub-Phase processes within the INFO_EXCH
   high-level state as shown in Figure 12.  Each subsidiary state
   machine consists of two essentially independent components known as
   the "Initiator role" and the "Listener role".  One of these
   components is instantiated in each node.  The Initiator role starts
   the Information Exchange Phase in each node and the Listener role
   responds to the initial messages, but it is not a passive listener as
   it also originates messages.  The transition from the ESTAB state is
   a "forking" transition in that it starts both subsidiary state
   machines.  The two subsidiary state machines operate in parallel for
   as long as the neighbor remains in range and connected.

Top      Up      ToC       Page 65 
   + - - - - - - - - +                              + - - - - - - - - +

   |    SYN node     |    PRoPHET messages with:    |   SYNACK node   |

   | +-------------+ | A. Delivery Predictabilities | +-------------+ |
     | Subsidiary  |--->---->---->---->---->---->---->| Subsidiary  |
   | |   State     | | C. Bundle Responses          | |   State     | |
     | Machine 1:  |                                  | Machine 1:  |
   | |  Initiator  | | B. Bundle Offers             | |  Listener   | |
     |    Role     |<----<----<----<----<----<----<---|    Role     |
   | +-------------+ | D. Requested Bundles         | +-------------+ |

   | +-------------+ | A. Delivery Predictabilities | +-------------+ |
     | Subsidiary  |<----<----<----<----<----<----<---| Subsidiary  |
   | |   State     | | C. Bundle Responses          | |   State     | |
     | Machine 2:  |                                  | Machine 2:  |
   | |  Listener   | | B. Bundle Offers             | |  Initiator  | |
     |    Role     |--->---->---->---->---->---->---->|    Role     |
   | +-------------+ | D. Requested Bundles         | +-------------+ |

   + - - - - - - - - +                              + - - - - - - - - +

         The letters (A - D) indicate the sequencing of messages.

      Figure 12: Information Exchange Phase Subsidiary State Machines

   These subsidiary state machines can be thought of as mirror images:
   for each state machine, one node takes on the Initiator role while
   the other node takes on the Listener role.  TLVs sent by a node from
   the Initiator role will be processed by the peer node in the Listener
   role and vice versa.  As indicated in Figure 12, the Initiator role
   handles sending that node's current set of delivery predictabilities
   for known destinations to the Listener role node.  The Listener role
   node uses the supplied values to update its delivery predictabilities
   according to the update algorithms described in Section 2.1.2.  It
   then decides which bundles that it has in store should be offered for
   transfer to the Initiator role node as a result of comparing the
   local predictabilities and those supplied by the Initiator node.
   When these offers are delivered to the Initiator role node, it
   decides which ones to accept and supplies the Listener role node with
   a prioritized list of bundles that it wishes to accept.  The Listener
   role node then sends the requested bundles.

   These exchanges are repeated periodically for as long as the nodes
   remain in contact.  Additionally, if new bundles arrive from other
   sources, they may be offered, accepted, and sent in between these
   exchanges.

Top      Up      ToC       Page 66 
   The PRoPHET protocol is designed so that in most cases the TLV type
   determines the role in which it will be processed on reception.  The
   only exception to this is that both roles may send RIB Dictionary
   TLVs: the Initiator role sends dictionary entries for use in the
   subsequent RIB TLV(s), and the Listener role may send additional
   dictionary entries for use in subsequent Bundle Offer TLVs.  The two
   cases are distinguished by a TLV flag to ensure that they are
   processed in the right role context on reception.  If this flag was
   not provided, there are states where both roles could accept the RIB
   Dictionary TLV, making it impossible to ensure that the correct role
   state machine accepts the RIB Dictionary TLV.  Note that the correct
   updates would be made to the dictionary whichever role processed the
   TLV and that the ambiguity would not arise if the roles are adopted
   completely sequentially, i.e., if the RIB Exchange Sub-Phase and
   associated Bundle Passing Sub-Phase run to completion in one
   direction before the process for the reverse direction is started.

   If sequential operation is selected, the node that sent the Hello SYN
   function message MUST be the node that sends the first message in the
   Information Exchange Phase process.  This ensures that there is a
   well-defined order of events with the Initiator role in the Hello SYN
   node (i.e., the node identified by String ID 0) starting first.  The
   Hello SYNACK node MAY then postpone sending its first message until
   the Listener role state machine in the Hello SYNACK node has reached
   any of a number of points in its state progression according to
   locally configured policy and the nature of the physical link for the
   current encounter between the nodes as described above.  If
   concurrent operation is selected, the Hello SYNACK node can start
   sending messages immediately without waiting to receive messages from
   the peer.

   The original design of the PRoPHET protocol allowed it to operate
   over unreliable datagram-type transports as well as the reliable, in-
   order delivery transport of TCP that is currently specified.  When
   running over TCP, protocol errors and repeated timeouts during the
   Information Exchange Phase SHOULD result in the connection being
   terminated.

5.3.1.  State Definitions for the Initiator Role

   The state machine component with the Initiator role in each node
   starts the transfer of information from one node to its peer during
   the Information Exchange Phase.  The process from the Initiator's
   point of view does the following:

   o  The Initiator role determines the set of delivery predictabilities
      to be sent to the peer node and sends RIB dictionary entries
      necessary to interpret the set of RIB predictability values that

Top      Up      ToC       Page 67 
      are sent after the dictionary updates.  On second and subsequent
      executions of this state machine during a single session with the
      same peer, there may be no RIB Dictionary entries to send.  Either
      an empty TLV can be sent or the TLV can be omitted.

   o  The Initiator then waits to receive any RIB Dictionary updates
      followed by bundle offers from the Listener role on the peer node.

   o  The Initiator determines which of the bundle offers should be
      accepted and, if necessary, reorders the offers to suit its own
      priorities.  The possibly reordered list of accepted bundles is
      sent to the peer node using one or more bundle responses.

   o  The peer then sends the accepted bundles to the Initiator in turn.

   o  Assuming that the link remains open during the bundle sending
      process, the Initiator signals that the Bundle Passing Sub-Phase
      is complete by sending a message with an empty Bundle Response TLV
      (i.e, with the Bundle Offer Count set to 0 and no bundle offers
      following the TLV header).

   o  When the bundle transfer is complete, the Initiator starts the
      Timer(next_exchange).  Assuming that the connection to the
      neighbor remains open, when the timer expires, the Initiator
      restarts the Information Exchange Phase.  During this period,
      Hello SYN messages are exchanged as keep-alives to check that the
      neighbor is still present.  The keep-alive mechanism is common to
      the Initiator and Listener machines and is handled in the high-
      level state machine (see Section 5.1.

   A timer is provided that restarts the Initiator role state machine if
   Bundle Offers are not received after sending the RIB.  If this node
   receives a Hello ACK message containing an Error TLV indicating there
   has been a protocol problem, then the connection MUST be terminated.

   The following states are used:

   CREATE_DR
      The initial transition to this state from the ESTAB state is
      immediate and automatic for the node that sent the Hello SYN
      message.  For the peer (Hello SYNACK sender) node, it may be
      immediate for nodes implementing a fully concurrent process or may
      be postponed until the corresponding Listener has reached a
      specified state if a sequential process is configured in the node
      policy.

Top      Up      ToC       Page 68 
      The local dictionary is initialized when this state is entered for
      the first time from the ESTAB state.  The initial state of the
      dictionary contains two entries: the EID of the node that sent the
      Hello SYN (String ID 0) and the EID of the node that sent the
      Hello SYNACK (String ID 1).  If the peer reports via a Hello ACK
      message containing an Error TLV reporting a Dictionary Conflict or
      Bad String ID error, then the connection MUST be terminated.

      The CREATE_DR state will be entered in the same way from the
      REQUEST state when the Timer(next_exchange) expires, signaling the
      start of a new round of information exchange and bundle passing.

      When in this state:

      *  Determine the destination EIDs for which delivery
         predictabilities will be sent to the peer in a RIB TLV, if any.
         Record the prior state of the local dictionary (assuming that
         String IDs are numbers allocated sequentially, the state
         information needed is just the highest ID used before this
         process started) so that the process can be restarted if
         necessary.  Update the local dictionary if any new EIDS are
         required; format one or more RIB Dictionary TLVs and one or
         more RIB TLVs and send them to the peer.  If there are no
         dictionary entries to send, TLVs with zero entries MAY be sent,
         or the TLV can be omitted, but an empty RIB TLV MUST be sent if
         there is no data to send.  The RIB Dictionary TLVs generated
         here MUST have the Sent by Listener flag set to 0 to indicate
         that they were sent by the Initiator.

      *  If an Error TLV indicating a Dictionary Conflict or
         Bad String ID is received during or after sending the RIB
         Dictionary TLVs and/or the RIB TLVs, abort any in-progress
         Initiator or Listener process, and terminate the connection to
         the peer.

      *  Start a timer (known as Timer(info)) and transition to the
         SEND_DR state.

      Note that when (and only when) running over a transport protocol
      such as TCP, both the RIB Dictionary and RIB information MAY be
      spread across multiple TLVs and messages if required by known
      constraints of the transport protocol or to reduce the size of
      memory buffers.  Alternatively, the information can be formatted
      using a single RIB Dictionary TLV and a single RIB TLV.  These
      TLVs may be quite large, so it may be necessary to segment the
      message either using the PRoPHET submessage capability or, if the
      transport protocol has appropriate capabilities, using those
      inherent capabilities.  This discussion of segmentation applies to

Top      Up      ToC       Page 69 
      the other states and the bundle offer and bundle response messages
      and will not be repeated.

      If more than one RIB TLV is to be used, all but the last one have
      the "More RIB TLVs" flag set to 1 in the TLV flags.  It is not
      necessary to distinguish the last RIB Dictionary TLV because the
      actions taken at the receiver are essentially passive (recording
      the contents), and the sequence is ended by the sending of the
      first RIB TLV.

   SEND_DR
      In this state, the Initiator node expects to be receiving Bundle
      Offers and sending Bundle Responses.  The Initiator node builds a
      list of bundles offered by the peer while in this state:

      *  Clear the set of bundles offered by the peer on entry to the
         state.

      *  If the Timer(info) expires, re-send the RIB Dictionary and RIB
         information sent in the previous CREATE_DR state using the
         stored state to re-create the information.  The RIB dictionary
         update process in the peer is idempotent provided that the
         mappings between the EID and the String ID in the re-sent RIB
         Dictionary TLVs are the same as in the original.  This means
         that it does not matter if some of the RIB Dictionary TLVs had
         already been processed in the peer.  Similarly, re-sending RIB
         TLVs will not cause a problem.

      *  If a message with a RIB Dictionary TLV marked as sent by a
         Listener is received, update the local dictionary based on the
         received TLV.  If any of the entries in the RIB Dictionary TLV
         conflict with existing entries (i.e., an entry is received that
         uses the same String ID as some previously received entry but
         the EID in the entry is different), send a Response message
         with an Error TLV containing a Dictionary Conflict indicator,
         abort any in-progress Initiator or Listener process, and
         terminate the connection to the peer.  Note that in some
         circumstances no dictionary updates are needed, and the first
         message received in this state will carry a Bundle Offer TLV.

      *  If a message with a Bundle Offer TLV is received, restart the
         Timer(info) if the "More Offer/Response TLVs Following" flag is
         set in the TLV; otherwise, stop the Timer(info).  Then process
         any PRoPHET ACKs in the TLV by informing the bundle protocol
         agent, and add the bundles offered in the TLV to the set of
         bundles offered.  If the "More Offer/Response TLVs Following"
         flag is set in the TLV, wait for further Bundle Offer TLVs.  If
         a Bundle Offer TLV is received with a String ID that is not in

Top      Up      ToC       Page 70 
         the dictionary, send a message with an Error TLV containing a
         Bad String ID indicator, abort any in-progress Initiator or
         Listener process, and terminate the connection to the peer.

      *  If the "More Offer/Response TLVs Following" flag is clear in
         the last Bundle Offer TLV received, inspect the set of bundles
         offered to determine the set of bundles that are to be accepted
         using the configured queueing policy.  Record the set of
         bundles accepted so that reception can be checked in the Bundle
         Passing Sub-Phase.  Format one or more Bundle Response TLVs
         flagging the accepted offers and send them to the peer.  If
         more than one Bundle Response TLV is sent, all but the last one
         should have the "More Offer/Response TLVs Following" flag set
         to 1.  At least one Bundle Response TLV MUST be sent even if
         the node does not wish to accept any of the offers.  In this
         case, the Bundle Response TLV contains an empty set of
         acceptances.

      *  If an Error TLV indicating a Bad String ID is received during
         or after sending the Bundle Response TLVs, abort any in-
         progress Initiator or Listener process, re-initialize the local
         dictionary, and terminate the connection to the peer.

      *  Restart the Timer(info) timer in case the peer does not start
         sending the requested bundles.

      *  Transition to state REQUEST.

   REQUEST
      In this state, the Initiator node expects to be receiving the
      bundles accepted in the Bundle Response TLV(s):

      *  Keep track of the bundles received and delete them from the set
         of bundles accepted.

      *  If the Timer(info) expires while waiting for bundles, format
         and send one or more Bundle Response TLVs listing the bundles
         previously accepted but not yet received.  If more than one
         Bundle Response TLV is sent, all but the last one should have
         the "More Offer/Response TLVs Following" flag set to 1.

      *  If an Error TLV indicating a Bad String ID is received during
         or after sending the Bundle Response TLVs, abort any in-
         progress Initiator or Listener process, re-initialize the local
         dictionary, and terminate the connection to the peer.

      *  Restart the Timer(info) timer after each bundle is received in
         case the peer does not continue sending the requested bundles.

Top      Up      ToC       Page 71 
      *  When all the requested bundles have been received, format a
         Bundle Response TLV with the Bundle Offer Count set to zero and
         with the "More Offer/Response TLVs Following" flag cleared to 0
         to signal completion to the peer node.  Also, signal the
         Listener in this node that the Initiator has completed.  If the
         peer node is using a sequential policy, the Listener may still
         be in the initial state, in which case, it needs to start a
         timer to ensure that it detects if the peer fails to start the
         Initiator state machine.  Thereafter, coordinate with the
         Listener state machine in the same node: when the Listener has
         received the completion notification from the peer node and
         this Initiator has sent its completion notification, start
         Timer(next_exchange).

      *  If the Timer(next_exchange) expires, transition to state
         CREATE_DR to restart the Information Exchange Phase.

      Note that if Timer(info) timeout occurs a number of times
      (configurable, typically 3) without any bundles being received,
      then this SHOULD generally be interpreted as the problem that the
      link to the peer is no longer functional and the session should be
      terminated.  However, some bundles may be very large and take a
      long time to transmit.  Before terminating the session, this state
      machine needs to check if a large bundle is actually being
      received although no new completed bundles have been received
      since the last expiry of the timer.  In this case the timer should
      be restarted without sending the Bundle Response TLV.  Also, if
      the bundles are being exchanged over a transport protocol that can
      detect link failure, then the session MUST be terminated if the
      bundle exchange link is shut down because it has failed.

5.3.2.  State Definitions for the Listener Role

   The state machine component with the Listener role in each node
   initially waits to receive a RIB Dictionary update followed by a set
   of RIB delivery predictabilities during the Information Exchange
   Phase.  The process from the point of view of the Listener does the
   following:

   o  Receive RIB Dictionary updates and RIB values from the peer.  Note
      that in some circumstances no dictionary updates are needed, and
      the RIBD TLV will contain no entries or may be omitted completely.

   o  When all RIB messages have been received, the delivery
      predictability update algorithms are run (see Section 2.1.2) using
      the values received from the Initiator node and applying any of
      the optional optimizations configured for this node (see
      Section 2.1.3).

Top      Up      ToC       Page 72 
   o  Using the updated delivery predictabilities and the queueing
      policy and forwarding strategy configured for this node (see
      Section 2.1.4) examine the set of bundles currently stored in the
      Listener node to determine the set of bundles to be offered to the
      Initiator and order the list according to the forwarding strategy
      in use.  The Bundle Offer TLVs are also used to notify the peer of
      any PRoPHET ACKs that have been received by the Listener role
      node.

   o  Send the list of bundles in one or more bundle offers, preceded if
      necessary by one or more RIB dictionary updates to add any EIDs
      required for the source or destination EIDs of the offered
      bundles.  These updates MUST be marked as being sent by the
      Listener role so that they will be processed by the Initiator role
      in the peer.

   o  Wait for the Initiator to send bundle responses indicating which
      bundles should be sent and possibly a modified order for the
      sending.  Send the accepted bundles in the specified order.  The
      bundle sending will normally be carried out over a separate
      connection using a suitable DTN convergence layer.

   o  On completion of the sending, wait for a message with an empty
      Bundle Response TLV indicating correct completion of the process.

   o  The Listener process will be notified if any new bundles or
      PRoPHET ACKs are received by the node after the completion of the
      bundle sending that results from this information exchange.  The
      forwarding policy and the current delivery predictabilities will
      then be applied to determine if this information should be sent to
      the peer.  If it is determined that one or more bundles and/or
      ACKs ought to be forwarded, a new set of bundle offers are sent to
      the peer.  If the peer accepts them by sending bundle responses,
      the bundles and/or ACKS are transferred as previously.

   o  Periodically, the Initiator in the peer will restart the complete
      information exchange by sending a RIB TLV that may be, optionally,
      preceded by RIB Dictionary entries if they are required for the
      updated RIB.

   Timers are used to ensure that the Listener does not lock up if
   messages are not received from the Initiator in a timely fashion.
   The Listener is restarted if the RIB is not received, and a Hello ACK
   message is sent to force the Initiator to restart.  If bundle
   response messages are not received in a timely fashion, the Listener
   re-sends the bundle offers and associated dictionary updates.  The
   following states are used:

Top      Up      ToC       Page 73 
   WAIT_DICT
      The Listener subsidiary state machine transitions to this state
      automatically and immediately from the state ESTAB in both peers.
      This state will be entered in the same way if the
      Timer(next_exchange) expires in the peer, signaling the start of a
      new round of information exchange and bundle passing.  This will
      result in one or more RIB TLVs being sent to the Listener by the
      peer node's Initiator.

      *  When a RIB Dictionary TLV is received, use the TLV to update
         the local dictionary, start or (if it is running) restart the
         Timer(peer) and transition to state WAIT_RIB.  If any of the
         entries in the RIB Dictionary TLV conflict with existing
         entries (i.e., an entry is received that uses the same String
         ID as some previously received entry, but the EID in the entry
         is different), send a Response message with an Error TLV
         containing a Dictionary Conflict indicator, abort any in-
         progress Initiator or Listener process, and terminate the
         connection to the peer.

      *  If a Hello ACK message is received from the peer node,
         transition to state WAIT_DICT and restart the process.

      If multiple timeouts occur (configurable, typically 3), assume
      that the link is broken and terminate the session.  Note that the
      RIB Dictionary and RIB TLVs may be combined into a single message.
      The RIB TLV should be passed on to be processed in the WAIT_RIB
      state.

   WAIT_RIB
      In this state, the Listener expects to be receiving one or more
      RIB TLVs and possibly additional RIB Dictionary TLVs.

      *  On entry to this state, clear the set of received delivery
         predictabilities.

      *  Whenever a new message is received, restart the Timer(peer)
         timer.

      *  If a RIB dictionary TLV is received, use it to update the local
         dictionary and remain in this state.  If any of the entries in
         the RIB Dictionary TLV conflict with existing entries (i.e., an
         entry is received that uses the same String ID as some
         previously received entry, but the EID in the entry is
         different), send a message with an Error TLV containing a
         Dictionary Conflict indicator, abort any in-progress Initiator
         or Listener process, and terminate the connection to the peer.

Top      Up      ToC       Page 74 
      *  If a RIB TLV is received, record the received delivery
         predictabilities for use in recalculating the local delivery
         predictabilities.  If a delivery predictability value is
         received for an EID that is already in the set of received
         delivery predictabilities, overwrite the previously received
         value with the latest value.  If a delivery predictability
         value is received with a String ID that is not in the
         dictionary, send a message with an Error TLV containing a
         Bad String ID indicator, abort any in-progress Initiator or
         Listener process, and terminate the connection to the peer.

      *  When a RIB TLV is received with the "More RIB TLVs" flag
         cleared, initiate the recalculation of delivery
         predictabilities and stop the Timer(peer).  Use the revised
         delivery predictabilities and the configured queueing and
         forwarding strategies to create a list of bundles to be offered
         to the peer node.

      *  Record the state of the local dictionary in case the offer
         procedure has to be restarted.  Determine if any new dictionary
         entries are required for use in the Bundle Offer TLV(s).  If
         so, record them in the local dictionary, then format and send
         RIB Dictionary entries in zero or more RIB Dictionary TLV
         messages to update the dictionary in the peer if necessary.

      *  Format and send Bundle Offer TLV(s) carrying the identifiers of
         the bundles to be offered together with any PRoPHET ACKs
         received or generated by this node.  If more than one Bundle
         Offer TLV is sent, all but the last Bundle Offer TLV sent MUST
         have the "More Offer/Response TLVs Following" flag set to 1.

      *  When all Bundle Offer TLVs have been sent, start the
         Timer(info) and transition to state OFFER.

      *  If the Timer(peer) expires, send a Hello ACK TLV to the peer,
         restart the timer, and transition to state WAIT_DICT.

      *  If an Error TLV indicating a Dictionary Conflict or
         Bad String ID is received during or after sending the RIB
         Dictionary TLVs and/or the Bundle Offer TLVs, abort any in-
         progress Initiator or Listener process, and terminate the
         connection to the peer.

      *  If a Hello ACK message is received from the peer node,
         transition to state WAIT_DICT and restart the process.

Top      Up      ToC       Page 75 
   OFFER
      In this state, the Listener expects to be receiving one or more
      Bundle Response TLVs detailing the bundles accepted by the
      Initiator node.  The ordered list of accepted bundles is
      communicated to the bundle protocol agent, which controls sending
      them to the peer node over a separate connection.

      *  When a Bundle Response TLV is received with a non-zero count of
         Bundle Offers, extract the list of accepted bundles and send
         the list to the bundle protocol agent so that it can start
         transmission to the peer node.  Ensure that the order of offers
         from the TLV is maintained.  Restart the Timer(info) unless the
         last Bundle Response TLV received has the "More Offer/
         Response TLVs Following" flag set to 0.  If a Bundle Response
         TLV is received with a String ID that is not in the dictionary,
         send a message with an Error TLV containing a Bad String ID
         indicator, abort any in-progress Initiator or Listener process,
         and terminate the connection to the peer.

      *  After receiving a Bundle Response TLV with the "More Offer/
         Response TLVs Following" flag set to 0 stop the Timer(info) and
         transition to state SND_BUNDLE.

      *  If the Timer(info) expires, send a Hello ACK TLV to the peer,
         restart the timer and transition to state WAIT_DICT.

      *  If a Hello ACK message is received from the peer node,
         transition to state WAIT_DICT and restart the process.

   SND_BUNDLE
      In this state the Listener monitors the sending of bundles to the
      Initiator peer node.  In the event of disruption in transmission,
      the Initiator node will, if possible, re-send the list of bundles
      that were accepted but have not yet been received.  The bundle
      protocol agent has to be informed of any updates to the list of
      bundles to send (this is likely to involve re-sending one or more
      bundles).  Otherwise, the Listener is quiescent in this state.

      *  When a Bundle Response TLV is received with a non-zero count of
         Bundle Offers, extract the list of accepted bundles and update
         the list previously passed to the bundle protocol agent so that
         it can (re)start transmission to the peer node.  Ensure that
         the order of offers from the TLV is maintained so far as is
         possible.  Restart the Timer(info) unless the last Bundle
         Response TLV received has the "More Offer/Response TLVs
         Following" flag set to 0.  If a Bundle Response TLV is received
         with a String ID that is not in the dictionary, send a message
         with an Error TLV containing a Bad String ID indicator, abort

Top      Up      ToC       Page 76 
         any in-progress Initiator or Listener process, re-initialize
         the local dictionary, and restart the Information Exchange
         Phase as if the ESTAB state had just been reached.

      *  After receiving a Bundle Response TLV with the "More Offer/
         Response TLVs Following" flag set to 0, stop the Timer(info)
         and wait for completion of bundle sending.

      *  If the Timer(info) expires, send a Hello ACK TLV to the peer,
         restart the timer, and transition to state WAIT_DICT.

      *  If a Hello ACK message is received from the peer node,
         transition to state WAIT_DICT and restart the process.

      *  When a Bundle Response TLV is received with a zero count of
         Bundle Offers, the Bundle Passing Sub-Phase is complete.
         Notify the Initiator that the Listener process is complete and
         transition to state WAIT_MORE.

      As explained in the Initiator state REQUEST description, depending
      on the transport protocol (convergence layer) used to send the
      bundles to the peer node, it may be necessary during the bundle
      sending process to monitor the liveness of the connection to the
      peer node in the Initiator process using a timer.

   WAIT_MORE
      In this state, the Listener monitors the reception of new bundles
      that might be received from a number of sources, including

      *  local applications on the node,

      *  other mobile nodes that connect to the node while this
         connection is open, and

      *  permanent connections such as might occur at an Internet
         gateway.

      When the Listener is notified of received bundles, it determines
      if they should be offered to the peer.  The peer may also re-
      initiate the Information Exchange Phase periodically.

      *  When the bundle protocol agent notifies the Listener that new
         bundles and/or new PRoPHET ACKs have been received, the
         Listener applies the selected forwarding policy and the current
         delivery predictabilities to determine if any of the items
         ought to be offered to the connected peer.  If so, it carries

Top      Up      ToC       Page 77 
         out the same operations as are described in the WAIT_RIB state
         to build and send any necessary RIB Dictionary TLVs and RIB
         TLVs to the Initiator in the peer.

      *  When all Bundle Offer TLVs have been sent, start the
         Timer(info) and transition to state OFFER.

      *  If a RIB dictionary TLV is received, use it to update the local
         dictionary and transition to state WAIT_RIB.  If any of the
         entries in the RIB Dictionary TLV conflict with existing
         entries (i.e., an entry is received that uses the same String
         ID as some previously received entry, but the EID in the entry
         is different), send a message with an Error TLV containing a
         Dictionary Conflict indicator, abort any in-progress Initiator
         or Listener process, and terminate the connection to the peer.

      Note that the RIB Dictionary and RIB TLVs may be combined into a
      single message.  The RIB TLV should be passed on to be processed
      in the WAIT_RIB state.

5.3.3.  Recommendations for Information Exchange Timer Periods

   The Information Exchange Phase (IEP) state definitions include a
   number of timers.  This section provides advice and recommendations
   for the periods that are appropriate for these timers.

   Both Timer(info) and Timer(peer) are used to ensure that the state
   machines do not become locked into inappropriate states if the peer
   node does not apparently respond to messages sent in a timely fashion
   either because of message loss in the network or unresponsiveness
   from the peer.  The appropriate values are to some extent dependent
   on the speed of the network connection between the nodes and the
   capabilities of the nodes executing the PRoPHET implementations.
   Values in the range 1 to 10 seconds SHOULD be used, with a value of 5
   seconds RECOMMENDED as default.  The period should not be set to too
   low a value, as this might lead to inappropriate restarts if the
   hardware is relatively slow or there are large numbers of pieces of
   information to process before responding.  When using a reliable
   transport protocol such as TCP, these timers effectively provide a
   keep-alive mechanism and ensure that a failed connection is detected
   as rapidly as possible so that remedial action can be taken (if
   possible) or the connection shut down tidily if the peer node has
   moved out of range.

   Timer(next_exchange) is used to determine the maximum frequency of
   (i.e., minimum period between) successive re-executions of the
   information exchange state machines during a single session between a
   pair of nodes.  Selection of the timer period SHOULD reflect the

Top      Up      ToC       Page 78 
   trade-off between load on the node processor and desire for timely
   forwarding of bundles received from other nodes.  It is RECOMMENDED
   that the timer periods used should be randomized over a range from
   50% to 150% of the base value in order to avoid synchronization
   between multiple nodes.  Consideration SHOULD be given to the
   expected length of typical encounters and the likelihood of
   encounters between groups of nodes when setting this period.  Base
   values in the range of 20 to 60 seconds are RECOMMENDED.

5.3.4.  State Tables for Information Exchange

   This section shows the state transitions that nodes go through during
   the Information Exchange Phase.  State tables are given for the
   Initiator role and for the Listener role of the subsidiary state
   machines.  Both nodes will be running machines in each role during
   the Information Exchange Phase, and this can be done either
   concurrently or sequentially, depending on the implementation, as
   explained in Section 5.3.  The state tables in this section should be
   read in conjunction with the state descriptions in Sections 5.3.1 and
   5.3.2.

5.3.4.1.  Common Notation, Operations and Events

   The following notation is used:

   nS            Node that sent the Hello SYN message.

   nA            Node that sent the Hello SYNACK message.

   The following events are common to the Initiator and Listener state
   tables:

   ErrDC         Dictionary Conflict Error TLV received.

   ErrBadSI      Bad String ID Error TLV received.

   HelloAck      Hello ACK TLV received.  This message is delivered to
                 both Initiator and Listener roles in order to cause a
                 restart of the Information Exchange Phase in the event
                 of message loss or protocol problems.

Top      Up      ToC       Page 79 
   InitStart     Sent by Listener role to Initiator role to signal the
                 Initiator role to commence sending messages to peer.
                 If the Listener instance is running in the node that
                 sent the Hello SYN (nS), then InitStart is signaled
                 immediately when the state is entered.  For the node
                 that sent the Hello SYNACK (nA), InitStart may be
                 signaled immediately if the operational policy requires
                 concurrent operation of the Initiator and Listener
                 roles or postponed until the Listener role state
                 machine has reached a state defined by the configured
                 policy.

   RIBnotlast    RIB TLV received with "More RIB TLVs" flag set to 1.

   RIBlast       RIB TLV received with "More RIB TLVs" flag set to 0.

   REQnotlast    Bundle Response TLV received with More Offer/Response
                 TLVs Following flag set to 1.

   REQlast       Bundle Response TLV received with More Offer/Response
                 TLVs Following flag set to 0.

   RIBDi         RIBD TLV received with Sent by Listener flag set to 0
                 (i.e., it was sent by Initiator role).

   RIBDl         RIBD TLV received with Sent by Listener flag set to 1
                 (i.e., it was sent by Listener role).

   Timeout(info) The Timer(info) has expired.

   Timeout(peer) The Timer(peer) has expired.

   Both the Initiator and Listener state tables use the following common
   operations:

   o  The "Initialize Dictionary" operation is defined as emptying any
      existing local dictionary and inserting the two initial entries:
      the EID of the node that sent the Hello SYN (String ID 0) and the
      EID of the node that sent the Hello SYNACK (String ID 1).

   o  The "Send RIB Dictionary Updates" operation is defined as:

      1.  Determining what dictionary updates will be needed for any
          extra EIDs in the previously selected RIB entries set that are
          not already in the dictionary and updating the local
          dictionary with these EIDs.  The set of dictionary updates may
          be empty if no extra EIDs are needed.  The set may be empty
          even on the first execution if sequential operation has been

Top      Up      ToC       Page 80 
          selected, this is the second node to start and the necessary
          EIDs were in the set previously sent by the first node to
          start.

      2.  Formatting zero or more RIBD TLVs for the set of dictionary
          updates identified in the "Build RIB Entries" operation and
          sends them to the peer.  The RIBD TLVs MUST have the "Sent by
          Listener" flag set to 0 if the updates are sent by the
          Initiator role and to 1 if sent by the Listener role.  In the
          case of the Initiator role, an empty RIBD TLV MUST be sent
          even if the set of updates is empty in order to trigger the
          Listener state machine.

   o  The "Update Dictionary" operation uses received RIBD TLV entries
      to update the local dictionary.  The received entries are checked
      against the existing dictionary.  If the String ID in the entry is
      already in use, the entry is accepted if the EID in the received
      entry is identical to that stored in the dictionary previously.
      If it is identical, the entry is unchanged, but if it is not a
      Response message with an Error TLV indicating Dictionary Conflict
      is sent to the peer in an Error Response message, the whole
      received RIBD TLV is ignored, and the Initiator and Listener
      processes are restarted as if the ESTAB state has just been
      reached.

   o  The "Abort Exchange" operation is defined as aborting any in-
      progress information exchange state machines and terminating the
      connection to the peer.

   o  The "Start TI" operation is defined as (re)starting the
      Timer(info) timer.

   o  The "Start TP" operation is defined as (re)starting the
      Timer(peer) timer.

   o  The "Cancel TI" operation is defined as canceling the Timer(info)
      timer.

   o  The "Cancel TP" operation is defined as canceling the Timer(info)
      timer.

Top      Up      ToC       Page 81 
5.3.4.2.  State Tables for the Initiator Role

   The rules and state tables for the Initiator role use the following
   operations:

   o  The "Build RIB Entries" operation is defined as:

      1.  Recording the state of the local dictionary.

      2.  Determining the set of EIDs for which RIB entries should be
          sent during this execution of the Initiator role state machine
          component.  If this is a second or subsequent run of the state
          machine in this node during the current session with the
          connected peer, then the set of EIDs may be empty if no
          changes have occurred since the previous run of the state
          machine.

      3.  Determining and extracting the current delivery predictability
          information for the set of EIDs selected.

   o  The "Send RIB Entries" operation formats one or more RIB TLVs with
      the set of RIB entries identified in the "Build RIB Entries"
      operation and sends them to the peer.  If the set is empty, a
      single RIB TLV with zero entries is sent.  If more than one RIB
      TLV is sent, all but the last one MUST have the "More RIB TLVs"
      flag set to 1; the last or only one MUST have the flag set to 0.

   o  The "Clear Bundle Lists" operation is defined as emptying the
      lists of bundles offered by the peer and bundles requested from
      the peer.

   o  The "Notify ACKs" operation is defined as informing the bundle
      protocol agent that PRoPHET ACKs has been received for one or more
      bundles in a Bundle Offer TLV using the Bundle Delivered interface
      (see Section 2.2).

   o  The "Record Offers" operation is defined as recording all the
      bundles offered in a Bundle Offer TLV in the list of bundles
      offers.

   o  The "Select for Request" operation prunes and sorts the list of
      offered bundles held into the list of requested bundles according
      to policy and the available resources ready for sending to the
      offering node.

Top      Up      ToC       Page 82 
   o  The "Send Requests" operation is defined as formatting one or more
      non-empty Bundle Response TLVs and sending them to the offering
      node.  If more than one Bundle Offer TLV is sent, all but the last
      one MUST have the "More Offer/Response TLVs Following" flag set to
      1; the last or only one MUST have the flag set to 0.

   o  The "Record Bundle Received" operation deletes a successfully
      received bundle from the list of requests.

   o  The "All Requests Done" operation is defined as formatting and
      sending an empty Bundle Offer TLV, with the "More Offer/Response
      TLVs Following" flag set to 0, to the offering node.

   o  The "Check Receiving" operation is defined as checking with the
      node bundle protocol agent if bundle reception from the peer node
      is currently in progress.  This is needed in case a timeout occurs
      while waiting for bundle reception and a very large bundle is
      being processed.

   o  The "Start NE" operation is defined as (re)starting the
      Timer(next_exchange).

   The following events are specific to the Initiator role state
   machine:

   LastBndlRcvd  Bundle received from peer that is the only remaining
                 bundle in Bundle Requests List.

   NotLastBndlRcvd  Bundle received from peer that is not the only
                 remaining bundle in Bundle Requests List.

   OFRnotlast    Bundle Offer TLV received with "More Offer/Response
                 TLVs Following" flag set to 1.

   OFRlast       Bundle Offer TLV received with "More Offer/Response
                 TLVs Following" flag set to 0

   Timeout(next_exch)  The Timer(next_exchange) has expired

Top      Up      ToC       Page 83 
    State: CREATE_DR

    +==================================================================+
    |     Condition    |               Action              | New State |
    +==================+===================================+===========+
    |     On Entry     |    If previous state was ESTAB:   |           |
    |                  |         Initialize Dictionary     |           |
    |                  |    Always:                        |           |
    |                  |         Build RIB Entries         |           |
    |                  |         Wait for Init Start       | CREATE_DR |
    +------------------+-----------------------------------+-----------+
    |    InitStart     |    Send RIB Dictionary Updates    |           |
    |                  |    Send RIB Entries               |           |
    |                  |    Start TI                       |  SEND_DR  |
    +------------------+-----------------------------------+-----------+
    |      ErrDC       |           Abort Exchange          |(finished) |
    +------------------+-----------------------------------+-----------+
    |     ErrBadSI     |           Abort Exchange          |(finished) |
    +------------------+-----------------------------------+-----------+
    |     HelloAck     |           Abort Exchange          | CREATE_DR |
    +==================================================================+

Top      Up      ToC       Page 84 
    State: SEND_DR

    +==================================================================+
    |     Condition    |               Action              | New State |
    +==================+===================================+===========+
    |     On Entry     |         Clear Bundle Lists        |  SEND_DR  |
    +------------------+-----------------------------------+-----------+
    |  Timeout(info)   |   Send RIB Dictionary Updates     |           |
    |                  |   Send RIB Entries (note 1)       |  SEND_DR  |
    +------------------+-----------------------------------+-----------+
    |  RIBDl received  |   Update Dictionary (note 2)      |           |
    |                  |   If Dictionary Conflict found:   |           |
    |                  |           Abort Exchange          | CREATE_DR |
    |                  |   Else:                           |           |
    |                  |           Start TI                |  SEND_DR  |
    +------------------+-----------------------------------+-----------+
    |    OFRnotlast    |           Notify ACKs             |           |
    |                  |           Record Offers           |           |
    |                  |           Start TI                |  SEND_DR  |
    +------------------+-----------------------------------+-----------+
    |     OFRlast      |           Cancel TI               |           |
    |                  |           Notify ACKs             |           |
    |                  |           Record Offers           |           |
    |                  |           Select for Request      |           |
    |                  |           Send Requests           |           |
    |                  |           Start TI                |  REQUEST  |
    +------------------+-----------------------------------+-----------+
    |      ErrDC       |           Abort Exchange          |(finished) |
    +------------------+-----------------------------------+-----------+
    |     ErrBadSI     |           Abort Exchange          |(finished) |
    +------------------+-----------------------------------+-----------+
    |     HelloAck     |           Abort Exchange          | CREATE_DR |
    +==================================================================+

Top      Up      ToC       Page 85 
    State: REQUEST

    +==================================================================+
    |     Condition    |               Action              | New State |
    +==================+===================================+===========+
    |  Timeout(info)   |  Check Receiving                  |           |
    |                  |  If bundle reception in progress: |           |
    |                  |         Start TI                  |  REQUEST  |
    |                  |  Otherwise:                       |           |
    |                  |         Send Requests             |           |
    |                  |         Start TI (note 3)         |  REQUEST  |
    +------------------+-----------------------------------+-----------+
    | NotLastBndlRcvd  |     Record Bundle Received        |           |
    |                  |     Start TI                      |  REQUEST  |
    +------------------+-----------------------------------+-----------+
    |   LastBndlRcvd   |     Cancel TI                     |           |
    |                  |     All Requests Done             |           |
    |                  |     Start NE                      |  REQUEST  |
    +------------------+-----------------------------------+-----------+
    |Timeout(next_exch)|                                   | CREATE_DR |
    +------------------+-----------------------------------+-----------+
    |     HelloAck     |     Abort Exchange                | CREATE_DR |
    +==================================================================+

   Note 1:
      No response to the RIB has been received before the timer expired,
      so we re-send the dictionary and RIB TLVs.  If the timeout occurs
      repeatedly, it is likely that communication has failed and the
      connection MUST be terminated.

   Note 2:
      If a Dictionary Conflict error has to be sent, the state machine
      will be aborted.  If this event occurs repeatedly, it is likely
      that there is either a serious software problem or a security
      issue.  The connection MUST be terminated.

   Note 3:
      Remaining requested bundles have not arrived before the timer
      expired, so we re-send the list of outstanding requests.  If the
      timeout occurs repeatedly, it is likely that communication has
      failed and the connection MUST be terminated.

Top      Up      ToC       Page 86 
5.3.4.3.  State Tables for the Listener Role

   The rules and state tables for the Listener role use the following
   operations:

   o  The "Clear Supplied RIBs" operation is defined as setting up an
      empty container to hold the set of RIBs supplied by the peer node.

   o  The "Record RIBs Supplied" operation is defined as:

      1.  Taking the RIB entries from a received RIB TLV.

      2.  Verifying that the String ID used in each entry is present in
          the dictionary.  If not, an Error TLV containing the offending
          String ID is sent to the peer, and the Initiator and Listener
          processes are aborted and restarted as if the ESTAB state had
          just been reached.

      3.  If all the String IDs are present in the dictionary, record
          the delivery predictabilities for each EID in the entries.

   o  The "Recalc Dlvy Predictabilities" operation uses the algorithms
      defined in Section 2.1.2 to update the local set of delivery
      predictabilities using the using the set of delivery
      predictabilities supplied by the peer in RIB TLVs.

   o  The "Determine Offers" operation determines the set of bundles to
      be offered to the peer.  The local delivery predictabilities and
      the delivery predictabilities supplied by the peer are compared,
      and a prioritized choice of the bundles stored in this node to be
      offered to the peer is made according to the configured queueing
      policy and forwarding strategy.

   o  The "Determine ACKs" operation is defined as obtaining the set of
      PRoPHET ACKs recorded by the bundle protocol agent that need to be
      forwarded to the peer.  The list of PRoPHET ACKs is maintained
      internally by the PRoPHET protocol implementation rather than the
      main bundle protocol agent (see Section 3.5).

   o  The "Determine Offer Dict Updates" operation is defined as
      determining any extra EIDs that are not already in the dictionary,
      recording the previous state of the local dictionary, and then
      adding the required extra entries to the dictionary.

Top      Up      ToC       Page 87 
   o  The "Send Offers" operation is defined as formatting one or more
      non-empty Bundle Offer TLVs, incorporating the sets of Offers and
      PRoPHET ACKs previously determined, and sending them to the peer
      node.  If more than one Bundle Offer TLV is sent, all but the last
      one MUST have the "More Offer/Response TLVs Following" flag set to
      1; the last or only one MUST have the flag set to 0.

   o  The "Record Requests" operation is defined as recording all the
      bundles offered in a Bundle Offer TLV in the list of bundles
      offers.  Duplicates MUST be ignored.  The order of requests in the
      TLVs MUST be maintained so far as is possible (it is possible that
      a bundle has to be re-sent, and this may result in out-of-order
      delivery).

   o  The "Send Bundles" operation is defined as sending, in the order
      requested, the bundles in the requested list.  This requires the
      list to be communicated to the bundle protocol agent (see
      Section 2.2).

   o  The "Check Initiator Start Point" operation is defined as checking
      the configured sequential operation policy to determine if the
      Listener role has reached the point where the Initiator role
      should be started.  If so, the InitStart notification is sent to
      the Initiator role in the same node.

   The following events are specific to the Listener role state machine:

   RIBnotlast    RIB TLV received with "More RIB TLVs" flag set to 1.

   RIBlast       RIB TLV received with "More RIB TLVs" flag set to 0 and
                 a non-zero count of RIB Entries.

   REQnotlast    Bundle Response TLV received with More Offer/Response
                 TLVs Following flag set to 1.

   REQlast       Bundle Response TLV received with More Offer/Response
                 TLVs Following flag set to 0 and a non-zero count of
                 bundle offers.

   REQempty      Bundle Response TLV received with More Offer/Response
                 TLVs Following flag set to 0 and a zero count of bundle
                 offers.

Top      Up      ToC       Page 88 
    State: WAIT_DICT

    +==================================================================+
    |     Condition    |               Action              | New State |
    +==================+===================================+===========+
    |     On Entry     |     Check Initiator Start Point   | WAIT_DICT |
    +------------------+-----------------------------------+-----------+
    |       RIBDi      |     Update Dictionary (note 1)    |           |
    |                  |     If Dictionary Conflict found: |           |
    |                  |           Abort Exchange          |(finished) |
    |                  |     Else:                         |           |
    |                  |           Start TP                | WAIT_RIB  |
    +------------------+-----------------------------------+-----------+
    |     HelloAck     |     Abort Exchange                | WAIT_DICT |
    +==================================================================+

Top      Up      ToC       Page 89 
    State: WAIT_RIB

    +==================================================================+
    |     Condition    |               Action              | New State |
    +==================+===================================+===========+
    |     On Entry     |   Clear Supplied RIBS             | WAIT_RIB  |
    +------------------+-----------------------------------+-----------+
    |       RIBDi      |   Update Dictionary (note 1)      |           |
    |                  |   If Dictionary Conflict found:   |           |
    |                  |         Abort Exchange            |(finished) |
    |                  |   Else:                           |           |
    |                  |         Start TP                  | WAIT_RIB  |
    +------------------+-----------------------------------+-----------+
    |    RIBnotlast    |   Record RIBS Supplied (note 2)   |           |
    |                  |   If EID missing in dictionary:   |           |
    |                  |         Abort Exchange            |(finished) |
    |                  |   Else:                           |           |
    |                  |         Start TP                  | WAIT_RIB  |
    +------------------+-----------------------------------+-----------
    |     RIBlast      |   Check Initiator Start Point     |           |
    |                  |   Record RIBS Supplied (note 2)   |           |
    |                  |   If EID missing in dictionary:   |           |
    |                  |         Abort Exchange            |(finished) |
    |                  |   Otherwise                       |           |
    |                  |         Recalc Dlvy               |           |
    |                  |               Predictabilities    |           |
    |                  |         Cancel TP                 |           |
    |                  |         Determine Offers          |           |
    |                  |         Determine ACKs            |           |
    |                  |         Determine Offer           |           |
    |                  |               Dict Updates        |           |
    |                  |         Send RIB Dictionary       |           |
    |                  |               Updates             |           |
    |                  |         Send Offers               |           |
    |                  |         Start TI                  |   OFFER   |
    +------------------+-----------------------------------+-----------+
    |     HelloAck     |     Abort Exchange                | WAIT_DICT |
    +------------------+-----------------------------------+-----------+
    |Any Other TLV rcvd|     Abort Exchange                |(finished) |
    +------------------+-----------------------------------+-----------+
    |  Timeout(peer)   |     Send RIB Dictionary Updates   |           |
    |                  |     Send Offers                   |           |
    |                  |     Start TI (note 3)             |   OFFER   |
    +==================================================================+

Top      Up      ToC       Page 90 
    State: OFFER

    +==================================================================+
    |     Condition    |               Action              | New State |
    +==================+===================================+===========+
    |    REQnotlast    |      Send Bundles                 |           |
    |                  |      Start TI                     |   OFFER   |
    +------------------+-----------------------------------+-----------+
    |     REQlast      |      Cancel TI                    |           |
    |                  |      Check Initiator Start Point  |           |
    |                  |      Send Bundles                 | SND_BUNDLE|
    +------------------+-----------------------------------+-----------+
    |     REQempty     |      Cancel TI                    |           |
    |                  |      Check Initiator Start Point  | WAIT_MORE|
    +------------------+-----------------------------------+-----------+
    |     HelloAck     |      Abort Exchange               | WAIT_DICT |
    +------------------+-----------------------------------+-----------+
    |  Timeout(info)   |      Send RIB Dictionary Updates  |           |
    |                  |      Send Offers                  |           |
    |                  |      Start TI (note 3)            |   OFFER   |
    +==================================================================+



    State: SND_BUNDLE

    +==================================================================+
    |     Condition    |               Action              | New State |
    +==================+===================================+===========+
    |    REQnotlast    |      Send Bundles                 |           |
    |                  |      Start TI                     | SND_BUNDLE|
    +------------------+-----------------------------------+-----------+
    |     REQlast      |      Cancel TI                    |           |
    |                  |      Send Bundles                 | SND_BUNDLE|
    +------------------+-----------------------------------+-----------+
    |     REQempty     |      Cancel TI                    |           |
    |                  |      Check Initiator Start Point  | WAIT_MORE|
    +------------------+-----------------------------------+-----------+
    |     HelloAck     |      Abort Exchange               | WAIT_DICT |
    +------------------+-----------------------------------+-----------+
    |  Timeout(info)   |      Send RIB Dictionary Updates  |           |
    |                  |      Send Offers                  |           |
    |                  |      Start TI (note 3)            |   OFFER   |
    +==================================================================+

Top      Up      ToC       Page 91 
    State: WAIT_MORE

    +==================================================================+
    |     Condition    |               Action              | New State |
    +==================+===================================+===========+
    | More Bundles     |         Determine Offers          |           |
    |                  |         Determine ACKs            |           |
    |                  |         Determine Offer           |           |
    |                  |               Dict Updates        |           |
    |                  |         Send RIB Dictionary       |           |
    |                  |               Updates             |           |
    |                  |         Send Offers               |           |
    |                  |         Start TI                  |   OFFER   |
    +------------------+-----------------------------------+-----------+
    |       RIBDi      |   Update Dictionary (note 1)      |           |
    |                  |   If Dictionary Conflict found:   |           |
    |                  |         Abort Exchange            |(finished) |
    |                  |   Else:                           |           |
    |                  |         Start TP                  | WAIT_RIB  |
    +------------------+-----------------------------------+-----------+
    |    REQnotlast    |      Send Bundles                 |           |
    |                  |      Start TI                     | SND_BUNDLE|
    +------------------+-----------------------------------+-----------+
    |     REQlast      |      Cancel TI                    |           |
    |                  |      Send Bundles                 | SND_BUNDLE|
    +------------------+-----------------------------------+-----------+
    |     REQempty     |      Cancel TI                    |           |
    |                  |      Check Initiator Start Point  | SND_BUNDLE|
    +------------------+-----------------------------------+-----------+
    |     HelloAck     |      Abort Exchange               | WAIT_DICT |
    +------------------+-----------------------------------+-----------+
    |  Timeout(info)   |      Send RIB Dictionary Updates  |           |
    |                  |      Send Offers                  |           |
    |                  |      Start TI (note 3)            |   OFFER   |
    +==================================================================+

   Note 1:
      Both the dictionary and the RIB TLVs may come in the same PRoPHET
      message.  In that case, the state will change to WAIT_RIB, and the
      RIB will then immediately be processed.

   Note 2:
      Send an ACK if the timer for the peering node expires.  Either the
      link has been broken, and then the link setup will restart, or it
      will trigger the Information Exchange Phase to restart.

Top      Up      ToC       Page 92 
   Note 3:
      When the RIB is received, it is possible for the PRoPHET agent to
      update its delivery predictabilities according to Section 2.1.2.
      The delivery predictabilities and the RIB is then used together
      with the forwarding strategy in use to create a bundle offer TLV.
      This is sent to the peering node.

   Note 4:
      No more bundles are requested by the other node; transfer is
      complete.

   Note 5:
      No response to the bundle offer has been received before the timer
      expired, so we re-send the bundle offer.

5.4.  Interaction with Nodes Using Version 1 of PRoPHET

   There are existing implementations of PRoPHET based on draft versions
   of this specification that use version 1 of the protocol.  There are
   a number of significant areas of difference between version 1 and
   version 2 as described in this document:

   o  In version 1, the delivery predictability update equations were
      significantly different, and in the case of the transitivity
      equation (Equation 3) could lead to degraded performance or non-
      delivery of bundles in some circumstances.

   o  In the current version , constraints were placed on the String IDs
      generated by each node to ensure that it was not possible for
      there to be a conflict if the IDs were generated concurrently and
      independently in the two nodes.

   o  In the current version, a flag has been added to the Routing
      Information Base Dictionary TLV to distinguish dictionary updates
      sent by the Initiator role and by the Listener role.

   o  In the current version, the Bundle Offer and Response TLVs have
      been significantly revised.  The version 2 TLVs have been
      allocated new TLV Type numbers, and the version 1 TLVs (types 0xA2
      and 0xA3) are now deprecated.  For each bundle specifier, the
      source EID is transmitted in addition to the creation timestamp by
      version 2 to ensure that the bundle is uniquely identified.
      Version 2 also transmits the fragment payload offset and length
      when the offered bundle is a bundle fragment.  The payload length
      can optionally be transmitted for each bundle (whether or not it
      is a fragment) to give the receiver additional information that
      can be useful when determining which bundle offers to accept.

Top      Up      ToC       Page 93 
   o  The behavior of the system after the first Information Exchange
      Phase has been better defined.  The state machine has been altered
      to better describe how the ongoing operations work.  This has
      involved the removal of the high-level state WAIT_INFO and the
      addition of two states in the Listener role subsidiary state
      machine (SND_BUNDLE and WAIT_MORE).  The protocol on the wire has
      not been altered by this change to the description of the state
      machine.  However, the specification of the later stages of
      operation was slightly vague and might have been interpreted
      differently by various implementers.

   A node implementing version 2 of the PRoPHET protocol as defined in
   this document MAY ignore a communication opportunity with a node that
   sends a HELLO message indicating that it uses version 1, or it MAY
   partially downgrade and respond to messages as if it were a version 1
   node.  This means that the version field in all message headers MUST
   contain 1.

   It is RECOMMENDED that the version 2 node use the metric update
   equations defined in this document even when communicating with a
   version 1 node as this will partially inhibit the problems with the
   transitivity equation in version 1, and that the version 2 node
   modify any received metrics that are greater than (1 - delta) to be
   (1 - delta) to avoid becoming a "sink" for bundles that are not
   destined for this node.  Also version 1 nodes cannot be explicitly
   offered bundle fragments, and an exchange with a node supporting
   version 1 MUST use the, now deprecated, previous versions of the
   Bundle Offer and Response TLVs.

   Generally, nodes using version 1 should be upgraded if at all
   possible because of problems that have been identified.



(page 93 continued on part 4)

Next RFC Part