idnits 2.17.1 draft-ietf-bmwg-hash-stuffing-05.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 16. -- Found old boilerplate from RFC 3978, Section 5.5 on line 986. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 963. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 970. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 976. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. 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 : ---------------------------------------------------------------------------- == There are 2 instances of lines with private range IPv4 addresses in the document. If these are generic example addresses, they should be changed to use any of the ranges defined in RFC 6890 (or successor): 192.0.2.x, 198.51.100.x or 203.0.113.x. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 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 (February 9, 2006) is 6650 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'UDP' is mentioned on line 928, but not defined == Unused Reference: 'Ca63' is defined on line 793, but no explicit reference was found in the text == Unused Reference: 'Go97' is defined on line 796, but no explicit reference was found in the text == Unused Reference: 'Kn97' is defined on line 799, but no explicit reference was found in the text ** Downref: Normative reference to an Informational RFC: RFC 2544 ** Downref: Normative reference to an Informational RFC: RFC 2889 Summary: 5 errors (**), 0 flaws (~~), 7 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group D. Newman 3 Internet-Draft Network Test 4 Expires: August 13, 2006 T. Player 5 Spirent Communications 6 February 9, 2006 8 Hash and Stuffing: Overlooked Factors in Network Device Benchmarking 9 draft-ietf-bmwg-hash-stuffing-05.txt 11 Status of this Memo 13 By submitting this Internet-Draft, each author represents that any 14 applicable patent or other IPR claims of which he or she is aware 15 have been or will be disclosed, and any of which he or she becomes 16 aware will be disclosed, in accordance with Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on August 13, 2006. 36 Copyright Notice 38 Copyright (C) The Internet Society (2006). 40 Abstract 42 Test engineers take pains to declare all factors that affect a given 43 measurement, including intended load, packet length, test duration, 44 and traffic orientation. However, current benchmarking practice 45 overlooks two factors that have a profound impact on test results. 46 First, existing methodologies do not require the reporting of 47 addresses or other test traffic contents, even though these fields 48 can affect test results. Second, "stuff" bits and bytes inserted in 49 test traffic by some link-layer technologies add significant and 50 variable overhead, which in turn affects test results. This document 51 describes the effects of these factors; recommends guidelines for 52 test traffic contents; and offers formulas for determining the 53 probability of bit- and byte-stuffing in test traffic. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 2. Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 3. General considerations . . . . . . . . . . . . . . . . . . . . 5 60 3.1. Repeatability . . . . . . . . . . . . . . . . . . . . . . 5 61 3.2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . 5 62 4. Packet Content Variations . . . . . . . . . . . . . . . . . . 6 63 4.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 6 64 4.2. Ethernet MAC Addresses . . . . . . . . . . . . . . . . . . 7 65 4.2.1. Randomized Sets of MAC Addresses . . . . . . . . . . . 8 66 4.3. MPLS Addressing . . . . . . . . . . . . . . . . . . . . . 10 67 4.4. Network-layer Addressing . . . . . . . . . . . . . . . . . 10 68 4.5. Transport-layer Addressing . . . . . . . . . . . . . . . . 11 69 4.6. Application-layer Patterns . . . . . . . . . . . . . . . . 11 70 5. Control Character Stuffing . . . . . . . . . . . . . . . . . . 12 71 5.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 12 72 5.2. PPP Bit Stuffing . . . . . . . . . . . . . . . . . . . . . 12 73 5.2.1. Calculating Bit-Stuffing Probability . . . . . . . . . 15 74 5.2.2. Bit Stuffing for Finite Strings . . . . . . . . . . . 16 75 5.2.3. Applied Bit Stuffing . . . . . . . . . . . . . . . . . 17 76 5.3. POS Byte Stuffing . . . . . . . . . . . . . . . . . . . . 17 77 5.3.1. Nullifying ACCM . . . . . . . . . . . . . . . . . . . 18 78 5.3.2. Other Stuffed Characters . . . . . . . . . . . . . . . 18 79 5.3.3. Applied Byte Stuffing . . . . . . . . . . . . . . . . 18 80 6. Security Considerations . . . . . . . . . . . . . . . . . . . 20 81 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 82 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 83 8.1. Normative References . . . . . . . . . . . . . . . . . . . 22 84 8.2. Informative References . . . . . . . . . . . . . . . . . . 22 85 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 23 86 Appendix B. Proof of Formula for Finite Bit Stuffing . . . . . . 24 87 Appendix C. Explicit Calculation of Bit Stuffing Overhead . . . . 25 88 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27 89 Intellectual Property and Copyright Statements . . . . . . . . . . 28 91 1. Introduction 93 Experience in benchmarking networking devices suggests that the 94 contents of test traffic can have a profound impact on test results. 95 For example, some devices may forward randomly addressed traffic 96 without loss, but drop significant numbers of packets when offered 97 packets containing nonrandom addresses. 99 Methodologies such as [RFC2544] and [RFC2889] do not require any 100 declaration of packet contents. These methodologies do require the 101 declaration of test parameters such as traffic distribution and 102 traffic orientation, and yet packet contents can have at least as 103 great an impact on test results as the other factors. Variations in 104 packet contents also can lead to non-repeatability of test results: 105 Two individuals may follow methodology procedures to the letter, and 106 still obtain very different results. 108 A related issue is the insertion of stuff bits or bytes by link-layer 109 technologies using PPP with HDLC-like framing. This stuffing is done 110 to ensure sequences in test traffic will not be confused with flag or 111 control characters. 113 Stuffing adds significant and variable overhead. Currently there is 114 no standard method for determining the probability that stuffing will 115 occur for a given pattern, and thus no way to determine what impact 116 stuffing will have on test results. 118 This document covers two areas. First, we discuss strategies for 119 dealing with randomness and nonrandomness in test traffic. Second, 120 we present formulas to determine the probability of bit- and byte- 121 stuffing on PPP and POS circuits. In both areas, we provide 122 recommendations for obtaining more repeatability in test results. 124 2. Requirements 126 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 127 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 128 document are to be interpreted as described in [RFC2119]. 130 3. General considerations 132 3.1. Repeatability 134 Repeatability is a desirable trait in benchmarking, but it can be an 135 elusive goal. It is a common but mistaken belief that test results 136 can always be reproduced provided the device under test and test 137 instrument are configured identically for each test iteration. In 138 fact, even identical configurations may introduce some variations in 139 test traffic, such as changes in timestamps, TCP sequence numbers, or 140 other naturally occurring phenomena. 142 While this variability does not necessarily invalidate test results, 143 it is important to recognize such variation exists. Exact bit-for- 144 bit reproduction of test traffic in all cases is a hard problem. A 145 simpler approach is to acknowledge that some variation exists, 146 characterize that variation, and describe it when analyzing test 147 results. 149 3.2. Randomness 151 This document recommends the use of pseudorandom patterns in test 152 traffic under controlled lab conditions. The rand() functions 153 available in many programming languages produce output that is 154 pseudorandom rather than truly random. Pseudorandom patterns are 155 sufficient for the recommendations given in this document, provided 156 they produce output that is uniformly distributed across the pattern 157 space. 159 Specifically, for any random bit pattern of length L, the probability 160 of generating that specific pattern SHOULD equal 1 over 2 to the Lth 161 power. 163 4. Packet Content Variations 165 4.1. Problem Statement 167 The contents of test traffic can have a significant impact on metrics 168 such as throughput, jitter, latency, and loss. For example, many 169 network devices feed addresses into a hashing algorithm to determine 170 which path upon which to forward a given packet. 172 Consider the simple case of an Ethernet switch with eight network 173 processors (NPs) in its switching fabric: 175 ingress 176 || 177 \/ 178 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 179 | ___ ___ ___ ___ ___ ___ ___ ___ | 180 || | | | | | | | | | | | | | | | | 181 ||NP0| |NP1| |NP2| |NP3| |NP4| |NP5| |NP6| |NP7| | 182 ||___| |___| |___| |___| |___| |___| |___| |___| | 183 | | 184 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 185 || 186 \/ 187 egress 189 To assign incoming traffic to the various NPs, suppose a hashing 190 algorithm performs an exclusive-or (XOR) operation on the least 191 significant 3 bits of the source and destination MAC addresses in 192 each frame. (This is an actual example the authors have observed in 193 multiple devices from multiple manufacturers.) 195 In theory, a random distribution of source and destination MAC 196 addresses should result in traffic being uniformly distributed across 197 all eight NPs. (Instances of the term "random" in this document 198 refer to a random uniform distribution across a given address space. 199 Section 3.2 describes random uniform distributions in more detail.) 200 In practice, the actual outcome of the hash (and thus any test 201 results) will be very different depending on the degree of randomness 202 in test traffic. 204 Suppose the traffic is nonrandom so that every interface of the test 205 instrument uses this pattern in its source MAC addresses: 207 00:00:PP:00:00:01 208 where PP is the source interface number of the test instrument. 210 In this case, the least significant 3 bits of every source and 211 destination MAC address are 001, regardless of interface number. 212 Thus, the outcome of the XOR operation will always be 0, given the 213 same three least significant bits: 215 001 ^ 001 = 000 217 Thus, the switch will assign all traffic to NP0, leaving the other 218 seven NPs idle. Given a heavy enough load, NP0 and the switch will 219 become congested, even though seven other NPs are available. At 220 most, this device will be able to utilize approximately 12.5 percent 221 of its total capacity, with the remaining 87.5 percent of capacity 222 unused. 224 Now consider the same example with randomly distributed addresses. 225 In this case, the test instrument offers traffic using MAC addresses 226 with this pattern: 228 00:00:PP:00:00:RR 230 where PP is the source interface number of the test instrument and RR 231 is a pseudorandom number. In this case, there should be an equal 232 probability of the least significant 3 bits of the MAC address having 233 any value from 000 to 111 inclusive. Thus, the outcome of XOR 234 operations should be equally distributed from 0 to 7, and 235 distribution across NPs should also be equal (at least for this 236 particular 3-bit hashing algorithm). Absent other impediments, the 237 device should be able to utilize 100 percent of available bandwidth. 239 This simple example presumes knowledge on the tester's part of the 240 hashing algorithm used by the device under test. Knowledge of such 241 algorithms is not always possible beforehand, and in any event 242 violates the "black box" spirit of many documents produced by the 243 IETF BMWG. 245 Therefore, this memo adds a new consideration for benchmarking 246 methodologies, to select traffic patterns that overcome the effects 247 of non-randomness regardless of the hashing algorithms in use. The 248 balance of this section offers recommendations for test traffic 249 patterns to avoid these effects, starting at the link layer and 250 working up to the application layer. 252 4.2. Ethernet MAC Addresses 254 Test traffic SHOULD use pseudorandom patterns in Ethernet addresses. 255 The following source and destination Ethernet address pattern is 256 RECOMMENDED for use when benchmarking Ethernet devices: 258 (RR & 0xFE):PP:PP:RR:RR:RR 260 where (RR & 0xFE) is a pseudorandom number bitwise ANDed with 0xFE, 261 PP:PP is the 1-indexed interface number of the test instrument and 262 RR:RR:RR is a pseudorandom number. 264 The bitwise ANDing of the high-order byte in the MAC address with 265 0xFE guarantees a non multicast address. 267 Test traffic SHOULD use PP:PP to identify the source interface number 268 of the test instrument. Such identification can be useful in 269 troubleshooting. Allocating 2 bytes of the MAC address for interface 270 identification allows for tests of up to 65,536 interfaces. A 2-byte 271 space allows for tests much larger than those currently used in 272 device benchmarking; however, tests involving more than 256 273 interfaces (fully utilizing a 1-byte space) are fairly common. 275 Note that the "PP:PP" designation refers to the source interface of 276 the test instrument, not the DUT/SUT. There are situations where the 277 DUT/SUT interface number may change during the test; one example 278 would be a test of wireless LAN roaming. By referring to the 279 (presumably static) source interface number of the test instrument, 280 test engineers can keep track of test traffic regardless of any 281 possible DUT/SUT changes. 283 Further, source interface numbers SHOULD be 1-indexed and SHOULD NOT 284 be 0-indexed. This avoids the low but nonzero probability of an 285 all-0s Ethernet address. Some devices will drop frames with all-0s 286 Ethernet addresses. 288 It is RECOMMENDED to use pseudorandom patterns in the least 289 significant 3 bytes of the MAC address. Using pseudorandom values 290 for the low-order 3 bytes means choosing one of 16.7 million unique 291 addresses. While this address space is vastly larger than is 292 currently required in lab benchmarking, it does assure more realistic 293 test traffic. 295 Note also that since only 31 of 48 bits in the MAC address have 296 pseudorandom values, there is no possibility of randomly generating a 297 broadcast or multicast value by accident. 299 4.2.1. Randomized Sets of MAC Addresses 301 It is common benchmarking practice for a test instrument to emulate 302 multiple hosts, even on a single interface. This is desirable in 303 assessing DUT/SUT scalability. 305 However, test instruments may emulate multiple MAC addresses by 306 incrementing and/or decrementing addresses from a fixed starting 307 point. This leads to situations as described above in "Address 308 Pattern Variations" where hashing algorithms produce nonoptimal 309 outcomes. 311 The outcome can be nonoptimal even if the set of addresses begins 312 with a pseudorandom number. For example, the following source/ 313 destination pairs will not be equally distributed by the 3-bit 314 hashing algorithm discussed above: 316 Source Destination 317 00:00:01:FC:B3:45 00:00:19:38:8C:80 318 00:00:01:FC:B3:46 00:00:19:38:8C:81 319 00:00:01:FC:B3:47 00:00:19:38:8C:82 320 00:00:01:FC:B3:48 00:00:19:38:8C:83 321 00:00:01:FC:B3:49 00:00:19:38:8C:84 322 00:00:01:FC:B3:4A 00:00:19:38:8C:85 323 00:00:01:FC:B3:4B 00:00:19:38:8C:86 324 00:00:01:FC:B3:4C 00:00:19:38:8C:87 326 Again working with our 3-bit XOR hashing algorithm, we get the 327 following outcomes: 329 101 ^ 000 = 101 330 110 ^ 001 = 111 331 111 ^ 010 = 101 332 000 ^ 011 = 011 333 001 ^ 100 = 101 334 010 ^ 101 = 111 335 011 ^ 110 = 101 336 100 ^ 111 = 011 338 Note that only three of eight possible outcomes are achieved when 339 incrementing addresses. This is actually the best case. 340 Incrementing from other combinations of pseudorandom address pairs 341 produces only one or two out of eight possible outcomes. 343 Every MAC address SHOULD be pseudorandom, not just the starting one. 345 When generating traffic with multiple addresses, it is RECOMMENDED 346 that all addresses use pseudorandom values. There are multiple ways 347 to use sets of pseudorandom numbers. One strategy would be for the 348 test instrument to iterate over an array of pseudorandom values 349 rather than incrementing/decrementing from a starting address. The 350 actual method is an implementation detail; in the end, any method 351 that uses multiple addresses and avoids the undesired effects of 352 address processing in the DUT/SUT will be sufficient 354 4.3. MPLS Addressing 356 Similiar to L2 switches, MPLS routers make forwarding decisions based 357 on a 20 bit MPLS label. Unless specific labels are required, it is 358 RECOMMENDED that uniformly random values between 0 and 1,048,575 be 359 used for all labels assigned by test equipment. 361 4.4. Network-layer Addressing 363 When routers make forwarding decisions based solely on destination 364 network address, there may be no potential for hashing collision of 365 source and destination addresses, as in the case of Ethernet 366 switching discussed earlier. However, the potential still exists for 367 hashing collisions to exist at the network layer, and testers SHOULD 368 take this potential into consideration when crafting the network- 369 layer contents of test traffic. 371 For example, the equal cost multipath (ECMP) feature performs load- 372 sharing across multiple links. Routers implementing ECMP may perform 373 a hash of source and destination IP addresses in assigning flows. 375 Since multiple ECMP routes by definition have the same metric, 376 routers use some other "tiebreaker" mechanism to assign traffic to 377 each link. As far as the authors are aware, there is no standard 378 algorithm for ECMP link assignment. Some implementations perform a 379 hash of all bits of the source and destination IP addresses for this 380 purpose. Others may perform a hash on one or more bytes in the 381 source and destination IP addresses. 383 Just as in the case of MAC addresses, nonrandom IP addresses can have 384 an adverse effect on the outcome of ECMP link assignment decisions. 386 When benchmarking devices that implement ECMP or any other form of 387 Layer 3 aggregation, it is RECOMMENDED to use a randomly distributed 388 range of IP addresses. In particular, testers SHOULD NOT use 389 addresses that produce the undesired effects of address processing. 390 If, for example, a DUT can be observed to exhibit high packet loss 391 when offered IP network addresses that take the form x.x.1.x/24, and 392 relatively low packet loss when the source and destination network 393 addresses take the form of x.x.R.x/24 (where R is some random value 394 between 0 and 9), test engineers SHOULD use the random pattern. 396 4.5. Transport-layer Addressing 398 Some devices with transport- or application-layer awareness use TCP 399 or UDP port numbers in making forwarding decisions. Examples of such 400 devices include load balancers and application-layer firewalls. 402 Test instruments have the capability of generating packets with 403 random TCP and UDP source and destination port numbers. Known 404 destination port numbers are often required for testing application- 405 layer devices. However, unless known port numbers are specifically 406 required for a test, it is RECOMMENDED to use randomly distributed 407 values for both source and destination port numbers. 409 In addition, it may be desirable to pick pseudorandom values from a 410 selected pool of numbers. Many services identify themselves through 411 use of reserved destination port numbers between 1 and 1023 412 inclusive. Unless specific port numbers are required, it is 413 RECOMMENDED to pick randomly distributed destination port numbers 414 between these lower and upper boundaries. 416 Similarly, clients typically choose source port numbers in the space 417 between 1024 and 65535 inclusive. Unless specific port numbers are 418 required, it is RECOMMENDED to pick randomly distributed source port 419 numbers between these lower and upper boundaries. 421 4.6. Application-layer Patterns 423 Many measurements require the insertion of application-layer 424 header(s) and payload into test traffic. Application-layer packet 425 contents offer additional opportunities for stuffing to occur, and 426 may also present nonrandom outcomes when fed through application 427 layer-aware hashing algorithms. Given the vast number of 428 application-layer protocols in use, we make no recommendation for 429 specific test traffic patterns to be used; however, test engineers 430 SHOULD be aware that application-layer traffic contents MAY produce 431 nonrandom outcomes with some hashing algorithms. The same issues 432 that apply with lower-layer traffic patterns also apply at the 433 application layer. As discussed in section 5, the potential for 434 stuffing exists with any part of a test packet, including 435 application-layer contents. For example, some traffic generators 436 insert fields into packet payloads to distinguish test traffic. 437 These fields may contain a transmission timestamp; sequence number; 438 test equipment interface identifier and/or "stream" number; and a CRC 439 over the contents of the test payload or test packet. All these 440 fields are potential candidates for stuffing. 442 5. Control Character Stuffing 444 5.1. Problem Statement 446 Link-layer technologies that use HDLC-like framing may insert an 447 extra bit or byte before each instance of a control character in 448 traffic. These insertions prevent confusion with control characters, 449 but they may also introduce significant overhead. 451 The overhead of these escape sequences is problematic for two 452 reasons. First, explictly calculating the amount of overhead can be 453 non-trivial or even impossible for certain types of test traffic. In 454 such cases, the best testers can do is to characterize the 455 probability that an escape sequence will occur for a given pattern. 456 This greatly complicates the requirement of declaring exactly how 457 much traffic is offered to a DUT/SUT. 459 Second, in the absence of characterization and compensation for this 460 overhead, the tester may unwittingly congest the DUT/SUT. For 461 example, if a tester intends to offer traffic to a DUT at 95 percent 462 of line rate, but the link-layer protocol introduces an additional 1 463 percent of overhead to escape control characters, then the aggregate 464 offered load will be 96 percent of line rate. If the DUT's actual 465 channel capacity is only 95 percent, congestion will occur and the 466 DUT will drop traffic even though the tester did not intend this 467 outcome. 469 As described in [RFC1661] and [RFC1662], PPP and HDLC-like framing 470 introduce two kinds of escape sequences: bit and byte stuffing. Bit 471 stuffing refers to the insertion of an escape bit on bit-synchronous 472 links. Byte stuffing refers to the insertion of an escape byte on 473 byte-synchronous links. We discuss each in turn. 475 5.2. PPP Bit Stuffing 477 [RFC1662], section 5.2 specifies that any sequence of five contiguous 478 "1" bits within a frame must be escaped by inserting a "0" bit prior 479 to the sequence. This escaping is necessary to avoid confusion with 480 the HDLC control character 0x7E, which contains six "1" bits. 482 Consider the following PPP frame containing a TCP/IP packet. Not 483 shown is the 1-byte flag sequence (0x7E), at least one of which must 484 occur between frames. 486 The contents of the various frame fields can be described one of 487 three ways: 489 1. Field contents never change over the test duration. An example 490 would be the IP version number. 492 2. Field contents change over the test duration. Some of these 493 changes are known prior to the test duration. An example would 494 be the use of incrementing IP addresses. Some of these changes 495 are unknown. An example would be a dynamically calculated field 496 such as the TCP checksum. 498 3. Field contents may not be known. An example would be proprietary 499 payload fields in test packets. 501 In the diagram below, 30 out of 48 total bytes in the packet headers 502 are subject to change over the test duration. Additionally, the 503 payload field could be subject to change both content and size. The 504 fields containing the changeable bytes are given in ((double 505 parentheses)). 507 0 1 2 3 508 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 509 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 510 | Address | Control | Protocol | 511 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 512 |Version| IHL |Type of Service| Total Length | 513 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 514 | Identification |Flags| Fragment Offset | 515 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 516 | Time to Live | Protocol | ((Header Checksum)) | 517 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 518 | ((Source Address)) | 519 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 520 | ((Destination Address)) | 521 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 522 | ((Source Port)) | ((Destination Port)) | 523 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 524 | ((Sequence Number)) | 525 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 526 | ((Acknowledgment Number)) | 527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 528 | Data | |U|A|P|R|S|F| | 529 | Offset| Reserved |R|C|S|S|Y|I| ((Window)) | 530 | | |G|K|H|T|N|N| | 531 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 532 | ((Checksum)) | Urgent Pointer | 533 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 534 | | 535 / ((payload)) / 536 | | 537 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 538 | ((FCS (4 bytes) )) | 539 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 541 None of the other fields are known to contain sequences subject to 542 bit-stuffing, at least not in their entirety. Note that there is no 543 payload in this simple example; as noted in section 4.6, the payload 544 contents of test traffic often will present additional opportunities 545 for stuffing to occur, and MUST be taken into account when 546 calculating stuff probability. 548 Given the information at hand, and assuming static contents for the 549 rest of the fields, the challenge is to determine the probability 550 that bit-stuffing will occur. 552 5.2.1. Calculating Bit-Stuffing Probability 554 In order to calculate bit-stuffing probabilities, we assume that for 555 any string of length L, where b_n represents the "n"th bit of the 556 string and 1 <= n <= L, the probability of b_n equalling "1" is 0.5 557 and the probability of b_n equalling "0" is 0.5. Additionally, the 558 value of b_n is independent of any other bits. 560 We can calculate the probability of bit-stuffing for both infinite 561 and finite strings of random bits. We begin with the infinite-string 562 case. For an infinitely long string of uniformly random bits, we 563 will need to insert a stuff bit if and only if state 5 is reached in 564 the following state table. 566 |--------------------<----------------------| 567 | |1 568 _______ __|__ _____ _____ _____ __|__ 569 | | 1 | | 1 | | 1 | | 1 | | 1 | | 570 | start |--->| 1 |--->| 2 |--->| 3 |--->| 4 |--->| 5 | 571 |_______| |_____| |_____| |_____| |_____| |_____| 572 | | | | | | | 573 | |0 |0 |0 |0 |0 |0 574 |-<-|----<----|----<-----|----<-----|----<-----|----<-----| 576 Initially, we begin in the "start" state. A "1" bit moves us into 577 the next highest state, and a "0" bit returns us to the start state. 578 From state 5, a "1" bit takes us back to the 1 state and a "0" bit 579 returns us to "start." From this state table we can build the 580 following transition matrix: 582 \ To | 583 \ | 584 \ | 585 From \ | start 1 2 3 4 5 586 ______\|_________________________________________________ 587 start | 0.5 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 588 1 | 0.5 | 0.0 | 0.5 | 0.0 | 0.0 | 0.0 589 2 | 0.5 | 0.0 | 0.0 | 0.5 | 0.0 | 0.0 590 3 | 0.5 | 0.0 | 0.0 | 0.0 | 0.5 | 0.0 591 4 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 592 5 | 0.5 | 0.5 | 0.0 | 0.0 | 0.0 | 0.0 594 With this transition matrix we can build the following system of 595 equations. If P(x) represents the probability of reaching state x, 596 then: 598 P(start) = 0.5 * P(start) + 0.5 * P(1) + 0.5 * P(2) + 0.5 * P(3) + 599 0.5 * P(4) + 0.5 * P(5) 601 P(1) = 0.5 * P(start) + 0.5 * P(5) 602 P(2) = 0.5 * P(1) 603 P(3) = 0.5 * P(2) 604 P(4) = 0.5 * P(3) 605 P(5) = 0.5 * P(4) 607 P(start) + P(1) + P(2) + P(3) + P(4) + P(5) = 1 609 Solving this system of equations yields: 611 P(start) = 0.5 612 P(1) = 8/31 613 P(2) = 4/31 614 P(3) = 2/31 615 P(4) = 1/31 616 P(5) = 1/62 618 Thus, for an infinitely long string of uniformly random bits, the 619 probability of any individual bit causing a transition to state 5, 620 and thus causing a stuff, is 1/62. 622 5.2.2. Bit Stuffing for Finite Strings 624 For a uniformly random finite bit string of length L, we can 625 explicitly count the number of bit-stuffs in the set of all possible 626 strings of length L. This count can then be used to calculate the 627 expected number of stuffs for the string. 629 Let f(L) represent the number of bit-stuffs in the set of all 630 possible strings of length L. Clearly, for 0 <= L <= 4, f(L) = 0 as 631 there are no strings of length 5. For L >= 5, f(L) = 2^(L-5) + (L-5) 632 * 2^(L-6) + f(L-5). 634 A proof of this formula can be found in Appendix A. 636 Now, the expected number of stuffing events, E[stuffs], can be found 637 by dividing the total number of stuffs in all possible strings by the 638 total number of strings. Thus for any L, E[stuffs] = f(L) / 2^L. 640 Similiarly, the probability that any particular bit is the cause of a 641 bit-stuff can be calculated by dividing the total number of stuffs in 642 the set of all strings of length L by the total number of bits in the 643 set of all strings of length L. Hence for any L, the probability that 644 L_n, where 5 <= n <= L, caused a stuff is f(L) / (L * 2^L). 646 5.2.3. Applied Bit Stuffing 648 The amount of overhead attributable to bit-stuffing may be calculated 649 explicitly as long as the expected number of stuff bits per frame, 650 E[bit-stuffs] is known. For long uniformly random bit-strings, 651 E[bit-stuffs] may be approximated by multiplying the length of the 652 string by 1/62. 654 % overhead = E[bit-stuffs] / framesize (in bits) 656 Given that the overhead added by bit-stuffing is approximately 1 in 657 62, or 1.6 percent, it is RECOMMENDED that testers reduce the maximum 658 intended load by 1.6 percent to avoid introducing congestion when 659 testing devices using bit-synchronous interfaces (such as T1/E1, 660 DS-3, and the like). 662 The percentage given above is an approximation. For greatest 663 precision, the actual intended load SHOULD be explicitly calculated 664 from the test traffic. 666 Note that the DUT/SUT may be able to forward intended loads higher 667 than the calculated theoretical maximum rate without packet loss. 668 Such results are the result of queuing on the part of the DUT/SUT. 669 While a device's throughput may be above this level, delay-related 670 measurements may be affected. Accordingly, it is RECOMMENDED to 671 reduce offered levels by the amount of bit-stuffing overhead when 672 testing devices using bit-synchronous links. This recommendation 673 applies for all measurements, including throughput. 675 5.3. POS Byte Stuffing 677 [RFC1662] requires that "Each Flag Sequence, Control Escape octet, 678 and any octet which is flagged in the sending Async-Control- 679 Character-Map (ACCM), is replaced by a two octet sequence consisting 680 of the Control Escape octet followed by the original octet exclusive- 681 or'd with hexadecimal 0x20." The practical effect of this is to 682 insert a stuff byte for instances of up to 34 characters: 0x7E, 0x7D, 683 or any of 32 ACCM values. 685 A common implementation of PPP in HDLC-like framing is in PPP over 686 Sonet/SDH (POS), as defined in [RFC2615]. 688 As with the bit-stuffing case, the requirement in characterizing POS 689 test traffic is to determine the probability that byte-stuffing will 690 occur for a given sequence. This is much simpler to do than with 691 bit-synchronous links, since there is no possibility of overlap 692 across byte boundaries. 694 5.3.1. Nullifying ACCM 696 Testers can greatly reduce the probability of byte-stuffing by 697 configuring link partners to negotiate an ACCM value of 0x00. It is 698 RECOMMENDED that testers configure the test instrument(s) and DUT/SUT 699 to negotiate an ACCM value of 0x00 unless specific ACCM values are 700 required. 702 One instance where nonzero ACCM values are used is in the layer 2 703 tunneling protocol (L2TP), as defined in [RFC2661], section 4.4.6. 704 When the default ACCM values are used, the probability of stuffing 705 for any given random byte is 34 in 256, or approximately 13.3 706 percent. 708 5.3.2. Other Stuffed Characters 710 If an ACCM value of 0x00 is negotiated, the only characters subject 711 to stuffing are the flag and control escape characters. Thus, we can 712 say that without ACCM the probability of stuffing for any given 713 random byte is 2 in 256, or approximately 0.8 percent. 715 5.3.3. Applied Byte Stuffing 717 The amount of overhead attributable to byte stuffing may be 718 calculated explicitly as long as the expected number of stuff bytes 719 per frame, E[byte-stuffs], is known. For long uniformly random byte- 720 strings, E[byte-stuffs] may be approximated by multiplying the length 721 of the string by the probability that any single byte is a stuff 722 byte. 724 % overhead = E[byte-stuffs] / framesize (in bytes) 726 When testing a DUT/SUT that implements PPP in HDLC-like framing and 727 L2TP (or any other technology that uses nonzero ACCM values), it is 728 RECOMMENDED that testers reduce the maximum intended load by 13.3 729 percent to avoid introducing congestion. 731 When testing a DUT/SUT that implements PPP in HDLC-like framing and 732 an ACCM value of 0x00, it is RECOMMENDED that testers reduce the 733 maximum offered load by 0.8 percent to avoid introducing congestion. 735 Note that the percentages given above are approximations. For 736 greatest precision, the actual intended load SHOULD be explictly 737 calculated from the test traffic 738 Note also that the DUT/SUT may be able to forward intended loads 739 higher than the calculated theoretical maximum rate without packet 740 loss. Such results are the result of queuing on the part of the DUT/ 741 SUT. While a device's throughput may be above this level, delay- 742 related measurements may be affected. Accordingly, it is RECOMMENDED 743 to reduce offered levels by the amount of byte-stuffing overhead when 744 testing devices using byte-synchronous links. This recommendation 745 applies for all measurements, including throughput. 747 6. Security Considerations 749 This document recommends the use of pseudorandom patterns in test 750 traffic. The rand() functions of many programming languages produce 751 output that is pseudorandom rather than truly random. As far as the 752 authors are aware, pseudorandom patterns are sufficient for 753 generating test traffic in lab conditions. 755 [RFC2615], section 6, discusses a denial-of-service attack involving 756 the intentional transmission of characters that require stuffing. 757 This attack could consume up to 100 percent of available bandwidth. 758 However, the test networks described in BMWG documents generally 759 SHOULD NOT be reachable by anyone other than the tester(s). 761 7. IANA Considerations 763 This document has no actions for IANA. 765 8. References 767 8.1. Normative References 769 [RFC1661] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51, 770 RFC 1661, July 1994. 772 [RFC1662] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662, 773 July 1994. 775 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 776 Requirement Levels", BCP 14, RFC 2119, March 1997. 778 [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for 779 Network Interconnect Devices", RFC 2544, March 1999. 781 [RFC2615] Malis, A. and W. Simpson, "PPP over SONET/SDH", RFC 2615, 782 June 1999. 784 [RFC2661] Townsley, W., Valencia, A., Rubens, A., Pall, G., Zorn, 785 G., and B. Palter, "Layer Two Tunneling Protocol "L2TP"", 786 RFC 2661, August 1999. 788 [RFC2889] Mandeville, R. and J. Perser, "Benchmarking Methodology 789 for LAN Switching Devices", RFC 2889, August 2000. 791 8.2. Informative References 793 [Ca63] Campbell, D. and J. Stanley, "Experimental and Quasi- 794 Experimental Designs for Research", 1963. 796 [Go97] Goralski, W., "SONET: A Guide to Synchronous Optical 797 Networks", 1997. 799 [Kn97] Knuth, D., "The Art of Computer Programming, Volume 2, Third 800 Edition", 1997. 802 Appendix A. Acknowledgements 804 The authors gratefully acknowledge reviews and contributions by Len 805 Ciavattone, Robert Craig, John Dawson, Neil Carter, Glenn Chagnot, 806 Kevin Dubray, Rafael Francis, Paul Hoffman, David Joyner, Al Morton, 807 Joe Perches, Scott Poretsky, and Kris Rousey. 809 Appendix B. Proof of Formula for Finite Bit Stuffing 811 We would like to construct a function, f(L), that allows us to 812 explictly count the total number of bit-stuffs in the set of all 813 strings of length L. Let S represent a bit string of length L. 814 Additionally, let b_n be the nth bit of string S where 1 <= n <= L. 816 Clearly, when 0 <= L <= 4, f(L) = 0, as there can be no possible bit- 817 stuff if there are < 5 bits. 819 Suppose L >= 5, then there are some number of strings that will cause 820 stuffing events. Let us count them. 822 We begin by counting the number of strings that will cause at least 823 one bit-stuff. Let us suppose that the first 5 bits, b_1,...,b_5, 824 cause a stuffing event. Then, there are (L-5) bits that could have 825 any value, i.e. the bits in position b_6 to b_L. So, there must be 826 2^(L-5) strings where the first 5 bits cause a stuff. 828 Now suppose that some other sequence of bits cause a stuff, b_n to 829 b_(n+4) for some 1 < n <= L-4. In order to guarantee that b_n starts 830 a stuff sequence, b_(n-1) must be 0, otherwise a stuff could occur at 831 b_(n+3). Thus, there are a total of 6 bits which must have fixed 832 values in the string, S, and a total of L-6 bits which do not have 833 fixed values. Hence, for each value of n, there are 2^(L-6) possible 834 strings with at least one bit-stuff for a total of (L-5) * 2^(L-6) 836 So, given a string of length L, where L >= 5, we know that there are 837 2^(L-5) + (L-5) * 2^(L-6) strings which will be transmitted with at 838 least one stuffed bit. However, if L >= 10, then there could be more 839 than one bit-stuff within the string S. Let Z represent a sequence of 840 5 sequential ones bits. Consider the bit string ..., b_n, b_(n+1), 841 b_(n+2), Z, b_(n+8), b_(n+9), ... where 1 <= n <= L-9. For the above 842 sequence of bits to generate two stuffing events, there must be at 843 least one run of five sequential one's bits in ..., b_n, b_(n+1), 844 b_(n+2), b_(n+8), b_(n+9), ... Note that the position of Z in the 845 above squence is irrelevant when looking for bit-stuffs. 846 Additionally, we've already determined that the number of strings 847 with at least one stuff in a bit string of length L is 2^(L-5) + 848 (L-5) * 2^(L-6). Thus, the total number of stuffing events in the 849 set of all bit strings of length L can be represented as f(L) = 850 2^(L-5) + (L-5) * 2^(L-6) + f(L-5) for all L >= 5. 852 Appendix C. Explicit Calculation of Bit Stuffing Overhead 854 Consider a scenario where a tester is transmitting test frames across 855 a bit synchronous link. The test traffic has the following 856 parameters (values are in decimal): 858 +----------------------+-----------------------------+ 859 | Field | Value | 860 +----------------------+-----------------------------+ 861 | IP Version | 4 | 862 | | | 863 | IP Header Length | 5 | 864 | | | 865 | TOS | 0 | 866 | | | 867 | Datagram Length | 1028 | 868 | | | 869 | ID | 0 | 870 | | | 871 | Flags/Fragments | 0 | 872 | | | 873 | TTL | 64 | 874 | | | 875 | Protocol | 17 | 876 | | | 877 | Source IP | 192.168.13.1-192.168.13.254 | 878 | | | 879 | Destination IP | 192.168.1.10 | 880 | | | 881 | Source UDP Port | pseudorandom port | 882 | | | 883 | Destination UDP Port | pseudorandom port | 884 | | | 885 | UDP Length | 1008 | 886 | | | 887 | Payload | 1000 pseudorandom bytes | 888 +----------------------+-----------------------------+ 890 We want to calculate the expected number of stuffs per packet, or 891 E[packet stuffs]. 893 First, we observe that we have 254 different IP headers to consider, 894 and secondly, that the changing 4th octet in the IP source addresses 895 will produce occasional bit-stuffing events, so we must enumerate 896 these occurances. Additionally, we must take into account that the 897 3rd octet of the source IP and the first octet of the destination IP 898 will affect stuffing occurences. 900 An exhaustive search shows that cycling through all 254 headers 901 produces 51 bit stuffs for the destination IP address. This gives us 902 an expectation of 51/254 stuffs per packet due to the changing source 903 IP address. 905 For the IP CRC, we observe that the value will decrement as the 906 source IP is incremented. A little calculation shows that the CRC 907 values for these headers will fall in the range of 0xE790 to 0xE88F. 908 Additionally, both the protocol and source IP address must be 909 considered, as they provide a source of extra leading and trailing 910 ones bits. 912 An exhaustive search shows that cycling through all 254 headers will 913 produce 102 bit stuffs for the CRC. This gives us an expectation of 914 102/254 stuffs per packet due to the CRC. 916 Since our destination IP address is even and the UDP length is less 917 than 32768, the random source and destination ports provide 32 bits 918 of sequential random data without forcing us to consider the boundry 919 bits. Additionally, we will assume that since our payload is 920 pseudorandom, our UDP CRC will be too. The even UDP length field 921 again allows us to only consider the bits explicitly contained within 922 the CRC and data fields. So, using the forumla for the expected 923 number of stuffs in a finite string from section 5.2.2, we determine 924 that E[UDP stuffs] = f(32)/2^32 + f(8000+16)/2^(8000+16). Now, 925 f(32)/2^32 is calculatable without too much difficulty and is 926 approximately 0.465. However, f(8016)/2^8016 is a little large to 927 calculate easily, so we will approximate this value by using the 928 probability value obtained in section 5.2.1. Thus, E[UDP] ~ 0.465 + 929 8016/62 ~ 129.755. 931 Hence, E[packet stuffs] = 51/254 + 102/254 + 129.755 = 130.357. 932 However, since we cannot have a fractional stuff, we round down to 933 130. Thus, we expect 130 stuffs per packet. 935 Finally, we can calculate bit-stuffing overhead by dividing the 936 expected number of stuff bits by the total number of bits in the IP 937 datagram. So, this example traffic would generate 1.58% overhead. 938 If our payload had consisted exclusively of zero bits, our overhead 939 would have been 0.012%. An all ones payload would produce 19.47% 940 overhead. 942 Authors' Addresses 944 David Newman 945 Network Test 947 Email: dnewman@networktest.com 949 Timmons C. Player 950 Spirent Communications 952 Email: timmons.player@spirentcom.com 954 Intellectual Property Statement 956 The IETF takes no position regarding the validity or scope of any 957 Intellectual Property Rights or other rights that might be claimed to 958 pertain to the implementation or use of the technology described in 959 this document or the extent to which any license under such rights 960 might or might not be available; nor does it represent that it has 961 made any independent effort to identify any such rights. Information 962 on the procedures with respect to rights in RFC documents can be 963 found in BCP 78 and BCP 79. 965 Copies of IPR disclosures made to the IETF Secretariat and any 966 assurances of licenses to be made available, or the result of an 967 attempt made to obtain a general license or permission for the use of 968 such proprietary rights by implementers or users of this 969 specification can be obtained from the IETF on-line IPR repository at 970 http://www.ietf.org/ipr. 972 The IETF invites any interested party to bring to its attention any 973 copyrights, patents or patent applications, or other proprietary 974 rights that may cover technology that may be required to implement 975 this standard. Please address the information to the IETF at 976 ietf-ipr@ietf.org. 978 Disclaimer of Validity 980 This document and the information contained herein are provided on an 981 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 982 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 983 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 984 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 985 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 986 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 988 Copyright Statement 990 Copyright (C) The Internet Society (2006). This document is subject 991 to the rights, licenses and restrictions contained in BCP 78, and 992 except as set forth therein, the authors retain all their rights. 994 Acknowledgment 996 Funding for the RFC Editor function is currently provided by the 997 Internet Society.