idnits 2.17.00 (12 Aug 2021) /tmp/idnits63340/draft-irtf-dtnrg-sdnv-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 15. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 628. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 639. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 646. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 652. 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 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 (September 17, 2007) is 5359 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 601 -- Looks like a reference, but probably isn't: '1' on line 601 == Outdated reference: draft-irtf-dtnrg-ltp has been published as RFC 5326 == Outdated reference: draft-irtf-dtnrg-ltp-motivation has been published as RFC 5325 == Outdated reference: draft-heffner-frag-harmful has been published as RFC 4963 == Outdated reference: draft-irtf-dtnrg-ltp has been published as RFC 5326 -- Duplicate reference: draft-irtf-dtnrg-ltp, mentioned in 'RBF06', was also mentioned in 'BRF04'. -- Obsolete informational reference (is this intentional?): RFC 1323 (Obsoleted by RFC 7323) == Outdated reference: draft-irtf-dtnrg-bundle-spec has been published as RFC 5050 Summary: 1 error (**), 0 flaws (~~), 6 warnings (==), 12 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 September 17, 2007 5 Expires: March 20, 2008 7 Using Self-Delimiting Numeric Values in Protocols 8 draft-irtf-dtnrg-sdnv-00 10 Status of this Memo 12 By submitting this Internet-Draft, each author represents that any 13 applicable patent or other IPR claims of which he or she is aware 14 have been or will be disclosed, and any of which he or she becomes 15 aware will be disclosed, in accordance with Section 6 of BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on March 20, 2008. 35 Copyright Notice 37 Copyright (C) The IETF Trust (2007). 39 Abstract 41 Self-Delimiting Numeric Values (SDNVs) have recently been introduced 42 as a field type within proposed Delay-Tolerant Networking protocols. 43 The basic goal of an SDNV is to hold a non-negative integer value of 44 arbitrary magnitude, without consuming much more space than 45 necessary. The primary motivation is to conserve the bits sent 46 across low-capacity or energy-intensive links typical of NASA deep- 47 space missions, with a secondary goal of allowing the protocol to 48 automatically adjust to unforseen usage scenarios. This can be 49 desirable in that it allows protocol designers to avoid making 50 difficult and potentially erroneous engineering decisions that may 51 have to be hacked around in the future. This document describes 52 formats and algorithms for SDNV encoding and decoding, and discusses 53 implementation and usage of SDNVs. 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 . . . . . . . . . . . . . . . . . . . 13 67 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 68 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 15 69 8. Informative References . . . . . . . . . . . . . . . . . . . . 16 70 Appendix A. SNDV Python Source Code . . . . . . . . . . . . . . . 18 71 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 20 72 Intellectual Property and Copyright Statements . . . . . . . . . . 21 74 1. Introduction 76 This section begins by describing a common problem encountered in 77 network protocol engineering. It then provides some background on 78 the Self-Delimiting Numeric Values (SDNVs) proposed for use in Delay- 79 Tolerant Networking (DTN) protocols, and motivates their potential 80 applicability in other networking protocols. The DTN Research Group 81 (DTNRG) within the Internet Research Task Force was created SDNVs to 82 meet the challenges it attempts to solve, and it has been noted that 83 SDNVs closely resemble certain constructs within ASN.1 and even older 84 ITU protocols, so the problems are not new or unique to DTN, nor is 85 the solution too radical for more mundane uses. 87 1.1. Problems with Fixed Value Fields 89 Protocol designers commonly face an optimization problem in 90 determining the proper size for header fields. There is a strong 91 desire to keep fields as small as possible, in order to reduce the 92 protocol's overhead on the wire, and also allow for fast processing. 93 Since protocols can be used many years (even decades) after they are 94 designed, and networking technology has tended to change rapidly, it 95 is not uncommon for the use, deployment, or performance of a 96 particular protocol to be limited or infringed upon by the length of 97 some header field being too short. Two well-known examples of this 98 phenomenon are the TCP advertised receive window, and the IPv4 99 address length. 101 TCP segments contain an advertised receive window field that is fixed 102 at 16 bits [RFC0793], encoding a maximum value of around 65 103 kilobytes. The purpose of this value is to provide flow control, by 104 allowing a receiver to specify how many sent bytes its peer can have 105 outstanding (unacknowledged) at any time, thus allowing the receiver 106 to limit its buffer size. As network speeds have grown by several 107 orders of magnitude since TCP's inception, the combination of the 65 108 kilobyte maximum advertised window and long round-trip times 109 prevented TCP senders from being able to acheive the high-rates that 110 the underlying network supported. This limitation was remedied 111 through the use of the Window Scale option [RFC1323], which provides 112 a multiplier for the advertised window field. However, the Window 113 Scale multiplier is fixed for the duration of the connection, 114 requires bi-directional support, and limits the precision of the 115 advertised receive window, so this is certainly a less-than-ideal 116 solution. Because of the field width limit in the original design 117 however, the Window Scale is necessary for TCP to reach high sending 118 rates. 120 An IPv4 address is fixed at 32 bits [RFC0791] (as a historical note, 121 earlier versions of the IP specification supported variable-length 122 addresses). Due to the way that subnetting and assignment of address 123 blocks was performed, the number of IPv4 addresses has been seen as a 124 limit to the growth of the Internet [Hain05]. Two divergent paths to 125 solve this problem have been the use of Network Address Translators 126 (NATs) and the development of IPv6. NATs have caused a number of 127 side-issues and problems [RFC2993], leading to increased complexity 128 and fragility, as well as forcing work-arounds to be engineered for 129 many other protocols to function within a NATed environment. The 130 IPv6 solution's transitional work has been underway for several 131 years, but has still only begun to have visible impact on the global 132 Internet. 134 Of course, in both the case of the TCP receive window and IPv4 135 address length, the field size chosen by the designers seemed like a 136 good idea at the time. The fields were more than big enough for the 137 originally perceived usage of the protocols, and yet were small 138 enough to allow the total headers to remain compact and relatively 139 easy and efficient to parse on machines of the time. The fixed sizes 140 that were defined represented a tradeoff between the scalability of 141 the protocol versus the overhead and efficiency of processing. In 142 both cases, these engineering decisions turned out to be painfully 143 incorrect. 145 1.2. SDNVs for DTN Protocols 147 In proposals for the DTN Bundle Protocol (BP) [SB05] and Licklider 148 Transmission Protocol (LTP) [RBF06], SDNVs have been used for several 149 fields including identifiers, payload/header lengths, and serial 150 (sequence) numbers. SDNVs were developed for use in these types of 151 fields, to avoid sending more bytes than needed, as well as avoiding 152 fixed sizes that may not end up being appropriate. For example, 153 since LTP is intended primarily for use in long-delay interplanetary 154 communications [BRF06], where links may be fairly low in capacity, it 155 is desirable to avoid the header overhead of routinely sending a 64- 156 bit field where a 16-bit field would suffice. Since many of the 157 nodes implementing LTP are expected to be beyond the current range of 158 human spaceflight, upgrading their on-board LTP implementations to 159 use longer values if the defined fields are found to be too short 160 would also be problematic. Furthermore, extensions similar in 161 mechanism to TCP's Window Scale option are unsuitable for use in DTN 162 protocols since due to high delays, DTN protocols must avoid 163 handshaking and configuration parameter negotiation to the greatest 164 extent possible. All of these reasons make the choice of SDNVs for 165 use in DTN protocols particularly wise. 167 1.3. SDNV Usage 169 In short, an SDNV is simply a way of representing non-negative 170 integers (both positive integers of arbitrary magnitude and 0), 171 without expending too-much unneccessary space. This definition 172 allows SDNVs to represent many common protocol header fields, such 173 as: 175 o Random identification fields as used in the IPsec Security 176 Parameters Index or in IP headers for fragment reassembly (Note: 177 the 16-bit IP ID field for fragment reassembly was recently found 178 to be too short in some environments [I-D.heffner-frag-harmful]), 180 o Sequence numbers as in TCP or SCTP, 182 o Values used in cryptographic algorithms such as RSA keys, Diffie- 183 Hellman key-agreement, or coordinates of points on elliptic 184 curves. 186 o Message lengths as used in file transfer protocols. 188 o Nonces and cookies. 190 o Etc. 192 The use of SDNVs rather than fixed length fields gives protocol 193 designers the ability to somewhat circumvent making difficult-to- 194 reverse field-sizing decisions, since the SDNV wire-format grows and 195 shrinks depending on the particular value encoded. SDNVs do not 196 necessarily provide optimal encodings for values of any particular 197 length, however they allow protocol designers to avoid potential 198 blunders in assigning fixed lengths, and remove the complexity 199 involved with either negotiating field lengths or constructing 200 protocol extensions. 202 To our knowledge, at this time, no IETF transport or network-layer 203 protocol designed for use outside of the DTN domain have proposed to 204 use SDNVs, however there is no inherent reason not to use SDNVs more 205 broadly in the future. The two examples cited here of fields that 206 have proven too-small in general Internet protocols are only a small 207 sampling of the much larger set of similar instances that the authors 208 can think of. Outside the Internet protocols, within ASN.1 and 209 previous ITU protocols, constructs very similar to SDNVs have been 210 used for many years due to engineering concerns very similar to those 211 facing the DTNRG. 213 Many protocols use a Type-Length-Value method for encoding variable 214 length strings (e.g. TCP's options format, or many of the fields in 215 IKEv2). An SDNV is equivalent to combining the length and value 216 portions of this type of field, with the overhead of the length 217 portion amortized out over the bytes of the value. The penalty paid 218 for this in an SDNV may be several extra bytes for long values (e.g. 219 1024 bit RSA keys). See Section 4 for further discussion and a 220 comparison. 222 As is shown in later sections, for large values, the current SDNV 223 scheme is fairly inefficient in terms of space (1/8 of the bits are 224 overhead) and not particularly easy to encode/decode in comparison to 225 alternatives. The best use of SDNVs may often be to define the 226 Length field of a TLV structure to be an SDNV whose value is the 227 length of the TLV's Value field. In this way, one can avoid forcing 228 large numbers from being directly encoded as an SDNV, yet retain the 229 extensibility that using SDNVs grants. 231 2. Definition of SDNVs 233 An early definition of the SDNV format bore resemblance to the ASN.1 234 [ASN1] Basic Encoding Rules (BER) [ASN1-BER] for lengths (Section 235 8.1.3 of X.690). The current SDNV format is the one used by ASN.1 236 BER for encoding tag identifiers greater than or equal to 31 (Section 237 8.1.2.4.2 of X.690). A comparison between the current SDNV format 238 and the early SDNV format is made in Section 4. 240 The currently-used format is very simple. Before encoding, an 241 integer is represented as a left-to-right bitstring beginning with 242 its most significant bit, and ending with its least signifcant bit. 243 On the wire, the bits are encoded into a series of bytes. The most 244 significant bit of each wire format byte specifies whether it is the 245 final byte of the encoded value (when it holds a 0), or not (when it 246 holds a 1). The remaining 7 bits of each byte in the wire format are 247 taken in-order from the integer's bitstring representation. If the 248 bitstring's length is not a multiple of 7, then the string is left- 249 padded with 0s. 251 For example: 253 o 1 (decimal) is represented by the bitstring "0000001" and encoded 254 as the single byte 0x01 (in hexadecimal) 256 o 128 is represented by the bitstring "10000001 00000000" and 257 encoded as the bytes 0x81 followed by 0x00. 259 o Other values can be found in the test vectors of the source code 260 in Appendix A 262 To be perfectly clear, and avoid potential interoperability issues 263 (as have occurred with ASN.1 BER time values), we explicitly state 264 two considerations regarding zero-padding. (1) When encoding SDNVs, 265 any leading (most significant) zero bits in the input number might be 266 discarded by the SDNV encoder. Protocols that use SDNVs should not 267 rely on leading-zeros being retained after encoding and decoding 268 operations. (2) When decoding SDNVs, the relevant number of leading 269 zeros required to pad up to a machine word or other natural data unit 270 might be added. These are put in the most-significant positions in 271 order to not change the value of the number. 273 3. Basic Algorithms 275 This section describes some simple algorithms for creating and 276 parsing SDNV fields. These may not be the most efficient algorithms 277 possible, however, they are easy to read, understand, and implement. 278 Appendix A contains Python source code implementing the routines 279 described here. Only SDNV's of the currently-used form are 280 considered in this section. 282 3.1. Encoding Algorithm 284 There is a very simple algorithm for the encoding operation that 285 converts a non-negative integer (n, of length 1+floor(log_2 n) bits) 286 into an SDNV. This algorithm takes n as its only argument and 287 returns a string of bytes: 289 o (Initial Step) Set the return value to a byte sharing the least 290 significant 7 bits of n, and with 0 in the most significant bit, 291 but do not return yet. Right shift n 7 bits and use this as the 292 new n value. If implemented using call-by-reference rather than 293 call-by-value, make a copy of n for local use at the start of the 294 function call. 296 o (Recursion Step) If n == 0, return. Otherwise, take the byte 297 0x80, and bitwise-or it with the 7 least significant bits left in 298 n. Set the return value to this result with the previous return 299 string appended to it. Set n to itself shifted right 7 bits 300 again. Repeat Recursion Step. 302 This encoding algorithm can easily be seen to have time complexity of 303 O(log_2 n), since it takes a number of steps equal to ceil(n/7), and 304 no additional space beyond the size of the result (8/7 log_2 n) is 305 required. One aspect of this algorithm is that it assumes strings 306 can be efficiently appended to new bytes. One way to implement this 307 is to allocate a buffer for the expected length of the result and 308 fill that buffer one byte at a time from the right end. 310 3.2. Decoding Algorithm 312 Decoding SNDVs is a more difficult operation than encoding them, due 313 to the fact that no bound on the resulting value is known until the 314 SDNV is parsed, at which point the value itself is already known. 315 This means that if space is allocated for decoding the value of an 316 SDNV into, it is never known whether this space will be overflowed 317 until it is 7 bits away from happening. 319 (Initial Step) Set the result to 0. Set a pointer to the beginning 320 of the SDNV. 322 (Recursion Step) Shift the result left 7 bits. Add the lower 7 bits 323 of the value at the pointer to the result. If the high-order bit 324 under the pointer is a 1, move the pointer right one byte and repeat 325 the Recursion Step, otherwise return the current value of the result. 327 This decoding algorithm takes no more additional space than what is 328 required for the result (7/8 the length of the SDNV) and the pointer. 329 The complication is that before the result can be left-shifted in the 330 Recursion Step, an implementation needs to first make sure that this 331 won't cause any bits to be lost, and re-allocate a larger piece of 332 memory for the result, if required. The pure time complexity is the 333 same as for the encoding algorithm given, but if re-allocation is 334 needed due to the inability to predict the size of the result, in 335 reality decoding may be slower. 337 4. Comparison to Alternatives 339 This section compares three alternative ways of implementing the 340 concept of SDNVs: (1) the TLV scheme commonly used in the Internet 341 family, and many other families of protocols, (2) the old style of 342 SDNVs (both the SDNV-8 and SDNV-16) defined in an early stage of 343 LTP's development [BRF04], and (3) the current SDNV format. 345 The TLV method uses two fixed-length fields to hold the Type" and 346 Length elements that then imply the syntax and semantics of the 347 "value" element. This is only similar to an SDNV in that the value 348 element can grow or shrink within the bounds capable of being 349 conveyed by the Length field. Two fundamental differences between 350 TLVs and SDNVs are that through the Type element, TLVs also contain 351 some notion of what their contents are semantically, while SDNVs are 352 simply generic non-negative integers, and protocol engineers still 353 have to pick fixed-lengths for the Type and Length fields in the TLV 354 format. 356 Some protocols use TLVs where the value conveyed within the Length 357 field needs to be decoded into the actual length of the Value field. 358 This may be accomplished through simple multiplication, left- 359 shifting, or a look-up table. In any case, this tactic limits the 360 granularity of the possible Value lengths, and can contribute some 361 degree of bloat if Values do not fit neatly within the available 362 decoded Lengths. 364 In the SDNV format originally used by LTP, parsing the first byte of 365 the SDNV told an implementation how much space was required to hold 366 the contained value. There were two different types of SDNVs defined 367 for different ranges of use. The SDNV-8 type could hold values up to 368 127 in a single byte, while the SDNV-16 type could hold values up to 369 32,767 in 2 bytes. Both formats could encode values requiring up to 370 N bytes in N+2 bytes, where N<127. The two major difference between 371 this old SDNV format and the currently-used SDNV format is that the 372 new format is not as easily decoded as the old format was, but the 373 new format also has absolutely no limitation on its length. 375 The advantage in ease of parsing that the old format manifests itself 376 in two aspects: (1) the size of the value is determinable ahead of 377 time, in a way equivalent to parsing a TLV, and (2) the actual value 378 is directly encoded and decoded, without shifting and masking bits as 379 is required in the new format. For these reasons, the old format 380 requires less computational overhead to deal with, but is also very 381 limited, in that it can only hold a 1024-bit number, at maximum. 382 Since according to IETF Best Current Practices, an asymmetric 383 cryptography key needed to last for a long term requires using moduli 384 of over 1228 bits [RFC3766], this could be seen as a severe 385 limitation of the old-style of SDNVs, which the currently-used style 386 does not suffer from. 388 Table 1 compares the maximum values that can be encoded into SDNVs of 389 various lengths using the old SDNV-8/16 method and the current SDNV 390 method. The only place in this table where SDNV-16 is used rather 391 than SDNV-8 is in the 2-byte row. Starting with a single byte, the 392 two methods are equivalent, but when using 2 bytes, the old method is 393 a more compact encoding by one-bit. From 3 to 7 bytes of length 394 though, the current SDNV format is more compact, since it only 395 requires one-bit per byte of overhead, whereas the old format used a 396 full byte. Thus, at 8 bytes, both schemes are equivalent in 397 efficiency since they both use 8 bits of overhead. Up to 129 bytes, 398 the old format is more compact than the current one, although after 399 this limit it becomes unusable. 401 +-------+---------------+-------------+---------------+-------------+ 402 | Bytes | SDNV-8/16 | SDNV | SDNV-8/16 | SDNV | 403 | | Maximum Value | Maximum | Overhead Bits | Overhead | 404 | | | Value | | Bits | 405 +-------+---------------+-------------+---------------+-------------+ 406 | 1 | 127 | 127 | 1 | 1 | 407 | | | | | | 408 | 2 | 32,767 | 16,383 | 1 | 2 | 409 | | | | | | 410 | 3 | 65,535 | 2,097,151 | 8 | 3 | 411 | | | | | | 412 | 4 | 2^24 - 1 | 2^28 - 1 | 8 | 4 | 413 | | | | | | 414 | 5 | 2^32 - 1 | 2^35 - 1 | 8 | 5 | 415 | | | | | | 416 | 6 | 2^40 - 1 | 2^42 - 1 | 8 | 6 | 417 | | | | | | 418 | 7 | 2^48 - 1 | 2^49 - 1 | 8 | 7 | 419 | | | | | | 420 | 8 | 2^56 - 1 | 2^56 - 1 | 8 | 8 | 421 | | | | | | 422 | 9 | 2^64 - 1 | 2^63 - 1 | 8 | 9 | 423 | | | | | | 424 | 10 | 2^72 - 1 | 2^70 - 1 | 8 | 10 | 425 | | | | | | 426 | 16 | 2^120 - 1 | 2^112 - 1 | 8 | 16 | 427 | | | | | | 428 | 32 | 2^248 - 1 | 2^224 - 1 | 8 | 32 | 429 | | | | | | 430 | 64 | 2^504 - 1 | 2^448 - 1 | 8 | 64 | 431 | | | | | | 432 | 128 | 2^1016 - 1 | 2^896 - 1 | 8 | 128 | 433 | | | | | | 434 | 129 | 2^1024 - 1 | 2^903 - 1 | 8 | 129 | 435 | | | | | | 436 | 130 | N/A | 2^910 - 1 | N/A | 130 | 437 | | | | | | 438 | 256 | N/A | 2^1792 - 1 | N/A | 256 | 439 +-------+---------------+-------------+---------------+-------------+ 441 Table 1 443 In general, it seems like the most promising use of SDNVs may be to 444 define the Length field of a TLV structure to be an SDNV whose value 445 is the length of the TLV's Value field. This leverages the strengths 446 of the SDNV format and limits the effects of its weaknesses. 448 5. Security Considerations 450 The only security considerations with regards to SDNVs are that code 451 which parses SDNVs should have bounds-checking logic and be capable 452 of handling cases where an SDNV's value is beyond the code's ability 453 to parse. These precautions can prevent potential exploits involving 454 SDNV decoding routines. 456 Stephen Farrell noted that very early definitions of SDNVs also 457 allowed negative integers. This was considered a potential security 458 hole, since it could expose implementations to underflow attacks 459 during SDNV decoding. There is a precedent in that many existing TLV 460 decoders map the Length field to a signed integer and are vulnerable 461 in this way. An SDNV decoder should be based on unsigned types and 462 not have this issue. 464 6. IANA Considerations 466 This document has no IANA considerations. 468 7. Acknowledgements 470 Scott Burleigh, Manikantan Ramadas, Michael Demmer, Stephen Farrell 471 and other members of the IRTF DTN Research Group contributed to the 472 development and usage of SDNVs in DTN protocols. George Jones and 473 Keith Scott from Mitre, Lloyd Wood, Gerardo Izquierdo, and Joel 474 Halpern also contributed useful comments on and criticisms of this 475 document. 477 Work on this document was performed at NASA's Glenn Research Center, 478 in support of the NASA Space Communications Architecture Working 479 Group (SCAWG), NASA's Earth Science Technology Office (ESTO), and the 480 FAA/Eurocontrol Future Communications Study (FCS). 482 8. Informative References 484 [ASN1] ITU-T Rec. X.680, "Abstract Syntax Notation One (ASN.1). 485 Specification of Basic Notation", ISO/IEC 8824-1:2002, 486 2002. 488 [ASN1-BER] 489 ITU-T Rec. X.690, "Abstract Syntax Notation One (ASN.1). 490 Encoding Rules: Specification of Basic Encoding Rules 491 (BER), Canonical Encoding Rules (CER) and Distinguished 492 Encoding Rules (DER)", ISO/IEC 8825-1:2002, 2002. 494 [BRF04] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider 495 Transmission Protocol", draft-irtf-dtnrg-ltp-00 (expired), 496 May 2004. 498 [BRF06] Burleigh, S., Ramadas, M., and S. Farrell, "Licklider 499 Transmission Protocol - Motivation", 500 draft-irtf-dtnrg-ltp-motivation-02 (work in progress), 501 March 2006. 503 [Hain05] Hain, T., "A Pragmatic Report on IPv4 Address Space 504 Consumption", Internet Protocol Journal Vol. 8, No. 3, 505 September 2005. 507 [I-D.heffner-frag-harmful] 508 Heffner, J., "IPv4 Reassembly Errors at High Data Rates", 509 draft-heffner-frag-harmful-05 (work in progress), 510 May 2007. 512 [RBF06] Ramadas, M., Burleigh, S., and S. Farrell, "Licklider 513 Transmission Protocol - Specification", 514 draft-irtf-dtnrg-ltp-04 (work in progress), March 2006. 516 [RFC0791] Postel, J., "Internet Protocol", STD 5, RFC 791, 517 September 1981. 519 [RFC0793] Postel, J., "Transmission Control Protocol", STD 7, 520 RFC 793, September 1981. 522 [RFC1323] Jacobson, V., Braden, B., and D. Borman, "TCP Extensions 523 for High Performance", RFC 1323, May 1992. 525 [RFC2993] Hain, T., "Architectural Implications of NAT", RFC 2993, 526 November 2000. 528 [RFC3766] Orman, H. and P. Hoffman, "Determining Strengths For 529 Public Keys Used For Exchanging Symmetric Keys", BCP 86, 530 RFC 3766, April 2004. 532 [SB05] Scott, K. and S. Burleigh, "Bundle Protocol 533 Specification", draft-irtf-dtnrg-bundle-spec-04 (work in 534 progress), November 2005. 536 Appendix A. SNDV Python Source Code 538 # sdnv_decode() takes a string argument s, which is assumed to be an 539 # SDNV. The function returns a pair of the non-negative integer n 540 # that is the numeric value encoded in the SDNV, and and integer l 541 # that is the distance parsed into the input string. If the slen 542 # argument is not given (or is not a non-zero number) then, s is 543 # parsed up to the first byte whose high-order bit is 0 -- the 544 # length of the SDNV portion of s does not have to be pre-computed 545 # by calling code. If the slen argument is given as a non-zero 546 # value, then slen bytes of s are parsed. The value for n of -1 is 547 # returned for any type of parsing error. 548 # 549 # NOTE: In python, integers can be of arbitrary size. In other 550 # languages, such as C, SDNV-parsing routines should take 551 # precautions to avoid overflow (e.g. by using the Gnu MP library, 552 # or similar). 553 # 554 def sdnv_decode(s, slen=0): 555 n = long(0) 556 for i in range(0, len(s)): 557 v = ord(s[i]) 558 n = n<<7 559 n = n + (v & 0x7F) 560 if v>>7 == 0: 561 slen = i+1 562 break 563 elif i == len(s)-1 or (slen != 0 and i > slen): 564 n = -1 # reached end of input without seeing end of SDNV 565 return (n, slen) 567 # sdnv_encode() returns the SDNV-encoded string that represents n. 568 # An empty string is returned if n is not a non-negative integer 569 def sdnv_encode(n): 570 r = "" 571 # validate input 572 if n >= 0 and (type(n) in [type(int(1)), type(long(1))]): 573 flag = 0 574 done = False 575 while not done: 576 # encode lowest 7 bits from n 577 newbits = n & 0x7F 578 n = n>>7 579 r = chr(newbits + flag) + r 580 if flag == 0: 581 flag = 0x80 582 if n == 0: 583 done = True 585 return r 587 # test cases from LTP and BP internet-drafts, only print failures 588 def sdnv_test(): 589 tests = [(0xABC, chr(0x95) + chr(0x3C)), 590 (0x1234, chr(0xA4) + chr (0x34)), 591 (0x4234, chr(0x81) + chr(0x84) + chr(0x34)), 592 (0x7F, chr(0x7F))] 594 for tp in tests: 595 # test encoding function 596 if sdnv_encode(tp[0]) != tp[1]: 597 print "sdnv_encode fails on input %s" % hex(tp[0]) 598 # test decoding function 599 if sdnv_decode(tp[1])[0] != tp[0]: 600 print "sdnv_decode fails on input %s, giving %s" % \ 601 (hex(tp[0]), sdnv_decode(tp[1])) 603 Author's Address 605 Wesley M. Eddy 606 Verizon Federal Network Systems 607 NASA Glenn Research Center 608 21000 Brookpark Rd, MS 54-5 609 Cleveland, OH 44135 611 Phone: 216-433-6682 612 Email: weddy@grc.nasa.gov 614 Full Copyright Statement 616 Copyright (C) The IETF Trust (2007). 618 This document is subject to the rights, licenses and restrictions 619 contained in BCP 78, and except as set forth therein, the authors 620 retain all their rights. 622 This document and the information contained herein are provided on an 623 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 624 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 625 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 626 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 627 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 628 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 630 Intellectual Property 632 The IETF takes no position regarding the validity or scope of any 633 Intellectual Property Rights or other rights that might be claimed to 634 pertain to the implementation or use of the technology described in 635 this document or the extent to which any license under such rights 636 might or might not be available; nor does it represent that it has 637 made any independent effort to identify any such rights. Information 638 on the procedures with respect to rights in RFC documents can be 639 found in BCP 78 and BCP 79. 641 Copies of IPR disclosures made to the IETF Secretariat and any 642 assurances of licenses to be made available, or the result of an 643 attempt made to obtain a general license or permission for the use of 644 such proprietary rights by implementers or users of this 645 specification can be obtained from the IETF on-line IPR repository at 646 http://www.ietf.org/ipr. 648 The IETF invites any interested party to bring to its attention any 649 copyrights, patents or patent applications, or other proprietary 650 rights that may cover technology that may be required to implement 651 this standard. Please address the information to the IETF at 652 ietf-ipr@ietf.org. 654 Acknowledgment 656 Funding for the RFC Editor function is provided by the IETF 657 Administrative Support Activity (IASA).