tech-invite   World Map     

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

RFC 6940


REsource LOcation And Discovery (RELOAD) Base Protocol

Part 3 of 7, p. 42 to 66
Prev RFC Part       Next RFC Part


prevText      Top      Up      ToC       Page 42 
6.3.  Message Structure

   RELOAD is a message-oriented request/response protocol.  The messages
   are encoded using binary fields.  All integers are represented in
   network byte order.  The general philosophy behind the design was to
   use Type, Length, Value (TLV) fields to allow for extensibility.
   However, for the parts of a structure that were required in all
   messages, we just define these in a fixed position, as adding a type
   and length for them is unnecessary and would only increase bandwidth
   and introduce new potential interoperability issues.

   Each message has three parts, which are concatenated, as shown below:

     |    Forwarding Header    |
     |    Message Contents     |
     |     Security Block      |

Top      Up      ToC       Page 43 
   The contents of these parts are as follows:

   Forwarding Header:  Each message has a generic header which is used
      to forward the message between peers and to its final destination.
      This header is the only information that an intermediate peer
      (i.e., one that is not the target of a message) needs to examine.
      Section 6.3.2 describes the format of this part.

   Message Contents:  The message being delivered between the peers.
      From the perspective of the forwarding layer, the contents are
      opaque; however, they are interpreted by the higher layers.
      Section 6.3.3 describes the format of this part.

   Security Block:  A security block containing certificates and a
      digital signature over the "Message Contents" section.  Note that
      this signature can be computed without parsing the message
      contents.  All messages MUST be signed by their originator.
      Section 6.3.4 describes the format of this part.

6.3.1.  Presentation Language

   The structures defined in this document are defined using a C-like
   syntax based on the presentation language used to define TLS
   [RFC5246].  Advantages of this style include:

   o  It is familiar enough that most readers can grasp it quickly.

   o  The ability to define nested structures allows a separation
      between high-level and low-level message structures.

   o  It has a straightforward wire encoding that allows quick
      implementation, but the structures can be comprehended without
      knowing the encoding.

   o  It is possible to mechanically compile encoders and decoders.

   Several idiosyncrasies of this language are worth noting:

   o  All lengths are denoted in bytes, not objects.

   o  Variable-length values are denoted like arrays, with angle

   o  "select" is used to indicate variant structures.

   For instance, "uint16 array<0..2^8-2>;" represents up to 254 bytes,
   which corresponds to up to 127 values of two bytes (16 bits) each.

Top      Up      ToC       Page 44 
   A repetitive structure member shares a common notation with a member
   containing a variable-length block of data.  The latter always starts
   with "opaque", whereas the former does not.  For instance, the
   following denotes a variable block of data:

                     opaque data<0..2^32-1>;

   whereas the following denotes a list of 0, 1, or more instances of
   the Name element:

                     Name names<0..2^32-1>;  Common Definitions

   This section provides an introduction to the presentation language
   used throughout RELOAD.

   An enum represents an enumerated type.  The values associated with
   each possibility are represented in parentheses, and the maximum
   value is represented as a nameless value, for purposes of describing
   the width of the containing integral type.  For instance, Boolean
   represents a true or false:

         enum { false(0), true(1), (255) } Boolean;

   A boolean value is either a 1 or a 0.  The max value of 255 indicates
   that this is represented as a single byte on the wire.

   The NodeId, shown below, represents a single Node-ID.

             typedef opaque       NodeId[NodeIdLength];

   A NodeId is a fixed-length structure represented as a series of
   bytes, with the most significant byte first.  The length is set on a
   per-overlay basis within the range of 16-20 bytes (128 to 160 bits).
   (See Section 11.1 for how NodeIdLength is set.)  Note that the use of
   "typedef" here is an extension to the TLS language, but its meaning
   should be relatively obvious.  Also note that the [ size ] syntax
   defines a fixed-length element that does not include the length of
   the element in the on-the-wire encoding.

   A ResourceId, shown below, represents a single Resource-ID.

             typedef opaque       ResourceId<0..2^8-1>;

   Like a NodeId, a ResourceId is an opaque string of bytes, but unlike
   NodeIds, ResourceIds are variable length, up to 254 bytes (2040 bits)
   in length.  On the wire, each ResourceId is preceded by a single

Top      Up      ToC       Page 45 
   length byte (allowing lengths up to 255 bytes).  Thus, the 3-byte
   value "FOO" would be encoded as: 03 46 4f 4f.  Note the < range >
   syntax defines a variable length element that includes the length of
   the element in the on-the-wire encoding.  The number of bytes to
   encode the length on the wire is derived by range; i.e., it is the
   minimum number of bytes which can encode the largest range value.

   A more complicated example is IpAddressPort, which represents a
   network address and can be used to carry either an IPv6 or IPv4

        enum { invalidAddressType(0), ipv4_address(1), ipv6_address(2),
             (255) } AddressType;

        struct {
          uint32                  addr;
          uint16                  port;
        } IPv4AddrPort;

        struct {
          uint128                 addr;
          uint16                  port;
        } IPv6AddrPort;

        struct {
          AddressType             type;
          uint8                   length;

          select (type) {
            case ipv4_address:
               IPv4AddrPort       v4addr_port;

            case ipv6_address:
               IPv6AddrPort       v6addr_port;

            /* This structure can be extended */
        } IpAddressPort;

   The first two fields in the structure are the same no matter what
   kind of address is being represented:

   type:  The type of address (IPv4 or IPv6).

   length:  The length of the rest of the structure.

Top      Up      ToC       Page 46 
   By having the type and the length appear at the beginning of the
   structure regardless of the kind of address being represented, an
   implementation which does not understand new address type X can still
   parse the IpAddressPort field and then discard it if it is not

   The rest of the IpAddressPort structure is either an IPv4AddrPort or
   an IPv6AddrPort.  Both of these simply consist of an address
   represented as an integer and a 16-bit port.  As an example, here is
   the wire representation of the IPv4 address "" with port

             01           ; type    = IPv4
             06           ; length  = 6
             c0 00 02 01  ; address =
             17 c4        ; port    = 6084

   Unless a given structure that uses a select explicitly allows for
   unknown types in the select, any unknown type SHOULD be treated as a
   parsing error, and the whole message SHOULD be discarded with no

6.3.2.  Forwarding Header

   The forwarding header is defined as a ForwardingHeader structure, as
   shown below.

        struct {
          uint32             relo_token;
          uint32             overlay;
          uint16             configuration_sequence;
          uint8              version;
          uint8              ttl;
          uint32             fragment;
          uint32             length;
          uint64             transaction_id;
          uint32             max_response_length;
          uint16             via_list_length;
          uint16             destination_list_length;
          uint16             options_length;
          Destination        via_list[via_list_length];
          Destination        destination_list
          ForwardingOption   options[options_length];
        } ForwardingHeader;

Top      Up      ToC       Page 47 
   The contents of the structure are:

   relo_token:  The first four bytes identify this message as a RELOAD
      message.  This field MUST contain the value 0xd2454c4f (the string
      "RELO" with the high bit of the first byte set).

   overlay:  The 32-bit checksum/hash of the overlay being used.  This
      MUST be formed by taking the lower 32 bits of the SHA-1 [RFC3174]
      hash of the overlay name.  The purpose of this field is to allow
      nodes to participate in multiple overlays and to detect accidental
      misconfiguration.  This is not a security-critical function.  The
      overlay name MUST consist of a sequence of characters that would
      be allowable as a DNS name.  Specifically, as it is used in a DNS
      lookup, it will need to be compliant with the grammar for the
      domain as specified in Section 2.3.1 of [RFC1035].

   configuration_sequence:  The sequence number of the configuration
      file.  See Section for details.

   version:  The version of the RELOAD protocol being used times 10.
      RELOAD version numbers are fixed-point decimal numbers between
      fixed-point integer between 0.1 and 25.4.  This document describes
      version 1.0, with a value of 0x0a.  (Note that versions used prior
      to the publication of this RFC used version number 0.1.)  Nodes
      MUST reject messages with other versions.

   ttl:  An 8-bit field indicating the number of iterations, or hops, a
      message can experience before it is discarded.  The TTL (time-to-
      live) value MUST be decremented by one at every hop along the
      route the message traverses just before transmission.  If a
      received message has a TTL of 0 and the message is not destined
      for the receiving node, then the message MUST NOT be propagated
      further, and an Error_TTL_Exceeded error should be generated.  The
      initial value of the TTL SHOULD be 100 and MUST NOT exceed 100
      unless defined otherwise by the overlay configuration.
      Implementations which receive messages with a TTL greater than the
      current value of initial-ttl (or the default of 100) MUST discard
      the message and send an Error_TTL_Exceeded error.

   fragment:  This field is used to handle fragmentation.  The high bit
      (0x80000000) MUST be set for historical reasons.  If the next bit
      (0x40000000) is set to 1, it indicates that this is the last (or
      only) fragment.  The next six bits (0x20000000 through 0x01000000)
      are reserved and SHOULD be set to zero.  The remainder of the
      field is used to indicate the fragment offset; see Section 6.7 for

Top      Up      ToC       Page 48 
   length:  The count in bytes of the size of the message, including the
      header, after the eventual fragmentation.

   transaction_id:  A unique 64-bit number that identifies this
      transaction and also allows receivers to disambiguate transactions
      which are otherwise identical.  In order to provide a high
      probability that transaction IDs are unique, they MUST be randomly
      generated.  Responses use the same transaction ID as the request
      to which they correspond.  Transaction IDs are also used for
      fragment reassembly.  See Section 6.7 for details.

   max_response_length:  The maximum size in bytes of a response.  This
      is used by requesting nodes to avoid receiving (unexpected) very
      large responses.  If this value is non-zero, responding peers MUST
      check that any response would not exceed it and if so generate an
      Error_Incompatible_with_Overlay value.  This value SHOULD be set
      to zero for responses.

   via_list_length:  The length of the Via List in bytes.  Note that in
      this field and the following two length fields, we depart from the
      usual variable-length convention of having the length immediately
      precede the value, in order to make it easier for hardware
      decoding engines to quickly determine the length of the header.

   destination_list_length:  The length of the Destination List in

   options_length:  The length of the header options in bytes.

   via_list:  The via_list contains the sequence of destinations through
      which the message has passed.  The via_list starts out empty and
      grows as the message traverses each peer.  In stateless cases, the
      previous hop that the message is from is appended to the Via List
      as specified in Section 6.1.2.

   destination_list:  The destination_list contains a sequence of
      destinations through which the message should pass.  The
      Destination List is constructed by the message originator.  The
      first element on the Destination List is where the message goes
      next.  Generally, the list shrinks as the message traverses each
      listed peer, though if list compression is used, this may not be

   options:  Contains a series of ForwardingOption entries.  See

Top      Up      ToC       Page 49  Processing Configuration Sequence Numbers

   In order to be part of the overlay, a node MUST have a copy of the
   overlay Configuration Document.  In order to allow for configuration
   document changes, each version of the Configuration Document MUST
   contain a sequence number which MUST be monotonically increasing mod
   65535.  Because the sequence number may, in principle, wrap, greater
   than or less than are interpreted by modulo arithmetic as in TCP.

   When a destination node receives a request, it MUST check that the
   configuration_sequence field is equal to its own configuration
   sequence number.  If they do not match, the node MUST generate an
   error, either Error_Config_Too_Old or Error_Config_Too_New.  In
   addition, if the configuration file in the request is too old, the
   node MUST generate a ConfigUpdate message to update the requesting
   node.  This allows new Configuration Documents to propagate quickly
   throughout the system.  The one exception to this rule is that if the
   configuration_sequence field is equal to 65535 and the message type
   is ConfigUpdate, then the message MUST be accepted regardless of the
   receiving node's configuration sequence number.  Since 65535 is a
   special value, peers sending a new configuration when the
   configuration sequence is currently 65534 MUST set the configuration
   sequence number to 0 when they send a new configuration.

Top      Up      ToC       Page 50  Destination and Via Lists

   The Destination List and Via List are sequences of Destination

     enum { invalidDestinationType(0), node(1), resource(2),
            opaque_id_type(3), /* 128-255 not allowed */ (255) }

     select (destination_type) {
      case node:
             NodeId               node_id;

      case resource:
             ResourceId           resource_id;

      case opaque_id_type:
             opaque               opaque_id<0..2^8-1>;

          /* This structure may be extended with new types */
     } DestinationData;

     struct {
        DestinationType         type;
        uint8                   length;
        DestinationData         destination_data;
     } Destination;

     struct {
        uint16               opaque_id; /* Top bit MUST be 1 */
     } Destination;

   If the destination structure is a 16-bit integer, then the first bit
   MUST be set to 1, and it MUST be treated as if it were a full
   structure with a DestinationType of opaque_id_type and an opaque_id
   that was 2 bytes long with the value of the 16-bit integer.  If the
   destination structure starts with DestinationType, then the first bit
   MUST be set to 0, and the destination structure must use a TLV
   structure with the following contents:

      The type of the DestinationData Payload Data Unit (PDU).  It may
      be one of "node", "resource", or "opaque_id_type".

      The length of the destination_data.

Top      Up      ToC       Page 51 
      The destination value itself, which is an encoded DestinationData
      structure that depends on the value of "type".

   Note that the destination structure encodes a Type, Length, Value.
   The Length field specifies the length of the DestinationData values,
   which allows the addition of new DestinationTypes.  It also allows an
   implementation which does not understand a given DestinationType to
   skip over it.

   A DestinationData can be one of three types:

      A Node-ID.

      A compressed list of Node-IDs and an eventual Resource-ID.
      Because this value has been compressed by one of the peers, it is
      meaningful only to that peer and cannot be decoded by other peers.
      Thus, it is represented as an opaque string.

      The Resource-ID of the resource which is desired.  This type MUST
      appear only in the final location of a Destination List and MUST
      NOT appear in a Via List.  It is meaningless to try to route
      through a resource.

   One possible encoding of the 16-bit integer version as an opaque
   identifier is to encode an index into a Connection Table.  To avoid
   misrouting responses in the event a response is delayed and the
   Connection Table entry has changed, the identifier SHOULD be split
   between an index and a generation counter for that index.  When a
   Node first joins the overlay, the generation counters SHOULD be
   initialized to random values.  An implementation MAY use 12 bits for
   the Connection Table index and 3 bits for the generation counter.
   (Note that this does not suggest a 4096-entry Connection Table for
   every peer, only the ability to encode for a larger Connection
   Table.)  When a Connection Table slot is used for a new connection,
   the generation counter is incremented (with wrapping).  Connection
   Table slots are used on a rotating basis to maximize the time
   interval between uses of the same slot for different connections.
   When routing a message to an entry in the Destination List encoding a
   Connection Table entry, the peer MUST confirm that the generation
   counter matches the current generation counter of that index before
   forwarding the message.  If it does not match, the message MUST be
   silently dropped.

Top      Up      ToC       Page 52  Forwarding Option

   The Forwarding header can be extended with forwarding header options,
   which are a series of ForwardingOption structures:

    enum { invalidForwardingOptionType(0), (255) }

    struct {
      ForwardingOptionType      type;
      uint8                     flags;
      uint16                    length;
      select (type) {
            /* This type may be extended */
    } ForwardingOption;

   Each ForwardingOption consists of the following values:

      The type of the option.  This structure allows for unknown options

      Three flags are defined: FORWARD_CRITICAL(0x01),
      DESTINATION_CRITICAL(0x02), and RESPONSE_COPY(0x04).  These flags
      MUST NOT be set in a response.  If the FORWARD_CRITICAL flag is
      set, any peer that would forward the message but does not
      understand this option MUST reject the request with an
      Error_Unsupported_Forwarding_Option error response.  If the
      DESTINATION_CRITICAL flag is set, any node that generates a
      response to the message but does not understand the forwarding
      option MUST reject the request with an
      Error_Unsupported_Forwarding_Option error response.  If the
      RESPONSE_COPY flag is set, any node generating a response MUST
      copy the option from the request to the response except that the
      MUST be cleared.

      The length of the rest of the structure.  Note that a 0 length may
      be reasonable if the mere presence of the option is meaningful and
      no value is required.

      The option value.

Top      Up      ToC       Page 53 
6.3.3.  Message Contents Format

   The second major part of a RELOAD message is the contents part, which
   is defined by MessageContents:

   enum { invalidMessageExtensionType(0),
          (2^16-1) } MessageExtensionType;

   struct {
     MessageExtensionType  type;
     Boolean               critical;
     opaque                extension_contents<0..2^32-1>;
   } MessageExtension;

   struct {
     uint16                 message_code;
     opaque                 message_body<0..2^32-1>;
     MessageExtension       extensions<0..2^32-1>;
   } MessageContents;

   The contents of this structure are as follows:

      This indicates the message that is being sent.  The code space is
      broken up as follows:

      0x0  Invalid Message Code.  This code will never be assigned.

      0x1 .. 0x7FFF  Requests and responses.  These code points are
         always paired, with requests being an odd value and the
         corresponding response being the request code plus 1.  Thus,
         "probe_request" (the Probe request) has the value 1 and
         "probe_answer" (the Probe response) has the value 2

      0x8000 .. 0xFFFE  Reserved

      0xFFFF  Error

      The message codes are defined in Section 14.8.

      The message body itself, represented as a variable-length string
      of bytes.  The bytes themselves are dependent on the code value.
      See the sections describing the various RELOAD methods (Join,
      Update, Attach, Store, Fetch, etc.) for the definitions of the
      payload contents.

Top      Up      ToC       Page 54 
      Extensions to the message.  Currently no extensions are defined,
      but new extensions can be defined by the process described in
      Section 14.14.

   All extensions have the following form:

      The extension type.

      Whether this extension needs to be understood in order to process
      the message.  If critical = True and the recipient does not
      understand the message, it MUST generate an
      Error_Unknown_Extension error.  If critical = False, the recipient
      MAY choose to process the message even if it does not understand
      the extension.

      The contents of the extension (which are extension dependent).

   The subsections 6.4.2, 6.5, and 7 describe structures that are
   inserted inside the message_body member, depending on the value of
   the message_code value.  For example, a message_code value of
   join_req means that the structure named JoinReq is inserted inside
   message_body.  This document does not contain a mapping between
   message_code values and structure names, as the conversion between
   the two is obvious.

   Similarly, this document uses the name of the structure without the
   "Req" or "Ans" suffix to mean the execution of a transaction
   consisting of the matching request and answer.  For example, when the
   text says "perform an Attach", it must be understood as performing a
   transaction composed of an AttachReq and an AttachAns.  Response Codes and Response Errors

   A node processing a request MUST return its status in the
   message_code field.  If the request was a success, then the message
   code MUST be set to the response code that matches the request (i.e.,
   the next code up).  The response payload is then as defined in the
   request/response descriptions.

   If the request has failed, then the message code MUST be set to
   0xffff (error) and the payload MUST be an error_response message, as
   shown below.

Top      Up      ToC       Page 55 
   When the message code is 0xFFFF, the payload MUST be an

         public struct {
           uint16             error_code;
           opaque             error_info<0..2^16-1>;
         } ErrorResponse;

   The contents of this structure are as follows:

      A numeric error code indicating the error that occurred.

      An optional arbitrary byte string.  Unless otherwise specified,
      this will be a UTF-8 text string that provides further information
      about what went wrong.  Developers are encouraged to include
      enough diagnostic information to be useful in error_info.  The
      specific text to be used and any relevant language or encoding
      thereof is left to the implementation.

   The following error code values are defined.  The numeric values for
   these are defined in Section 14.9.

      The requesting node does not have permission to make this request.

      The resource or node cannot be found or does not exist.

      A response to the request has not been received in a suitable
      amount of time.  The requesting node MAY resend the request at a
      later time.

      A store cannot be completed because the storage_time precedes the
      existing value.

      A store cannot be completed because the requested object exceeds
      the size limits for that Kind.

      A store cannot be completed because the generation counter
      precedes the existing value.

Top      Up      ToC       Page 56 
      A peer receiving the request is using a different overlay, overlay
      algorithm, or hash algorithm, or some other parameter that is
      inconsistent with the overlay configuration.

      A node received the request with a forwarding options flagged as
      critical, but the node does not support this option.  See

      A peer received the request in which the TTL was decremented to
      zero.  See Section 6.3.2.

      A peer received a request that was too large.  See Section 6.6.

      A node would have generated a response that is too large per the
      max_response_length field.

      A destination node received a request with a configuration
      sequence that is too old.  See Section

      A destination node received a request with a configuration
      sequence that is too new.  See Section

      A destination peer received a request with an unknown Kind-ID.
      See Section

      An Attach to this peer is already in progress.  See

      A destination node received a request with an unknown extension.

      Something about this message is invalid, but it does not fit the
      other error codes.  When this message is sent, implementations
      SHOULD provide some meaningful description in error_info to aid in

Top      Up      ToC       Page 57 
      For the purposes of experimentation.  It is not meant for vendor-
      specific use of any sort and MUST NOT be used for operational

      For the purposes of experimentation.  It is not meant for vendor-
      specific use of any sort and MUST NOT be used for operational

6.3.4.  Security Block

   The third part of a RELOAD message is the security block.  The
   security block is represented by a SecurityBlock structure:

   struct {
      CertificateType     type;   // From RFC 6091
      opaque              certificate<0..2^16-1>;
   } GenericCertificate;

   struct {
      GenericCertificate certificates<0..2^16-1>;
      Signature          signature;
   } SecurityBlock;

   The contents of this structure are:

      A bucket of certificates.

      A signature.

   The certificates bucket SHOULD contain all the certificates necessary
   to verify every signature in both the message and the internal
   message objects, except for those certificates in a root-cert element
   of the current configuration file.  This is the only location in the
   message which contains certificates, thus allowing only a single copy
   of each certificate to be sent.  In systems that have an alternative
   certificate distribution mechanism, some certificates MAY be omitted.
   However, unless an alternative mechanism for immediately generating
   certificates, such as shared secret security (Section 13.4) is used,
   implementers MUST include all referenced certificates.

   NOTE TO IMPLEMENTERS: This requirement implies that a peer storing
   data is obligated to retain certificates for the data that it holds.

Top      Up      ToC       Page 58 
   Each certificate is represented by a GenericCertificate structure,
   which has the following contents:

      The type of the certificate, as defined in [RFC6091].  Only the
      use of X.509 certificates is defined in this document.

      The encoded version of the certificate.  For X.509 certificates,
      it is the Distinguished Encoding Rules (DER) form.

   The signature is computed over the payload and parts of the
   forwarding header.  In case of a Store, the payload MUST contain an
   additional signature computed as described in Section 7.1.  All
   signatures MUST be formatted using the Signature element.  This
   element is also used in other contexts where signatures are needed.
   The input structure to the signature computation MAY vary depending
   on the data element being signed.

     enum { invalidSignerIdentityType(0),
            cert_hash(1), cert_hash_node_id(2),
            (255) } SignerIdentityType;

     struct {
       select (identity_type) {

         case cert_hash;
           HashAlgorithm      hash_alg;              // From TLS
           opaque             certificate_hash<0..2^8-1>;

         case cert_hash_node_id:
           HashAlgorithm      hash_alg;              // From TLS
           opaque             certificate_node_id_hash<0..2^8-1>;

         case none:
           /* empty */
         /* This structure may be extended with new types if necessary*/
     } SignerIdentityValue;

     struct {
       SignerIdentityType     identity_type;
       uint16                 length;
       SignerIdentityValue    identity[SignerIdentity.length];
     } SignerIdentity;

Top      Up      ToC       Page 59 
     struct {
        SignatureAndHashAlgorithm     algorithm;   // From TLS
        SignerIdentity                identity;
        opaque                        signature_value<0..2^16-1>;
     } Signature;

   The Signature construct contains the following values:

      The signature algorithm in use.  The algorithm definitions are
      found in the IANA TLS SignatureAlgorithm and HashAlgorithm
      registries.  All implementations MUST support RSASSA-PKCS1-v1_5
      [RFC3447] signatures with SHA-256 hashes [RFC6234].

      The identity, as defined in the two paragraphs following this
      list, used to form the signature.

      The value of the signature.

      Note that storage operations allow for special values of algorithm
      and identity.  See the Store Request definition (Section
      and the Fetch Response definition (Section

   There are two permitted identity formats, one for a certificate with
   only one Node-ID and one for a certificate with multiple Node-IDs.
   In the first case, the cert_hash type MUST be used.  The hash_alg
   field is used to indicate the algorithm used to produce the hash.
   The certificate_hash contains the hash of the certificate object
   (i.e., the DER-encoded certificate).

   In the second case, the cert_hash_node_id type MUST be used.  The
   hash_alg is as in cert_hash, but the cert_hash_node_id is computed
   over the NodeId used to sign concatenated with the certificate; i.e.,
   H(NodeId || certificate).  The NodeId is represented without any
   framing or length fields, as simple raw bytes.  This is safe because
   NodeIds are a fixed length for a given overlay.

   For signatures over messages, the input to the signature is computed

      overlay || transaction_id || MessageContents || SignerIdentity

   where overlay and transaction_id come from the forwarding header and
   || indicates concatenation.

Top      Up      ToC       Page 60 
   The input to signatures over data values is different and is
   described in Section 7.1.

   All RELOAD messages MUST be signed.  Intermediate nodes do not verify
   signatures.  Upon receipt (and fragment reassembly, if needed), the
   destination node MUST verify the signature and the authorizing
   certificate.  If the signature fails, the implementation SHOULD
   simply drop the message and MUST NOT process it.  This check provides
   a minimal level of assurance that the sending node is a valid part of
   the overlay, and it provides cryptographic authentication of the
   sending node.  In addition, responses MUST be checked as follows by
   the requesting node:

   1.  The response to a message sent to a Node-ID MUST have been sent
       by that Node-ID unless the response has been sent to the wildcard

   2.  The response to a message sent to a Resource-ID MUST have been
       sent by a Node-ID which is at least as close to the target
       Resource-ID as any node in the requesting node's Neighbor Table.

   The second condition serves as a primitive check for responses from
   wildly wrong nodes but is not a complete check.  Note that in periods
   of churn, it is possible for the requesting node to obtain a closer
   neighbor while the request is outstanding.  This will cause the
   response to be rejected and the request to be retransmitted.

   In addition, some methods (especially Store) have additional
   authentication requirements, which are described in the sections
   covering those methods.

6.4.  Overlay Topology

   As discussed in previous sections, RELOAD defines a default overlay
   topology (CHORD-RELOAD) but allows for other topologies through the
   use of Topology Plug-ins.  This section describes the requirements
   for new Topology Plug-ins and the methods that RELOAD provides for
   overlay topology maintenance.

6.4.1.  Topology Plug-in Requirements

   When specifying a new overlay algorithm, at least the following MUST
   be described:

   o  Joining procedures, including the contents of the Join message.

Top      Up      ToC       Page 61 
   o  Stabilization procedures, including the contents of the Update
      message, the frequency of topology probes and keepalives, and the
      mechanism used to detect when peers have disconnected.

   o  Exit procedures, including the contents of the Leave message.

   o  The length of the Resource-IDs and for DHTs the hash algorithm to
      compute the hash of an identifier.

   o  The procedures that peers use to route messages.

   o  The replication strategy used to ensure data redundancy.

   All overlay algorithms MUST specify maintenance procedures that send
   Updates to clients and peers that have established connections to the
   peer responsible for a particular ID when the responsibility for that
   ID changes.  Because tracking this information is difficult, overlay
   algorithms MAY simply specify that an Update is sent to all members
   of the Connection Table whenever the range of IDs for which the peer
   is responsible changes.

6.4.2.  Methods and Types for Use by Topology Plug-ins

   This section describes the methods that Topology Plug-ins use to
   join, leave, and maintain the overlay.  Join

   A new peer (which already has credentials) uses the JoinReq message
   to join the overlay.  The JoinReq is sent to the responsible peer
   depending on the routing mechanism described in the Topology Plug-in.
   This message notifies the responsible peer that the new peer is
   taking over some of the overlay and that it needs to synchronize its

         struct {
            NodeId                joining_peer_id;
            opaque                overlay_specific_data<0..2^16-1>;
         } JoinReq;

   The minimal JoinReq contains only the Node-ID which the sending peer
   wishes to assume.  Overlay algorithms MAY specify other data to
   appear in this request.  Receivers of the JoinReq MUST verify that
   the joining_peer_id field matches the Node-ID used to sign the
   message and, if not, the message MUST be rejected with an
   Error_Forbidden error.

Top      Up      ToC       Page 62 
   Because joins may be executed only between nodes which are directly
   adjacent, receiving peers MUST verify that any JoinReq they receive
   arrives from a transport channel that is bound to the Node-ID to be
   assumed by the Joining Node.  Implementations MUST use DTLS
   anti-replay mechanisms, thus preventing replay attacks.

   If the request succeeds, the responding peer responds with a JoinAns
   message, as defined below:

         struct {
            opaque                overlay_specific_data<0..2^16-1>;
         } JoinAns;

   If the request succeeds, the responding peer MUST follow up by
   executing the right sequence of Stores and Updates to transfer the
   appropriate section of the overlay space to the Joining Node.  In
   addition, overlay algorithms MAY define data to appear in the
   response payload that provides additional information.

   Joining Nodes MUST verify that the signature on the JoinAns message
   matches the expected target (i.e., the adjacency over which they are
   joining).  If not, they MUST discard the message.

   In general, nodes which cannot form connections SHOULD report an
   error to the user.  However, implementations MUST provide some
   mechanism whereby nodes can determine that they are potentially the
   first node and can take responsibility for the overlay.  (The idea is
   to avoid having ordinary nodes try to become responsible for the
   entire overlay during a partition.)  This specification does not
   mandate any particular mechanism, but a configuration flag or setting
   seems appropriate.  Leave

   The LeaveReq message is used to indicate that a node is exiting the
   overlay.  A node SHOULD send this message to each peer with which it
   is directly connected prior to exiting the overlay.

         struct {
            NodeId                leaving_peer_id;
            opaque                overlay_specific_data<0..2^16-1>;
         } LeaveReq;

   LeaveReq contains only the Node-ID of the leaving peer.  Overlay
   algorithms MAY specify other data to appear in this request.
   Receivers of the LeaveReq MUST verify that the leaving_peer_id field
   matches the Node-ID used to sign the message and, if not, the message
   MUST be rejected with an Error_Forbidden error.

Top      Up      ToC       Page 63 
   Because leaves may be executed only between nodes which are directly
   adjacent, receiving peers MUST verify that any LeaveReq they receive
   arrives from a transport channel that is bound to the Node-ID to be
   assumed by the leaving peer.  This also prevents replay attacks,
   provided that DTLS anti-replay is used.

   Upon receiving a Leave request, a peer MUST update its own Routing
   Table and send the appropriate Store/Update sequences to re-stabilize
   the overlay.

   LeaveAns is an empty message.  Update

   Update is the primary overlay-specific maintenance message.  It is
   used by the sender to notify the recipient of the sender's view of
   the current state of the overlay (that is, its routing state), and it
   is up to the recipient to take whatever actions are appropriate to
   deal with the state change.  In general, peers send Update messages
   to all their adjacencies whenever they detect a topology shift.

   When a peer receives an Attach request with the send_update flag set
   to True (Section, it MUST send an Update message back to
   the sender of the Attach request after completion of the
   corresponding ICE check and TLS connection.  Note that the sender of
   such an Attach request may not have joined the overlay yet.

   When a peer detects through an Update that it is no longer
   responsible for any data value it is storing, it MUST attempt to
   Store a copy to the correct node unless it knows the newly
   responsible node already has a copy of the data.  This prevents data
   loss during large-scale topology shifts, such as the merging of
   partitioned overlays.

   The contents of the UpdateReq message are completely overlay
   specific.  The UpdateAns response is expected to be either success or
   an error.  RouteQuery

   The RouteQuery request allows the sender to ask a peer where they
   would route a message directed to a given destination.  In other
   words, a RouteQuery for a destination X requests the Node-ID for the
   node that the receiving peer would next route to in order to get to
   X.  A RouteQuery can also request that the receiving peer initiate an
   Update request to transfer the receiving peer's Routing Table.

Top      Up      ToC       Page 64 
   One important use of the RouteQuery request is to support iterative
   routing.  The sender selects one of the peers in its Routing
   Table and sends it a RouteQuery message with the destination field
   set to the Node-ID or Resource-ID to which it wishes to route.  The
   receiving peer responds with information about the peers to which the
   request would be routed.  The sending peer MAY then use the Attach
   method to attach to that peer(s) and repeat the RouteQuery.
   Eventually, the sender gets a response from a peer that is closest to
   the identifier in the destination field as determined by the Topology
   Plug-in.  At that point, the sender can send messages directly to
   that peer.  Request Definition

   A RouteQueryReq message indicates the peer or resource that the
   requesting node is interested in.  It also contains a "send_update"
   option that allows the requesting node to request a full copy of the
   other peer's Routing Table.

         struct {
           Boolean                send_update;
           Destination            destination;
           opaque                 overlay_specific_data<0..2^16-1>;
         } RouteQueryReq;

   The contents of the RouteQueryReq message are as follows:

      A single byte.  This may be set to True to indicate that the
      requester wishes the responder to initiate an Update request
      immediately.  Otherwise, this value MUST be set to False.

      The destination which the requester is interested in.  This may be
      any valid destination object, including a Node-ID, opaque ID, or
      Note: If implementations are using opaque IDs for privacy
      purposes, answering RouteQueryReqs for opaque IDs will allow the
      requester to translate an opaque ID.  Implementations MAY wish to
      consider limiting the use of RouteQuery for opaque IDs in such

      Other data as appropriate for the overlay.

Top      Up      ToC       Page 65  Response Definition

   A response to a successful RouteQueryReq request is a RouteQueryAns
   message.  This message is completely overlay specific.  Probe

   Probe provides primitive "exploration" services: it allows a node to
   determine which resources another node is responsible for.  A probe
   can be addressed to a specific Node-ID or to the peer controlling a
   given location (by using a Resource-ID).  In either case, the target
   node responds with a simple response containing some status
   information.  Request Definition

   The ProbeReq message contains a list (potentially empty) of the
   pieces of status information that the requester would like the
   responder to provide.

        enum { invalidProbeInformationType(0), responsible_set(1),
               num_resources(2), uptime(3), (255) }

        struct {
          ProbeInformationType     requested_info<0..2^8-1>;
        } ProbeReq;

   The currently defined values for ProbeInformationType are:

      Indicates that the peer should Respond with the fraction of the
      overlay for which the responding peer is responsible.

      Indicates that the peer should Respond with the number of
      resources currently being stored by the peer.  Note that multiple
      values under the same Resource-ID are counted only once.

      Indicates that the peer should Respond with how long the peer has
      been up, in seconds.

Top      Up      ToC       Page 66  Response Definition

   A successful ProbeAns response contains the information elements
   requested by the peer.

         struct {
           select (type) {
             case responsible_set:
               uint32             responsible_ppb;

             case num_resources:
               uint32             num_resources;

             case uptime:
               uint32             uptime;

             /* This type may be extended */
         } ProbeInformationData;

         struct {
           ProbeInformationType    type;
           uint8                   length;
           ProbeInformationData    value;
         } ProbeInformation;

         struct {
           ProbeInformation        probe_info<0..2^16-1>;
         } ProbeAns;

   A ProbeAns message contains a sequence of ProbeInformation
   structures.  Each has a "length" indicating the length of the
   following value field.  This structure allows for unknown option

   Each of the current possible Probe information types is a 32-bit
   unsigned integer.  For type "responsible_ppb", it is the fraction of
   the overlay for which the peer is responsible, in parts per billion.
   For type "num_resources", it is the number of resources the peer is
   storing.  For the type "uptime", it is the number of seconds the peer
   has been up.

   The responding peer SHOULD include any values that the requesting
   node requested and that it recognizes.  They SHOULD be returned in
   the requested order.  Any other values MUST NOT be returned.

Next RFC Part