doc: Add RFC documents

1 files changed, 955 insertions, 0 deletions

diff --git a/doc/rfc/rfc6256.txt b/doc/rfc/rfc6256.txt
new file mode 100644
index 0000000..9f89164
--- /dev/null
+++ b/doc/rfc/rfc6256.txt
@@ -0,0 +1,955 @@
+
+
+
+
+
+
+Internet Research Task Force (IRTF)                              W. Eddy
+Request for Comments: 6256                                   MTI Systems
+Category: Informational                                        E. Davies
+ISSN: 2070-1721                                         Folly Consulting
+                                                                May 2011
+
+
+           Using Self-Delimiting Numeric Values in Protocols
+
+Abstract
+
+   Self-Delimiting Numeric Values (SDNVs) have recently been introduced
+   as a field type in proposed Delay-Tolerant Networking protocols.
+   SDNVs encode an arbitrary-length non-negative integer or arbitrary-
+   length bitstring with minimum overhead.  They are intended to provide
+   protocol flexibility without sacrificing economy and to assist in
+   future-proofing protocols under development.  This document describes
+   formats and algorithms for SDNV encoding and decoding, along with
+   notes on implementation and usage.  This document is a product of the
+   Delay-Tolerant Networking Research Group and has been reviewed by
+   that group.  No objections to its publication as an RFC were raised.
+
+Status of This Memo
+
+   This document is not an Internet Standards Track specification; it is
+   published for informational purposes.
+
+   This document is a product of the Internet Research Task Force
+   (IRTF).  The IRTF publishes the results of Internet-related research
+   and development activities.  These results might not be suitable for
+   deployment.  This RFC represents the consensus of the Delay-Tolerant
+   Networking Research Group of the Internet Research Task Force (IRTF).
+   Documents approved for publication by the IRSG are not a candidate
+   for any level of Internet Standard; see Section 2 of RFC 5741.
+
+   Information about the current status of this document, any errata,
+   and how to provide feedback on it may be obtained at
+   http://www.rfc-editor.org/info/rfc6256.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Eddy & Davies                 Informational                     [Page 1]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+Copyright Notice
+
+   Copyright (c) 2011 IETF Trust and the persons identified as the
+   document authors.  All rights reserved.
+
+   This document is subject to BCP 78 and the IETF Trust's Legal
+   Provisions Relating to IETF Documents
+   (http://trustee.ietf.org/license-info) in effect on the date of
+   publication of this document.  Please review these documents
+   carefully, as they describe your rights and restrictions with respect
+   to this document.
+
+Table of Contents
+
+   1. Introduction ....................................................2
+      1.1. Problems with Fixed-Value Fields ...........................3
+      1.2. SDNVs for DTN Protocols ....................................4
+      1.3. SDNV Usage .................................................5
+   2. Definition of SDNVs .............................................6
+   3. Basic Algorithms ................................................8
+      3.1. Encoding Algorithm .........................................8
+      3.2. Decoding Algorithm .........................................9
+      3.3. Limitations of Implementations ............................10
+   4. Comparison to Alternatives .....................................10
+   5. Security Considerations ........................................13
+   6. Acknowledgements ...............................................13
+   7. Informative References .........................................14
+   Appendix A. SDNV Python Source Code ...............................15
+
+1.  Introduction
+
+   This document is a product of the Internet Research Task Force (IRTF)
+   Delay-Tolerant Networking (DTN) Research Group (DTNRG).  The document
+   has received review and support within the DTNRG, as discussed in the
+   Acknowledgements section of this document.
+
+   This document begins by describing the drawbacks of using fixed-width
+   protocol fields.  It then provides some background on the Self-
+   Delimiting Numeric Values (SDNVs) proposed for use in DTN protocols,
+   and motivates their potential applicability in other networking
+   protocols.  The DTNRG has created SDNVs to meet the challenges it
+   attempts to solve, and it has been noted that SDNVs closely resemble
+   certain constructs within ASN.1 and even older ITU protocols, so the
+   problems are not new or unique to DTN.  SDNVs focus strictly on
+   numeric values or bitstrings, while other mechanisms have been
+   developed for encoding more complex data structures, such as ASN.1
+
+
+
+
+
+Eddy & Davies                 Informational                     [Page 2]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+   encoding rules and Haverty's Message Services Data Transmission
+   Protocol (MSDTP) [RFC0713].  Because of this focus, SDNVs can be
+   quickly implemented with only a small amount of code.
+
+   SDNVs are tersely defined in both the Bundle Protocol [RFC5050] and
+   Licklider Transmission Protocol (LTP) [RFC5326] specifications, due
+   to the flow of document production in the DTNRG.  This document
+   clarifies and further explains the motivations and engineering
+   decisions behind SDNVs.
+
+1.1.  Problems with Fixed-Value Fields
+
+   Protocol designers commonly face an optimization problem in
+   determining the proper size for header fields.  There is a strong
+   desire to keep fields as small as possible, in order to reduce the
+   protocol's overhead and also allow for fast processing.  Since
+   protocols can be used for many years (even decades) after they are
+   designed, and networking technology has tended to change rapidly, it
+   is not uncommon for the use, deployment, or performance of a
+   particular protocol to be limited or infringed upon by the length of
+   some header field being too short.  Two well-known examples of this
+   phenomenon are the TCP-advertised receive window and the IPv4 address
+   length.
+
+   TCP segments contain an advertised receive window field that is fixed
+   at 16 bits [RFC0793], encoding a maximum value of around 65
+   kilobytes.  The purpose of this value is to provide flow control, by
+   allowing a receiver to specify how many sent bytes its peer can have
+   outstanding (unacknowledged) at any time, thus allowing the receiver
+   to limit its buffer size.  As network speeds have grown by several
+   orders of magnitude since TCP's inception, the combination of the 65
+   kilobyte maximum advertised window and long round-trip times
+   prevented TCP senders from being able to achieve the high throughput
+   that the underlying network supported.  This limitation was remedied
+   through the use of the Window Scale option [RFC1323], which provides
+   a multiplier for the advertised window field.  However, the Window
+   Scale multiplier is fixed for the duration of the connection,
+   requires support from each end of a TCP connection, and limits the
+   precision of the advertised receive window, so this is certainly a
+   less-than-ideal solution.  Because of the field width limit in the
+   original design however, the Window Scale is necessary for TCP to
+   reach high sending rates.
+
+   An IPv4 address is fixed at 32 bits [RFC0791] (as a historical note,
+   an early version of the IP header format specification in [IEN21]
+   used variable-length addresses in multiples of 8 bits up to 120
+   bits).  Due to the way that subnetting and assignment of address
+   blocks was performed, the number of IPv4 addresses has been seen as a
+
+
+
+Eddy & Davies                 Informational                     [Page 3]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+   limit to the growth of the Internet [Hain05].  Two divergent paths to
+   solve this problem have been the use of Network Address Translators
+   (NATs) and the development of IPv6.  NATs have caused a number of
+   other issues and problems [RFC2993], leading to increased complexity
+   and fragility, as well as forcing workarounds to be engineered for
+   many other protocols to function within a NATed environment.  The
+   IPv6 solution's transitional work has been underway for several
+   years, but has still only just begun to have visible impact on the
+   global Internet.
+
+   Of course, in both the case of the TCP receive window and IPv4
+   address length, the field size chosen by the designers seemed like a
+   good idea at the time.  The fields were more than big enough for the
+   originally perceived usage of the protocols, and yet were small
+   enough to allow the headers to remain compact and relatively easy and
+   efficient to parse on machines of the time.  The fixed sizes that
+   were defined represented a trade-off between the scalability of the
+   protocol versus the overhead and efficiency of processing.  In both
+   cases, these engineering decisions turned out to be painfully
+   restrictive in the longer term.
+
+1.2.  SDNVs for DTN Protocols
+
+   In specifications for the DTN Bundle Protocol (BP) [RFC5050] and
+   Licklider Transmission Protocol (LTP) [RFC5326], SDNVs have been used
+   for several fields including identifiers, payload/header lengths, and
+   serial (sequence) numbers.  SDNVs were developed for use in these
+   types of fields, to avoid sending more bytes than needed, as well as
+   avoiding fixed sizes that may not end up being appropriate.  For
+   example, since LTP is intended primarily for use in long-delay
+   interplanetary communications [RFC5325], where links may be fairly
+   low in capacity, it is desirable to avoid the header overhead of
+   routinely sending a 64-bit field where a 16-bit field would suffice.
+   Since many of the nodes implementing LTP are expected to be beyond
+   the current range of human spaceflight, upgrading their on-board LTP
+   implementations to use longer values if the defined fields are found
+   to be too short would also be problematic.  Furthermore, extensions
+   similar in mechanism to TCP's Window Scale option are unsuitable for
+   use in DTN protocols since, due to high delays, DTN protocols must
+   avoid handshaking and configuration parameter negotiation to the
+   greatest extent possible.  All of these reasons make the choice of
+   SDNVs for use in DTN protocols attractive.
+
+
+
+
+
+
+
+
+
+Eddy & Davies                 Informational                     [Page 4]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+1.3.  SDNV Usage
+
+   In short, an SDNV is simply a way of representing non-negative
+   integers (both positive integers of arbitrary magnitude and 0),
+   without expending much unnecessary space.  This definition allows
+   SDNVs to represent many common protocol header fields, such as:
+
+   o  Random identification fields as used in the IPsec Security
+      Parameters Index or in IP headers for fragment reassembly (Note:
+      the 16-bit IP ID field for fragment reassembly was recently found
+      to be too short in some environments [RFC4963]).
+
+   o  Sequence numbers as in TCP or the Stream Control Transmission
+      Protocol (SCTP).
+
+   o  Values used in cryptographic algorithms such as RSA keys, Diffie-
+      Hellman key agreement, or coordinates of points on elliptic
+      curves.
+
+   o  Message lengths as used in file transfer protocols.
+
+   o  Nonces and cookies.
+
+   As any bitfield can be interpreted as an unsigned integer, SDNVs can
+   also encode arbitrary-length bitfields, including bitfields
+   representing signed integers or other data types; however, this
+   document assumes SDNV encoding and decoding in terms of unsigned
+   integers.  Implementations may differ in the interface that they
+   provide to SDNV encoding and decoding functions, in terms of whether
+   the values are numeric, bitfields, etc.; this detail does not alter
+   the representation or algorithms described in this document.
+
+   The use of SDNVs rather than fixed-length fields gives protocol
+   designers the ability to ameliorate the consequences of making
+   difficult-to-reverse field-sizing decisions, as the SDNV format grows
+   and shrinks depending on the particular value encoded.  SDNVs do not
+   necessarily provide optimal encodings for values of any particular
+   length; however, they allow protocol designers to avoid potential
+   blunders in assigning fixed lengths and remove the complexity
+   involved with either negotiating field lengths or constructing
+   protocol extensions.  However, if SDNVs are used to encode bitfields,
+   it is essential that the sender and receiver have a consistent
+   interpretation of the decoded value.  This is discussed further in
+   Section 2.
+
+   To our knowledge, at this time, no IETF transport or network-layer
+   protocol designed for use outside of the DTN domain has proposed to
+   use SDNVs; however, there is no inherent reason not to use SDNVs more
+
+
+
+Eddy & Davies                 Informational                     [Page 5]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+   broadly in the future.  The two examples cited here, of fields that
+   have proven too small in general Internet protocols, are only a small
+   sampling of the much larger set of similar instances that the authors
+   can think of.  Outside the Internet protocols, within ASN.1 and
+   previous ITU protocols, constructs very similar to SDNVs have been
+   used for many years due to engineering concerns very similar to those
+   facing the DTNRG.
+
+   Many protocols use a Type-Length-Value method for encoding variable-
+   length fields (e.g., TCP's options format or many of the fields in
+   the Internet Key Exchange Protocol version 2 (IKEv2)).  An SDNV is
+   equivalent to combining the length and value portions of this type of
+   field, with the overhead of the length portion amortized out over the
+   bytes of the value.  The penalty paid for this in an SDNV may be
+   several extra bytes for long values (e.g., 1024-bit RSA keys).  See
+   Section 4 for further discussion and a comparison.
+
+   As is shown in later sections, for large values, the current SDNV
+   scheme is fairly inefficient in terms of space (1/8 of the bits are
+   overhead) and not particularly easy to encode/decode in comparison to
+   alternatives.  The best use of SDNVs may often be to define the
+   Length field of a TLV structure to be an SDNV whose value is the
+   length of the TLV's Value field.  In this way, one can avoid forcing
+   large numbers from being directly encoded as an SDNV, yet retain the
+   extensibility that using SDNVs grants.
+
+2.  Definition of SDNVs
+
+   Early in the work of the DTNRG, it was agreed that the properties of
+   an SDNV were useful for DTN protocols.  The exact SDNV format used by
+   the DTNRG evolved somewhat over time before the publication of the
+   initial RFCs on LTP and BP.  An earlier version (see the initial
+   version of LTP Internet Draft [BRF04]) bore a resemblance to the
+   ASN.1 [ASN1] Basic Encoding Rules (BER) [X.690] for lengths (Section
+   8.1.3 of X.690).  The current SDNV format is the one used by ASN.1
+   BER for encoding tag identifiers greater than or equal to 31 (Section
+   8.1.2.4.2 of X.690).  A comparison between the current SDNV format
+   and the early SDNV format is made in Section 4.
+
+   The format currently used is very simple.  Before encoding, an
+   integer is represented as a left-to-right bitstring beginning with
+   its most significant bit and ending with its least significant bit.
+   If the bitstring's length is not a multiple of 7, then the string is
+   left-padded with zeros.  When transmitted, the bits are encoded into
+   a series of bytes.  The low-order 7 bits of each byte in the encoded
+   format are taken left-to-right from the integer's bitstring
+
+
+
+
+
+Eddy & Davies                 Informational                     [Page 6]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+   representation.  The most significant bit of each byte specifies
+   whether it is the final byte of the encoded value (when it holds a
+   0), or not (when it holds a 1).
+
+   For example:
+
+   o  1 (decimal) is represented by the bitstring "0000001" and encoded
+      as the single byte 0x01 (in hexadecimal).
+
+   o  128 is represented by the bitstring "10000001 00000000" and
+      encoded as the bytes 0x81 followed by 0x00.
+
+   o  Other values can be found in the test vectors of the source code
+      in Appendix A.
+
+   To be perfectly clear, and avoid potential interoperability issues
+   (as have occurred with ASN.1 BER time values), we explicitly state
+   two considerations regarding zero-padding. (1) When encoding SDNVs,
+   any leading (most significant) zero bits in the input number might be
+   discarded by the SDNV encoder.  Protocols that use SDNVs should not
+   rely on leading-zeros being retained after encoding and decoding
+   operations. (2) When decoding SDNVs, the relevant number of leading
+   zeros required to pad up to a machine word or other natural data unit
+   might be added.  These are put in the most significant positions in
+   order to not change the value of the number.  Protocols using SDNVs
+   should consider situations where lost zero-padding may be
+   problematic.
+
+   The issues of zero-padding are particularly relevant where an SDNV is
+   being used to represent a bitfield to be transmitted by a protocol.
+   The specification of the protocol and any associated IANA registry
+   should specify the allocation and usage of bit positions within the
+   unencoded field.  Unassigned and reserved bits in the unencoded field
+   will be treated as zeros by the SDNV encoding prior to transmission.
+   Assuming the bit positions are numbered starting from 0 at the least
+   significant bit position in the integer representation, then if
+   higher-numbered positions in the field contain all zeros, the
+   encoding process may not transmit these bits explicitly (e.g., if all
+   the bit positions numbered 7 or higher are zeros, then the
+   transmitted SDNV can consist of just one octet).  On reception, the
+   decoding process will treat any untransmitted higher-numbered bits as
+   zeros.  To ensure correct operation of the protocol, the sender and
+   receiver must have a consistent interpretation of the width of the
+   bitfield.  This can be achieved in various ways:
+
+   o  the bitfield width is implicitly defined by the version of the
+      protocol in use in the sender and receiver,
+
+
+
+
+Eddy & Davies                 Informational                     [Page 7]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+   o  sending the width of the bitfield explicitly in a separate item,
+
+   o  the higher-numbered bits can be safely ignored by the receiver
+      (e.g., because they represent optimizations), or
+
+   o  marking the highest-numbered bit by prepending a '1' bit to the
+      bitfield.
+
+   The protocol specification must record how the consistent
+   interpretation is achieved.
+
+   The SDNV encoding technique is also known as Variable Byte Encoding
+   (see Section 5.3.1 of [Manning09]) and is equivalent to Base-128
+   Elias Gamma Encoding (see Section 5.3.2 of [Manning09] and Section
+   3.5 of [Sayood02]).  However, the primary motivation for SDNVs is to
+   provide an extensible protocol framework rather than optimal data
+   compression, which is the motivation behind the other uses of the
+   technique.  [Manning09] points out that the key feature of this
+   encoding is that it is "prefix free" meaning that no code is a prefix
+   of any other, which is an alternative way of expressing the self-
+   delimiting property.
+
+3.  Basic Algorithms
+
+   This section describes some simple algorithms for creating and
+   parsing SDNV fields.  These may not be the most efficient algorithms
+   possible, however, they are easy to read, understand, and implement.
+   Appendix A contains Python source code implementing the routines
+   described here.  The algorithms presented here are convenient for
+   converting between an internal data block and serialized data stream
+   associated with a transmission device.  Other approaches are possible
+   with different efficiencies and trade-offs.
+
+3.1.  Encoding Algorithm
+
+   There is a very simple algorithm for the encoding operation that
+   converts a non-negative integer (value n, of length 1+floor(log n)
+   bits) into an SDNV.  This algorithm takes n as its only argument and
+   returns a string of bytes:
+
+   o  (Initial Step) Set a variable X to a byte sharing the least
+      significant 7 bits of n, and with 0 in the most significant bit,
+      and a variable Y to n, right-shifted by 7 bits.
+
+   o  (Recursion Step) If Y == 0, return X.  Otherwise, set Z to the
+      bitwise-or of 0x80 with the 7 least significant bits of Y, and
+      append Z to X.  Right-shift Y by 7 bits and repeat the Recursion
+      Step.
+
+
+
+Eddy & Davies                 Informational                     [Page 8]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+   This encoding algorithm has a time complexity of O(log n), since it
+   takes a number of steps equal to ceil(n/7), and no additional space
+   beyond the size of the result (8/7 log n) is required.  One aspect of
+   this algorithm is that it assumes strings can be efficiently appended
+   to new bytes.  One way to implement this is to allocate a buffer for
+   the expected length of the result and fill that buffer one byte at a
+   time from the right end.
+
+   If, for some reason, an implementation requires an encoded SDNV to be
+   some specific length (possibly related to a machine word), any
+   leftmost zero-padding included needs to properly set the high-order
+   bit in each byte of padding.
+
+3.2.  Decoding Algorithm
+
+   Decoding SDNVs is a more difficult operation than encoding them, due
+   to the fact that no bound on the resulting value is known until the
+   SDNV is parsed, at which point the value itself is already known.
+   This means that if space is allocated in advance to hold the value
+   that results from decoding an SDNV, in general, it is not known
+   whether this space will be large enough until it is 7 bits away from
+   being overflowed.  However, as specified in Section 3.3, protocols
+   using SDNVs must specify the largest number of bits that an
+   implementation is expected to handle, which mitigates this problem.
+
+   o  (Initial Step) Set the result to 0.  Set an index to the first
+      byte of the encoded SDNV.
+
+   o  (Recursion Step) Shift the result left 7 bits.  Add the low-order
+      7 bits of the value at the index to the result.  If the high-order
+      bit under the pointer is a 1, advance the index by one byte within
+      the encoded SDNV and repeat the Recursion Step, otherwise return
+      the current value of the result.
+
+   This decoding algorithm takes no more additional space than what is
+   required for the result (7/8 the length of the SDNV) and the pointer.
+   The complication is that before the result can be left-shifted in the
+   Recursion Step, an implementation needs to first make sure that this
+   will not cause any bits to be lost, and re-allocate a larger piece of
+   memory for the result, if required.  The pure time complexity is the
+   same as for the encoding algorithm given, but if re-allocation is
+   needed due to the inability to predict the size of the result,
+   decoding may be slower.
+
+   These decoding steps include removal of any leftmost zero-padding
+   that might be used by an encoder to create encodings of a certain
+   length.
+
+
+
+
+Eddy & Davies                 Informational                     [Page 9]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+3.3.  Limitations of Implementations
+
+   Because of efficiency considerations or convenience of internal
+   representation of decoded integers, implementations may choose to
+   limit the number of bits in SDNVs that they will handle.  To avoid
+   interoperability problems, any protocol that uses SDNVs must specify
+   the largest number of bits in an SDNV that an implementation of that
+   protocol is expected to handle.
+
+   For example, Section 4.1 of [RFC5050] specifies that implementations
+   of the DTN Bundle Protocol are not required to handle SDNVs with more
+   than 64 bits in their unencoded value.  Accordingly, integer values
+   transmitted in SDNVs have an upper limit and SDNV-encoded flag fields
+   must be limited to 64 bit positions in any future revisions of the
+   protocol unless the restriction is altered.
+
+4.  Comparison to Alternatives
+
+   This section compares three alternative ways of implementing the
+   concept of SDNVs: (1) the TLV scheme commonly used in the Internet
+   family, and many other families of protocols, (2) the old style of
+   SDNVs (both the SDNV-8 and SDNV-16) defined in an early stage of
+   LTP's development [BRF04], and (3) the current SDNV format.
+
+   The TLV method uses two fixed-length fields to hold the Type and
+   Length elements that then imply the syntax and semantics of the Value
+   element.  This is only similar to an SDNV in that the value element
+   can grow or shrink within the bounds capable of being conveyed by the
+   Length field.  Two fundamental differences between TLVs and SDNVs are
+   that through the Type element, TLVs also contain some notion of what
+   their contents are semantically, while SDNVs are simply generic non-
+   negative integers, and protocol engineers still have to choose fixed-
+   field lengths for the Type and Length fields in the TLV format.
+
+   Some protocols use TLVs where the value conveyed within the Length
+   field needs to be decoded into the actual length of the Value field.
+   This may be accomplished through simple multiplication, left-
+   shifting, or a look-up table.  In any case, this tactic limits the
+   granularity of the possible Value lengths, and can contribute some
+   degree of bloat if Values do not fit neatly within the available
+   decoded Lengths.
+
+   In the SDNV format originally used by LTP, parsing the first byte of
+   the SDNV told an implementation how much space was required to hold
+   the contained value.  There were two different types of SDNVs defined
+   for different ranges of use.  The SDNV-8 type could hold values up to
+   127 in a single byte, while the SDNV-16 type could hold values up to
+   32,767 in 2 bytes.  Both formats could encode values requiring up to
+
+
+
+Eddy & Davies                 Informational                    [Page 10]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+   N bytes in N+2 bytes, where N<127.  The major difference between this
+   old SDNV format and the current SDNV format is that the new format is
+   not as easily decoded as the old format was, but the new format also
+   has absolutely no limitation on its length.
+
+   The advantage in ease of parsing the old format manifests itself in
+   two aspects: (1) the size of the value is determinable ahead of time,
+   in a way equivalent to parsing a TLV, and (2) the actual value is
+   directly encoded and decoded, without shifting and masking bits as is
+   required in the new format.  For these reasons, the old format
+   requires less computational overhead to deal with, but is also very
+   limited in that it can only hold a 1024-bit number, at maximum.
+   Since according to IETF Best Current Practices, an asymmetric
+   cryptography key needed to last for a long term requires using moduli
+   of over 1228 bits [RFC3766], this could be seen as a severe
+   limitation of the old style of SDNVs, from which the currently used
+   style does not suffer.
+
+   Table 1 compares the maximum values that can be encoded into SDNVs of
+   various lengths using the old SDNV-8/16 method and the current SDNV
+   method.  The only place in this table where SDNV-16 is used rather
+   than SDNV-8 is in the 2-byte row.  Starting with a single byte, the
+   two methods are equivalent, but when using 2 bytes, the old method is
+   a more compact encoding by one bit.  From 3 to 7 bytes of length
+   though, the current SDNV format is more compact, since it only
+   requires one bit per byte of overhead, whereas the old format used a
+   full byte.  Thus, at 8 bytes, both schemes are equivalent in
+   efficiency since they both use 8 bits of overhead.  Up to 129 bytes,
+   the old format is more compact than the current one, although after
+   this, limit it becomes unusable.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Eddy & Davies                 Informational                    [Page 11]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+   +-------+---------------+-------------+---------------+-------------+
+   | Bytes |   SDNV-8/16   |     SDNV    |   SDNV-8/16   |     SDNV    |
+   |       | Maximum Value |   Maximum   | Overhead Bits |   Overhead  |
+   |       |               |    Value    |               |     Bits    |
+   +-------+---------------+-------------+---------------+-------------+
+   |   1   |      127      |     127     |       1       |      1      |
+   |       |               |             |               |             |
+   |   2   |     32,767    |    16,383   |       1       |      2      |
+   |       |               |             |               |             |
+   |   3   |     65,535    |  2,097,151  |       8       |      3      |
+   |       |               |             |               |             |
+   |   4   |    2^24 - 1   |   2^28 - 1  |       8       |      4      |
+   |       |               |             |               |             |
+   |   5   |    2^32 - 1   |   2^35 - 1  |       8       |      5      |
+   |       |               |             |               |             |
+   |   6   |    2^40 - 1   |   2^42 - 1  |       8       |      6      |
+   |       |               |             |               |             |
+   |   7   |    2^48 - 1   |   2^49 - 1  |       8       |      7      |
+   |       |               |             |               |             |
+   |   8   |    2^56 - 1   |   2^56 - 1  |       8       |      8      |
+   |       |               |             |               |             |
+   |   9   |    2^64 - 1   |   2^63 - 1  |       8       |      9      |
+   |       |               |             |               |             |
+   |   10  |    2^72 - 1   |   2^70 - 1  |       8       |      10     |
+   |       |               |             |               |             |
+   |   16  |   2^120 - 1   |  2^112 - 1  |       8       |      16     |
+   |       |               |             |               |             |
+   |   32  |   2^248 - 1   |  2^224 - 1  |       8       |      32     |
+   |       |               |             |               |             |
+   |   64  |   2^504 - 1   |  2^448 - 1  |       8       |      64     |
+   |       |               |             |               |             |
+   |  128  |   2^1016 - 1  |  2^896 - 1  |       8       |     128     |
+   |       |               |             |               |             |
+   |  129  |   2^1024 - 1  |  2^903 - 1  |       8       |     129     |
+   |       |               |             |               |             |
+   |  130  |      N/A      |  2^910 - 1  |      N/A      |     130     |
+   |       |               |             |               |             |
+   |  256  |      N/A      |  2^1792 - 1 |      N/A      |     256     |
+   +-------+---------------+-------------+---------------+-------------+
+
+                                  Table 1
+
+   Suggested usages of the SDNV format that leverage its strengths and
+   limit the effects of its weaknesses are discussed in Section 1.3.
+
+   Another aspect of the comparison between SDNVs and alternatives using
+   fixed-length fields is the result of errors in transmission.  Bit-
+   errors in an SDNV can result in either errors in the decoded value,
+
+
+
+Eddy & Davies                 Informational                    [Page 12]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+   or parsing errors in subsequent fields of the protocol.  In fixed-
+   length fields, bit errors always result in errors to the decoded
+   value rather than parsing errors in subsequent fields.  If the
+   decoded values from either type of field encoding (SDNV or fixed-
+   length) are used as indexes, offsets, or lengths of further fields in
+   the protocol, similar failures result.
+
+5.  Security Considerations
+
+   The only security considerations with regard to SDNVs are that code
+   that parses SDNVs should have bounds-checking logic and be capable of
+   handling cases where an SDNV's value is beyond the code's ability to
+   parse.  These precautions can prevent potential exploits involving
+   SDNV decoding routines.
+
+   Stephen Farrell noted that very early definitions of SDNVs also
+   allowed negative integers.  This was considered a potential security
+   hole, since it could expose implementations to underflow attacks
+   during SDNV decoding.  There is a precedent in that many existing TLV
+   decoders map the Length field to a signed integer and are vulnerable
+   in this way.  An SDNV decoder should be based on unsigned types and
+   not have this issue.
+
+6.  Acknowledgements
+
+   Scott Burleigh, Manikantan Ramadas, Michael Demmer, Stephen Farrell,
+   and other members of the IRTF DTN Research Group contributed to the
+   development and usage of SDNVs in DTN protocols.  George Jones and
+   Keith Scott from Mitre, Lloyd Wood, Gerardo Izquierdo, Joel Halpern,
+   Peter TB Brett, Kevin Fall, and Elwyn Davies also contributed useful
+   comments on and criticisms of this document.  DTNRG last call
+   comments on the document were sent to the mailing list by Lloyd Wood,
+   Will Ivancic, Jim Wyllie, William Edwards, Hans Kruse, Janico
+   Greifenberg, Teemu Karkkainen, Stephen Farrell, and Scott Burleigh.
+   Further constructive comments from Dave Crocker, Lachlan Andrew, and
+   Michael Welzl were incorporated.
+
+   Work on this document was performed at NASA's Glenn Research Center,
+   in support of the NASA Space Communications Architecture Working
+   Group (SCAWG), NASA's Earth Science Technology Office (ESTO), and the
+   FAA/Eurocontrol Future Communications Study (FCS) in the 2005-2007
+   time frame, while the editor was an employee of Verizon Federal
+   Network Systems.
+
+
+
+
+
+
+
+
+Eddy & Davies                 Informational                    [Page 13]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+7.  Informative References
+
+   [ASN1]       ITU-T Rec. X.680, "Abstract Syntax Notation One (ASN.1).
+                Specification of Basic Notation", ISO/IEC 8824-1:2002,
+                2002.
+
+   [BRF04]      Burleigh, S., Ramadas, M., and S. Farrell, "Licklider
+                Transmission Protocol", Work in Progress, May 2004.
+
+   [Hain05]     Hain, T., "A Pragmatic Report on IPv4 Address Space
+                Consumption", Internet Protocol Journal Vol. 8, No. 3,
+                September 2005.
+
+   [IEN21]      Cerf, V. and J. Postel, "Specification of Internetwork
+                Transmission Control Program: TCP Version 3", Internet
+                Experimental Note 21, January 1978.
+
+   [Manning09]  Manning, c., Raghavan, P., and H. Schuetze,
+                "Introduction to Information Retrieval", Cambridge
+                University Press ISBN-13: 978-0521865715, 2009,
+                <http://informationretrieval.org/>.
+
+   [RFC0713]    Haverty, J., "MSDTP-Message Services Data Transmission
+                Protocol", RFC 713, April 1976.
+
+   [RFC0791]    Postel, J., "Internet Protocol", STD 5, RFC 791,
+                September 1981.
+
+   [RFC0793]    Postel, J., "Transmission Control Protocol", STD 7,
+                RFC 793, September 1981.
+
+   [RFC1323]    Jacobson, V., Braden, B., and D. Borman, "TCP Extensions
+                for High Performance", RFC 1323, May 1992.
+
+   [RFC2993]    Hain, T., "Architectural Implications of NAT", RFC 2993,
+                November 2000.
+
+   [RFC3766]    Orman, H. and P. Hoffman, "Determining Strengths For
+                Public Keys Used For Exchanging Symmetric Keys", BCP 86,
+                RFC 3766, April 2004.
+
+   [RFC4963]    Heffner, J., Mathis, M., and B. Chandler, "IPv4
+                Reassembly Errors at High Data Rates", RFC 4963,
+                July 2007.
+
+   [RFC5050]    Scott, K. and S. Burleigh, "Bundle Protocol
+                Specification", RFC 5050, November 2007.
+
+
+
+
+Eddy & Davies                 Informational                    [Page 14]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+   [RFC5325]    Burleigh, S., Ramadas, M., and S. Farrell, "Licklider
+                Transmission Protocol - Motivation", RFC 5325,
+                September 2008.
+
+   [RFC5326]    Ramadas, M., Burleigh, S., and S. Farrell, "Licklider
+                Transmission Protocol - Specification", RFC 5326,
+                September 2008.
+
+   [Sayood02]   Sayood, K., "Lossless Data Compression", Academic
+                Press ISBN-13: 978-0126208610, December 2002,
+                <http://books.google.co.uk/books?id=LjQiGwyabVwC>.
+
+   [X.690]      ITU-T Rec. X.690, "Abstract Syntax Notation One (ASN.1).
+                Encoding Rules: Specification of Basic Encoding Rules
+                (BER), Canonical Encoding Rules (CER) and Distinguished
+                Encoding Rules (DER)", ISO/IEC 8825-1:2002, 2002.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Eddy & Davies                 Informational                    [Page 15]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+Appendix A.  SDNV Python Source Code
+
+   #  This code may be freely copied.  Attribution would be appreciated.
+   #
+   # sdnv_decode() takes a string argument (s), which is assumed to be
+   #   an SDNV, and optionally a number (slen) for the maximum number of
+   #   bytes to parse from the string.  The function returns a pair of
+   #   the non-negative integer n that is the numeric value encoded in
+   #   the SDNV, and integer that is the distance parsed into the input
+   #   string.  If the slen argument is not given (or is not a non-zero
+   #   number) then, s is parsed up to the first byte whose high-order
+   #   bit is 0 -- the length of the SDNV portion of s does not have to
+   #   be pre-computed by calling code.  If the slen argument is given
+   #   as a non-zero value, then slen bytes of s are parsed.  The value
+   #   for n of -1 is returned for any type of parsing error.
+   #
+   # NOTE: In python, integers can be of arbitrary size.  In other
+   #   languages, such as C, SDNV-parsing routines should take
+   #   precautions to avoid overflow (e.g., by using the Gnu MP library,
+   #   or similar).
+   #
+   def sdnv_decode(s, slen=0):
+     n = long(0)
+     for i in range(0, len(s)):
+       v = ord(s[i])
+       n = n<<7
+       n = n + (v & 0x7F)
+       if v>>7 == 0:
+         slen = i+1
+         break
+       elif i == len(s)-1 or (slen != 0 and i > slen):
+         n = -1 # reached end of input without seeing end of SDNV
+     return (n, slen)
+
+   # sdnv_encode() returns the SDNV-encoded string that represents n.
+   #   An empty string is returned if n is not a non-negative integer
+   def sdnv_encode(n):
+     r = ""
+     # validate input
+     if n >= 0 and (type(n) in [type(int(1)), type(long(1))]):
+       flag = 0
+       done = False
+       while not done:
+         # encode lowest 7 bits from n
+         newbits = n & 0x7F
+         n = n>>7
+         r = chr(newbits + flag) + r
+         if flag == 0:
+
+
+
+Eddy & Davies                 Informational                    [Page 16]
+
+RFC 6256                       Using SDNVs                      May 2011
+
+
+           flag = 0x80
+         if n == 0:
+           done = True
+     return r
+
+
+   # test cases from LTP and BP internet-drafts, only print failures
+   def sdnv_test():
+     tests = [(0xABC, chr(0x95) + chr(0x3C)),
+              (0x1234, chr(0xA4) + chr (0x34)),
+              (0x4234, chr(0x81) + chr(0x84) + chr(0x34)),
+              (0x7F, chr(0x7F))]
+
+     for tp in tests:
+       # test encoding function
+       if sdnv_encode(tp[0]) != tp[1]:
+         print "sdnv_encode fails on input %s" % hex(tp[0])
+       # test decoding function
+       if sdnv_decode(tp[1])[0] != tp[0]:
+         print "sdnv_decode fails on input %s, giving %s" % \
+               (hex(tp[0]), sdnv_decode(tp[1]))
+
+Authors' Addresses
+
+   Wesley M. Eddy
+   MTI Systems
+   NASA Glenn Research Center
+   MS 500-ASRC; 21000 Brookpark Rd
+   Cleveland, OH  44135
+
+   Phone: 216-433-6682
+   EMail: wes@mti-systems.com
+
+
+   Elwyn Davies
+   Folly Consulting
+   Soham
+   UK
+
+   Phone:
+   EMail: elwynd@folly.org.uk
+   URI:
+
+
+
+
+
+
+
+
+
+Eddy & Davies                 Informational                    [Page 17]
+