idnits 2.17.00 (12 Aug 2021) /tmp/idnits3871/draft-irtf-dtnrg-sdnv-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (January 26, 2011) is 4132 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 737 -- Looks like a reference, but probably isn't: '1' on line 737 == Outdated reference: draft-irtf-dtnrg-ltp has been published as RFC 5326 -- Obsolete informational reference (is this intentional?): RFC 1323 (Obsoleted by RFC 7323) Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group W. Eddy 3 Internet-Draft MTI Systems 4 Intended status: Informational E. Davies 5 Expires: July 30, 2011 Folly Consulting 6 January 26, 2011 8 Using Self-Delimiting Numeric Values in Protocols 9 draft-irtf-dtnrg-sdnv-08 11 Abstract 13 Self-Delimiting Numeric Values (SDNVs) have recently been introduced 14 as a field type in proposed Delay-Tolerant Networking protocols. 15 SDNVs encode an arbitrary-length non-negative integer or arbitrary- 16 length bit-string with minimum overhead. They are intended to 17 provide protocol flexibility without sacrificing economy, and to 18 assist in future-proofing protocols under development. This document 19 describes formats and algorithms for SDNV encoding and decoding, 20 along with notes on implementation and usage. This document is a 21 product of the Delay Tolerant Networking Research Group and has been 22 reviewed by that group. No objections to its publication as an RFC 23 were raised. 25 Status of this Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at http://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on July 30, 2011. 42 Copyright Notice 44 Copyright (c) 2011 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (http://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 60 1.1. Problems with Fixed Value Fields . . . . . . . . . . . . . 3 61 1.2. SDNVs for DTN Protocols . . . . . . . . . . . . . . . . . 4 62 1.3. SDNV Usage . . . . . . . . . . . . . . . . . . . . . . . . 5 63 2. Definition of SDNVs . . . . . . . . . . . . . . . . . . . . . 7 64 3. Basic Algorithms . . . . . . . . . . . . . . . . . . . . . . . 9 65 3.1. Encoding Algorithm . . . . . . . . . . . . . . . . . . . . 9 66 3.2. Decoding Algorithm . . . . . . . . . . . . . . . . . . . . 9 67 3.3. Limitations of Implementations . . . . . . . . . . . . . . 10 68 4. Comparison to Alternatives . . . . . . . . . . . . . . . . . . 11 69 5. Security Considerations . . . . . . . . . . . . . . . . . . . 15 70 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 71 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 17 72 8. Informative References . . . . . . . . . . . . . . . . . . . . 18 73 Appendix A. SNDV Python Source Code . . . . . . . . . . . . . . . 20 74 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 76 1. Introduction 78 This document is a product of the Internet Research Task Force (IRTF) 79 Delay-Tolerant Networking (DTN) Research Group (DTNRG). The document 80 has received review and support within the DTNRG, as discussed in the 81 Acknowledgements section of this document. 83 This document begins by describing the drawbacks of using fixed-width 84 protocol fields. It then provides some background on the Self- 85 Delimiting Numeric Values (SDNVs) proposed for use in DTN protocols, 86 and motivates their potential applicability in other networking 87 protocols. One example of SDNVs being used outside of the DTN 88 protocols is in Hixie's Web Socket protocol 89 [I-D.hixie-thewebsocketprotocol], which includes a binary frame 90 length indicator field identical to an SDNV. The DTNRG has created 91 SDNVs to meet the challenges it attempts to solve, and it has been 92 noted that SDNVs closely resemble certain constructs within ASN.1 and 93 even older ITU protocols, so the problems are not new or unique to 94 DTN. SDNVs focus strictly on numeric values or bitstrings, while 95 other mechanisms have been developed for encoding more complex data 96 structures, such as ASN.1 encoding rules, and Haverty's MSDTP 97 [RFC0713]. Because of this focus, SDNVs are can be quickly 98 implemented with only a small amount of code. 100 SDNVs are tersely defined in both the bundle protocol [RFC5050] and 101 LTP [RFC5326] specifications, due to the flow of document production 102 in the DTNRG. This document clarifies and further explains the 103 motivations and engineering decisions behind SDNVs. 105 1.1. Problems with Fixed Value Fields 107 Protocol designers commonly face an optimization problem in 108 determining the proper size for header fields. There is a strong 109 desire to keep fields as small as possible, in order to reduce the 110 protocol's overhead, and also allow for fast processing. Since 111 protocols can be used many years (even decades) after they are 112 designed, and networking technology has tended to change rapidly, it 113 is not uncommon for the use, deployment, or performance of a 114 particular protocol to be limited or infringed upon by the length of 115 some header field being too short. Two well-known examples of this 116 phenomenon are the TCP advertised receive window, and the IPv4 117 address length. 119 TCP segments contain an advertised receive window field that is fixed 120 at 16 bits [RFC0793], encoding a maximum value of around 65 121 kilobytes. The purpose of this value is to provide flow control, by 122 allowing a receiver to specify how many sent bytes its peer can have 123 outstanding (unacknowledged) at any time, thus allowing the receiver 124 to limit its buffer size. As network speeds have grown by several 125 orders of magnitude since TCP's inception, the combination of the 65 126 kilobyte maximum advertised window and long round-trip times 127 prevented TCP senders from being able to achieve the high throughput 128 that the underlying network supported. This limitation was remedied 129 through the use of the Window Scale option [RFC1323], which provides 130 a multiplier for the advertised window field. However, the Window 131 Scale multiplier is fixed for the duration of the connection, 132 requires support from each end of a TCP connection, and limits the 133 precision of the advertised receive window, so this is certainly a 134 less-than-ideal solution. Because of the field width limit in the 135 original design however, the Window Scale is necessary for TCP to 136 reach high sending rates. 138 An IPv4 address is fixed at 32 bits [RFC0791] (as a historical note, 139 an early version of the IP header format specification in [IEN21] 140 used variable-length addresses in multiples of 8-bits up to 120- 141 bits). Due to the way that subnetting and assignment of address 142 blocks was performed, the number of IPv4 addresses has been seen as a 143 limit to the growth of the Internet [Hain05]. Two divergent paths to 144 solve this problem have been the use of Network Address Translators 145 (NATs) and the development of IPv6. NATs have caused a number of 146 other issues and problems [RFC2993], leading to increased complexity 147 and fragility, as well as forcing workarounds to be engineered for 148 many other protocols to function within a NATed environment. The 149 IPv6 solution's transitional work has been underway for several 150 years, but has still only just begun to have visible impact on the 151 global Internet. 153 Of course, in both the case of the TCP receive window and IPv4 154 address length, the field size chosen by the designers seemed like a 155 good idea at the time. The fields were more than big enough for the 156 originally perceived usage of the protocols, and yet were small 157 enough to allow the headers to remain compact and relatively easy and 158 efficient to parse on machines of the time. The fixed sizes that 159 were defined represented a trade off between the scalability of the 160 protocol versus the overhead and efficiency of processing. In both 161 cases, these engineering decisions turned out to be painfully 162 restrictive in the longer term. 164 1.2. SDNVs for DTN Protocols 166 In specifications for the DTN Bundle Protocol (BP) [RFC5050] and 167 Licklider Transmission Protocol (LTP) [RFC5326], SDNVs have been used 168 for several fields including identifiers, payload/header lengths, and 169 serial (sequence) numbers. SDNVs were developed for use in these 170 types of fields, to avoid sending more bytes than needed, as well as 171 avoiding fixed sizes that may not end up being appropriate. For 172 example, since LTP is intended primarily for use in long-delay 173 interplanetary communications [RFC5325], where links may be fairly 174 low in capacity, it is desirable to avoid the header overhead of 175 routinely sending a 64-bit field where a 16-bit field would suffice. 176 Since many of the nodes implementing LTP are expected to be beyond 177 the current range of human spaceflight, upgrading their on-board LTP 178 implementations to use longer values if the defined fields are found 179 to be too short would also be problematic. Furthermore, extensions 180 similar in mechanism to TCP's Window Scale option are unsuitable for 181 use in DTN protocols since, due to high delays, DTN protocols must 182 avoid handshaking and configuration parameter negotiation to the 183 greatest extent possible. All of these reasons make the choice of 184 SDNVs for use in DTN protocols attractive. 186 1.3. SDNV Usage 188 In short, an SDNV is simply a way of representing non-negative 189 integers (both positive integers of arbitrary magnitude and 0), 190 without expending much unnecessary space. This definition allows 191 SDNVs to represent many common protocol header fields, such as: 193 o Random identification fields as used in the IPsec Security 194 Parameters Index or in IP headers for fragment reassembly (Note: 195 the 16-bit IP ID field for fragment reassembly was recently found 196 to be too short in some environments [RFC4963]), 198 o Sequence numbers as in TCP or SCTP, 200 o Values used in cryptographic algorithms such as RSA keys, Diffie- 201 Hellman key-agreement, or coordinates of points on elliptic 202 curves. 204 o Message lengths as used in file transfer protocols. 206 o Nonces and cookies. 208 As any bit-field can be interpreted as an unsigned integer, SDNVs can 209 also encode arbitrary-length bit-fields, including bit-fields 210 representing signed integers or other data types; however, this 211 document assumes SDNV encoding and decoding in terms of unsigned 212 integers. Implementations may differ in the interface that they 213 provide to SDNV encoding and decoding functions, in terms of whether 214 the values are numeric, bit-fields, etc.; this detail does not alter 215 the representation or algorithms described in this document. 217 The use of SDNVs rather than fixed length fields gives protocol 218 designers the ability to ameliorate the consequences of making 219 difficult-to-reverse field-sizing decisions, as the SDNV format grows 220 and shrinks depending on the particular value encoded. SDNVs do not 221 necessarily provide optimal encodings for values of any particular 222 length, however they allow protocol designers to avoid potential 223 blunders in assigning fixed lengths, and remove the complexity 224 involved with either negotiating field lengths or constructing 225 protocol extensions. However, if SDNVs are used to encode bit- 226 fields, it is essential that the sender and receiver have a 227 consistent interpretation of the decoded value. This is discussed 228 further in Section 2. 230 To our knowledge, at this time, no IETF transport or network-layer 231 protocol designed for use outside of the DTN domain has proposed to 232 use SDNVs; however there is no inherent reason not to use SDNVs more 233 broadly in the future. The two examples cited here, of fields that 234 have proven too small in general Internet protocols, are only a small 235 sampling of the much larger set of similar instances that the authors 236 can think of. Outside the Internet protocols, within ASN.1 and 237 previous ITU protocols, constructs very similar to SDNVs have been 238 used for many years due to engineering concerns very similar to those 239 facing the DTNRG. 241 Many protocols use a Type-Length-Value method for encoding variable 242 length fields (e.g. TCP's options format, or many of the fields in 243 IKEv2). An SDNV is equivalent to combining the length and value 244 portions of this type of field, with the overhead of the length 245 portion amortized out over the bytes of the value. The penalty paid 246 for this in an SDNV may be several extra bytes for long values (e.g. 247 1024 bit RSA keys). See Section 4 for further discussion and a 248 comparison. 250 As is shown in later sections, for large values, the current SDNV 251 scheme is fairly inefficient in terms of space (1/8 of the bits are 252 overhead) and not particularly easy to encode/decode in comparison to 253 alternatives. The best use of SDNVs may often be to define the 254 Length field of a TLV structure to be an SDNV whose value is the 255 length of the TLV's Value field. In this way, one can avoid forcing 256 large numbers from being directly encoded as an SDNV, yet retain the 257 extensibility that using SDNVs grants. 259 2. Definition of SDNVs 261 Early in the work of the DTNRG, it was agreed that the properties of 262 an SDNV were useful for DTN protocols. The exact SDNV format used by 263 the DTNRG evolved somewhat over time before the publication of the 264 initial RFCs on LTP and the BP. An earlier version bore resemblance 265 to the ASN.1 [ASN1] Basic Encoding Rules (BER) [ASN1-BER] for lengths 266 (Section 8.1.3 of X.690). The current SDNV format is the one used by 267 ASN.1 BER for encoding tag identifiers greater than or equal to 31 268 (Section 8.1.2.4.2 of X.690). A comparison between the current SDNV 269 format and the early SDNV format is made in Section 4. 271 The format currently used is very simple. Before encoding, an 272 integer is represented as a left-to-right bitstring beginning with 273 its most significant bit, and ending with its least significant bit. 274 If the bitstring's length is not a multiple of 7, then the string is 275 left-padded with zeros. When transmitted, the bits are encoded into 276 a series of bytes. The low-order 7 bits of each byte in the encoded 277 format are taken left-to-right from the integer's bitstring 278 representation. The most significant bit of each byte specifies 279 whether it is the final byte of the encoded value (when it holds a 280 0), or not (when it holds a 1). 282 For example: 284 o 1 (decimal) is represented by the bitstring "0000001" and encoded 285 as the single byte 0x01 (in hexadecimal) 287 o 128 is represented by the bitstring "10000001 00000000" and 288 encoded as the bytes 0x81 followed by 0x00. 290 o Other values can be found in the test vectors of the source code 291 in Appendix A 293 To be perfectly clear, and avoid potential interoperability issues 294 (as have occurred with ASN.1 BER time values), we explicitly state 295 two considerations regarding zero-padding. (1) When encoding SDNVs, 296 any leading (most significant) zero bits in the input number might be 297 discarded by the SDNV encoder. Protocols that use SDNVs should not 298 rely on leading-zeros being retained after encoding and decoding 299 operations. (2) When decoding SDNVs, the relevant number of leading 300 zeros required to pad up to a machine word or other natural data unit 301 might be added. These are put in the most-significant positions in 302 order to not change the value of the number. Protocols using SDNVs 303 should consider situations where lost zero-padding may be 304 problematic. 306 The issues of zero-padding are particularly relevant where an SDNV is 307 being used to represent a bit-field to be transmitted by a protocol. 308 The specification of the protocol and any associated IANA registry 309 should specify the allocation and usage of bit positions within the 310 unencoded field. Unassigned and reserved bits in the unencoded field 311 will be treated as zeros by the SDNV encoding prior to transmission. 312 Assuming the bit positions are numbered starting from 0 at the least 313 significant bit position in the integer representation, then if 314 higher numbered positions in the field contain all zeros, the 315 encoding process may not transmit these bits explicitly (e.g., if all 316 the bit positions numbered 7 or higher are zeros then the transmitted 317 SDNV can consist of just one octet). On reception the decoding 318 process will treat any untransmitted higher numbered bits as zeros. 319 To ensure correct operation of the protocol, the sender and receiver 320 must have a consistent interpretation of the width of the bit-field. 321 This can be achieved in various ways: 323 o the bit-field width is implicitly defined by the version of the 324 protocol in use in the sender and receiver, 326 o sending the width of the bit-field explicitly in a separate item, 328 o the higher numbered bits can be safely ignored by the receiver 329 (e.g., because they represent optimizations), or 331 o marking the highest numbered bit by prepending a 1 bit to the bit- 332 field. 334 The protocol specification must record how the consistent 335 interpretation is achieved. 337 The SDNV encoding technique is also known as Variable Byte Encoding 338 (see Section 5.3.1 of [Manning09]) and is equivalent to Base-128 339 Elias Gamma Encoding (see Section 5.3.2 of [Manning09] and Section 340 3.5 of [Sayood02]). However the primary motivation for SDNVs is to 341 provide an extensible protocol framework rather than optimal data 342 compression which is the motivation behind the other uses of the 343 technique. [Manning09] points out that the key feature of this 344 encoding is that it is 'prefix free' meaning that no code is a prefix 345 of any other, which an alternative way of expressing the self- 346 delimiting property 348 3. Basic Algorithms 350 This section describes some simple algorithms for creating and 351 parsing SDNV fields. These may not be the most efficient algorithms 352 possible, however, they are easy to read, understand, and implement. 353 Appendix A contains Python source code implementing the routines 354 described here. The algorithms presented here are convenient for 355 converting between an internal data block and serialized data stream 356 associated with a transmission device. Other approaches are possible 357 with different efficiencies and trade-offs. 359 3.1. Encoding Algorithm 361 There is a very simple algorithm for the encoding operation that 362 converts a non-negative integer (value n, of length 1+floor(log n) 363 bits) into an SDNV. This algorithm takes n as its only argument and 364 returns a string of bytes: 366 o (Initial Step) Set a variable X to a byte sharing the least 367 significant 7 bits of n, and with 0 in the most significant bit, 368 and a variable Y to n, right-shifted by 7 bits. 370 o (Recursion Step) If Y == 0, return X. Otherwise, set Z to the 371 bitwise-or of 0x80 with the 7 least significant bits of Y, and 372 append Z to X. Right-shift Y by 7 bits and repeat the Recursion 373 Step. 375 This encoding algorithm has time complexity of O(log n), since it 376 takes a number of steps equal to ceil(n/7), and no additional space 377 beyond the size of the result (8/7 log n) is required. One aspect of 378 this algorithm is that it assumes strings can be efficiently appended 379 to new bytes. One way to implement this is to allocate a buffer for 380 the expected length of the result and fill that buffer one byte at a 381 time from the right end. 383 If, for some reason, an implementation requires an encoded SDNV to be 384 some specific length (possibly related to a machine word), any 385 leftmost zero-padding included needs to properly set the high-order 386 bit in each byte of padding. 388 3.2. Decoding Algorithm 390 Decoding SDNVs is a more difficult operation than encoding them, due 391 to the fact that no bound on the resulting value is known until the 392 SDNV is parsed, at which point the value itself is already known. 393 This means that if space is allocated for decoding the value of an 394 SDNV into, it is never known whether this space will be overflowed 395 until it is 7 bits away from happening. 397 (Initial Step) Set the result to 0. Set an index to the first byte 398 of the encoded SDNV. 400 (Recursion Step) Shift the result left 7 bits. Add the low-order 7 401 bits of the value at the index to the result. If the high-order bit 402 under the pointer is a 1, advance the index by one byte within the 403 encoded SDNV and repeat the Recursion Step, otherwise return the 404 current value of the result. 406 This decoding algorithm takes no more additional space than what is 407 required for the result (7/8 the length of the SDNV) and the pointer. 408 The complication is that before the result can be left-shifted in the 409 Recursion Step, an implementation needs to first make sure that this 410 won't cause any bits to be lost, and re-allocate a larger piece of 411 memory for the result, if required. The pure time complexity is the 412 same as for the encoding algorithm given, but if re-allocation is 413 needed due to the inability to predict the size of the result, 414 decoding may be slower. 416 These decoding steps include removal of any leftmost zero-padding 417 that might be used by an encoder to create encodings of a certain 418 length. 420 3.3. Limitations of Implementations 422 Because of efficiency considerations or convenience of internal 423 representation of decoded integers, implementations may choose to 424 limit the number of bits in SDNVs that they will handle. To avoid 425 interoperability problems any protocol that uses SDNVs must specify 426 the largest number of bits in an SDNV that an implementation of that 427 protocol is expected to handle. 429 For example Section 4.1 of [RFC5050] specifies that implementations 430 of the DTN Bundle Protocol are not required to handle SDNVs with more 431 than 64 bits in their unencoded value. Accordingly integer values 432 transmitted in SDNVs have an upper limit and SDNV encoded flag fields 433 must be limited to 64 bit positions in any future revisions of the 434 protocol unless the restriction is altered. 436 4. Comparison to Alternatives 438 This section compares three alternative ways of implementing the 439 concept of SDNVs: (1) the TLV scheme commonly used in the Internet 440 family, and many other families of protocols, (2) the old style of 441 SDNVs (both the SDNV-8 and SDNV-16) defined in an early stage of 442 LTP's development [BRF04], and (3) the current SDNV format. 444 The TLV method uses two fixed-length fields to hold the Type and 445 Length elements that then imply the syntax and semantics of the Value 446 element. This is only similar to an SDNV in that the value element 447 can grow or shrink within the bounds capable of being conveyed by the 448 Length field. Two fundamental differences between TLVs and SDNVs are 449 that through the Type element, TLVs also contain some notion of what 450 their contents are semantically, while SDNVs are simply generic non- 451 negative integers, and protocol engineers still have to choose fixed 452 field lengths for the Type and Length fields in the TLV format. 454 Some protocols use TLVs where the value conveyed within the Length 455 field needs to be decoded into the actual length of the Value field. 456 This may be accomplished through simple multiplication, left- 457 shifting, or a look-up table. In any case, this tactic limits the 458 granularity of the possible Value lengths, and can contribute some 459 degree of bloat if Values do not fit neatly within the available 460 decoded Lengths. 462 In the SDNV format originally used by LTP, parsing the first byte of 463 the SDNV told an implementation how much space was required to hold 464 the contained value. There were two different types of SDNVs defined 465 for different ranges of use. The SDNV-8 type could hold values up to 466 127 in a single byte, while the SDNV-16 type could hold values up to 467 32,767 in 2 bytes. Both formats could encode values requiring up to 468 N bytes in N+2 bytes, where N<127. The major difference between this 469 old SDNV format and the current SDNV format is that the new format is 470 not as easily decoded as the old format was, but the new format also 471 has absolutely no limitation on its length. 473 The advantage in ease of parsing the old format manifests itself in 474 two aspects: (1) the size of the value is determinable ahead of time, 475 in a way equivalent to parsing a TLV, and (2) the actual value is 476 directly encoded and decoded, without shifting and masking bits as is 477 required in the new format. For these reasons, the old format 478 requires less computational overhead to deal with, but is also very 479 limited, in that it can only hold a 1024-bit number, at maximum. 480 Since according to IETF Best Current Practices, an asymmetric 481 cryptography key needed to last for a long term requires using moduli 482 of over 1228 bits [RFC3766], this could be seen as a severe 483 limitation of the old-style of SDNVs, which the currently-used style 484 does not suffer from. 486 Table 1 compares the maximum values that can be encoded into SDNVs of 487 various lengths using the old SDNV-8/16 method and the current SDNV 488 method. The only place in this table where SDNV-16 is used rather 489 than SDNV-8 is in the 2-byte row. Starting with a single byte, the 490 two methods are equivalent, but when using 2 bytes, the old method is 491 a more compact encoding by one bit. From 3 to 7 bytes of length 492 though, the current SDNV format is more compact, since it only 493 requires one bit per byte of overhead, whereas the old format used a 494 full byte. Thus, at 8 bytes, both schemes are equivalent in 495 efficiency since they both use 8 bits of overhead. Up to 129 bytes, 496 the old format is more compact than the current one, although after 497 this limit it becomes unusable. 499 +-------+---------------+-------------+---------------+-------------+ 500 | Bytes | SDNV-8/16 | SDNV | SDNV-8/16 | SDNV | 501 | | Maximum Value | Maximum | Overhead Bits | Overhead | 502 | | | Value | | Bits | 503 +-------+---------------+-------------+---------------+-------------+ 504 | 1 | 127 | 127 | 1 | 1 | 505 | | | | | | 506 | 2 | 32,767 | 16,383 | 1 | 2 | 507 | | | | | | 508 | 3 | 65,535 | 2,097,151 | 8 | 3 | 509 | | | | | | 510 | 4 | 2^24 - 1 | 2^28 - 1 | 8 | 4 | 511 | | | | | | 512 | 5 | 2^32 - 1 | 2^35 - 1 | 8 | 5 | 513 | | | | | | 514 | 6 | 2^40 - 1 | 2^42 - 1 | 8 | 6 | 515 | | | | | | 516 | 7 | 2^48 - 1 | 2^49 - 1 | 8 | 7 | 517 | | | | | | 518 | 8 | 2^56 - 1 | 2^56 - 1 | 8 | 8 | 519 | | | | | | 520 | 9 | 2^64 - 1 | 2^63 - 1 | 8 | 9 | 521 | | | | | | 522 | 10 | 2^72 - 1 | 2^70 - 1 | 8 | 10 | 523 | | | | | | 524 | 16 | 2^120 - 1 | 2^112 - 1 | 8 | 16 | 525 | | | | | | 526 | 32 | 2^248 - 1 | 2^224 - 1 | 8 | 32 | 527 | | | | | | 528 | 64 | 2^504 - 1 | 2^448 - 1 | 8 | 64 | 529 | | | | | | 530 | 128 | 2^1016 - 1 | 2^896 - 1 | 8 | 128 | 531 | | | | | | 532 | 129 | 2^1024 - 1 | 2^903 - 1 | 8 | 129 | 533 | | | | | | 534 | 130 | N/A | 2^910 - 1 | N/A | 130 | 535 | | | | | | 536 | 256 | N/A | 2^1792 - 1 | N/A | 256 | 537 +-------+---------------+-------------+---------------+-------------+ 539 Table 1 541 In general, it seems like the most promising use of SDNVs may be to 542 define the Length field of a TLV structure to be an SDNV whose value 543 is the length of the TLV's Value field. As previously discussed, 544 this leverages the strengths of the SDNV format and limits the 545 effects of its weaknesses. 547 Another aspect of comparison between SDNVs and alternatives using 548 fixed-length fields is the result of errors in transmission. Bit- 549 errors in an SDNV can result in either errors in the decoded value, 550 or parsing errors in subsequent fields of the protocol. In fixed- 551 length fields, bit errors always result in errors to the decoded 552 value rather than parsing errors in subsequent fields. If the 553 decoded values from either type of field encoding (SDNV or fixed- 554 length) are used as indexes, offsets, or lengths of further fields in 555 the protocol, similar failures result. 557 5. Security Considerations 559 The only security considerations with regards to SDNVs are that code 560 which parses SDNVs should have bounds-checking logic and be capable 561 of handling cases where an SDNV's value is beyond the code's ability 562 to parse. These precautions can prevent potential exploits involving 563 SDNV decoding routines. 565 Stephen Farrell noted that very early definitions of SDNVs also 566 allowed negative integers. This was considered a potential security 567 hole, since it could expose implementations to underflow attacks 568 during SDNV decoding. There is a precedent in that many existing TLV 569 decoders map the Length field to a signed integer and are vulnerable 570 in this way. An SDNV decoder should be based on unsigned types and 571 not have this issue. 573 6. IANA Considerations 575 This document has no IANA considerations. 577 7. Acknowledgements 579 Scott Burleigh, Manikantan Ramadas, Michael Demmer, Stephen Farrell, 580 and other members of the IRTF DTN Research Group contributed to the 581 development and usage of SDNVs in DTN protocols. George Jones and 582 Keith Scott from Mitre, Lloyd Wood, Gerardo Izquierdo, Joel Halpern, 583 Peter TB Brett, Kevin Fall, and Elwyn Davies also contributed useful 584 comments on and criticisms of this document. DTNRG last call 585 comments on the draft were sent to the mailing list by Lloyd Wood, 586 Will Ivancic, Jim Wyllie, William Edwards, Hans Kruse, Janico 587 Greifenberg, Teemu Karkkainen, Stephen Farrell, and Scott Burleigh. 588 Further constructive comments were incorporated from Dave Crocker, 589 Lachlan Andrew and Michael Welzl. 591 Work on this document was performed at NASA's Glenn Research Center, 592 in support of the NASA Space Communications Architecture Working 593 Group (SCAWG), NASA's Earth Science Technology Office (ESTO), and the 594 FAA/Eurocontrol Future Communications Study (FCS) in the 2005-2007 595 time frame, while the editor was an employee of Verizon Federal 596 Network Systems. 598 8. Informative References 600 [ASN1] ITU-T Rec. X.680, "Abstract Syntax Notation One (ASN.1). 601 Specification of Basic Notation", ISO/IEC 8824-1:2002, 602 2002. 604 [ASN1-BER] 605 ITU-T Rec. X.690, "Abstract Syntax Notation One (ASN.1). 606 Encoding Rules: Specification of Basic Encoding Rules 607 (BER), Canonical Encoding Rules (CER) and Distinguished 608 Encoding Rules (DER)", ISO/IEC 8825-1:2002, 2002. 610 [BRF04] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider 611 Transmission Protocol", 612 draft-irtf-dtnrg-ltp-00 (replaced), May 2004. 614 [Hain05] Hain, T., "A Pragmatic Report on IPv4 Address Space 615 Consumption", Internet Protocol Journal Vol. 8, No. 3, 616 September 2005. 618 [I-D.hixie-thewebsocketprotocol] 619 Hickson, I., "The WebSocket protocol", 620 draft-hixie-thewebsocketprotocol-76 (work in progress), 621 May 2010. 623 [IEN21] Cerf, V. and J. Postel, "Specification of Internetwork 624 Transmission Control Program: TCP Version 3", Internet 625 Experimental Note 21, January 1978. 627 [Manning09] 628 Manning, c., Raghavan, P., and H. Schuetze, "Introduction 629 to Information Retrieval", Cambridge University 630 Press ISBN-13: 978-0521865715, 2009, 631 . 633 [RFC0713] Haverty, J., "MSDTP-Message Services Data Transmission 634 Protocol", RFC 713, April 1976. 636 [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, 637 September 1981. 639 [RFC0793] Postel, J., "Transmission Control Protocol", STD 7, 640 RFC 793, September 1981. 642 [RFC1323] Jacobson, V., Braden, B., and D. Borman, "TCP Extensions 643 for High Performance", RFC 1323, May 1992. 645 [RFC2993] Hain, T., "Architectural Implications of NAT", RFC 2993, 646 November 2000. 648 [RFC3766] Orman, H. and P. Hoffman, "Determining Strengths For 649 Public Keys Used For Exchanging Symmetric Keys", BCP 86, 650 RFC 3766, April 2004. 652 [RFC4963] Heffner, J., Mathis, M., and B. Chandler, "IPv4 Reassembly 653 Errors at High Data Rates", RFC 4963, July 2007. 655 [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol 656 Specification", RFC 5050, November 2007. 658 [RFC5325] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider 659 Transmission Protocol - Motivation", RFC 5325, 660 September 2008. 662 [RFC5326] Ramadas, M., Burleigh, S., and S. Farrell, "Licklider 663 Transmission Protocol - Specification", RFC 5326, 664 September 2008. 666 [Sayood02] 667 Sayood, K., "Lossless Data Compression", Academic 668 Press ISBN-13: 978-0126208610, December 2002, 669 . 671 Appendix A. SNDV Python Source Code 673 # sdnv_decode() takes a string argument (s), which is assumed to be 674 # an SDNV, and optionally a number (slen) for the maximum number of 675 # bytes to parse from the string. The function returns a pair of 676 # the non-negative integer n that is the numeric value encoded in 677 # the SDNV, and integer that is the distance parsed into the input 678 # string. If the slen argument is not given (or is not a non-zero 679 # number) then, s is parsed up to the first byte whose high-order 680 # bit is 0 -- the length of the SDNV portion of s does not have to 681 # be pre-computed by calling code. If the slen argument is given 682 # as a non-zero value, then slen bytes of s are parsed. The value 683 # for n of -1 is returned for any type of parsing error. 684 # 685 # NOTE: In python, integers can be of arbitrary size. In other 686 # languages, such as C, SDNV-parsing routines should take 687 # precautions to avoid overflow (e.g. by using the Gnu MP library, 688 # or similar). 689 # 690 def sdnv_decode(s, slen=0): 691 n = long(0) 692 for i in range(0, len(s)): 693 v = ord(s[i]) 694 n = n<<7 695 n = n + (v & 0x7F) 696 if v>>7 == 0: 697 slen = i+1 698 break 699 elif i == len(s)-1 or (slen != 0 and i > slen): 700 n = -1 # reached end of input without seeing end of SDNV 701 return (n, slen) 703 # sdnv_encode() returns the SDNV-encoded string that represents n. 704 # An empty string is returned if n is not a non-negative integer 705 def sdnv_encode(n): 706 r = "" 707 # validate input 708 if n >= 0 and (type(n) in [type(int(1)), type(long(1))]): 709 flag = 0 710 done = False 711 while not done: 712 # encode lowest 7 bits from n 713 newbits = n & 0x7F 714 n = n>>7 715 r = chr(newbits + flag) + r 716 if flag == 0: 717 flag = 0x80 718 if n == 0: 720 done = True 721 return r 723 # test cases from LTP and BP internet-drafts, only print failures 724 def sdnv_test(): 725 tests = [(0xABC, chr(0x95) + chr(0x3C)), 726 (0x1234, chr(0xA4) + chr (0x34)), 727 (0x4234, chr(0x81) + chr(0x84) + chr(0x34)), 728 (0x7F, chr(0x7F))] 730 for tp in tests: 731 # test encoding function 732 if sdnv_encode(tp[0]) != tp[1]: 733 print "sdnv_encode fails on input %s" % hex(tp[0]) 734 # test decoding function 735 if sdnv_decode(tp[1])[0] != tp[0]: 736 print "sdnv_decode fails on input %s, giving %s" % \ 737 (hex(tp[0]), sdnv_decode(tp[1])) 739 Authors' Addresses 741 Wesley M. Eddy 742 MTI Systems 743 NASA Glenn Research Center 744 MS 500-ASRC; 21000 Brookpark Rd 745 Cleveland, OH 44135 747 Phone: 216-433-6682 748 Email: wes@mti-systems.com 750 Elwyn Davies 751 Folly Consulting 752 Soham 753 UK 755 Phone: 756 Email: elwynd@folly.org.uk 757 URI: