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