< draft-irtf-dtnrg-sdnv-03.txt   draft-irtf-dtnrg-sdnv-04.txt >
Network Working Group W. Eddy Network Working Group W. Eddy
Internet-Draft Verizon Internet-Draft MTI Systems
Intended status: Informational August 18, 2009 Intended status: Informational November 19, 2009
Expires: February 19, 2010 Expires: May 23, 2010
Using Self-Delimiting Numeric Values in Protocols Using Self-Delimiting Numeric Values in Protocols
draft-irtf-dtnrg-sdnv-03 draft-irtf-dtnrg-sdnv-04
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 bit-string 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 Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
skipping to change at page 1, line 32 skipping to change at page 1, line 46
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on February 19, 2010. This Internet-Draft will expire on May 23, 2010.
Copyright Notice Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of Provisions Relating to IETF Documents
publication of this document (http://trustee.ietf.org/license-info). (http://trustee.ietf.org/license-info) in effect on the date of
Please review these documents carefully, as they describe your rights publication of this document. Please review these documents
and restrictions with respect to this document. carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
Abstract include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
Self-Delimiting Numeric Values (SDNVs) have recently been introduced described in the BSD License.
as a field type in proposed Delay-Tolerant Networking protocols.
SDNVs encode an arbitrary-length non-negative integer with minimum
wire-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.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Problems with Fixed Value Fields . . . . . . . . . . . . . 3 1.1. Problems with Fixed Value Fields . . . . . . . . . . . . . 3
1.2. SDNVs for DTN Protocols . . . . . . . . . . . . . . . . . 4 1.2. SDNVs for DTN Protocols . . . . . . . . . . . . . . . . . 4
1.3. SDNV Usage . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3. SDNV Usage . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Definition of SDNVs . . . . . . . . . . . . . . . . . . . . . 7 2. Definition of SDNVs . . . . . . . . . . . . . . . . . . . . . 7
3. Basic Algorithms . . . . . . . . . . . . . . . . . . . . . . . 8 3. Basic Algorithms . . . . . . . . . . . . . . . . . . . . . . . 8
3.1. Encoding Algorithm . . . . . . . . . . . . . . . . . . . . 8 3.1. Encoding Algorithm . . . . . . . . . . . . . . . . . . . . 8
skipping to change at page 3, line 19 skipping to change at page 3, line 19
has received review and support within the DTNRG, as discussed in the has received review and support within the DTNRG, as discussed in the
Acknowledgements section of this document. Acknowledgements section of this document.
This document begins by describing a common problem encountered in This document begins by describing a common problem encountered in
network protocol engineering. It then provides some background on network protocol engineering. It then provides some background on
the Self-Delimiting Numeric Values (SDNVs) proposed for use in DTN the Self-Delimiting Numeric Values (SDNVs) proposed for use in DTN
protocols, and motivates their potential applicability in other protocols, and motivates their potential applicability in other
networking protocols. The DTNRG has created SDNVs to meet the networking protocols. The DTNRG has created SDNVs to meet the
challenges it attempts to solve, and it has been noted that SDNVs challenges it attempts to solve, and it has been noted that SDNVs
closely resemble certain constructs within ASN.1 and even older ITU closely resemble certain constructs within ASN.1 and even older ITU
protocols, so the problems are not new or unique to DTN, nor is the protocols, so the problems are not new or unique to DTN.
solution too radical for more mundane uses.
SDNVs are tersely defined in both the bundle protocol [RFC5050] and SDNVs are tersely defined in both the bundle protocol [RFC5050] and
LTP [RFC5326] specifications, due to the flow of document production LTP [RFC5326] specifications, due to the flow of document production
in the DTNRG. This document clarifies and further explains the in the DTNRG. This document clarifies and further explains the
motivations and engineering decisions behind SDNVs. motivations and engineering decisions behind SDNVs.
1.1. Problems with Fixed Value Fields 1.1. Problems with Fixed Value Fields
Protocol designers commonly face an optimization problem in Protocol designers commonly face an optimization problem in
determining the proper size for header fields. There is a strong determining the proper size for header fields. There is a strong
desire to keep fields as small as possible, in order to reduce the desire to keep fields as small as possible, in order to reduce the
protocol's overhead on the wire, and also allow for fast processing. protocol's overhead, and also allow for fast processing. Since
Since protocols can be used many years (even decades) after they are protocols can be used many years (even decades) after they are
designed, and networking technology has tended to change rapidly, it designed, and networking technology has tended to change rapidly, it
is not uncommon for the use, deployment, or performance of a is not uncommon for the use, deployment, or performance of a
particular protocol to be limited or infringed upon by the length of particular protocol to be limited or infringed upon by the length of
some header field being too short. Two well-known examples of this some header field being too short. Two well-known examples of this
phenomenon are the TCP advertised receive window, and the IPv4 phenomenon are the TCP advertised receive window, and the IPv4
address length. address length.
TCP segments contain an advertised receive window field that is fixed TCP segments contain an advertised receive window field that is fixed
at 16 bits [RFC0793], encoding a maximum value of around 65 at 16 bits [RFC0793], encoding a maximum value of around 65
kilobytes. The purpose of this value is to provide flow control, by 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 allowing a receiver to specify how many sent bytes its peer can have
outstanding (unacknowledged) at any time, thus allowing the receiver outstanding (unacknowledged) at any time, thus allowing the receiver
to limit its buffer size. As network speeds have grown by several to limit its buffer size. As network speeds have grown by several
orders of magnitude since TCP's inception, the combination of the 65 orders of magnitude since TCP's inception, the combination of the 65
kilobyte maximum advertised window and long round-trip times kilobyte maximum advertised window and long round-trip times
prevented TCP senders from being able to acheive the high-rates that prevented TCP senders from being able to acheive the high throughput
the underlying network supported. This limitation was remedied that the underlying network supported. This limitation was remedied
through the use of the Window Scale option [RFC1323], which provides through the use of the Window Scale option [RFC1323], which provides
a multiplier for the advertised window field. However, the Window a multiplier for the advertised window field. However, the Window
Scale multiplier is fixed for the duration of the connection, Scale multiplier is fixed for the duration of the connection,
requires bi-directional support, and limits the precision of the requires support from each end of a TCP connection, and limits the
advertised receive window, so this is certainly a less-than-ideal precision of the advertised receive window, so this is certainly a
solution. Because of the field width limit in the original design less-than-ideal solution. Because of the field width limit in the
however, the Window Scale is necessary for TCP to reach high sending original design however, the Window Scale is necessary for TCP to
rates. reach high sending rates.
An IPv4 address is fixed at 32 bits [RFC0791] (as a historical note, An IPv4 address is fixed at 32 bits [RFC0791] (as a historical note,
earlier versions of the IP specification supported variable-length an early version 0 IP header format specification in [IEN21] used
addresses). Due to the way that subnetting and assignment of address variable-length addresses in multiples of 8-bits up to 120-bits).
blocks was performed, the number of IPv4 addresses has been seen as a Due to the way that subnetting and assignment of address blocks was
limit to the growth of the Internet [Hain05]. Two divergent paths to performed, the number of IPv4 addresses has been seen as a limit to
solve this problem have been the use of Network Address Translators the growth of the Internet [Hain05]. Two divergent paths to solve
(NATs) and the development of IPv6. NATs have caused a number of this problem have been the use of Network Address Translators (NATs)
side-issues and problems [RFC2993], leading to increased complexity and the development of IPv6. NATs have caused a number of other
and fragility, as well as forcing work-arounds to be engineered for issues and problems [RFC2993], leading to increased complexity and
many other protocols to function within a NATed environment. The fragility, as well as forcing work-arounds to be engineered for many
IPv6 solution's transitional work has been underway for several other protocols to function within a NATed environment. The IPv6
years, but has still only begun to have visible impact on the global solution's transitional work has been underway for several years, but
has still only just begun to have visible impact on the global
Internet. Internet.
Of course, in both the case of the TCP receive window and IPv4 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 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 good idea at the time. The fields were more than big enough for the
originally perceived usage of the protocols, and yet were small originally perceived usage of the protocols, and yet were small
enough to allow the total headers to remain compact and relatively enough to allow the headers to remain compact and relatively easy and
easy and efficient to parse on machines of the time. The fixed sizes efficient to parse on machines of the time. The fixed sizes that
that were defined represented a tradeoff between the scalability of were defined represented a tradeoff between the scalability of the
the protocol versus the overhead and efficiency of processing. In protocol versus the overhead and efficiency of processing. In both
both cases, these engineering decisions turned out to be painfully cases, these engineering decisions turned out to be painfully
restrictive in the longer term. restrictive in the longer term.
1.2. SDNVs for DTN Protocols 1.2. SDNVs for DTN Protocols
In specifications for the DTN Bundle Protocol (BP) [RFC5050] and In specifications for the DTN Bundle Protocol (BP) [RFC5050] and
Licklider Transmission Protocol (LTP) [RFC5326], SDNVs have been used Licklider Transmission Protocol (LTP) [RFC5326], SDNVs have been used
for several fields including identifiers, payload/header lengths, and for several fields including identifiers, payload/header lengths, and
serial (sequence) numbers. SDNVs were developed for use in these serial (sequence) numbers. SDNVs were developed for use in these
types of fields, to avoid sending more bytes than needed, as well as types of fields, to avoid sending more bytes than needed, as well as
avoiding fixed sizes that may not end up being appropriate. For avoiding fixed sizes that may not end up being appropriate. For
skipping to change at page 5, line 14 skipping to change at page 5, line 14
similar in mechanism to TCP's Window Scale option are unsuitable for similar in mechanism to TCP's Window Scale option are unsuitable for
use in DTN protocols since due to high delays, DTN protocols must use in DTN protocols since due to high delays, DTN protocols must
avoid handshaking and configuration parameter negotiation to the avoid handshaking and configuration parameter negotiation to the
greatest extent possible. All of these reasons make the choice of greatest extent possible. All of these reasons make the choice of
SDNVs for use in DTN protocols attractive. SDNVs for use in DTN protocols attractive.
1.3. SDNV Usage 1.3. SDNV Usage
In short, an SDNV is simply a way of representing non-negative In short, an SDNV is simply a way of representing non-negative
integers (both positive integers of arbitrary magnitude and 0), integers (both positive integers of arbitrary magnitude and 0),
without expending too-much unneccessary space. This definition without expending much unneccessary space. This definition allows
allows SDNVs to represent many common protocol header fields, such SDNVs to represent many common protocol header fields, such as:
as:
o Random identification fields as used in the IPsec Security o Random identification fields as used in the IPsec Security
Parameters Index or in IP headers for fragment reassembly (Note: Parameters Index or in IP headers for fragment reassembly (Note:
the 16-bit IP ID field for fragment reassembly was recently found the 16-bit IP ID field for fragment reassembly was recently found
to be too short in some environments [RFC4963]), to be too short in some environments [RFC4963]),
o Sequence numbers as in TCP or SCTP, o Sequence numbers as in TCP or SCTP,
o Values used in cryptographic algorithms such as RSA keys, Diffie- o Values used in cryptographic algorithms such as RSA keys, Diffie-
Hellman key-agreement, or coordinates of points on elliptic Hellman key-agreement, or coordinates of points on elliptic
curves. curves.
o Message lengths as used in file transfer protocols. o Message lengths as used in file transfer protocols.
o Nonces and cookies. o Nonces and cookies.
o Etc. o Etc.
As any bit-string can be interpreted as an unsigned integer, SDNVs
can also encode arbitrary-length bit strings, including bit-strings
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, bit-strings, 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 The use of SDNVs rather than fixed length fields gives protocol
designers the ability to somewhat circumvent making difficult-to- designers the ability to ameliorate the consequences of making
reverse field-sizing decisions, since the SDNV wire-format grows and difficult-to-reverse field-sizing decisions, as the SDNV format grows
shrinks depending on the particular value encoded. SDNVs do not and shrinks depending on the particular value encoded. SDNVs do not
necessarily provide optimal encodings for values of any particular necessarily provide optimal encodings for values of any particular
length, however they allow protocol designers to avoid potential length, however they allow protocol designers to avoid potential
blunders in assigning fixed lengths, and remove the complexity blunders in assigning fixed lengths, and remove the complexity
involved with either negotiating field lengths or constructing involved with either negotiating field lengths or constructing
protocol extensions. protocol extensions.
To our knowledge, at this time, no IETF transport or network-layer To our knowledge, at this time, no IETF transport or network-layer
protocol designed for use outside of the DTN domain have proposed to 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 use SDNVs; however there is no inherent reason not to use SDNVs more
broadly in the future. The two examples cited here of fields that broadly in the future. The two examples cited here, of fields that
have proven too-small in general Internet protocols are only a small have proven too small in general Internet protocols, are only a small
sampling of the much larger set of similar instances that the authors sampling of the much larger set of similar instances that the authors
can think of. Outside the Internet protocols, within ASN.1 and can think of. Outside the Internet protocols, within ASN.1 and
previous ITU protocols, constructs very similar to SDNVs have been previous ITU protocols, constructs very similar to SDNVs have been
used for many years due to engineering concerns very similar to those used for many years due to engineering concerns very similar to those
facing the DTNRG. facing the DTNRG.
Many protocols use a Type-Length-Value method for encoding variable Many protocols use a Type-Length-Value method for encoding variable
length strings (e.g. TCP's options format, or many of the fields in length strings (e.g. TCP's options format, or many of the fields in
IKEv2). An SDNV is equivalent to combining the length and value IKEv2). An SDNV is equivalent to combining the length and value
portions of this type of field, with the overhead of the length portions of this type of field, with the overhead of the length
skipping to change at page 7, line 14 skipping to change at page 7, line 14
2. Definition of SDNVs 2. Definition of SDNVs
An early definition of the SDNV format bore resemblance to the ASN.1 An early definition of the SDNV format bore resemblance to the ASN.1
[ASN1] Basic Encoding Rules (BER) [ASN1-BER] for lengths (Section [ASN1] Basic Encoding Rules (BER) [ASN1-BER] for lengths (Section
8.1.3 of X.690). The current SDNV format is the one used by ASN.1 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 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 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. and the early SDNV format is made in Section 4.
The currently-used format is very simple. Before encoding, an The format currently used is very simple. Before encoding, an
integer is represented as a left-to-right bitstring beginning with integer is represented as a left-to-right bitstring beginning with
its most significant bit, and ending with its least signifcant bit. its most significant bit, and ending with its least signifcant bit.
On the wire, the bits are encoded into a series of bytes. The most When transmitted, the bits are encoded into a series of bytes. The
significant bit of each wire format byte specifies whether it is the most significant bit of each byte specifies whether it is the final
final byte of the encoded value (when it holds a 0), or not (when it byte of the encoded value (when it holds a 0), or not (when it holds
holds a 1). The remaining 7 bits of each byte in the wire format are a 1). The remaining 7 bits of each byte in the wire format are taken
taken in-order from the integer's bitstring representation. If the in order from the integer's bitstring representation. If the
bitstring's length is not a multiple of 7, then the string is left- bitstring's length is not a multiple of 7, then the string is left-
padded with 0s. padded with 0s.
For example: For example:
o 1 (decimal) is represented by the bitstring "0000001" and encoded o 1 (decimal) is represented by the bitstring "0000001" and encoded
as the single byte 0x01 (in hexadecimal) as the single byte 0x01 (in hexadecimal)
o 128 is represented by the bitstring "10000001 00000000" and o 128 is represented by the bitstring "10000001 00000000" and
encoded as the bytes 0x81 followed by 0x00. encoded as the bytes 0x81 followed by 0x00.
skipping to change at page 8, line 11 skipping to change at page 8, line 11
order to not change the value of the number. Protocols using SDNVs order to not change the value of the number. Protocols using SDNVs
should consider situations where lost zero-padding may be should consider situations where lost zero-padding may be
problematic. problematic.
3. Basic Algorithms 3. Basic Algorithms
This section describes some simple algorithms for creating and This section describes some simple algorithms for creating and
parsing SDNV fields. These may not be the most efficient algorithms parsing SDNV fields. These may not be the most efficient algorithms
possible, however, they are easy to read, understand, and implement. possible, however, they are easy to read, understand, and implement.
Appendix A contains Python source code implementing the routines Appendix A contains Python source code implementing the routines
described here. Only SDNV's of the currently-used form are described here.
considered in this section.
3.1. Encoding Algorithm 3.1. Encoding Algorithm
There is a very simple algorithm for the encoding operation that There is a very simple algorithm for the encoding operation that
converts a non-negative integer (n, of length 1+floor(log_2 n) bits) converts a non-negative integer (value n, of length 1+floor(log_2 n)
into an SDNV. This algorithm takes n as its only argument and bits) into an SDNV. This algorithm takes n as its only argument and
returns a string of bytes: returns a string of bytes:
o (Initial Step) Set the return value to a byte sharing the least o (Initial Step) Set the return value to a byte sharing the least
significant 7 bits of n, and with 0 in the most significant bit, significant 7 bits of n, and with 0 in the most significant bit,
but do not return yet. Right shift n 7 bits and use this as the but do not return yet. Right shift n 7 bits and use this as the
new n value. If implemented using call-by-reference rather than new n value. If implemented using call-by-reference rather than
call-by-value, make a copy of n for local use at the start of the call-by-value, make a copy of n for local use at the start of the
function call. function call.
o (Recursion Step) If n == 0, return. Otherwise, take the byte o (Recursion Step) If n == 0, return. Otherwise, take the byte
0x80, and bitwise-or it with the 7 least significant bits left in 0x80, and bitwise-or it with the 7 least significant bits of n.
n. Set the return value to this result with the previous return Set the return value to this result with the previous return
string appended to it. Set n to itself shifted right 7 bits string appended to it. Shift n right 7 bits again. Repeat
again. Repeat Recursion Step. Recursion Step.
This encoding algorithm can easily be seen to have time complexity of This encoding algorithm can easily be seen to have time complexity of
O(log_2 n), since it takes a number of steps equal to ceil(n/7), and O(log_2 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_2 n) is no additional space beyond the size of the result (8/7 log_2 n) is
required. One aspect of this algorithm is that it assumes strings required. One aspect of this algorithm is that it assumes strings
can be efficiently appended to new bytes. One way to implement this 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 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. fill that buffer one byte at a time from the right end.
If, for some reason, an implementation requires an encoded SDNV to be If, for some reason, an implementation requires an encoded SDNV to be
skipping to change at page 9, line 22 skipping to change at page 9, line 21
under the pointer is a 1, move the pointer right one byte and repeat under the pointer is a 1, move the pointer right one byte and repeat
the Recursion Step, otherwise return the current value of the result. the Recursion Step, otherwise return the current value of the result.
This decoding algorithm takes no more additional space than what is 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. 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 The complication is that before the result can be left-shifted in the
Recursion Step, an implementation needs to first make sure that this Recursion Step, an implementation needs to first make sure that this
won't cause any bits to be lost, and re-allocate a larger piece of won't 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 memory for the result, if required. The pure time complexity is the
same as for the encoding algorithm given, but if re-allocation is same as for the encoding algorithm given, but if re-allocation is
needed due to the inability to predict the size of the result, in needed due to the inability to predict the size of the result,
reality decoding may be slower. decoding may be slower.
These decoding steps include removal of any leftmost zero-padding These decoding steps include removal of any leftmost zero-padding
that might be used by an encoder to create encodings of a certain that might be used by an encoder to create encodings of a certain
length. length.
4. Comparison to Alternatives 4. Comparison to Alternatives
This section compares three alternative ways of implementing the This section compares three alternative ways of implementing the
concept of SDNVs: (1) the TLV scheme commonly used in the Internet concept of SDNVs: (1) the TLV scheme commonly used in the Internet
family, and many other families of protocols, (2) the old style of 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 SDNVs (both the SDNV-8 and SDNV-16) defined in an early stage of
LTP's development [BRF04], and (3) the current SDNV format. LTP's development [BRF04], and (3) the current SDNV format.
The TLV method uses two fixed-length fields to hold the Type" and The TLV method uses two fixed-length fields to hold the Type and
Length elements that then imply the syntax and semantics of the Length elements that then imply the syntax and semantics of the Value
"value" element. This is only similar to an SDNV in that the value element. This is only similar to an SDNV in that the value element
element can grow or shrink within the bounds capable of being can grow or shrink within the bounds capable of being conveyed by the
conveyed by the Length field. Two fundamental differences between Length field. Two fundamental differences between TLVs and SDNVs are
TLVs and SDNVs are that through the Type element, TLVs also contain that through the Type element, TLVs also contain some notion of what
some notion of what their contents are semantically, while SDNVs are their contents are semantically, while SDNVs are simply generic non-
simply generic non-negative integers, and protocol engineers still negative integers, and protocol engineers still have to choose fixed
have to pick fixed-lengths for the Type and Length fields in the TLV field lengths for the Type and Length fields in the TLV format.
format.
Some protocols use TLVs where the value conveyed within the Length Some protocols use TLVs where the value conveyed within the Length
field needs to be decoded into the actual length of the Value field. field needs to be decoded into the actual length of the Value field.
This may be accomplished through simple multiplication, left- This may be accomplished through simple multiplication, left-
shifting, or a look-up table. In any case, this tactic limits the shifting, or a look-up table. In any case, this tactic limits the
granularity of the possible Value lengths, and can contribute some granularity of the possible Value lengths, and can contribute some
degree of bloat if Values do not fit neatly within the available degree of bloat if Values do not fit neatly within the available
decoded Lengths. decoded Lengths.
In the SDNV format originally used by LTP, parsing the first byte of 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 SDNV told an implementation how much space was required to hold
the contained value. There were two different types of SDNVs defined 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 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 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 32,767 in 2 bytes. Both formats could encode values requiring up to
N bytes in N+2 bytes, where N<127. The major difference between this N bytes in N+2 bytes, where N<127. The major difference between this
old SDNV format and the currently-used SDNV format is that the new old SDNV format and the current SDNV format is that the new format is
format is not as easily decoded as the old format was, but the new not as easily decoded as the old format was, but the new format also
format also has absolutely no limitation on its length. has absolutely no limitation on its length.
The advantage in ease of parsing the old format manifests itself in 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, 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 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 directly encoded and decoded, without shifting and masking bits as is
required in the new format. For these reasons, the old format required in the new format. For these reasons, the old format
requires less computational overhead to deal with, but is also very requires less computational overhead to deal with, but is also very
limited, in that it can only hold a 1024-bit number, at maximum. limited, in that it can only hold a 1024-bit number, at maximum.
Since according to IETF Best Current Practices, an asymmetric Since according to IETF Best Current Practices, an asymmetric
cryptography key needed to last for a long term requires using moduli cryptography key needed to last for a long term requires using moduli
of over 1228 bits [RFC3766], this could be seen as a severe of over 1228 bits [RFC3766], this could be seen as a severe
limitation of the old-style of SDNVs, which the currently-used style limitation of the old-style of SDNVs, which the currently-used style
does not suffer from. does not suffer from.
Table 1 compares the maximum values that can be encoded into SDNVs of 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 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 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 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 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 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 though, the current SDNV format is more compact, since it only
requires one-bit per byte of overhead, whereas the old format used a requires one bit per byte of overhead, whereas the old format used a
full byte. Thus, at 8 bytes, both schemes are equivalent in full byte. Thus, at 8 bytes, both schemes are equivalent in
efficiency since they both use 8 bits of overhead. Up to 129 bytes, 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 the old format is more compact than the current one, although after
this limit it becomes unusable. this limit it becomes unusable.
+-------+---------------+-------------+---------------+-------------+ +-------+---------------+-------------+---------------+-------------+
| Bytes | SDNV-8/16 | SDNV | SDNV-8/16 | SDNV | | Bytes | SDNV-8/16 | SDNV | SDNV-8/16 | SDNV |
| | Maximum Value | Maximum | Overhead Bits | Overhead | | | Maximum Value | Maximum | Overhead Bits | Overhead |
| | | Value | | Bits | | | | Value | | Bits |
+-------+---------------+-------------+---------------+-------------+ +-------+---------------+-------------+---------------+-------------+
skipping to change at page 13, line 7 skipping to change at page 13, line 7
In general, it seems like the most promising use of SDNVs may be to In general, it seems like the most promising use of SDNVs may be to
define the Length field of a TLV structure to be an SDNV whose value define the Length field of a TLV structure to be an SDNV whose value
is the length of the TLV's Value field. This leverages the strengths is the length of the TLV's Value field. This leverages the strengths
of the SDNV format and limits the effects of its weaknesses. of the SDNV format and limits the effects of its weaknesses.
Another aspect of comparison between SDNVs and alternatives using Another aspect of comparison between SDNVs and alternatives using
fixed-length fields is the result of errors in transmission. Bit- fixed-length fields is the result of errors in transmission. Bit-
errors in an SDNV can result in either errors in the decoded value, errors in an SDNV can result in either errors in the decoded value,
or parsing errors in subsequent fields of the protocol. In fixed- or parsing errors in subsequent fields of the protocol. In fixed-
length fields, bit-errors always result in errors to the decoded length fields, bit errors always result in errors to the decoded
value rather than parsing errors in subsequent fields. If the value rather than parsing errors in subsequent fields. If the
decoded values from either type of field encoding (SDNV or fixed- decoded values from either type of field encoding (SDNV or fixed-
length) are used as indexes, offsets, or lengths of further fields in length) are used as indexes, offsets, or lengths of further fields in
the protocol, similar failures result. the protocol, similar failures result.
5. Security Considerations 5. Security Considerations
The only security considerations with regards to SDNVs are that code The only security considerations with regards to SDNVs are that code
which parses SDNVs should have bounds-checking logic and be capable which parses SDNVs should have bounds-checking logic and be capable
of handling cases where an SDNV's value is beyond the code's ability of handling cases where an SDNV's value is beyond the code's ability
skipping to change at page 16, line 11 skipping to change at page 16, line 11
6. IANA Considerations 6. IANA Considerations
This document has no IANA considerations. This document has no IANA considerations.
7. Acknowledgements 7. Acknowledgements
Scott Burleigh, Manikantan Ramadas, Michael Demmer, Stephen Farrell, Scott Burleigh, Manikantan Ramadas, Michael Demmer, Stephen Farrell,
and other members of the IRTF DTN Research Group contributed to the and other members of the IRTF DTN Research Group contributed to the
development and usage of SDNVs in DTN protocols. George Jones and development and usage of SDNVs in DTN protocols. George Jones and
Keith Scott from Mitre, Lloyd Wood, Gerardo Izquierdo, Joel Halpern, Keith Scott from Mitre, Lloyd Wood, Gerardo Izquierdo, Joel Halpern,
and Peter TB Brett also contributed useful comments on and criticisms Peter TB Brett, Kevin Fall, and Elwyn Davies also contributed useful
of this document. DTNRG last call comments on the draft were sent to comments on and criticisms of this document. DTNRG last call
the mailing list by Lloyd Wood, Will Ivancic, Jim Wyllie, William comments on the draft were sent to the mailing list by Lloyd Wood,
Edwards, Hans Kruse, Janico Greifenberg, Teemu Karkkainen, Stephen Will Ivancic, Jim Wyllie, William Edwards, Hans Kruse, Janico
Farrell, and Scott Burleigh. Greifenberg, Teemu Karkkainen, Stephen Farrell, and Scott Burleigh.
Work on this document was performed at NASA's Glenn Research Center, Work on this document was performed at NASA's Glenn Research Center,
in support of the NASA Space Communications Architecture Working in support of the NASA Space Communications Architecture Working
Group (SCAWG), NASA's Earth Science Technology Office (ESTO), and the Group (SCAWG), NASA's Earth Science Technology Office (ESTO), and the
FAA/Eurocontrol Future Communications Study (FCS). FAA/Eurocontrol Future Communications Study (FCS) in the 2005-2007
timeframe, while the editor was an employee of Verizon Federal
Network Systems.
8. Informative References 8. Informative References
[ASN1] ITU-T Rec. X.680, "Abstract Syntax Notation One (ASN.1). [ASN1] ITU-T Rec. X.680, "Abstract Syntax Notation One (ASN.1).
Specification of Basic Notation", ISO/IEC 8824-1:2002, Specification of Basic Notation", ISO/IEC 8824-1:2002,
2002. 2002.
[ASN1-BER] [ASN1-BER]
ITU-T Rec. X.690, "Abstract Syntax Notation One (ASN.1). ITU-T Rec. X.690, "Abstract Syntax Notation One (ASN.1).
Encoding Rules: Specification of Basic Encoding Rules Encoding Rules: Specification of Basic Encoding Rules
skipping to change at page 17, line 25 skipping to change at page 17, line 25
Encoding Rules (DER)", ISO/IEC 8825-1:2002, 2002. Encoding Rules (DER)", ISO/IEC 8825-1:2002, 2002.
[BRF04] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider [BRF04] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider
Transmission Protocol", Transmission Protocol",
draft-irtf-dtnrg-ltp-00 (replaced), May 2004. draft-irtf-dtnrg-ltp-00 (replaced), May 2004.
[Hain05] Hain, T., "A Pragmatic Report on IPv4 Address Space [Hain05] Hain, T., "A Pragmatic Report on IPv4 Address Space
Consumption", Internet Protocol Journal Vol. 8, No. 3, Consumption", Internet Protocol Journal Vol. 8, No. 3,
September 2005. September 2005.
[IEN21] Cerf, V. and J. Postel, "Specification of Internetwork
Transmission Control Program: TCP Version 3", Internet
Experimental Note 21, January 1978.
[RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791,
September 1981. September 1981.
[RFC0793] Postel, J., "Transmission Control Protocol", STD 7, [RFC0793] Postel, J., "Transmission Control Protocol", STD 7,
RFC 793, September 1981. RFC 793, September 1981.
[RFC1323] Jacobson, V., Braden, B., and D. Borman, "TCP Extensions [RFC1323] Jacobson, V., Braden, B., and D. Borman, "TCP Extensions
for High Performance", RFC 1323, May 1992. for High Performance", RFC 1323, May 1992.
[RFC2993] Hain, T., "Architectural Implications of NAT", RFC 2993, [RFC2993] Hain, T., "Architectural Implications of NAT", RFC 2993,
skipping to change at page 21, line 8 skipping to change at page 21, line 8
if sdnv_encode(tp[0]) != tp[1]: if sdnv_encode(tp[0]) != tp[1]:
print "sdnv_encode fails on input %s" % hex(tp[0]) print "sdnv_encode fails on input %s" % hex(tp[0])
# test decoding function # test decoding function
if sdnv_decode(tp[1])[0] != tp[0]: if sdnv_decode(tp[1])[0] != tp[0]:
print "sdnv_decode fails on input %s, giving %s" % \ print "sdnv_decode fails on input %s, giving %s" % \
(hex(tp[0]), sdnv_decode(tp[1])) (hex(tp[0]), sdnv_decode(tp[1]))
Author's Address Author's Address
Wesley M. Eddy Wesley M. Eddy
Verizon Federal Network Systems MTI Systems
NASA Glenn Research Center NASA Glenn Research Center
21000 Brookpark Rd MS 500-ASRC; 21000 Brookpark Rd
Cleveland, OH 44135 Cleveland, OH 44135
Phone: 216-433-6682 Phone: 216-433-6682
Email: weddy@grc.nasa.gov Email: wes@mti-systems.com
 End of changes. 32 change blocks. 
98 lines changed or deleted 116 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/