idnits 2.17.00 (12 Aug 2021) /tmp/idnits4512/draft-irtf-dtnrg-sdnv-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.ii or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) 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 (August 18, 2009) is 4658 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 629 -- Looks like a reference, but probably isn't: '1' on line 629 == 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: 1 error (**), 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 Verizon 4 Intended status: Informational August 18, 2009 5 Expires: February 19, 2010 7 Using Self-Delimiting Numeric Values in Protocols 8 draft-irtf-dtnrg-sdnv-03 10 Status of this Memo 12 This Internet-Draft is submitted to IETF in full conformance with the 13 provisions of BCP 78 and BCP 79. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet- 18 Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt. 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 This Internet-Draft will expire on February 19, 2010. 33 Copyright Notice 35 Copyright (c) 2009 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents in effect on the date of 40 publication of this document (http://trustee.ietf.org/license-info). 41 Please review these documents carefully, as they describe your rights 42 and restrictions with respect to this document. 44 Abstract 46 Self-Delimiting Numeric Values (SDNVs) have recently been introduced 47 as a field type in proposed Delay-Tolerant Networking protocols. 48 SDNVs encode an arbitrary-length non-negative integer with minimum 49 wire-overhead. They are intended to provide protocol flexibility 50 without sacrificing economy, and to assist in future-proofing 51 protocols under development. This document describes formats and 52 algorithms for SDNV encoding and decoding, along with notes on 53 implementation and usage. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 1.1. Problems with Fixed Value Fields . . . . . . . . . . . . . 3 59 1.2. SDNVs for DTN Protocols . . . . . . . . . . . . . . . . . 4 60 1.3. SDNV Usage . . . . . . . . . . . . . . . . . . . . . . . . 5 61 2. Definition of SDNVs . . . . . . . . . . . . . . . . . . . . . 7 62 3. Basic Algorithms . . . . . . . . . . . . . . . . . . . . . . . 8 63 3.1. Encoding Algorithm . . . . . . . . . . . . . . . . . . . . 8 64 3.2. Decoding Algorithm . . . . . . . . . . . . . . . . . . . . 8 65 4. Comparison to Alternatives . . . . . . . . . . . . . . . . . . 10 66 5. Security Considerations . . . . . . . . . . . . . . . . . . . 14 67 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 68 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16 69 8. Informative References . . . . . . . . . . . . . . . . . . . . 17 70 Appendix A. SNDV Python Source Code . . . . . . . . . . . . . . . 19 71 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 21 73 1. Introduction 75 This document is a product of the Internet Research Task Force (IRTF) 76 Delay-Tolerant Networking (DTN) Research Group (DTNRG). The document 77 has received review and support within the DTNRG, as discussed in the 78 Acknowledgements section of this document. 80 This document begins by describing a common problem encountered in 81 network protocol engineering. It then provides some background on 82 the Self-Delimiting Numeric Values (SDNVs) proposed for use in DTN 83 protocols, and motivates their potential applicability in other 84 networking protocols. The DTNRG has created SDNVs to meet the 85 challenges it attempts to solve, and it has been noted that SDNVs 86 closely resemble certain constructs within ASN.1 and even older ITU 87 protocols, so the problems are not new or unique to DTN, nor is the 88 solution too radical for more mundane uses. 90 SDNVs are tersely defined in both the bundle protocol [RFC5050] and 91 LTP [RFC5326] specifications, due to the flow of document production 92 in the DTNRG. This document clarifies and further explains the 93 motivations and engineering decisions behind SDNVs. 95 1.1. Problems with Fixed Value Fields 97 Protocol designers commonly face an optimization problem in 98 determining the proper size for header fields. There is a strong 99 desire to keep fields as small as possible, in order to reduce the 100 protocol's overhead on the wire, and also allow for fast processing. 101 Since protocols can be used many years (even decades) after they are 102 designed, and networking technology has tended to change rapidly, it 103 is not uncommon for the use, deployment, or performance of a 104 particular protocol to be limited or infringed upon by the length of 105 some header field being too short. Two well-known examples of this 106 phenomenon are the TCP advertised receive window, and the IPv4 107 address length. 109 TCP segments contain an advertised receive window field that is fixed 110 at 16 bits [RFC0793], encoding a maximum value of around 65 111 kilobytes. The purpose of this value is to provide flow control, by 112 allowing a receiver to specify how many sent bytes its peer can have 113 outstanding (unacknowledged) at any time, thus allowing the receiver 114 to limit its buffer size. As network speeds have grown by several 115 orders of magnitude since TCP's inception, the combination of the 65 116 kilobyte maximum advertised window and long round-trip times 117 prevented TCP senders from being able to acheive the high-rates that 118 the underlying network supported. This limitation was remedied 119 through the use of the Window Scale option [RFC1323], which provides 120 a multiplier for the advertised window field. However, the Window 121 Scale multiplier is fixed for the duration of the connection, 122 requires bi-directional support, and limits the precision of the 123 advertised receive window, so this is certainly a less-than-ideal 124 solution. Because of the field width limit in the original design 125 however, the Window Scale is necessary for TCP to reach high sending 126 rates. 128 An IPv4 address is fixed at 32 bits [RFC0791] (as a historical note, 129 earlier versions of the IP specification supported variable-length 130 addresses). Due to the way that subnetting and assignment of address 131 blocks was performed, the number of IPv4 addresses has been seen as a 132 limit to the growth of the Internet [Hain05]. Two divergent paths to 133 solve this problem have been the use of Network Address Translators 134 (NATs) and the development of IPv6. NATs have caused a number of 135 side-issues and problems [RFC2993], leading to increased complexity 136 and fragility, as well as forcing work-arounds to be engineered for 137 many other protocols to function within a NATed environment. The 138 IPv6 solution's transitional work has been underway for several 139 years, but has still only begun to have visible impact on the global 140 Internet. 142 Of course, in both the case of the TCP receive window and IPv4 143 address length, the field size chosen by the designers seemed like a 144 good idea at the time. The fields were more than big enough for the 145 originally perceived usage of the protocols, and yet were small 146 enough to allow the total headers to remain compact and relatively 147 easy and efficient to parse on machines of the time. The fixed sizes 148 that were defined represented a tradeoff between the scalability of 149 the protocol versus the overhead and efficiency of processing. In 150 both cases, these engineering decisions turned out to be painfully 151 restrictive in the longer term. 153 1.2. SDNVs for DTN Protocols 155 In specifications for the DTN Bundle Protocol (BP) [RFC5050] and 156 Licklider Transmission Protocol (LTP) [RFC5326], SDNVs have been used 157 for several fields including identifiers, payload/header lengths, and 158 serial (sequence) numbers. SDNVs were developed for use in these 159 types of fields, to avoid sending more bytes than needed, as well as 160 avoiding fixed sizes that may not end up being appropriate. For 161 example, since LTP is intended primarily for use in long-delay 162 interplanetary communications [RFC5325], where links may be fairly 163 low in capacity, it is desirable to avoid the header overhead of 164 routinely sending a 64-bit field where a 16-bit field would suffice. 165 Since many of the nodes implementing LTP are expected to be beyond 166 the current range of human spaceflight, upgrading their on-board LTP 167 implementations to use longer values if the defined fields are found 168 to be too short would also be problematic. Furthermore, extensions 169 similar in mechanism to TCP's Window Scale option are unsuitable for 170 use in DTN protocols since due to high delays, DTN protocols must 171 avoid handshaking and configuration parameter negotiation to the 172 greatest extent possible. All of these reasons make the choice of 173 SDNVs for use in DTN protocols attractive. 175 1.3. SDNV Usage 177 In short, an SDNV is simply a way of representing non-negative 178 integers (both positive integers of arbitrary magnitude and 0), 179 without expending too-much unneccessary space. This definition 180 allows SDNVs to represent many common protocol header fields, such 181 as: 183 o Random identification fields as used in the IPsec Security 184 Parameters Index or in IP headers for fragment reassembly (Note: 185 the 16-bit IP ID field for fragment reassembly was recently found 186 to be too short in some environments [RFC4963]), 188 o Sequence numbers as in TCP or SCTP, 190 o Values used in cryptographic algorithms such as RSA keys, Diffie- 191 Hellman key-agreement, or coordinates of points on elliptic 192 curves. 194 o Message lengths as used in file transfer protocols. 196 o Nonces and cookies. 198 o Etc. 200 The use of SDNVs rather than fixed length fields gives protocol 201 designers the ability to somewhat circumvent making difficult-to- 202 reverse field-sizing decisions, since the SDNV wire-format grows and 203 shrinks depending on the particular value encoded. SDNVs do not 204 necessarily provide optimal encodings for values of any particular 205 length, however they allow protocol designers to avoid potential 206 blunders in assigning fixed lengths, and remove the complexity 207 involved with either negotiating field lengths or constructing 208 protocol extensions. 210 To our knowledge, at this time, no IETF transport or network-layer 211 protocol designed for use outside of the DTN domain have proposed to 212 use SDNVs, however there is no inherent reason not to use SDNVs more 213 broadly in the future. The two examples cited here of fields that 214 have proven too-small in general Internet protocols are only a small 215 sampling of the much larger set of similar instances that the authors 216 can think of. Outside the Internet protocols, within ASN.1 and 217 previous ITU protocols, constructs very similar to SDNVs have been 218 used for many years due to engineering concerns very similar to those 219 facing the DTNRG. 221 Many protocols use a Type-Length-Value method for encoding variable 222 length strings (e.g. TCP's options format, or many of the fields in 223 IKEv2). An SDNV is equivalent to combining the length and value 224 portions of this type of field, with the overhead of the length 225 portion amortized out over the bytes of the value. The penalty paid 226 for this in an SDNV may be several extra bytes for long values (e.g. 227 1024 bit RSA keys). See Section 4 for further discussion and a 228 comparison. 230 As is shown in later sections, for large values, the current SDNV 231 scheme is fairly inefficient in terms of space (1/8 of the bits are 232 overhead) and not particularly easy to encode/decode in comparison to 233 alternatives. The best use of SDNVs may often be to define the 234 Length field of a TLV structure to be an SDNV whose value is the 235 length of the TLV's Value field. In this way, one can avoid forcing 236 large numbers from being directly encoded as an SDNV, yet retain the 237 extensibility that using SDNVs grants. 239 2. Definition of SDNVs 241 An early definition of the SDNV format bore resemblance to the ASN.1 242 [ASN1] Basic Encoding Rules (BER) [ASN1-BER] for lengths (Section 243 8.1.3 of X.690). The current SDNV format is the one used by ASN.1 244 BER for encoding tag identifiers greater than or equal to 31 (Section 245 8.1.2.4.2 of X.690). A comparison between the current SDNV format 246 and the early SDNV format is made in Section 4. 248 The currently-used format is very simple. Before encoding, an 249 integer is represented as a left-to-right bitstring beginning with 250 its most significant bit, and ending with its least signifcant bit. 251 On the wire, the bits are encoded into a series of bytes. The most 252 significant bit of each wire format byte specifies whether it is the 253 final byte of the encoded value (when it holds a 0), or not (when it 254 holds a 1). The remaining 7 bits of each byte in the wire format are 255 taken in-order from the integer's bitstring representation. If the 256 bitstring's length is not a multiple of 7, then the string is left- 257 padded with 0s. 259 For example: 261 o 1 (decimal) is represented by the bitstring "0000001" and encoded 262 as the single byte 0x01 (in hexadecimal) 264 o 128 is represented by the bitstring "10000001 00000000" and 265 encoded as the bytes 0x81 followed by 0x00. 267 o Other values can be found in the test vectors of the source code 268 in Appendix A 270 To be perfectly clear, and avoid potential interoperability issues 271 (as have occurred with ASN.1 BER time values), we explicitly state 272 two considerations regarding zero-padding. (1) When encoding SDNVs, 273 any leading (most significant) zero bits in the input number might be 274 discarded by the SDNV encoder. Protocols that use SDNVs should not 275 rely on leading-zeros being retained after encoding and decoding 276 operations. (2) When decoding SDNVs, the relevant number of leading 277 zeros required to pad up to a machine word or other natural data unit 278 might be added. These are put in the most-significant positions in 279 order to not change the value of the number. Protocols using SDNVs 280 should consider situations where lost zero-padding may be 281 problematic. 283 3. Basic Algorithms 285 This section describes some simple algorithms for creating and 286 parsing SDNV fields. These may not be the most efficient algorithms 287 possible, however, they are easy to read, understand, and implement. 288 Appendix A contains Python source code implementing the routines 289 described here. Only SDNV's of the currently-used form are 290 considered in this section. 292 3.1. Encoding Algorithm 294 There is a very simple algorithm for the encoding operation that 295 converts a non-negative integer (n, of length 1+floor(log_2 n) bits) 296 into an SDNV. This algorithm takes n as its only argument and 297 returns a string of bytes: 299 o (Initial Step) Set the return value to a byte sharing the least 300 significant 7 bits of n, and with 0 in the most significant bit, 301 but do not return yet. Right shift n 7 bits and use this as the 302 new n value. If implemented using call-by-reference rather than 303 call-by-value, make a copy of n for local use at the start of the 304 function call. 306 o (Recursion Step) If n == 0, return. Otherwise, take the byte 307 0x80, and bitwise-or it with the 7 least significant bits left in 308 n. Set the return value to this result with the previous return 309 string appended to it. Set n to itself shifted right 7 bits 310 again. Repeat Recursion Step. 312 This encoding algorithm can easily be seen to have time complexity of 313 O(log_2 n), since it takes a number of steps equal to ceil(n/7), and 314 no additional space beyond the size of the result (8/7 log_2 n) is 315 required. One aspect of this algorithm is that it assumes strings 316 can be efficiently appended to new bytes. One way to implement this 317 is to allocate a buffer for the expected length of the result and 318 fill that buffer one byte at a time from the right end. 320 If, for some reason, an implementation requires an encoded SDNV to be 321 some specific length (possibly related to a machine word), any 322 leftmost zero-padding included needs to properly set the high-order 323 bit in each byte of padding. 325 3.2. Decoding Algorithm 327 Decoding SNDVs is a more difficult operation than encoding them, due 328 to the fact that no bound on the resulting value is known until the 329 SDNV is parsed, at which point the value itself is already known. 330 This means that if space is allocated for decoding the value of an 331 SDNV into, it is never known whether this space will be overflowed 332 until it is 7 bits away from happening. 334 (Initial Step) Set the result to 0. Set a pointer to the beginning 335 of the SDNV. 337 (Recursion Step) Shift the result left 7 bits. Add the lower 7 bits 338 of the value at the pointer to the result. If the high-order bit 339 under the pointer is a 1, move the pointer right one byte and repeat 340 the Recursion Step, otherwise return the current value of the result. 342 This decoding algorithm takes no more additional space than what is 343 required for the result (7/8 the length of the SDNV) and the pointer. 344 The complication is that before the result can be left-shifted in the 345 Recursion Step, an implementation needs to first make sure that this 346 won't cause any bits to be lost, and re-allocate a larger piece of 347 memory for the result, if required. The pure time complexity is the 348 same as for the encoding algorithm given, but if re-allocation is 349 needed due to the inability to predict the size of the result, in 350 reality decoding may be slower. 352 These decoding steps include removal of any leftmost zero-padding 353 that might be used by an encoder to create encodings of a certain 354 length. 356 4. Comparison to Alternatives 358 This section compares three alternative ways of implementing the 359 concept of SDNVs: (1) the TLV scheme commonly used in the Internet 360 family, and many other families of protocols, (2) the old style of 361 SDNVs (both the SDNV-8 and SDNV-16) defined in an early stage of 362 LTP's development [BRF04], and (3) the current SDNV format. 364 The TLV method uses two fixed-length fields to hold the Type" and 365 Length elements that then imply the syntax and semantics of the 366 "value" element. This is only similar to an SDNV in that the value 367 element can grow or shrink within the bounds capable of being 368 conveyed by the Length field. Two fundamental differences between 369 TLVs and SDNVs are that through the Type element, TLVs also contain 370 some notion of what their contents are semantically, while SDNVs are 371 simply generic non-negative integers, and protocol engineers still 372 have to pick fixed-lengths for the Type and Length fields in the TLV 373 format. 375 Some protocols use TLVs where the value conveyed within the Length 376 field needs to be decoded into the actual length of the Value field. 377 This may be accomplished through simple multiplication, left- 378 shifting, or a look-up table. In any case, this tactic limits the 379 granularity of the possible Value lengths, and can contribute some 380 degree of bloat if Values do not fit neatly within the available 381 decoded Lengths. 383 In the SDNV format originally used by LTP, parsing the first byte of 384 the SDNV told an implementation how much space was required to hold 385 the contained value. There were two different types of SDNVs defined 386 for different ranges of use. The SDNV-8 type could hold values up to 387 127 in a single byte, while the SDNV-16 type could hold values up to 388 32,767 in 2 bytes. Both formats could encode values requiring up to 389 N bytes in N+2 bytes, where N<127. The major difference between this 390 old SDNV format and the currently-used SDNV format is that the new 391 format is not as easily decoded as the old format was, but the new 392 format also has absolutely no limitation on its length. 394 The advantage in ease of parsing the old format manifests itself in 395 two aspects: (1) the size of the value is determinable ahead of time, 396 in a way equivalent to parsing a TLV, and (2) the actual value is 397 directly encoded and decoded, without shifting and masking bits as is 398 required in the new format. For these reasons, the old format 399 requires less computational overhead to deal with, but is also very 400 limited, in that it can only hold a 1024-bit number, at maximum. 401 Since according to IETF Best Current Practices, an asymmetric 402 cryptography key needed to last for a long term requires using moduli 403 of over 1228 bits [RFC3766], this could be seen as a severe 404 limitation of the old-style of SDNVs, which the currently-used style 405 does not suffer from. 407 Table 1 compares the maximum values that can be encoded into SDNVs of 408 various lengths using the old SDNV-8/16 method and the current SDNV 409 method. The only place in this table where SDNV-16 is used rather 410 than SDNV-8 is in the 2-byte row. Starting with a single byte, the 411 two methods are equivalent, but when using 2 bytes, the old method is 412 a more compact encoding by one-bit. From 3 to 7 bytes of length 413 though, the current SDNV format is more compact, since it only 414 requires one-bit per byte of overhead, whereas the old format used a 415 full byte. Thus, at 8 bytes, both schemes are equivalent in 416 efficiency since they both use 8 bits of overhead. Up to 129 bytes, 417 the old format is more compact than the current one, although after 418 this limit it becomes unusable. 420 +-------+---------------+-------------+---------------+-------------+ 421 | Bytes | SDNV-8/16 | SDNV | SDNV-8/16 | SDNV | 422 | | Maximum Value | Maximum | Overhead Bits | Overhead | 423 | | | Value | | Bits | 424 +-------+---------------+-------------+---------------+-------------+ 425 | 1 | 127 | 127 | 1 | 1 | 426 | | | | | | 427 | 2 | 32,767 | 16,383 | 1 | 2 | 428 | | | | | | 429 | 3 | 65,535 | 2,097,151 | 8 | 3 | 430 | | | | | | 431 | 4 | 2^24 - 1 | 2^28 - 1 | 8 | 4 | 432 | | | | | | 433 | 5 | 2^32 - 1 | 2^35 - 1 | 8 | 5 | 434 | | | | | | 435 | 6 | 2^40 - 1 | 2^42 - 1 | 8 | 6 | 436 | | | | | | 437 | 7 | 2^48 - 1 | 2^49 - 1 | 8 | 7 | 438 | | | | | | 439 | 8 | 2^56 - 1 | 2^56 - 1 | 8 | 8 | 440 | | | | | | 441 | 9 | 2^64 - 1 | 2^63 - 1 | 8 | 9 | 442 | | | | | | 443 | 10 | 2^72 - 1 | 2^70 - 1 | 8 | 10 | 444 | | | | | | 445 | 16 | 2^120 - 1 | 2^112 - 1 | 8 | 16 | 446 | | | | | | 447 | 32 | 2^248 - 1 | 2^224 - 1 | 8 | 32 | 448 | | | | | | 449 | 64 | 2^504 - 1 | 2^448 - 1 | 8 | 64 | 450 | | | | | | 451 | 128 | 2^1016 - 1 | 2^896 - 1 | 8 | 128 | 452 | | | | | | 453 | 129 | 2^1024 - 1 | 2^903 - 1 | 8 | 129 | 454 | | | | | | 455 | 130 | N/A | 2^910 - 1 | N/A | 130 | 456 | | | | | | 457 | 256 | N/A | 2^1792 - 1 | N/A | 256 | 458 +-------+---------------+-------------+---------------+-------------+ 460 Table 1 462 In general, it seems like the most promising use of SDNVs may be to 463 define the Length field of a TLV structure to be an SDNV whose value 464 is the length of the TLV's Value field. This leverages the strengths 465 of the SDNV format and limits the effects of its weaknesses. 467 Another aspect of comparison between SDNVs and alternatives using 468 fixed-length fields is the result of errors in transmission. Bit- 469 errors in an SDNV can result in either errors in the decoded value, 470 or parsing errors in subsequent fields of the protocol. In fixed- 471 length fields, bit-errors always result in errors to the decoded 472 value rather than parsing errors in subsequent fields. If the 473 decoded values from either type of field encoding (SDNV or fixed- 474 length) are used as indexes, offsets, or lengths of further fields in 475 the protocol, similar failures result. 477 5. Security Considerations 479 The only security considerations with regards to SDNVs are that code 480 which parses SDNVs should have bounds-checking logic and be capable 481 of handling cases where an SDNV's value is beyond the code's ability 482 to parse. These precautions can prevent potential exploits involving 483 SDNV decoding routines. 485 Stephen Farrell noted that very early definitions of SDNVs also 486 allowed negative integers. This was considered a potential security 487 hole, since it could expose implementations to underflow attacks 488 during SDNV decoding. There is a precedent in that many existing TLV 489 decoders map the Length field to a signed integer and are vulnerable 490 in this way. An SDNV decoder should be based on unsigned types and 491 not have this issue. 493 6. IANA Considerations 495 This document has no IANA considerations. 497 7. Acknowledgements 499 Scott Burleigh, Manikantan Ramadas, Michael Demmer, Stephen Farrell, 500 and other members of the IRTF DTN Research Group contributed to the 501 development and usage of SDNVs in DTN protocols. George Jones and 502 Keith Scott from Mitre, Lloyd Wood, Gerardo Izquierdo, Joel Halpern, 503 and Peter TB Brett also contributed useful comments on and criticisms 504 of this document. DTNRG last call comments on the draft were sent to 505 the mailing list by Lloyd Wood, Will Ivancic, Jim Wyllie, William 506 Edwards, Hans Kruse, Janico Greifenberg, Teemu Karkkainen, Stephen 507 Farrell, and Scott Burleigh. 509 Work on this document was performed at NASA's Glenn Research Center, 510 in support of the NASA Space Communications Architecture Working 511 Group (SCAWG), NASA's Earth Science Technology Office (ESTO), and the 512 FAA/Eurocontrol Future Communications Study (FCS). 514 8. Informative References 516 [ASN1] ITU-T Rec. X.680, "Abstract Syntax Notation One (ASN.1). 517 Specification of Basic Notation", ISO/IEC 8824-1:2002, 518 2002. 520 [ASN1-BER] 521 ITU-T Rec. X.690, "Abstract Syntax Notation One (ASN.1). 522 Encoding Rules: Specification of Basic Encoding Rules 523 (BER), Canonical Encoding Rules (CER) and Distinguished 524 Encoding Rules (DER)", ISO/IEC 8825-1:2002, 2002. 526 [BRF04] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider 527 Transmission Protocol", 528 draft-irtf-dtnrg-ltp-00 (replaced), May 2004. 530 [Hain05] Hain, T., "A Pragmatic Report on IPv4 Address Space 531 Consumption", Internet Protocol Journal Vol. 8, No. 3, 532 September 2005. 534 [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, 535 September 1981. 537 [RFC0793] Postel, J., "Transmission Control Protocol", STD 7, 538 RFC 793, September 1981. 540 [RFC1323] Jacobson, V., Braden, B., and D. Borman, "TCP Extensions 541 for High Performance", RFC 1323, May 1992. 543 [RFC2993] Hain, T., "Architectural Implications of NAT", RFC 2993, 544 November 2000. 546 [RFC3766] Orman, H. and P. Hoffman, "Determining Strengths For 547 Public Keys Used For Exchanging Symmetric Keys", BCP 86, 548 RFC 3766, April 2004. 550 [RFC4963] Heffner, J., Mathis, M., and B. Chandler, "IPv4 Reassembly 551 Errors at High Data Rates", RFC 4963, July 2007. 553 [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol 554 Specification", RFC 5050, November 2007. 556 [RFC5325] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider 557 Transmission Protocol - Motivation", RFC 5325, 558 September 2008. 560 [RFC5326] Ramadas, M., Burleigh, S., and S. Farrell, "Licklider 561 Transmission Protocol - Specification", RFC 5326, 562 March 2008. 564 Appendix A. SNDV Python Source Code 566 # sdnv_decode() takes a string argument s, which is assumed to be an 567 # SDNV. The function returns a pair of the non-negative integer n 568 # that is the numeric value encoded in the SDNV, and and integer l 569 # that is the distance parsed into the input string. If the slen 570 # argument is not given (or is not a non-zero number) then, s is 571 # parsed up to the first byte whose high-order bit is 0 -- the 572 # length of the SDNV portion of s does not have to be pre-computed 573 # by calling code. If the slen argument is given as a non-zero 574 # value, then slen bytes of s are parsed. The value for n of -1 is 575 # returned for any type of parsing error. 576 # 577 # NOTE: In python, integers can be of arbitrary size. In other 578 # languages, such as C, SDNV-parsing routines should take 579 # precautions to avoid overflow (e.g. by using the Gnu MP library, 580 # or similar). 581 # 582 def sdnv_decode(s, slen=0): 583 n = long(0) 584 for i in range(0, len(s)): 585 v = ord(s[i]) 586 n = n<<7 587 n = n + (v & 0x7F) 588 if v>>7 == 0: 589 slen = i+1 590 break 591 elif i == len(s)-1 or (slen != 0 and i > slen): 592 n = -1 # reached end of input without seeing end of SDNV 593 return (n, slen) 595 # sdnv_encode() returns the SDNV-encoded string that represents n. 596 # An empty string is returned if n is not a non-negative integer 597 def sdnv_encode(n): 598 r = "" 599 # validate input 600 if n >= 0 and (type(n) in [type(int(1)), type(long(1))]): 601 flag = 0 602 done = False 603 while not done: 604 # encode lowest 7 bits from n 605 newbits = n & 0x7F 606 n = n>>7 607 r = chr(newbits + flag) + r 608 if flag == 0: 609 flag = 0x80 610 if n == 0: 611 done = True 613 return r 615 # test cases from LTP and BP internet-drafts, only print failures 616 def sdnv_test(): 617 tests = [(0xABC, chr(0x95) + chr(0x3C)), 618 (0x1234, chr(0xA4) + chr (0x34)), 619 (0x4234, chr(0x81) + chr(0x84) + chr(0x34)), 620 (0x7F, chr(0x7F))] 622 for tp in tests: 623 # test encoding function 624 if sdnv_encode(tp[0]) != tp[1]: 625 print "sdnv_encode fails on input %s" % hex(tp[0]) 626 # test decoding function 627 if sdnv_decode(tp[1])[0] != tp[0]: 628 print "sdnv_decode fails on input %s, giving %s" % \ 629 (hex(tp[0]), sdnv_decode(tp[1])) 631 Author's Address 633 Wesley M. Eddy 634 Verizon Federal Network Systems 635 NASA Glenn Research Center 636 21000 Brookpark Rd 637 Cleveland, OH 44135 639 Phone: 216-433-6682 640 Email: weddy@grc.nasa.gov