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